软件基础-2-02线性表
《软件基础-2-02线性表》由会员分享，可在线阅读，更多相关《软件基础-2-02线性表（34页珍藏版）》请在文档大全上搜索。
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元
