数据结构与算法（009）：线性表-双向链表

素颜马尾好姑娘i 2022-02-04 01:21 305阅读 0赞

# 双向链表 #

大家都知道，任何事物出现的初期都显得有些不完善。例如我们的火车刚发明的时候是只有一个“头”的，所以如果它走的线路是如下：

A->B->C->D->E->F->G->H->I->J->K->L->A

假设这会儿火车正停在K处呢，要他送一批货到J处，那么它将走的路线是：

K->L->A->B->C->D->E->F->G->H->I->J

嗯，所以后来我们的火车就都有两个头了。看完这个例子，大家就明白双向链表的必要性了吧。

### 双向链表结点结构 ###

typedef struct DualNode
    {
        ElemType data;
        struct DualNode *prior;  //前驱结点
        struct DualNode *next;   //后继结点
    } DualNode, *DuLinkList;

![20190506162836898.png][]

既然单链表可以有循环链表，那么双向链表当然也可以有。

![20190506162856383.png][]

在这里小甲鱼问大家一个问题：由于这是双向链表，那么对于链表中的某一个结点p，它的后继结点的前驱结点是什么？

## 双向链表的插入操作 ##

插入操作其实并不复杂，不过顺序很重要，千万不能写反了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTU2MzE4_size_16_color_FFFFFF_t_70][]

代码实现：

s->next = p;

s->prior = p->prior;

p->prior->next = s;

p->prior = s;

关键在于交换的过程中不要出现矛盾，例如第四步先被执行了，那么p->prior就会提前变成s，使得插入的工作出错。严重性打个比方就是打电话给老婆的时候不小心叫成小三的名字！

### 双向链表的删除操作 ###

如果刚才的插入操作理解了，那么再来理解接下来的删除操作就容易多了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTU2MzE4_size_16_color_FFFFFF_t_70 1][]

代码实现：

p->prior->next = p->next;

p->next->prior = p->prior;

free(p);

最后总结一下，双向链表相对于单链表来说，是要更复杂一点，每个结点多了一个prior指针，对于插入和删除操作的顺序大家要格外小心。

不过，双向链表可以有效提高算法的时间性能，说白了就是用空间来换取时间。

### 双向循环链表实践 ###

课堂演示题目：

要求实现用户输入一个数使得26个字母的排列发生变化，例如用户输入3，输出结果：

DEFGHIJKLMNOPQRSTUVWXYZABC

同时需要支持负数，例如用户输入-3，输出结果：

XYZABCDEFGHIJKLMNOPQRSTUVW

实现代码如下：

/*
 题目：对A-Z26个英文字母，根据指定的数字，将其循环移动，例如
 ABCDEFGHIJKLMNOPQRSTUVWXYZ
 输入3，得到
 DEFGHIJKLMNOPQRSTUVWXYZABC
 输入-3，得到
 XYZABCDEFGHIJKLMNOPQRSTUVW
 思路：使用双向循环链表来实现
 
 */
 #include <stdio.h>
 #include <stdlib.h>
 
 #define OK 1
 #define ERROR 0
 
 typedef char ElemType;
 typedef int status;
 
 typedef struct node
 {
 	ElemType data;
 	struct node *prior;
 	struct node *next;
 } node, *list;
 
 status init(list *L)
 {
 	node *p, *q;
 	int i;
 
 	*L = (list)malloc(sizeof(node));
 	if (!(*L)) return ERROR;
 	(*L)->next = (*L)->prior = NULL;
 	p = (*L);
 
 	for (i = 0; i<26; i++)
 	{
 		q = (node*)malloc(sizeof(node));
 		if (!q) return ERROR;
 		q->data = 'A' + i;
 		q->prior = p;
 		q->next = p->next;
 		p->next = q;
 
 		p = q;
 	}
 
 	// 形成闭环： 
 	p->next = (*L)->next;
 	(*L)->next->prior = p;
 	return OK;
 }
 
 void caesar(list L, int n)
 {
 	node *p = L->next;
 	if (n>0)
 	{
 		do
 		{
 			p = p->next;
 		} while (--n);
 	}
 	if (n<0)
 	{
 		do
 		{
 			p = p->prior;
 		} while (++n);
 	}
 	L->next = p;
 }
 
 int main()
 {
 	list L = NULL;
 	int i = 0, n = 0;
 	node *p = NULL;
 	init(&L);
 
 	p = L->next;
 	for (i = 0; i<26; i++)
 	{
 		printf("%c", p->data);
 		p = p->next;
 	}
 	printf("\n");
 	printf("请输入一个整数:");
 	scanf("%d", &n);
 	caesar(L, n);
 	p = L->next;
 	for (i = 0; i<26; i++)
 	{
 		printf("%c", p->data);
 		p = p->next;
 	}
 	return 0;
 }

