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

devtools/2024/11/14 12:53:28/

文章目录

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

一 顺序表

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

代码：

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

#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.ppmy.cn/devtools/17886.html

相关文章

Prompt Engineering，提示工程

Prompt Engineering，提示工程

什么是提示工程&#xff1f; 提示工程也叫【指令工程】。 Prompt发送给大模型的指令。比如[讲个笑话]、[用Python编个贪吃蛇游戏]、[给男/女朋友写情书]等看起来简单&#xff0c;但上手简单精通难 [Propmpt]是AGI时代的[编程语言][Propmpt]是AGI时代的[软件工程][提示工程]是…
阅读更多...
Centos 5 的yum源

Centos 5 的yum源

背景 有使用较老的Centos 5 系统内部安装软件无法正常报错&#xff0c;是由于系统叫老yum源存在问题 处理方法 更换下述yum源&#xff0c;可以将其他repo源文件备份移动到其他目录&#xff0c;添加下述源后重新测试 [C5.11-base] nameCentOS-5.11 baseurlhttp://vault.c…
阅读更多...
C#开发-Null的整型数值比较

C#开发-Null的整型数值比较

大家都知道整数类型、浮点数类型、布尔类型比较的规则。这在各个语言中都是通用的。但是有谁知道Null类型和整型比较的结果呢&#xff1f; 我在.NET8.0下编写了这个测试程序来解释Null和整型比较的结果。 int? count null; bool compare1 count > 2; bool compare2 co…
阅读更多...
Linux 内核的汇编级别的系统调用

Linux 内核的汇编级别的系统调用

2024年4月19日&#xff0c;周五下午 Linux 内核支持多种汇编级别的系统调用&#xff0c;这些系统调用通常以软中断&#xff08;soft interrupt&#xff09;的方式实现。 这里列举了一些常见的汇编级别的系统调用&#xff1a; x86 架构下的 int 0x80 调用&#xff1a;在 x86 架…
阅读更多...
抖音小店想要快速出单，必须做好这两点，这也是做店的两大核心。

抖音小店想要快速出单，必须做好这两点，这也是做店的两大核心。

大家好&#xff0c;我是电商糖果 很多刚开店的新手商家&#xff0c;都会发现店铺运营并没有网上说的这么简单。 店铺开好之后&#xff0c;是不会自己爆单的。 但是会有很多人说&#xff0c;为什么别人的店铺就可以很快的出单&#xff0c;然后爆单呢&#xff1f; 那些开电商…
阅读更多...
【学习笔记】

【学习笔记】

如何保护软件模块的定义 将数据定义放在模块xx.c文件中&#xff0c;C库中结构体的封装方法 这种方式的前提是模块xx需要有动态内存分配&#xff0c;通过create的方式&#xff0c;生成变量&#xff1b; 通过结构体共用体的方式[忘记了是哪个视频里看到] 利用的是共用体的思路…
阅读更多...
qt5core.dll怎么下载，qt5core.dll丢失能否修复？

qt5core.dll怎么下载，qt5core.dll丢失能否修复？

qt5core.dll的丢失真是让人头疼。这个Visual C Redistributable for Visual Studio 2015的运行时库被许多程序和游戏所依赖&#xff0c;一旦缺失了qt5core.dll&#xff0c;就会面临无法打开程序或游戏&#xff0c;甚至系统崩溃等一系列问题。 qt5core.dll的消失会带来以下麻烦 …
阅读更多...
《欢乐钓鱼大师》攻略，钓友入坑必备！

《欢乐钓鱼大师》攻略，钓友入坑必备！

欢迎来到《欢乐钓鱼大师》&#xff01;在这个游戏里&#xff0c;你可以尽情享受垂钓的乐趣&#xff0c;通过不断更换和升级高阶鱼竿&#xff0c;轻松地钓到各种稀有鱼类。因为许多玩家在挑战关卡时遇到了一些困难&#xff0c;所以今天我给大家带来了《欢乐钓鱼大师攻略指南》&a…
阅读更多...
最新文章

Copyright @ 2022~2023