软件基础-2-02线性表

1、2022-6-2线性表1第二节 线性表2022-6-2线性表2 什么是线性什么是线性DS、线性表、线性表 了解线性了解线性DS的特点的特点 了解线性了解线性DS的逻辑结构、的逻辑结构、物理结构以及操作物理结构以及操作教学目标：教学目标：2022-6-2线性表3学习要求学习要求通过本单元的学习，了解并掌握：通过本单元的学习，了解并掌握： 线性线性DS的常用存储结构的常用存储结构 顺序、链表顺序、链表 单向、双向、循环链表等单向、双向、循环链表等 线性线性DS的有关算法的有关算法 增、删、改增、删、改2022-6-2线性表4 2.1 线性表的逻辑结构 定义：一个线性表是n个数据元素的有限序列nia

2、aaa,21如例 英文字母表（A,B,C,.Z)是一个线性表例学号姓名年龄001张三18002李四19数据元素 特征： 元素个数n表长度，n=0空表 1i 0 a, i = 0 a+i*la2022-6-2线性表9a1a2an01n-112n内存V数组下标元素序号M-1typedef int DATATYPE; #define M 1000DATATYPE dataM;例 typedef struct card int num; char name20; char author10; char publisher30; float price;DATATYPE;DATATYPE library

3、M; 备用空间数据元素不是简单类型时,可定义结构体数组或动态申请和释放内存DATATYPE *pData = (DATATYPE *)malloc(M*sizeof(DATATYPE);free(pData); 2022-6-2线性表10 用typedef定义类型 功能：用自定义名字为已有数据类型命名 类型定义简单形式： typedef type name;例 typedef int INTEGER;类型定义语句关键字已有数据类型名用户定义的类型名例 typedef float REAL;类型定义后,与已有类型一样使用例 INTEGER a,b,c; REAL f1,f2; int a,b,c

4、; float f1,f2; 说明:1.typedef 没有创造新数据类型2.typedef 是定义类型,不能定义变量3.typedef 与 define 不同 define typedef预编译时处理 编译时处理简单字符置换 为已有类型命名 2022-6-2线性表11 typedef定义类型步骤按定义变量方法先写出定义体 如 int i; 将变量名换成新类型名 如 int INTEGER; 最前面加typedef 如 typedef int INTEGER; 用新类型名定义变量 如 INTEGER i,j; 例 定义数组类型 int a100; int ARRAY100; typedef i

5、nt ARRAY100; ARRAY a,b,c; int a100,b100,c100;例 定义指针类型 char *str; char *STRING; typedef char *STRING; STRING p,s10; char *p; char *s10;例 定义函数指针类型 int (*p)(); int (*POWER)(); typedef int (*POWER)(); POWER p1,p2; int (*p1)(),(*p2)(); 例 定义结构体类型 struct date int month; int day; int year; d;例 定义结构体类型 struc

6、t date int month; int day; int year; DATE;例 定义结构体类型typedef struct date int month; int day; int year; DATE;例 定义结构体类型 DATE birthday, *p; struct date int month; int day; int year; birthday, *p; 类型定义可嵌套例 typedef struct club char name20; int size; int year; GROUP; typedef GROUP *PG; PG pclub; GROUP *pclu

7、b; struct club *pclub;2022-6-2线性表12 插入 定义：线性表的插入是指在第I（1i n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表niiaaaaa,1,21 变成长度为n+1的线性表niiaaxaaa,1,21 需将第i至第n共（n-i+1)个元素后移 算法Ch2_1.c2022-6-2线性表13内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x2022-6-2线性表14 算法时间复杂度T(n) 设Pi是在第i个元素之前

8、插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：11)1(niiinPEis nOnTninnEisnPnii112)1(1111则若认为2022-6-2线性表15 删除 定义：线性表的删除是指将第i（1i n）个元素删除，使长度为n的线性表niiaaaaa,1,21 变成长度为n-1的线性表niiaaaaa,11,21 需将第i+1至第n共（n-i)个元素前移 算法Ch2_2.c2022-6-2线性表16内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元

