线性表(Linear List):由同类型数据元素构成有序序列的线性结构。
类型名称：线性表（List）。
数据对象集：线性表是 n(n≥0) 个元素构成的有序序列 ( a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an)。
操作集：线性表 L ∈ L i s t L \in List L∈List,整数i表示位置，元素 X ∈ E l e m e n t T y p e X \in ElementType X∈ElementType,线性表的基本操作主要有：
利用数组的连续存储空间顺序存放线性表的各元素。
struct LNode{
ELementType Data[MAXSIZE];//MAXSIZE是空间大小
int Last;//最后一个元素的下标是Last，而不是Last+1
};
typedef struct LNode* List;
struct LNode L;
List LPtr;
访问下标为i的元素：L.Data[i]或LPtr->Data[i]。
线性表的长度：L.Last+1或者LPtr->Last+1。
主要操作的实现
初始化（建立空的顺序表）
List MakeEmpty()
{
List LPtr=NULL;
LPtr=(List)malloc(sizeof(struct LNode));
LPtr->Last=-1;
return LPtr;
}
查找
int Find(ElementType X,List LPtr)
{
int i=0;
while(i<=LPtr->Last&&LPtr->Data[i]!=x)
{
i++;
}
if(i>LPtr->Last)
{
return -1;//如果没有找到，返回-1
}
else
{
return i;//找到后返回存储位置i
}
}
插入（第i（ 1 ≤ i ≤ n + 1 1 \leq i \leq n+1 1≤i≤n+1)个位置上插入一个之为X的新元素）
| 下标i | 0 | 1 | …… | i-1 | i | …… | n-1 | …… | MAZSIZE-1 |
|---|---|---|---|---|---|---|---|---|---|
| Data | a 1 a_1 a1 | a 2 a_2 a2 | …… | a i a_i ai | a i + 1 a_{i+1} ai+1 | …… | a n ( L a s t ) a_n(Last) an(Last) | …… | - |
再第i个位置插入，将 a i a_i ai~ a n a_n an往后移动，再插入。
| 下标i | 0 | 1 | …… | i-1 | i | i+1 | …… | n | …… | MAZSIZE-1 |
|---|---|---|---|---|---|---|---|---|---|---|
| Data | a 1 a_1 a1 | a 2 a_2 a2 | …… | a i a_i ai | a i + 1 a_{i+1} ai+1 | …… | a n ( L a s t ) a_n(Last) an(Last) | …… | - |
算法实现：
void Insert(ElementType X,int i,List LPtr)
{
int j=0;
//表空间已满，不能插入
if(LPtr->Last==MAXSIZE-1)
{
printf("表满\n")；
return；
}
//检查插入位置的合法性
if(1>i||LPtr->Last+2<i)
{
printf("位置不合法\n");
return;
}
//将a_i~a_n往后移动
for(j=LPtr->Last;j>=i-1;j--)
{
LPtr->Data[j+1]=LPtr->Data[j];
}
LPtr->Data[i-1]=X;//将数据X放在第i个位置
LPtr->Last++;//Last指向最后一个元素
}
平均移动次数为n/2
平均时间复杂度为O(n)。
删除（删除表的第i（ 1 ≤ i ≤ n 1 \leq i \leq n 1≤i≤n）个位置上的元素）
| 下标i | 0 | 1 | …… | i-1 | i | …… | n-1 | …… | MAZSIZE-1 |
|---|---|---|---|---|---|---|---|---|---|
| Data | a 1 a_1 a1 | a 2 a_2 a2 | …… | a i a_i ai | a i + 1 a_{i+1} ai+1 | …… | a n ( L a s t ) a_n(Last) an(Last) | …… | - |
删除第i个位置的数据，将第i个数据之后的数据往前挪。
| 下标i | 0 | 1 | …… | i-1 | …… | n-2 | n-1 | …… | MAZSIZE-1 |
|---|---|---|---|---|---|---|---|---|---|
| Data | a 1 a_1 a1 | a 2 a_2 a2 | …… | a i + 1 a_{i+1} ai+1 | …… | a n ( L a s t ) a_n(Last) an(Last) | …… | - |
算法实现：
void Delete(int i,List LPtr)
{
int j=0;
//检查空表及删除位置的合法性
if(1>i||i>LPtr->Last+1)
{
printf("不存在第%d个元素",i);
return;
}
//将第i个元素后面的元素向前移动
for(j=i;j<=LPtr->Last;j++)
{
LPtr->Data[j-1]=LPtr->Data[j];
}
LPtr->Last--;//Last指向最后元素
}
平均移动次数为(n-1)/2
平均时间复杂度O(n)。
线性表的链式存储实现
不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系。
struct LNode{
ElementType Data;
struct LNode *Next;
};
typedef struct LNode *List;
struct LNode L;
List LPtr;
主要操作的实现
求表长
int Length(List LPtr)
{
List currentPtr=LPtr;//currentPtr指向第一个节点
int i=0;
while(currentPtr)
{
currentPtr=currentPtr->Next;
i++;
}
return i;
}
时间复杂度O(n)。
查找
按序号查找：FindKth();
List FindKth(int K,List LPtr)
{
List currentPtr=LPtr;
int i=1;
//将currentPtr指向第K个元素或者将currentPtr指向最后的NULL
while(currentPtr!=NULL&&K>i)
{
currentPtr=currentPtr->Next;
i++;
}
//判断K是否超过链表长度，没有超过返回指向第K个元素指针，超过则返回NULL
if(K==i)
{
return currentPtr;
}
else
{
return NULL;
}
}
时间复杂度O(n)。
按值查找：Find()
List Find(ElementType X,List LPtr)
{
List currentPtr=LPtr;
while(currentPtr!=NULL&&X!=currentPtr->Data)
{
currentPtr=currentPtr->Next;
}
return currentPtr;
}
时间复杂度O(n)。
插入（再第i-1（ 1 ≤ i ≤ n + 1 1 \leq i \leq n+1 1≤i≤n+1）个节点后插入一个值为X的新节点）
插入前：
操作顺序：
s->Next=p->Next;
p->Next=s;
插入后：
代码示例：
List Insert(ElementType X,int i,List LPtr)
{
List p=NULL,s=NULL;
//插入节点在表头的情况
if(i==1)
{
s=(List)malloc(sizeof(struct LNode));//构造新节点
s->Data=X;
s->Next=LPtr;
return s;
}
//插入节点不再表头的情况
p=FindKth(int i-1,LPtr);//查找第i-1个节点
//第i-1个节点不存在，不能插入
if(p=NULL)
{
printf("参数i错误");
return NULL;
}
else
{
s=(List)malloc(sizeof(struct LNode));//构造新节点
s->Data=X;
s->Next=p->Next;
p->Next=s;
return LPtr;
}
}
时间复杂度O(n)。
删除（删除链表的第i（ 1 ≤ i ≤ n 1 \leq i \leq n 1≤i≤n)个位置上的节点）
删除前：
操作顺序：
p->Next=s->Next;
free(s);
删除后：
代码示例：
List Delete(int i,List LPtr)
{
List p=NULL,s=NULL;
//要删除的节点是头节点的情况
if(1==i)
{
s=LPtr；
//判断是不是空表
if(LPtr!=NULL)
{
LPtr=LPtr->Next;
free(s);
return LPtr;
}
else
{
return NULL;
}
}
//要删除的节点不是头节点的情况
p=FindKth(i-1,LPtr);
//第i个节点不存在的情况
if(p==NULL||p->Next==NULL)
{
printf("第%d个节点不存在",i)；
return NULL;
}
//第i个节点存在的情况
else
{
s=p->Next;//s指向将被删除的第i个节点
p->Next=s->Next;//删除节点
free(s);//释放被删除节点
return LPtr;
}
}
时间复杂度O(n)。
struct GNode{
int Tag;//标志域：0表示节点是单元素，1表示节点是广义表
//子表指针域subList与单元数据域Data复用，即共用存储空间
union{
ElementType Data;
GList SubList;
}URegion;
struct GNode *Next;//指向后继节点
};
typedef struct GNode* GList;
多重链表：链表中的节点可能同时属于多个链
多重链表有广泛的用途：基本上如树、图这样的相对复杂的数据结构都可以采用多重链表方式实现存储。
多重链表的应用：
矩阵多重链表示意图:
矩阵多重链表节点设计:
堆栈（Stack）：具有一定操作约束的线性表。
只在一端（栈顶，Top）做插入、删除
插入数据：入栈（Push）
删除数据：出栈（Pop）
后入先出：Last In First Out(LIFO)
类型名称：堆栈(Stack)
数据对象集：一个有个或多个元素的有穷线性表。
操作集：长度为MaxSize的堆栈
S
∈
S
t
a
c
k
S \in Stack
S∈Stack,堆栈元素
i
t
e
m
∈
E
l
e
m
e
n
t
T
y
p
e
item \in ElementType
item∈ElementType
栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。
#define MaxSize <存储数据元素的最大个数>
struct SNode{
ElementType Data[MaxSize];
int Top;//栈顶的下标
};
typedef struct SNode* Stack;
主要操作实现
入栈
void Push(Stack SPtr, ElementType itme)
{
if(SPtr->Top==MaxSize-1)
{
printf("堆栈满");
return;
}
else
{
SPtr->Data[++(SPtr->Top)]=itme;//Top先自加一，然后再给栈顶元素赋值。
return;
}
}
出栈
ElementType Pop(Stack SPtr)
{
if(SPtr->Top==-1)
{
printf("堆栈空");
return ERROR;//ERROR是ElementType的特殊值，标志错误
}
else
{
return (SPtr->Data[(SPtr->Top)--]);//先返回栈顶元素，再将Top减一。
}
}
堆栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。
思考：栈顶指针Top应该在链表的哪一头？
答：应该将栈顶指针放在链表的头部，这样插入和删除操作都很方便；如果将栈顶指针放在链表尾部，那么删除操作实现比较困难。
struct SNode{
ElementType Data;
struct SNode *Next;
};
typedef struct SNode* Stack;
主要操作实现
建立空栈（空栈指只有一个头节点，节点不带任何数据）
Stack CreateStack()
{
//建立堆栈的一个头节点，返回指针。
Stack S=NULL;
S=(Stack)malloc(sizeof(struct SNode));
S->Next=NULL;
return S;
}
判断堆栈S是否为空
int IsEmpty(Stack S)
{
//为空返回1；否则返回0
return (S->Next==NULL);
}
入栈
void Push(ElementType item,Stack S)
{
//不需要判断空间是否已经满了，因为链式堆栈的空间是动态申请的。
Stack Temp=NULL;
Temp=(stack)malloc(sizeof(struct SNode));
Temp->Data=item;
Temp->Next=S->Next;
S->Next=Temp;
}
出栈
ElementType Pop(Stack S)
{
Stack TempCell=NULL;
ElementType TempElem=0;
if(S->Next==NULL)
{
printf("d堆栈空");
return NULL;
}
else
{
TempCell=S->Next;
S->Next=TempCell->Next;
TempElem=TempCell->Data;
free(TempCell);
return TempElem;
}
}
队列（Queue）：具有一定操作约束的线性表
数据名称：队列（Queue）
数据对象集：一个有0个或多个元素的有穷线性表。
操作集：长度为MaxSize的队列
Q
∈
Q
u
e
u
e
Q \in Queue
Q∈Queue，队列元素
i
t
e
m
∈
E
l
e
m
e
n
t
T
y
p
e
item \in ElementType
item∈ElementType
队列的顺序存储结构通常由一个一位数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。（rear指向对列尾最后一个元素，front指向队列头元素的前一个元素）
#define MAXSIZE <存储数据元素的最大个数>
struct QNode{
ElementType Data[MAXSIZE];
int rear;
int front;
};
typedef struct QNode *Queue;
在循环队列中，判空和判满的条件都是rear==front:
队列空时：
队列将满时（再增加一个元素之后队列满，然后rear==front）：
解决这个问题的方法有两种：
使用额外标记：size或者tag域
仅使用MAXSIZE-1个数组空间
入队列
void AddQ(Queue QPtr,ElementType item)
{
if((QPtr->rear+1)%MAXSIZE==QPtr->front)
{
printf("队列满");
return;
}
QPtr->rear=(QPtr->rear+1)%MAXSIZE;
QPtr->Data[QPtr->rear]=item;
}
出队列
ElementType DeleteQ(Queue QPtr)
{
if(QPtr->rear==QPtr->front)
{
printf("队列空");
return ERROR;
}
else
{
QPtr->front=(QPtr->front+1)%MAXSIZE;
return QPtr->Data[QPtr->front];
}
}
队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行。（front指向队列头元素，rear指向队列尾元素）
问：队列指针front和rear应该分别指向链表的哪一头？
答：队列front端用来进行删除操作，rear端用来做插入操作；而单向链表的头部插入删除都很方便，尾部插入方便，但是删除麻烦；所以front应该指向单向链表的头部，rear应该指向单向链表的尾部。
//链表节点结构
struct Node{
ElementType Data;
struct Node *Next;
};
//队列头尾结构
struct QNode{
struct Node *rear;
struct Node *front;
};
typedef struct QNode *Queue;
Queue QPtr;
入队列（不带头结点）
void AddQ(Queue QPtr,ElementType item)
{
//新建一个节点
struct Node *RearCell;
RearCell=(struct Node*)malloc(sizeof(struct Node));
RearCell->Data=item;
RearCell->Next=NULL;
//队列为空的情况
if(QPtr->rear==NULL)
{
QPtr->rear=RearCell;
QPtr->front=RearCell;
}
//队列不为空时
else
{
QPtr->rear->Next=RearCell;
QPtr->rear=RearCell;
}
}
出队列（不带头结点）
ElementType Delete(Queue QPtr)
{
struct Node *FrontCell;
ElementType FrontElem;
if(QPtr->front==NULL)
{
printf("队列空");
return ERROR;
}
FrontCell=QPtr->front;//将FrontCell指向当前头元素
//队列只有一个元素时
if(QPtr->front==QPtr->rear)
{
//将front和rear都指向空
QPtr->front=NULL;
QPtr->rear=NULL;
}
//队列不止一个元素时
else
{
//将front指向下一节点
QPtr->front=QPtr->front->Next;
}
FrontElem=FrontCell->Data;
free(FrontCell);//释放被删除节点
return FrontElem;
}