程序内功篇二--线性顺序表
一、线性表顺序存储
1、顺序存储结构的表示
若将
线性表L=(a0,a1, ……,an-1)中的各元素依次存储于计算机一片连续的存储空间。
例如：
设Loc(ai)为ai的地址，Loc(a0)=b，
每个元素占d个单元 则：Loc(ai)=b+i*d
2、顺序存储结构的特点
逻辑上相邻的元素ai, ai+1，其存储位置也是相邻的- 对数据元素ai的存取为
随机存取或按地址存取 - 存储密度高
存储密度D=(数据结构中元素所占存储空间)/（整个数据结构所占空间）
3、顺序存储结构的表示
在C语言中，可借助于一维数组类型来描述线性表的顺序存储结构
如下：
#define N 100 //宏定义储存数，方便调整
typedef int data_t; //重定义数据类型，方便数据转换
typedef struct
{ data_t data[N]； //表的存储空间
int last; //最后一位数据的位置
} sqlist, *sqlink;
二、线性表的C程序实现
1、线性表的基本运算
（1）建立一个空表：list_create(L)
/**
* @description: 顺序表创建
* @param {无}
* @return {sqlink-成功返回顺序表的地址，NULL-失败返回}
*/
sqlink sqlist_creat()
{
sqlink sq = (sqlist *)malloc(sizeof(sqlist));
if(sq == NULL)
{
#if DEBUG
printf("sqlist creat erorr!\n");
#endif
return NULL;
}
memset(sq,0,sizeof(sqlist));
sq->list = -1;
return sq;
}
（2）删除一个顺序表：list_delete(L)
/**
* @description: 顺序表删除
* @param {sqlink-传递顺序表的地址}
* @return {1-函数成功，0-函数失败}
*/
int sqlist_delete(sqlink sq)
{
if(sq == NULL)
{
#if DEBUG
printf("sqlist has been delete or sqlist isn't exist!\n");
#endif
return 0;
}
free(sq);
sq = NULL;
return 1;
}
（3）置空表：list_clear(L)
/**
* @description: 顺序表清空
* @param {sqlink-传递顺序表的地址}
* @return {1-函数成功，0-函数失败}
*/
int sqlist_clear(sqlink sq)
{
if(sq == NULL)
{
#if DEBUG
printf("sqlist isn't exist!\n");
#endif
return 0;
}
if(sq->list == -1)
{
#if DEBUG
printf("The sqlist has been clear!\n");
#endif
return 0;
}
else
{
memset(sq,0,sizeof(sqlist));
sq->list = -1;
return 1;
}
}
（4）判断表是否为空：list_empty (L)
/**
* @description: 查看顺序表是否为空
* @param {sqlink-传递顺序表的地址}
* @return {1-表为空，-1，表不空，0-函数失败}
*/
int sqlist_empty(sqlink sq)
{
if(sq == NULL)
{
#if DEBUG
printf("sqlist isn't exist!\n");
#endif
return 0;
}
if(sq->list == -1)
return 1;
else
return -1;
}
（5）求表长：length (L)
/**
* @description:求顺序表长度
* @param {sqlink-传递顺序表的地址}
* @return {储存数据的长度，0-函数失败}
*/
int sqlist_length(sqlink sq)
{
if(sq == NULL)
{
#if DEBUG
printf("sqlist isn't exist!\n");
#endif
return 0;
}
return sq->list+1;
}
（6）定位运算：Locate(L,x)，确定元素x在表L中的位置（或序号）
/**
* @description: 顺序表元素查找
* @param {sqlink-传递顺序表的地址}
* @param {unsigned int-查找元素的位置}
* @return {i位置的元素，0-函数失败}
*/
int sqlist_element_query(sqlink sq,unsigned int i)
{
if(sq == NULL)
{
#if DEBUG
printf("sqlist isn't exist!\n");
#endif
return 0;
}
if(i > sq->list)
{
#if DEBUG
printf("i too big\n");
#endif
return 0;
}
return sq->data[i];
}
（7）遍历列表：ergodic(L,x)，确定元素x在表L中的位置（或序号）
/**
* @description: 顺序表遍历所有元素
* @param {sqlink-传递顺序表的地址}
* @return {1-函数成功，0-函数失败}
*/
int sqlist_ergodic(sqlink sq)
{
int i;
if(sq == NULL)
{
#if DEBUG
printf("sqlist isn't exist!\n");
#endif
return 0;
}
if(sq->list == -1)
{
#if DEBUG
printf("sqlist is empty!\n");
#endif
return 0;
}
for(i = 0; i < sq->list+1; i++)
printf("%d ", sq->data[i]);
puts("");
return 1;
}
2、基本运算的相关算法
（1）插入：Insert(L,x,i)
将元素x插入到表L中第i个元素ai之前,且表长+1。
插入前: (a0,a1,---,ai-1,ai,ai+1-------,an-1) 0≤i≤n,i=n时,x插入表尾
插入后: (a0,a1,---,ai-1, x, ai,ai+1-------,an-1)
算法思路：
若表存在空闲空间，且参数i满足：0≤i≤L->last+1,则可进行正常插入。
插入前，将表中（L->data[L->last]～L->data[i]）部分顺序下移一个位置
然后将x插入L->data[i]处即可。算法对应的表结构。
C程序实现：
/**
* @description: 顺序表插入数据
* @param {sqlink-传递顺序表的地址}
* @param {unsigned int-插入数据的位置}
* @param {data_t-插入的数据}
* @return {1-函数成功，0-函数失败}
*/
int sqlist_insert(sqlink sq, unsigned int i, data_t x)
{
int n;
if(sq == NULL)
{
#if DEBUG
printf("sqlist isn't exist!\n");
#endif
return 0;
}
if(sq->list == N-1)
{
#if DEBUG
printf("sqlist already full!\n");
#endif
return 0;
}
if(i > sq->list+1)
{
#if DEBUG
printf("i is too big!\n");
#endif
return 0;
}
for(n = sq->list; i < n+1; n--)
sq->data[n+1] = sq->data[n];
sq->data[i] = x;
sq->list++;
return 1;
}
（2）删除：DeleteSqlist(L, i)
将表中第i个元素ai从表中删除。
算法思路：
若参数i满足：0≤i≤L->last,
将表中L->data[i+1]∽L->data[L->last] 部分顺序向上移动一个位置，
覆盖L->data[i]。
C程序实现：
/**
* @description: 删除中元素
* @param {sqlink-传递顺序表的地址}
* @param {unsigned int-删除数据的位置}
* @return {1-函数成功，0-函数失败}
*/
int sqlist_element_delete(sqlink sq, unsigned int i)
{
if(sq == NULL)
{
#if DEBUG
printf("sqlist isn't exist!\n");
#endif
return 0;
}
if(i > sq->list)
{
#if DEBUG
printf("i is too big!\n");
#endif
return 0;
}
for(; i < sq->list; i++)
sq->data[i] = sq->data[i+1];
sq->data[sq->list] = 0;
sq->list--;
return 1;
}
（3）设线性表La=(a0a1, ……,am-1), Lb= (b0b1, ……,bn-1)，求La与Lb的并集并用La表示
算法思路：
依次取表Lb中的bi(i=0,1,……,n-1)，
若bi不属于La,则将其插入表La中。
C程序实现：
/**
* @description: 两个顺序表求并集
* @param {sqlink-传递顺序表1的地址}
* @param {sqlink-传递顺序表2的地址}
* @return {1-函数成功，0-函数失败}
*/
int sqlist_union(sqlink sq1, sqlink sq2)
{
int i,j;
if(sq1 == NULL || sq2 == NULL)
{
#if DEBUG
printf("sqlist isn't exist!\n");
#endif
return 0;
}
if(sq2->list == -1)
{
#if DEBUG
printf("sqlist2 is empty!\n");
#endif
return 0;
}
for(i = 0; i < sq2->list+1; i++)
{
if(sq1->list == -1)
{
sq1->data[0] = sq2->data[i];
sq1->list++;
}
for(j = 0; j < sq1->list+1; j++)
{
if(sq1->data[j] == sq2->data[i])
break;
}
if(j > sq1->list)
sqlist_insert(sq1,sq1->list+1, sq2->data[i]);
}
return 1;
}
（4）设计清除线性表L=(a0,a1,—,ai,-------,an-1)中重复元素的算法
算法思路：
对当前表L中的每个ai（0≤i≤n-2），依次与aj(i+1≤j≤n-1) 比较，
若与ai相等，则删除之。
C程序实现：
/**
* @description: 顺序表删除重复元素
* @param {sqlink-传递顺序表的地址}
* @return {1-函数成功，0-函数失败}
*/
int sqlist_repeat_delete(sqlink sq)
{
int i,j;
if(sq == NULL)
{
#if DEBUG
printf("sqlist isn't exist!\n");
#endif
return 0;
}
if(sq->list == -1)
{
#if DEBUG
printf("sqlist is empty!\n");
#endif
return 0;
}
for(i = 1; i < sqlist_length(sq)+1; i++)
for(j = 0; j < i; j++)
{
if(sq->data[i] == sq->data[j])
sqlist_element_delete(sq, j);
}
return 1;
}
最后这里给出整体文件的免费下载链接：
顺序表C程序
到这里就结束啦！
