《数据结构(c语言版)》第二章 线性表(jian)1.ppt

第二章 线性表 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继 2.1 线性表的定义和操作 定义：一个线性表是n个数据元素的有限序列 线性表是一种线性结构，用二元组表示为： linear_list=(A,R), 其中 A={ai|1≤i≤n, n≥0, ai∈ElemType} R={ai,ai+1|1≤i≤n-1} 对线性可以进行各种数据处理操作如： (1) 初始化线性表L，即置L为一个空表 void InitList(L) (2) 清除线性表L中的所有元素，使之成为一个空表 void ClearList(L) (3) 返回线性表L的长度，若L为空则返回0 int SizeList(L) (4) 判断线性表L是否为空，若为空则返回1，否则返回0 int EmptyList(L) (5) 返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行 ElemType GetElem(L,pos) 2.2 线性表的顺序存储结构和操作实现 2.2.1线性表的顺序存储 定义：用一组地址连续的存储单元存放一个线性表叫~ 元素地址计算方法： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中： L—一个元素占用的存储单元个数 LOC(ai)—线性表第i个元素的地址 特点： 实现逻辑上相邻—物理地址相邻 实现随机存取 实现：可用C语言的一维数组实现 如何定义顺序存储空间? 2.2.2 顺序存储结构线性表的操作实现 初始化线性表L，即进行动态存储空间分配并置L为一个空表，算法： void InitList(struct List *L, int ms) { /*检查ms是否有效，若无效则退出运行*/ if(ms=0) {printf(ms值非法!\n); exit(1);} /*置线性表空间大小为ms*/ L-MaxSize=ms; /*动态存储空间分配，若分配失败则退出运行*/ L-list=malloc(ms*sizeof(ElemType)); if(!L-list) { printf(动态存储分配失败!\n); exit(1); /*执行此函数则中止程序运行，此函数在 stdlib.h中有定义*/ } /*初始置线性表为空*/ L-size=0; } 清空 free( L-list); L-list=0; L-size= L-MaxSize＝０; 求线性表长度 　　　return L-size； 遍历线性表 for(i=0;i L-size;i++) printf(“%d”, L-list[i]); 在线性表中查找值为x的元素 　　 for(i=0;i L-size;i++) if(L-list[i]==x) return i 插入：线性表的插入是指在第I（1?i ? n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表 教材中的插入算法 11. 向线性表L中第pos个元素位置插入元素x，若插入成功返回1，否则返回0 该操作过程分为以下六步： (1) 检查pos值是否越界，即pos1或posn+1是否成立（n为线性表长度），若是则无法插入，表明插入失败，应返回0； (2) 检查线性表的存储空间是否已被占满，若是则重新分配更大的动态存储空间； (3) 从表尾元素向前至下标为pos-1位置的元素止，使每一个元素均后移一个存储位置，把下标为pos-1的位置空出，以便插入新元素； (4) 将新元素写入到第pos个元素位置，即下标为pos-1的位置； (5) 修改线性表的长度，使其增1； (6) 返回1表示插入成功。 算法描述如下： int InsertPosList(struct List *L, int pos, ElemType x) { int i;