【文档说明】C语言工程设计3-2_线性表.pptx，共(60)页，560.609 KB，由精品优选上传

转载请保留链接：https://www.ichengzhen.cn/view-290367.html

以下为本文档部分文字说明：

线性表主要知识点线性表抽象数据类型顺序表单链表循环单链表循环双向链表静态链表设计举例12.1线性表抽象数据类型1.线性表的定义线性表是一种可以在任意位置插入和删除数据元素操作、由n(n≥0)个相同类型数据元素a0,a1,…,an-1组成的线性结构。线性结

构:22.线性表抽象数据类型数据:｛a0,a1,…,an-1｝,ai的数据类型为DataType操作:(1)ListInitiate(L)初始化线性表(2)ListLength(L)求当前数据元素个数(3)ListInsert(L,i,x)插入数据元素(4)ListDelete(L,

i,x)删除数据元素(5)ListGet(L,i,x)取数据元素｛a0,a1,…,an-1｝表示数据元素有次序关系,简称序列。32.2线性表的顺序表示和实现1.顺序表的存储结构实现顺序存储结构的方法是

使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元中，这样线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置上。顺序表的存储结构如图所示顺序存储结构的线性表称作顺序表4a0a1a2a3a4a5…lis

tsize=6MaxSize-10123456其中a0,a1,a2等表示顺序表中存储的数据元素，list表示顺序表存储数据元素的数组，MaxSize表示存储顺序表的数组的最大存储单元个数，size表示顺序表当前存储的数据元素个数。t

ypedefstruct{DataTypelist[MaxSize];intsize;}SeqList;52.顺序表操作的实现（1）初始化ListInitiate(L)voidListInitiate(SeqList*L

){L->size=0;/*定义初始数据元素个数*/}（2）求当前数据元素个数ListLength(L)intListLength(SeqListL){returnL.size;}6（3）插入数据元素ListInsert(L,

i,x)intListInsert(SeqList*L,inti,DataTypex){intj;for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];/*依次后移*/L->list[i]=x;/*插入x*/L->size++;/*元素个数

加1*/return1;}7101112141516listlistMaxSize-10123456i=3Size=6size=713待插数据x710111213141516MaxSize-101234567i=3size=6......8（4）删除数据元素ListDelete(

L,i,x)intListDelete(SeqList*L,inti,DataType*x){intj;*x=L->list[i];/*保存删除的元素到x中*/for(j=i+1;j<=L->size-1;j++)L->list[j-1]=L->list[j];/*依次前移*/L-

>size--;/*数据元素个数减1*/return1;}910111213141516list删除前101112141516list删除后MaxSize-10123456MaxSize-10123456i=3s

ize=7size=6要删的数据x13......10（5）取数据元素ListGet(L,i,x)intListGet(SeqListL,inti,DataType*x){if(i<0||i>L.size-1){printf("参数

i不合法!\n");return0;}else{*x=L.list[i];return1;}}113.顺序表操作的效率分析时间效率分析:算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作(最深层语句频度)T(n)=O(移动元素次数)而移动元素的个数取决于插入或删除元素的

位置i.若i=size，则根本无需移动（特别快）；若i=0，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。12设Pi是在第i个存储位置插入一个数据元素的概率，顺序表中的数据元素个数为n,当在顺序表的任何位置上插入数据元素的概率相等时，有Pi=1/(

n+1),则插入时的平均移动次数为:n(n+1)/2÷（n+1）＝n/2≈O(n)同理可证:顺序表删除一元素的时间效率为:T（n)=(n-1)/2≈O(n)001()()12nnisiiinEpninin===−=−=+

110011()()2nndliiinEqninin−−==−=−=−=13顺序表中的其余操作都和数据元素个数n无关，因此，在顺序表中插入和删除一个数据元素的时间复杂度为O(n),其余操作的时间复

杂度都为O(1)主要优点是算法简单，空间单元利用率高；主要缺点是需要预先确定数据元素的最大个数，插入和删除时需要移动较多的数据元素。主要优缺点144.顺序表应用举例例：编程实现如下任务:建立一个线性表，首先依次输入数据元素1，2，3，…，

10，然后删除数据元素5，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过100个。15实现方法：1、采用直接编写一个主函数实现。2、利用已设计实现的抽象数据类型模块。（存放在头文件名为SeqList.h中

，通过#include“SeqList.h”）程序设计如下：#include<stdio.h>#defineMaxSize100typedefintDataType;#include"SeqList.h"16voidmain(void){SeqListmyList;inti,x;ListI

nitiate(&myList);for(i=0;i<10;i++)ListInsert(&myList,i,i+1);ListDelete(&myList,4,&x);for(i=0;i<ListLength(myList);i+

+)ListGet(myList,i,&x);}程序运行结果：1234678910172.3线性表的链式表示和实现1.单链表的结构(1)单链表中构成链表的结点只有一个指向直接后继结点的指针域。其结构特点：逻

辑上相邻的数据元素在物理上不一定相邻。18结点结构如图示：指针域数据域nextdata或数据域：存储元素数值数据指针域：存储直接后继的存储位置19(2)头指针、头结点和首元结点的区别头指针头结点首元结点a0heada1…

an^示意图如下：20头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a０的结点。(3)带头结点单链表和不带头结点单链表的比较21p

a0a1an-1∧…headdatanextx∧s(a)插入前pa0a1an-1∧…headdatanextx∧s(b)插入后1).在带头结点单链表第一个数据元素前插入结点222).删除带头结点单链表第一个数据元素结点pa0

