王道考研数据结构--3.双链表

news/2024/11/26 7:21:03/

目录

1.前言

2.代码难点

2.1双链表的插入和删除

3.代码函数

3.1双链表结构体定义

3.2双链表初始化函数

3.3双链表插入

3.4双链表节点删除

3.5双链表的遍历

4.全部代码 

1.前言

日期：2023.6.21

书籍：2024年数据结构考研复习指导（王道考研系列）

内容：双链表的实现，结构体定义，初始化，创建新结点，头插和尾插，查询，按位序插入，删除指定节点，输出单链表

2.代码难点

2.1双链表的插入和删除

在p节点后插操作s节点，

上图操作的语句顺序不是唯一的，但也不是任意的，

①和②两步必须在④步之前，

否则p的后继结点的指针就会丢掉，导致插入失败。
为了加深理解，读者可以在纸上画出示意图。

此处①②无顺序要求
若问题改成要求删除结点q的前驱结点*p,请读者思考具体的操作步骤。

3.代码函数

3.1双链表结构体定义

#include <stdio.h>
#include <stdlib.h>//C语言自定义bool操作
#define bool char
#define false 0
#define true 1/*数据元素类型*/
typedef int ElemType;/*双链表结构体定义*/
typedef struct DNode        //定双链表结点类型
{ElemType data;          //每个结点存放一个数据元素struct DNode *next;     //指针指向下一节点struct DNode *prior;    //指针指向上一节点
}DNode,*DLinkList;

3.2双链表初始化函数

/*双链表初始化函数*/
DLinkList DLinkListInit()
{//[1]申请空间DLinkList L = (DLinkList)malloc(sizeof(DLinkList));//[2]安排指针L->next = NULL;L->prior = NULL;//[3]返回头节点return L;
}

3.3双链表插入

/*双链表的插入操作*/
//【1】双链表新节点的创建，返回新节点指针
DNode* CreateNewDNode(ElemType data){//[1]为新节点分配空间,并判断是否分配成功DNode* newNode = (DNode*)malloc(sizeof(DNode));if(!newNode){printf("分配空间失败,请检查内存!\n");return NULL;}//[2]初始化新节点newNode->data = data;newNode->next = NULL;newNode->prior = NULL;//[3]返回节点地址return newNode;
}//【2】双链表节点定位----按位序号查询，返回需要查找的节点的指针
DNode* GetElem(DLinkList L, int i){//[1]判空if(L->next == NULL) {printf("这是空表!"); return L;}//[2]生成指向目标节点的指针pDNode* p = L->next;//[3]如果i = 0if(i < 1){p = L;return p;}//[4]开始循环定位while (p->next != NULL && i != 1){p = p->next;i--;}//[5]返回节点if(i != 1)printf("没有这个节点,返回链表的最后一位.\n");return p;
}//【3】双链表节点定位----按内容值查询，返回需要查找的节点的指针
DNode* LocateElem(DLinkList L,ElemType e){//[1]判空if(L->next == NULL) {printf("这是空表!"); return L;}//[2]生成指向目标节点的指针pDNode* p = L->next;//[3]开始循环定位while (p->next != NULL && p->data != e){p = p->next;}//[4]返回节点if(p->data != e)//排除最后一位元素是目标元素的情况printf("没有这个节点,返回链表的最后一位.");return p;
}//【4】双链表的插入操作
//在第i位插入新元素,如果第i位不存在,则插入在表尾
bool DLinkListInsert(DLinkList L,int i,ElemType e){//[0]程序健壮性增强if(i < 1){printf("输入出错!");return 0;}//[1]建立新元素节点DNode* s = CreateNewDNode(e);if(s == NULL) return 0;//[2]生成指向待插入位置的指针pDNode* p = GetElem(L,i-1);//[3]插入新节点s->next = p->next;if(p->next != NULL)p->next->prior = s;s->prior = p;p->next = s;//[4]插入成功,返回结果return 1;
}

3.4双链表节点删除

//按位删除
bool DLinkLisDelete(DLinkList L,int i){//[1]判空if(L->next == NULL){printf("表空,无删除元素\n");return false;}//[2]定位,找到待删除元素的前一位*p和待删除元素*qDNode* p = GetElem(L,i-1);if(p == NULL) return false;DNode* q = p->next;if(q == NULL) return false; //*p没有后继结点//[3]执行删除操作p->next = q->next;if(q->next != NULL)         //*q不是最后一位元素q->next->prior = p;free(q);return true;//没有q的写法// if(p->next == NULL) false;  //最后一位,没有后继// p->next = p->next->next;// if(p->next->next != NULL)   //待删除结点不是最后一个节点//     p->next->next->prior = p;// free(p);              //释放结点空间// return true;
}
//删除双链表
void DestoryList(DLinkList L){while (L->next != NULL){DLinkLisDelete(L,1);}
}

