数据结构 | 线性表

 🔥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);//链表打印
}