本文共 6352 字,大约阅读时间需要 21 分钟。
链表初始化,头插法创建链表,尾插法创建链表,取值,查找(第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/