数据结构 第5讲_线性表的链式存储结构ppt课件.ppt

《数据结构 第5讲_线性表的链式存储结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5讲线性表的链式存储结构主讲人：陈红丽2.3线性表类型的实现----链式映象用一组地址任意的存储单元存放线性表中的数据元素。一、单链表以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素或数据元素的映象)以“结点的序列”表示线性表称作链表以线性表中第一个数据元素的存储地址作为线性表的基地址，称作线性表的头指针头结点a1a2…...an^头指针头指针有时为了操作方便，在第一个结点之前附加一个“头结点”，令该结点中指针域的指针指向第一个元素结点，并令头指针指向头结点。通常称这类单链表为"带头结点的单链表"。空指针线

2、性表为空表时，头结点的指针域为空结点类型：TypedefstructLNode{ElemTypedata;//数据域structLnode*next;//指针域}LNode;二、结点和单链表的C语言描述a1a2…...an^H结点单链表类型：TypedefLNode*LinkList;若设LNode*p,*q;LinkListH；则p，q和H均为以上定义的指针型变量。指针型变量只能作同类型的指针赋值与比较操作。指针型变量的“值”除了由同类型的指针变量赋值得到外，都必须用C语言中的动态分配函数得到。例如，p=newLNode;表示在运行时刻

3、系统动态生成了一个LNode类型的结点，并令指针p“指向”该结点。当指针p所指结点不再使用，可用deletep;释放此结点空间。三、单链表操作的实现GetElem(L,i,&e)//取第i个数据元素ListInsert(&L,i,e)//插入数据元素ListDelete(&L,i,&e)//删除数据元素ClearList(&L)//重置线性表为空表InitList(&L)//初始化DestroyList(&L)//销毁线性表操作InitList(&L)链表是一个进行动态存储管理的结构，因此在初始化时不需要按照线性表实际所需最大容量进行预分配

4、。voidInitList_L(LinkList&L){//创建一个带头结点的空链表，L为指向头结点的指针}//InitList算法时间复杂度：O(1)L=newLNode;if(!L)exit(1);//存储空间分配失败L->next=NULL;操作DestroyList(&L)与ClearList(&L)voidDestroyList_L(LinkList&L){//销毁以L为头指针的单链表，//释放链表中所有结点空间while(L){p=L;　L=L->next;deletep;}}//DestroyList算法时间复杂度：O(Li

5、stLength(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和i单链表是一种顺序存取的结

6、构，为找第i个数据元素，必须先找到第i-1个数据元素。因此不论i值为多少，都必须从头结点开始起"点数"，直数到第i个为止。头结点可看成是第0个结点。p和j同步变化，始终保持指针p指向第j个结点StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，若1≤i≤LengthList(L)，则用e带回第i个元素的值且返回函数值为TRUE,否则返回函数值为FALSE}//GetElem_L算法时间复杂度为:O(ListLength(L))p=L->next;j=1;//p指向第一个结点，

7、j为计数器while(p&&jnext;++j;}//顺指针向后查找，直到p指向第i个元素或p为空if(!p

8、

9、j>i)returnFALSE;//第i个元素不存在e=p->data;//取得第i个元素returnOK;ai-1线性表的操作ListInsert(&L,i,e)在单链表中的实现：有序对改变为和eaiai-1因此，在单链表中第i个结点之前进行插入的基本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。可见，在链表中插入结点只需要修改指针。但同时，若要在第

10、i个结点之前插入元素，修改的是第i-1个结点的指针。StatusListInsert_L(LinkList&L,inti,ElemTypee){//L为带头结点的单链表的头指针，