线性表的介绍
线性表是一种常用的数据结构。在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。
特征：
1.存在唯一的一个被称做“第一个”的数据元素；
2.存在唯一的一个被称做“最后一个”的数据元素；
3.除第一个之外，集合中的每个数据元素只有一个前驱；
4.除最后一个外，集合中每个数据元素均只有一个后继
顺序表（线性表的顺序表示）
顺序表是在计算机内存中以数组的形式保存的线性表。（一般用数组表示）
- 优点：支持随机查找 可以在O(1)内查找元素
- 缺点：插入和和删除的时候，需要移动大量的元素
- 适用于需要大量访问元素的，而少量增添/删除元素的程序
顺序表的操作（C语言实现）
结构体定义
// 顺序表的大小
#define MAXSIZE 100
typedef int elemtype;
typedef struct {
elemtype data[MAXSIZE];
int length;
}sqlist;
顺序表的判空
/*判断线性表是否为空，返回1为空，0为不空*/
int list_empty(sqlist L)
{
if (0 == L.length)
return 1;
else
return 0;
}
查找
根据索引查找可以在O(1)的时间下找到
/*按序号查找，查找第i个元素的值（从0开始），找到返回1，将结果保存在e中，查找失败返回-1*/
int get_elem(sqlist L,int i,elemtype *e)
{
if (i<0||i>L.length-1)
return -1;
*e = L.data[i];
return i;
}
根据值查找需要遍历顺序表查找
/*按内容查找，查找线性表中值为e的元素，查找成功返回对应的序号，返回0表示失败*/
int local_elem(sqlist L, elemtype e)
{
int i;
for (i = 0; i < L.length; i++) {
if (e == L.data[i])
return i;
}
return 0;
}
插入操作
顺序表在进行插入操作时，需要将插入位置之后的元素都向后移动，注意要从后往前操作，不然元素会被覆盖
顺序表-插入
/*插入操作，在线性表的第i个位置插入元素e，返回1表示成功*/
int list_insert(sqlist *L,int i,elemtype e)
{
int j;
if (i<0||i>L->length)
{
printf("插入位置错误");
return -1;
}
else if(L->length>=MAXSIZE)
{
printf("顺序表已满，不能插入元素");
return 0;
}
else
{
for (j=L->length;j>i;j--)
{
L->data[j] = L->data[j-1];
}
L->data[i] = e;
L->length = L->length + 1;
return 1;
}
}
删除操作
顺序表在进行删除操作时，需要将删除元素后面的元素往前移动，不能让删除元素的位置空着，注意要从前往后操作
顺序表-删除
/*删除线性表中第i个位置的元素*/
int list_delete(sqlist *L,int i)
{
int j;
if (L->length<=0)
{
printf("顺序表已空，不能删除！");
return -1;
}else if(i<0||i>L->length-1)
{
printf("删除位置错误！");
return -1;
}
else
{
for (j=i;j<L->length-1;j++)
{
L->data[j] = L->data[j+1];
}
L->length = L->length - 1;
return 1;
}
}
插入和删除操作在最好情况下其时间复杂度为O(1)（这个元素在最后一个位置，不用移动元素），最坏情况下其时间复杂度为O(n)
顺序表的使用
#include "sqlist.h"
int main(void)
{
sqlist La;
int i,x;
int n,m;//线性表长度
init_list(&La);
printf("请输入线性表La的长度:");
scanf ("%d",&n);
La.length = n;
printf("请输入线性表La中的元素:");
for(i=0; i<n; i++)
scanf ("%d",&La.data[i]);
printf("请输入要插入到线性表La中的数字x和插入的位置i:");
scanf("%d%d",&x,&i);
list_insert(&La,i,x);
printf("线性表La=");
for(i=0; i<La.length; i++)
printf("%d ",La.data[i]);
printf("\n请输入要删除的数字的位置:");
scanf("%d",&i);
list_delete(&La,i) ;
printf("线性表La=");
for(i=0; i<La.length; i++)
printf("%d ",La.data[i]);
printf("\n请输入要查找的数字:");
scanf("%d",&x);
printf("数字%d所在的位置为%d\n",x,local_elem(La,x));
clean_list(&La);
return 0;
}
