严蔚敏数据结构课件.ppt

《严蔚敏数据结构课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表2.3线性表的链式表示和实现一、单链表二、结点和单链表的C语言描述三、线性表的操作在单链表中的实现四、其它形式的链表用一组地址任意的存储单元存放线性表中的数据元素。一、单链表以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素或数据元素的映象)以“结点的序列”表示线性表称作链表以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。头结点a1a2…...an^头指针头指针有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空Typ

2、edefstructLNode{ElemTypedata;//数据域structLnode*next;//指针域}LNode,*LinkList;二、结点和单链表的C语言描述LinkListL；//L为单链表的头指针三、单链表操作的实现GetElem(L,i,&e)//取第i个数据元素ListInsert(&L,i,e)//插入数据元素ListDelete(&L,i,&e)//删除数据元素ClearList(&L)//重置线性表为空表CreateList(&L,n)//生成含n个数据元素的链表L线性表的操作GetElem(L,i,&e)在单链表中的实现:21

3、1830754256∧pppj123因此，查找第i个数据元素的基本操作为：移动指针，比较j和i。单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。令指针p始终指向线性表中第j个数据元素。StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，以e返回第i个元素}//GetElem_L算法时间复杂度为:O(ListLength(L))p=L->next;j=1;//p指向第一个结点，j为计数器while(p&&jnext;++j;}//顺指针向后查找，直

4、到p指向第i个元素//或p为空if(!p

5、

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

7、tL,inti,ElemTypee){//L为带头结点的单链表的头指针，本算法//在链表中第i个结点之前插入新的元素e}//LinstInsert_L算法的时间复杂度为:O(ListLength(L))……p=L;j=0;while(p&&jnext;++j;}//寻找第i-1个结点if(!p

8、

9、j>i-1)returnERROR;//i大于表长或者小于1s=(LinkList)malloc(sizeof(LNode));//生成新结点s->data=e;s->next=p->next;p->next=s;//插入returnOK;ea

10、i-1aiai-1sp线性表的操作ListDelete(&L,i,&e)在链表中的实现:有序对和改变为ai-1aiai+1ai-1在单链表中删除第i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p->next;p->next=q->next;e=q->data;free(q);pqStatusListDelete_L(LinkListL,inti,ElemType&e){//删除以L为头指针(带头结点)的单链表中第i个结点}//ListDelet

11、e_L算法的时间复杂度为:O(ListLength(L))p=L;j=0;while(p->next&&jnext;++j;}//寻找第i个结点，并令p指向其前趋if(!(p->next)

12、

13、j>i-1)returnERROR;//删除位置不合理q=p->next;p->next=q->next;//删除并释放结点e=q->data;free(q);returnOK;操作ClearList(&L)在链表中的实现:voidClearList(&L){//将单链表重新置为一个空表while(L->next){p=L->next;L->nex

14、t=p->next;}}//ClearListfre