数据结构- 顺序表-单链表-双链表 --【求个关注!】

2024-04-20 00:04
文章标签 数据结构 顺序 单链 关注 求个 双链

本文主要是介绍数据结构- 顺序表-单链表-双链表 --【求个关注!】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 一 顺序表
    • 代码：
  • 二 链表
    • 单链表
    • 双向链表

一 顺序表

顺序表是线性表的一种
所谓线性表指一串数据的组织存储在逻辑上是线性的，而在物理上不一定是线性的
顺序表的底层实现是数组，其由一群数据类型相同的元素组成，其在逻辑与物理上均是线性的。

代码：

对于顺序表的结构及各种操作函数的声明
在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS 1
#include <assert.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>//顺序表的声明
typedef int Datatype;  //规定顺序表的基本元素是什么类型
struct SeqList {Datatype* arr;   //顺序表空间的首地址int size;        //顺序表中当前元素的个数int capacity;    //顺序表当前所申请的空间个数,单位为数据类型大小
};//初始化一个顺序表的声明
void Initialize(struct SeqList* ps);
// 插入数据操作
//尾插法
void TailInsert(struct SeqList* ps, Datatype x);
//头插法
void HeadInsert(struct SeqList* ps, Datatype x);
//在指定位置插入数据
void RanInsert(struct SeqList* ps, int pos, Datatype x);
//删除数据操作
//头删法
void HeadDelete(struct SeqList* ps);
//尾删法
void TailDelete(struct SeqList* ps);
//在指定位置删除数据
void RanInsert(struct SeqList* ps, int pos);
//查找数据，返回下标
int Select(struct SeqList* ps, Datatype x);//删除顺序表的声明
void DeleteList(struct SeqList* ps);

对于顺序表及各种操作函数的实现：
在这里插入图片描述

