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

1、线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 可表示为：（a1 , a2 , , an） 简言之，线性结构反映结点间的逻辑关系是 的。特点 只有一个首结点和尾结点；特点 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、栈、队列、字符串、数组等，其中最典型、最常用的是-线性表见第2章一对一 (1:1)1（a1, a2, ai-1，ai, ai1 ，, an）2.1 线性表的逻辑结构 1. 线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是

2、元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点2例1 分析26 个英文字母组成的英文表是什么结构。 （ A, B, C, D, , Z）学号姓名性别年龄班级012002009524刘禹圻男 182002级计科0201班012002009613武 锐男 182002级计科0202班012002009710彭 隽男 172002级计科0203班012002009801郭 芳女 182002级计科0204班012002009904张珍珍女182002级计科0205班： ：例2 分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析： 数据元素都是

3、同类型（字母）， 元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性 ！32.2.1 顺序表的表示用一组地址连续的存储单元依次存储线性表的元素。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储方法：简言之：逻辑上相邻的元素，物理上也相邻可以利用数组Vn来实现。注意：在C语言中数组的下标是从0开始，即：Vn的有效范围是从 V0Vn-14线性表顺序存储特点：1. 逻辑上相邻的数据元素，其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组Vn的下标）。设首元素a1的存放

4、地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为： LOC(ai+1) = LOC(ai)+L LOC(ai) = LOC(a1) + L *（i-1）对上述公式的解释如图所示：5线性表的顺序存储结构示意图a1a2aiai+1an 地址 内容 元素在表中的位序1i2n空闲区i+1Lb=LOC(a1)b + Lb +(i-1)Lb +(n-1)Lb +(max-1)L6设有一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是，则的第一个字节的地址是113例1因此：LOC( M3

5、 ) = 98 + 5 (3-0) =113解：已知地址计算通式为：LOC(ai) = LOC(a1) + L *（i-1）72.2.2 顺序表的实现（或操作）回忆：数据结构基本运算操作有： 修改、插入、删除、查找、排序1) 修改 通过数组的下标便可访问某个特定元素并修改之。核心语句: Vi=x;显然，顺序表修改操作的时间效率是T(n)=O(1)82)插入 在线性表的第i个位置前插入一个元素实现步骤：将第n至第i 位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。注意：事先应判断: 插入位置i 是否合法?表是否已满? 应当有1in+1 或 i=1,n+1for (j=n;j=i

6、;j-)aj+1=aj; ai=x; n+;/ 元素后移一个位置/ 插入x / 表长加1 核心语句：9在线性表的第i个位置前插入一个元素的示意图如下：121321242830427712132124252830427712345678123456789插入2510实现步骤：将第i +1至第n 位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i 是否合法?应当有1in 或 i=1, n3)删除 删除线性表的第i个位置上的元素for (j=i+1;jdata=a; p-next=q; 方式3： p指向结点首地址，然后 (*p).data=a； (*p).nextqabqp213.

7、补充结构数据类型的C表示法 类型定义和变量说明可以合写为：typedef struct chy /chy是自定义结构类型名称 char data; /定义数据域的变量名及其类型struct chy *next; /定义指针域的变量名及其类型node，*head; /node是chy结构类型的变量, *head是chy结构类型的头指针/ 对于指向结构变量node首地址的指针，可说明为：struct node *p, *q; /或用 struct chy *p , *q; /注：上面已经定义了node为用户自定义的chy类型。22 介绍三个有用的库函数（都在 中）：sizeof(x)计算变量x的长

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

9、(p) /只能借助其指针删除！p-data=a; p-next=q242.3.2 链表的实现1. 单链表的建立和输出2. 单链表的修改3. 单链表的插入4. 单链表的删除5. 链表插入删除实例6. 其他链表形式251. 单链表的建立和输出实例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，z）,请写出C语言程序。实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址也要及时送给前面的指针。先挖“坑”,后种“萝卜”！26将全局变量及函数提前说明：#include#includetypedef struct nodechar data; struct node

10、 *next;node; node *p,*q,*head; /一般需要3个指针变量int n ; / 数据元素的个数int m=sizeof(node); /结构类型定义好之后，每个变量的长度就固定了，m求一次即可*/ 27void build( ) /字母链表的生成。要一个个慢慢链入 int i;head=(node*)malloc(m); /m=sizeof(node) 前面已求出p=head;for(i=1;idata=i+a-1; / 第一个结点值为字符ap-next=(node*)malloc(m); /为后继结点“挖坑”！p=p-next； /让指针变量P指向后一个结点p-dat

11、a=i+a-1; /最后一个元素要单独处理p-next=NULL ; /单链表尾结点的指针域要置空！28void display() /*字母链表的输出*/p=head;while (p) /当指针不空时循环，仅限于无头结点的情况 printf(%c,p-data); p=p-next; /让指针不断“顺藤摸瓜” 讨论：要统计链表中数据元素的个数，该如何改写？ sum+;sum=0;292. 单链表的修改(或读取）思路：要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，然后才能：p-data=new_value 。缺点：想寻找单链表中第i个元素，只能从头指针开始逐一查询（顺藤摸瓜），

12、无法随机存取 。核心语句：见教材的函数说明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;303. 单链表的插入在链表中插入一个元素x的示意图如下：xsabp链表插入的核心语句：Step 1：s-next=p-next;Step 2：p-next=s ；p-nexts-next思考：Step1和2能互换么？x结点的生成方式：S=(node*)malloc(m);S-data=x;S-n

13、ext=p-nextbap插 入 x314. 单链表的删除在链表中删除某元素b的示意图如下：cabp删除动作的核心语句（要借助辅助指针变量q）：q = p-next; /首先保存b的指针，靠它才能找到c；p-next=q-next; /将a、c两结点相连，淘汰b结点；free(q) ； /彻底释放b结点空间p-next思考： 省略free(q)语句行不行？(p-next) - nextq32讨论1： 链表能不能首尾相连？怎样实现？答：能。只要将表中最后一个结点的指针域指向头结点即可 (P-next=head;) 。这种形成环路的链表称为循环链表。特别：带头结点的空循环链表之样式参见教材P27

14、特点： 1、从任一结点出发均可找到表中其他结点。 2、操作仅循环条件与单链表不同： 单链表 - p = NULL 或 p -next =NULL 循环链表- p= head 或 p-next = headH33讨论2： 单链表只能查找结点的直接后继，若想查找结点的直接前驱，该如何设计？答：只要把单链表再多开一个指针域即可(如用*next和*prior) 。priordatanext这种链表称为双向链表。其特点是可以双向查找表中结点。参见教材P16。特别：带头结点的空双向循环链表样式：想一想：双链表和双向链表有何不同？H342.3.3 链表的运算效率分析1. 查找 因线性链表只能顺序存取，即在查

15、找时要从头指针找起，查找的时间复杂度为 O(n)。时间效率分析2. 插入和删除 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。 但是，如果要在单链表中进行前插或删除操作，因为要从头查找前驱结点，所耗时间复杂度将是 O(n)。35练：空间效率分析链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变量，空间复杂度为 O(n)。在n个结点的单链表中要删除已知结点*P，需找到它的 ，其时间复杂度为 。 前驱结点的地址O(n)362.4 应用举例一元多项式的数学通式？用抽象数据类型如何描述它的定义？用C语言如何描述它的定义？如何编程实现两个一元多项式相加？一元多项式的计算 (参见教材P34 36)讨论：37但当多项式的次数很高且零系数项很多时，更适于用链表存储。1. 一元多项式的数学通式？一元多项式的通式可表示为：分析：一元多项式在计算机内存储时，一般用顺序表存储。a0a1a2am-2am-1顺序表（只存系数项）链表形式am-1 em-1am-2 em-2 a0 e0 或0.0 -1 am-1 em-1 a0 e0通常设计两个数据域（系数项和指数项）和一个指针域。头结点382.