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

🕗 发布于 2024-04-20 15:46 数据结构

文章目录

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

一顺序表

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

代码：

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

#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找到顺序表中最后一个元素置为0
ps->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;
}

}

//找不到返回0
return 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;
//释放掉pos
free(pos);
}
}
// 删除pos之后的结点
void DeleteAfterNode(Node* pos) {
assert(pos && pos->Next);
//要删除pos之后的结点，要将pos->next之后的结点与pos链接起来,再删除pos
Node* 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；
}

原文地址：https://blog.csdn.net/2301_77993957/article/details/137817842

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：微信小程序之自定义组件及使用
下一篇：记录一下易语言post get使用WinHttp的操作

大数据研究实训室建设方案
大数据项目实训平台作为一个通用的项目实训管理系统，具有高度的灵活性和可扩展性，能够根据学校或机构的特定需求进行定制，内置大数据、云计算和人工智能等领域的实训实战课程资源。实训室将专注于培养学生在大数据
阅读更多2024-10-19
ollama上传本地模型到仓库
一定要添加ollama的密钥，不然上传的时候会报错登录上之后找到设置然后加入你电脑上的ollama的key。
阅读更多2024-10-19
通过PHP与API的结合，开启电商数据集成的新篇章
在数字化转型的浪潮中，电子商务数据的集成对于企业来说变得越来越重要。PHP，作为服务端脚本语言的佼佼者，为开发者提供了强大的工具和库来实现与电商API的无缝对接。通过掌握API调用，PHP开发者可以轻
阅读更多2024-10-19
Java爬虫：API接口数据爬取入门详解及示例代码
API接口数据爬取是Java爬虫技术的一个重要应用领域。通过使用Java的HTTP客户端库和数据解析库，我们可以高效地从API接口获取数据，并进行进一步的分析和应用。掌握这些技能，将使你在数据获取和处
阅读更多2024-10-19
VUE传递字符串显示二维码
1.安装插件npm install vue-qrcode2.使用<script setup lang="ts">import { ref } from
阅读更多2024-10-19
智能指针(3)
我们会发现如果使用的是普通的开辟在栈里面的成员变量或者静态的全局变量都是跟着智能指针走的，但是我们的引用计数计数的是一个空间被多少个智能指针管理着，所以这个计数是肯定要跟着被管理的空间走的，以上两种表
阅读更多2024-10-19
C#两个窗体之间传递参数
C#两个窗体之间传递参数
阅读更多2024-10-19
【C#】使用Visual Studio创建Windows Forms应用程序计算对角线之和
118 Pages（2）课后练习题
阅读更多2024-10-19
DFS算法经典题目： Leetcode 51.N皇后
题目详情如下这道题如果使用暴力解法的话，需要对N个皇后放在每个地方都进行枚举并判断是否可行，时间复杂度非常之高，肯定是过不了的，所以需要使用其他解法。根据题目可以知道每两个皇后之间的位置关系不能是在同
阅读更多2024-10-19
Mybatis多对一查询的配置及两种方法的使用示例对比以及Mybatis一对多查询两种方法使用示例及对比
同多对一的查询一样，mapper.xml配置中使用子查询嵌套的方法在SQL执行的时候会进行多次查询，最终查询次数和取得的行数成正比增加。City(id=0, cityname=北京, areaList
阅读更多2024-10-19

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

文章目录

一 顺序表

代码：

二 链表

单链表

双向链表

相关文章

一顺序表

二链表