数据结构（5）线性表之双向链表
程序员文章站
2022-06-06 23:49:40
...
前言
在先前讨论的链式存储结构中，无论是单链表还是单循环链表，都只有一个指向后继的指针，因此可以很容易找到它的后继，但是要找它的前驱却很麻烦。那么可不可以再增加一个指向前驱的指针，这样在遍历链表时不仅能从前往后遍历，也能从后往前遍历呢？这就是我们今天所说的双向链表。
顾名思义，双向链表就是其结点中有两个指针域，一个指向直接前驱，一个指向直接后继。当然，链表的第一个结点无直接前驱，最后一个结点无直接后继，设置为空即可。
实现双向链表的相关操作，思路上同单链表是一致的，唯一的区别是还需要考虑Prior指针的指向问题。
增加双向链表的管理结构
我们同样为双向链表设置管理结构，first指针指向头结点，last指针指向最后一个结点，size保存链表结点的数量。同单链表一样，在增加了管理结构之后，在做插入、删除操作时，除了保证链表本身的正确性，还要考虑到管理结构的正确性，也就是注意first和last指针指向的正确，和size的数量正确。
双向链表的插入
与单链表不同的是，双向链表的改动除了涉及Next指针外，还涉及Prior指针，因此每当我们要执行插入操作时，一般要考虑四个指针的指向
- 待插入结点的Prior指针
- 待插入结点的Next指针
- 待插入结点前驱的Next指针
- 待插入结点后继的Prior指针
只要想好了这四个指针的指向问题，双向链表的操作也就没什么难点了
尾部插入
尾部插入只涉及两个结点，因此只需要考虑两个指针，以及管理结构的last指针即可
头部与按值插入
头部插入是直接插在头结点后的位置，按值插入是找到插入位置后直接进行插入(如果是最后一位直接进行尾部插入)，两种方式都需要考虑四个指针的指向
同时，在设置四个指针指向的时候要注意先后的顺序，避免出现指针丢失的问题
双向链表的删除
双向链表的删除比单链表的删除方便，因为可以找到直接前驱，所以也不需要使用修改值的方法了，直接修改直接前驱和直接后继的指针就好了。尾部、头部和按值删除的方法都类似，只是涉及到的指针有区别，不详谈了。
排序与逆置
与单链表的思路一样，在进行双向链表的排序时，可以借鉴按值插入的思路，将原有的双向链表断开，再遍历一个个取出结点，进行按值插入。而在进行逆置时，则进行头部插入即可。
在这里我是利用了已经写好的方法，直接调用方法进行按值插入，再将原来的结点释放掉。
while (q != NULL) {
//取出后续结点
s = q;
q = q->next;
//进行按值插入
insert_val(list, s->data);
//释放原来的结点
free(s);
list->size --;
}
也可以不调用方法，通过设置指针的方式将结点重新连接到链表中
while (q != NULL) {
//取出后续结点
s = q;
q = q->next;
Node *p = list->first;
//寻找插入位置
while (p->next != NULL && p->next->data<s->data) {
p = p->next;
}
//判断是否是最后一个
if (p->next == NULL) {
//是，进行尾部插入
s->next = NULL;
s->prior = list->last;
list->last->next = s;
list->last = s;
}else{
//s的后继指向p的后继
s->next = p->next;
//s的前驱指向p
s->prior = p;
//p后继的前驱指向s
p->next->prior = s;
//p的后继指向s
p->next = s;
}
逆置同理
全部代码
DList.h
#ifndef DList_h
#define DList_h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define ElemType int
typedef struct Node{
ElemType data;
struct Node *prior;
struct Node *next;
}Node,*PNode;
typedef struct List{
PNode first;
PNode last;
int size;
}List;
//初始化双链表
void InitDList(List *list);
//1.尾部插入
void push_back(List *list,ElemType x);
//2.头部插入
void push_fount(List *list,ElemType x);
//3.展示
void show_list(List *list);
//4.尾部删除
void pop_back(List *list);
//5.头部删除
void pop_fount(List *list);
//6.按值插入(要求插入前的链表是有序的(此处为顺序
void insert_val(List *list,ElemType x);
//7.按值查找
Node* find(List *list,ElemType x);
//8.获取长度
int length(List *list);
//9.按值删除
void delete_val(List *list,ElemType x);
//10.排序
void sort(List *list);
//11.逆置(前后转换
void resver(List *list);
//12.清除单链表 ->只清除数据，保留头结点
void clearList(List *list);
//13.摧毁 ->包括头结点在内一起摧毁
void destroy(List *list);
//生成一个结点
Node* getNode(ElemType x);
#endif /* DList_h */
DList.cpp
#include "DList.h"
//初始化
void InitDList(List *list){
Node *s = (Node *)malloc(sizeof(Node));
assert(s != NULL);
list->first = list->last = s;
list->first->next = NULL;
list->first->prior = NULL;
list->size = 0;
}
//1.尾部插入
void push_back(List *list,ElemType x){
//获得一个结点
Node *s = getNode(x);
//s的前驱指向最后一个结点
s->prior = list->last;
//最后一个结点的后继指向s
list->last->next = s;
//重新设置last指针的指向
list->last = s;
list->size ++;
}
//2.头部插入
void push_fount(List *list,ElemType x){
Node *s = getNode(x);
//判断是否是第一个结点
if (list->first == list->last) {
//是第一个结点，s的后继不需要设置
//s的前驱指向头结点
//s->prior = list->first;
//重新设置first指针的指向，使s成为新的首元结点
//list->first->next = s;
//重新设置last指针的指向
list->last = s;
}else{
//s的后继指向首元结点
s->next = list->first->next;
//s的前驱指向头结点
//s->prior = list->first;
//首元结点的前驱指向s
//s->next->prior = s;
list->first->next->prior = s;
//重新设置first指针的指向，使s成为新的首元结点
list->first->next = s;
}
//if-else语句中有重复的部分，可以提出来
//s的前驱指向头结点
s->prior = list->first;
//重新设置first指针的指向，使s成为新的首元结点
list->first->next = s;
list->size ++;
}
//3.展示
void show_list(List *list){
Node *p = list->first->next;
while (p != NULL) {
printf("%4d",p->data);
p = p->next;
}
printf("\n");
}
//4.尾部删除
void pop_back(List *list){
if (list->size == 0) {
printf("链表已空！\n");
return;
}
//方法1
Node *p = list->first;
//循环到链表的最后一位
while (p->next != NULL) {
p = p->next;
}
//将last指针指向倒数第二位(即p的前一位
list->last = p->prior;
//释放该结点的空间
free(p);
//此时链表最后一位的后继为空
list->last->next = NULL;
list->size --;
/*
//方法2
Node *p = list->first;
//循环到链表倒数第二位
while (p->next != list->last) {
p = p->next;
}
//释放最后一个结点的空间
free(p->next);
p->next = NULL;
//重新设置last指针的指向
list->last = p;
list->size --;
*/
}
//5.头部删除
void pop_fount(List *list){
if (list->size == 0) {
printf("链表已空!\n");
return;
}
Node *s = list->first->next;
//判断是否是最后一个结点
if (s->next == NULL) {
//是，则s没有后继,不需要修改后继的指针
//修改last指针的指向
list->last = list->first;
list->last->next = NULL;
}else{
//s的后继的prior指针指向头结点
s->next->prior = list->first;
//头结点的next指针指向s的后继
list->first->next = s->next;
}
//释放该结点
free(s);
list->size --;
}
//6.按值插入(要求插入前的链表是有序的(此处为顺序
void insert_val(List *list,ElemType x){
Node *p = list->first;
//寻找插入位置
while (p->next != NULL && p->next->data<x) {
p = p->next;
}
//判断是否是最后一个
if (p->next == NULL) {
//是，直接进行尾部插入
push_back(list, x);
}else{
Node *s = getNode(x);
//s的后继指向p的后继
s->next = p->next;
//s的前驱指向p
s->prior = p;
//p后继的前驱指向s
p->next->prior = s;
//p的后继指向s
p->next = s;
list->size ++;
}
}
//7.按值查找
Node* find(List *list,ElemType x){
Node *p = list->first->next;
while (p != NULL && p->data != x) {
p = p->next;
}
return p;
}
//8.获取长度
int length(List *list){
return list->size;
}
//9.按值删除
void delete_val(List *list,ElemType x){
if (list->size == 0) {
printf("链表已空！\n");
return;
}
Node *p = find(list, x);
if (p == NULL) {
printf("要删除的值不存在！\n");
return;
}
//判断是否是最后一个节点
if (p == list->last) {
//直接进行尾部删除
pop_back(list);
}else{
//p后继的前驱指向p的前驱
p->next->prior = p->prior;
//p前驱的后继指向p的后继
p->prior->next = p->next;
//释放结点空间
free(p);
list->size --;
}
}
//10.排序
void sort(List *list){
if (list->size <= 1) {
//不需要排序
return;
}
Node *s = list->first->next;
Node *q = s->next;
//将链表断开
list->last = s;
list->last->next = NULL;
while (q != NULL) {
//取出后续结点
s = q;
q = q->next;
//进行按值插入
insert_val(list, s->data);
//释放原来的结点
free(s);
list->size --;
// Node *p = list->first;
// //寻找插入位置
// while (p->next != NULL && p->next->data<s->data) {
// p = p->next;
// }
//
// //判断是否是最后一个
// if (p->next == NULL) {
// //是，直接进行尾部插入
// s->next = NULL;
// s->prior = list->last;
// list->last->next = s;
// list->last = s;
// }else{
//
// //s的后继指向p的后继
// s->next = p->next;
// //s的前驱指向p
// s->prior = p;
// //p后继的前驱指向s
// p->next->prior = s;
// //p的后继指向s
// p->next = s;
// }
}
}
//11.逆置(前后转换
void resver(List *list){
if (list->size <= 1) {
//不需要逆置
return;
}
Node *s = list->first->next;
Node *q = s->next;
//将链表断开
list->last = s;
list->last->next = NULL;
while (q != NULL) {
s = q;
q = q->next;
//直接进行头部插入
push_fount(list, s->data);
//释放原有结点
free(s);
list->size --;
}
}
//12.清除单链表 ->只清除数据，保留头结点
void clearList(List *list){
if (list->size == 0) {
printf("链表已空！\n");
return;
}
Node *s = list->first;
Node *p = s->next;
//遍历整个链表
while (p != NULL) {
s = p;
p = p->next;
//释放结点
free(s);
list->size --;
}
list->last = list->first;
list->last->next = NULL;
}
//13.摧毁 ->包括头结点在内一起摧毁
void destroy(List *list){
clearList(list);
free(list->first);
list->first = list->last = NULL;
}
//生成一个结点
Node* getNode(ElemType x){
Node *s = (Node *)malloc(sizeof(Node));
assert(s != NULL);
s->data = x;
s->prior = NULL;
s->next = NULL;
return s;
}
Main.cpp
#include "DList.h"
int main(int argc, const char * argv[]) {
List myList;
InitDList(&myList);
//保存要输入的数据
ElemType item;
//保存要查找的地址
Node *p = NULL;
int select = 1;
while (select) {
printf("**************************************\n");
printf("* [1] push_back [2] push_front *\n");
printf("* [3] show_list [4] pop_back *\n");
printf("* [5] pop_front [6] insert_val *\n");
printf("* [7] find [8] length *\n");
printf("* [9] delete_val [10] sort *\n");
printf("* [11] resver [12] clear *\n");
printf("* [13*] destroy [0] quit_system*\n");
printf("**************************************\n");
printf("请选择:");
scanf("%d",&select);
if (select == 0) {
break;
}
switch (select) {
case 1:
//尾部插入
printf("请输入要插入的数据(-1结束):");
scanf("%d",&item);
while (item != -1) {
push_back(&myList, item);
scanf("%d",&item);
}
break;
case 2:
//头部插入
printf("请输入要插入的数据(-1结束):");
scanf("%d",&item);
while (item != -1) {
push_fount(&myList, item);
scanf("%d",&item);
}
break;
case 3:
//展示单链表
show_list(&myList);
break;
case 4:
//尾部删除
pop_back(&myList);
break;
case 5:
//头部删除
pop_fount(&myList);
break;
case 6:
//按值插入
printf("请输入要插入的数据:\n");
scanf("%d",&item);
insert_val(&myList, item);
break;
case 7:
//按值查找
printf("请输入要查找的值:\n");
scanf("%d",&item);
p = find(&myList, item);
if (p == NULL) {
printf("要查找的数据不存在!\n");
}else{
printf("地址为:%p\n",p);
}
break;
case 8:
//展示链表长度
printf("链表的长度为:%d\n",length(&myList));
break;
case 9:
//按值删除
printf("请输入要删除的值：\n");
scanf("%d",&item);
delete_val(&myList, item);
break;
case 10:
//排序
sort(&myList);
break;
case 11:
//逆置(前后转换
resver(&myList);
break;
case 12:
//清除
clearList(&myList);
break;
case 13:
destroy(&myList);
break;
default:
printf("输入的命令有误，请重新插入\n");
break;
}
}
return 0;
}