我是靠谱客的博主 时尚百褶裙，最近开发中收集的这篇文章主要介绍数据结构与算法学习：3.双向链表1 双链表2.双向链表的相关操作及实现3 完整代码和运行测试4 总结，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
文章目录
- 1 双链表
- 1.1 双向链表的定义
- 1.2 双向链表相较于单向链表的优点
- 2.双向链表的相关操作及实现
- 2.1 链表的初始化
- 2.2 链表中元素的打印
- 2.3 在指定的位置插入元素
- 2.4 删除指定元素
- 2.5结点的查找
- 2.6 整表的删除
- 3 完整代码和运行测试
- 4 总结
1 双链表
1.1 双向链表的定义
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱点和后继结点。
1.2 双向链表相较于单向链表的优点
既然双向链表的每个数据结点中都有两个指针，那么它相较于单向链表的优点就很明显了，那就是它可以找到前驱和后继，可进可退，而单向链表只能找到后继，无法找到前驱，也就是只能前进。
2.双向链表的相关操作及实现
2.1 链表的初始化
// 初始化表
DLNodePtr initLinkList(){
DLNodePtr tempHeader = (DLNodePtr)malloc(sizeof(struct DoubleLinkedNode));
tempHeader->data = ' ';
tempHeader->previous = NULL;
tempHeader->next = NULL;
return tempHeader;
}
2.2 链表中元素的打印
// 打印表
void printList(DLNodePtr paraHeader){
DLNodePtr p = paraHeader->next;
while(p != NULL){
printf("%c",p->data);
p = p->next;
}
printf("rn");
}
2.3 在指定的位置插入元素
// 在相应位置插入元素
void insertElement(DLNodePtr paraHeader, char paraChar, int paraPosition){
DLNodePtr p,q,r;
//第一步：查找相应的位置
p = paraHeader;
for(int i = 0;i < paraPosition;i++)
{
p = p->next;
if(p == NULL){
printf("The position %d is beyond the scope of the list.",paraPosition);
return;
}
}
// 第二步：建立一个新结点
q = (DLNodePtr)malloc(sizeof(struct DoubleLinkedNode));
q->data = paraChar;
// 第三步：连接
r = p->next;
q->next = p->next;
q->previous = p;
p->next = q;
if(r != NULL){
r->previous = q;
}
}
2.4 删除指定元素
// 删除指定元素
void deleteElement(DLNodePtr paraHeader, char paraChar){
DLNodePtr p,q,r;
p = paraHeader;
// Step 寻找指定元素的对应位置.
while((p->next != NULL)&&(p->next->data != paraChar)){
p = p->next;
}
// step 2. 查看是否存在指定元素.
if(p->next == NULL){
printf("The char '%c' does not exist.rn",paraChar);
return;
}
// step 3. 改变表的结构.
q = p->next;
r = q->next;
p->next = r;
if(r != NULL){
r->previous = p;
}
// step 4. 将指定元素free掉.
free(q);
}
2.5结点的查找
// 结点的查找
int locateElement(DLNode *head, char targetElement)
{
DLNode *t = head;
int i = 1;
while(t){
if(t->data==targetElement)return i;
i++;
t=t->next;
}
return -1;
}
2.6 整表的删除
// 双向链表的整表删除
void clear(DLNodePtr paraHeader){
DLNodePtr p,q;
p=paraHeader->next;
while(p){
q=p->next;
free(p);
p=q;
}
paraHeader=NULL;
}
3 完整代码和运行测试
#include<stdio.h>
#include<malloc.h>
// 双向链表的定义
typedef struct DoubleLinkedNode{
char data;
struct DoubleLinkedNode *previous;
struct DoubleLinkedNode *next;
} DLNode, *DLNodePtr;
// 初始化表
DLNodePtr initLinkList(){
DLNodePtr tempHeader = (DLNodePtr)malloc(sizeof(struct DoubleLinkedNode));
tempHeader->data = ' ';
tempHeader->previous = NULL;
tempHeader->next = NULL;
return tempHeader;
}
// 打印表
void printList(DLNodePtr paraHeader){
DLNodePtr p = paraHeader->next;
while(p != NULL){
printf("%c",p->data);
p = p->next;
}
printf("rn");
}
// 在相应位置插入元素
void insertElement(DLNodePtr paraHeader, char paraChar, int paraPosition){
DLNodePtr p,q,r;
//第一步：查找相应的位置
p = paraHeader;
for(int i = 0;i < paraPosition;i++)
{
p = p->next;
if(p == NULL){
printf("The position %d is beyond the scope of the list.",paraPosition);
return;
}
}
// 第二步：建立一个新结点
q = (DLNodePtr)malloc(sizeof(struct DoubleLinkedNode));
q->data = paraChar;
// 第三步：连接
r = p->next;
q->next = p->next;
q->previous = p;
p->next = q;
if(r != NULL){
r->previous = q;
}
}
// 删除指定元素
void deleteElement(DLNodePtr paraHeader, char paraChar){
DLNodePtr p,q,r;
p = paraHeader;
// Step 1. Locate.
while((p->next != NULL)&&(p->next->data != paraChar)){
p = p->next;
}
// step 2. Error check.
if(p->next == NULL){
printf("The char '%c' does not exist.rn",paraChar);
return;
}
// step 3. Change links.
q = p->next;
r = q->next;
p->next = r;
if(r != NULL){
r->previous = p;
}
// step 4. Free the space.
free(q);
}
// 结点的查找
void locateElement(DLNode *head, char targetElement)
{
DLNode *t = head;
int i = 0,flag = 0;
while(t){
if(t->data==targetElement)
{
printf("所查找元素的位置在%dn",i);
flag = 1;
break;
}
i++;
t=t->next;
}
if(flag == 0)printf("所查找元素不在该表中n");
}
// 双向链表的整表删除
void clear(DLNodePtr paraHeader){
DLNodePtr p,q;
p=paraHeader->next;
while(p){
q=p->next;
free(p);
p=q;
}
paraHeader=NULL;
}
void insertDeleteTest(){
// 第一步：初始化一个空表
DLNodePtr tempList = initLinkList();
printList(tempList);
// 第二步：添加一些元素
insertElement(tempList,'H',0);
insertElement(tempList,'e',1);
insertElement(tempList,'l',2);
insertElement(tempList,'l',3);
insertElement(tempList,'o',4);
insertElement(tempList,'!',5);
printList(tempList);
locateElement(tempList,'H');
locateElement(tempList,'A');
// 第三步：删除一些元素
deleteElement(tempList,'e');
deleteElement(tempList,'a');
deleteElement(tempList,'o');
printList(tempList);
// 第四步：在给定的位置增加一个元素
insertElement(tempList,'o',1);
printList(tempList);
}
void basicAddressTest(){
DLNode tempNode1,tempNode2;
tempNode1.data = 4;
tempNode1.next = NULL;
tempNode2.data = 6;
tempNode2.next = NULL;
printf("The first node: %d, %d, %drn",&tempNode1,&tempNode1.data,&tempNode1.next);
printf("The first node: %d, %d, %drn",&tempNode2,&tempNode2.data,&tempNode2.next);
tempNode1.next = &tempNode2;
}
int main(){
insertDeleteTest();
basicAddressTest();
}
4 总结
通过与之前单链表的代码对比可以看出，实际上双向链表和单向链表之间是差不多的，在单向链表的基础上增加了可以寻找前驱点的操作。但是从存储结构来看，每个双链表的结点都要比单链表多一个指针，因此在一些追求不太高的时间效率的情况下双向链表是不适用的，因为它所占的空间远远大于单链表所占的空间。这也是为什么在当下的环境中单链表的使用要大于双链表。
最后
以上就是时尚百褶裙为你收集整理的数据结构与算法学习：3.双向链表1 双链表2.双向链表的相关操作及实现3 完整代码和运行测试4 总结的全部内容，希望文章能够帮你解决数据结构与算法学习：3.双向链表1 双链表2.双向链表的相关操作及实现3 完整代码和运行测试4 总结所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复