数据结构第2章线性表课件.ppt

1、1线性结构的定义：线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。接后继。可表示为：（可表示为：（a a1 1,a,a2 2 ,a,an n）简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 的。的。特点特点 只有一个首结点和尾结点；只有一个首结点和尾结点；特点特点 除首尾结点外，其他结点只有一个直接前驱和一个除首尾结点外，其他结点只有一个直接前驱和一个直接后继。直接后继。线性结构包括：线性结

2、构包括：线性表、栈、队列、字符串、数组线性表、栈、队列、字符串、数组等，等，其中最典型、最常用的是其中最典型、最常用的是-见第见第2章章一对一一对一(1:1)2（a1,a2,ai-1，ai,ai1，,an）2.1 线性表的逻辑结构线性表的逻辑结构 1.线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点3例例1 分析分析26 个英

3、文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。（A,B,C,D,Z）学号学号姓名姓名性别性别年龄年龄班级班级012002009524刘禹圻刘禹圻男男 182002级计科级计科0201班班012002009613武武 锐锐男男 182002级计科级计科0202班班012002009710彭彭 隽隽男男 172002级计科级计科0203班班012002009801郭郭 芳芳女女 182002级计科级计科0204班班012002009904张珍珍女18182002级计科级计科0205班班：例例2 分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：分析：数据元素都是同

4、类型（数据元素都是同类型（记录）记录），元素间关系是线性的。，元素间关系是线性的。分析：分析：数据元素都是同类型（数据元素都是同类型（字母）字母），元素间关系是线性的。元素间关系是线性的。42.2.1 顺序表的表示顺序表的表示用一组用一组地址连续地址连续的存储单元依次的存储单元依次存储线性表的元素。存储线性表的元素。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或顺序映像。或顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：简言之：简

5、言之：逻辑上相邻的元素，物理上也相邻逻辑上相邻的元素，物理上也相邻可以利用可以利用数组数组VnVn来实现。来实现。注意：注意：在在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即：VnVn的有效范围是从的有效范围是从 VV0 0 VVn-1n-1 5线性表顺序存储特点：线性表顺序存储特点：1.逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出素存放位置亦可求出（利用数组利用数组VnVn的的下标下标）。）。设首元素设首元素a1的存放地址为的存放

6、地址为LOC(a1)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为：LOC(ai+1)=LOC(ai)+L 对上述公式的解释如图所示：对上述公式的解释如图所示：6线性表的顺序存储结构示意图线性表的顺序存储结构示意图a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i i2 2n n空闲区空闲区i+1i+1Lb=LOC(a1)b+L Lb+(i-1)+(i-1)L Lb+(n-1)+(n-1

7、)L Lb+(max-1)+(max-1)L L7设有一维数组，下标的范围是到，每设有一维数组，下标的范围是到，每个数组元素用相邻的个数组元素用相邻的个字节个字节存储。存储器按字存储。存储器按字节编址，设存储数组元素节编址，设存储数组元素 的第一个字节的的第一个字节的地址是地址是，则，则 的第一个字节的地址是的第一个字节的地址是113例例1因此：因此：LOC(M3)=98+5(3-0)=113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）82.2.2 顺序表的实现（或操作）顺序表的实现（或操作）回忆回忆：数据结构基本运算操作有：数据结构基本运算操

8、作有：修改、插入、删除、修改、插入、删除、查找、排序查找、排序1)1)修改修改 通过数组的下标便可访问某个特定元通过数组的下标便可访问某个特定元素并修改之。素并修改之。核心语句核心语句:Vi=x;显然，顺序表修改操作的时间效率是显然，顺序表修改操作的时间效率是T(n)=O(1)92)2)插入插入 在线性表的第在线性表的第i i个位置个位置前前插入插入一个元素一个元素实现步骤：实现步骤：将第将第n至第至第i 位的元素向后移动一个位置；位的元素向后移动一个位置；将要插入的元素写到第将要插入的元素写到第i个位置；个位置；表长加表长加1。事先应判断事先应判断:插入位置插入位置i 是否合法是否合法?表是

9、否已满表是否已满?应当有应当有1in+1 或或 i=1,n+1for(j=n;j=i;j)aj+1=aj;ai=x;n+;/元素后移一个位置元素后移一个位置/插入插入x x/表长加表长加1 1 核心语句：核心语句：10在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：1213212428304277121321242830427712345678123456789插入插入11实现步骤：实现步骤：将第将第i+1至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置；表长减表长减1。注意：注意：事先需要判断，事先需要判断，删除位置删除位置i

