线性表的链式存储结构.pptxVIP

第5讲线性表的

链式存储结构主讲人：陈红丽

2.3线性表类型的实现----链式映象

01用一组地址任意的存储单元存放线性表中的数据元素。02以元素(数据元素的映象)03+指针(指示后继元素存储位置)04=结点05(表示数据元素或数据元素的映象)06以“结点的序列”表示线性表07??称作链表一、单链表

以线性表中第一个数据元素的存储地址作为线性表的基地址，称作线性表的头指针头结点a1a2…...an^头指针头指针有时为了操作方便，在第一个结点之前附加一个“头结点”，令该结点中指针域的指针指向第一个元素结点，并令头指针指向头结点。通常称这类单链表为带头结点的单链表。空指针线性表为空表时，头结点的指针域为空?

二、结点和单链表的C语言描述结点类型：TypedefstructLNode{ElemTypedata;//数据域structLnode*next;//指针域}LNode;a1a2…...an^H结点单链表类型：TypedefLNode*LinkList;

若设LNode*p,*q;则p，q和H均为以上定义的指针型变量。指针型变量的“值”除了由同类型的指针变量赋值得到外，都必须用C语言中的动态分配函数得到。例如，p=newLNode;表示在运行时刻系统动态生成了一个LNode类型的结点，并令指针p“指向”该结点。LinkListH；指针型变量只能作同类型的指针赋值与比较操作。当指针p所指结点不再使用，可用deletep;释放此结点空间。123456

010203040506GetElem(L,i,e)//取第i个数据元素ListInsert(L,i,e)//插入数据元素ListDelete(L,i,e)//删除数据元素ClearList(L)//重置线性表为空表InitList(L)//初始化DestroyList(L)//销毁线性表三、单链表操作的实现

操作InitList(L)O(1)if(!L)exit(1);//存储空间分配失败L=newLNode;01链表是一个进行动态存储管理的结构，因此在初始化时不需要按照线性表实际所需最大容量进行预分配。voidInitList_L(LinkListL){//创建一个带头结点的空链表，L为指向头结点的指针

}//InitList算法时间复杂度：L-next=NULL;02

操作DestroyList(L)与ClearList(L)voidDestroyList_L(LinkListL){//销毁以L为头指针的单链表，//释放链表中所有结点空间 while(L){

p=L;

L=L-next;

deletep;

}}//DestroyList算法时间复杂度：O(ListLength(L))voidClearList_L(L){//将单链表重新置为一个空表while(L-next){ p=L-next; L-next=p-next;delete(p);}}//ClearListL所指结点的指针域内容赋值给L.即L指向L的后继结点.p所指结点的指针域内容赋值给L的指针域。即L的指针域指向p的后继结点.

L线性表的操作GetElem(L,i,e)在单链表中的实现:211830754256∧pppj123

因此，查找第i个数据元素的基本操作为：移动指针，比较指针所指元素的位序j和i01单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。因此不论i值为多少，都必须从头结点开始起点数，直数到第i个为止。头结点可看成是第0个结点。02p和j同步变化，始终保持指针p指向第j个结点03

算法时间复杂度为:StatusGetElem_L(LinkListL,inti,ElemTypee){//L是带头结点的链表的头指针，若1≤i≤LengthList(L)，则用e带回第i个元素的值且返回函数值为TRUE,否则返回函数值为FALSE}//GetElem_LO(ListLength(L))p=L-next;j=1;//p指向第一个结点，j为计数器w