【文档说明】数据结构-C语言版第二章-线形表课件.ppt，共(65)页，452.512 KB，由小橙橙上传

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

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

第二章线性表本章主要介绍线性表的定义、运算和线性表的几种存储结构等内容重点：线性表的定义、线性表的基本操作，线性表的存储结构难点：线性表的基本操作，线性表的存储结构教学目标线性表是最简单常用的数据结构，顺序存储结构链式存储结构也是应用中最常用的存储方法，这一部分内容和方法掌握了，有助于理解和

掌握后续章节的内容，如栈队列串是特殊的线性表，数组和广义表是线性表的扩展；有助于理解和掌握树和图等复杂的数据结构存储结构和图等复杂结构的操作算法，因为树和图的存储结构大多或是这两种存储结构的扩充，或是它们的组合，因此这一章的内容非常重要，同学们要很好地学

习理解和掌握。第二章线性表第二章线性表2.1线性表概念及基本操作2.2线性表的顺序存储和实现2.3线性表的链式存储和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加第二章线性表在本课程介绍的几种数据结构中，线性表是最常简单的，也是最常用的数据结构，线

性表在实际应用大量使用，并不是一个陌生的概念。线性表是n个类型相同数据元素的有限序列，通常记作（a1,a2,a3,…,an）。姓名电话号码蔡颖63214444陈红63217777刘建平63216666王小林6

3218888张力63215555...2.1线性表的概念例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,EZ）。例3、某单位的电话号码簿。一线性表的逻辑结构2.1线性表的概念说明：设A=（

a1,a2,...,ai-1,ai,ai+1,…,an）是一线性表1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；2）在表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱，ai+1是a

i的直接后继；3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；4）线性表中元素的个数n称为线性表的长度，n=0时称

为空表；5）ai是线性表的第i个元素，称i为数据元素ai的序号，每一个元素在线性表中的位置，仅取决于它的序号；2.1线性表的概念线性表的其他表示方式二元组表示L=<D,S>，其中D={a1,a2,a3,...an}S={R}R={<a1,a2>,<a2,a3>,<a3,a

4>…<an-1,an>}图示表示ai+1a1ai-1a2aian顶点：表示数据边：表示是数据间的顺序结构关系2.1线性表的概念二线性表的基本操作1存取操作：存取线性表中第i个数据元素；2查找操作：在线性表中

查找满足条件元素；3插入操作：在线性表的第i个元素之前插入一个新元素;4删除操作：删除线性表的第i个元素；5分解操作：将一个线性表拆分为多个线性表；6合并操作:7排序2.1线性表的概念说明1上面列出的操作，只是线性表的一些常用的基本操作；2不同

的应用，基本操作可能是不同的；3线性表的复杂操作可通过基本操作实现；为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；2）线性表中数据元素的顺序关系；如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？？2.2线性表的顺序存储和实现一线性表的顺序存储结构——顺序表二

顺序表的基本操作算法三效率分析线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。a1a2ai-1aiai+1an线性表（a1,a2,a3,...an）的顺序存储结构用顺序存储结构存储的线性表——称为顺序表2.2线性

表的顺序存储和实现一线性表的顺序存储结构——顺序表线性表的顺序存储结构2.2线性表的顺序存储和实现说明：·在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存储顺序反映（表示）出来；·假设线性表中每个数据元素占用t个存储单元，那么，在顺序存储结构中，线性

表的第i个元素的存储位置与第1个元素的存储位置的关系是：Loc(ai)=Loc(a1)+(i–1)ta1a2ai-1aiai+1ant个单元Loc(a1)Loc(ai)2.2线性表的顺序存储和实现怎样在计算

机上实现线性表的顺序存储结构？？可用C语言中的一维数组来表示,但数组不是线性表,数组存放的是线性表,数组的类型由线性表中的数据元素的性质决定.如:#defineMAX100intv[MAX];2.2线性表的顺序存储和实现顺序表的类型定义#defineLIST_I

NIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{ElemType*elem;//线性表存储空间基址intlength;//当前线性表长度intlistsize;//当前分配

的线性表存储空间大小//（以sizeof(ElemType)为单位）}SqList;SqList：类型名，SqList类型的变量是结构变量，它的三个域分别是：*elem：存放线性表元素的一维数组基址；其

存储空间在初始化操作（建空表）时动态分配；length：存放线性表的表长；listsize：用于存放当前分配（存放线性表元素）的存储空间的大小。2.2线性表的顺序存储和实现存放线性表元素的一维数组设A=（a1,a2,a3,...an）是一

线性表，L是SqList类型的结构变量，用于存放线性表A，则L在内存中的状态如图所示：顺序表通过元素的存储顺序反映线性表元素间的逻辑关系a1a2ai-1aiai+1an01i-2i-1in-199L.elemL.lenghtL.listsizen99

2.2线性表的顺序存储和实现二、顺序表的基本操作算法1.插入insert(v,x,i)功能：在顺序表v中的第i(1<=i<=n+1)个数据元素之前插入一个新元素x,插入前线性表为(a1,a2,a3,…,ai-1,ai,,…an)插入后,线性表长度为n+1,线性表为(a1

,a2,a3,…,ai-1,x,ai,,…an)2.2线性表的顺序存储和实现插入前插入后插入操作示意图：a1a2ai-1aiai+1an01i-2i-1in-1MAX-1nP_lena1a2ai-1xaian

01i-2i-1n-2n-1nMAX-1n+1P_len2.2线性表的顺序存储和实现intinsert(intv[],inti,intx,int*p_len){intj;if(i<=0||i>*p_len)ret

urn(0);/*i值不合法for(j=*p_len,j>=i;j--)v[j]=v[j-1];v[i-1]=x;*p_len++;/*插入x,表长增1return(1);}插入操作算法删除算法的主要步骤1）若i不合法或表L空，算法结束，并返回0；否则

转2）2）将第i个元素之后的元素（不包括第i个元素）依次向前移动一个位置;3）表长-12.2线性表的顺序存储和实现2.2线性表的顺序存储和实现intdelete(intv[],inti,int*p_len){int

j;if(i<=0||i>*p_len)return(0);/*i值不合法for(j=i,j<*p_len;j++)v[j-1]=v[j];*p_len--;return(1);}删除操作算法2.2线性表的顺序存储和实现怎样在顺序表中取第i个数据元素？？2

.2线性表的顺序存储和实现插入位置移动元素个数1n2n-1in-i+1n1n+10·算法时间复杂度分析算法时间复杂度取决于移动元素的个数，移动元素的个数不仅与表长有关，而且与插入位置有关。a1a2ai-1aiai+1an01i-1i-

2n-1..2.2线性表的顺序存储和实现由此可见·在顺序表中插入一个元素，平均要移动表的一半元素。·表长为n的顺序表，插入算法的时间复杂度为O（n）Eis=+=11nipi(n–i+1)假设在线性表的任何位置插入元素的概率相同，即pi=1/

(n+1)pi:在第i个元素之前插入元素的概率，在长度为n的顺序表中插入一个元素，所需移动元素个数数学期望值为：ninnEisni21)1(1111=+−+=+=2.2线性表的顺序存储和实现顺序表是线性表最简单的一种存储结构小结顺序表的特点：

1通过元素的存储顺序反映线性表中数据元素之间的逻辑关系；2可随机存取顺序表的元素；3顺序表的插入、删除操作要通过移动元素实现；2.3线性表的链式存储和实现线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。为了表示线性表中元素的先后关系，每个元素除了需要存储自身的信息

外还需保存直接前趋元素或直接后继元素的存储位置。ai+1a1ai-1a2aian2.3线性表的链式存储和实现2.3.1线性链表一线性链表的概念二线性链表的基本操作算法三线性链表的其它操作2.3.2循环

链表2.3.3双向链表一双向链表的概念二双向链表的基本操作算法一线性链表的概念1线性链表2.3.1线性链表a4a3a1a20101010241014101010121014101610181020102210241026用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外

，还保存了直接后继元素的存储位置。用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的ai-1aia2a1ai+1nan结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结

点；结点的数据域：结点中用于保存数据元素的部分;结点的指针域：结点中用于保存数据元素直接后继存储地址的部分;线性链表有关术语2.3.1线性链表存储数据元素存储后继结点存储地址结点数据域指针域2.3.1线性链表头指针：用于存放线性链表中第一个结点的存储地址;空指针：不指向任何结点，线性

链表最后一个结点的指针通常是指针;头结点：线性链表的第一元素结点前面的一个附加结点，称为头结点；带头结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表；head是头指针ai-1aia2a1ai+1nan头结点空指针head线性链表的每个结点中

只有一个指针域故也称为单链表2.3.1线性链表怎样在计算机上实现线性链表？？2.3.1线性链表结点变量图示structnode{intdata;Structnode*next;}typedefstructnodeNODE;·Nod

e：结构类型名；Node类型结构变量有两个域：data：用于存放线性表的数据元素，next：用于存放元素直接后继结点的地址；·该类型结构变量用于表示线性链表中的一个结点；·NODE*p：p为指向结点(结构)的指针变量；数据域指针域datanextnode类型结构变量pp

是NODE类型的指针变量线性链表的结点类型定义及指向结点的指针类型定义2.3线性链表两个C函数1)malloc(intsize)功能：在系统内存中分配size个的存储单元，并返回该空间的基址。使用方法：p=(NODE*)malloc(sizeof(NODE));为p申请一个结点pp=(NOD

E*)malloc(sizeof(NODE));图示2.2线性链表调用free(p)01299p调用free(p)图示2)free(p)功能：将指针变量p所指示的存储空间，回收到系统内存空间中去使用方法：...NODE*p;p=(NODE*)mall

oc(sizeof(NODE));//一旦p所指示的内存空间不再使用，//调用free()回收之free(p);2.3.1线性链表ai-1aia2a1ai+1nanP二线性链表基本操作的算法如何在线性链表上实现线性表的基本操作？

如何建表？如何插入？删除？？约定用带头结点的线性链表存储线性表2.3.1线性链表head∧算法：NODE*create_head(){NODE*headhead=(NODE*)malloc(sizeof(NODE));head->next=null;Return(he

ad);}1）初始化操作功能：建空线性链表参数：head为线性链表的头指针主要步骤：调用malloc()分配一结点的空间,并将其地址赋值给head；建立链表•NODE*create_next(n)/*建立有n个结点的线性单链表的算法{NODE*head,*p,*q;

inti;p=(NODE*)malloc(sizeof(NODE));head=p;for(i=I;I<=n;i++){q=(NODE*)malloc(sizeof(NODE));q->data=i;q->next=NULL;p->next=q;p=q;}return

(head);}插入结点•q=(NODE*)malloc(sizeof(NODE));q->deta=‘a’;q->next=p->next;p->next=q;headzyxpyxzpheada13插入操作Insert_next(NODE*hea

d,intx,inti)功能：在线性链表的第i个元素结点之前插入一个新元素结点x；插入操作图示：2.3.1线性链表插入前插入后ai-1aia2a1ai+1nanheadai-1aia2a1ai+1nanxhe

ad2.3.1线性链表插入操作主要步骤：1）查找链表L的第i-1个元素结点；2）为新元素建立结点；3）修改第i-1个元素结点的指针和新元素结点指针完成插入；•Intinsert_next(NODE*head,intx,i

nti){NODE*p,*s;intj;p=head;j=0;while((p!=NULL)&&(j<i-1)){p=p->next;j++;}if(p==NULL)return(0);s=(NODE*(malloc

(sizcof(NODE));s->data=x;s->next=p->next;p->next=s;return(1);}删除结点•q=p->next;p->next=q->next;free(q);headzyxqyxz

qheadpp2.3.1线性链表删除操作主要步骤：1）查找链表的第i-1个元素结点,使指针p指向它,将指针q指向第i个结点；2）修改第i-1个元素结点指针，使其指向第i个元素结点的后继；3)回收q指针所指的第i个结点空间；2.3.1线性链表删除前删除后ai-1aia

2a1ai+1nanheadai-1aia2a1ai+1nanheadppqq•在线性链表中删除第i个结点•Intdelete_next(NODE*head,inti){NODE*p,*q;intj;p=head;j=0

;while((p!=NULL)&&(j<i-1)){p=p->next;j++;}if(p==NULL)return(0);q=p->next;p->next=q->next;free(q);return(1);}2.

3.1线性链表三线性链表的其他操作的实现例：将两个递增有序线性链表归并成一个递减有序表。设线性表A、B分别用头指针为head_a、head_b的两个带头结点的线性链表存储,归并后的递减有序表头指针为head,将两表数据较小的结点依次取出插入到新表利用基本操作直接对链表进行操作2.3.1线

性链表线性链表归并操作图示73n952n7head_ahead_b79n2head38785NODE*merge_next(NODE*head_a,NODE*head_b){NODE*p,*q,*head;head=(NODE*)malloc(sizeof(NODE));head-

>next=NULL;p=head_a->next;q=head_b->next;while((p!=NULL)&&(q!=NULL))If(p->data<q->data){head_a->next=p->next;p->next=head->next;he

ad->next=p;p=head_a->next;}else{head_b->next=q->next;q->next=head->next;head->next=q;q=head_b->next;}while(p!=NULL){head_a-

>next=p->next;p->next=head->next;head->next=p;p=head_a->next;}while(q!=NULL){head_b->next=q->next;q->next=head->next;head->next=q;q=head_b->next;}fr

ee(head_a);free(head_b);return(head);}2.3.1线性链表小结线性链表是线性表的一种链式存储结构线性链表的特点1通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；2插入删除操作通过修改结点的指针实现；3不能随机存取元素

；1循环链表的概念循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点2循环链表图示2.4单向循环链表(a)非空表（b）空表headheada1an2.4单向循环链表说明·在解决某些实际问题时循环链表可能要比线性链表方便些。

如将一个链表链在另一个链表的后面；·循环链表与线性链表操作的主要差别是算法中循环结束的条件不是p或p->next是否为NULL,而是它们是否等于首指针；·对循环链表，有时不给出头指针，而是给出尾指针aa1an给出尾指针的循环链表2.4单向循环链表baa1anbb1

bnaa1anb1bnqqppp=a->next;q=b->next;a->next=q->next;b->next=p;free(q);1双向链表的概念2.5双向链表(a)结点图示数据域指针域指针域结点存储数据元素存储后继结点的地址存储

前趋结点的地址双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。2.5双向链表2双向链表图示head(b)空的双向循环链表（c）非空的双向循环链表headabStructnode{in

tdatastructnode*lnext,*rnext;}在双向链表中删除结点时指针变化情况在双向链表中插入一个结点时指针的变化情况pai-1x①②③④aipaiai+1①②ai-12.5双向链表3、双向链表的基本操作算法2.5双向链表1）插入操作算法(在p所指结点之后插入q结

点的过程)q=(NODE*)malloc(sizeof(NODE));q->data=x;q->rnext=p->rnext;q->lnext=p;p->rnext=q;(q->rnext)->lnext=q;2.5双向链表2）

删除操作算法(p->lnext)->rnext=p->rnext;(p->rnext)->lnext=p->lnext;free(p);aiai+1p①②ai-1第二章线性表小结本章学习了线性表的顺序存储结

构——顺序表，链式存储结构,线性链表,循环链表,双向链表，以及在这两种存储结构下如何实现线性表的基本操作。这里再一次需要强调：本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存

储线性表，如何在计算机上实现线性表的操作。我们已经看到，在不同的存储结构下，线性表的同一操作的算法是不同的，在顺序表存储结构下，线性表的插入删除操作，通过移动元素实现，在线性链表存储结构下，线性表的插入删除操作，通过修改指针实现。对于某一实际问题

，如何选择合适的存储结构，如何在某种存储结构下实现对数据对象的操作，我们要通过数据结构课程的学习，很好地理解各种存储结构是如何存储和表达数据对象的有关信息的，各种存储结构下操作的特点。为实际问题的程序设计打下坚实

的基础。上机实验题上机验证第一、二章的算法例子和习题•#defineNULL0•structnode•{intdata;•structnode*next;•};typedefstructnodeNODE;•NODE*crea

te_next(n)•{NODE*head,*p,*q;•inti;•p=(NODE*)malloc(sizeof(NODE));•head=p;•for(i=1;i<=n;i++)•{q=(NODE*)malloc(size

of(NODE));•q->data=i;q->next=NULL;•p->next=q;p=q;•}•return(head);上机实例•intinsert_next(NODE*head,intx,

inti)•{NODE*p,*s;intj;•p=head;j=0;•while((p!=NULL)&&(j<i-1))•{p=p->next;j++;}•if(p==NULL)return(0);•s=(NODE*)malloc(sizeof(NODE))

;•s->data=x;•s->next=p->next;•p->next=s;•return(1);•}上机实例上机实例•main()•{•intj;•NODE*t;•t=create_next(10);•for(j=1;j<=10;j++)•{t=t->n

ext;printf("%3d",t->data);•}•insert_next(t,99,6);•for(j=1;j<=11;j++)•{t=t->next;printf("%3d",t->data);•}•}