双向链表
一、双向链表结构
双向链表结点结构
typedef struct DualNode
{
ElemType data;
struct DualNode *prior; //前驱结点
struct DualNode *next; //后继结点
} DualNode, *DuLinkList;
双向链表结点结构.png
既然单链表可以有循环链表,那么双向链表当然也可以有。
非空的双循环链表.png由于这是双向链表,那么对于链表中的某一个结点p,它的后继结点的前驱结点是它本身。
二、双向链表的插入操作
插入操作.jpg代码实现:
s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;
关键在于交换的过程中不要出现矛盾,例如第四步先被执行了,那么p->prior就会提前变成s,使得插入的工作出错。
三、双向链表的删除操作
删除操作.png代码实现:
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
双向链表可以有效提高算法的时间性能,说白了就是用空间来换取时间。
四、双向链表的实践
要求实现用户输入一个数使得26个字母的排列发生变化,例如用户输入3,输出结果:
DEFGHIJKLMNOPQRSTUVWXYZABC
同时需要支持负数,例如用户输入-3,输出结果:
XYZABCDEFGHIJKLMNOPQRSTUVW
代码实现:
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
typedef char ElemType;
typedef int Status;
typedef struct DualNode{
ElemType data;
struct DualNode *prior;
struct DualNode *next;
}DualNode,*DuLinkList;
Status InitList(DuLinkList *L){
DualNode *p,*q;
int i;
*L = (DuLinkList)malloc(sizeof(DualNode));
if(!(*L)){
return ERROR;
}
(*L)->next = (*L)->prior = NULL;
p = (*L);
for(i=0;i<26;i++){
q = (DualNode *)malloc(sizeof(DualNode));
if(!q){
return ERROR;
}
q->data = 'A'+i;
q->prior = p;
q->next = p->next;
p = q;
}
p->next = (*L)->next;
(*L)->next->prior = p;
return OK;
}
void Caesar(DuLinkList *L,int i){
if(i>0){
do{
(*L) = (*L)->next;
}while(--i);
}
if(i<0){
do{
(*L) = (*L)->next;
}while(++i);
}
}
int main(){
DuLinkList L;
int i,n;
InitList(&L);
printf("请输入一个整数:");
scanf("%d",&n);
printf("\n");
Caesar(&L,n);
for(i=0;i<26;i++){
L = L->next;
printf("%c",L->data);
}
printf("\n");
return 0;
}
网友评论