1. 线性表的定义
- 线性表L是n（n≥0）个具有相同属性的数据元素a1，a2，a3，…，an组成的有限序列，其中序列中元素的个数n称为线性表的长度。
- 当n=0时称为空表，即不含有任何元素。
- 常常将非空的线性表L(n>0)记作：L=(a1，a2，…an)
- 其中ai-1为ai的直接前驱，ai＋1为ai的直接后继。a1为表头元素，an为表尾元素。
- 线性表（Linear list）是最简单且最常用的一种数据结构，其逻辑结构为线性结构。
- 线性表具有下列特点：
存在唯一的一个没有前驱的（头）数据元素；
存在唯一的一个没有后继的（尾）数据元素；
每个数据元素(除表头元素)均有一个直接前驱；
每个数据元素(除表尾元素)均有一个直接后继；
表中数据元素的类型是相同的
2. 线性表的基本运算
数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现则是建立在存储结构上的。
（1）初始化线性表L：InitList(L)
（2）求线性表L的长度：GetLength(L)
（3）按序号取元素：GetNode（L，i）
（4）按值查找：LocateList（L，e）
（5）插入新元素：InsertList（L，i，e）
（6）在线性表中删除元素：DeleteList（L，i）
（7）把已有线性表置为空表：ClearList（L）
3. 线性表的实现
- 顺序表在具体实现时，一般用高级语言中的数组来对应连续的存储空间。设最多可存储MaxLen个元素，在C语言中可用数组data[MaxLen]来存储数据元素，为保存线性表的长度需定义一个整型变量length。
- 线性表的第l，2，…，n个元素分别存放在此数组下标为0，1，…，length-1数组元素中，如下图所示
c语言示例：
#include<stdio.h>
# define MaxLen 100
typedef struct
{
int no;
int score;
}DataType;
typedef struct
{
DataType data[MaxLen]; // 定义存储表元素的数组
int length;
}SeqList;
// 顺序表的初始化
void InitList(SeqList *p){ p->length=0; }
// 顺序表的创建
void CreatList(SeqList *p){
int i = 0;
DataType x;
printf("请输入学号和成绩，以学号-1为结束：\n");
scanf("%d",&x.no);
while(x.no!=-1)
{
scanf("%d",&x.score);
p->data[i]=x;
scanf("%d",&x.no);
i++;
}
p->length=i;
}
// 顺序表中插入元素
void InsertList(SeqList *p, int i, DataType x){
for(int j=p->length-1; j>i-1; j--){
p->data[j+1] = p->data[j];
}
p->data[i-1] = x;
p->length++;
}
// 按序号顺序表中元素
DataType GetNode(SeqList *L, int i){
if(i<1 || i>L->length) printf("position error\n");
return L->data[i-1];
}
// 在顺序表中查找元素
int LocateList(SeqList *p, int no)
{
int i = 0;
while(i<p->length && p->data[i].no != no)
i++;
if(i<p->length) return i+1; //第i+1个元素，i从0开始
else return -1;
}
// 修改第i个元素
void EditList(SeqList *p,int i,DataType e)
{
if(i<1 || i>p->length)
{
printf("position error\n");
}
p->data[i-1]=e;
}
// 删除第i个元素
void DeleteList(SeqList *L,int i)
{
if(i<1 || i>L->length)
{
printf("position error\n");
}
for(int j=i;j<=L->length-1;j++)
//向前移动元素
L->data[j-1]=L->data[j];
L->length--;
}
void PrintList(SeqList *p)
{
int i;
for(i=0;i<p->length;i++)
printf("[%d,%d]\n",p->data[i].no,p->data[i].score);
printf("\n");
}
void main(){
SeqList L;
DataType e;
InitList(&L);
//创建
CreatList(&L);
PrintList(&L);
//插入
e.no=9; e.score=80;
InsertList(&L,L.length+1,e);
printf("插入后：\n");
PrintList(&L);
//查询
int i=LocateList(&L,3);
if (i>0)
printf("学号为3的成绩: %d \n",GetNode(&L,i).score);
else
printf("Can't find the elem.\n");
//修改
e.no=3; e.score=65;
int m=LocateList(&L,3);
EditList(&L,m,e);
printf("修改后：\n");
PrintList(&L);
//删除
int k=LocateList(&L,2);
DeleteList(&L,k);
printf("删除学号为2的记录后：\n");
PrintList(&L);
}
4. 线性表的顺序存储结构的特点
优点：顺序表中的任意数据元素的存储地址可由公式直接导出，因此顺序表可以“随机存取”其中的任意元素。
不足：
- 需预先分配相应的存储空间。预分配空间过小，存储空间不便于扩充；预分配空间过大，容易造成空间浪费。
- 插入与删除运算的效率很低，插入、删除操作时需移动大量数据。
