2.2 线性表
2.2.1 线性表的概念
2.2.2线性表的基本运算
2.2.3 顺序存储结构线性表的基本运算
2.2.4 链式存储结构线性表的基本运算
2.2.5 小结
2.2.1 线性表的概念
线性表的定义,
定义,线性表是 n个元素的有限序列,它们之间的关系可以排成一个线性序列：
a1,a2,……,ai,……,an
其中 n称作线性表的表长,当 n=0时,称作空表 。
线性表的逻辑关系：
元素之间的关系是 一对一 的线性关系。
a1 a2 a3 a4 a5 a6
线性表的特点：
2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。第一个数据元素无前驱，
最后一个数据元素无后继。
1.线性表中所有元素的数据类型相同。
2.2.1 线性表的概念
2.2.2 线性表的基本运算
（ 1） 线性表初始化：
构造一个空的线性表 。
（ 2） 求线性表的长度：
返回线性表中所含元素的个数 。
（ 3） 按值查找：
在线性表 L中查找关键字值为 x的数据元素 。
（ 4） 插入操作：
在线性表 L的第 i个位置插入一个值为 x的新元素 。
（ 5） 删除操作：
删除线性表 L中第 i个位置的数据元素 。
2.2.2 线性表的基本运算
2.2.3 顺序存储线性表的基本运算顺序存储是指在内存中用 一片连续的地址空间将数据元素 按其逻辑关系 依次存放起来。
由于线性表的逻辑关系是一对一的线性关系，
用顺序存储结构存储线性表，只要按线性表中数据元素的逻辑先后次序将其存放在一维数组中即可实现。
顺序存储结构的线性表简称,顺序表,。
ai-1…,.a2a1 an…ai+1ai
x
2.2.3.1 插入运算
ai-1…,.a2a1 ai ai+1 … an an… …ai+1x
插入运算是指在顺序表中的第 i个位置上插入一个新元素 x，
使得表长 n增 1。
当 1≤ i≤n+1 时，要 在顺序表的第 I个位置上插入一个新元素,可分 三 步进行：
①元素 后 移：将第 n至第 i个元素依次 后 移（ 注意：顺序不能反 ）
②将元素存放在第 i个位置上；
③ 修改表长：表长加 1
2.2.3.1 插入运算不能插入的情况：
表满
位置不对插入运算是指在顺序表中的第 i个位置上插入一个新元素 x，
使得表长 n增 1。
注意,c语言数组下标默认从 0开始！！！
#define MAXLEN 100
void InsertList(ElemType list[],int *plength,int i,ElemType x)
{ int j,n;
n=*plength;
if (i<1||i>n+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中,要求新表的元素仍然按从小到大的升序排列 。
顺序表插入算法应用举例可选解法一：
分两步完成：
1,找新元素的插入位置 i（ 思考插入位置应在什么地方？）可通过查找算法实现。
2,将新元素插入到第 i个位置上，可通过刚介绍的插入算法完成。
如,x=3
3
2
1
0
10
7
5
2
可选解法二：
思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
思考：为什么？
如,x=3
3
2
1
0
10
7
5
2思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
j为当前查找元素的位置，
从表的末端开始查找
j=3
可选解法二：
如,x=3
3
2
1
0
10
7
5
2思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
j=3当前元素比待插元素大，
将其后移一个位置，并继续往前查找可选解法二：
如,x=3
3
2
1
0
j=3
10
7
5
2思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
当前元素比待插元素大，
将其后移一个位置，并继续往前查找可选解法二：
如,x=3
3
2
1
0
10
7
5
2思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
当前元素比待插元素大，
将其后移一个位置，并继续往前查找
j=2
可选解法二：
如,x=3
3
2
1
0
j=2
10
7
5
2
当前元素比待插元素大，
将其后移一个位置，并继续往前查找思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
可选解法二：
如,x=3
3
2
1
0
10
7
5
2
当前元素比待插元素大，
将其后移一个位置，并继续往前查找思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
j=1
可选解法二：
如,x=3
3
2
1
0
j=1
10
7
5
2
当前元素比待插元素大，
将其后移一个位置，并继续往前查找思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
可选解法二：
如,x=3
3
2
1
0 j=0
10
7
5
2
碰到第一个小于或等于待插元素的元素，停止查找。
思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
思考：此时当前位置是一个什么位置？
可选解法二：
3
如,x=3
3
2
1
0 j=0
10
7
5
2
最终将新元素插在第一个小于等于它的元素之后。
任务完成！
可选解法二：
如,x=3
3
2
1
0
10
7
5
2
完整程序的实现,（主函数）
#include<stdio.h>
void main()
{
int a[10]={2,5,7,10};
int i,x,n=4;
scanf("%d",&x);
insert(a,&n,x);
for(i=0;i<n;i++)
printf(" %5d ",a[i]);
}
如,x=3
3
2
1
0
10
7
5
2void insert (int s[],int *pn,int x)
{
}
完整程序的实现,（插入子函数）
如,x=3
3
2
1
0
10
7
5
2void insert (int s[],int *pn,int x)
{
int j;
j=*pn-1;
}
j=3
完整程序的实现,（插入子函数）
如,x=3
3
2
1
0
10
7
5
2
j=3
void insert (int s[],int *pn,int x)
{
int j;
j=*pn-1;
while(s[j]>x&&j>=0)
{ s[j+1]=s[j];
}
}
完整程序的实现,（插入子函数）
如,x=3
3
2
1
0
j=2
10
7
5
2void insert (int s[],int *pn,int x)
{
int j;
j=*pn-1;
while(s[j]>x&&j>=0)
{ s[j+1]=s[j];
j--;
}
}
完整程序的实现,（插入子函数）
如,x=3
3
2
1
0
j=1
10
7
5
2void insert (int s[],int *pn,int x)
{
int j;
j=*pn-1;
while(s[j]>x&&j>=0)
{ s[j+1]=s[j];
j--;
}
}
完整程序的实现,（插入子函数）
如,x=3
3
2
1
0 j=0
10
7
5
2void insert (int s[],int *pn,int x)
{
int j;
j=*pn-1;
while(s[j]>x&&j>=0)
{ s[j+1]=s[j];
j--;
}
}
完整程序的实现,（插入子函数）
3如,x=3
3
2
1
0
10
7
5
2void insert (int s[],int *pn,int x)
{
int j;
j=*pn-1;
while(s[j]>x&&j>=0)
{ s[j+1]=s[j];
j--;
}
s[j+1]=x;
(*pn)++;
}
完整程序的实现,（插入子函数）
为了使算法具有更好的可读性，可用结构体类型定义描述线性表的顺序存储结构。
#define MAXLEN 100
typedef struct
{ElemType list[MAXLEN]; //存放线性表元素
int length; //存放线性表表长
}SeqList;
#define MAXLEN 100
void InsertList(SeqList*L,int i,ElemType x)
{
int j,n;
n=L->length;
if (i<1||i>n+1)
{
printf(“\n i值不合法,);
exit(1);
}
if(n>=MAXLEN)
{
printf(“\n表空间溢出,)；
exit(1);
}
for(j=n-1;j>=i-1;j－－ )
L->list[j+1]=L->list[j]; //元素向后移动一个位置
L->list[i-1]=x; //插入 x
L->length++; //表长加 1
}
插入运算算法 （ 二 ）
思考,若线性表存放的是某超市的商品信息，每种商品信息包括编号、名称、单价和库存量四项信息。如何定义上面插入算法中的 ElemType 类型，实现将一个新商品信息
（保存在 x变量中）插入到表中的第 i个位置上？
typedef struct goodstype
{
long int num;
char name[20];
int price;
int stock;
}ElemType;
2.2.3.2 删除运算删除运算是指删除顺序表中第 i个位置上的元素，使得表长 n减 1。
当 1≤ i≤n 时，要删除 第 i个位置的 元素，可分两步进行,（注意：顺序不能反）
①元素 前 移：将第 i+1至第 n个元素依次 前 移
②修改表长：表长减 1
a1 a2 a3 …,,ai-1 ai ai+1 ai+2 …,,an-1 an …,,
2.2.3.2 删除运算删除运算是指删除顺序表中第 i个位置上的元素，使得表长 n减 1。
a1 a2 a3 …,,ai-1 ai ai+1 ai+2 …,,an-1 an …,,i+1
当 1≤ i≤n 时，要删除 第 i个位置的 元素，可分两步进行,（注意：顺序不能反）
①元素 前 移：将第 i+1至第 n个元素依次 前 移
②修改表长：表长减 1
2.2.3.2 删除运算删除运算是指删除顺序表中第 i个位置上的元素，使得表长 n减 1。
a1 a2 a3 …,,ai-1 ai ai+1 ai+2 …,,an-1 an …,,i+1 ai+2
当 1≤ i≤n 时，要删除 第 i个位置的 元素，可分两步进行,（注意：顺序不能反）
①元素 前 移：将第 i+1至第 n个元素依次 前 移
②修改表长：表长减 1
2.2.3.2 删除运算删除运算是指删除顺序表中第 i个位置上的元素，使得表长 n减 1。
a1 a2 a3 …,,ai-1 ai ai+1 an-1 an …,,i+1 ai+2 …,.
当 1≤ i≤n 时，要删除 第 i个位置的 元素，可分两步进行,（注意：顺序不能反）
①元素 前 移：将第 i+1至第 n个元素依次 前 移
②修改表长：表长减 1
2.2.3.2 删除运算删除运算是指删除顺序表中第 i个位置上的元素，使得表长 n减 1。
a1 a2 a3 …,,ai-1 ai ai+1 an-1 an …,,i+1 ai+2 …,.
不能删除的情况,? 表空
位置不对
当 1≤ i≤n 时，要删除 第 i个位置的 元素，可分两步进行,（注意：顺序不能反）
①元素 前 移：将第 i+1至第 n个元素依次 前 移
②修改表长：表长减 1
void DeleteList(SeqList* L,int i,ElemType *x)
{
int j,n;
n=L->length;
if(i<1||i>n)
{printf("\n i值不合法 !");
exit(1);
}
*x=L->list[i-1]; /*保存 被删元素的值 */
for(j=i;j<=n-1;j++)
L->list[j-1]=L->list[j]; /*元素依次 前移 */
L->length--; /*表长减 1*/
}
删除运算算法 （ 一 ）
算法要点：
（ 1） 1<=i<=n删除位置有效。
（ 2）表空时不能删除。
（ 3）注意元素的移动方向
ElemType DeleteList(SeqList* L,int i)
{int j,n;
ElemType x;
n=L->length;
if(i<1||i>n)
{printf("\n i值不合法 !");
exit(1);
}
x=L->list[i-1]; /*保存 被删元素的值 */
for(j=i;j<=n-1;j++)
L->list[j-1]=L->list[j]; /*前移 */
L->length--; /*表长减 1*/
return(x);
}
删除运算算法 (二 ）
查找运算是指在顺序表查找关键字值等于给定值的元素，若查找成功则返回该元素所在的位置（下标），
若查找失败则返回一个无意义的下标值。
2.2.3.3 查找运算从前向后 (或从后向前 )逐个元素进行关键字值比较，
若等与给定值则停止查找，返回该元素所在的下标；
若不等则继续查找过程。若查遍整个线性表仍未查找到，则说明查找失败，返回无意义的下标值表示该元素不存在。
2.2.3.3 查找运算
35 41 60 19 55 27 89 11 96
i查找 x=55的元素从后往前查找,i初值为 n
采用顺序查找方法实现可按如下步骤完成：
从前向后 (或从后向前 )逐个元素进行关键字值比较，
若等与给定值则停止查找，返回该元素所在的下标；
若不等则继续查找过程。若查遍整个线性表仍未查找到，则说明查找失败，返回无意义的下标值表示该元素不存在。
2.2.3.3 查找运算
采用顺序查找方法实现可按如下步骤完成：
35 41 60 19 55 27 89 11 96
i查找 x=55的元素从前向后 (或从后向前 )逐个元素进行关键字值比较，
若等与给定值则停止查找，返回该元素所在的下标；
若不等则继续查找过程。若查遍整个线性表仍未查找到，则说明查找失败，返回无意义的下标值表示该元素不存在。
2.2.3.3 查找运算
采用顺序查找方法实现可按如下步骤完成：
35 41 60 19 55 27 89 11 96
i查找 x=55的元素从前向后 (或从后向前 )逐个元素进行关键字值比较，
若等与给定值则停止查找，返回该元素所在的下标；
若不等则继续查找过程。若查遍整个线性表仍未查找到，则说明查找失败，返回无意义的下标值表示该元素不存在。
2.2.3.3 查找运算
采用顺序查找方法实现可按如下步骤完成：
35 41 60 19 55 27 89 11 96
i查找 x=55的元素从前向后 (或从后向前 )逐个元素进行关键字值比较，
若等与给定值则停止查找，返回该元素所在的下标；
若不等则继续查找过程。若查遍整个线性表仍未查找到，则说明查找失败，返回无意义的下标值表示该元素不存在。
2.2.3.3 查找运算
采用顺序查找方法实现可按如下步骤完成：
35 41 60 19 55 27 89 11 96
i查找 x=55的元素 查找成功从前向后 (或从后向前 )逐个元素进行关键字值比较，
若等与给定值则停止查找，返回该元素所在的下标；
若不等则继续查找过程。若查遍整个线性表仍未查找到，则说明查找失败，返回无意义的下标值表示该元素不存在。
2.2.3.3 查找运算
采用顺序查找方法实现可按如下步骤完成：
35 41 60 19 55 27 89 11 96
i查找 x=55的元素 查找成功，返回结果为该元素在数组中的位置
typedef ElemType int; //线性表元素类型
typedef KeyType int; //查找关键字类型
int SearchList(SeqList* L,KeyType x)
{int i;
i=L->length-1;
while(L->list[i]!=x&&i>=0)
i--;
return(i);
//查找成功返回元素所在的位置；若查找失败,返回 -1
}
查找运算算法 （ 假设线性表的类型为整型 ）
实现在长度为 n的线性表上顺序查找关键字为 x的元素
思考：
若线性表存放的是某超市的商品信息，每种商品信息包括编号、名称、单价和库存量四项。如何定义上面查找算法中的 ElemType和 KeyType类型，实现按照 编号 查找对应商品信息的功能？
typedef struct goodstype
{ long int num;
char name[20];
int price;
int stock;}ElemType;
typedef long int KeyType;
有两个整型顺序表 A和 B,其元素均按从小到大的升序排列,编写一个算法将它们合并成一个顺序表,要求新表的元素也按从小到大的升序排列 。
顺序表插入算法应用思考题提示：可通过将 B中元素逐个插入 A中的方法实现。
顺序线性表应用实例编写程序实现超市商品信息管理中的插入、删除、查找及显示等功能。
要求,1.各功能均用独立的模块实现；
2.具有菜单选择功能；
3.用户可在运行该程序过程中多次选择执行不同的功能。
顺序表的特点：
1,存储结构与逻辑关系一致；
2,随机存取顺序表的元素很方便；
3,顺序表的插入、删除操作要通过移动元素实现顺序表小结
2.2.1 线性表的概念
2.2.2线性表的基本运算
2.2.3 顺序存储结构线性表的基本运算
2.2.4 链式存储结构线性表的基本运算
2.2.5 小结
2.2.1 线性表的概念
线性表的定义,
定义,线性表是 n个元素的有限序列,它们之间的关系可以排成一个线性序列：
a1,a2,……,ai,……,an
其中 n称作线性表的表长,当 n=0时,称作空表 。
线性表的逻辑关系：
元素之间的关系是 一对一 的线性关系。
a1 a2 a3 a4 a5 a6
线性表的特点：
2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。第一个数据元素无前驱，
最后一个数据元素无后继。
1.线性表中所有元素的数据类型相同。
2.2.1 线性表的概念
2.2.2 线性表的基本运算
（ 1） 线性表初始化：
构造一个空的线性表 。
（ 2） 求线性表的长度：
返回线性表中所含元素的个数 。
（ 3） 按值查找：
在线性表 L中查找关键字值为 x的数据元素 。
（ 4） 插入操作：
在线性表 L的第 i个位置插入一个值为 x的新元素 。
（ 5） 删除操作：
删除线性表 L中第 i个位置的数据元素 。
2.2.2 线性表的基本运算
2.2.3 顺序存储线性表的基本运算顺序存储是指在内存中用 一片连续的地址空间将数据元素 按其逻辑关系 依次存放起来。
由于线性表的逻辑关系是一对一的线性关系，
用顺序存储结构存储线性表，只要按线性表中数据元素的逻辑先后次序将其存放在一维数组中即可实现。
顺序存储结构的线性表简称,顺序表,。
ai-1…,.a2a1 an…ai+1ai
x
2.2.3.1 插入运算
ai-1…,.a2a1 ai ai+1 … an an… …ai+1x
插入运算是指在顺序表中的第 i个位置上插入一个新元素 x，
使得表长 n增 1。
当 1≤ i≤n+1 时，要 在顺序表的第 I个位置上插入一个新元素,可分 三 步进行：
①元素 后 移：将第 n至第 i个元素依次 后 移（ 注意：顺序不能反 ）
②将元素存放在第 i个位置上；
③ 修改表长：表长加 1
2.2.3.1 插入运算不能插入的情况：
表满
位置不对插入运算是指在顺序表中的第 i个位置上插入一个新元素 x，
使得表长 n增 1。
注意,c语言数组下标默认从 0开始！！！
#define MAXLEN 100
void InsertList(ElemType list[],int *plength,int i,ElemType x)
{ int j,n;
n=*plength;
if (i<1||i>n+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中,要求新表的元素仍然按从小到大的升序排列 。
顺序表插入算法应用举例可选解法一：
分两步完成：
1,找新元素的插入位置 i（ 思考插入位置应在什么地方？）可通过查找算法实现。
2,将新元素插入到第 i个位置上，可通过刚介绍的插入算法完成。
如,x=3
3
2
1
0
10
7
5
2
可选解法二：
思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
思考：为什么？
如,x=3
3
2
1
0
10
7
5
2思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
j为当前查找元素的位置，
从表的末端开始查找
j=3
可选解法二：
如,x=3
3
2
1
0
10
7
5
2思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
j=3当前元素比待插元素大，
将其后移一个位置，并继续往前查找可选解法二：
如,x=3
3
2
1
0
j=3
10
7
5
2思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
当前元素比待插元素大，
将其后移一个位置，并继续往前查找可选解法二：
如,x=3
3
2
1
0
10
7
5
2思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
当前元素比待插元素大，
将其后移一个位置，并继续往前查找
j=2
可选解法二：
如,x=3
3
2
1
0
j=2
10
7
5
2
当前元素比待插元素大，
将其后移一个位置，并继续往前查找思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
可选解法二：
如,x=3
3
2
1
0
10
7
5
2
当前元素比待插元素大，
将其后移一个位置，并继续往前查找思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
j=1
可选解法二：
如,x=3
3
2
1
0
j=1
10
7
5
2
当前元素比待插元素大，
将其后移一个位置，并继续往前查找思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
可选解法二：
如,x=3
3
2
1
0 j=0
10
7
5
2
碰到第一个小于或等于待插元素的元素，停止查找。
思路：从后往前查找插入位置，在查找过程中若当前元素比待插元素大，则将其后移一个位置。
思考：此时当前位置是一个什么位置？
可选解法二：
3
如,x=3
3
2
1
0 j=0
10
7
5
2
最终将新元素插在第一个小于等于它的元素之后。
任务完成！
可选解法二：
如,x=3
3
2
1
0
10
7
5
2
完整程序的实现,（主函数）
#include<stdio.h>
void main()
{
int a[10]={2,5,7,10};
int i,x,n=4;
scanf("%d",&x);
insert(a,&n,x);
for(i=0;i<n;i++)
printf(" %5d ",a[i]);
}
如,x=3
3
2
1
0
10
7
5
2void insert (int s[],int *pn,int x)
{
}
完整程序的实现,（插入子函数）
如,x=3
3
2
1
0
10
7
5
2void insert (int s[],int *pn,int x)
{
int j;
j=*pn-1;
}
j=3
完整程序的实现,（插入子函数）
如,x=3
3
2
1
0
10
7
5
2
j=3
void insert (int s[],int *pn,int x)
{
int j;
j=*pn-1;
while(s[j]>x&&j>=0)
{ s[j+1]=s[j];
}
}
完整程序的实现,（插入子函数）
如,x=3
3
2
1
0
j=2
10
7
5
2void insert (int s[],int *pn,int x)
{
int j;
j=*pn-1;
while(s[j]>x&&j>=0)
{ s[j+1]=s[j];
j--;
}
}
完整程序的实现,（插入子函数）
如,x=3
3
2
1
0
j=1
10
7
5
2void insert (int s[],int *pn,int x)
{
int j;
j=*pn-1;
while(s[j]>x&&j>=0)
{ s[j+1]=s[j];
j--;
}
}
完整程序的实现,（插入子函数）
如,x=3
3
2
1
0 j=0
10
7
5
2void insert (int s[],int *pn,int x)
{
int j;
j=*pn-1;
while(s[j]>x&&j>=0)
{ s[j+1]=s[j];
j--;
}
}
完整程序的实现,（插入子函数）
3如,x=3
3
2
1
0
10
7
5
2void insert (int s[],int *pn,int x)
{
int j;
j=*pn-1;
while(s[j]>x&&j>=0)
{ s[j+1]=s[j];
j--;
}
s[j+1]=x;
(*pn)++;
}
完整程序的实现,（插入子函数）
为了使算法具有更好的可读性，可用结构体类型定义描述线性表的顺序存储结构。
#define MAXLEN 100
typedef struct
{ElemType list[MAXLEN]; //存放线性表元素
int length; //存放线性表表长
}SeqList;
#define MAXLEN 100
void InsertList(SeqList*L,int i,ElemType x)
{
int j,n;
n=L->length;
if (i<1||i>n+1)
{
printf(“\n i值不合法,);
exit(1);
}
if(n>=MAXLEN)
{
printf(“\n表空间溢出,)；
exit(1);
}
for(j=n-1;j>=i-1;j－－ )
L->list[j+1]=L->list[j]; //元素向后移动一个位置
L->list[i-1]=x; //插入 x
L->length++; //表长加 1
}
插入运算算法 （ 二 ）
思考,若线性表存放的是某超市的商品信息，每种商品信息包括编号、名称、单价和库存量四项信息。如何定义上面插入算法中的 ElemType 类型，实现将一个新商品信息
（保存在 x变量中）插入到表中的第 i个位置上？
typedef struct goodstype
{
long int num;
char name[20];
int price;
int stock;
}ElemType;
2.2.3.2 删除运算删除运算是指删除顺序表中第 i个位置上的元素，使得表长 n减 1。
当 1≤ i≤n 时，要删除 第 i个位置的 元素，可分两步进行,（注意：顺序不能反）
①元素 前 移：将第 i+1至第 n个元素依次 前 移
②修改表长：表长减 1
a1 a2 a3 …,,ai-1 ai ai+1 ai+2 …,,an-1 an …,,
2.2.3.2 删除运算删除运算是指删除顺序表中第 i个位置上的元素，使得表长 n减 1。
a1 a2 a3 …,,ai-1 ai ai+1 ai+2 …,,an-1 an …,,i+1
当 1≤ i≤n 时，要删除 第 i个位置的 元素，可分两步进行,（注意：顺序不能反）
①元素 前 移：将第 i+1至第 n个元素依次 前 移
②修改表长：表长减 1
2.2.3.2 删除运算删除运算是指删除顺序表中第 i个位置上的元素，使得表长 n减 1。
a1 a2 a3 …,,ai-1 ai ai+1 ai+2 …,,an-1 an …,,i+1 ai+2
当 1≤ i≤n 时，要删除 第 i个位置的 元素，可分两步进行,（注意：顺序不能反）
①元素 前 移：将第 i+1至第 n个元素依次 前 移
②修改表长：表长减 1
2.2.3.2 删除运算删除运算是指删除顺序表中第 i个位置上的元素，使得表长 n减 1。
a1 a2 a3 …,,ai-1 ai ai+1 an-1 an …,,i+1 ai+2 …,.
当 1≤ i≤n 时，要删除 第 i个位置的 元素，可分两步进行,（注意：顺序不能反）
①元素 前 移：将第 i+1至第 n个元素依次 前 移
②修改表长：表长减 1
2.2.3.2 删除运算删除运算是指删除顺序表中第 i个位置上的元素，使得表长 n减 1。
a1 a2 a3 …,,ai-1 ai ai+1 an-1 an …,,i+1 ai+2 …,.
不能删除的情况,? 表空
位置不对
当 1≤ i≤n 时，要删除 第 i个位置的 元素，可分两步进行,（注意：顺序不能反）
①元素 前 移：将第 i+1至第 n个元素依次 前 移
②修改表长：表长减 1
void DeleteList(SeqList* L,int i,ElemType *x)
{
int j,n;
n=L->length;
if(i<1||i>n)
{printf("\n i值不合法 !");
exit(1);
}
*x=L->list[i-1]; /*保存 被删元素的值 */
for(j=i;j<=n-1;j++)
L->list[j-1]=L->list[j]; /*元素依次 前移 */
L->length--; /*表长减 1*/
}
删除运算算法 （ 一 ）
算法要点：
（ 1） 1<=i<=n删除位置有效。
（ 2）表空时不能删除。
（ 3）注意元素的移动方向
ElemType DeleteList(SeqList* L,int i)
{int j,n;
ElemType x;
n=L->length;
if(i<1||i>n)
{printf("\n i值不合法 !");
exit(1);
}
x=L->list[i-1]; /*保存 被删元素的值 */
for(j=i;j<=n-1;j++)
L->list[j-1]=L->list[j]; /*前移 */
L->length--; /*表长减 1*/
return(x);
}
删除运算算法 (二 ）
查找运算是指在顺序表查找关键字值等于给定值的元素，若查找成功则返回该元素所在的位置（下标），
若查找失败则返回一个无意义的下标值。
2.2.3.3 查找运算从前向后 (或从后向前 )逐个元素进行关键字值比较，
若等与给定值则停止查找，返回该元素所在的下标；
若不等则继续查找过程。若查遍整个线性表仍未查找到，则说明查找失败，返回无意义的下标值表示该元素不存在。
2.2.3.3 查找运算
35 41 60 19 55 27 89 11 96
i查找 x=55的元素从后往前查找,i初值为 n
采用顺序查找方法实现可按如下步骤完成：
从前向后 (或从后向前 )逐个元素进行关键字值比较，
若等与给定值则停止查找，返回该元素所在的下标；
若不等则继续查找过程。若查遍整个线性表仍未查找到，则说明查找失败，返回无意义的下标值表示该元素不存在。
2.2.3.3 查找运算
采用顺序查找方法实现可按如下步骤完成：
35 41 60 19 55 27 89 11 96
i查找 x=55的元素从前向后 (或从后向前 )逐个元素进行关键字值比较，
若等与给定值则停止查找，返回该元素所在的下标；
若不等则继续查找过程。若查遍整个线性表仍未查找到，则说明查找失败，返回无意义的下标值表示该元素不存在。
2.2.3.3 查找运算
采用顺序查找方法实现可按如下步骤完成：
35 41 60 19 55 27 89 11 96
i查找 x=55的元素从前向后 (或从后向前 )逐个元素进行关键字值比较，
若等与给定值则停止查找，返回该元素所在的下标；
若不等则继续查找过程。若查遍整个线性表仍未查找到，则说明查找失败，返回无意义的下标值表示该元素不存在。
2.2.3.3 查找运算
采用顺序查找方法实现可按如下步骤完成：
35 41 60 19 55 27 89 11 96
i查找 x=55的元素从前向后 (或从后向前 )逐个元素进行关键字值比较，
若等与给定值则停止查找，返回该元素所在的下标；
若不等则继续查找过程。若查遍整个线性表仍未查找到，则说明查找失败，返回无意义的下标值表示该元素不存在。
2.2.3.3 查找运算
采用顺序查找方法实现可按如下步骤完成：
35 41 60 19 55 27 89 11 96
i查找 x=55的元素 查找成功从前向后 (或从后向前 )逐个元素进行关键字值比较，
若等与给定值则停止查找，返回该元素所在的下标；
若不等则继续查找过程。若查遍整个线性表仍未查找到，则说明查找失败，返回无意义的下标值表示该元素不存在。
2.2.3.3 查找运算
采用顺序查找方法实现可按如下步骤完成：
35 41 60 19 55 27 89 11 96
i查找 x=55的元素 查找成功，返回结果为该元素在数组中的位置
typedef ElemType int; //线性表元素类型
typedef KeyType int; //查找关键字类型
int SearchList(SeqList* L,KeyType x)
{int i;
i=L->length-1;
while(L->list[i]!=x&&i>=0)
i--;
return(i);
//查找成功返回元素所在的位置；若查找失败,返回 -1
}
查找运算算法 （ 假设线性表的类型为整型 ）
实现在长度为 n的线性表上顺序查找关键字为 x的元素
思考：
若线性表存放的是某超市的商品信息，每种商品信息包括编号、名称、单价和库存量四项。如何定义上面查找算法中的 ElemType和 KeyType类型，实现按照 编号 查找对应商品信息的功能？
typedef struct goodstype
{ long int num;
char name[20];
int price;
int stock;}ElemType;
typedef long int KeyType;
有两个整型顺序表 A和 B,其元素均按从小到大的升序排列,编写一个算法将它们合并成一个顺序表,要求新表的元素也按从小到大的升序排列 。
顺序表插入算法应用思考题提示：可通过将 B中元素逐个插入 A中的方法实现。
顺序线性表应用实例编写程序实现超市商品信息管理中的插入、删除、查找及显示等功能。
要求,1.各功能均用独立的模块实现；
2.具有菜单选择功能；
3.用户可在运行该程序过程中多次选择执行不同的功能。
顺序表的特点：
1,存储结构与逻辑关系一致；
2,随机存取顺序表的元素很方便；
3,顺序表的插入、删除操作要通过移动元素实现顺序表小结
