线性表
一般情况下，按照存储方式，线性表分为两种，顺序存储（用地址连续的存储单元依次存储线性表的数据元素），链式存储（每一个存储单元，除了保存自己的信息以外，还需要保存后继存储单元的内存地址。）
线性表的抽象数据类型定义
ADT 线性表(List)
Data
线性表的数据对象集合为{a1,a2,a3,...}，每个元素的类型均为DataType。其中，除了第一个元素a1外，每一个元素有且仅有一个直接前驱元素，除了最后一个元素an以外，每个元素有且仅有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
InitList(*L);
ListEmpty(L);
ClearList(*L);
GetElem(L,i,*e);
LocateElem(L,e);
ListInsert(*L,i,e);
ListDelete(*L,i,*e);
ListLength(L);
endADT线性表的顺序存储结构—顺序表
顺序表的结构声明
利用结构体的方式定义顺序表 这个才是最重要的
#define MAXSIZE 20 /*存储空间初始化分配量*/
/*定义一个顺序存储的线性表*/
typedef int ElemType; /*ElemType类型视实际情况而定，这里假设是int*/
typedef struct{
ElemType data[MAXSIZE]; /*数组存储数据元素，最大值为MAXSIZE*/
int length; /*线性表当前的长度*/
}SqList; 顺序表具体操作
初始化 只需要将顺序表的长度置为0即可
Status InitList(SqList *L){
L->length = 0; /*初始化的操作很简单，将长度设置为即可*/
return OK;
}不初始化顺序表可能会出现错误，下午L初始化了的顺序表，L2是没有初始化的顺序表。输出L2有其他东西在里面。
获取 遍历顺序表将数据逐个输出
/*获取元素的操作*/
Status GetElem(SqList L, int i, ElemType *e){
if(L.length==0 || i<i || i>L.length)
return ERROR;
*e = L.data[i-1];
return OK;
}插入 先从插入位置开始将数据元素逐个后移，空出插入位置，然后再把要插入的数据放到插入位置，最后记得将长度加一。
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 在指定位置后插入数据 */
Status ListInsert(SqList *L, int i, ElemType e){
int k;
if(L->length==MAXSIZE) /* 顺序表已经满了 */
return ERROR;
if(i<1 || i>L->length+1) /* 下标位置越界不做处理 */
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;
}删除 把插入位置之后的元素一个一个向前移动，最后将总长度减一。
/* 删除指定位置的元素 */
Status ListDelete(SqList *L, int i, ElemType *e){
int k;
if(L->length==MAXSIZE) /*顺序表已经满了*/
return ERROR;
if(i<1 || i>L->length+1) /*下标位置越界不做处理*/
return ERROR;
*e = L->data[i-1]; /*暂存要删除位置的数据 */
if(i<L->length){
for(k=i-1; k<L->length-1; k++)
L->data[k] = L->data[k+1];
}
L->length--; /*将顺序表的长度减一*/
return OK;
}遍历显示顺序表中的元素 直接按照顺序输出即可
/* 遍历显示顺序表中的所有元素的函数 */
Status ListShow(SqList *L){
for(int i=0; i<L->length; i++){
/* 打印的时候是不需要的加&的 */
printf("%d ", L->data[i]);
}
printf("\n");
return OK;
}复制顺序表的函数 将一个顺序表遍历赋值给另外一个顺序表
/* 复制顺序表的函数 */
SqList ListCopy(SqList *L){
SqList temp;
temp.length = L->length;
for(int i=0; i<L->length; i++){
temp.data[i] = L->data[i];
}
return temp;
}将顺序表逆序 遍历元素之后首位交换
/* 将顺序表逆序的函数 */
Status ListReverse(SqList *L) {
SqList temp = ListCopy(L); // 在这里L已经是一个指针了
for(int i=0; i<temp.length; i++){
L->data[i] = temp.data[temp.length-i-1];
}
return OK;
}获取特定位置的元素 直接用下标查找
/* 获取特定位置元素的操作 */
Status GetElem(SqList L, int i, ElemType *e){
if(L.length==0 || i<i || i>L.length)
return ERROR;
*e = L.data[i-1];
return OK;
}
置空顺序表 直接将顺序表的length置为0即可
/* 将顺序表置空 */
Status ClearList(SqList *L){
L->length = 0;
return OK;
}判断顺序表是否为空
/* 判断顺序表是否为空表 */
Status ListEmpty(SqList L){
if(L.length==0)
return TRUE;
else
return FALSE;
}
获取顺序表长度
/* 初始条件：线性表已经存在并初始化。 */
/* 获取顺序表线性中数据的个数 */
int ListLength(SqList L){
return L.length;
}定位顺序表中某个元素的位置 遍历查找，找到即返回。
/* 返回顺序表中第1个与e大小相等的数据元素的位序。 */
int LocateElem(SqList L, ElemType e) {
int i;
if(L.length==0){
return ERROR;
}
for(i=0; i<L.length; i++){
if(L.data[i] == e){
return i+1;
}
}
return ERROR;
}合并两个线性表的函数
void unionList(SqList *La,SqList Lb)
{
int La_len,Lb_len,i;
ElemType e;
La_len=ListLength(*La);
Lb_len=ListLength(Lb);
for (i=1;i<=Lb_len;i++)
{
GetElem(Lb,i,&e);
if (!LocateElem(*La,e))
ListInsert(La,++La_len,e);
}
}线性表的链式存储结构—链表
- 链式存储的结点由数据域和指针域组成，因为每一个结点都只有一个指针域，所以叫做单链表。
头指针和头结点
- 一般会在链表的第一个结点前增设一个结点，名为头结点。
- 头指针是指链表指向第一个结点的指针。若链表有头结点，则是指向头结点的指针。
- 头指针具有标识作用，常用头指针冠以链表的名字。
- 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义(也可存放链表的长度)
- 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了。
- 头结点不一定是链表必须要素
、
空链表和链表的区别 空链表头结点的指针域是空的，正常链表头结点的指针域不是空的。
链表的结构声明
利用结构体的方式定义顺序表 这个才是最重要的
#define MAXSIZE 20 /*存储空间初始化分配量*/
/*定义一个顺序存储的线性表*/
typedef int ElemType; /*ElemType类型视实际情况而定，这里假设是int*/
typedef struct{
ElemType data[MAXSIZE]; /*数组存储数据元素，最大值为MAXSIZE*/
int length; /*线性表当前的长度*/
}SqList;