数据结构课件第二章线性表3讲

2023/9/17计算机科学与技术教研室1/18第二章线性表

第3讲2.3线性表的链式表示和实现

1、链式查找

2、插入

3、删除

4、单链表的建立

5、单链表特点2023/9/17计算机科学与技术教研室2/182.3线性表的链式表示和实现特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点 数据域：元素本身信息指针域：指示直接后继的存储位置数据域指针域结点2023/9/17计算机科学与技术教研室3/18ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针2023/9/17计算机科学与技术教研室4/18实现typedefstructLNode{

ElemType

data;structLNode*next;}LNode,*LinkList;LNode*h,*p;datanextp结点（*p）(*p)表示p所指向的结点(*p).data

p->data表示p指向结点的数据域(*p).next

p->next表示p指向结点的指针域生成一个LNode型新结点：p=(LinkList)malloc(sizeof(LNode));系统回收p结点：free(p)线性链表定义：结点中只含一个指针域的链表叫~，也叫单链表2023/9/17计算机科学与技术教研室5/18头结点：在单链表第一个结点前附设一个结点叫~头结点指针域为空表示线性表为空ha1a2头结点an^…...h空表^2023/9/17计算机科学与技术教研室6/18单链表的基本运算查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULLWhile循环中语句频度为若找到结点X，为结点X在表中的序号否则，为n算法评价2023/9/17计算机科学与技术教研室7/18StatusGetElem_L(LinkListL,intpos,ElemType&e){//L为带头结点的单链表的头指针。当线性表中存在第pos个//元素存在时，则将第pos个数据元素的值赋给e并返回OK，//否则返回ERRORp=L->next;j=1;//初始化，p指向第一个结点，j为计数器while(p&&j<pos){//顺指针向后查找，直到p指向第pos个元素或p为空p=p->next;++j;}if(!p||j>pos)returnERROR;//第pos个元素不存在e=p->data;//取第pos个元素returnOK;}//GetElem_L算法的时间复杂度为:O(ListLength(L))查找2023/9/17计算机科学与技术教研室8/18C源代码:LNode*dlbcz(LNode*h,intx){ LNode*p; p=h; while(p!=NULL&&p->data!=X) p=p->next; return(p);}2023/9/17计算机科学与技术教研室9/18插入：在线性表两个数据元素a和b间插入x，已知p指向apabxsp->next=s;s->next=p->next;单链表插入视频演示算法评价2023/9/17计算机科学与技术教研室10/18//在带头结点的单链线性表L中第i个位置之前插入元素eStatusListInsert_L(LinkList&L,inti,ElemTypee){p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;returnOK;}//ListInsert_L插入2023/9/17计算机科学与技术教研室11/18C源代码：voiddlbcr(LNode*p,intx){ LNode*s; s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=p->next; p->next=s;}2023/9/17计算机科学与技术教研室12/18pabc算法评价删除：单链表中删除b，设p指向ap->next=p->next->next;单链表删除视频演示2023/9/17计算机科学与技术教研室13/18//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值StatusListDelete_L(LinkList&L,inti,ElemType&e){p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;free(q);returnOK;}//ListDelete_L删除2023/9/17计算机科学与技术教研室14/18C源代码：voiddlbsc(LNode*p){ LNode*q; if(p->next!=NULL) {q=p->next; p->next=q->next; free(q); }}2023/9/17计算机科学与技术教研室15/18动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针算法评价h头结点an^0h头结点an-10an^a2…...h头结点an-10an^ha1a2头结点an^…...0Ch2_3.ch头结点0^2023/9/17计算机科学与技术教研室16/18//逆位序输入n个元素的值，建立带头结点的单链线性表LvoidCreateList_L(LinkList&L,intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));scanf(&p->data);p->next=L->next;L->next=p;}}//CreateList_L建单链表2023/9/17计算机科学与技术教研室17/18C源代码：LNode*dlbjl(inta[],intn){ LNode*s,*h; inti; h=(LNode*)malloc(sizeof(LNode)); h->data=0; h->next=NULL; for(i=n;i>0;i--) {s=(LNode*)mallo