线性表需要学习的内容
线性表的定义
. 首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
2. 然后，线性表强调是有限的，元素个数当然也是有限的。事实上，在计算机中处理的对象都是有限的，那种无限的数列，只存在于数学的概念中。
如果用数学语言来进行定义：
若将线性表记为(a1, ……, ai-1, ai, ai+1, ……,an),则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当丨=1, 2, ……, n-1时，ai有且仅有一个直接后继，当i=2, 3, ……, n时，ai有且仅有一个直接前驱。
所以线性表元素的个数n (n>0)定义为线性表的长度，当n=0时，称为空表。
在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。
这就是线性表的定义
线性表的抽象定义类型ADT
ADT 线性表 (List)
Data
Operation
void initList(*L); //创建并初始化一个空线性表，如果成功返回true，修改表传指针
bool listEmpty(L); //判断一个线性表是否为空，不修改表传值
void clearList(*L); //清空一个线性表，成功返回true
bool getElem(L,i,*e); //从某个位置取出元素并赋值给e(i的范围是[1,L.length])，修改e的值所以传递一个指针，成功返回true
int locateElem(L,e); //查找线性表中是否有e，如果有返回它的位置(从1开始)，否则返回0表示失败
bool listInsert(*L,i,e); //插入一个元素e在第i个元素之前(i的取值范围是[1,L.length+1]) ，成功返回true
bool listDelete(*L,i,*e); //删除在第i个位置上的元素(i的取值范围是[1,L.length]),删除的元素赋给e，成功返回true
int listLength(L); //返回线性表的元素个数
endADT
实现两个线性表集合A和B的并集操作
void unionL(List *la,List lb){
int index;
int laLength = listLength(*la); //得到a的长度，需要一个线性表而不是一个地址
int lbLength = listLength(lb);}
ElemType e; //声明一个元素
for(index=1;index<=lbLength;index++){ //遍历lb
getElem(lb,index,&e); //依次得到lb中的元素
if(!locateElem(*la,e)){ //检查是否在la中出现
listInsert(la,++laLength,e); //没有出现则插入队尾，前自增！
}
}
}
对于union操作，用到了前面线性表基本操作ListLength、GetElem、LocateElem、Listlnsert等，可见，对于复杂的个性化的操作，其实就是把基本操作组合起来实现的。
线性表的顺序存储结构
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
线性表的顺序存储结构，说白了，就是在内存中找了块地方，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中
线性表的顺序存储的结构体定义为：
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef struct
{
ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
int length; /* 线性表当前长度 */
}SqList;
描述顺序存储结构需要三个属性：
存储空间的起始位置：数组data,它的存储位置就是存储空间的存储位置。
线性表的最大存储容量：数组长度MaxSize。
线性表的当前长度：length。
线性表的初始化
初始化就是建立一个空线性表，那直接把长度置为0就行了
/* 初始化顺序线性表 */
Status InitList(SqList *L)
{
L->length=0;
return OK;
}
这里 InitList(SqList *L) 用了地址传递
因为要初始化，要对线性表本身进行操作，所以不能用值传递。值传递不会改变实参的值嘛。地址传递的话呢，实际上在函数内部执行了这么一个操作：L = &L. 所以操作函数内部的L，也就相当于操作外部的线性表L。其实地址传递也是值传递。不过这个值是地址而已。
就是说，需要修改表的就传指针，不需要修改表的传值就行了。
#include "stdio.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef struct
{
ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
int length; /* 线性表当前长度 */
}SqList;
/* 初始化顺序线性表 */
Status InitList(SqList *L)
{
L->length=0;
return OK;
}
int main()
{
SqList L;
ElemType e;
Status i;
i=InitList(&L);
printf("初始化L后：L.length=%d\n",L.length);
}
程序运行结果：
初始化L后：L.length=0
函数内部 L->length=0; 使用箭头，而在外面调用的时候 L.length 用实心点在函数内部，传递的参数是 *L，那么L就是指针。指针需要用->指向成员。而在外部的L是实体对象，实体对象则用实心点来指向成员。
线性表插入数据元素
当时ADT是这么设计插入操作的：bool listInsert(*L,i,e); //插入一个元素e在第i个元素之前(i的取值范围是[1,L.length+1])，成功返回true.
插入算法的思路：
如果插入位置不合理，抛出异常；
如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
将要插入元素填入位置i处；
表长加1。
插入操作会改变原有链表，所以要用地址传递。函数设计如下：
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if (L->length==MAXSIZE) /* 顺序线性表已经满 */
return ERROR;
if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
return ERROR;
if (i<=L->length) /* 若插入数据位置不在表尾 */
{
for(k=L->length-1; k>=i-1; k--) /* 将要插入位置之后的数据元素向后移动一位 */
L->data[k+1] = L->data[k];
}
L->data[i-1]=e; /* 将新元素插入 */
L->length++;
return OK;
}
给线性表随机赋10个值
//顺序表的建立
SqList Create(SqList L)
{
int i;
srand((unsigned)time(NULL));
for(i=0; i < 10; i++)
{
L.data[i] = rand()%100;
L.length++;
}
return L;
}
// 调用
L = Create(L);
每插入一个元素，注意表长要加1. 下面是遍历操作的函数：
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{
int i;
for(i=0;i < L.length;i++)
visit(L.data[i]);
printf("\n");
return OK;
}
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
线性表置为空的操作
ADT里判断线性表是否为空的函数设计如下：bool listEmpty(L); //判断一个线性表是否为空，不修改表传值
/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(SqList L)
{
if(L.length==0)
return TRUE;
else
return FALSE;
}
其实就是判断表的长度是否为0而已。将表置空的函数就更简单了，直接将长度赋值为0即可。
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(SqList *L)
{
L->length=0;
return OK;
}
函数调用
i=ClearList(&L);
printf("清空L后：L.length=%d\n",L.length);
注意这里是使用地址传值，毕竟要对表进行清空操作，所以这里不用值传递。
这两个函数如果要测试的话可以自行加入到刚刚的完整可运行代码里。
线性表的查找功能
如何设计查找功能的函数呢。首先参数，我们需要传入线性表L，仅仅查找的话是不需要对表进行变化的，所以用值传递就行。然后就是传入需要查找元素的位置 i，最后还需要一个参数 *e，这个需要用地址传递，因为要保存函数的查找结构。所以函数设计如下：
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i<1 || i>L.length)
return ERROR;
*e=L.data[i-1];
return OK;
}
调用如下：
SqList L;
ElemType e;
int pos;
printf("你要查找第几个元素？ ");
scanf("%d",&pos);
GetElem(L,pos,&e);
printf("第%d个元素的值为：%d\n",pos,e);
线性表是从1开始的
查找蛮简单的，就是 *e=L.data[i-1]; 把线性表数据数组的第 i 个，也就是下标 i - 1 的元素赋值给 *e; 只是要注意，保存数据的 e 需要地址传值。
还有一个查找需求，就是知道一个数值，查找这个值是否在表中。函数原型，int locateElem(L,e); //查找线性表中是否有e，如果有返回它的位置(从1开始)，否则返回0表示失败。
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(SqList L,ElemType e)
{
int i;
if (L.length==0)
return 0;
for(i=0;i < L.length;i++)
{
if (L.data[i]==e)
break;
}
if(i>=L.length)
return 0;
return i+1;
}
线性表的删除
删除算法的思路：
- 如果删除位置不合理，抛出异常；
- 取出删除元素；
- 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
- 表长减1。
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if (L->length==0) /* 线性表为空 */
return ERROR;
if (i < 1 || i>L->length) /* 删除位置不正确 */
return ERROR;
*e=L->data[i-1];
if (i < L->length) /* 如果删除不是最后位置 */
{
for(k=i;k < L->length; k++)/* 将删除位置后继元素前移 */
L->data[k-1]=L->data[k];
}
L->length--;
return OK;
}
参数设计与插入函数一样，从第 i-1 （数组有0下标）个元素开始，将后一个元素挪前一个位置。最后线性表长度减一。
完整的可运行程序如下：
#include "stdio.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef struct
{
ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
int length; /* 线性表当前长度 */
}SqList;
/* 初始化顺序线性表 */
Status InitList(SqList *L)
{
L->length=0;
return OK;
}
//顺序表的建立
SqList Create(SqList L)
{
int i;
srand((unsigned)time(NULL));
for(i=0; i < 10; i++)
{
L.data[i] = rand()%100;
L.length++;
}
return L;
}
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(SqList *L)
{
L->length=0;
return OK;
}
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{
int i;
for(i=0;i < L.length;i++)
visit(L.data[i]);
printf("\n");
return OK;
}
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if (L->length==MAXSIZE) /* 顺序线性表已经满 */
return ERROR;
if (i < 1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
return ERROR;
if (i <= L->length) /* 若插入数据位置不在表尾 */
{
for(k=L->length-1;k>=i-1;k--) /* 将要插入位置之后的数据元素向后移动一位 */
L->data[k+1]=L->data[k];
}
L->data[i-1]=e; /* 将新元素插入 */
L->length++;
return OK;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if (L->length==0) /* 线性表为空 */
return ERROR;
if (i < 1 || i>L->length) /* 删除位置不正确 */
return ERROR;
*e=L->data[i-1];
if (i < L->length) /* 如果删除不是最后位置 */
{
for(k=i; k < L->length; k++)/* 将删除位置后继元素前移 */
L->data[k-1]=L->data[k];
}
L->length--;
return OK;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i < 1 || i>L.length)
return ERROR;
*e=L.data[i-1];
return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(SqList L,ElemType e)
{
int i;
if (L.length==0)
return 0;
for(i=0;i < L.length;i++)
{
if (L.data[i]==e)
break;
}
if(i>=L.length)
return 0;
return i+1;
}
int main()
{
SqList L;
ElemType e;
Status i;
char opp;
int j,k;
int pos;
ElemType value;
i=InitList(&L);
printf("初始化成功，L.length=%d\n",L.length);
printf("\n1.遍历线性表 \n2.线性表赋值 \n3.清空线性表 \n4.线性表插入 \n5.查找表中元素 \n6.判断元素是否在表中 \n7.删除某个元素 \n0.退出 \n请选择你的操作：\n");
while(opp != '0'){
scanf("%c",&opp);
switch(opp){
case '1':
ListTraverse(L);
printf("\n");
break;
case '2':
L = Create(L);
printf("创建随机链表：L.data=");
ListTraverse(L);
printf("\n");
break;
case '3':
i=ClearList(&L);
printf("清空L后：L.length=%d\n",L.length);
ListTraverse(L);
printf("\n");
break;
case '4':
printf("请输入插入元素位置：");
scanf("%d",&pos);
printf("请输入插入元素的值：");
scanf("%d",&value);
i = ListInsert(&L,pos,value);
printf("插入完毕，现在线性表为：\n");
ListTraverse(L);
printf("\n");
break;
case '5':
printf("你要查找第几个元素？ ");
scanf("%d",&pos);
GetElem(L,pos,&e);
printf("第%d个元素的值为：%d\n",pos,e);
break;
case '6':
printf("输入你想知道是否在表中的数值： ");
scanf("%d",&e);
k=LocateElem(L,e);
// 这里假定随机数组中的元素互不重复
if(k)
printf("值为%d是表中的第%d个元素\n",e,k);
else
printf("没有值为%d的元素\n",e);
break;
case '7':
printf("要删除第几个元素？");
scanf("%d",&pos);
ListDelete(&L,pos,&e);
printf("删除完毕，现在线性表为：\n");
ListTraverse(L);
printf("\n");
break;
case '0':
exit(0);
}
}
}
线性表顺序存储结构的优缺点
从优点开始说。当我们在使用线性表的时候，我们不需要为表中元素之间的逻辑关系而增加额外的存储空间，而且可以快速的存取表中任意位置的元素。接下来谈谈缺点。如我们所见，如果我们要插入或者删除的元素是在第一个位置，那么无疑的，我们需要移动大量的元素来完成这样的操作，而且限于线性表长度必须小于数组长度，如果我们需要插入大量数据，那么很难保证空间是否充足，而如果我们要删除大量数据的时候，无疑又会造成空间的浪费。
优点：
具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出；
缺点：
顺序存储插入与删除一个元素，必须移动大了的数据元素，以此对大的线性表，特别是在元素的插入和删除很频繁的情况下，采取顺序存储很是不方便，效率低；
顺序存储空间容易满，出现上溢，程序访问容易出问题，顺序存储结构下，存储空间不便扩充；
顺序存储空间的分配问题，分多了浪费，分少了空间不足上溢。
