线性表
用于存储若干相同属性元素的有序序列称为线性表。
直线工作台特点：
- 有一个独特的第一个元素；
- 只有最后一个元素；
- 序列中除第一个元素外的每个元素都有一个前驱元素，最后一个元素有一个后继元素。
顺序表
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素， 这种表示
也称作线性表的顺序存储结构，称为顺序表。
顺序表满足等差数列：LOC(a;+ 1) = LOC(a;) + i
线性表的第l个数据元素a;的存储位置为： LOC(a;) = LOC(a1) + (i - I) x i
LOC(a1)是线性表的第一个数据元素a1 的存储 存储地址位置，·通常称作线性表的起始位置或基地址， 表中相邻的元素a; 和a; + I 的存储位置LOC(a;)和LOC(a;+ 1) 是相邻的。因此顺序表中最要的就是起始地址，知道起始地址可以计算任何位置的值。只要确定了存储线性表的起始位置， 线性表中任一数据元素都可随机存取， 所以线性表的顺序存储结构是一种随机存取存储结构。
数组是C语言中一种特殊的数据结构。与int、float类型不同，数组是几种基本数据类型的集合，可以存储多种基本数据类型变量的数据类型。数组的本质也是一种数据类型，但是它会存储多个变量的错误值。
序列表也是基于数组实现的，可以是动态分配的存储空间，也可以是定值的表空间。
对于序列表的数据结构来说，需要对数据实现增删改查操作。 （数组只能由用户存储，不能进行操作。如果序列表是基于定值数组实现的，那么序列表至少包含两个信息，表的长度和表的数据。
- 添加
数组可以通过循环赋值来实现。序列表需要尝试对数组进行操作，在某个位置添加元素，或者通过尾部插值或头部插值的方式添加数据。
在尾部插入数据需要对数组长度加一并对新的数组元素赋值；向数组的任何部分插入值需要将数组中该位置之后的所有元素向后移动 1，以便为新元素腾出空间。
- 修订
修改意味着重新分配，即重新分配表中的指定位置。
- 删除
删除与添加类似。需要先找到指定位置的元素，并将后一个元素赋值给该位置的前一个元素，即将该位置的元素向前移动一位。
- 寻找
要查找表中的所有元素，需要遍历，直到找到所需元素的位置。
变量用于提供信息。语言之间的信息分为几类，即基本数据类型，如int、float、long等。但是这些只能存储一条信息，无法存储某一类型信息的集合，所以有一个数组。数据类型，用于存储相同类型的变量。序列表是实现对数组类型的操作。
#include<stdio.h>
#define MAXSIZE 10
//结构体定义
struct List{
int item[MAXSIZE];
int length;
};
//结构体声明
typedef struct List SeqList;
//方法申明
int InitList(SeqList *list);
int AddElem(SeqList *list ,int e);
int InsertElem(SeqList *list,int i,int e);
int GetElem(SeqList *list,int e);
int DeleteElem(SeqList *list,int n);
void displayElem(SeqList list);
int main(){
SeqList a;
InitList(&a);
AddElem(&a,2);
AddElem(&a,8);
InsertElem(&a,1,10);
InsertElem(&a,3,20);
//InsertElem(&a,8,200); //插入失败但是没有提示
displayElem(a);
int tmp = GetElem(&a,8);
printf("取出的值位次为：%d\n",tmp);
DeleteElem(&a,1);
displayElem(a);
}
// list -> item <===> (*list).item
int InitList(SeqList *list){
list -> item[0] = 0;
list -> length = 0;
if (!list) return 0;
return 1;
}
int AddElem(SeqList *list ,int e){
//判断表是否满（略）
int i = list->length ;
list ->item[i] = e;
list->length ++;
}
int InsertElem(SeqList *list,int i,int e){
if(i<1 || i> (list ->length)){
//TODO
return 0;
}
//判断表是否满了 (略)
int j;
for(j=(list->length);j>i-1;j--){
list->item[j] = list->item[j-1];
}
list->item[i-1] = e;
list->length +=1;
return i;
}
int GetElem(SeqList *list,int e){
int i;
for(i=0;i<(list->length);i++){
if(list->item[i] == e){
return i+1;
}
}
return 0;
}
//按位次删除
int DeleteElem(SeqList *list,int n){
if (n<1 || n>list->length){
return 0;
}
for(int i=n-1;i<list->length;i++){
list->item[i] = list->item[i+1];
}
list->length--;
}
void displayElem(SeqList list){
int i;
for(i= 0;i<= list.length-1;i++){
//TODO
printf("%d,",list.item[i]);
}
printf("\n");
}
如上的代码就是实现顺序表的操作，其中list -> item <===> (*list).item。
上述代码是定值表，也是就该顺序表最多课存储MAXSIZE个元素，若想实现动态的数组，需要将存储数据的变量定义为指针变量。
#include<stdio.h>
#include <stdlib.h>
#define SIZE 5
struct ListTo{
int *item;
int length;
int size;
};
typedef struct ListTo List;
int main(){
List t;
t.item=(int*)malloc(SIZE*sizeof(int));
//第一次赋值
t.item[0] = 1;
t.size = SIZE;
printf("第一次赋值后表的容量为%d\n",t.size);
for(int i=1;i<8;i++){
//TODO
*(t.item+i) = i;
}
for(int i=1;i<8;i++){
//TODO
printf("%d\n", *(t.item+i));
}
//int *p
printf("8次赋值后表的长度为%d\n",sizeof(t.item)/sizeof(int));
}
说到动态内存分配，需要注意的是，序列表包含两个长度，一个是卷，另一个是当前长度。当存储的数据超过表的长度时，数组会动态分配一个新的双长度数组。
链表
线性表链式存储结构的特点是用一组任意的存储单元来存储线性表的数据元素。对于数据中的任何元素，除了存储数据之外，还需要存储直接后继元素的节点信息，以将整个数据连接在一起。
链表中存储数据和后续信息的每个元素称为节点，包括数据字段和指针字段。链表的每个节点只包含一个指针字段，因此也称为线性链表或单向链表。
根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、
双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表和双向链表用
千实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。
可见单链表由头节点唯一确定。
上述对序列表的操作都需要使用指针。原因是在传递参数时，直接使用变量名按值传递，再次克隆了变量。因此，形式参数是实际参数的备份。函数运行后，合并实际参数。不会有任何改变，它会保持不变。当使用指针作为形参时，传递的是实参的地址。对地址的操作会改变实际参数的值。因此，执行指针作为参数的函数会改变实际参数的值。
在单链表中每一个结点都是一个变量，共同存在于内存中，通过指针信息联系起来。
- 单链表节点定义
typedef struct LNode{
int data;
struct LNode *next;
}LNode,LinkList;
每个节点都是一个结构变量，包含数据和后续节点指针。指针也是一种节点类型，并且是递归使用的。
LNode和LinkList是同一类型，在逻辑上定义前者为结点，后者为整个链表。
- 链表的创建
根据上图可以看出，链表的节点本质上是不同的变量。变量之间通过记录地址连接，变量为n个同级。
注意，链表不能通过方法创建，因为链表是由多个同级节点通过地址连接而成的。局部变量在方法中创建，并在方法结束时销毁。
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef struct LNode{
int data;
struct LNode *next;
}LNode,LinkList;
int main(){
//生成链表
LinkList* L = (LNode*)malloc(sizeof(LNode));
//链表必须存在头指针
LNode* head = L;
printf("输入添加元素的个数:\n");
int e,length;
scanf("%d",&length);
for(int i=0;i<length;i++){
//创建新结点
LNode* node = (LNode*)malloc(sizeof(LNode));
printf("请输入：");
scanf("%d",&e);
node->data = e;
node->next =NULL;
head->next = node;
head = node; //头指正记录当前最后一个结点
}
//打印链表
while(L->next != NULL){
L=L->next;
printf("%d",L->data);
}
}
链表由头节点或首节点唯一确定，并通过记录的地址顺序寻址。上面的代码通过尾部插入创建了一个链表。
LinkList* L = (LNode*)malloc(sizeof(LNode))创建了一个链表指针。
LNode* head = L创建头结点，实际上就是链表指针，在逻辑上充当头结点，作用是记录当前结点，并传递结点地址。（也可以直接将链表指针当做做头结点，一样的意义）。
LNode* node = (LNode*)malloc(sizeof(LNode))每次输入创建新的结点，并将头结点后继结点地址指向新结点head->next = node，在头结点之后就插入了一个新的结点。
此时链表中存在两个结点头结点和A结点，如再插入一个结点就有两种方案：（1）将A结点后继结点指向新结点地址即NULL改为新结点（后插法或尾插法）；（2）新结点的后继结点地址改为头结点后继节点地址，头结点后继结点改为新结点地址（前插法或头插法）。
（1）后插法
head = node非常关键，执行该程序使的head重新指向新的地址，实际上头结点head是一个逻辑上的头结点，依次移想新结点地址，而原地址就为存放结点信息的链表结点。
后插法中，每次逻辑头节点移动到新的节点地址时，都将原来的地址作为独立的节点来存储信息。
［算法步骤】
1.创建一个只有头结点的空链表。
2.尾指针r初始化， 指向头结点。
3.根据创建链表包括的元素个数n, 循环n次执行以下操作：
• 生成一个新结点p;
• 输入元素值赋给新结点p 的数据域；
• 将新结点p 插入到最后一个节点r之后；
• 尾指针r指向新的尾结点*p。
简单来说，后插法中，尾节点的指针域指向新节点后，与新节点交换地址。原来的尾指针地址存储了新的节点地址，新的节点地址成为尾指针。比喻。这样，每次前一个节点存储下一个节点的地址，就相当于尾指针作为游标向后移动。
(2) 正向插值法
在前插法中头结点是不变的，改变的只有头结点的指针域。每次有新结点时，将新结点的指针域指向头结点的指针域，头结点的指针域指向新结点。，将头结点初始指针域设置为NULL，那么从结点生成开始后续结点的指针域都存储了前一个结点地址。
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
int data;
struct LNode *next;
}LNode,LinkList;
int main(){
//创建空链表
LinkList* L = (LinkList*)malloc(sizeof(LinkList));
L->next =NULL;
for(int i=0;i<5;i++){
LNode* node = (LNode*)malloc(sizeof(LNode));
node->data = i+1;
node->next = L->next;
L->next = node;
}
while(L->next != NULL){
L = L->next;
printf("%d",L->data);
}
}
【算法步骤】
1.创建一个只有头结点的空链表。
2.根据待创建链表包括的元素个数n, 循环n次执行以下操作：
• 生成一个新结点p;
• 输入元素值赋给新结点p的数据域；
• 将新结点*p插入到头结点之后。