（含有头结点以及尾结点）单链表各类功能的实现

void InitList(List *list); //初始化单链表 bool push_back(List *list,ElemType x); //尾插法 void show_seqlist(List *list); //显示链表内容 bool push_front(List *list,ElemType x);//头插法 bool pop_back(List *list); //尾删法 bool pop_front(List *list); //头删法 Node *find(List *list,ElemType x); //查找函数，找到返回指向该元素的指针 bool modify(List *list,ElemType x); //修改某1元素的值 void delete_val(List *list,ElemType x);//按值删除 void clear(List *list); //清空链表 void destroy(List *list); //烧毁链表 int length(List *list); //求链表长度 void resver(List *list); //逆至链表 void prio(List *list,ElemType x); //求某个值的先驱 void next(List *list,ElemType x); //求某个值的后继

#ifndef __LIST_H__ #define __LIST_H__ #include<assert.h> #include<iostream> using namespace std; typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; }Node; typedef struct List { Node *first; Node *last; int size; }List; void InitList(List *list); //初始化单链表 bool push_back(List *list,ElemType x); //尾插法 void show_seqlist(List *list); //显示链表内容 bool push_front(List *list,ElemType x);//头插法 bool pop_back(List *list); //尾删法 bool pop_front(List *list); //头删法 Node *find(List *list,ElemType x); //查找函数，找到返回指向该元素的指针 bool modify(List *list,ElemType x); //修改某1元素的值 void delete_val(List *list,ElemType x);//按值删除 void clear(List *list); //清空链表 void destroy(List *list); //烧毁链表 int length(List *list); //求链表长度 void resver(List *list); //逆至链表 void prio(List *list,ElemType x); //求某个值的先驱 void next(List *list,ElemType x); //求某个值的后继 #endif

#include"List.h" //初始化单链表 void InitList(List *list) { Node *s = (Node *)malloc(sizeof(Node)); assert(s != NULL); s->next = NULL; list->first = list->last = s; list->size = 0; } //尾插法：开辟并初始化--->>连接---->>指针后移 bool push_back(List *list,ElemType x) { Node *s = (Node *)malloc(sizeof(Node));//开辟1个结点 if(s == NULL) { return false; } s->next = NULL;//对节点的初始化 s->data = x; list->last->next = s;//连接 list->last = s; //后移（尾指针后移） list->size++; return true; } //打印链表的内容 void show_seqlist(List *list) { Node *p = list->first->next; while(p != NULL) { cout<<p->data<<"--->"; p = p->next; } cout<<"NULL"<<endl; } //头插法：开辟并初始化--->>连接---->>指针后移 ！！注意特殊情况！！ bool push_front(List *list,ElemType x) { Node *s = (Node *)malloc(sizeof(Node)); if(s == NULL) { return false; } s->data = x; s->next = list->first->next; list->first->next = s; //注意：如果是第1个结点，则尾指针需要改变指向即指向第1个结点 //（不再指向头）如果不是第1个结点，尾指针指向无需改变 if(list->size == 0) { list->last = s; } list->size++; return true; } //尾删法：找到最后1个节点的先驱（指向赋空）---->尾指针指向它--->size - 1 bool pop_back(List *list) { if(list->size == 0) { cout<<"链表已空"<<endl; return false; } Node *pre = list->first; while(pre->next != list->last)//找到要删除节点（最后1个结点）的先驱 { pre = pre->next; } pre->next = NULL;//由于该先驱要作为尾结点，所以其指针域得赋空 free(list->last);//释放要删除的结点 list->last = pre;//尾指针指向改变 /* pre->next = NULL; list->last = pre; free(pre); pre = NULL; // free(list->last);*/ list->size--; return true; } //free(p)作用是：释放p所指向的空间，而非释放指针p！！！！！ //动态开辟的空间才需要手工释放，其他的空间系统自动回收 //头删法：释放第1个节点->size⑴(如果只有1个节点，释放它以后尾指针得指向头结点)，其他情况尾指针不变 bool pop_front(List *list) { if(list->size == 0) { cout<<"链表已空"<<endl; return false; } Node *p = list->first->next;//p指向要释放的第1个节点 list->first->next = p->next;//头指针指向下1个节点 free(p); //释放第1个节点 if(list->size == 1) { list->last = list->first;//如果只有1个节点，释放它以后尾指针得指向头结点)，其他情况尾指针不变 } list->size--; return true; } //查找函数 /*Node *find(List *list,ElemType x) { Node *p = list->first->next;//p指向第1个节点 while(p != NULL) { if(x == p->data) return p; else p = p->next; } return NULL; }*/ Node *find(List *list,ElemType x) { Node *p = list->first->next;//p指向第1个节点 while(p!=NULL && p->data!= x) { p = p->next; } return p;//while循环退出条件：没找到则-->p=NULL,找到p为指向所寻觅节点的指针 } //修改函数 bool modify(List *list,ElemType x) { ElemType item; Node *p = find(list,x); if(p != NULL) { cout<<"Please input the new value:"<<endl; cin>>item; p->data = item; cout<<"it is modified"<<endl; return true; } else cout<<"it's not exist!"<<endl; } //按值删除结点 void delete_val(List *list,ElemType x) { Node *p = find(list,x); //找到要删除的结点 if(p != NULL) { if(p == list->first->next)//如果是第1个结点（头删法） { pop_front(list); } else if(p == list->last) //如果是最后1个结点（尾删法） { pop_back(list); } else //既不是第1个结点，也不是最后1个节点 { p->data = p->next->data;//将要删除的结点的data赋值为下1个节点的data p->next = p->next->next;//连接 free(p->next); //将要删除的结点的下1个结点释放 } /*else //既不是第1个结点，也不是最后1个节点 { Node *pre = list->first; while(pre->next != p)//找到要删除节点的先驱 { pre = pre->next; } pre->next = p->next;//连接 free(p); //释放要删除的结点 }*/ list->size--; cout<<"it is deleted!"<<endl; } else { cout<<"it is not exist!"<<endl; } } //清空单链表 /*void clear(List *list,ElemType x) { for(int i=0;i<list->size;++i) { pop_back(list);//或pop_front(list) } }*/ void clear(List *list) { Node *p = list->first->next;//p指向第1个节点 while(p != NULL) { list->first->next = p->next;//分离出第1个结点 free(p);//将第1个节点释放 p = list->first->next;//又指向第1个节点(连续删除第1个结点) } list->last = list->first; //尾指针和头指针都指向头结点 list->size = 0; } //烧毁链表 void destroy(List *list) { clear(list);//清空链表 free(list->first);//头结点释放 list->first = list->last = NULL;//头（尾）指针赋空，避免成为野指针 } //求链表长度 int length(List *list) { return list->size; } //链表逆至 /*改变指针的指向*/ void resver(List *list) { Node *pre = list->first->next;//pre指向第1个节点 Node *p = pre->next; // p指向第2个结点 pre->next = NULL; //逆序以后第1个节点成为最后1个节点，所以next=NULL while(p != NULL) { Node *pre1 = pre;//将当前的指向保存下来 Node *p1 = p; pre = p; //为下1次（第n⑴次）交换做准备（必须在指向改变以后进行！！！！！） p = p->next; p1->next = pre1;//交换当前两个(第n次)后1个指向前1个 } list->first->next = pre; //退出循环，p=NULL,pre指向原来的最后1个结点（逆序后成为第1个） } /*交换值*/ /*void resver(List *list) { Node *left = list->first->next; Node *right = list->last; Node *p = list->first; while(left != right) { left->data = left->data + right->data;//对称的两个数交换 right->data = left->data - right->data; left->data = left->data - right->data; while(p->next != right)//找到倒数第2个结点 { p = p->next; } right = p;//为下1次交换做准备 left = left->next; } }*/ //求某个值的先驱 void prio(List *list,ElemType x) { Node *p = find(list,x); if(p == NULL) { cout<<"it is not exist! "<<endl; } if(p == list->first->next) { cout<<"it does not have next"<<endl; } else { Node *pre = list->first; while(pre->next != p) { pre = pre->next; } cout<<"it's prio is found"<<endl; cout<<"it is"<<pre->data<<endl;; } } //求某个值的后继 void next(List *list,ElemType x) { Node *p = find(list,x); if(p == NULL) { cout<<"it is not exist! "<<endl; } if(p == list->last) { cout<<"it does not have next"<<endl; } else { cout<<"it's next is found"<<endl; cout<<"it is"<<p->next->data<<endl; } }

