- 雙向鏈表概念
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針照卦，分別指向直接后繼和直接前驅(qū)。所以乡摹，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始役耕，都可以很方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。（引用于：百度百科）
2.代碼部分
1）雙向鏈表節(jié)點(diǎn)結(jié)構(gòu)：
//例1.
typedef struct node
{
Elemtype data;
struct node *previous;
struct node *next;
}Node;
2）雙向鏈表的初始化和創(chuàng)建：
//例2
Status InitLinkList(Node **node)
{
*node = (Node *)malloc(sizeof(Node));
(*node)->next = *node;
(*node)->previous = *node;
}
Status CreateLinkList(Node **node) //這里創(chuàng)建的是循環(huán)雙向鏈表
{
char i;
Node *target, *temp, *temp2;
target = *node;
printf("Please input the elements you want in the LinkList(input 0 means stop input):");
scanf("%c", &i);
getchar();
target->data = i;
while(i)
{
temp = (Node *)malloc(sizeof(Node));
scanf("%c", &i);
if(i == '0') break;
getchar();
temp->data = i;
temp2 = target;
target->next = temp;
target = target->next;
target->previous = temp2;
}
target->next = *node;
(*node)->previous = target;
}
3）雙向鏈表的插入：
//例3.
Status Insert(Node **node, int i, Elemtype e)
{
Node *target, *temp;
int j;
target = *node;
temp = (Node *)malloc(sizeof(Node));
temp->data = e;
if(i == 1)
{
temp->previous = target->previous;
target->previous->next = temp;
temp->next = target;
target->previous = temp;
*node = temp;//(target = temp;)?
}
else
{
for(j = 1; j < i; j++)
{
target = target->next;
}
temp->next = target;
temp->previous = target->previous;
target->previous->next = temp;
target->previous = temp;
//target->previous->next = temp;
//temp->previous = target->previous;
//temp->next = target;
//target->previous = temp;
}
}
4）雙向鏈表的刪除：（注意聪廉，這里創(chuàng)建的是循環(huán)雙向鏈表）
//例4.
Status Delete(Node **node, int i)
{
Node *target, *temp;
int j;
target = *node;
if(i == 1)
{
temp = target->next;
temp->previous = target->previous;
target->previous->next = temp;
*node = temp;
}
else
{
for(j = 1; j < i; j ++)
{
target = target->next;
}
target->previous->next = target->next;
target->next->previous = target->previous;
}
}
//例5瞬痘，總體框架代碼（注意，這里創(chuàng)建的是循環(huán)雙向鏈表）
#include<stdio.h>
#include<stdlib.h>
typedef void Status;
typedef int Elemtype;
typedef struct node
{
Elemtype data;
struct node *previous;
struct node *next;
}Node;
Status InitLinkList(Node **node)
{
*node = (Node *)malloc(sizeof(Node));
(*node)->next = *node;
(*node)->previous = *node;
}
Status CreateLinkList(Node **node)
{
char i;
Node *target, *temp, *temp2;
target = *node;
printf("Please input the elements you want in the LinkList(input 0 means stop input):");
scanf("%c", &i);
getchar();
target->data = i;
while(i)
{
temp = (Node *)malloc(sizeof(Node));
scanf("%c", &i);
if(i == '0') break;
getchar();
temp->data = i;
temp2 = target;
target->next = temp;
target = target->next;
target->previous = temp2;
}
target->next = *node;
(*node)->previous = target;
}
Status CreateLinkList2(Node **node)
{
Elemtype i;
Node *target, *temp, *temp2;
target = *node;
target->data = 65;
for(i = 66; i <= 90; i++)
{
temp = (Node *)malloc(sizeof(Node));
temp->data = i;
target->next = temp;
temp2 = target;
target = target->next;
temp2->next = target;
target->previous = temp2;
}
target->next = *node;
(*node)->previous = target;
}
Status Visit(Node *node)
{
if(node)
{
printf("%c", node->data);
}
}
Status TraversalLinkList(Node **node) //正著看
{
Node *target;
target = *node;
Visit(target);
target = target->next;
while(target != *node)
{
Visit(target);
target = target->next;
}
printf("\n");
}
Status TraversalLinkList2(Node **node) //倒著看
{
Node *target;
target = *node;
target = target->previous;
Visit(target);
while(target != *node)
{
target = target->previous;
Visit(target);
}
printf("\n");
}
Status Insert(Node **node, int i, Elemtype e)
{
Node *target, *temp;
int j;
target = *node;
temp = (Node *)malloc(sizeof(Node));
temp->data = e;
if(i == 1)
{
temp->previous = target->previous;
target->previous->next = temp;
temp->next = target;
target->previous = temp;
*node = temp;//(target = temp;)?
}
else
{
for(j = 1; j < i; j++)
{
target = target->next;
}
temp->next = target; //這里鏈接的次序需要格外注意
temp->previous = target->previous;
target->previous->next = temp;
target->previous = temp;
//target->previous->next = temp;
//temp->previous = target->previous;
//temp->next = target;
//target->previous = temp;
}
}
Status Delete(Node **node, int i)
{
Node *target, *temp;
int j;
target = *node;
if(i == 1)
{
temp = target→next; //這里鏈接的次序需要格外注意
temp->previous = target->previous;
target->previous->next = temp;
*node = temp;
}
else
{
for(j = 1; j < i; j ++)
{
target = target->next;
}
target->previous->next = target->next;
target->next->previous = target->previous;
}
}
void main()
{
Node *node;
InitLinkList(&node);
CreateLinkList(&node); //使用該函數(shù)構(gòu)造鏈表的話由于scanf會(huì)輸入“\n”板熊，所以會(huì)造成插入框全、刪除錯(cuò)誤(然而插入getchar()函數(shù)可以去除scanf函數(shù)產(chǎn)生的“\n”)
//CreateLinkList2(&node);
TraversalLinkList(&node);
Insert(&node, 6, 'u');
TraversalLinkList(&node);
Delete(&node, 2);
Delete(&node, 5);
TraversalLinkList(&node);
TraversalLinkList2(&node);
}
- 例題：
要求實(shí)現(xiàn)用戶輸入一個(gè)數(shù)使得 26 個(gè)字母的排列發(fā)生變化,例如用戶輸入 3 ,輸出結(jié)果:
DEFGHIJKLMNOPQRSTUVWXYZABC
同時(shí)需要支持負(fù)數(shù),例如用戶輸入 -3 ,輸出結(jié)果:
XYZABCDEFGHIJKLMNOPQRSTUVW
//例6
#include<stdio.h>
#include<stdlib.h>
typedef char Elemtype;
typedef void Status;
typedef struct node
{
Elemtype data;
struct node *next;
struct node *previous;
}Node;
Status Traversal(Node **head)
{
Node *target;
target = *head;
if (target)
{
printf("%c ", target->data);
target = target->next;
while(target && target != *head)
{
printf("%c ", target->data);
target = target->next;
}
}
}
Status InitDoubleLinkList(Node **head)
{
*head = (Node *)malloc(sizeof(Node));
if(!(*head))
{
printf("ERROR! There is no more memory space!");
exit(0);
}
(*head)->next = *head;
(*head)->previous = *head;
}
Status CreateDoubleLinkList(Node **head)
{
Node *target, *temp1, *temp2;
char c = 65;
int n;
target = *head;
target->data = c;
for(n = 0, c = 66; n < 25; n++, c++)
{
temp1 = (Node *)malloc(sizeof(Node));
temp1->data = c;
temp2 = target;
target->next = temp1;
target = target->next;
target->previous = temp2;
}
target->next = *head;
(*head)->previous = target;
}
Status PlayWords(Node **head, int n)
{
Node *target1, *target2; //target1表示head， target2表示rear
int i;
target1 = *head;
target2 = (*head)->previous;
if(n > 0)
{
for(i = 1; i < n; i++)
{
target1 = target1->next;
}
*head = target1;
}
else if(n < 0)
{
for(i = -1; i > n; i--)
{
target2 = target2->previous;
}
*head = target2;
}
}
void main()
{
Node *L;
int n;
printf("Please input the number:");
scanf("%d", &n);
InitDoubleLinkList(&L);
CreateDoubleLinkList(&L);
Traversal(&L);
printf("\n");
PlayWords(&L, n);
Traversal(&L);
}
