数据结构 | 线性表

news/2024/11/9 2:00:49/

 🔥Go for it!🔥
📝个人主页：按键难防
📫 如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步👀

📖系列专栏：数据结构与算法
🔥 如果感觉博主的文章还不错的话，还请 点赞👍🏻收藏⭐️ + 留言📝​支持 一下博主哦

目录

​​​​​​​​​​​​​​一.线性表

①顺序表(顺序存储)

具体操作

1.顺序表插入元素：

2.顺序表删除元素： 

3.遍历查找（按值）：

②链表（链式存储）

1.单链表

①单链表定义：

②头插法：

③尾插法：

具体操作

①按位查找（遍历）：

②按值查找：

③插入元素：

④删除操作 

​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​一.线性表

3e8573ac6503453c9c840d6c1fefaa86.png

 定义：由n(n≥0)个相同类型的元素组成的有序集合。（L=a1, a2, … , ai , ai+1, … , an）

线性表中元素个数n，称为线性表的长度。当n=0时，为空表。
a1是唯一的"第一个"数据元素，an是唯一的“最后一个”数据元素。
ai-1为a的直接前驱，ai+1为a的直接后继。


特点：

表中元素的个数是有限的。

表中元素的数据类型都相同。意味着每一个元素占用相同大小的空间
表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后顺序

线性表第一个元素的位序是1，下标是0。

线性表是逻辑结构，表示元素之间一对一的相邻关系，用存储结构实现线性表就是顺序表或链表。

​​​​​​​​​​​​​​

a925b9a606f848fd8cfa60a35fc533df.png

①顺序表(顺序存储)

用顺序存储的方式实现线性表

定义方法（静态版本）：

#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;
}

 b2d31c8d248b4d51a211061fd8de8992.png

bf48b7f6a8a840be9b9de2357588e6e4.png

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;
}

 336ad493e77240e682ade1ed79001372.png561cc26c4e304e99a1dee029c644b9d7.png

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;
}

160dc2eef2c64c3788f32d59cfce7666.png

动态版本：

#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创建变量，就是指向这个结构体的指针

②头插法：

1b16993672c146a0b3f3ab4d3864250e.jpeg

 重点在灵活变化头结点的指针域，插进来一个，我就把头结点指针域原值赋给插进来结点的指针域，然后头结点的指针域改为新插进来结点的指针。

#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;
}

③尾插法：

44d56d1b9ad84b564a33cc8a502ae699.jpeg

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


http://www.ppmy.cn/news/24077.html

相关文章

Git | 在IDEA中使用Git

Git | 在IDEA中使用Git

目录 一、在IDEA中配置Git 1.1 配置Git 1.2 获取Git仓库 1.3 将本地项目推送到远程仓库 1.4 .gitignore文件的作用 二、本地仓库操作 2.1 将文件加入暂存区 2.2 将暂存区的文件提交到版本库 2.3 查看日志 三、远程仓库操作 3.1 查看和添加远程仓库 3.2 推送至远程仓…
阅读更多...
第01章_数据库概述

第01章_数据库概述

第01章_数据库概述 讲师&#xff1a;尚硅谷-宋红康&#xff08;江湖人称&#xff1a;康师傅&#xff09; 官网&#xff1a;http://www.atguigu.com 1. 为什么要使用数据库 持久化(persistence)&#xff1a;把数据保存到可掉电式存储设备中以供之后使用。大多数情况下&#x…
阅读更多...
java ssm集装箱码头TOS系统调度模块的设计与实现

java ssm集装箱码头TOS系统调度模块的设计与实现

由于历史和经济体制的原因&#xff0c;国内码头物流企业依然保持大而全的经营模式。企业自己建码头、场地、经营集装箱运输车辆。不过近几年来随着经济改革的进一步深入和竞争的激烈&#xff0c;一些大型的码头物流企业逐步打破以前的经营模式&#xff0c;其中最明显的特征就是…
阅读更多...
Linux 编译器 gcc/g++

Linux 编译器 gcc/g++

本文已收录至《Linux知识与编程》专栏&#xff01; 作者&#xff1a;ARMCSKGT 演示环境&#xff1a;CentOS 7 目录 前言 正文 gcc/g常用命令 自定义可执行程序名命令-o 预处理指令-E 编译指令-S 汇编指令-c 链接指令gcc 命令巧记口诀 链接库 动态库-动态链接 静态库…
阅读更多...
UDP协议详解

UDP协议详解

目录 前言&#xff1a; 再谈协议 UDP协议 比较知名的校验和 小结&#xff1a; 前言&#xff1a; UDP和TCP作为传输层非常知名的两个协议&#xff0c;那么将数据从应用层到传输层数据是怎样进行打包的&#xff1f;具体都会增加一些什么样的报头&#xff0c;下面内容详细介绍…
阅读更多...
Github | 个人资料自述文件配置的不完全总结

Github | 个人资料自述文件配置的不完全总结

本文简单总结配置 Github 主页上个人资料自述文件的流程和参考文件。 更新&#xff1a;2022 / 02 / 11 Github | 配置个人主页的信息总览方法的不完全总结创建、删除个人资料自述文件编辑个人资料自述文件参考链接创建、删除个人资料自述文件 首推自然是官方说明文档 1&#…
阅读更多...
Python 之 NumPy 简介和创建数组

Python 之 NumPy 简介和创建数组

文章目录一、NumPy 简介1. 为什么要使用 NumPy2. NumPy 数据类型3. NumPy 数组属性4. NumPy 的 ndarray 对象二、numpy.array() 创建数组1. 基础理论2. 基础操作演示3. numpy.array() 参数详解三、numpy.arange() 生成区间数组四、numpy.linspace() 创建等差数列五、numpy.logs…
阅读更多...
2023最详细的接口测试用例设计教程

2023最详细的接口测试用例设计教程

一、接口测试流程 1、需求讨论 2、需求评审 3、场景设计 4、数据准备 5、测试执行 二、分析接口文档元素 1、接口名称 2、接口地址 3、支持格式 4、请求方式 5、请求参数&#xff08;参数名称、类型、是否必填、参数说明等&#xff09; 6、返回参数&#xff08;返回…
阅读更多...
最新文章

Copyright @ 2022~2023