双向链表
一双向链表结构
双向链表结点结构
- 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;
- }
来源: http://www.jianshu.com/p/f58a56ca6401