【数据结构课件】链表.pptVIP

… front rear ^ procedure Del_link_queue( front, rear, item ); Begin // 删除队头元素,并将数据域信息保存在变元item中// if (front = nil) then call Queue_empty( ‘Queue is empty!’ ) else [ q:=front↑.next; front↑.next:=q↑.next; item:=q↑.data; if q↑.next=nil then rear:=front; dispose(q); ] End; 三. 删除算法 算 法 North China Electric Power University North China Electric Power University Data Structure 华北电力大学计算机科学与工程系 Dept. of Computer ScienceEngineering of North China Electric Power University North China Electric Power University 第三章 链 表 ★ 线性链表 ★ 链栈、链队 ★ 循环链表 ★ 多重链表 ★ 线性链表 假定上图为当前内存的使用情况，阴影部分为已用内存， 现有一线性表L=(A,B,C,D,E,F,G,H),假若采用顺序存储 的话，则在当前内存中不能分配一块长度为7的连续的存 储空间。但实际上，系统的可用内存远大于该线性表所 要求的内存空间，应采用其它的存储结构—链式存储。 North China Electric Power University North China Electric Power University G F B C E D H ^ A 可以采用上面的存储结构，每一个数据元素占用两个存 储单元，其中一个用来存放数据元素的值，另外一个存 放下一个数据元素存储单元的地址，这种结构称为链式 存储结构。在这种结构中，数据元素存放是不连续的。 Head North China Electric Power University 线性表的链式存储结构： 用一组地址任意的存储单元存放线性表中的数据元素 结点(表示数据元素)=元素(数据元素的映象) + 指针( 指示后继元素存储位置) 链表：以“结点的序列”表示的线性表。 A B C D E F G ^ H 头结点 数据域 指针域 链表结点 头指针：指向链表中第一个结点的指针。 首元结点 表结点 头指针 Head 头结点：单链表的第一个结点之前附设的一个结点，它 的数据域不存放信息、或存放如线性的长度等附加信息。 North China Electric Power University 首元结点：单链表中存放第一个元素的结点。 表结点：存放线性表中所有数据元素的结点。 单链表中设置头结点的好处： 1)其头指针是指向头结点的非空指针，无论链表是否为 空，头指针始终保持值不变，因此头指针的处理方法 对空表和非空表的操作是一致的，这与不带头结点的 单链表为空时头指针为空不同。 2)首元结点的地址存放在头结点的指针域中，对该结点 的操作与其它结点的操作一致，无需进行特殊处理(如 删除首元结点时，对不带头结点的单链表要修改头指 针)。 单链表上基本运算的实现 North China Electric Power University 1)Init_Link(Head):初始化一个单链表 Procedure Init_Link(Var Head:Link_list); Begin new(Head); Head↑.Next:=Nil; End; 单链表的类型定义如下： Type Pointer=↑ Node; Node=Record data:ElemType; next:Pointer; End; Link_list=Pointer; North China Electric Power University 2)Length_Link