#include "seqlist.h"
// 初始化一个顺序表
void Initialize(struct SeqList * ps) {//初始化地址ps->arr = NULL;  //NULL在文件string.h中定义ps->size = ps->capacity = 0;
}
// 判断空间是否够用，不够的话申请空间
void DeterSpace(struct SeqList* ps) {if (ps == NULL) {perror("ps");}if (ps->size == ps->capacity) {// 如果并未分配空间，返回int  exsp = ps->capacity == 0 ? 4 : 2 * ps->capacity;ps->capacity = exsp; //将扩展后的空间大小记录下来Datatype* p1 = NULL;// 扩展空间大小p1 = realloc(ps->arr, exsp * sizeof(Datatype));assert(p1);ps->arr = p1;}}
//尾插法
void TailInsert(struct SeqList* ps, Datatype x) {if (ps == NULL) {perror("ps");}//需要先确定空间是否够用？//如果顺序表中的元素个数等于空间大小，则需要扩展空间--申请原来空间两倍的空间DeterSpace(ps);// 将值插到顺序表末尾ps->arr[ps->size++] = x;}
// 头插法：
void HeadInsert(struct SeqList* ps, Datatype x) {//对于头插法，我们也需要判断空间是否足够用DeterSpace(ps);//在保证了空间之后，将顺序表中数据先往右移动一个元素大小，再进行插入for (int i = ps->size; i > 0; i--) {ps->arr[i] = ps->arr[i - 1];}//空出首地址之后：ps->arr[0] = x;//元素的个数也需要++ps->size++;
}
// 在指定位置插入一个数据
void RanInsert(struct SeqList *ps,int pos,Datatype x) {assert(ps);assert(pos>=0 &&pos<=ps->size -1);//在指定位置插入一个数据可以由 将此位置及此位置以后的数据往后移动一位,然后再将数据插入此位置//在此之前要判断空间是否够用DeterSpace(ps);for (int i = ps->size-1; i >= pos; i--) {ps->arr[i+1] = ps->arr[i]; //将pos在内之后的数据往右移动一位}ps->arr[pos] = x;ps->size++;
}
// 头删法  
// 即删除顺序表中的首个元素
void HeadDelete(struct SeqList* ps) {for (int i = ps->size - 1; i > 0; i++) {ps->arr[i - 1] = ps->arr[i];}ps->arr[ps->size - 1] = 0;ps->size--;
}
// 尾删法  -- 找到最后一个数组元素置为0；
void TailDelete(struct SeqList* ps) {//直接通过ps->size找到顺序表中最后一个元素置为0ps->arr[ps->size - 1] = 0;ps->size--;}
// 删除指定位置的数据 
void RanInsert(struct SeqList*ps,int pos) {//我们删除指定位置的数据后，可以由在此位置之后的数据整体往前移动来实现assert(ps);assert(0 <= pos && pos <= ps->size - 1);//在下标pos之前的数据向前移动for (int i = ps->size - 1; i > pos; i--) {ps->arr[i - 1] = ps->arr[i]; }ps->arr[ps->size - 1] = 0;//将顺序表原来的最后一个元素位置置为0；ps->size--; // 元素个数-1}
// 查找
// 返回相应的下标
int Select(struct SeqList * ps,Datatype x) {assert(ps);for (int i = 0; i < ps->size - 1; i++) {if (ps->arr[i] == x) {return i;}}//找不到返回0return 0;}
// 删除一个顺序表
void DeleteList(struct SeqList* ps) {if (ps == NULL) {exit(1);}free(ps->arr);ps->arr = NULL;//并将元素个数,空间记录清除ps->size = ps->capacity = 0;}

二 链表

链表是线性表的一种
1   链表的逻辑结构是线性的，但其物理存储结构不是线性的。
2   链表的基本元素为结点，结点由数据域与指针域组成，数据域中存放存储的数据，
指针域中存放指向其他结点的指针， 结点之间通过指针互相联系。
链表共有8种（2*2*2）
链表的三种特性分别为：      带头与不带头（ 所谓头即指不携带有效数据的头节点）单向与双向链表循环与不循环（所谓循环即第一个结点与尾结点链接在一起）

链表：

在这里插入图片描述

在这里插入图片描述
最常见的有两种：单链表与双向链表

单链表

单链表的全称是不带头单向不循环链表

我在代码中的注释所写的首节点是可以携带有效数据的，为了避免与头节点混淆，所以我用首节点作为名称，而不是头节点！
在这里插入图片描述

代码：

#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
// 声明单链表结点
// 对链表中数据类型的声明
typedef int Datatype;
typedef struct ListNode {Datatype data;      //结点中的数据struct ListNode* Next;//指向下一个结点的指针
}Node;
//打印链表函数声明
void PrintList(Node* ps);
//创建新结点并赋值的函数声明
Node* CreateNode(Datatype x);
// 插入数据
// 头插
void HeadInsert(Node** phead, Datatype x);
//尾插
void TailInsert(Node** phead, Datatype x);
// 尾删
void TailDelete(Node** phead);
// 头删
void HeadDelete(Node** phead);
// 查找
Node* Select(Node* phead, Datatype x);
// 在指定位置之前插入数据
void RanLeftInsert(Node** phead, Node* pos, Datatype x);
// 在指定位置之后插入数据
// 我们不需要首节点的参数，因为不需要遍历，也不需要在首节点之前插入数据
void RanRightInsert(Node* pos, Datatype x);
// 删除pos位置的结点
void DeleteNode(Node** phead, Node* pos);
// 删除pos之后的结点
void DeleteAfterNode(Node* pos);
// 销毁链表：
void Distory(Node** phead);

在这里插入图片描述
代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//打印链表函数
void PrintList(Node* ps) {while (ps!=NULL) {printf("%d\n", ps->data);ps = ps->Next;}
}
// 创建新结点：
Node* CreateNode(Datatype x) {Node* newnode = (Node*)malloc(sizeof(Node));if (newnode == NULL) {perror("malloc");exit(1);   //退出程序}newnode->data = x;newnode->Next = NULL;return newnode;//返回新结点的指针
}
// 插入数据
// 头插
void HeadInsert(Node ** phead,Datatype x ) {Node* newnode = CreateNode(x);// 将新节点插入到原链表的首部newnode->Next = *phead;// 将新节点即新链表首节点的地址赋给*phead*phead = newnode;
}//尾插
void TailInsert(Node** phead, Datatype x) {//参数为指向 指定链表的首结点 的指针与要插入的数据//如果链表一开始为空，即phead =NULL时，则ptail->Next则有问题，Node* ptail = *phead;if (* phead == NULL) {* phead = CreateNode(x); //在函数调用结束后，函数中的局部变量会被收回，//形参phead值的改变不会影响到实参,如果采用首节点二重指针// 则可以通过形参改变首节点的指针。}else {//先找到尾结点while (ptail->Next != NULL) {ptail = ptail->Next;}//在找到尾结点后，在尾结点后插入新的结点，并赋值ptail->Next = CreateNode(x);}}
// 尾删
void TailDelete(Node**phead) {//链表不能为空assert(phead && *phead);//我们在删除尾结点之后，尾结点之前的指针就变为野指针，我们需要找到此指针并置为空//当链表只有一个结点时：if ((*phead)->Next == NULL) {free(*phead);*phead = NULL;}else {// 创建存放指向尾结点的指针Node* prev = NULL;Node* ptail = *phead;//查找头节点while (ptail->Next) {// ptail->Next !=	NULL;prev = ptail;ptail = ptail->Next;}//在找到尾结点后：free(ptail);ptail = NULL;//将指向尾结点的指针置为空prev->Next = NULL;}
}
// 头删
void HeadDelete(Node **phead) {assert(phead && *phead); //链表不能为空//在删除首节点之后，我们需要能够找到下一个结点的地址Node* next = (*phead)->Next;//->的优先级比*大free(*phead);*phead = next;
}
// 查找
Node* Select(Node* phead, Datatype x) {Node* sel = phead;while (sel) {if (sel->data == x) {return sel;}sel = sel->Next;}
}
// 在指定位置之前插入数据
void RanLeftInsert(Node**phead,Node *pos,Datatype x) {//因为首节点可能会改变，所以用二级指针作为形参，避免用一级指针无法改变链表的首地址//在指定位置之前插入数据的情况只有图中的三种情况，在链表之前，在链表中，在链表最后一个元素之前assert(phead&& *phead);  assert(pos);          //因为pos不能为空，所以*phead也不能为空,否则*phead为空时，也可以进行头插if (pos == *phead) {//pos在首节点处，这相当于头插法HeadInsert(phead, x);}else {//pos位置在链表中与链表最后一个元素上，操作没有本质区别Node* newnode = CreateNode(x);Node* prev = *phead;while (prev->Next!=pos) {prev = prev->Next;}//当找到了pos之前的prev时：newnode->Next = pos;prev->Next = newnode;}
}
// 在指定位置之后插入数据
// 我们不需要首节点的参数，因为不需要遍历，也不需要在首节点之前插入数据
void RanRightInsert(Node * pos,Datatype x) {assert(pos);//我们先创建新结点Node* newnode = CreateNode(x);//将结点插入到pos之后：newnode->Next = pos->Next;pos->Next = newnode;
}
// 删除pos位置的结点
void DeleteNode(Node** phead, Node* pos) {assert(phead && *phead);assert(pos);//在删除pos结点时，我们需要将pos之后的结点与pos之前的结点链接起来，//pos之后的结点可以用pos->next找到,pos之前的结点需要在遍历时，用变量prev保存！if (pos == *phead) {//当pos是首节点时，此时的情况即头删法HeadDelete(phead);}else {Node* prev = *phead;//在采用这条判断语句的前提是：pos不是首结点while (prev->Next != pos) {prev = prev->Next;}//当找到prev时,将pos之后的结点与pos之前的结点链接起来;prev->Next = pos->Next;//释放掉posfree(pos);}
}
// 删除pos之后的结点
void DeleteAfterNode(Node* pos) {assert(pos && pos->Next);//要删除pos之后的结点，要将pos->next之后的结点与pos链接起来,再删除posNode* del = pos->Next;     pos->Next = del->Next;free(del);//难道此时pos->Next的值不会发生变化？del = NULL;// 兄弟们，下面的c打印的值是多少？它的值会不会随着a的变化而变化呢？//int a = 1;//int c = a;// a++;//printf("%d\n",c);}
// 销毁链表：
void Distory(Node **phead) {assert(phead && *phead);Node* pcur = *phead;while (pcur != NULL) {//链表的销毁需要一个结点一个结点的释放Node* next = pcur->Next;free(pcur);pcur = next;}*phead = NULL;}

在这里插入图片描述

双向链表

双向链表的全称是带头双向循环链表

分析图：

在这里插入图片描述
在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS 1
#include<string.h>
#include<assert.h>
#include<stdlib.h>
typedef int Datatype;
//定义双链表结点的格式
typedef struct ListNode {Datatype data;struct ListNode* next;struct ListNode* prev;
}ListNode;
//函数操作的声明：
// 创建结点
void CreateNode(Datatype x);
// 打印链表：
void PrintList(ListNode* phead);
//初始化链表
void Initialize(ListNode** phead);
//插入数据操作
// 尾插法：
// 我们不需要改变头节点，所以用一级指针作为形参即可
void TailInsert(ListNode* phead, Datatype x);
//头插法
void HeadInsert(ListNode* phead, Datatype x);
// 尾删法
void TailDelete(ListNode* phead);
//头删：
void HeadDelete(ListNode* phead);
// 查找
ListNode* Select(ListNode* phead, Datatype x);
// 在指定位置之后插入数据
ListNode* AfterSelect(ListNode* pos, Datatype x);
//删除指定位置pos节点
//pos的形参是一级而不是二级是因为前面的函数形参皆是一级指针 ，这样保证了接口的一致性，确保了
//                                                    他人的方便调用与解读。
void DeleteNode(ListNode* pos, ListNode* phead);
//销毁链表：
void Distory(ListNode* phead);

在这里插入图片描述

#include"List.h"// 打印链表：
void PrintList(ListNode *phead){//我们遍历双向链表的条件是什么？//我们能够找到判断条件是因为，我们知道双向链表从哪里开始到哪里结束是一个循环，我们只是把自己所知道的//用符号的形式表述出来，这是一种能力！ListNode* p1 = phead->next;while(p1 !=phead) {printf("%d\n", p1->data);p1 = p1->next;}
}
//初始化链表
//因为双向链表是带头的【即有头节点】,所以需要先为链表创建一个头节点
void Initialize(ListNode ** phead) {*phead = CreateNode(-1);//创建头节点并随便赋值为1}
//创建新节点并赋值函数
ListNode * CreateNode(Datatype x) {ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));newnode->data = x;
//既然双向链表是循环的，我们在创建结点时，可以先使其自循环！newnode->next = newnode;newnode->prev = newnode;return newnode;	
}
//插入数据操作
// 尾插法：
// 我们不需要改变头节点，所以用一级指针作为形参即可
void TailInsert(ListNode * phead,Datatype x) {ListNode* newnode = CreateNode(x);//创建一个新结点//用phead->prev即可找到尾结点//找到后phead->prev->next = newnode;//将新节点插入到链表尾部newnode->next = phead;newnode->prev = phead->prev; phead->prev = newnode;}
//头插法
void HeadInsert(ListNode* phead, Datatype x) {ListNode* newnode = CreateNode(x);//指针先动谁？//先操作phead->next指向的结点//如果先操作phead结点，则在将phead->next指向新节点后，后面的链表部分就找不到位置了//头插法最多动4个指针：头节点的next,原来第二个结点(可能没有)的prev，新节点的prev与next指针newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;}
// 尾删法
void TailDelete(ListNode * phead) {// 尾删首先要找到尾结点，然后安排好相应的结点//这是判断链表有效，必须有头节点assert(phead);//这是判断链表不能为空，否则无法删除assert(phead->next!=phead);// phead del del->prev //涉及的节点ListNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;// 删除del节点free(del);del = NULL;}
//头删：
void HeadDelete(ListNode* phead) {assert(phead && phead->next != phead);ListNode* del = phead->next;del->next->prev = phead;
// 删除节点free(del);del = NULL;}
// 查找
ListNode* Select(ListNode* phead,Datatype x) {ListNode* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}//没有找到return NULL;
}
// 在指定位置之后插入数据
ListNode* AfterSelect(ListNode* pos, Datatype x) {assert(pos);ListNode* newnode = CreateNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}
//删除指定位置pos节点
//pos的形参是一级而不是二级是因为前面的函数形参皆是一级指针 ，这样保证了接口的一致性，确保了
//                                                    他人的方便调用与解读。
void DeleteNode(ListNode * pos,ListNode* phead) {assert(pos && pos != phead);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
//销毁链表：
void Distory(ListNode*phead) {assert(phead);ListNode* pcur = (phead)->next;while (pcur != NULL) {ListNode* next = pcur->next;free(pcur);pcur = next;}// 此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL; //为了接口的一致性，不将形参改为ListNode**类型，//则需要在调用函数后，再将实参赋值为NULL；
}

这篇关于数据结构- 顺序表-单链表-双链表 --【求个关注!】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/918796。

相关文章

C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
Spring Boot 配置文件之类型、加载顺序与最佳实践记录

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio
阅读更多...
Python中顺序结构和循环结构示例代码

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》：本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句（1）条件语句的定义（2）条件语句的语法（a）单分支 if（b）双分支 if-else（
阅读更多...
关于Spring @Bean 相同加载顺序不同结果不同的问题记录

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
C++实现封装的顺序表的操作与实践

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表
阅读更多...
使用C++实现单链表的操作与实践

使用C++实现单链表的操作与实践

《使用C++实现单链表的操作与实践》在程序设计中,链表是一种常见的数据结构,特别是在动态数据管理、频繁插入和删除元素的场景中,链表相比于数组,具有更高的灵活性和高效性,尤其是在需要频繁修改数据结构的应... 目录一、单链表的基本概念二、单链表类的设计1. 节点的定义2. 链表的类定义三、单链表的操作实现四、
阅读更多...
JAVA利用顺序表实现“杨辉三角”的思路及代码示例

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,：本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一：“杨辉三角”题目链接二：题解代码：三：题解思路：总结一：“杨辉三角”题目链接题目链接：点击这里
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2