数据结构-合肥工业大学 3(合肥工大).ppt

《数据结构-合肥工业大学 3(合肥工大).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章链表华电计算机系NorthChinaElectricPowerUniversity3.1线性链表3.2链栈、链队3.3循环链表3.4多重链表华电计算机系3.1线性链表华电计算机系假定上图为当前内存的使用情况，阴影部分为已用内存，现有一线性表L=(A,B,C,D,E,F,G,H),假若采用顺序存储的话，则在当前内存中不能分配一块长度为8的连续的存储空间。但实际上，系统的可用内存远大于该线性表所要求的内存空间，应采用其它的存储结构—链式存储。NorthChinaElectricPowerUniversity可以采用上面的存储结构，每一个数据元素占

2、用两个存储单元，其中一个用来存放数据元素的值，另外一个存放下一个数据元素存储单元的地址，这种结构称为链式存储结构。在这种结构中，数据元素存放是不连续的。GFBCEDH^AHead华电计算机系链表：以“结点的序列”表示的线性表。数据域指针域链表结点头指针：指向链表中第一个结点的指针。线性表的链式存储结构：用一组地址任意的存储单元存放线性表中的数据元素,为表示元素间的逻辑关系，除了存储元素本身的信息外，还需存储一个指示其直接后继元素存储位置的信息，这两部分信息组成一个元素的存储映像，称为结点。华电计算机系头结点首元结点ABCDEFG^H表结点头指针He

3、adNorthChinaElectricPowerUniversity链表基本概念头结点：单链表的第一个结点之前附设的一个结点，它的数据域不存放信息、或存放如线性的长度等附加信息。首元结点：单链表中存放第一个元素的结点。表结点：存放线性表中数据元素的结点。单链表中设置头结点的好处：1)其头指针是指向头结点的非空指针，无论链表是否为空，头指针始终保持值不变，因此头指针的处理方法对空表和非空表的操作是一致的，这与不带头结点的单链表为空时头指针为空不同。华电计算机系2)首元结点的地址存放在头结点的指针域中，对该结点的操作与其它结点的操作一致，无需进行特殊

4、处理(如删除首元结点时，对不带头结点的单链表要修改头指针)。ProcedureInit_Link(VarHead:Link_list);Beginnew(Head);Head↑.Next:=Nil;End;单链表的类型定义如下（Pascal语言）TypePointer=↑Node;Node=Recorddata:ElemType;next:Pointer;End;Link_list=Pointer;二、单链表基本运算的实现1)Init_Link(Head):初始化一个单链表华电计算机系单链表的类型定义如下（C语言）typedefstructNode

5、{ElemTypedata;structNode*next;}*Pointer;voidInitial(Pointer&head){head=newNode;if(!head)exit(1);//存储空间分配失败head->next=NULL;}FunctionLength_Link(Head:Link_list):Integer;Beginp:=Head;j:=0;whilep↑.Next<>NilDo[p:=p↑.Next;j:=j+1;]Return(j);End;intLength(Pointer&head){p=Head;j=0;2)Le

6、ngth_Link(Head):返回单链表中所含表结点的个数。Pascal实现Length(Pointer&head):返回单链表中所含表结点的个数。C实现华电计算机系while(p->next!=NULL)//继续点数{p=p->next;j++;}return(j);//回传表长}FunctionFind_Link(Head:Link_list;i:Integer):Link_list;Beginp:=Head;j:=0;3)返回指向线性表第i个结点的指针。(Pascal实现)返回指向线性表第i个结点的指针。(C语言实现)华电计算机系while

7、(p↑.Next<>Nil)and(jnext)&&(jnext;j++;}if(i==j)return(p);Elsereturn(NULL);}//FindFunctionLocate_Link(Head;x:ElemType):Link_list;Beginp:=Head;ABCD^x=‘C’Hea

8、dp4)Locate_Link(Head,x):在单链表中查找值等于x的结点，返回指向该结点的指针。(Pascal实现)华