10、是否合法是否合法?应当有应当有1in 或或 i=1,n3)3)删除删除 删除删除线性表的第线性表的第i i个位置上的元素个位置上的元素for(j=i+1;jdata=;p-next=;方式方式3：p指向结点首地址，然后指向结点首地址，然后(*p).data=；(*p).nextb223.补充结构数据类型的补充结构数据类型的C表示法表示法 类型定义和变量说明可以合写为：类型定义和变量说明可以合写为：chy /chychy是自定义结构类型名称是自定义结构类型名称 char data;/定义数据域的变量名及其类型定义数据域的变量名及其类型 chy*next;/定义指针域的变量名及其类型定义指针域的变

11、量名及其类型node，*head;/nodenode是是chychy结构类型的变量结构类型的变量,*headhead是是chychy结构类型的头指针结构类型的头指针/对于指向结构变量对于指向结构变量node首地址的指针，可说明为：首地址的指针，可说明为：struct node *p,*q;/或用或用 struct *p,*q;/注：上面已经定义了注：上面已经定义了node为用户自定义的为用户自定义的chychy类型。类型。23 介绍三个有用的库函数（都在介绍三个有用的库函数（都在 中）：中）：sizeof(x)计算变量计算变量x x的长度；的长度；malloc(m)开辟开辟m m字节长度的地址

12、空间，并返回这段空间的字节长度的地址空间，并返回这段空间的首地址；首地址；free(p)释放指针释放指针p p所指变量的存储空间，即彻底删除所指变量的存储空间，即彻底删除一个变量。一个变量。设设p p为指向链表的第为指向链表的第i i个元素的指针个元素的指针,则第则第i i个元素的个元素的数据域写为数据域写为 ，指针域写为，指针域写为 。练习：练习：p-dataai的值的值p-nextai+1的地址的地址24sizeof(x)计算计算x x的长度的长度malloc(m)开开m m字节字节空间空间free(p)删除一个变量删除一个变量问问1：自定义结构类型变量自定义结构类型变量node的长度的长

13、度m是多少？是多少？问问2：结构变量结构变量node的首地址的首地址(指针指针p）是多少？）是多少？问问3：怎样删除结构变量怎样删除结构变量node？*nextdatanode，长度为长度为m字节字节pmsizeof(node)p(node*)malloc(m)free(p)/只能借助其指针删除！只能借助其指针删除！p-data=a;p-p-data=a;p-next=qnext=q252.3.2 链表的实现链表的实现1.1.单链表的建立和输出单链表的建立和输出2.2.单链表的修改单链表的修改3.3.单链表的插入单链表的插入4.4.单链表的删除单链表的删除5.5.链表插入删除实链表插入删除实例

14、例6.6.其他链表形式其他链表形式261.1.单链表的建立和输出单链表的建立和输出实例实例：用单链表结构来存放用单链表结构来存放26个英文字母组成的线个英文字母组成的线性表（性表（a，b，c，z）,请写出请写出C语言程序语言程序。实现思路：实现思路：先开辟头指针，然后陆续为每个结点开先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址也要及时辟存储空间并及时赋值，后继结点的地址也要及时送给前面的指针。送给前面的指针。先挖先挖“坑坑”,后种后种“萝萝卜卜”！27将全局变量及函数提前说明：将全局变量及函数提前说明：#include#includetypedef struct no

15、dechar data;struct node*next;node;node*p,*q,*head;/一般需要一般需要3 3个指针变量个指针变量int n;/数据元素的个数数据元素的个数int m=sizeof(node);/结构类型定义好之后，每个变量的结构类型定义好之后，每个变量的长度就固定了，长度就固定了，m m求一次即可求一次即可*/28void build()/字母链表的生成。字母链表的生成。要一个个慢慢链入要一个个慢慢链入 int i;head=(node*)malloc(m);/m=sizeof(node)前面已求出前面已求出p=head;for(i=1;idata=i+a-1;

16、/第一个结点值为字符第一个结点值为字符ap-next=(node*)malloc(m);/为后继结点为后继结点“挖坑挖坑”！p=p-next；/让指针变量让指针变量P指向后一个结点指向后一个结点p-data=i+a-1;/最后一个元素要单独处理最后一个元素要单独处理p-next=NULL;/单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！29void display()/*字母链表的输出字母链表的输出*/p=head;while(p)/当指针不空时循环，仅限于当指针不空时循环，仅限于无头结点无头结点的情况的情况 printf(%c,p-data);p=p-next;/让指针不断让指针不

17、断“顺藤摸瓜顺藤摸瓜”讨论：要统计链表中数据元素的个数，该如何改写？讨论：要统计链表中数据元素的个数，该如何改写？sum+;sum+;sum=0;sum=0;302.2.单链表的修改单链表的修改(或读取）或读取）思路：思路：要修改第要修改第i i个数据元素，必须从头指针起一直找个数据元素，必须从头指针起一直找到该结点的指针到该结点的指针p p，然后才能：，然后才能：p-data=p-data=new_valuenew_value。缺点：缺点：想寻找单链表中第想寻找单链表中第i i个元素，只能从头指针开个元素，只能从头指针开始逐一查询（始逐一查询（顺藤摸瓜顺藤摸瓜），无法随机存取），无法随机存取

18、 。核心语句：核心语句：见教材的函数说明见教材的函数说明Status GetElem_L(LinkList L,int i,ElemType&e)p=L-next;j=1;/带头结点的链表带头结点的链表while(p&jnext;+j;if(!p ji)return ERROR;e=p-data;return OK;313.3.单链表的插入单链表的插入在链表中插入一个元素在链表中插入一个元素x x的示意图如下：的示意图如下：xsabp链表插入的核心语句：链表插入的核心语句：p-nexts-nextx x结点的生成方式：结点的生成方式：S=(node*)malloc(m);S-data=x;S-

19、next=p-nextbap324.4.单链表的删除单链表的删除在链表中删除某元素在链表中删除某元素b b的示意图如下：的示意图如下：cabp删除动作的核心语句（要借助辅助指针变量删除动作的核心语句（要借助辅助指针变量q q）：）：q=p-next;/首先保存首先保存b b的指针，靠它才能找到的指针，靠它才能找到c c；p-next=q-next;/将将a a、c c两结点相连，淘汰两结点相连，淘汰b b结点；结点；free(q)；/彻底释放彻底释放b b结点空间结点空间p-next思考：思考：省略省略free(q)语句语句行不行？行不行？(p-next)-nextq33讨论讨论1 1：链表能

20、不能首尾相连？怎样实现？链表能不能首尾相连？怎样实现？答：能。只要将表中最后一个结点的指针域指向头结答：能。只要将表中最后一个结点的指针域指向头结点即可点即可 (P-next=head;P-next=head;)。这种形成环路的链表称。这种形成环路的链表称为为循环链表循环链表。特别：特别：带头结点的带头结点的空空循循环链表之样式环链表之样式参见教材参见教材P27P27 特点：特点：H34讨论讨论2 2：单链表只能查找结点的直接后继，若想查找结点的单链表只能查找结点的直接后继，若想查找结点的直接前驱，该如何设计？直接前驱，该如何设计？答：只要把单链表再多开一个指针域即可答：只要把单链表再多开一个

21、指针域即可(如用如用*nextnext和和*priorprior)。data这种链表称为这种链表称为。其特点是可以。其特点是可以双向查找双向查找表表中结点。中结点。参见教材参见教材P16P16。特别：带头结点的特别：带头结点的双向双向链表样式：链表样式：H352.3.3 链表的运算效率分析链表的运算效率分析1.查找查找 因线性链表只能顺序存取，即在查找时要从头指针因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为找起，查找的时间复杂度为 O(n)。时间效率分析2.插入和删除插入和删除 因线性链表不需要移动元素，只要修改指针，一般因线性链表不需要移动元素，只要修改指针，一般情况

22、下时间复杂度为情况下时间复杂度为 O(1)。但是，如果要在单链表中进行但是，如果要在单链表中进行前前插或删除操作，因插或删除操作，因为要为要从头查找前驱从头查找前驱结点，所耗时间复杂度将是结点，所耗时间复杂度将是 O(n)。36练：练：空间效率分析空间效率分析链表中每个结点都要增加一个指针空间，相当于总链表中每个结点都要增加一个指针空间，相当于总共增加了共增加了n 个整型变量，空间复杂度为个整型变量，空间复杂度为 O(n)。在在n n个结点的单链表中要删除已知结点个结点的单链表中要删除已知结点*P P，需找到它，需找到它的的 ，其时间复杂度为，其时间复杂度为 。O O(n)(n)372.4 应

23、用举例应用举例1.1.一元多项式的数学通式？一元多项式的数学通式？2.2.用抽象数据类型如何描述它的定义？用抽象数据类型如何描述它的定义？3.3.用用C C语言如何描述它的定义？语言如何描述它的定义？4.4.如何编程实现两个一元多项式相加？如何编程实现两个一元多项式相加？(参见教材参见教材P34 36)讨论：讨论：38但当多项式的但当多项式的次数很高次数很高且且零系数项很多零系数项很多时，更适于用链表存储。时，更适于用链表存储。1.一元多项式的数学通式？一元多项式的数学通式？一元多项式的通式可表示为：一元多项式的通式可表示为：A xaxaxa xmemeemm().120120分析：分析：一元

24、多项式在计算机内存储时，一般用一元多项式在计算机内存储时，一般用顺序表顺序表存储。存储。a0a1a2am-2am-1顺序表顺序表（只存系数项）（只存系数项）链表形式链表形式am-1 em-1am-2 em-2 a0 e0 或或0.0 -1 am-1 em-1 a0 e0通常设计两个数据域（系数项和指数项）和一个指针域。通常设计两个数据域（系数项和指数项）和一个指针域。头结点头结点392.2.用抽象数据类型如何用抽象数据类型如何定义定义一元多项式？一元多项式？PolynomialPolynomial数据对象数据对象：D=ai|aiTermSet,i=1,2,m,m0TermSetTermSet中的中的每个元素包含每个元素包含一个表示系数的一个表示系数的实数实数和表示指数的和表示指数的整数整数数据关系：数据关系：R1=|ai-1,ai D,且且a ai-1i-1中的指数值中的指数值 expon=、Pb-expon等情况，等情况，再决定是再决定是将两系数域的数值相加（并判其和是否为将两系数域的数值相加（并判其和是否为0 0），还是），还是将较高指数项的结点插入到新表将较高指数项的结点插入到新表c c中。中。3 142 81 0 aPaPa8 14-3 1010 6 bPbPb11 14-3 102 81 0 cPcPc10 6+