线性表之双向链表
2019-03-12 本文已影响17人
此间不留白
基本概念
在之前的学习中，已经学习了单向链表及其实现，在单向链表中，查找一个数据，只能从某个结点出发，顺着指针往后查找其他结点，若需要查找结点的前驱结点，只能从表头指针重新出发。在单向链表中，查找一个结点的直接后继结点，其时间复杂度为O(1)，而查找其直接前驱结点，需要的时间复杂度为O(n)，为了克服这种缺点，特地引入了双向链表。
双向链表与单向链表相比，双向链表有两个指针域，一个指向其直接后继，另一个指向其直接前驱，其结构如下图所示：
双向链表
双向链表的结点可以用以下结构体定义
typedef struct dulNode {
int pData; //数据域
struct dulNode *next; //后继结点
struct dulNode *pre; //前驱结点
}dulNode, *dulList;
双向链表的接口及其实现
接口定义
接口定义如下代码所示：
#pragma once
#ifndef DOUBLELINKLIST_H
#define DOUBLELINKLIST_H
typedef struct dulNode {
int pData; //数据域
struct dulNode *next; //后继结点
struct dulNode *pre; //前驱结点
}dulNode, *dulList;
dulList initDulList(); //初始化
dulList insertDulList(dulList list, int i, int elem); //位置i处插入元素elem
dulList deleteDulList(dulList list, int i);//删除i处的结点
int locateDulList(dulList list, int elem); //查找元素elem的位置‘
void dulList_trave(dulList list); //遍历链表
void freeDulList(dulList list); //销毁链表
dulList updateDulList(dulList list, int i, int elem); //修改i处的元素
int getLength(dulList list);
#endif // !DOUBLELINKLIST_H
接口实现
- 初始化
初始化的过程就是给链表头结点分配一块固定大小的内存，并将它的后继结点与前驱结点置空，当然也可以将前驱结点和后继结点设置为头结点本身。具体实现代码如下所示;
dulList initDulList()
{
dulList list = (dulList)malloc(sizeof(dulNode));
if (list)
{
list->next = list->pre = NULL;
list->pData = NULL;
return list;
}
else
return NULL;
}
-
插入结点
双向链表中插入一个结点与单向链表相比，要多考虑其前驱指针的变化，当插入位置是头结点之前时，直接将插入结点的后继指针指向原来的链表头结点，并将其前驱指针指向其结点本身。而当插入位置是尾结点是，需要将原来链表的后继指针指向要插入的结点，将要插入结点的前驱指针指向原来链表的尾结点。当插入位置是中间位置时，实现过程可有下图动态表示;
插入元素
以上过程可以由以下代码实现
dulList insertDulList(dulList list, int i, int elem)
{
dulList temp = (dulList)malloc(sizeof(dulNode));
temp->pData = elem;
temp->next = NULL;
temp->pre = NULL;
if (i<1||i>getLength(list)+1)
{
printf("位置无效！");
exit(0);
}
else if (i == 1)
{
temp->next = list;
list->pre = temp;
list = temp;
}
else
{
//找到插入位置的前一个结点
dulList p = list;
for (int j = 1; j < i-1; j++)
{
p = p->next;
}
//判断是否是尾
if (p->next == NULL)
{
p->next = temp;
temp->pre = p;
}
else
{
p->next->pre = temp;
temp->next = p->next;
p->next = temp;
temp->pre = p;
}
}
return list;
}
- 删除元素
在双向链表中删除一个元素，需要处理好被删除结点直接前驱和直接后继结点的指针域，具体实现可以简单描述为以下两步:
- 将被删除结点的后继指针赋值给其直接前驱结点的后继指针;
-
将被删除结点的前驱指针赋值给其直接后继结点的前驱指针。
具体过程可由以下动态图所示：
删除一个结点
以上过程的具体实现代码如下所示：
dulList deleteDulList(dulList list, int i)
{
if (i<1 || i>getLength(list))
{
printf("位置错误！");
exit(0);
}
dulList p = list;
for (int j = 0; j <i-1; j++)
{
p = p->next;
}
if (p!=NULL)
{
p->pre->next = p->next;
p->next->pre = p->pre;
free(p);
}
return list;
}
-
查找指定元素
双向链表查找指定元素的代码如下所示，若找到指定元素，返回其位置，否则返回-1.
动态图演示如下：
查找指定元素
int locateDulList(dulList list, int elem)
{
int index = 0;
dulList p = list;
while (p!=NULL)
{
if (p->pData == elem)
{
return index;
}
index++;
p = p->next;
}
return -1;
}
- 修改数据
双向链表要修改一个数据，首先通过遍历找到要修改结点的位置，然后将其数据域更改为指定的元素即可。如下代码所示：
dulList updateDulList(dulList list, int i, int elem)
{
if (i < 1 || i>getLength(list))
{
printf("无效位置！");
exit(0);
}
dulList p = list;
if (p != NULL)
{
for (int j = 1; j < i; j++)
{
p = p->next;
}
p->pData = elem;
return list;
}
}
- 获取链表长度
要获得链表长度，设置计数器初始值为0，需要遍历整个链表，计数器累加即可，具体代码如下所示：
int getLength(dulList list)
{
int i = 0;
dulList p = list->next;
while (p != NULL)
{
i++;
p = p->next;
}
return i;
}
- 遍历链表
遍历整个链表的实现代码如下所示：
void dulList_trave(dulList list)
{
dulList p = list;
if (p->next == NULL)
{
exit(0);
}
while (p->next)
{
if (p->next == NULL)
{
printf("%d", p->pData);
}
else
{
printf("%d->", p->pData);
}
p = p->next;
}
}
- 销毁链表
对链表销毁，就是销毁链表的每一个结点，通过遍历链表，销毁每个结点，具体实现代码如下所示:
void freeDulList(dulList list)
{
dulList p = list;
if (list)
{
exit(0);
}
while (list)
{
p = list;
list = list->next;
free(p);
}
}
对双向链表的测试代码如下所示：
int main()
{
struct dulList* list = initDulList();
list = insertDulList(list, 1, 1);
list = insertDulList(list, 2, 2);
list = insertDulList(list, 3, 3);
list = insertDulList(list, 4, 4);
int index = locateDulList(list, 4);
list = updateDulList(list, 4, 6);
//printf("%d\n", index);
freeDulList(list);
//dulList_trave(list);
system("pause");
return 0;
}
教材：数据结构（C语言版）清华大学出版社
辅助学习网站：https://visualgo.net