a1an-1∧…headdatanext233).在不带头结点单链表第一个数据元素前插入结点a0a1an-1∧…headx∧s(a)插入前a0a1an-1∧…headxs(b)插入后244).在不带头结点单链表其他数据元素前插入结点pai-1a0aian-1∧…headdatanextxs

…×255).删除不带头结点单链表第一个数据元素结点a0a1an-1∧…headdatanext×6).删除不带头结点单链表其他数据元素结点pai-1a0aian-1∧…headdatanext…×ai+126结论：（1）带头结点单链表

无论在第一个数据元素结点前插入，还是在其他结点前插入，操作方法一样；而不带头结点单链表在第一个数据元素结点前插入，和在其他结点前插入，操作方法不一样（2）删除操作和插入操作类似（3）设计带头结点单链表的算法时，头指针参数可设计成输入型参数；设计不带头结点单链表

的算法时，头指针参数必须设计成输出型参数（4）因此，带头结点单链表的算法设计简单27结点定义：typedefstructNode{DataTypedata;structNode*next;}SLNode;2.单链表的操作实现（1）初始化ListInitia

te(head)voidListInitiate(SLNode**head){*head=(SLNode*)malloc(sizeof(SLNode));(*head)->next=NULL;}28（2）求当前数据元素个数ListLength(head)int

ListLength(SLNode*head){SLNode*p=head;intsize=0;while(p->next!=NULL){p=p->next;size++;}returnsize;}29head...0a1a1−na∧size=0(a)...0a1a1−na∧

size=n(b)pphead30（3）插入ListInsert(head,i,x)intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;p=head;j=-1;while(p->next!=NULL&&j

<i-1){p=p->next;j++;}if(j!=i-1){printf(“插入位置参数错！”);return0;}q=(SLNode*)malloc(sizeof(SLNode));q->dat

a=x;q->next=p->next;p->next=q;return1;}310a...ia1−na∧qx...1−ia0a...ia1−na∧...1−iaxq(a)(c)(b)ppheadhead①②32说明：①要在带头结点的单链表第i（0≤i≤si

ze）个结点前插入一个存放数据元素x的结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后动态申请一个结点存储空间并由指针q指示，并把数据元素x的值赋予新结点的数据元素域（即q->data=x），最后修改新结点的指针域指向ai结点（即q->next=p->next），并修改ai-1结

