数据结构与算法笔记 lesson8 双向链表

双向链表结构

typedef struct DualNode { ElemType data; struct DualNode *prior; struct DualNode *next; }DualNode, *DuLinkList;

插入

s->next = p;

s->prior = p->prior;

p->prior->next=s;

p->prior=s;

删除

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

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

free(p)

双向链表可以有效的提高算法的性能，用空间换取时间。

运用

输入一个数（支持负数），使得26个字母的排列顺序发生变化

例如输入3，  输出DEFGHIJKLMNOPQRSTUVWXYZABC

#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->next = q; 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("请输入一个整数\n"); scanf("%d", &n); Caesar(&L, n); for (i = 0; i < 26; i++) { L = L->next; printf("%c", L->data); } return 0; }