数据结构与算法(009):线性表-双向链表
双向链表
大家都知道,任何事物出现的初期都显得有些不完善。例如我们的火车刚发明的时候是只有一个“头”的,所以如果它走的线路是如下:
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;
既然单链表可以有循环链表,那么双向链表当然也可以有。
在这里小甲鱼问大家一个问题:由于这是双向链表,那么对于链表中的某一个结点p,它的后继结点的前驱结点是什么?
双向链表的插入操作
插入操作其实并不复杂,不过顺序很重要,千万不能写反了。
代码实现:
s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;
关键在于交换的过程中不要出现矛盾,例如第四步先被执行了,那么p->prior就会提前变成s,使得插入的工作出错。严重性打个比方就是打电话给老婆的时候不小心叫成小三的名字!
双向链表的删除操作
如果刚才的插入操作理解了,那么再来理解接下来的删除操作就容易多了。
代码实现:
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(维吉尼亚)加密:
当输入明文,自动生成随机密匙匹配明文中每个字母并移位加密。
明文 |
I |
L |
O |
V |
E |
B |
A |
I |
D |
U |
随机密匙 |
3 |
15 |
23 |
2 |
52 |
1 |
3 |
5 |
7 |
3 |
密文 |
L |
A |
L |
X |
E |
C |
D |
N |
K |
X |
建议:当然你的随机密匙生成后不能丢掉,丢掉了就很难把明文还原来了,建议把随机密匙和密文加密存储在一起。
#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;
}
}
}