点的指针域指向新结点q（即p->next=q）。②循环条件由两个子条件逻辑与组成，其中子条件p->next!=NULL保证指针所指结点存在，子条件j<i-1保证最终让指针p指向ai-1结点。33（4）删除ListDelete(hea

d,i,x)intListDelete(SLNode*head,inti,DataType*x){SLNode*p,*s;intj;p=head;j=-1;while(p->next!=NULL&&p-

>next->next!=NULL&&j<i-1){p=p->next;j++;}if(j!=i-1){printf(“插入位置参数错！”);return0;}s=p->next;*x=s->data;p->next=p->

next->next;free(s);//释放空间return1;}340a...ia1−na∧...1−ia(a)0a...1−na∧...1−ia(b)iaiasheadheadp①1+ia1+iap说明：要在带头结点

的单链表中删除第i（0≤i≤size-1）个结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向ai结点（即s=p->next），并把数据元素ai的值赋予x（即*x=s->data），最后把ai结点脱链（即p->next=p->next->next），并

动态释放ai结点的存储空间（即free(s)）。删除过程如图2-14所示。图中的①对应算法中的删除语句。35（5）取数据元素ListGet(head,i,x)intListGet(SLNode*head,inti,DataType*x){SLNode*p;intj;p=head;j=-1;wh

ile(p->next!=NULL&&j<i){p=p->next;j++;}//定位if(j!=i){printf(“取元素位置参数错！”);return0;}*x=p->data;return1;}36（6）撤消单链表Des

troy(head)voidDestroy(SLNode**head){SLNode*p,*p1;p=*head;while(p!=NULL)//free（null）不可以{p1=p;p=p->next;free(p1);

}*head=NULL;}37001()()12nnisiiinEpninin===−=−=+110011()()2nndliiinEqninin−−==−=−=−=4.单链表操作的效率分析单链表的插入和删除操作不需移动数据元素，只需比较数据元素。因

此，当在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：删除一个数据元素时比较数据元素的平均次数为：另外，单链表求数据元素个数操作的时间复杂度为O(n)。38和顺序表相比主要优点是不需要预先确定数据元素的最大个数，插入和删

除操作不需要移动数据元素；主要缺点是查找数据元素时需要顺序进行，不能像顺序表那样随机查找任意一个数据元素。另外，每个结点中要有一个指针域，因此空间单元利用率不高。而且单链表操作的算法也较复杂。单链表和顺序表相比，单链表的优点和缺点正

好相反。395.单链表应用举例例：编程实现如下任务:建立一个线性表，首先依次输入数据元素1，2，3，…，10，然后删除数据元素5，最后依次显示当前线性表中的数据元素。要求采用单链表实现。#include<stdio.h>#include<stdlib.h>#include<ma

lloc.h>typedefintDataType;#include"LinList.h"40voidmain(void){SLNode*head;inti,x;ListInitiate(&head);for(i=0;i<10;i++)

ListInsert(head,i,i+1);ListDelete(head,4,&x);for(i=0;i<ListLength(head);i++){ListGet(head,i,&x);printf(“%d”,x);}Destroy(&head);}程序运行结果：1234678

910412.4循环单链表循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域指向整个链表的第一个结点，从而使链表形成一个环。它的优点是从链尾到链头比较方便。循环单链表也有带头结点和不带头结点两种结构。一个带头结

点的循环单链表如下图示：42a0a1an-1…headhead(a)空链表(b)非空链表程序设计：p!=NULL改为p!=headP->next!=NULL改为p->next!=head432.5双向链表双向链表是每个结点除后继指针域外还有一个前驱指

针域，它有带头结点和不带头结点，循环和非循环结构，双向链表是解决查找前驱结点问题的有效途径。结点结构如图示：priordatanext下图是带头结点的循环双向链表的结构，可见，其前驱指针和后继指针各自构成自己的循环单链表。44head(a)空链表a

0a1an-1head(b)非空链表…在双向链表中:设指针p指向第i个数据元素结点，则p->next指向第i+1个数据元素结点，p->next->prior仍指向第i个数据元素结点，即p->next->prior=p;同样p-

>prior->next=p。45循环双向链表的插入过程如图示：a0aian-1head…xs…ai-1××…④①②③p46删除过程如图示：ai+1aian-1head……ai-1××①②p472.6静态链表在数组中增加一个(或两个)指针域用来存放下一个(或上一个)数据元素在

数组中的下标，从而构成用数组构造的单链表。因为数组内存空间的申请方式是静态的，所以称为静态链表，增加的指针称做仿真指针。结构如下：ABCE∧headD(a)常规链表48A1B2C3D4E-1┇(b)静态链表1d