#include"List.h" void main() { List mylist; InitList(&mylist); int select = 1; ElemType item; Node *p = NULL; while(select) { cout<<"**********************************"<<endl; cout<<"* [1] push_back [2] push_front *"<<endl; cout<<"* [3] show_seqlist[0] quit_system*"<<endl; cout<<"* [4] pop_back [5] pop_front *"<<endl; cout<<"* [6] find *"<<endl; cout<<"* [7] modify [8] clear *"<<endl; cout<<"* [9] destroy [10]delete_val *"<<endl; cout<<"* [11] resver [12]length *"<<endl; cout<<"* [13] prio [14]next *"<<endl; cout<<"**********************************"<<endl; cout<<"请选择:>"; cin>>select; switch(select) { case 1: cout<<"请输入要插入的数据(⑴结束):>"; while(cin>>item,item!=⑴) { push_back(&mylist,item); } break; case 2: cout<<"请输入要插入的数据(⑴结束):>"; while(cin>>item,item!=⑴) { push_front(&mylist,item); } break; case 3: show_seqlist(&mylist); break; case 4: pop_back(&mylist); break; case 5: pop_front(&mylist); break; case 6: cout<<"输入你要查找的值："; cin>>item; p =find(&mylist,item); if(p != NULL) cout<<"it is found!"<<endl; else cout<<"it is not exit!"<<endl; break; case 7: cout<<"请输入要修改的值："; cin>>item; modify(&mylist,item); break; case 8: clear(&mylist); break; case 9: destroy(&mylist); break; case 10: cout<<"请输入要删除的值："; cin>>item; delete_val(&mylist,item); break; case 11: resver(&mylist); break; case 12: { int n = length(&mylist); cout<<"the length of the list is:"<<n<<endl; } break; case 13: cout<<"输入你要查找先驱的值："; cin>>item; prio(&mylist,item); break; case 14: cout<<"输入你要查找后继的值："; cin>>item; next(&mylist,item); break; default: break; } } destroy(&mylist);//函数调用完以后，自动烧毁链表 }