线性表
线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面上的概念。
线性表的基本操作
bool InitList(&L)//初始化表，构造一个空的线性表
int Length(L)//求表长。返回线性表L的长度，即L中数据元素的个数
int LocateElem(L,e)//按值查找操作。在表L中查找具有给定关键字值的元素
ElemType GetElem(L,i)//按位查找操作，获取表L中第i个位置的元素的值
bool ListInsert(&L,i,e)//插入操作，在表L的第i个位置上插入指定元素e
bool ListDelete(&L,i,&e)//删除操作，删除表L中的第i个位置的元素，并用e返回删除元素的值
void PrintList(L)//输出操作，按前后顺序输出线性表L的所有元素值
bool Empty(L)//判空操作，若L为空表，则返回true,否则返回false
void DestroyList(&L)//销毁操作，销毁线性表，并释放线性表L所占用的内存空间顺序表
顺序存储结构的优点：存储密度大，每个节点只存储数据元素。
顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间O(1)内找到指定的元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。
单链表
定义单链表结点类型
#include<stdio.h>
#define ElemType int
typedef struct LNode{//定义单链表节点类型
ElemType data;
struct LNode *next;
}LNode,*LinkList;通常用头指针来标识一个单链表，如单链表L。
头指针为NULL时表示一个空表。
此外为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。
头结点的指针域指向线性表的第一个元素结点。
引入头结点带来的优点：①链表第一个位置上的操作和其他位置上的操作一致，无需进行特殊处理。②空表和非空表的处理得到了统一。
采用头插法和尾插法建立单链表
//建立单链表
LinkList List_HeadInsert(LinkList &L){//头插法建立单链表
LinkList s;int x;//假设单链表的元素类型都是int好了，也别搞什么ElemType了
L=(LinkList)malloc(sizeof(LNode));//先把头结点安排上
L->next=NULL;//不要忘记这一步，否则单链表建成后发现尾结点不是NULL
scanf("%d",&x);
while(x!=9999){//输入9999就是结束
s=(LNode*)malloc(sizeof(LNode));//创建新结点
s->data=x;
s->next=L->next;//注意看这一步，所以才是头插嘛
L->next=s;
scanf("%d",&x);
}
return L;
}
LinkList List_TailInsert(LinkList &L){//尾插法建立单链表
LinkList s;int x;
L=(LinkList)malloc(sizeof(LNode));//别忘了先把头结点的空间开辟好！
LNode *t;//t为表尾指针
t=L;
scanf("%d",&x);
while(x!=9999){
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
t->next=s;
t=s;
scanf("%d",&x);
}
t->next=NULL;//插入结束后，安排一下尾结点的指针为NULL
return L;
}输出测试一下
//输出单链表，测试用的
void PrintList(LinkList L){
LNode *s;
s=L->next;
printf("开始输出：\n");
while(s!=NULL){
printf("%d ",s->data);
s=s->next;
}
printf("\n**输出结束**\n");
}两个查找：按值查找和按序号查找结点
//按序号查找节点
LNode *GetElem(LinkList L,int i){
if(i<1){return NULL;}//输入不合法，直接返回NULL得了
LNode *s=L->next;//创建一个临时指针，指向第一个元素
int j=1;
while(j!=i){
s=s->next;
j++;
}
return s;//直接把整个LNode结点作为结果返回了
}
//按值查找表节点
LNode *LocateElem(LinkList L,ElemType e){
LNode *s=L->next;
while(s->data!=e&&s!=NULL){
s=s->next;
}
return s;//直接把整个LNode结点作为结果返回了
}两个操作：插入结点操作和删除结点操作
//插入节点操作
bool ListInsert(LinkList &L,int i,ElemType e){
if(i==1){
LNode *newnode=(LNode*)malloc(sizeof(LNode));
newnode->data=e;
newnode->next=L->next;
L->next=newnode;
return true;
}//之所以专门搞个i==1的情况还是受限于GetElem不能把头结点给弄出来
LNode *s=GetElem(L,i-1);//用上边的GetElem先获取第i-1个结点******这一步要注意，可以利用已有的函数
if(s==NULL)return false;
LNode *newnode=(LNode*)malloc(sizeof(LNode));//创建一个新结点并开辟空间
newnode->data=e;
newnode->next=s->next;
s->next=newnode;
return true;
}
//删除节点操作
bool ListDelete(LinkList &L,int i){
if(i==1){
LNode *s=L->next;
L->next=L->next->next;
free(s);
return true;
}
LNode *s=GetElem(L,i-1);
if(s==NULL)return false;
LNode *temp=s->next;
s->next=s->next->next;
free(temp);
return true;
}
//求表长操作
int Length(LinkList L){
LNode *s=L->next;
int i=0;
while(s!=NULL){
s=s->next;
i++;
}
return i;
}