North China Electric Power University 数据结构 Data Structure 华北电力大喾计算机斛学与工程柰 Dept of Computer Science& Engineering of North China Electric Power University
数据结构 North China Electric Power University Data Structure 华北电力大学计算机科学与工程系 Dept. of Computer Science&Engineering of North China Electric Power University
North China Electric Power University 第三章链表 ★线性链表 ★链栈、锭队 ★循坏森 ★多重镟裘
North China Electric Power University 第三章 链 表 ★ 线性链表 ★ 链栈、链队 ★ 循环链表 ★ 多重链表
★窥性髓 North China Electric Power University 假定上图为当前内存的使用情况,阴影部分为已用内存, 现有一线性表L=(A,B,CD,EF,G,H),假若采用顺序存储 的话,则在当前内存中不能分配一块长度为7的连续的存 储空间。但实际上,系统的可用内存远大于该线性表所 要求的内存空间,应采用其它的存储结构一链式存储
★ 线性链表 假定上图为当前内存的使用情况，阴影部分为已用内存， 现有一线性表L=(A,B,C,D,E,F,G,H),假若采用顺序存储 的话，则在当前内存中不能分配一块长度为7的连续的存 储空间。但实际上，系统的可用内存远大于该线性表所 要求的内存空间，应采用其它的存储结构—链式存储。 North China Electric Power University
North China Electric Power University Head A B C G F D E mmzvdddd/ HA 可以采用上面的存储结构,每一个数据元素占用两个存 储单元,其中一个用来存放数据元素的值,另外一个存 放下一个数据元素存储单元的地址,这种结构称为链式 存储结构。在这种结构中,数据元素存放是不连续的
North China Electric Power University G F B C E D H ^ A 可以采用上面的存储结构，每一个数据元素占用两个存 储单元，其中一个用来存放数据元素的值，另外一个存 放下一个数据元素存储单元的地址，这种结构称为链式 存储结构。在这种结构中，数据元素存放是不连续的。 Head
North China Electric Power University 线性表的链式存储结构: 用一组地址任意的存储单元存放线性表中的数据元素 结点表示数据元素)元素(数据元素的映象)+指针( 指示后继元素存储位置) 连表结点数据域针域 链表:以“结点的序列”表示的线性表 头指针:指向链表中第一个结点的指针 头指针头结点首元结点 Heady 圆,四闻D 表结点 F E
North China Electric Power University 线性表的链式存储结构： 用一组地址任意的存储单元存放线性表中的数据元素 结点(表示数据元素)=元素(数据元素的映象) + 指针( 指示后继元素存储位置) 链表：以“结点的序列”表示的线性表。 A B C D ^ H G F E 头结点 链表结点 数据域 指针域 头指针：指向链表中第一个结点的指针。 首元结点 表结点 头指针 Head
North China Electric Power University 头结点:单链表的第一个结点之前附设的一个结点,它 的数据域不存放信息、或存放如线性的长度等附加信息 首元结点:单链表中存放第一个元素的结点 表结点:存放线性表中所有数据元素的结点 单链表中设置头结点的好处: 1)其头指针是指向头结点的非空指针,无论链表是否为 空,头指针始终保持值不变,因此头指针的处理方法 对空表和非空表的操作是一致的,这与不带头结点的 单链表为空时头指针为空不同。 2)首元结点的地址存放在头结点的指针域中,对该结点 的操作与其它结点的操作一致,无需进行特殊处理(如 删除首元结点时,对不带头结点的单链表要修改头指 针)
头结点：单链表的第一个结点之前附设的一个结点，它 的数据域不存放信息、或存放如线性的长度等附加信息。 North China Electric Power University 首元结点：单链表中存放第一个元素的结点。 表结点：存放线性表中所有数据元素的结点。 单链表中设置头结点的好处： 1)其头指针是指向头结点的非空指针，无论链表是否为 空，头指针始终保持值不变，因此头指针的处理方法 对空表和非空表的操作是一致的，这与不带头结点的 单链表为空时头指针为空不同。 2)首元结点的地址存放在头结点的指针域中，对该结点 的操作与其它结点的操作一致，无需进行特殊处理(如 删除首元结点时，对不带头结点的单链表要修改头指 针)
North China Electric Power University 单链表上基本运算的实现 单链表的类型定义如下: Type Pointers=↑ Node; Node=record data: Elem Type; next pointer End; Link list=pointer. I) Init Link(Head):初始化一个单链表 Procedure Init Link(var Head: Link list) Begin new (head); Head个.Next:=Nil: nd
单链表上基本运算的实现 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 I 2) Length Link(Head):返回单链表中所含表结点的个数 Function Length Link(Head: Link list): Integer; Begin p:=Head; j: =0 while p↑Next<>NiD0[p:=p↑Next;j:≡j+1;l Returned; End; 3 Length Link(Head):返回指向线性表第个结点的指针 Function Find Link(head: Link list; i: Integer: Link list; begin p:=Head; j: =0 while(p↑Next>Ni)and〔jD0 Ip:=p↑.Next;j=+1; if i=j then return(p) else return(niD); End
North China Electric Power University 2)Length_Link (Head):返回单链表中所含表结点的个数。 Function Length_Link(Head:Link_list):Integer; Begin p:=Head;j:=0; while p↑.NextNil Do [ p:=p↑.Next; j:=j+1;] Return(j); End; 3)Length_Link (Head):返回指向线性表第i个结点的指针。 Function Find_Link(Head:Link_list;i:Integer):Link_list; Begin p:=Head;j:=0; while (p↑.NextNil) and (j<i) Do [ p:=p↑.Next; j:=j+1;] if i=j then Return(p) else Return(Nil); End;
North China Electric Power University 4) Locate link(Head,x):在单链表中查找值等于x的结点 返回指向该结点的指针。 Heady B Function Locate Link(Head; x: ElemType): Link list Begin p:Head; while(pt. nextNil)and (p. data<>x)do p:→p↑.Next; if pf data=x then return(p else return (nil) End
North China Electric Power University 4)Locate_Link (Head,x):在单链表中查找值等于x的结点， 返回指向该结点的指针。 Function Locate_Link(Head;x:ElemType):Link_list; Begin p:=Head; while (p↑.NextNil) and (p↑.data x) Do p:=p↑.Next; if p↑.data=x then Return(p) else Return(Nil); End; A B C D ^ x=‘C’ Head p
North China Electric Power University 5) Insert Link(Head,x;):在单链表的第个结点之前插入值 等于x的结点。 3 Heady F Procedure Insert_ Link(Var Head; x: ElemType; i Integer) B egn p:=Find Link(Head, i-1); if p=Nil then Error( without) else[new(S);s↑data:=x;s↑.next:=p↑.next; p↑next:=s: End
North China Electric Power University 5)Insert_Link (Head,x,i):在单链表的第i个结点之前插入值 等于x的结点。 Procedure Insert_Link(Var Head;x:ElemType;i:Integer); Begin p:=Find_Link(Head,i-1); if p=Nil then Error(‘Without’) else [ new(s);s↑.data:=x;s↑.next:=p↑.next; p↑.next:=s; ] End; A B C D ^ x=‘F’ i=3 Head p F ② ① S