### 课后作业 ###

Vigenere（维吉尼亚）加密：

当输入明文，自动生成随机密匙匹配明文中每个字母并移位加密。

建议：当然你的随机密匙生成后不能丢掉，丢掉了就很难把明文还原来了，建议把随机密匙和密文加密存储在一起。

#include <stdio.h>
 #include <stdlib.h>
 #include <time.h>
 
 typedef struct Vigenere
 {
 	int data;
 	char ciphertext;
 	struct Vigenere *next;
 }sqvigen, *vigenere;
 
 typedef struct Content
 {
 	char content;
 	struct Content *next;
 }sqlist, *linklist;
 
 int random() //随机产生数字，作为密匙 
 {
 	int num;
 	srand(time(0));
 	num = rand() % 100;
 	return num;
 }
 
 linklist Create()
 {
 	int i;
 	linklist head = NULL;
 	linklist s, r;
 	r = head;
 	printf("Please input your real words: ");
 	getchar(); //清空输入缓冲区 
 	while (1)
 	{
 		s = (linklist)malloc(sizeof(sqlist));
 		s->content = getchar();
 		if (s->content == '\n')
 		{
 			break;
 		}
 		if (head == NULL)
 		{
 			head = s;
 		}
 		else
 		{
 			r->next = s;
 		}
 		r = s;
 	}
 	r->next = NULL;
 	return head;
 }
 
 vigenere Encrypt(linklist head)
 {
 	linklist p;
 	vigenere vigen = NULL;
 	vigenere s, r;
 	r = vigen;
 	p = head;
 	srand(time(0));
 	while (p != NULL)
 	{
 		s = (vigenere)malloc(sizeof(sqvigen));
 		s->data = rand() % 100;
 		s->ciphertext = (p->content) + (s->data);
 		if (vigen == NULL)
 		{
 			vigen = s;
 		}
 		else
 		{
 			r->next = s;
 		}
 		r = s;
 		p = p->next;
 	}
 	r->next = NULL;
 	return vigen;
 }
 
 void decipher(vigenere top)
 {
 	vigenere p = top;
 	printf("解码: \n");
 	while (p != NULL)
 	{
 		printf("%c", (p->ciphertext) - (p->data));
 		p = p->next;
 	}
 }
 int main()
 {
 	linklist p, head;
 	vigenere temp, top;
 	int i;
 	while (1)
 	{
 		printf("请选择将要进行的操作: \n");
 		printf("1.输入明文\n2.输出明文\n3.输出密文并解码\n4.退出程序\n");
 		scanf("%d", &i);
 		switch (i)
 		{
 		case 1:
 			head = p = Create();
 			printf("\n\n");
 			break;
 		case 2:
 			printf("\n明文是: \n");
 			while (p != NULL)
 			{
 				printf("%c", p->content);
 				p = p->next;
 			}
 			printf("\n\n");
 			break;
 		case 3:
 			top = temp = Encrypt(head);
 			printf("\n密文是: \n");
 			while (temp != NULL)
 			{
 				printf("%c", temp->ciphertext);
 				temp = temp->next;
 			}
 			printf("\n\n");
 			decipher(top);
 			printf("\n\n");
 			break;
 		case 4:
 			return 0;
 		}
 	}
 }

[20190506162836898.png]: /images/20220204/9c1e7a1e54344437886fe9229d2a378c.png
[20190506162856383.png]: /images/20220204/bd454efd7f0d4732a7ad867128df8436.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTU2MzE4_size_16_color_FFFFFF_t_70]: /images/20220204/2a5ffec98a1545d99e27a4ae96379681.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTU2MzE4_size_16_color_FFFFFF_t_70 1]: /images/20220204/27896a46a2f44c3ba281ff22947b1fde.png