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

对单链表实现如下功能：

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); //修改某一元素的值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);//求某个值的后继

List.h:#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); //修改某一元素的值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);//求某个值的后继#endifList.cpp:#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));//开辟一个结点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;//注意：如果是第一个结点，则尾指针需要改变指向即指向第一个结点//（不再指向头）如果不是第一个结点，尾指针指向无需改变 if(list->size == 0){list->last = s;}list->size++;return true;}//尾删法：找到最后一个节点的前驱（指向赋空）—->尾指针指向它—>size – 1bool pop_back(List *list){if(list->size == 0){cout<<"链表已空"<<endl;return false;}Node *pre = list->first;while(pre->next != list->last)//找到要删除节点（最后一个结点）的前驱{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！！！！！//动态开辟的空间才需要手工释放，其他的空间系统自动回收//头删法：释放第一个节点->size-1(如果只有一个节点，释放它之后尾指针得指向头结点)，其他情况尾指针不变bool pop_front(List *list){if(list->size == 0){cout<<"链表已空"<<endl;return false;}Node *p = list->first->next;//p指向要释放的第一个节点list->first->next = p->next;//头指针指向下一个节点free(p);//释放第一个节点if(list->size == 1){list->last = list->first;//如果只有一个节点，释放它之后尾指针得指向头结点)，其他情况尾指针不变}list->size–;return true;}//查找函数/*Node *find(List *list,ElemType x){Node *p = list->first->next;//p指向第一个节点while(p != NULL){if(x == p->data)return p;elsep = p->next;}return NULL;}*/Node *find(List *list,ElemType x){Node *p = list->first->next;//p指向第一个节点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;}elsecout<<"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)//如果是第一个结点（头删法）{pop_front(list);}else if(p == list->last) //如果是最后一个结点（尾删法）{pop_back(list);}else //既不是第一个结点，，也不是最后一个节点{p->data = p->next->data;//将要删除的结点的data赋值为下一个节点的datap->next = p->next->next;//连接free(p->next);//将要删除的结点的下一个结点释放}/*else //既不是第一个结点，也不是最后一个节点{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指向第一个节点while(p != NULL){list->first->next = p->next;//分离出第一个结点free(p);//将第一个节点释放p = list->first->next;//又指向第一个节点(连续删除第一个结点)}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指向第一个节点Node *p = pre->next;// p指向第二个结点pre->next = NULL;//逆序之后第一个节点成为最后一个节点，所以next=NULLwhile(p != NULL){Node *pre1 = pre;//将当前的指向保存下来Node *p1 = p;pre = p; //为下一次（第n-1次）交换做准备（必须在指向改变之后进行！！！！！）p = p->next;p1->next = pre1;//交换当前两个(第n次)后一个指向前一个}list->first->next = pre; //退出循环，p=NULL,pre指向原来的最后一个结点（逆序后成为第一个）}/*交换值*//*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)//找到倒数第二个结点{p = p->next;}right = p;//为下一次交换做准备left = left->next;}}*///求某个值的前驱void prio(List *list,ElemType x){Node *p = find(list,x);if(p == NULL){cout<<"it is not exist!\n"<<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!\n"<<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;}}main.cpp:#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<<"请输入要插入的数据(-1结束):>";while(cin>>item,item!=-1){push_back(&mylist,item);}break;case 2:cout<<"请输入要插入的数据(-1结束):>";while(cin>>item,item!=-1){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;elsecout<<"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);//函数调用完之后，自动销毁链表}

任何的限制，都是从自己的内心开始的。