数据结构学年设计：创建线性表链式存储类MyLinkList

题目：
创建线性表链式存储类MyLinkList
目的：通过对线性表链式存储类的创建和应用，增强面向对象程序设计和链表的理解与应用实践。
内容：（1）MyLinkList提供创建多种类型链表，包括：单链表、双链表，单循环链表，双循环链表。
（2） 提供初始化数据功能（即创建该对象时可以通过指定数组将初始参数传入该对象）
（3）提供插入一个元素功能；
（4）提供删除一个元素功能；
（5）提供根据指定关键字排序功能；（默认升序，也能降序，提供用户自己选择方式。）
（6）提供根据指定关键字查找功能，查找结果返回该元素指针，NULL表示查找失败。
（7）提供两个有序顺序表合并功能；
（8）提供根据指定关键字，返回指定第K大的元素指针；
（9）提供输出显示链表中各个元素功能；
（10）提供释放指定对象功能；
（11）给出各个功能的测试样例。

#include
#include
#include
#include
#include
using namespace std;typedef struct Node
{int data;//学生成绩int no;//学生学号struct Node* next;//指针域
}Node;typedef struct Node* PtrToNode;
typedef PtrToNode Position;
typedef PtrToNode MyArrayList;//初始化
void init(MyArrayList& L, vector<Node> student)
{/*//头插法初始化，但输入数据和输出数据顺序相反for (int i = 0; i < N; i++)addList(L, student[i].data, student[i].no);*///下面用尾插法数据输入，输入的数据和输出的数据顺序一致MyArrayList tail;tail = L;for (unsigned i = 0; i < student.size(); i++){PtrToNode tmpcell = (PtrToNode)malloc(sizeof(struct Node));if (tmpcell == NULL)cout << "申请空间失败！" << endl;else{tmpcell->data = student[i].data;tmpcell->no = student[i].no;tail->next = tmpcell;tail = tmpcell;}}tail->next = NULL;cout << "初始化成功！" << endl;cout << "学生成绩信息导入成功！" << endl;
}//创建链表
MyArrayList createList()
{MyArrayList L = (PtrToNode)malloc(sizeof(struct Node));if (L == NULL)cout << "分配内存空间失败！" << endl;elseL->next = NULL;return L;
}//插入学生到链表
void addStudent(MyArrayList& L, int e, int n)
{MyArrayList tmpcell = (PtrToNode)malloc(sizeof(struct Node));if (tmpcell == NULL)cout << "分配内存失败" << endl;else{//头插法将数据插入tmpcell->data = e;tmpcell->no = n;tmpcell->next = L->next;L->next = tmpcell;}
}//按学号删除学生信息
void deleteNode(MyArrayList L, int n)
{Position p = L->next;Position tmpcell;if (p->no == n){tmpcell = p;L->next = p->next;free(tmpcell);}else{while (p){if (p->next->no == n){tmpcell = p->next;p->next = p->next->next;free(tmpcell);break;}p = p->next;}}
}//用于清空链表
void Clear(MyArrayList& L)
{Position tmp;Position p = L->next;L->next = NULL;while (p!=NULL){tmp = p->next;free(p);p = tmp;}
}//sort函数中的回调函数
bool cmp(Node x, Node y)
{return x.data < y.data;
}//按成绩对学生排序
void sortList(MyArrayList& L1, MyArrayList& L2)
{Position p = L1->next;vector<Node> stu_arr;while (p){  Node stu;stu.data = p->data;stu.no = p->no;stu_arr.push_back(stu);p = p->next;}sort(stu_arr.begin(), stu_arr.end(), cmp);Clear(L1);//清空L1链表中的数据for (unsigned i = 0; i < stu_arr.size(); i++)addStudent(L1, stu_arr[i].data, stu_arr[i].no);cout << "按成绩高到低排序成功！" << endl;
}//合并两个链表信息
void mergeList(MyArrayList& L1, MyArrayList& L2, MyArrayList& L3)
{Position p = L1->next;Position q = L2->next;Clear(L3);while (p){addStudent(L3, p->data, p->no);p = p->next;}while (q){addStudent(L3, q->data, q->no);q = q->next;}Clear(L1);Position r = L3->next;while (r){addStudent(L1, r->data, r->no);r = r->next;}//L1->next = L3->next;cout << "合并成功！" << endl;
}//打印输出学生信息
void printList(MyArrayList& L)
{cout << setw(3) << "学号" << setw(8) << "成绩" << endl;Position p = L->next;while (p){cout<<setw(2) << p->no << setw(8)<< p->data << endl;p = p->next;}
}//输出对应学号的学生的信息
void Find(MyArrayList& L, int n)
{bool f = true;Position p = L->next;while (p){if (p->no == n){cout << "该生的学号：" << n << endl << "该生的成绩：" << p->data << endl;f = false;}p = p->next;}if (f)cout << "-1" << endl;
}//找到成绩排名K的学生的信息
void Findkth(MyArrayList& L, int k)
{Position p = L->next;vector<Node> stu_arr;while (p){Node stu;stu.data = p->data;stu.no = p->no;stu_arr.push_back(stu);p = p->next;}sort(stu_arr.begin(), stu_arr.end(), cmp);cout << "第" << k << "名的信息：" << endl;cout << setw(3) << "学号" << setw(8) << "成绩" << endl;cout << setw(2) << stu_arr[stu_arr.size() - k].no << setw(8) << stu_arr[stu_arr.size() - k].data << endl;}void ShowMenu()
{cout << "|----------------------------------|" << endl;cout << "           (1)初始化                     " << endl;cout << "           (2)插入记录                     " << endl;cout << "           (3)删除记录                   " << endl;cout << "           (4)排序记录                   " << endl;cout << "           (5)查找记录                     " << endl;cout << "           (6)合并记录                     " << endl;cout << "           (7)返回第K大元素                     " << endl;cout << "           (8)显示数据                     " << endl;cout << "           (9)退出                    " << endl;cout << "|-----------------------------------|" << endl;cout << endl;
}int main()
{MyArrayList L = createList();MyArrayList L2 = createList();MyArrayList L3 = createList();MyArrayList L4 = createList();//将数据输入到文件中ofstream output;output.open("student.txt");srand(unsigned(time(0)));for (int i = 1; i <= 100; i++)output << i << " " << rand() % 100 << endl;output.close();//将数据从文件中读取，存到数组当中vector<Node> studentB;ifstream input;input.open("student.txt");Node stu;input >> stu.no >> stu.data;while (!input.eof()){studentB.push_back(stu);input >> stu.no >> stu.data;}input.close();//给L3填充数据for (int i = 0; i < 3; i++)addStudent(L3, 8, 3);ShowMenu();char in;//输入进行选择do{cin >> in;switch (in)//输入进行选择功能{case '1':init(L, studentB);//system("cls");//清屏//ShowMenu();break;case '2':int score1;//输入学生的分数int n;//输入学生的学号cout << "请输入学生的学号：";cin >> n;cout << "请输入学生的分数：";cin >> score1;addStudent(L, score1, n);system("cls");ShowMenu();break;case '3':cout << endl << "请输入学生学号：";int m;//学生学号cin >> m;deleteNode(L, m);system("cls");ShowMenu();break;case '4':sortList(L, L2);break;case '5':cout << "请输入查找学生的学号：";int xh2;cin >> xh2;Find(L, xh2);break;case '6':mergeList(L, L3, L4);break;case '7':int k;cout << "请输入K值来查找：";cin >> k;Findkth(L, k);break;case '8':printList(L);break;case '9':break;default:cout << "输入错误，请重新输入。" << endl;}} while (in != '9');//输入9退出程序*/return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！