目 录
2 线性表
2.1 线性表的定义
在线性表中，我们将会学习常用的顺序表和链表，使用的语言为C语言，其中包含大量结构体以及指针的内容，务必掌握以上知识，否则理解后面知识会难以接受。
线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为：
L = （a1，a2，...，an）
其中：a1是表头元素，an是表尾元素
重点：除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。
2.2 线性表的基本操作
后面的顺序表以及链表也基本是以下操作，下面操作均以常用的链表为介绍，在此文章不用深究，在链表部分会细讲
（1）定义管理结构体：
一般分为数据域以及指针域
（2）初始化表：
构造一个空的线性表
init：初始化
一般会对初始化表进行函数封装，构造一个空的线性表myList，为其分配内存空间。
（3）对表进行插入操作：
insert：插入
在表myList中插入元素data，在链表中不必考虑数据位置，顺序表需要考虑位置。
（4）对表的值进行删除操作
delete：删除
删除表中的data元素。
（5）对表进行遍历操作
对表遍历后，可以遍历出表中的每个元素。
（6）对表进行销毁操作
destroy：销毁
销毁该线性表（链表），并释放该线性表在程序中所占用的内存空间。
以上操作为线性表的基本操作，你也可以自己封装一些如按值查找、求表长等操作。
2.2 顺序表
2.2.1 顺序表的定义
顺序表：顺序存储的线性表。
顺序存储就是将数据存储到一片连续的内存中，在C语言中，你也可以将数组当成顺序表，数组就是一种常见的顺序表。
2.2.2 顺序表的基本操作
顺序表设计
下面由我们来设计顺序表：
（1）定义管理结构体
一般而言，为了方便操作顺序表，需要一个专门管理顺序表的”管理结构体“，管理结构体中一般会包含：顺序表的总容量（数据域），顺序表的下标。
typedef 的作用是将定义这个结构体可以区别名，在此结构体我取了别名*p_list，则后续定义结构体指针可以简略写出成p_list plist
typedef struct seq_list {
//数据域
int data[5];
//下标域
int n;
}*p_list;
（2）初始化顺序表
所谓初始化就是建立一个不包含任何元素的顺序表，设置好管理结构体中的表的总容量、末元素下标等系列准备工作。
void init_list(p_list plist){
//清空数据域
plist->data[0] = 0;
plist->data[1] = 0;
plist->data[2] = 0;
plist->data[3] = 0;
plist->data[4] = 0;
//设置下标域-1 数组是下标0开始存数据
plist->n = -1;
}
（3）插入数据进顺序表
//插入数据---头插
void insert_head_to_list(struct seq_list *plist,int i_data)
{
//顺序表是否已满
if(plist->n == 4)
{
printf("list is full\n");
return;
}
//未满就插入新的数据
//给新数据腾位置---把已有的数据向后移动一个位置
(plist->n)++;//下标加1
for(int i =(plist->n);i>0;i--)
{
plist->data[i] = plist->data[i-1];
}
//放入新的数据
plist->data[0] = i_data;
}
（4）删除数据
//删除目标数据
void del_data_from_list(p_list plist,int i_data)
{
//检测顺序表是否为空
if(plist->n == -1)
{
printf("list is empty\n");
return;
}
//定位---找到目标数据的位置
int pos = -1;//保存目标数据所在的下标
for(int i=0;i<=(plist->n);i++)
{
if(plist->data[i]== i_data)
{
pos = i;
break;
}
}
if(pos == -1)
{
printf("no this data\n");
return;
}
//2.删除---移位覆盖删除法
for(int i = pos;i<(plist->n);i++)
{
plist->data[i] = plist->data[i+1];
}
plist->data[plist->n] = 0;//将删除的值清0
(plist->n)--;//下标往前移动一位
}
（5）遍历顺序表
当你想要对插入或删除的结果遍历输出时，可以参考以下代码
//遍历输出
void show_list(p_list plist)
{
//如果顺序表为空，给提示信息
if(plist == NULL){
printf("list is NULL");
return;
}
//否则遍历循序表
for(int i=0;i<=(plist->n);i++)
{
printf("%d ",plist->data[i]);
}
printf("\n");
}
在主函数中使用函数接口：
在主函数中，我们定义了一个mylist顺序表，并对其进行初始化，写了一个对顺序表进行插入和删除的while循环，在程序中我们可以输入0或者按住Ctrl+C就可以退出对顺序表的操作，如果我们输出一个数，进行插入操作并遍历输出，反之输出这个数的相反数则进行删除操作并遍历输出，你也可以设计自己更利于理解的方法。
int main(){
int i_data = 0;
//定义一个顺序表
list mylist;
//初始化
init_list(&mylist);
//操作 大于0 插入数据 小于 0 删除 这个数绝对值
while(1)
{
scanf("%d",&i_data);//输入目标数据
if(i_data > 0)
{
//insert_tail_to_list(&mylist,i_data);//尾插
insert_head_to_list(&mylist,i_data);//头插
}
if(i_data < 0)
{
del_data_from_list(&mylist,-i_data);//删除
}
if(i_data == 0)
{
break;
}
show_list(&mylist);//遍历打印
}
}
操作结果：
2.3 链式表
（重点！！！！！）
2.3.1 链表的定义
顺序存储中的数据因为挤在一起而导致需要成片移动，那很容易想到的解决方案是将数据离散地存储在不同内存块中，然后在用来指针将它们串起来。在逻辑上他们是线性存储的，这种朴素的思路所形成的链式线性表，就是所谓的链表。
顺序表和链表在内存在的基本样态如下图所示：
逻辑上是线性存储，用图可以这样理解，用一条条线串起来组成他们的关系，其中的线一般都是指针，它在内存中的存储是不一定连续的。
单向链表
2.3.2 链表的分类
根据链表中各个节点之间使用指针的个数，以及首尾节点是否相连，可以将链表细分为如下种类：
- 单向链表
- 单向循环链表
- 双向链表
- 双向循环链表
这些不同链表的操作都是差不多的，只是指针数目的异同。以最简单的单向链表为例，其基本示意图如下所示：
2.3.3 单向链表
顾名思义，单向链表即只有一个头结点，以及指向下一个结点的指针。
上图中，所有的节点均保存一个指针，指向其逻辑上相邻的下一个节点（末尾节点指向空）。另外注意到，整条链表用一个所谓的头指针 head 来指向，由 head 开始可以找到链表中的任意一个节点。head 通常被称为头指针。
链表的基本操作，一般包括：
- 节点设计
- 初始化链表节点
- 增删查改节点
- 链表遍历
- 销毁链表
下面着重针对这几项常见操作，讲解单向链表的处理。
2.3.3.1 结点设计
我们将定义一个单向链表的管理结构体，通常包含数据域和指针域，在后续我们对结点进行增删改查等操作通过使用指针域会更方便
管理结构体代码：
typedef struct node{
int data;//数据域
struct node *next;//指针域
}*list;
2.3.3.2 链表的初始化
任何的链表都可以使用无头结点或有头结点的形式，但是一般情况下不推荐使用无头结点的链表，因为在操作的过程中很容易造成断链，即头结点不存放数据。
链表初始化封装函数代码：
//初始化链表
list Init_List(){
list head = malloc(sizeof (list));//为头结点申请内存空间
if(head == NULL){
printf("malloc error");
return NULL;
}//若申请内存空间失败，返回NULL并打印失败信息
//初始化头结点
head->data = 0;
head->next = NULL;
return head;//返回头结点
}
malloc作用：申请内存空间，括号内是内存的大小。
我们对链表进行初始化，首先需要对头结点申请一段内存空间，才能创建链表，然后将头结点的数据清空并让它的指针域指向空，最后将头结点返回即可初始化一个只有头结点的链表。
2.3.3.3 数据的插入
数据的插入有两种方法，一种是头插法，另一种是尾插法，头插法是将数据插入头结点之前，尾插法是将数据插入链表的尾部。
头插法：
我们将新的结点指向头结点的下一个结点，并将头结点与旧结点断开，指向新的结点。
注意（重点）：头插法插入必须先指向头结点的后继结点，才能将头结点指向新结点！！顺序不能调换！！（俗称：先建立新关系，再断开旧关系）
代码实现：
//头插法
int Insert_node(list head,int data){
list new = malloc(sizeof (struct node));//为新结点申请内存空间
new->data = data;//将插入的数据给进新结点的数据域
if(head == NULL)
{
printf("malloc error!\n");
return -1;//申请内存空间失败
}
new->next = head->next;//建立新关系
head->next = new;//断开旧关系
return 1;//插入成功
}
尾插法：
顾名思义，将数据结点插入到链表的最后一个位置，这个操作我们需要遍历整个链表，才能将数据结点插入，其方法跟头插法大同小异，只不过需要遍历链表。
//尾插法
int Insert_node_back(list head,int data){
list new = malloc(sizeof (list));//为新结点申请内存空间
if(head == NULL){
printf("malloc error!\n");
return -1;//申请内存空间失败
}
new->data = data;//将插入的数据给进新结点的数据域
list p = head;//建立一个结点p指向
while(p->next!=NULL){
p = p->next;
}//遍历整个链表
new->next = NULL;//建立新关系
p->next = new;//断开旧关系
return 1;//插入成功
}
2.3.3.4 数据的删除
结点删除的步骤：
1.判断链表是否为空
2.定位
3.删除节点关系
4.释放空间
删除结点代码实现：
//删除目标数据
int del_data_list(list head,int data){
//检测链表是否为空
if(head->next == NULL)
{
printf("list is empty\n");
return 0;
}
//定位---找到目标数据的位置
list pos = NULL;
list temp = NULL;
for(pos = head;pos->next!=NULL;pos = pos->next )
{
if((pos->next)->data == data)
{
temp = pos->next;//要删除的目标节点
break;
}
}
//判断是否找到目标节点
if(pos->next==NULL)
{
printf("no this node\n");
return -1;
}
//删除关系
pos->next = temp->next;
temp->next = NULL;
//释放节点空间
free(temp);
return 1;
}
注意定位的时候需要遍历链表才能找到需要删除的数据结点，这也是链表的缺点。
2.3.3.5 销毁链表
只需要将链表遍历并释放每个结点即可销毁链表，使用完链表后一般都要将其销毁并释放内存空间，否则容易出现内存泄漏等问题。
// 销毁链表
void Destroy_list(struct node *head) {
struct node *temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}
链表的操作结果与如上顺序表类似，可参考顺序表操作结果
其他链表我将在下一章节进行一一讲解。
标签：结点,线性表,list,head,链表,算法,数据结构,data,plist From： https://blog.csdn.net/sinat_39377093/article/details/140573082