如何按数字顺序插入链表节点?

Question

我已经非常接近完成学校的链表作业，但正在为最后一个功能而苦苦挣扎。此函数的目的是从文本文件中读取的数字，并按数字顺序将它们放入链表中。我试图让它遍历列表的位置，每当值大于前一个数字但达到分段错误时，就会添加节点。我已经尴尬地坚持了很长时间，并希望任何人的帮助。下面是我正在使用的文件以及一个名为insertStrategy的函数的可怕混乱，该函数应该按数字顺序获取列表。

主要

#include "linkedlist.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
int main (){
NodePtr newNode = NULL;
// after you implemented your functions in .cpp file 
// - use the code below for testing your linked list. 
// Demonstrate that ALL functions are working correctly.
// After that add code for reading data from input file.
// Every time you read an integer, create a node and insert it
// in the ascending order into the list.
int num;
FILE *fptr;
// make sure file exists, give message and exit otherwise
if ((fptr = fopen("input.txt","r")) == NULL){
printf("Error! opening file");
exit(1);
}
// while we still have items to read
while( fscanf(fptr,"%d", &num) != EOF){
newNode = makeNewNode(num);
insertStrategic(newNode);
}
fclose(fptr);  // close the file  
// At the end print the entire list to show that your code 
// functions correctly.

printList();
cout << "After DeleteFromFront: " << endl; 
deleteFromFront();
printList();
NodePtr seven = makeNewNode(7);     
insertAtEnd(seven);
cout <<"Inserting seven at END" << endl;
printList();
NodePtr eight = makeNewNode(8);     
insertAtEnd(eight);
cout <<"Inserting eight at END" << endl;
printList();
cout << "After deleting eight: " << endl; 
deleteFromEnd();
printList();
cout << "After deleting seven:" << endl;
deleteFromEnd();
printList();

return 0;
}

链表文件

#include "linkedlist.h"
#include <stdlib.h>
#include <iostream>

using namespace std;
NodePtr head = NULL;
NodePtr tail = NULL;

bool isEmpty(){
return (head == NULL);
}
NodePtr makeNewNode(int number){
NodePtr newNode = (NodePtr) malloc(sizeof(Node));
if(newNode != NULL){
newNode->data = number;
newNode->next = NULL;
}
return newNode;
}
void insertAtFront(const NodePtr newPtr){
if (isEmpty()){
head = newPtr;
tail = newPtr;
}
else{ // not empty
newPtr->next = head;
head = newPtr;
}
}
void insertAtEnd(const NodePtr newPtr){
NodePtr end = head;
newPtr->next = NULL;
while (end->next != NULL){
end = end->next; 
}
end->next = newPtr; 
}

void insertStrategic(const NodePtr newPtr){
if (isEmpty()){
head = newPtr;
tail = newPtr;
}
else {
NodePtr traverse = head;
newPtr->next = NULL;
while ((traverse->next = NULL)){
while ((traverse->data < newPtr->data)){
traverse = traverse->next;
}
traverse = traverse->prev;
traverse->next = newPtr;
break;
}
} 
}   
void deleteFromFront( ){
NodePtr temp = head;
head = head->next;
}
void deleteFromEnd( ){
NodePtr temp = head;
NodePtr secTemp;
while(temp->next != NULL) {
secTemp = temp;
temp = temp->next;
}
free(secTemp->next);
secTemp->next = NULL;  
}

void printList( ){
if (isEmpty()){
cout << "List is empty" << endl;
}
else {
NodePtr temp = head;
while (temp != NULL){
cout << " The data is: " << temp->data << endl;
temp = temp->next;
}
}
}

头文件

#ifndef MYLIST_H
#define MYLIST_H
#include <cstddef>
struct listNode {
int data;
struct listNode* prev;
struct listNode* next;
};
typedef struct listNode Node;
typedef Node* NodePtr;

static int nodeCount = 0;
bool isEmpty();
NodePtr makeNewNode(int); 
void insertAtFront(const NodePtr);
void insertAtEnd(const NodePtr);
void insertStrategic(const NodePtr);
void deleteFromFront( );
void deleteFromEnd( );
void printList();

#endif

要读入的文本文件

3
5
11
2
7
1
65
12
3
45
6

Answer 1

下面是一个简单的解决方案，可能不是最好的，但有效。此函数将按升序插入元素。

请注意，我们不会在此函数中更新列表的"尾部"。

void insertOrdered(const NodePtr newPtr){
if (isEmpty()){
head = newPtr;
return;
}
NodePtr lastNode, whereToInsert = head;
while (whereToInsert){
if (whereToInsert->data > newPtr->data){
break;
}
lastNode = whereToInsert;
whereToInsert = whereToInsert->next;
}
if (whereToInsert == head){
newPtr->next = head;
head->prev = newPtr;
head = newPtr;
}
else if (whereToInsert) {
newPtr->next = whereToInsert;
whereToInsert = whereToInsert->prev;
newPtr->prev = whereToInsert;
whereToInsert->next = newPtr;
}
else {
lastNode->next = newPtr;
newPtr->prev = lastNode;
}
}

另外，请避免使用以下代码：

if ((fptr = fopen("input.txt","r")) == NULL){

请改用单独的代码行：

fptr = fopen("input.txt","r")
if (fptr == NULL){ /* your stuff */ } 

Answer 2

你可以在 insertStrategic(( 中写这样的东西; 2 次 虽然 是不需要的

while ((traverse->next != NULL)){
if(traverse->data < newPtr->data)){
traverse = traverse->next;
}
else{
traverse->prev->next = newPtr;
newPtr->next = traverse;
break;
}
}