第3章(链表)

数据结构NorthChinaElectricPowerUniversityDataStructure华北电力大学计算机科学与工程系Dept.ofComputerScience&EngineeringofNorthChinaElectricPowerUniversity第1章绪论第2章线性表第3章链表第4章数组和广义表第5章串第6章树第7章图第8章查找表第9章内排序目录NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity第三章链表3.1单链表3.2链栈、链队3.3循环链表、多重链表假定上图为当前内存的使用情况，阴影部分为已用内存，现有一线性表L=(A,B,C,D,E,F,G,H),假若采用顺序存储的话，则在当前内存中不能分配一块长度为8的连续的存储空间。但实际上，系统的可用内存远大于该线性表所要求的内存空间，应采用其它的存储结构—链式存储。NorthChinaElectricPowerUniversity3.1单链表NorthChinaElectricPowerUniversity当前内存的状态建立一个含有8个元素的线性表L=(a1,a2,a3,a4,a5,a6,a7,a8)可以采用链式存储结构，每一个数据元素占用两个存储单元，其中一个用来存放数据元素的值，另外一个存放下一个数据元素存储单元的地址，这种结构称为链式存储结构。在这种结构中，数据元素存放是不连续的。^a1Heada2a3a4a5a6a7a8地址数据指针6462149594327901137991a24212743495990a1a3a7a6a4a5a864990275943^21HeadNorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity用一组地址任意的存储单元存放线性表中的数据元素结点(表示数据元素)=元素(数据元素的映象)+指针(指示后继元素存储位置)链表：以“结点的序列”表示的线性表。头指针：指向链表中第一个结点的指针。数据域指针域链表结点ABCDEFG^H头结点首元结点表结点头指针Head一、线性表的链式存储结构链表基本概念头结点：单链表的第一个结点之前附设的一个结点，它的数据域不存放信息、或存放如线性的长度等附加信息。首元结点：单链表中存放第一个元素的结点。表结点：存放线性表中数据元素的结点。NorthChinaElectricPowerUniversity单链表中设置头结点的好处1)其头指针是指向头结点的非空指针，无论链表是否为空，头指针始终保持值不变，因此头指针的处理方法对空表和非空表的操作是一致的，这与不带头结点的单链表为空时头指针为空不同。2)首元结点的地址存放在头结点的指针域中，对该结点的操作与其它结点的操作一致，无需进行特殊处理(如删除首元结点时，对不带头结点的单链表要修改头指针)。NorthChinaElectricPowerUniversity1)Initial(Head):初始化一个单链表voidInitial(Pointer&head){//创建一个带头结点的空链表，head为指向头结点的指针head=newNode;if(!head)exit(1);//存储空间分配失败head-next=NULL;}单链表的类型定义如下：typedefstructNode{ElemTypedatastructNode*next}*Pointer;二、单链表上基本运算的实现NorthChinaElectricPowerUniversity2)Length(Head):返回单链表中所含表结点的个数。intLength(Pointer&head){//求表head的长度，P是Pointer类型变量p=head;j=0;//计数器置初值while(p-next!=NULL)//继续点数{p=p-next;j++;}return(j);//回传表长}3)Find(Head,i):返回指向线性表第i个结点的指针。NorthChinaElectricPowerUniversityPointerFind(Pointerhead,inti){//在单链表head中查找第i个结点，若找到则回传指向该结点的指针；否则回传NULLp=head-next;//变量初始化，p指向第一个结点j=0;while((p-next!＝Null)&&(ji)){p=p-next;j++;}//whileif(i==j)return(p);elsereturn(NULL);}//FindNorthChinaElectricPowerUniversity4)Locate(Head,x):在单链表中查找值等于x的结点，返回指向该结点的指针。intLocate(Pointerhead,ElemTypex){p=head;j=0;//置初值while((p-next)&&(p-data!=x)){p=p-next;j++;}if(p-data==x)return(j);elsereturn(0);}ABCD^x=‘C’HeadpNorthChinaElectricPowerUniversity5)Insert(Head,x,i):在单链表的第i个结点之前插入值等于x的结点。ABCD^x=‘F’i=3HeadpF①②SvoidInsert(Pointer&head,inti,ElemTypex){//在表head的第i个结点之前插入一个以x为值的新结点p=Find(head,i-1);if(!p)error(“without”);//参数不合法，i小于1或者大于表长+1else{s=newNode;if(!s)exit(1);//存储空间分配失败s-data=x;//创建新元素的结点s-next=p-next;p-next=s;//修改指针}}NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity6)Delete(Head,i):删除单链表的第i个结点。voidDelete(Pointer&head,intpos,ElemType&x){p=Find(head,i-1);//p指向第i-1个结点if((p!=NULL)&&(p-next!=NULL)){q=p-next;p-next=q-next;//修改指针x=q-data;delete(q);//释放结点空间}elseerror(“Without”);}ABCD^i=3HeadpNorthChinaElectricPowerUniversity7)CreateList(Head):建立一个单链表。voidCreateList(Pointer&head){head=newNode;//生成头结点p=head;//尾指针指向头结点getchar(x);//读入第一个元素while(x!=’*’){q=newNode;if(!q)exit(1);//存储空间分配失败q-data=x;p-next=q;p=q;getchar(x);}p-next=NULL;}NorthChinaElectricPowerUniversityvoidCreate_Link_2(Pointer&head);{//从前建立链表voidCreate_Link_3(Pointer&head);{//从后建立链表华电计算机系Initial(Head);p=Head;getchar(x);while(x!=’*’){q=newNode;q-data=x;p-next=q;p=q;getchar(x);}p-next=NULL;}p=NULL;getchar(x);while(x!=’*’){q=newNode;q-data=x;q-next=p;p=q;getchar(x);}Initial(Head);Head-next=p;}NorthChinaElectricPowerUniversity1)存储空间动态分配，可以按需要使用；2)插入/删除结点操作时，只需要修改指针，不必移动数据元素线性表的链式存储结构的优缺点：优点缺点1)每个结点需加一指针域，存储密度降低；2)非随机存储结构，查找定位操作需要从头指针出发顺着链表扫描。NorthChinaElectricPowerUniversity例1.将一个单链表逆置voidInvert_Link_1(Pointer&head);{//不带头结点p=Head;Head=NULL;while(p!=NULL){s=p;p=p-next;s-next=Head;Head=s;}}voidInvert_Link_2(Pointer&head);{//带头结点p=Head-next;h=NULL;while(p!=NULL){s=p;p=p-next;s-next=h;h=s;}head-next=h;}单链表的应用示例例2：一元多项式的表示及相加。在数学上，一个一元n次多项式Pn(X)可按升幂写成：Pn(x)=P1xe1+P2xe2+…+Pmxem其中,Pi是指数为ei的项的非零系数，且满足0≤e1e2…em=n若用一个长度为m且每个元素有两个数据项（系数项和指数项）的线性表((p1,e1),(p2,e2),…,(pm,em))便可唯一确定多项式Pn(x)。可以采用链式存储结构来表示线性表：typedefstructNode{doublecoef;intexp;structNode*next;}*polynom;NorthChinaElectricPowerUniversity算法描述如下：voidPolyadd(polynom&pa,&pb,&pc){p=pa-next;q=pb-next;S=pa;pc=pa;//S指向p结点的直接前驱while((p!=NULL)&&(q!=NULL)){if(p-expq-exp){s=p;p=p-next;}//p指针后移if(p-exp==q-exp){x=p-coef+q-coef;if(x!=0){p-coef=x;s=p}//修改p结点else{s-next=p-next;delete(p);}p=s-next;u=q;q=q-next;delete(u);}if(p-expq-exp){u=q-next;q-next=p;s-next=q;s=q;q=u;}}if(q!=NULL)s-next=q;delete(pb);}练习1若已知非空线性链表第一个结点的指针为list，请写一个算法，将该链表中数据域值最小的那个结点移到链表的最前端。NorthChinaElectricPowerUniversitylist356718658271521014……^list356718658271521014……^qpqs华电计算机系NorthChinaElectricPowerUniversityvoidRemove(Pointer&list);{q=list;p=list-next;r=list;while(p!=null){if(p-dataq-data){s=r;q=p;}r=pp=p-next;//s始终指向q的前一个结点}//找到值最小的那个结点，地址由q记录if(q!=list)//若值最小的结点不是链表最前面那个结点{s-next=q-next;q-next=list;list=q;}end;堆栈的链式存储结构一.构造原理链接堆栈就是用一个线性链表来实现一个堆栈结构,同时设置一个指针变量(这里用Ls表示)指出当前栈顶元素所在链结点的位置。当栈为空时，有Ls=nil。NorthChinaElectricPowerUniversity3.2链栈和链队在一个初始为空的链接堆栈中依次插入数据元素A,B,C,D以后