建设银行手机银行下载官方网站下载,百度影响力排名顺序,网站开发要怎么学,网站开发的心得目录
一、双向链表的基本概念
二、双向链表的结构
三、双向链表的基本操作实现方法
1.双向链表的初始化
2.双向链表的头插
3.双向链表的尾插
6.查找节点
7.在指定位置之前插入节点
8.删除指定位置节点
9.打印链表数据 10.双向链表销毁
四、完整代码实现
…目录
一、双向链表的基本概念
二、双向链表的结构
三、双向链表的基本操作实现方法
1.双向链表的初始化
2.双向链表的头插
3.双向链表的尾插
6.查找节点
7.在指定位置之前插入节点
8.删除指定位置节点
9.打印链表数据 10.双向链表销毁
四、完整代码实现
LIst.h
List.c 博客主页C-SDN花园GGbond ⏩ 文章专栏探索数据结构与算法 一、双向链表的基本概念 双向链表是一种常见的数据结构与单向链表类似但它允许我们从两个方向遍历链表向前和向后。每个节点包含三个部分一个数据元素和两个指针一个指向链表中的前一个节点另一个指向链表中的下一个节点。 一般情况下我们所说的双向链表指的是带头节点双向循环链表以下若无特殊说明均代表此含义。 二、双向链表的结构 双向链表中的每个节点通常包含以下部分 数据元素可以是任何类型的数据如整数、浮点数、字符串或对象。prev 指针指向前一个节点的指针。next 指针指向下一个节点的指针。相比单链表只有独立存在的每个节点双向链表多了哨兵位节点该节点作为头结点不存储有效数据只有指向第一个有效节点的next指针和指向尾节点的prev指针。 只要链表存在哨兵位节点就存在 相比单链表只有独立存在的每个节点双向链表多了哨兵位节点该节点作为头结点不存储有效数据只有指向第一个有效节点的next指针和指向尾节点的prev指针。 只要链表存在哨兵位节点就存在
三、双向链表的基本操作实现方法 初始化顺序表中的数据。对顺序表进行头插(开头插入数据)。对顺序表进行尾插插(末尾插入数据)。对顺序表进行头删(开头删除数据)。对顺序表进行尾删(末尾删除数据)。对顺序表进行查找。7.在指定位置之前插入节点删除指定位置节点。打印顺序表中的数据。.双向链表销毁 1.双向链表的初始化
双向链表的初始化也就是创建一个哨兵位节点所以实现初始化之前需要先封装一个节点申请函数 单独封装的申请节点函数 动态申请节点大小的空间判空通过形参接受的数据初始化节点数据部分next指针和prev指针都指向自身因为双向链表是循环链表返回节点地址 LTNode* NewNode(LTDataType x)//申请节点
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(NewNode\n);exit(1);}newnode-data x;//根据参数初始化数据newnode-next newnode-prev newnode;//两个指针初始都指向自身return newnode;
} 双向链表初始化 调用申请节点函数创建一个哨兵位节点作为链表的头结点返回链表头结点地址 注意 双向链表因为有哨兵位的存在链表始终不为空哨兵位节点不会被改变所以不再需要传递地址以及用二级指针接收。这一点区别于单链表实现 LTNode* LTInit() //链表初始化
{LTNode* newnode NewNode(-1);return newnode;
}
2.双向链表的头插 双向链表头插 头插就是将新节点插入到哨兵位节点和第一个有效节点之间形参接收一个哨兵位地址和要插入的数据首先对哨兵位地址判空判断链表结构是否正常 申请新节点存入要插入的数据 接下来是移动指针 一般情况下应当先调整新节点的指针因为新节点指针调整不会影响到原链表: 新节点prev指向哨兵位next指向哨兵位的next所指向节点 然后调整第一个有效节点的prev指针不再指向哨兵位而是指向新节点调整哨兵位 next指针不再指向原来的第一个有效节点而是指向新节点 新节点插入完成 void LTPushFront(LTNode* phead, LTDataType x)//头插
{assert(phead);//判空LTNode* newnode NewNode(x);//申请节点newnode-next phead-next;//改变新节点指针指向newnode-prev phead;phead-next-prev newnode;//改变原链表相关节点指针指向phead-next newnode;} 3.双向链表的尾插 双向链表尾删 尾删就是将双向链表的最后一个有效节点删除尾删的前提是至少存在一个有效节点首先创建一个指针del指向要删除的节点哨兵位prev指向节点然后将倒数第二个节点的next指针指向哨兵位将哨兵位的prev指针指向倒数第二个节点指针修改完成此时倒数第二个节点成为最后一个节点释放del指向的节点如果删除之前链表只有一个节点删除完之后只剩下一个哨兵位节点两个指针都指向自己 void LTPopBack(LTNode* phead) //尾删
{assert(phead phead-next ! phead);//判空LTNode* del phead-prev;//暂时存储要删除的节点del-prev-next phead;//移动指针phead-prev del-prev;free(del);//释放节点空间del NULL;
}
4.双向链表的头删 双向链表头删 头删就是将双向链表第一个有效节点删除头删的前提是链表至少存在一个有效节点首先创建一个指针del指向要删除的节点哨兵位节点next指向的节点然后将第二个有效节点的prev指针指向哨兵位节点哨兵位节点的next指针指向第二个有效节点指针修改完成此时第二个有效节点成为链表的第一个有效节点释放del指向的节点如果删除之前链表只有一个节点删除完之后只剩下一个哨兵位节点两个指针都指向自己 void LTPopFront(LTNode* phead) //头删
{assert(phead phead-next ! phead);//判空LTNode* del phead-next;//暂时存储要删除的节点del-next-prev phead;//移动指针phead-next del-next;free(del);//释放节点空间del NULL;
} 5.双向链表的尾删 双向链表尾删 尾删就是将双向链表的最后一个有效节点删除尾删的前提是至少存在一个有效节点首先创建一个指针del指向要删除的节点哨兵位prev指向节点然后将倒数第二个节点的next指针指向哨兵位将哨兵位的prev指针指向倒数第二个节点指针修改完成此时倒数第二个节点成为最后一个节点释放del指向的节点如果删除之前链表只有一个节点删除完之后只剩下一个哨兵位节点两个指针都指向自己 void LTPopBack(LTNode* phead) //尾删
{assert(phead phead-next ! phead);//判空LTNode* del phead-prev;//暂时存储要删除的节点del-prev-next phead;//移动指针phead-prev del-prev;free(del);//释放节点空间del NULL;
} 6.查找节点 双向链表查找根据数据查找节点 首先对哨兵位地址判空否则可能对空地址解引用创建一个遍历链表的指针从第一个有效节点开始将节点数据与要查找的数据进行比对如果相同返回节点地址出循环说明未找到返回NULL LTNode* LTFind(LTNode* phead, LTDataType x)//查找节点
{assert(phead);//判空LTNode* pcur phead-next;//遍历链表的指针while (pcur! phead){if (pcur-data x)return pcur;pcur pcur-next;}return NULL;
}
7.在指定位置之前插入节点 双向链表在指定位置之前插入节点 插入的前提是指定位置存在 申请新节点存入要插入的数据 调整指针: 临时创建一个指针prev指向指定位置节点的perv指向节点 新节点next指针指向指定位置节点prev指针指向prev节点 然后再修改原链表指针: 指定位置节点的prev指针指向新节点prev节点的next指针指向新节点 新节点插入完成 void LTInsert(LTNode* pos, LTDataType x)//在pos位置之前插入数据
{assert(pos);//判空LTNode* newnode NewNode(x);//申请新节点newnode-next pos;//改变新节点指针指向newnode-prev pos-prev;pos-prev-next newnode;//改变原链表相关节点指针指向pos-prev newnode;} 8.删除指定位置节点 双向链表删除指定位置节点 删除指定节点的前提是该节点必须存在首先创建一个指针del指向要删除的节点然后将该节点的前一个结点的next指针指向它的后一个节点后一个节点的prev指针指向他的前一个节点释放该节点如果删除之前链表只有一个节点删除完之后只剩下一个哨兵位节点两个指针都指向自己 void LTErase(LTNode* pos)//删除指定位置节点
{assert(pos);//判空pos-next-prev pos-prev;//改变要删除节点的前后节点指针指向pos-prev-next pos-next;free(pos);pos NULL;} 9.打印链表数据 双向链表数据打印 首先对地址判空防止对空地址解引用创建一个遍历链表的指针从第一个有效节点打印数据然后向后移动直到指针遍历到哨兵位 void LTPrint(LTNode* phead) //链表数据打印
{assert(phead);//判空LTNode* pcur phead-next;//遍历链表的指针while (pcur ! phead)//打印数据{printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
} 10.双向链表销毁 双向链表的销毁 从第一个有效节点开始创建指针循环遍历链表: 创建next指针临时保存下一个节点释放本节点遍历指针指向next节点 循环至有效节点全部被释放 然后将哨兵位节点释放指针置空销毁完成注意 为了与其他配套函数的参数保持一致这里的参数本该用二级指针接收却用一级指针接收。出函数后需要手动将哨兵位指针置空 oid LTDestroy(LTNode* phead)//链表销毁
{assert(phead);//判空LTNode* pcur phead-next;//遍历链表的指针while (pcur ! phead)//从第一个有效节点开始逐个释放节点{LTNode* next pcur-next;free(pcur);pcur next;}free(phead);//释放哨兵位节点phead NULL;}四、完整代码实现
LIst.h
//List.h 双链表头文件
#define _CRT_SECURE_NO_WARNINGS 1#includestdio.h
#includestdlib.h
#includeassert.htypedef int LTDataType;//数据类型重定义可以是任意数据类型
typedef struct ListNode//双向链表节点结构
{LTDataType data;//数据struct ListNode* prev;//指向前一个节点的指针struct ListNode* next;//指向下一个节点的指针
}LTNode;LTNode* NewNode(LTDataType x);//申请节点
LTNode* LTInit(); //链表初始化void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPushBack(LTNode* phead, LTDataType x);//尾插void LTPopBack(LTNode* phead); //尾删
void LTPopFront(LTNode* phead); //头删LTNode* LTFind(LTNode* phead, LTDataType x);//查找节点void LTInsert(LTNode* pos, LTDataType x);//在pos位置之后插入数据
void LTErase(LTNode* pos);//删除指定位置节点void LTPrint(LTNode* phead); //链表数据打印
void LTDestroy(LTNode* phead);//链表销毁
List.c
//DouSList.c 双链表源文件
#define _CRT_SECURE_NO_WARNINGS 1
#includeDouSList.hLTNode* NewNode(LTDataType x)//申请节点
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(NewNode\n);exit(1);}newnode-data x;//根据参数初始化数据newnode-next newnode-prev newnode;//两个指针初始都指向自身return newnode;
}
LTNode* LTInit() //链表初始化
{LTNode* newnode NewNode(-1);return newnode;
}
void LTPushFront(LTNode* phead, LTDataType x)//头插
{assert(phead);//判空LTNode* newnode NewNode(x);//申请节点newnode-next phead-next;//改变新节点指针指向newnode-prev phead;phead-next-prev newnode;//改变原链表相关节点指针指向phead-next newnode;}
void LTPushBack(LTNode* phead, LTDataType x)//尾插
{assert(phead);//判空LTNode* newnode NewNode(x);//申请节点newnode-next phead;//改变新节点指针指向newnode-prev phead-prev;phead-prev-next newnode;//改变原链表相关节点指针指向phead-prev newnode;
}void LTPopFront(LTNode* phead) //头删
{assert(phead phead-next ! phead);//判空LTNode* del phead-next;//暂时存储要删除的节点del-next-prev phead;//移动指针phead-next del-next;free(del);//释放节点空间del NULL;
}void LTPopBack(LTNode* phead) //尾删
{assert(phead phead-next ! phead);//判空LTNode* del phead-prev;//暂时存储要删除的节点del-prev-next phead;//移动指针phead-prev del-prev;free(del);//释放节点空间del NULL;
}LTNode* LTFind(LTNode* phead, LTDataType x)//查找节点
{assert(phead);//判空LTNode* pcur phead-next;//遍历链表的指针while (pcur! phead){if (pcur-data x)return pcur;pcur pcur-next;}return NULL;
}void LTInsert(LTNode* pos, LTDataType x)//在pos位置之前插入数据
{assert(pos);//判空LTNode* newnode NewNode(x);//申请新节点newnode-next pos;//改变新节点指针指向newnode-prev pos-prev;pos-prev-next newnode;//改变原链表相关节点指针指向pos-prev newnode;}void LTErase(LTNode* pos)//删除指定位置节点
{assert(pos);//判空pos-next-prev pos-prev;//改变要删除节点的前后节点指针指向pos-prev-next pos-next;free(pos);pos NULL;}void LTPrint(LTNode* phead) //链表数据打印
{assert(phead);//判空LTNode* pcur phead-next;//遍历链表的指针while (pcur ! phead)//打印数据{printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}void LTDestroy(LTNode* phead)//链表销毁
{assert(phead);//判空LTNode* pcur phead-next;//遍历链表的指针while (pcur ! phead)//从第一个有效节点开始逐个释放节点{LTNode* next pcur-next;free(pcur);pcur next;}free(phead);//释放哨兵位节点phead NULL;}
