实验3 有序链表操作
|
【编译工具及其版本】 |
VScode，mingw3.0 |
【结论分析、实验体会(去除重复，最少60个汉字)】 本题要求实现有序链表以及其操作。整体思路不难但是具体实现起来有很多细节需要注意，首先确认自己不是看着ppt或者书来实现的，否则会有很多东西被自己忽略掉。首先是在确认链表的结构的时候，我们必然要定义一个Node结点类这个是链表的基本组成元素，然后就会遇到第一个问题——既然Node是元素那么我们需不需要定义一个类称为Nodelist代表链表里面包含元素Node。我一开始是这么想的，但是在思考一段时间后否认了这样的想法理由如下：NodeList的本质是一个指针。这句话的意思就是链表是没有长度概念的，也就是说链表可以无限增加。那么我们定义一个新的链表的本质操作就是给他一个开头就是给他一个指向Node的指针，那么这个链表就是被创建了。有了这个想法不难推出，既然创建链表就是创建一个新的Node指针，那么我们便不需要重新建立一个类放NodeList，因为它和Node没有本质的区别。所以我们选用的是给Node*一个别名叫做NodeList，这样子我们创建一个NodeList就是创建一个指向Node的指针也就是创建了一个新的链表。 接下来我遇到的问题都是出在细节上：
|
#include <iostream> using namespace std; struct Node { int data; Node* next; }; typedef Node* NodeList; NodeList createSortedNodeList(int num[]) { NodeList head = new Node; head->data = -1; head->next = nullptr; for (int i = 0; num[i] != 0; i++) { Node* newNode = new Node; newNode->data = num[i]; newNode->next = nullptr; Node* prev = head; Node* current = head->next; while (current != nullptr && current->data < newNode->data) { prev = current; current = current->next; } prev->next = newNode; newNode->next = current; } return head; } void printNodeList(NodeList head) { if(head->next==NULL){ cout<<"<null>"<<endl; } else{ Node* current = head->next; while (current != nullptr) { cout << current->data; if (current->next != nullptr) { cout << ","; } current = current->next; } cout << endl; } } NodeList merge(NodeList list1, NodeList list2) { NodeList result = new Node; result->data = -1; result->next = nullptr; Node* endNode = result; Node* a = list1->next; Node* b = list2->next; while (a && b) { if (a->data < b->data) { endNode->next = new Node; endNode->next->data = a->data; endNode->next->next = nullptr; a = a->next; } else { endNode->next = new Node; endNode->next->data = b->data; endNode->next->next = nullptr; b = b->next; } endNode = endNode->next; } while (a) { endNode->next = new Node; endNode->next->data = a->data; endNode->next->next = nullptr; a = a->next; endNode = endNode->next; } while (b) { endNode->next = new Node; endNode->next->data = b->data; endNode->next->next = nullptr; b = b->next; endNode = endNode->next; } return result; } NodeList insert(NodeList list1, int data) {//存在两个特殊情况：空链表以及只有一个元素时 Node* newNode = new Node; newNode->data = data; newNode->next = NULL; if (list1->next == NULL) { list1->next = newNode;//空链表特殊处理 } else { Node* t = list1->next;//决定了空链表不行。同时直接到第一个元素上导致插入元素小于它时出问题 if (data < t->data) { newNode->next = t; list1->next = newNode; } else { while (t->next != NULL && t->next->data <= data) { t = t->next; } newNode->next = t->next; t->next = newNode; } } return list1; } NodeList deleteNumber(NodeList list1, int data) {//两个特殊情况：空链表，只有一个元素的链表 Node* t = list1->next; if (t == NULL) { return list1; } if (t->data == data) { list1->next = t->next; delete t; return list1; } while (t->next != NULL && t->next->data != data) {//决定考虑空链表 t = t->next; } if (t->next != NULL) { Node* a = t->next; t->next = a->next;//这里决定特殊情况有只有一个元素的情况 delete a; } return list1; } int positonFind(NodeList list1,int data){ if(list1->next==nullptr) return 0; else{ int count=1; Node* t=list1->next;//决定空链表是特殊情况 if(t->next==nullptr){ if(t->data!=data) return 0; else return 1; } else{ while(t!=NULL&&t->data!=data){//决定一个元素且元素值不等于data时会出问题 t=t->next; count++; } if(t->data!=data) count=0; return count; } } } int main() { NodeList nodeList1; int num1[50] = {0}; int t, count = 0; int insertNum,deleteNum,findNum=0; cout << "Input1" << endl; cin >> t; while (t != 0) { num1[count++] = t; cin >> t; } cout << "Output1" << endl; nodeList1 = createSortedNodeList(num1); printNodeList(nodeList1); NodeList nodeList2; int num2[50] = {0}; count = 0; cout <<"Input2"<< endl; cin >> t; while (t != 0) { num2[count++] = t; cin >> t; } cout << "Output2" << endl; nodeList2 = createSortedNodeList(num2); printNodeList(nodeList2); NodeList mergedList = merge(nodeList1, nodeList2); cout <<"Combine"<< endl; printNodeList(mergedList); cout<<"Insert"<<endl; cin>>insertNum; Node* InsertionList=insert(mergedList,insertNum); cout<<"Insertion"<<endl; printNodeList(InsertionList); cout<<"Delete"<<endl; cin>>deleteNum; Node* deletetionList=deleteNumber(InsertionList,deleteNum); cout<<"Deletion"<<endl; printNodeList(deletetionList); cout<<"Find"<<endl; cin>>findNum; int potion=positonFind(deletetionList,findNum); cout<<"Position"<<endl; cout<<potion<<endl; cout<<"End"<<endl; return 0; }
