第3章(链表)

第三章链表3.1线性链表3.2链栈、链队3.3循环链表与多重链表3.1线性链表假定上图为当前内存的使用情况，阴影部分为已用内存，现有一线性表L=(A,B,C,D,E,F,G,H),假若采用顺序存储的话，则在当前内存中不能分配一块长度为8的连续的存储空间。但实际上，系统的可用内存远大于该线性表所要求的内存空间，应采用其它的存储结构—链式存储。可以采用上面的存储结构，每一个数据元素占用两个存储单元，其中一个用来存放数据元素的值，另外一个存放下一个数据元素存储单元的地址，这种结构称为链式存储结构。在这种结构中，数据元素存放是不连续的。GFBCEDH^AHead链表：以“结点的序列”表示的线性表。数据域指针域链表结点头指针：指向链表中第一个结点的指针。一.线性表的链式存储结构用一组地址任意的存储单元存放线性表中的数据元素,为了表示元素间的逻辑关系，除了存储元素本身的信息外，还需存储一个指示其直接后继元素存储位置的信息，这两部分信息组成一个元素的存储映像，称为结点。头结点首元结点ABCDEFG^H表结点头指针Head链表基本概念头结点：单链表的第一个结点之前附设的一个结点，它的数据域不存放信息、或存放如线性的长度等附加信息。首元结点：单链表中存放第一个元素的结点。表结点：存放线性表中数据元素的结点。单链表中设置头结点的好处：1)其头指针是指向头结点的非空指针，无论链表是否为空，头指针始终保持值不变，因此头指针的处理方法对空表和非空表的操作是一致的，这与不带头结点的单链表为空时头指针为空不同。2)首元结点的地址存放在头结点的指针域中，对该结点的操作与其它结点的操作一致，无需进行特殊处理(如删除首元结点时，对不带头结点的单链表要修改头指针)。二、单链表基本运算的实现单链表的类型定义如下：typedefstructNode{ElemTypedata;structNode*next;}*Pointer;1)Init_Link():初始化一个单链表。PointerInitial(){Pointerhead；head=newNode;if(!head)exit(1);//存储空间分配失败head-next=NULL;returnhead;}intLength(Pointerhead){p=Head;j=0;2)Length(head):返回单链表中所含表结点的个数。while(p-next!=NULL)//继续点数{p=p-next;j++;}return(j);//回传表长}3)Find(head,i)返回指向线性表第i个结点的指针。PointerFind(Pointerhead,inti){p=head;j=0;while((p-next)&&(ji)){p=p-next;j++;}if(i==j)return(p);elsereturn(NULL);}ABCD^x=‘C’Headp4)Locate_Link(Head,x):在单链表中查找值等于x的结点，返回指向该结点的指针。PointerLocate(Pointerhead,ElemTypex){p=head;while((p-next)&&(p-data!=x))p=p-next;if(p-data==x)returnp;elsereturnNULL;}voidInsert(Pointerhead,inti,ElemTypex){//在表head的第i个结点之前插入一个以x为值的新结点p=Find(head,i-1);5)voidInsert(Pointerhead,inti,ElemTypex)在单链表的第i个结点之前插入值等于x的结点。ABCD^x=‘F’i=3HeadpF①②Sif(!p)error(“without”);else{s=newNode;if(!s)exit(1);//存储空间分配失败s-data=x;//创建新元素的结点s-next=p-next;p-next=s;}}voidDelete(Pointerhead,inti,ElemType&x){p=Find(head,i-1);//p指向第i-1个结点ABCD^i=3Headp6)Delete(head,i,x)：删除单链表的第i个结点。if((p!=NULL)&&(p-next!=NULL)){q=p-next;p-next=q-next;//修改指针x=q-data;delete(q);}//释放结点空间elseerror(“Without”);}PointerCreateList(){7)Create():建立一个单链表。PointerHead,p,q;//Head:头指针,p:尾指针,q:新节点指针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;}优点线性表的链式存储结构的优缺点：1)存储空间动态分配，可以按需要使用；2)插入/删除结点操作时，只需要修改指针，不必移动数据元素。缺点1)每个结点需要添加指针域，存储密度降低；2)非随机存储结构，查找定位操作需要从头指针出发顺链表扫描。voidpurge_lklist(PointerHead){p=Head-next;if(p==NULL)return;while(p-next!=NULL){q=p;while(q-next!=NULL){if(q-next-date==p-data){r=q-next;q-next=r-next;deleter;}elseq=q-next;}p=p-next;}}【例3.1】试编写一个删除重复节点，只保留其中序号最小的一个的算法。例如，线性表（3,1,2,1,5,3,1)删除后为（3,1,2,5)。栈的链式存储结构构造原理链栈就是用一个线性链表来实现一个堆栈结构,同时设置一个指针变量(这里不妨仍用top表示)指出当前栈顶元素所在链结点的位置。当栈为空时，有top=NULL。3.2链栈和链队在一个初始为空的链接堆栈中依次插入数据元素A,B,C,D以后,堆栈的状态为:DCBA^top栈顶元素例队列的链式存储结构队列的链式存储结构是用一个线性链表表示一个队列，指针front与rear分别指向队头元素与队尾元素所在的结点。约定：rear指出实际队尾元素所在的位置。构造原理在一个初始为空的链队列中依次插入数据元素A,B,C,D以后,队列的状态为：空队对应的链表为空链表，空队的标志是：front=rear例ABCD^rearfrontrearfront循环链表是指链表中最后那个链结点的指针域存放指向链表最前面那个结点的地址，整个链表形成一个环。3.3循环链表…^list…list线性链表带头结点的循环链表循环链表的特点1.只要给出表中任何一个结点的位置，则由此出发就可以访问表中其他所有结点。2.对循环链表，若在它的第一个结点之前设立一个特殊的称为表头的结点，它的数据域可以按需要设定。使这样的链表中任何时候都至少有一个结点存在，这样就可以把对空表和非空表的处理统一起来。3.当需要将整个链表中所有结点归还给可用空间栈时，用循环链表比用普通链表要方便的多。…^…^Havav……^Havav单链表循环链表