atanext01234┇maxSize-1A2E-1B4D1C3┇(b)静态链表2datanext01234┇maxSize-1492.7设计举例例2-4设计一个顺序表的删除函数，把顺序表L中的数据元素x删除。算法思想：首先，找到要删除元素的

位置，然后，从这个位置到最后一个元素，逐个前移，最后，把元素个数减1。50intListDataDelete(SeqList*L,DataTypex){inti,j;for(i=0;i<L->size;i++)if(x=

=L->list[i])break;if(i==L->size)return0;else{for(j=i;j<L->size;j++)L->list[j]=L->list[j+1];L->size--;return1;}}

51例2-5构造一个顺序表的删除算法，把顺序表L中所有值相同的数据元素x全部删除。算法思想：在例2-4所设计的删除算法的基础上，增加外重循环进行查找，查找到元素x则删除，然后继续进行这样的过程和删除过程，直到元素末尾结束。52intListMoreDataDele

te(SeqList*L,DataTypex){inti,j;inttag=0;for(i=0;i<L->size;i++){if(x==L->list[i]){for(j=i;j<L->size-1;j++)L->list[j]=L->list[j+1];L->size--;

i--;tag=1;}}returntag;}53例2-6设头指针为head，并设带头结点单链表中的数据元素递增有序，编写算法将数据元素x插入到带头结点单链表的适当位置上，要求插入后保持单链表数据元素的递增有序。算法思想：从链表的第一个数据元素结点开始，逐个比较每个结点

的data域值和x的值，当data小于等于x时，进行下一个结点的比较；否则就找到了插入结点的合适位置，此时申请新结点把x存入，然后把新结点插入；当比较到最后一个结点仍有data小于等于x时，则把新结点插入单链表尾。54voidLinListInsert(SLNode*head,Da

taTypex){SLNode*curr,*pre,*q;curr=head->next;pre=head;while(curr!=NULL&&curr->data<=x){pre=curr;curr=curr->next;}q=(SLNode*)malloc(sizeof(SLN

ode));q->data=x;q->next=pre->next;pre->next=q;}55算法设计说明：（1）在循环定位插入位置时，循环条件必须首先是curr!=NULL，然后是curr->data<=x。如果次序颠倒，则

当curr为空（即等于链表结束标记NULL）时,将因为curr->data不存在而出错；次序不颠倒时，当curr等于NULL时将退出循环，不会进行后边条件curr->data<=x的比较。（2）当比较

到最后一个结点仍有data小于等于x时，此时有pre指向最后一个结点，curr等于NULL，则上述算法把新结点插入到了单链表尾作为了单链表新的表尾结点。56例2-7设head为单链表的头指针，并设单链表带有头

结点，编写算法将单链表中的数据元素按照数据元素的值递增有序的顺序进行就地排序。算法思想：在例2-6算法的基础上，再增加一重循环即可实现全部数据元素的排序。由于此时的排序过程没有申请新的结点空间，所以这样的排序算法满足就地排序，即不增加新的内存空间的

设计要求。57具体实现过程是：把头指针head所指单链表置空（即初始时head所指单链表仅包含一个头结点），把去掉头结点的原单链表（设由头指针p指示）中的数据元素逐个重新插入head所指单链表中。每次插入从head所指单链表的第一个数据元素结点开始，逐个比

较head所指单链表每个结点的data域值和p所指单链表的当前第一个数据元素结点的data域值，当前者小于或等于后者时，用head所指单链表的下一个结点进行比较；否则就找到了插入结点的合适位置，从p所指单链表中取下当前第一个数

据元素结点插入到head所指单链表的合适位置。这样的过程一直进行到p所指单链表为空时结束。58voidLinListSort(SLNode*head){SLNode*curr,*pre,*p,*q;p=head->next;head->next=NULL;while(p!=NULL)

{curr=head->next;pre=head;while(curr!=NULL&&curr->data<=p->data){pre=curr;curr=curr->next;}q=p;p=p->next;q->next=pre->next;pre->next=q;

}}59练习：单链表的实现与应用（1）用带头结点的单循环链表作为存储结构。（2）使用C语言编写函数，实现单链表的基本操作：初始化链表、数据元素个数、插入、删除、取数据元素、撤销链表。（3）设计测试数据，要求测试数据能够全面的测试所设计程序的功能。60