9、素序号i+1n-1nanai+22022-6-2线性表17 算法评价 设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：niideinQE1)( nOnTninnEnQnidei121)(11则若认为故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低2022-6-2线性表18顺序存储结构的优缺点 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充2022-6-2线性表19 2.3 线性表的链式存储结构特点： 用一组任意的

10、存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置数据域 指针域结点2022-6-2线性表20ZHAOQIANSUNLIZHOUWUZHENGWANGH例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针2022-6-2线性表21 实现typedef struct

11、 node datatype data; struct node *link;JD;JD *h,*p;datalinkp结点（*p）(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).linkp-link表示p指向结点的指针域生成一个JD型新结点：p=(JD *)malloc(sizeof(JD);系统回收p结点：free(p) 线性链表 定义：结点中只含一个指针域的链表叫，也叫单链表2022-6-2线性表22ha1a2an .h空表头结点：在单链表第一个结点前附设一个结点叫头结点指针域为空表示线性表为空头结点2022-6-2线性表23 单链表的基本运算 查

12、找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULL 算法描述While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为n nOnTpabxs 算法评价 插入：在线性表两个数据元素a和b间插入x，已知p指向as-link=p-link;p-link=s; 1OnT 算法描述 算法评价2022-6-2线性表24 算法描述pabc 1OnT 算法评价 删除：单链表中删除b，设p指向ap-link=p-link-link;2022-6-2线性表25 nOnT 动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针 算法描述 算法评价h头结点

13、an 0h头结点an-10an a2.h头结点an-10an ha1a2头结点an .0Ch2_3.ch头结点02022-6-2线性表26单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢2022-6-2线性表27 循环链表(circular linked list) 循环链表是表中最后一个结点的指针指向头结点，使链表构成环状 特点：从表中任一结点出发均可找到表中其他结点，提高查找效率 操作与单链表基本一致,循环条件不同 单链表p或p-link=NULL 循环链表p或p-link=Hhh空表2022-6-2线性表28 双向链表（d

14、ouble linked list）单链表具有单向性的缺点 结点定义typedef struct node datatype element; struct node *prior,*next;JD;priorelementnextL空双向循环链表：非空双向循环链表： LABbcapp-prior-next= p= p-next-proir;2022-6-2线性表29void del_dulist(JD *p)p-prior-next=p-next; p-next-prior=p-prior; free(p); 删除 算法描述 算法评价：T(n)=O(1)p-prior-next=p-next

15、;p-next-prior=p-prior;bcaP2022-6-2线性表30void ins_dulist(JD* p,int x)JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; 算法描述 算法评价：T(n)=O(1)xSbaP 插入2022-6-2线性表31 2.4 线性表的应用举例 一元多项式的表示及相加 一元多项式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用线性表P表示200001000231)(xxxS但对

16、S(x)这样的多项式浪费空间一般emmnxPxPxPxPee2121)(其中为非零系数）（iPemee210用数据域含两个数据项的线性表表示emPePePm，2121其存储结构可以用顺序存储结构，也可以用单链表2022-6-2线性表32 单链表的结点定义coefexpnext17787172522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元多项式相加typedef struct node int coef,exp; struct node

17、 *next;JD;2022-6-2线性表33设p,q分别指向A,B中某一结点，p,q初值是第一结点比较p-exp与q-expp-exp exp: p结点是和多项式中的一项 p后移,q不动p-exp q-exp: q结点是和多项式中的一项 将q插在p之前,q后移,p不动p-exp = q-exp: 系数相加0：从A表中删去p, 释放p,q，p,q后移0：修改p系数域, 释放q，p,q后移直到p或q为NULL 若q=NULL，结束 若p=NULL，将B中剩余部分连到A上即可 运算规则2022-6-2线性表34q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-