数据结构 | 线性表
🔥Go for it!🔥
📝个人主页：按键难防
📫 如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步👀📖系列专栏：数据结构与算法
🔥 如果感觉博主的文章还不错的话，还请 点赞👍🏻收藏⭐️ + 留言📝支持 一下博主哦
目录
一.线性表
①顺序表(顺序存储)
具体操作
1.顺序表插入元素：
2.顺序表删除元素：
3.遍历查找（按值）：
②链表（链式存储）
1.单链表
①单链表定义：
②头插法：
③尾插法：
具体操作
①按位查找（遍历）：
②按值查找：
③插入元素：
④删除操作
一.线性表
定义：由n(n≥0)个相同类型的元素组成的有序集合。（L=a1, a2, … , ai , ai+1, … , an）
线性表中元素个数n，称为线性表的长度。当n=0时，为空表。
a1是唯一的"第一个"数据元素，an是唯一的“最后一个”数据元素。
ai-1为a的直接前驱，ai+1为a的直接后继。
特点：
表中元素的个数是有限的。
表中元素的数据类型都相同。意味着每一个元素占用相同大小的空间
表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后顺序
线性表第一个元素的位序是1，下标是0。
线性表是逻辑结构，表示元素之间一对一的相邻关系，用存储结构实现线性表就是顺序表或链表。
①顺序表(顺序存储)
用顺序存储的方式实现线性表
定义方法（静态版本）：
#define MaxSize 50 //定义线性表的长度
typedef int ElemType;//重定义线性表中每个元素的类型，便于修改
typedef struct{ElemType data[MaxSize];//顺序表int len;//记录顺序表的当前长度
}SqList;//顺序表的类型定义优点：可以随机存取（根据表头元素地址和序号）表中任意一个元素。存储密度高，每个结点只存储数据元素。
缺点： 插入和删除操作需要移动大量元素。线性表变化较大时，难以确定存储空间的容量。存储分配需要一整段连续的存储空间，不路灵活。
具体操作
1.顺序表插入元素：
#define MaxSize 50 //定义线性表的长度
typedef int ElemType;//重定义线性表中每个元素的类型，便于修改
typedef struct{ElemType data[MaxSize];//顺序表int len;//记录顺序表的当前长度
}SqList;//顺序表的类型定义
bool ListInsert(SqList &L, int i, ElemType e)
{//判断i的范围是否有效if (i<1 || i>L.len + 1){return false;}if (L.len>MaxSize) //当前存储空间已满，不能插入 {return false;}for (int j = L.len; j >= i; j--){ //将第i个元素及其之后的元素后移L.data[j] = L.data[j - 1];}L.data[i - 1] = e; //在位置i处放入eL.len++; //长度加1return true;
}
void PrintfList(SqList L)
{int i =0;for (i = 0; i < L.len; i++){printf("%d",L.data[i]);}printf("\n");
}
int main()
{SqList L;bool ret;//布尔类型返回值L.data[0] = 1;L.data[1] = 2;L.data[2] = 3;L.data[3] = 4;L.data[4] = 5;L.len = 5;//记录顺序表的当前长度ret = ListInsert(L,2,60);//在第二个元素位置插入60if (ret){printf("插入成功\n");PrintfList(L);}else{printf("插入失败\n");}return 0;
} 
2.顺序表删除元素：
#include<stdio.h>
#define MaxSize 50 //定义线性表的长度
typedef int ElemType;//重定义线性表中每个元素的类型，便于修改
typedef struct{ElemType data[MaxSize];//顺序表int len;//记录顺序表的当前长度
}SqList;//顺序表的类型定义
bool ListDelete(SqList &L, int i, ElemType &e)
{ //&e是为了将删去的值赋给e//判断i的范围是否有效int j = 0;if (i<1 || i>L.len){return false;}e = L.data[i - 1]; //将被删除的元素赋值给efor (j=i; j<=L.len; j++){ //将第i个后的元素前移L.data[j - 1] = L.data[j];}L.len--; //长度减1return true;
}
void PrintfList(SqList L)
{int i =0;for (i = 0; i < L.len; i++){printf("%d",L.data[i]);}printf("\n");
}
int main()
{SqList L;bool ret;//布尔类型返回值L.data[0] = 1;L.data[1] = 2;L.data[2] = 3;L.data[3] = 4;L.data[4] = 5;L.len = 5;//记录顺序表的当前长度ElemType del;//存储删去的元素ret = ListDelete(L,1,del);//删除第一个元素if (ret){printf("删除成功\n");PrintfList(L);}else{printf("删除 失败\n");}return 0;
} 
3.遍历查找（按值）：
#include<stdio.h>
#define MaxSize 50 //定义线性表的长度
typedef int ElemType;//重定义线性表中每个元素的类型，便于修改
typedef struct{ElemType data[MaxSize];//顺序表int len;//记录顺序表的当前长度
}SqList;//顺序表的类型定义
int LocateElem(SqList L, ElemType e)
{int i = 0;for (i = 0; i < L.len; i++)//遍历查找{if (L.data[i] == e)return i + 1;}//数组下标为i的元素值等于e，返回其位序i+1return 0;//退出循环，说明查找失败
}
void PrintfList(SqList L)
{int i = 0;for (i = 0; i < L.len; i++){printf("%d ", L.data[i]);}printf("\n");
}
int main()
{SqList L;int ret;//布尔类型返回值L.data[0] = 1;L.data[1] = 2;L.data[2] = 3;L.data[3] = 60;L.data[4] = 5;L.len = 5;//记录顺序表的当前长度ret = LocateElem(L,60);if (ret){printf("查找成功\n");printf("位序是%d\n", ret);}else{printf("查找失败\n");}return 0;
}
动态版本：
#define MaxSize 50 //定义线性表的长度
typedef struct{ElemType* data;//顺序表的元素int len;//顺序表的当前长度
}SqList;//顺序表的类型定义
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize)
//malloc函数申请一片连续的存储空间，大小为sizeof(ElemType)*InitSize
//用完要用free函数释放原来的内存空间②链表（链式存储）
用链式存储的方式实现线性表。
1.单链表
头指针：链表中第一个结点的存储位置，用来标识单链表。
头结点：在单链表第一个结点之前附加的一个结点，为了操作上的方便。
若链表有头结点，则头指针永远指向头结点，没有头结点则指向第一个结点，不论链表是否为空，头指针均不为空，头指针是链表的必须元素，他标识一个链表.
头结点是为了操作的方便而设立的，其数据域一般为空，或者存放链表的长度，
有头结点后，对在第一结点前插入和删除第一结点的操作就统一了，不需要频繁重置头指针，但头节点不是必须的。
优点：
插入和删除操作不需要移动元素，只需要修改指针。不需要大量的连续存储空间。
缺点：
单链表附加指针域。也存在浪费存储空间的缺点。查找操作时需要从表头开始遍历，依次查找，不能随机
①单链表定义：
typedef int ElemType;//重定义链表表中每个元素的类型，便于修改
typedef struct LNode//定义单链表结点类型
{ElemType data; //数据域struct LNode *next;//指针域，指向下一个结点。
}LNode, *LinkList;
解释：typedef重命名了两个数据类型，
分别是将struct LNode重命名为LNode，将struct LNode*重命名为LinkList
前者是个结构体，后者是个指向该结构体的指针
用LNode创建变量，就是创建一个结构体
用LinkList创建变量，就是指向这个结构体的指针
②头插法：
重点在灵活变化头结点的指针域，插进来一个，我就把头结点指针域原值赋给插进来结点的指针域，然后头结点的指针域改为新插进来结点的指针。
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 50 //定义线性表的长度
typedef int ElemType;//重定义链表表中每个元素的类型，便于修改
typedef struct LNode//定义单链表结点类型
{ElemType data; //数据域struct LNode* next;//指针域，指向下一个结点（结构体)。
}LNode, *LinkList;
LinkList list_head_insert(LinkList &L)
{L = (LinkList)malloc(sizeof(LNode));//用动态内存开辟初始化头指针，指向头结点L->next = NULL;ElemType x;//头结点不存数据,随机初始化即可scanf("%d", &x);LinkList s;//结构体指针，用来指向申请的新节点swhile (x!= 9999)//输入9999停止{s = (LinkList)malloc(sizeof(LNode));//为新节点申请空间s->data = x;//存数据s->next = L->next;L->next = s;//将插入的节点与头节点连接起来scanf("%d", &x);}return L;//链表建立完毕，返回头指针
}
void printf_list(LinkList L)
{L=L->next;while (L!= NULL){printf("%3d ", L->data);L=L->next;}printf("\n");
}
int main()
{LinkList L;//L是链表头指针，此时没初始化，还没指向头结点list_head_insert(L);printf_list(L);//链表打印return 0;
}③尾插法：
r一直在充当中转站的角色。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{ElemType data;struct LNode *next;//指向下一个结点
}LNode, *LinkList;
//尾插法新建链表
LinkList list_tail_insert(LinkList &L)
{L = (LinkList)malloc(sizeof(LNode));//带头节点的链表L->next = NULL;ElemType x;scanf("%d", &x);LinkList s, r = L;//s是指向新结点，r始终指向链表尾部。while (x != 9999){s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;//让尾部结点指向新结点r = s;//r=s是确保r指向的是新的表尾结点scanf("%d", &x);}r->next = NULL;//尾结点的 next 指针赋值为 NULLreturn L;
}
//打印链表中每个结点的值
void print_list(LinkList L)
{L = L->next;while (L != NULL){printf("%3d ", L->data);//打印当前结点数据L = L->next;//指向下一个结点}printf("\n");
}
int main()
{LinkList L;//链表头，是结构体指针类型list_tail_insert(L);//输入数据可以为 3 4 5 6 7 9999print_list(L);//链表打印return 0;
}具体操作
①按位查找（遍历）：
单链表只能从前往后查找
L的位置是0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int ElemType;
typedef struct LNode
{ElemType data;struct LNode *next;//指向下一个结点
}LNode, *LinkList;
//尾插法新建链表
LinkList list_tail_insert(LinkList &L)
{L = (LinkList)malloc(sizeof(LNode));//带头节点的链表L->next = NULL;ElemType x;scanf("%d", &x);LinkList s, r = L;//s是指向新结点，r始终指向链表尾部。while (x != 9999){s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;//让尾部结点指向新结点r = s;//r 指向新的表尾结点scanf("%d", &x);}r->next = NULL;//尾结点的 next 指针赋值为 NULLreturn L;
}
//打印链表中每个结点的值
void print_list(LinkList L)
{L = L->next;while (L != NULL){printf("%3d ", L->data);//打印当前结点数据L = L->next;//指向下一个结点}printf("\n");
}
LinkList GetElem(LinkList L, int i)
{int j = 0; if (i < 0){return NULL;} for(j=0; L&&j<i;j++){L =L->next;}return L;//返回查找到的结点
}
int main()
{LinkList L, search;//链表头，是结构体指针类型list_tail_insert(L);print_list(L);//链表打印search = GetElem(L, 2);if (search != NULL){printf("按序号查找成功\n");printf("该序号的值为%d\n", search->data);return 0;}
}②按值查找：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int ElemType;
typedef struct LNode
{ElemType data;struct LNode *next;//指向下一个结点
}LNode, *LinkList;
//尾插法新建链表
LinkList list_tail_insert(LinkList &L)
{L = (LinkList)malloc(sizeof(LNode));//带头节点的链表L->next = NULL;ElemType x;scanf("%d", &x);LinkList s, r = L;//s是指向新结点，r始终指向链表尾部。while (x != 9999){s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;//让尾部结点指向新结点r = s;//r 指向新的表尾结点scanf("%d", &x);}r->next = NULL;//尾结点的 next 指针赋值为 NULLreturn L;
}
//打印链表中每个结点的值
void print_list(LinkList L)
{L = L->next;while (L != NULL){printf("%3d ", L->data);//打印当前结点数据L = L->next;//指向下一个结点}printf("\n");
}
LinkList LocateElem(LinkList L, ElemType e)
{while (L){if (L->data == e)//如果相等直接返回那个结点{return L;}L = L->next;}
}
int main()
{LinkList L, search;//链表头，是结构体指针类型list_tail_insert(L);print_list(L);//链表打印search = LocateElem(L, 6);//按值查询if (search != NULL){printf("按值查找成功\n");printf("%d\n", search->data);}
}③插入元素：
在第i个节点插入某元素，那我就借助先按位查找到第i-1个节点，然后将i-1的指针域赋给要插入的指针域，将i-1节点的指针域改为新插入节点的位置
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int ElemType;
typedef struct LNode
{ElemType data;struct LNode *next;//指向下一个结点
}LNode, *LinkList;
//尾插法新建链表
LinkList list_tail_insert(LinkList &L)
{L = (LinkList)malloc(sizeof(LNode));//带头节点的链表L->next = NULL;ElemType x;scanf("%d", &x);LinkList s, r = L;//s是指向新结点，r始终指向链表尾部。while (x != 9999){s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;//让尾部结点指向新结点r = s;//r 指向新的表尾结点scanf("%d", &x);}r->next = NULL;//尾结点的 next 指针赋值为 NULLreturn L;
}
//打印链表中每个结点的值
void print_list(LinkList L)
{L = L->next;while (L != NULL){printf("%3d ", L->data);//打印当前结点数据L = L->next;//指向下一个结点}printf("\n");
}
//按位查找
LinkList GetElem(LinkList L, int i)
{int j = 0;if (i < 0){return NULL;}for(j=0; L&&j<i;j++){L =L->next;}return L;//返回查找到的结点
}
//插入操作
bool ListFrontInsert(LinkList L, int i, ElemType e)
{LinkList p = GetElem(L, i - 1);if (NULL == p){return false;}LinkList s = (LNode*)malloc(sizeof(LNode));//为新插入的结点申请空间s->data = e;s->next = p->next;p->next = s;return true;
}
int main()
{LinkList L, search;//链表头，是结构体指针类型list_tail_insert(L);print_list(L);//链表打印ListFrontInsert(L, 2, 99);//新结点插入第2个位置,值为99print_list(L);
}④删除操作
删除第i个节点，借助按位查找找到第i-1个，然后将该节点的指针域赋给中间变量，便于后续释放，然后将第i个节点的指针域赋给i-1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int ElemType;
typedef struct LNode
{ElemType data;struct LNode *next;//指向下一个结点
}LNode, *LinkList;
//尾插法新建链表
LinkList list_tail_insert(LinkList &L)
{L = (LinkList)malloc(sizeof(LNode));//带头节点的链表L->next = NULL;ElemType x;scanf("%d", &x);LinkList s, r = L;//s是指向新结点，r始终指向链表尾部。while (x != 9999){s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;//让尾部结点指向新结点r = s;//r 指向新的表尾结点scanf("%d", &x);}r->next = NULL;//尾结点的 next 指针赋值为 NULLreturn L;
}
//打印链表中每个结点的值
void print_list(LinkList L)
{L = L->next;while (L != NULL){printf("%3d ", L->data);//打印当前结点数据L = L->next;//指向下一个结点}printf("\n");
}
//按位查找
LinkList GetElem(LinkList L, int i)
{int j = 0;if (i < 0){return NULL;}for(j=0; L&&j<i;j++){L =L->next;}return L;//返回查找到的结点
}
//删除操作
bool ListFrontInsert(LinkList L, int i, ElemType e)
{LinkList p = GetElem(L, i - 1);if (NULL == p){return false;}LinkList q;//用来存储删除的节点，便于释放动态空间q=p->next;p->next=q->next;//断链free（q）//释放对应节点的空间return true;
}
int main()
{LinkList L, search;//链表头，是结构体指针类型list_tail_insert(L);print_list(L);//链表打印ListDelete(L,4);print_list(L);//链表打印
}