链表实现

此程序所写链表，删除功能只能在表尾每次删除一个学生，可在任意合理范围内根据key值插入学生，并打印消息。在查找某个学生位置时，可以考虑写一个search函数，本文在各个函数内直接查找，代码略显冗余。后期有空改进。

list.h

#ifndef LIST_H_ #define LIST_H_ #include "string" #include "iostream" using namespace std; typedef struct info //保存的学生信息 { string name; string number; }information; typedef struct stu //学生个体 { struct stu* prev; //指向前一个学生 int key; //学生位置 information name_num; //学生信息 struct stu* next; //指向后一个学生 }student; class list { public: list(); ~list(); void insert(string name,string number,int k); //插入函数，可在队列任意位置插入学生 void deletee(); //删除函数，删除表尾学生 void show() const; //显示链表上学生信息 private: student* head; //链表头 int key; //生成每个学生序号 }; #endif

list.cpp

#include "list.h" list::list() //初始化 { head=nullptr; //初始时无学生，链表头指向空 key=0; //无学生，key为0 } void list::insert(string name,string number,int k) //插入函数，可在队列任意位置插入学生 { ++key; if(k<1 || k>key) //输入K不在链表范围内 { cout<<"无此位置，请重新输入！"; return; } else if(k==1) //插入到第一个位置 { if(head==nullptr) //无学生 { head=new student; (*head).key=key; (*head).name_num.name=name; (*head).name_num.number=number; (*head).prev=nullptr; (*head).next=nullptr; } else //有学生 { (*head).prev=new student; //第一个学生前边new一个学生 (*(*head).prev).next=head; (*(*head).prev).prev=nullptr; (*(*head).prev).key=k; (*(*head).prev).name_num.name=name; (*(*head).prev).name_num.number=number; head=(*head).prev; //指向新的第一个学生 student* empty=head; //更新所有学生的key for(int i=0;i<key;++i) { (*empty).key=i+1; empty=(*empty).next; } } } else if(k>1 && k==key) //插入到最后一个位置(>1) { student* empty = head; while((*empty).next!=nullptr) //指向下一个学生的指针，如果不为空，则指向下一个同学 { empty=(*empty).next; } (*empty).next=new student; //最后一个学生的next指向一个新new的学生 (*(*empty).next).name_num.name=name; (*(*empty).next).name_num.number=number; (*(*empty).next).key=key; (*(*empty).next).next=nullptr; (*(*empty).next).prev=empty; } else //插入到中间位置 { student* empty = head; while((*empty).key!=k-1) //empty指向插入位置的前一个学生 { empty=(*empty).next; } student* dempty =(*empty).next; //dempty指向插入位置的后一个学生 (*empty).next=new student; (*(*empty).next).name_num.name=name; (*(*empty).next).name_num.number=number; (*(*empty).next).key=key; (*(*empty).next).prev=empty; (*(*empty).next).next=dempty; (*dempty).prev=(*empty).next; empty=head; //更新所有学生的key for(int i=0;i<key;++i) { (*empty).key=i+1; empty=(*empty).next; } } } void list::deletee() //删除函数，删除表尾学生 { if(key==0) //如果无学生，报错 { cout<<"No student can be delete!"<<endl; } else if(key==1) //如果只有一个学生，直接删 { delete head; head=nullptr; --key; } else { student* empty = head; while((*empty).next!=nullptr) //如果下一个学生不为空，则指向下一个同学 { empty=(*empty).next; } empty=(*empty).prev; // 删除表尾学生 delete (*empty).next; (*empty).next=nullptrL; --key; } } void list::show( ) const //显示链表上学生信息 { if(key==0) //如果key=0，说明链表上无学生 cout<<"No student!"<<endl; else { student* empty = head; cout<<"key: "<<(*empty).key<<" 姓名: "<<(*empty).name_num.name<<" 学号: "<<(*empty).name_num.number<<endl; //输出第一个学生的信息 while((*empty).next!=nullptr) //如果下一个学生不为空，则输出下一个学生信息， { empty=(*empty).next; cout<<"key: "<<(*empty).key<<" 姓名: "<<(*empty).name_num.name<<" 学号: "<<(*empty).name_num.number<<endl; } } }

main.h

#include "list.h" int main() { list student_list; student_list.show(); cout<<endl; student_list.insert("范冰冰","010308",1); student_list.show(); cout<<endl; student_list.insert("黄晓明","010305",2); student_list.show(); cout<<endl; student_list.insert("赵丽颖","010302",1); student_list.show(); cout<<endl; student_list.insert("吴彦祖","010301",2); student_list.show(); cout<<endl; student_list.deletee(); student_list.show(); cout<<endl; student_list.deletee(); student_list.show(); cout<<endl; student_list.insert("古天乐","010312",3); student_list.show(); cout<<endl; return 0; }

运行结果：