22线性表 ●221线性表的概念 ●222线性表的基本运算 223顺序存储结构线性表的基本运算 ●224链式存储结构线性表的基本运算 ●225小结
2.2 线性表 ⚫ 2.2.1 线性表的概念 ⚫ 2.2.2线性表的基本运算 ⚫ 2.2.3 顺序存储结构线性表的基本运算 ⚫ 2.2.4 链式存储结构线性表的基本运算 ⚫ 2.2.5 小结
221线性表的概念 线性表的定义 定义:线性表是n个元素的有限序列,它们之间的关系 可以排成一个线性序列: i a 其中n称作线性表的表长,当n=0时,称作空表。 线性表的逻辑关系: 元素之间的关系是一对一的线性关系
2.2.1 线性表的概念 • 线性表的定义 ： 定义： 线性表是n个元素的有限序列，它们之间的关系 可以排成一个线性序列： a1，a2，…… ，ai，…… ，an 其中n称作线性表的表长，当n=0时，称作空表。 • 线性表的逻辑关系： 元素之间的关系是一对一的线性关系。 a1 a2 a3 a4 a5 a6
221线性表的概念 °线性表的特点: 1线性表中所有元素的数据类型相同。 2除第一个和最后一个数据元素之外,其它数据元素有 且仅有一个前驱和一个后继。第一个数据元素无前驱 最后一个数据元素无后继
• 线性表的特点： 2.除第一个和最后一个数据元素之外，其它数据元素有 且仅有一个前驱和一个后继。第一个数据元素无前驱， 最后一个数据元素无后继。 1.线性表中所有元素的数据类型相同。 2.2.1 线性表的概念
222线性表的基本运算 (1)线性表初始化: 构造一个空的线性表。 (2)求线性表的长度: 返回线性表中所含元素的个数 (3)按值查找: 在线性表L中查找关键字值为x的数据元素
2.2.2 线性表的基本运算 （1） 线性表初始化： 构造一个空的线性表。 （2）求线性表的长度： 返回线性表中所含元素的个数。 （3）按值查找： 在线性表L中查找关键字值为x的数据元素
222线性表的基本运算 (4)插入操作: 在线性表L的第个位置插入一个值为x的新元素。 (5)删除操作: 删除线性表L中第i个位置的数据元素
（4）插入操作： 在线性表L的第i个位置插入一个值为x的新元素。 （5）删除操作： 删除线性表L中第i个位置的数据元素。 2.2.2 线性表的基本运算
223顺序存储线性表的基本运算 顺序存储是指在内存中用一片连续的地址空间 将数据元素按其逻辑关系依次存放起来。 由于线性表的逻辑关系是一对一的线性关系, 用顺序存储结构存储线性表,只要按线性表中数据 元素的逻辑先后次序将其存放在一维数组中即可实 现 顺序存储结构的线性表简称“顺序表
2.2.3 顺序存储线性表的基本运算 顺序存储是指在内存中用一片连续的地址空间 将数据元素按其逻辑关系依次存放起来。 由于线性表的逻辑关系是一对一的线性关系， 用顺序存储结构存储线性表，只要按线性表中数据 元素的逻辑先后次序将其存放在一维数组中即可实 现。 顺序存储结构的线性表简称“顺序表”
22.3.1插入运算 插入运算是指在顺序表中的第i个位置上插入一个新元素x, 使得表长n增1。 X a 2 a -1 a a i+1 a n a a 2 a i-1 a ai
a1 a2 ….. ai-1 ai ai+1 … an x 2.2.3.1 插入运算 a1 a2 ….. ai-1 axi ai+1 a…i+1 a…n an 插入运算是指在顺序表中的第i个位置上插入一个新元素x， 使得表长n增1
22.3.1插入运算 插入运算是指在顺序表中的第i个位置上插入一个新元素x, 使得表长n增1。 ●当1≤i≤n+1时,要在顺序表的第I个位置上插入 个新元素,可分三步进行: ①元素后移:将第n至第个元素依次后移(注意:顺 序不能反) ②将元素存放在第个位置上; ③修改表长:表长加1 不能插入 表满 的情况: 。位置不对 注意:c语言数组下标默认从0开始!!!
⚫ 当1≤ i≤n+1时，要在顺序表的第I个位置上插入一 个新元素，可分三步进行： ①元素后移：将第n至第i个元素依次后移（注意：顺 序不能反） ②将元素存放在第i个位置上； ③修改表长：表长加1 2.2.3.1 插入运算 不能插入 的情况： ⚫ 表满 ⚫ 位置不对 插入运算是指在顺序表中的第i个位置上插入一个新元素x， 使得表长n增1。 注意：c语言数组下标默认从0开始！！！
插入运算算法(一)传线性传线性 #define maxlen 100 表元素 表表长 typedef int ElemType; void Insertlist(ElemType listI, int *length, int i, Elem Type x) i intj, n length if (in+1) 注意:为了增加算法的通用性, printf("ni值不合法”);在此用 Elemtype代表任意一种数 exit(1); 据类型,在算法实现时需根据需 要选择具体的某一种数据类型。 if(n>=MAXLEN 如:线性表元素为整型,则在算 printf("n表空间溢出”)法中增加一条 typedef语句即可 exit(1) for(j=n-1;j>=i-l分-) list[j-+|= list[jl;∥元素向后移动一个位置 listi-1=x; /插入x 算法要点: (length)++; ∥表长加 (1)大于 MAXLEN溢出 (2)1<=i<=n+1位置有效 (3)注意元素移动的方向
#defineMAXLEN 100 void InsertList(ElemType list[], int *plength,inti,ElemType x) { int j,n; n=*plength; if (in+1) {printf(“\n i值不合法”); exit(1); } if(n>=MAXLEN) {printf(“\n表空间溢出”); exit(1); } for(j=n-1;j>=i-1;j--) list[j+1]=list[j]; //元素向后移动一个位置 list[i-1]=x; //插入x (*plength)++; //表长加1 } • 插入运算算法（一） ❖注意：为了增加算法的通用性， 在此用ElemType代表任意一种数 据类型，在算法实现时需根据需 要选择具体的某一种数据类型。 如：线性表元素为整型，则在算 法中增加一条typedef语句即可。 typedef int ElemType; 传递线性 表元素 传递线性 表表长 算法要点： (1)大于MAXLEN溢出。 (2)1<=i<=n+1位置有效。 (3)注意元素移动的方向
顺序表插入算法应用举例 有一个整型顺序表a,其元素均按从小 到大的升序排列编写一个算法将新元素x 插入此顺序表a中,要求新表的元素仍然按 从小到大的升序排列
有一个整型顺序表a,其元素均按从小 到大的升序排列,编写一个算法将新元素x 插入此顺序表a中,要求新表的元素仍然按 从小到大的升序排列。 顺序表插入算法应用举例