算法与数据结构 第二章
❹ 算法描述
1. 判断表是不是已经满，如果已经满不能插入；
2. 判断位置是否合理，不合理提示错误；
3. 表不满并且插入位置合理，从最后一个元素到第i个 位置元素依次后移；
4. 将元素 e 插入第 i 个位置；
5. 表长加1。
北京邮电大学世纪学院
算法与数据结构 第二章
在顺序表中第 i 个位置插入新元素 e
赵
头结点
钱
孙
李
周
吴
郑
尾结点
王
北京邮电大学世纪学院
算法与数据结构 第二章
例2 26 个英文字母组成的英文表
‘C’的 前驱 ‘C’的 后继
(A B
头结点C D…… Z)尾结点北京邮电大学世纪学院
算法与数据结构 第二章
例3 学生登记表
学号
012003010622 012003010704 012003010813 012003010906 012003011018
顶部伪代码描述 在顺序表中第 i 个位置插入新元素 e 第一步细化 异常情形处理，返回不成功处理标志 在顺序表中移动元素，空出下标为k的位置
问题
插入新元素e
修改顺序表长度 返回成功处理标志
北京邮电大学世纪学院
算法与数据结构 第二章
第一步细化
异常情形处理 返回不成功处理标志 在顺序表中移动元素，空出下标为k的 位置 插入新元素e 修改元素最后位置指针 返回成功处理标志
0 1 2 3 4 5 6 7 8 9
插入25
n=8
n=9
北京邮电大学世纪学院
算法与数据结构 第二章
➋ 测试用例分析
表2.2 顺序表插入操作测试用例
情形 测试数据 预期结果
问题的一般情形
临界点或特殊点 异常情况
1≤i≤n+1
i=1，i=n+1
插入成功
插入成功 插入失败
i<1或i>n+1 顺序表已满 n==MAXSIZE
MAXSIZE-1
北京邮电大学世纪学院
算法与数据结构 第二章
在顺序表的存储结构中，应包含两部分： 数据元素 当前顺序表中已存放的元素个数
#define MAXSIZE 100 /* 存储空间初始分配量 */ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; Int length; /* 线性表当前长度 */ }SqList;
北京邮电大学世纪学院
算法与数据结构 第二章
SqList L;
/* 定义线性表L */
SqList *LP; /* 定义指向线性表的指针变量LP */
定义了结构变量L后，顺序表中的结点如何表示？
L.data[0]=a1;
X=L.length; Lp=&L； p->data[0]=a1; X=p->length;
线性表的主要操作
初始化 给线性表相关参数赋初值 求长度 求线性表的元素个数 取元素 取给定位置的元素值 定位 插入 删除 遍历 查找给定元素值的位置 在指定位置插入给定的值 删除指定位置的值或给定的值 从头到尾扫描线性表，做指定的操作
算法与数据结构 第二章
2.2 线性表的顺序存储结构
北京邮电大学世纪学院
北京邮电大学世纪学院
算法与数据结构 第二章
根据顺序表的定义，在程序设计语言中，一维数组在内 存中占用的存储空间是连续的区域，因此，用一维数组data 来表示顺序表。 此外，考虑到顺序表的运算有插入、删除等，所以表的
长度是会改变的，需要将数组的容量设计的足够大，用
MAXSIZE（根据实际情况定义的整数）来表示。同时，需要 一个整数length来表示顺序表的实际长度。 顺序表中的数据从data[0]开始存放。
为 n-1上的元素，后移至位置n上，以此类推，空出第 i 个位
置； 然后在该位置上插入新元素 x ； 仅当插入位置i=n+1时，才无须移动元素，直接将x插入 顺序表的末尾。
北京邮电大学世纪学院
算法与数据结构 第二章
顺序表的插入操作过程示例：在第5个位置 i=5插入25
#define MAXSIZE 10
线性表结点之间具有先后的、线性的、一维的关系
开始 结点
终端 结点
a1
a2
a3
a4
…… an
中间结点只有一 个前趋和一个后 继结点
北京邮电大学世纪学院
算法与数据结构 第二章
顺序存储：顺序表 链式存储：链表 线性表 逻辑结构都相同 运算受限：栈和队列 内容特殊：数组和串
北京邮电大学世纪学院
算法与数据结构 第二章
北京邮电大学世纪学院
算法与数据结构 第二章
当结点内容有多 个数据项，而不 是基本类型int时， 怎么办？
typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; Int length; }SqList;
编号 书名 作者 出版社 价格
typedef struct card { int num; char name[20]; char author[10]; char publisher[30]; float price; } ElemType;
北京邮电大学世纪学院
算法与数据结构 第二章
2.1.2 顺序表的基本操作
1. 顺序表的初始化
北京邮电大学世纪学院
第二章 线性表
2.1 线性表及其逻辑结构
目 录
2.2 线性表的顺序存储结构
2.3 线性表的链式存储结构
2.4 线性表的应用
算法与数据结构 第二章
2.1 线性表及其逻辑结构
北京邮电大学世纪学院
算法与数据结构 第二章
2.1.1 实际问题中的线性关系
例1 百家姓
'周'的 前趋
'周'的 后继
第二步细化
若顺序表溢出 ，则 return 0; 若k是非法位置，则 return 0; 从顺序表的最后一个元素起 向后移动(length-k+1)个元素 将 e 放入表的k位置 length+1 return 1
北京邮电大学世纪学院
算法与数据结构 第二章
第三步细化
if ( LP->length= =MAXSIZE) return 0; if (i<0 || i>(LP->length＋1)) return 0; k=LP->length-1; 当 k>=i-1 LP->data[k+1]=LP->data[k]; k- - ; LP-> data[i-1]=e;
5. 顺序表的插入操作
顺序表插入操作的定义：在顺序表的第 i 个位置上插入一个
新元素 x，使长度为 n 的线性表变成长度为 n+1 的顺序表。
(a1，…ai-1，ai，…，an)
插入 x (a1，…ai-1，x，ai，…，an )
北京邮电大学世纪学院
算法与数据结构 第二章
➊ 算法分析
顺序表的插入操作过程是： 将顺序表中位置为 n 的元素，后移至位置 n+1上，位置
输出
无
数组长度 int
形参 函数类型
北京邮电大学世纪学院
算法与数据结构 第二章
void CreateList(SqList *LP,ElemType a[ ],int n) { int i; for(i=0;i<n;i++) { LP->data[i]=a[i]; LP->length++; } }
构造一个空的顺序表。
void InitList(SqList *LP) { LP->length=0; }
北京邮电大学世纪学院
算法与数据结构 第二章
2. 创建顺序表
表2.1 创建顺序表的函数结构
功能描述 用已有数组对顺序表中 的数组元素进行赋值 函数名 CreateList
输入 顺序表的地址 SqList * 已有数组
LP->length++; return 1
北京邮电大学世纪学院
算法与数据结构 第二章
❺ 程序实现
/*================================= 函数功能：顺序表运算——元素的插入 函数输入：顺序表地址，插入值，插入位置 函数输出：完成标志—— 0：异常 1：正常 ==================================*/ Status ListInsert(SqList *LP,int i,ElemType e) { int k; if(LP->length==MAXSIZE) //顺序表已满 return 0; if(i<1||i>LP->length+1) //插入位置i非法 return 0; for(k=LP->length-1;k>=i-1;k--) LP->data[k+1]= LP->data[k]; LP->data[i-1]=e; LP->length++; return 1; //从顺序表最后一个元素开始后移
顺序表序号i data中的元素 data数组下标k
顺序表序号i
data中的元素 data数组下标k
1 2 3 4 5 6 7 8 9 10
12
14 16 24 28 30 42 77
0 1 2 3 4 5 6 7 8 9