3.5双链表的遍历

/*双链表的遍历*/
int PrintDLinkList(DLinkList L){//[1]判空if (L == NULL){printf("该链表不存在\n");return 0;}if(L->next == NULL){printf("这是空表!没有需要打印的元素");   return 0;}//[2]生成当前要打印的元素位置的指针pDNode* p = L->next;//[3]遍历打印int i = 0;while (p!= NULL){i++;printf("第%d个元素的内容值为:%d\n",i,p->data);p = p->next;}printf("打印结束,共%d个链表结点.\n",i);return 0;
}

4.完成代码 

#include <stdio.h>
#include <stdlib.h>//C语言自定义bool操作
#define bool char
#define false 0
#define true 1/*数据元素类型*/
typedef int ElemType;/*双链表结构体定义*/
typedef struct DNode{        //定双链表结点类型ElemType data;          //每个结点存放一个数据元素struct DNode *next;     //指针指向下一节点struct DNode *prior;    //指针指向上一节点
}DNode,*DLinkList;/*双链表初始化函数*/
DLinkList DLinkListInit(){//[1]申请空间DLinkList L = (DLinkList)malloc(sizeof(DLinkList));//[2]安排指针L->next = NULL;L->prior = NULL;//[3]返回头节点return L;
}/*双链表的插入操作*/
//【1】双链表新节点的创建，返回新节点指针
DNode* CreateNewDNode(ElemType data){//[1]为新节点分配空间,并判断是否分配成功DNode* newNode = (DNode*)malloc(sizeof(DNode));if(!newNode){printf("分配空间失败,请检查内存!\n");return NULL;}//[2]初始化新节点newNode->data = data;newNode->next = NULL;newNode->prior = NULL;//[3]返回节点地址return newNode;
}
//【2】双链表节点定位----按位序号查询，返回需要查找的节点的指针
DNode* GetElem(DLinkList L, int i){//[1]判空if(L->next == NULL) {printf("这是空表!"); return L;}//[2]生成指向目标节点的指针pDNode* p = L->next;//[3]如果i = 0if(i < 1){p = L;return p;}//[4]开始循环定位while (p->next != NULL && i != 1){p = p->next;i--;}//[5]返回节点if(i != 1)printf("没有这个节点,返回链表的最后一位.\n");return p;
}
//【3】双链表节点定位----按内容值查询，返回需要查找的节点的指针
DNode* LocateElem(DLinkList L,ElemType e){//[1]判空if(L->next == NULL) {printf("这是空表!"); return L;}//[2]生成指向目标节点的指针pDNode* p = L->next;//[3]开始循环定位while (p->next != NULL && p->data != e){p = p->next;}//[4]返回节点if(p->data != e)//排除最后一位元素是目标元素的情况printf("没有这个节点,返回链表的最后一位.");return p;
}
//【4】双链表的插入操作
//在第i位插入新元素,如果第i位不存在,则插入在表尾
bool DLinkListInsert(DLinkList L,int i,ElemType e){//[0]程序健壮性增强if(i < 1){printf("输入出错!");return 0;}//[1]建立新元素节点DNode* s = CreateNewDNode(e);if(s == NULL) return 0;//[2]生成指向待插入位置的指针pDNode* p = GetElem(L,i-1);//[3]插入新节点s->next = p->next;if(p->next != NULL)p->next->prior = s;s->prior = p;p->next = s;//[4]插入成功,返回结果return 1;
}/*双链表的遍历*/
int PrintDLinkList(DLinkList L){//[1]判空if (L == NULL){printf("该链表不存在\n");return 0;}if(L->next == NULL){printf("这是空表!没有需要打印的元素");   return 0;}//[2]生成当前要打印的元素位置的指针pDNode* p = L->next;//[3]遍历打印int i = 0;while (p!= NULL){i++;printf("第%d个元素的内容值为:%d\n",i,p->data);p = p->next;}printf("打印结束,共%d个链表结点.\n",i);return 0;
}/*双链表的删除操作*/
//按位删除
bool DLinkLisDelete(DLinkList L,int i){//[1]判空if(L->next == NULL){printf("表空,无删除元素\n");return false;}//[2]定位,找到待删除元素的前一位*p和待删除元素*qDNode* p = GetElem(L,i-1);if(p == NULL) return false;DNode* q = p->next;if(q == NULL) return false; //*p没有后继结点//[3]执行删除操作p->next = q->next;if(q->next != NULL)         //*q不是最后一位元素q->next->prior = p;free(q);return true;//没有q的写法// if(p->next == NULL) false;  //最后一位,没有后继// p->next = p->next->next;// if(p->next->next != NULL)   //待删除结点不是最后一个节点//     p->next->next->prior = p;// free(p);              //释放结点空间// return true;
}
//删除双链表
void DestoryList(DLinkList L){while (L->next != NULL){DLinkLisDelete(L,1);}
}int main(){//[1]不带头结点的声明定义双链表DLinkList L = NULL;//[2]带头节点的声明定义双链表L = DLinkListInit();//[3]测试:插入结点DLinkListInsert(L,1,1);DLinkListInsert(L,1,2);DLinkListInsert(L,1,3);DLinkListInsert(L,1,4);DLinkListInsert(L,1,5);DLinkListInsert(L,1,6);DLinkListInsert(L,1,7);DLinkListInsert(L,1,8);DLinkListInsert(L,1,9);DLinkListInsert(L,1,10);DLinkListInsert(L,1,11);DLinkListInsert(L,1,12);PrintDLinkList(L);DLinkListInsert(L,4,888);DLinkListInsert(L,7,1022);DLinkListInsert(L,9,963);DLinkListInsert(L,11,8522);DLinkListInsert(L,100,150);DLinkListInsert(L,4,12000);DLinkListInsert(L,8,17869);PrintDLinkList(L);DLinkLisDelete(L,8);PrintDLinkList(L);DestoryList(L);L = NULL;PrintDLinkList(L);// DNode* node = LocateElem(L,150);// printf("Node.data = %d",node->data);
return 0;
}


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

