数据结构第2章线性表.ppt

2.1 线性表的逻辑结构 例1 分析26 个英文字母组成的英文表是什么结构。 （ A, B, C, D, …… , Z） 2.2.1 顺序表的表示 用一组地址连续的存储单元依次存储线性表的元素。 线性表顺序存储特点： 1. 逻辑上相邻的数据元素，其物理上也相邻； 2. 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。 线性表的顺序存储结构示意图 例1 设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是 2.2.2 顺序表的实现（或操作） 实现步骤： 将第i +1至第n 位的元素向前移动一个位置； 表长减1。 注意：事先需要判断，删除位置i 是否合法? 应当有1≤i≤n 或 i=[1, n] 2.2.3 顺序表的运算效率分析 算法时间主要耗费在移动元素的操作上，因此 计算时间复杂度的基本操作（最深层语句频度） T(n)= O (移动元素次数) 移动元素的个数取决于插入或删除元素的位置. 讨论2：若在长度为n的线性表上删除第i位上的元素，则向前移动元素的次数f(n)为： f(n) = 教材P11对执行效率的推导： 假定在表中任意位置插入、删除元素都是等概率的，即插入概率p(i)=1/(n+1) ，删除概率q(i)=1/n ，则： 2.3 线性表的链式存储结构 2.3.1 链表的表示 链式存储特点 与链式存储有关的术语 补充：结构数据类型的C表示法 例：请画出26 个英文字母表的链式存储结构。 3. 补充结构数据类型的C表示法 ① 类型定义和变量说明可以合写为： typedef struct chy //chy是自定义结构类型名称 { char data; //定义数据域的变量名及其类型 struct chy *next; //定义指针域的变量名及其类型 }node，*head; //node是chy结构类型的变量, *head是chy结构类型的头指针// 3. 补充结构数据类型的C表示法 ① 类型定义和变量说明可以合写为： typedef struct chy //chy是自定义结构类型名称 { char data; //定义数据域的变量名及其类型 struct chy *next; //定义指针域的变量名及其类型 }node，*head; //node是chy结构类型的变量, *head是chy结构类型的头指针// ③ 介绍三个有用的库函数（都在stdlib.h 中）： sizeof(x)——计算变量x的长度； malloc(m) —开辟m字节长度的地址空间，并返回这段空间的首地址； free(p) ——释放指针p所指变量的存储空间，即彻底删除一个变量。 sizeof(x)——计算x的长度 malloc(m) —开m字节空间 free(p) ——删除一个变量 2.3.2 链表的实现 1. 单链表的建立和输出 2. 单链表的修改 3. 单链表的插入 4. 单链表的删除 5. 链表插入删除实例 6. 其他链表形式 1. 单链表的建立和输出 实例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z）,请写出C语言程序。 将全局变量及函数提前说明： #includestdio.h #includestdlib.h typedef struct node{ char data; struct node *next;}node; node *p,*q,*head; //一般需要3个指针变量 int n ; // 数据元素的个数 int m=sizeof(node); //结构类型定义好之后，每个变量的长度就固定了，m求一次即可*/ void build( ) //字母链表的生成。要一个个慢慢链入 { int i; head=(node*)malloc(m); //m=sizeof(node) 前面已求出 p=head; for(i=1;i26;i++) //因尾结点要特殊处理，故i≠26 { p-data=i+‘a’-1; // 第一个结点值为字符a p-next=(node*)malloc(m); //为后继结点“挖坑”！ p=p-next；} //让指针变量P指向后一个结点 p-data=i+‘