数据线性结构、顺序表及链表..ppt

数据线性结构、顺序表及链表 数据的线性结构 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继 1 线性表的逻辑结构 定义：一个线性表是n个数据元素的有限序列 例 英文字母表（A,B,C,…..Z)是一个线性表 例 数据元素 特征： 元素个数n—表长度，n=0空表 1in时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继 元素同构，且不能出现缺项 2 线性表的顺序存储结构 顺序表： 定义：用一组地址连续的存储单元存放一个线性表叫~ 元素地址计算方法： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中： L—一个元素占用的存储单元个数 LOC(ai)—线性表第i个元素的地址 特点： 实现逻辑上相邻—物理地址相邻 实现随机存取 实现：可用一维数组实现 a1 a2 an 0 1 n-1 1 2 n 内存 V数组下标 元素序号 M-1 typedef int DATATYPE; #define M 1000 DATATYPE data[M]; 例 typedef struct card { int num; char name[20]; char author[10]; char publisher[30]; float price; }DATATYPE; DATATYPE library[M]; 备用空间 数据元素不是简单类型时,可定义结构体数组 或动态申请和释放内存 DATATYPE *pData = (DATATYPE *)malloc(M*sizeof(DATATYPE)); free(pData); 插入 定义：线性表的插入是指在第I（1?i ? n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表 变成长度为n+1的线性表 需将第i至第n共（n-i+1)个元素后移 算法 内存 a1 a2 ai ai+1 an 0 1 i-1 V数组下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 内存 a1 a2 ai ai+1 an 0 1 i-1 V数组下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 an-1 x 算法时间复杂度T(n) 设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为： 删除 定义：线性表的删除是指将第i（1?i ? n）个元素删除，使长度为n的线性表 变成长度为n-1的线性表 需将第i+1至第n共（n-i)个元素前移 算法 内存 a1 a2 ai ai+1 an 0 1 i-1 V数组下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 内存 a1 a2 ai+1 V数组下标 0 1 i-1 n-2 i n-1 1 2 i 元素序号 i+1 n-1 n an ai+2 算法评价 设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为： 故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低 顺序存储结构的优缺点 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充 3 线性表的链式存储结构 特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置 数据域 指针域 结点 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG ^ H 例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG) 43 13 1 NULL 37 7 19 25 数据域 指针域 LI QIAN SUN WANG WU ZHAO ZHENG ZHOU 存储地址 1 7 13 19 25 31 37 43 31 H 头指针 实现 typedef struct node { datatype data; struct node *link; }JD; JD *h,*p; data link p 结点（*p） (*p)表示p所指向的结点 (*p).data?p-data表示p指向结点的数据域 (