相关文章

Field userService in /UserController required a bean of type‘/UserService‘ that could not be found.

Field userService in /UserController required a bean of type‘/UserService‘ that could not be found.

在UserServiceImpl类上添加注解Service就可以解决问题&#xff0c; 如下&#xff1a; 问题截图&#xff1a; 问题描述&#xff1a; 问题解决&#xff1a; 在UserServiceImpl类上添加注解Service,问题便得以解决。 问题解决&#xff0c;正常运行&#xff1a;
阅读更多...
STM32H7 学习笔记1 QSPI FLASH 失败

STM32H7 学习笔记1 QSPI FLASH 失败

最近学习STM32H7 QSPI的&#xff0c;使用的FLASH为W25Q64JV。 尝试了很多方法(调整驱动函数 ,检查硬件&#xff0c;更换FLASH芯片等)&#xff0c;但是读写操作始终失败&#xff0c;Read ID也全是0x0000. 最后没有办法&#xff0c;无意间看到FLASH的数据手册的电气性能章节。 …
阅读更多...
各类燃料电池模型:包括密歇根大学燃料电池模型，动态模型，模糊控制等

各类燃料电池模型:包括密歇根大学燃料电池模型，动态模型，模糊控制等

各类燃料电池模型:包括密歇根大学燃料电池模型&#xff0c;动态模型&#xff0c;模糊控制等 ID:4366669804638346机智可爱火车侠
阅读更多...
Mybatis保错：Could not find resource com/**/dao/UserMapper.xml

Mybatis保错：Could not find resource com/**/dao/UserMapper.xml

未找到xml配置文件 解决方案&#xff1a; 在核心配置文件里又配置了映射配置文件&#xff08;UserMapper.xml&#xff09;的位置&#xff0c;目的就是在于“告诉”Mybatis&#xff0c;映射配置文件的位置&#xff0c;这样才能找到UserMapper.xml&#xff0c;所以先查看核心配…
阅读更多...
# Mapper method ‘...attempted to return null from a method with a primitive return type(int）SS整合错误

# Mapper method ‘...attempted to return null from a method with a primitive return type(int）SS整合错误

Mapper method …attempted to return null from a method with a primitive return type(int&#xff09;在配置Mybatis出现这个错误 <select id"deleteUserByUsername" parameterType"String" >delete from userinfo where username #{username}…
阅读更多...
OCH147H （霍尔效应锁定传感器）

OCH147H （霍尔效应锁定传感器）

1.概述 OCH147H是一种集成的霍尔效应锁存传感器&#xff0c;设计用于无刷直流电机的电子换向应用。使用高压BCD工艺的装置包括一个用于磁传感的片上霍尔电压发生器、一个放大霍尔电压的比较器和一个用于为噪声抑制提供开关迟滞的施密特触发器&#xff0c;以及一个开集电极输出。…
阅读更多...
智博通 ZBT WG2626原机编程器

智博通 ZBT WG2626原机编程器

智博通 ZBT WG2626原机编程器备份 , 相关下载链接&#xff1a;https://download.csdn.net/download/lt165/20418045?utm_sourcebbsseo
阅读更多...
pytest报错 E ModuleNotFoundError解决办法

pytest报错 E ModuleNotFoundError解决办法

Hint: make sure your test modules/packages have valid Python names. Pytest报错 _____________________________________________________________________________________ ERROR collecting test_panda_1.py _________________________________________________________…
阅读更多...
最新文章

Copyright @ 2022~2023