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↑.Next< >Nil 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↑.Next< >Nil) 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. next< >Nil)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↑.Next< >Nil) 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