本文共 6352 字，大约阅读时间需要 21 分钟。
C++实现单链表的16种基本操作
链表初始化，头插法创建链表，尾插法创建链表，取值，查找（第i个节点的数据域或者数据域为某个特定值的节点），有顺序的合并两个链表，无顺序的合并两个链表，插入，删除，逆置链表，求链表的节点个数，删除数据域重复的节点，输出链表，判空，置空链表。
以下是我写的头文件的代码
#ifndef DANLIANBIAO_H#define DANLIANBIAO_H#endif#include #include #include #define ElemType int//头结点是链表里面第一个结点，他的数据域可以不存放任何信息（有时候也会存放链表的长度等等信息），他的指针区域存放的是链表中第一个数据元素的结点（就是传说中的首元结点）存放的地址。//指向第一个结点（可能是头节点也可能是首元节点）的指针称为头指针using namespace std;typedef struct Lnode{ ElemType data;//数据域 //elemtype 定义元素类型，使元素种类可以多样 struct Lnode *next;//指针域,指向下一个节点的指针}Lnode,*Linklist;// LNode是一个具象的结构体类型，指向的是包含某个数据类型的数据域和指针域的结构体类型。// 而LinkList是LNode的指针类型，它占用一定内存空间，内存空间中的值是一个LNode类型结构体的地址//用typedef将结构体等价于类型名Lnode，指针Linklist//初始化单链表bool InitList_L(Linklist &L){ //创建了一个带有头节点的空链表 L=new Lnode;//头节点L，其数值域为空，L->next指向第一个存有数据的节点即首节点 if(!L) return false; L->next=NULL; return true;}//头插法创建单链表（头插法创建单链表，出来是和你输入的数据顺序是相反的，因为是把输入的数据不断放到头部）void CreateList_H(Linklist &L){ int n;//输入n个元素的值，建立到头节点的单链表L Linklist s;//定义指针变量s L=new Lnode;//头节点L，其数值域为空，L->next指向第一个存有数据的节点即首节点 L->next=NULL; cout<<"请输入元素个数n："< >n; cout<<"头插法创建单链表"< next=s;，s的地址不断改变，linklist指针也在不断后移 cin>>s->data; s->next=L->next;//先修改没有指针标记的一端，要不然原来L后面的节点就找不到了 L->next=s; } } //尾插法创建单链表（尾插法创建的链表是和你输入的顺序相同的，因为是不断把你输入的数据放到链表尾部） void CreateList_R(Linklist & L) { int n; Linklist s,r; L=new Lnode; L->next=NULL; r=L;//将头节点L的地址存储于r中即尾指针指向头节点 cout<<"请输入元素个数 n："< >n; cout<<"尾插法创建单链表 "< >s->data; s->next=NULL; r->next=s;//r原来存贮的是L的地址，此步相当于 L->next=s，但是后来随着节点的不断插入，r->next=s就代表是尾节点的指针指向新插入的s，即尾插法 r=s;//r存储s的地址， } } //输出链表的元素 void Show_L(Linklist &L){ Linklist s; s=L->next; while(s){ cout< data<<" "; s=s->next; } cout< next;//p指向第一个数据节点 j=1;//j为计数器 while(j next;//p指向下一个节点 j++;//计数器加1 } if(!p||j>i)//i值不合法，i<=0,i>n return -1; e=p->data;//取第i 个节点的数据域 return e; } //查找,在带头节点的单链表L中查找值为e的元素 int LocateElem_L(Linklist L,int e) { Linklist p; p=L; int j=0; while(p&&p->data!=e){ //沿着链表向后扫描直到p为空或p所指节点数据域等于e p=p->next; j++; } if(!p)如果!p不为空，即如果p为空 //if（），while（），条件判断都是（）里的东西不为空 return -1; else return j; } //插入 bool ListInsert_L(Linklist &L,int i,int e) { int j; Linklist p,s; p=L; j=0; while(p&&j next; j++; } if(!p||j>i-1)//i值不合法 return false; else { s=new Lnode;//生成新节点 s->data=e;//将要插入的元素e放入新节点的数据域中 s->next=p->next;//新节点的指针指向第i个节点 p->next=s; return true; } } //删除bool ListDelete_L(Linklist &L,int i){ //删除第i 个位置 Linklist p,q;//q指向被删除的节点 int j; p=L;//p指向头指针L j=0; while((p->next)&&(j next)&&(j next，所以while(p)while(p->next)其实本质是一样的//while(p->next)使进了循环p就能赋值，但是如果while(p)的话，进了循环p不一定能赋值，因为可能p->next为空 { p=p->next; j++;//j=0 第一次循环：第一个节点，j=1，第二个节点,j=2...... } if(!(p->next)||(j>i-1))//删除位置i取值不合适 return false; else { q=p->next;// 临时保存被删节点的地址即第i个节点的地址以备释放空间 p->next=q->next;//将i 节点的下一个节点的地址赋值给p节点的指针域 delete q;//释放被删除节点的空间 return true; }} //单链表逆置void Reverse_L(Linklist &L){ Linklist r,p,q;//r代表前驱节点，p当前节点，q后继节点；Linklist r,p,q分别指向前驱节点，当前节点，后继节点 if(!L->next)//如果当前链表为空，则不需要逆置，结束 return; //反转每个节点的指针域，从单链表的第一个节点开始，沿着链表滑动，直到最后一个节点，逐一反转 r=NULL;p=L->next;q=p->next; while(p) { p->next=r;//修改当前节点的指针域next，把它反转指向其前驱节点 //把指针r,p,q依次后移一个结点 r=p; p=q; if(q)//保证指向后继节点的指针q不会移出表尾 q=q->next; } //当从循环出来时说明p为空，则r就是最后一个节点，此时把最后一个节点作为首节点 L->next=r;}//把单链表置空void clear_L(Linklist &L){ Linklist p,q;//指向代删除节点及其后继节点//回收每个节点的存储空间即从单链表的第一个节点开始，沿着链表滑动，直到最后一个节点，逐一回收p=NULL;q=L->next;while(q){ p=q;//把指针p指向代删除的节点q，便于后面清空储存空间 q=q->next;//指针q，指向下一个代删除的节点 delete p;//回收代删除节点的空间}L->next=NULL;}//删除单链表中数据域为e的第一个节点bool DeleteElem_L(Linklist &L,ElemType e){ Linklist r ,p;//分别指向待删除节点的前驱和待删除节点的指针 //L是头指针，是不能变换指向的，要不然会导致整个链表丢失，L->next;就是指向首节点的（即第一个data不为空的节点） r=L;//使r指向头节点，有头节点的好处是当要删除的元素是第一个节点时，不用再单独处理首节点 // 即省去了这两步操作 if(r==NULL)； L->next=L->next->next;单独对首节点处理 p=L->next; while(p&&(p->data)!=e)//查找待删除节点 { r=p;// 指向前驱节点 p=p->next;//指向当前节点 } if(p==NULL)//滑动到表尾，没找到代删除节点，返回false return false; //if(r==NULL) // L->next=L->next->next; else r->next=p->next;//修改待删除节点的前驱节点，使其指向待删除节点的下一个节点 free(p);//回收待删除节点的存储空间 return true; }//删除单链表中的重复值//查找当前节点p是否与前面的每个节点有重复值，用指针s来实现，s从链表的第一个节点直到p所指的当前节点为止，逐一判断是否有与p->data相等的节点//若有相同则指针p所指的当前节点， p=p->next;，重复判断是否有重复操作直到链表尾void DeleteRepeat(Linklist &L){ Linklist r,p;//分别指向前驱节点和当前节点的指针Linklist s;r=L;p=L->next;//从单链表的第一个节点开始，直到最后一个节点，逐一判断while(p){ s=L->next;//s指针的作用从第一个节点开始，直到p所指的当前节点，逐一判断看是否有重复 while(s!=p) { if(s->data==p->data)//如果有重复，使前驱节点绕过当前p节点即删掉p节点 { r->next=p->next;//如果有重复，使前驱节点绕过当前p节点即删掉p节点 delete p;//回收指针p所指当前节点的存储空间，不是删掉p指针 p=r;//p指针原本指向的节点被删除，使p指针指向前驱节点r，后面的操作 p=p->next;，就可使p后移一位，而前驱节点仍保持不变，因为删除了一个节点的原因，可以代入样例试一下 break; } s=s->next;//若没有重复，则下移一个节点，继续比较，直到s指向p出循环 } //前驱节点和当前节点都后移一个节点，直到p移到表尾 r=p; if(p)//判断指针p是否已经到达表尾 p=p->next;}}// 求单链表节点个数，头节点个数不计算在内int GetLength(Linklist &L){ int n=0; Linklist p; p=L; while(p->next)//while(p->next)头节点不计算在个数内；while(p)头节点计算在个数内 { p=p->next; n++; } return n;}//判断单链表是否为空bool IsEmpty(Linklist &L){ if(L->next)//如果头节点不为空，则链表不是空链表 return false; else return true;//如果头节点为空，则链表是空链表 }//将两个链表合并，有序的合并 void GuiblingList(Linklist & A,Linklist& B)//将B插入到A中合适位置，从而得到一个有顺序的合并链表 { Linklist p,q,r; q=A;p=B->next; //此处因为要把B链表插入到A链表中去，q指针指向的是A的头指针，这样当B链表中的值小于A链表中的值，需要插入到A链表中时（进行插入操作需要直到插入位置的前驱节点）q指针指向总是能指向要插入位置的前驱节点 //比较的是q->next->data和p->data的值，但是q的指向是q->next的前驱节点，这样便于B链表的插入while(p)//当B链表不为空时{ //看不懂，可以自己手动迭代一下代码，就清楚了 //从A链表第一个节点的值开始和B的第一个节点的值比较，如果A的第一个节点的值A1 next;A链表的下一个节点A2再和B1进行比较//如果A1>B1，则使用另一个指针r，r指针指向B1，p指针指向B2（保证B1后面的节点不会丢失），再让r指针指向A1r->next=q->next;（把A1插到B1后面）//再让A链表的头指针指向r（即B1）从而达到把B1插入到A链表中去 while((q->next)&&(q->next->data data))//从A链表第一个节点的值开始和B的第一个节点的值比较 { q=q->next;//当q->next->data小于p->data，q就指向链表A的下一个节点，再和p->data比较 }//如果q->next->data大于p->data，需要把B链表的节点插入到A中 r=p; p=p->next;//p指向当前节点的后继节点防止当前节点的后面节点丢失 r->next=q->next;//将q->next（因为此时q指向的是前驱节点）的节点插入到r指向节点的后面 q->next=r;//再将前面排好序好的节点重新插入到A链表中去 } Show_L(A);}//无序的合并链表void CoalitionLinkList(Linklist& A,Linklist &B) { Linklist p; for(p=A;p->next!=NULL;p=p->next)//找到A链表的尾节点 { }; p->next=B->next;//出循环后，将B链表的首节点接到A链表的尾节点 free (B);//释放B的存储空间 Show_L(A); }
以下是主方法的代码
#include #include"danlianbiao.h"//把我上面写的头文件导入到主方法的文件中，这样主方法看起来不会特别乱using namespace std;int main(){ Linklist L,A,B; InitList_L(L);//初始化链表，形成带有头节点的空链表 CreateList_H(L);//头插法创建链表，输出是正序 CreateList_R(L);//尾插法创建链表，输出是逆序 Show_L(L);//输出 cout<
初学新手，欢迎大家指正！
转载地址：http://acrcz.baihongyu.com/