03_线性表

数据结构和算法

3.1 定义

• 线性表：由零个或多个数据源元素组成的有限序列
• 前驱：直接前驱元素，第一个数据元素无前驱
• 后继：直接后继元素，最后一个数据元素无后继
• 其他元素有且仅有一个前驱和后继
• 线性表元素的个数n(n>=0)定义为线性表的长度，当n=0时，称为空表

3.2 抽象数据类型

• 把数据类型和相关操作捆绑在一起
• 描述抽象数据类型的标准格式：

ADT 抽象数据类型
Data
    数据元素之间逻辑关系的定义
Operation
    操作
endADT 

3.2.1 线性表的抽象数据类型

ADT 线性表（List）
Data
    线性表的数据对象集合为{a1,a2...,an}，每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且仅有一个直接前驱元素，除了最后一个元素an外，每一个元素有且仅有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
    InitList(*L)：初始化操作，建立一个空的线性表L。
    ListEmpty(L)：判断线性表是否为空表，若线性表为空，返回true，否则返回false。
    ClearList(*L)：将线性表清空。
    GetElem(L,i,*e)：将线性表L中的第i个位置元素值返回给e。
    Locate(L,e)：在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则， 返回0表示失败。
    ListInsert(*L,i,e)：在线性表L中第i个位置插入新元素e。
    ListDelete(*L,i,*e)：删除线性表L中第i个位置元素，并用e返回其值。
    ListLength(L)：返回线性表L的元素个数。
endADT 

例 求两个集合的并集

// La表示集合A，Lb表示集合B
void unionL(List *La, List Lb) 
{
    int La_len,Lb_len,i;
    ElemType e;
    La_len = ListLength(*La);
    Lb_len = ListLength(Lb);
    for(i=1;i<=Lb_len;i++)
    {
        GetElem(Lb,i,&e);
        if (!LocateElem(*La,e))
        {
            ListInsert(La,++La_len,e);
        }
    }
}

3.3 线性表的顺序存储结构

• 指的是用一段地址连续的存储单元依次存储线性表的数据元素

• 线性表顺序存储的结构代码：

#define MAXSIZE 20
typedef int ElemType;
typedef struct 
{
    ElemType data[MAXSIZE];
    int length; //线性表当前长度 
} SqList;

3.3.1 地址计算方法

• 线性表从1开始计数
• 假设ElemType占用的是c个存储单元（字节），那么线性表中第i+1个数据元素和第i个数据元素的存储位置的关系是（LOC表示获得存储位置的函数）
• LCO(ai+1) = LCO(ai) + c
• 所以，LCO(ai) = LCO (a1) + (i-1)*c
• 通过这个公式，可随时计算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么它的存储时间性能为O(1)，通常称为随机存储时间。

3.3.2 获得元素操作

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//Status 是函数的类型，其值是函数结果状态代码，如OK等
//初始条件，顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果，用e返回L中第i个数据元素的值
Status GetElem(SqList L, int i, ElemType *e) 
{
    if (L.length==0 || i<1 || i>L.length)
    {
        return ERROR;
    }
    *e = L.data(i-1);
    return OK;
}

3.3.3 插入操作

• 插入算法的思路
  
  • 如果插入位置不合理，抛出异常；
  • 如果线性表长度大于等于数组长度，则抛出异常或动态增加数组容量；
  • 从最后一个元素开始向前遍历到第i个位置，分别将他们都向后移一个位置；
  • 将要插入的元素填入位置i处；
  • 线性表长度+1。
• 实现代码

//初始条件，顺序线性表L已存在，1<=i<=ListLength(L).
//操作结果：在L中第i个位置之前插入新的数据元素e，L长度+1.
Status ListInsert（SqList *L, int i, ElemType e)
{
    int k;
    if (L->length == MAXSIZE)
    {
        return ERROR;
    }
    if (i<1 || i>L->length+1)
    {
        return ERROR;
    }
    if (i<=L->length)
    {
        for(k=L->length-1;k>=i-1;k--) {
            L->data[k+1] = L->data[k];
        }
    }
    L->data[i-1] = e;
    L->Length++;
    return OK;
 } 

3.3.4 删除操作

//初始条件，顺序线性表L已存在，1<=i<=ListLength(L).
//操作结果：删除L的第i个数据元素，并用e返回其值，L长度-1. 
Status ListDelete(SqList *L, int i, ElemType *e)
{
    int k;
    if (L->length == 0)
    {
        return ERROR;
    }
    if (i<1 || i>L->length)
    {
        return ERROR;
    }
    *e = L->data[i-1];
    if (i<L->length)
    {
        for(k=i;k<L->length;k++)
        {
            L->data[k-1] = L->data[k];
        }
    }
    L->length--;
    return OK;
}

3.3.5 插入和删除操作的时间复杂度

• 最好的情况：插入和删除操作刚好要求在最后一个位置上操作，因为不需要移动任何元素，所以此时的时间复杂度为O(1)
• 最坏的情况：如果要插入和删除的位置是第一个元素，那就意味着要移动所有的元素向后或者向前，所以这个时间复杂度为O(n)
• 至于平均情况，就取中间值O((n-1)/2)，简化后还是O(n)

3.3.6 线性表顺序存储结构的优缺点

• 特征

  • 线性表顺序存储结构的优缺点，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)。而在插入、删除时，时间复杂度都是O(n)
  • 这就说明，它比较适合元素个数比较稳定，不经常插入和删除元素，而更多的操作是存取数据的应用

• 优点

  • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速的存取表中任意位置的元素

• 缺点

  • 插入和删除操作需要移动大量元素
  • 当线性表的长度变化较大时，难以确定存储空间的容量
  • 容易造成存储结构的“碎片”

3.4 线性表的链式存储结构

3.4.1 定义

• 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置
• 链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址（指针）
• 存储数据元素信息的域称为数据域，存储直接后继元素位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像，称为结点（Node）
• n个结点链接成一个链表，即为线性表（a1,a2,...,an）的链式存储结构
• 因为此链表的每个结点中只包含一个指针域，所以叫做单链表

3.4.2 单链表

• 链表中的第一个结点的存储位置叫做头指针，最后一个结点指针为空（Null）

3.4.2.1 头指针与头结点的异同

• 头指针

  • 头指针是指向链表指第一个结点的指针，若链表有头结点，则是指向头结点的指针
  • 头指针具有标识作用，所以常用头指针冠以链表的名字（指针变量的名字）
  • 无论链表是否为空，头指针均不为空
  • 头指针是链表的必要元素

• 头结点

  • 头结点的数据域一般不存储任何信息
  • 头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义（也可以用来存放链表的长度）
  • 有了头结点，对在第一元素结点前插入结点的和删除第一结点操作与其他结点的操作就统一了
  • 头结点不一定是链表的必须元素

3.4.2.2 单链表的存储结构

typedef struct Node
{
    ElemType data;//数据域
    struct Node* Next;//指针域
} Node;
typedef struct Node* LinkList;

3.4.2.3 单链表的读取

• 获得链表第i个数据的算法思路

  • 声明一个结点P指向链表第一个结点，初始化j从1开始；
  • 当j
  • 若到链表末尾P为零，则说明第i个元素不存在；
  • 否则查找成功，返回结点P的数据。

• 实现代码

Status GetElem(LinkList L, int i, ELemType *e)
{
    int j;
    LinkList p;
    P = L->next;
    j = 1;
    while(p && j<i)
    {
        p = p->next;
        ++j;
    }
    if (!p || j>i) 
    {
        return ERROR;
    }
    *e = p->data;
    return OK;
}

• 最坏情况的时间复杂度为O(n)

3.4.2.4 单链表的插入

• 单链表第i个数据插入结点的算法思路

  • 声明一个结点P指向链表第一个结点，初始化j从1开始；
  • 当j
  • 若到链表末尾P为零，则说明第i个元素不存在；
  • 否则查找成功，在系统生成一个空结点S；
  • 将数据元素e复制给s->data；
  • 单链表插入两个标准语句
    
    • s->next = p->next;
    • p->next = s;
  • 返回成功。

• 实现代码

Status ListInsert(LinkList *L, int i, ELemType e)
{
    int j;
    LinkList p;
    P = *L;
    j = 1;
    while(p && j<i)
    {
        p = p->next;
        ++j;
    }
    if (!p || j>i) 
    {
        return ERROR;
    }
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

3.4.2.5 单链表的删除

• 单链表第i个数据删除结点的算法思路

  • 声明一个结点P指向链表第一个结点，初始化j从1开始；
  • 当j
  • 若到链表末尾P为零，则说明第i个元素不存在；
  • 否则查找成功，将欲删除结点p->next赋值给q:
  • 单链表的删除标准语句
    
    • q = p->next;
    • p->next = q->next;
    • p->next = p->next->next;
  • 将q结点中的数据赋值给e，作为返回
  • 释放q结点

• 实现代码

Status ListDelete(LinkList *L, int i, ELemType *e)
{
    int j;
    Linklist p,q;
    p = *L;
    j = 1;
    while(p->next && j<i)
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j>i)
    {
        return ERROR;
    }
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return OK;
}

3.4.2.6 单链表的整表创建

• 算法思路
  
  • 声明一结点P和计数器变量i；
  • 初始化一空链表L；
  • 让L的头结点的指针指向Null，即建立一个带头结点的单链表；
  • 循环实现后继结点的赋值和插入

3.4.2.7 头插法建立单链表

• 头插法从一个空表开始，生成新结点，读取数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止
• 实现代 码

void CreateListHead(LinkList *L, int n)
{
    LinkList p;
    int i;
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    for(i=0; i<n; i++) 
    {
        p = (LinkList)malloc(sizeof(Node));
        p->data = rand()%100+1;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

3.4.2.8 尾插法建立单链表

• 实现代码

void CreateListTail(LinkList *L, int n)
{
    LinkList p, r;
    int i;
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));
    r = *L;
    for(i=0; i<n; i++) 
    {
        p = (Node*)malloc(sizeof(Node));
        p->data = rand()%100+1;
        r->next = p;
        r = p;
    }
    r->next = NULL;
}

3.4.2.9 单链表的整表删除

• 算法思路
  
  • 声明结点p和q；
  • 将第一个结点赋值给p，下一结点赋值给q；
  • 循环执行释放p和将q赋值给p的操作；
• 实现代码

Status ClearList(LinkList *L)
{
    LinkList p, q;
    p = (*L)->next;
    while(p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    return OK;
}

3.4.2.10 单链表结构与顺序存储结构优缺点

• 存储分配方式：

  • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
  • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

• 时间性能：

  • 查找

    • 顺序存储结构O(1)
    • 单链表O(n)

  • 插入和删除

    • 顺序存储结构需要移动平均移动表长一半的元素，时间为O(1)

  • 空间性能

    • 顺序存储结构需要预分配存储空间，分大了，容易造成空间浪费，分小了，容易发生溢出
    • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

• 综上所述，得出一些经验性结论

  • 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构
  • 若需要频繁插入和删除时，宜采用单链表结构
  • 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构。这样可以不需要考虑存储空间的大小问题
  • 而如果事先知道线性表的大致长度，用顺序存储结构效率会高很多

3.4.3 静态链表

• 用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法
• 线性表的静态链表存储结构

#define MAXSIZE 1000
typedef struct 
{
    ElemType data; //数据
    int cur； //游标（cursor)
} Component, StaticLinkList [MAXSIZE];

• 对静态链表进行初始化相当于初始化数组：

Status InitList(StaticLinkList space)
{
    int i;
    for(i=0; i<MAXSIZE-1; i++)
    {
        space[i].cur = i+1;
    }
    space[MAXSIZE-1].cur = 0;
    return OK;
}

• 总结
  
  • 对数组的第一个和最后一个元素做特殊处理，它们的data不存放任何数据
  • 我们通常把未使用的数组元素称为备用链表
  • 数组的第一个元素，即下标为0的那个元素的cur就存放备用链表的第一个结点的下标
  • 数组的最后一个元素，即下标为MAXSIZE-1的cur则存放第一个有数组的元素的下标，相当于单链表中的头结点作用

3.4.3.1 静态链表的插入操作

• 实现代码
• 首先是获得空闲分量的下标

int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur;
    if(space[0].cur)
    {
        space[0].cur = space[i].cur;//把它的下一个分量用来作为备用
    }
    return i;
}

//在静态链表L中第i=2个元素之前插入新的数据元素e
Status ListInsert(StaticLinkList L, int i, ElemType e)
{
    int j, k, l;
    k = MAXSIZE-1;
    if(i<1 || i>ListLength(L)+1)
    {
        return ERROR;
    }
    j = Malloc_SLL(L);
    if(j)
    {
        L[j].data = e;
        for(l=1; l<=i-1; l++)
        {
            k = L[k].cur;
        }
        L[j].cur = L[k].cur;
        L[k].cur = j;
        return OK;
    }
    return ERROR                    ;
}

3.4.3.2 静态链表的删除操作

//删除在L中的第i个数据元素
Status ListDelete(StaticLinkList L, int i)
{
    int j, k;
    k = MAXSIZE-1;
    if(i<1 || i>ListLength(L))
    {
        return ERROR;
    }
    for(j=1; j<=i-1; j++)
    {
        k = L[k].cur;
    }
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SLL(L,j);
    return OK;
}
//将下标为k的空闲结点回收到备用链表
void Free_SLL(StaticLinkList space, int k)
{
    space[k].cur = space[0].cur;
    space[0].cur = k;
}
//返回L中数据元素个数
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE-1].cur;
    while(i)
    {
        i = L[i].cur;
        j++
    }
    return j;
} 

3.4.3.3 静态链表优缺点总结

• 优点

  • 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点

• 缺点

  • 没有解决连续存储分配（数组）带来的表长难以确定的问题
  • 失去了顺序存储结构随机存取的特性

• 总的来说，静态链表其实是为了给没有指针的编程语言设计的一种实现单链表的方法

• 尽管我们可以用单链表就不要静态链表了，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需

3.4.4 单链表小结腾讯面试题

题目：快速找到未知长度单链表的中间结点并显示

Status GetMidNode(StaticLinkList L, ElemType *e)
{
    LinkList search, mid;
    mid = search = L;
    while(search->next != NULL)
    {
        //search移动的速度是mid的2倍
        if(search->next->next != NULL)
        {
            search = search->next->next;
            mid = mid->next;
        }
        else
        {
            search = search->next;
        }
    }
    *e = mid->data;
    return OK;
}

3.4.5 循环链表

• 将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表
  注：并不是说循环链表一定要有头结点

• 其实循环链表和单链表的主要差异就在于循环的判断空链表的条件上。原来判断head->next是否为null，现在则是head->next是否等于head

3.4.5.1 初始化循环链表

//初始化循环链表
void ds_init(node **pNode)
{
    int item;
    node *temp;
    node *target;
    printf("输入结点的值，输入0完成初始化\n");
    while(1)
    {
        scanf("%d", &item);
        fflush(stdin);
        if(item==0)
        {
            return;
        }
        if((*pNode)==NULL)
        {
            //循环链表中只有一个结点
            *pNode = (node*)malloc(sizeof(struct CLinkList));
            if(!(*pNode))
            {
                exit(0);
            }
            (*pNode)->data = item;
            (*pNode)->next = *pNode;
        }
        else
        {
            //找到next指向第一个结点的结点
            for(target = (*pNode); target->next != (*pNode); target = target->next)
                ;
            //生成一个新的结点
            temp = (node*)malloc(sizeof(struct CLinkList));
            if(!temp)
            {
                exit(0);
            }
            temp->data = item;
            temp->next = *pNode;
            target->next = temp;
        }
    }
}

3.4.5.2 插入结点

//链表存储结构的定义
typedef struct CLinkList
{
    int data;
    struct CLinkList *next;
}node;
//插入结点
//参数：链表的第一个结点，插入的位置
void ds_insert(node **pNode, int i)
{
    node *temp;
    node *target;
    node *p;
    int item;
    int j = 1;
    printf("输入要插入结点的值：");
    scanf("%d", &item);
    if(i==1)
    {
        //新插入的结点作为第一个结点
        temp = (node*)malloc(sizeof(struct CLinkList));
        if(!temp)
        {
            exit(0);
        }
        temp->data = item;
        //寻找到最后一个结点
        for(target = (*pNode); target->next != (*pNode); target = target->next)
            ;
        temp->next = (*pNode);
        target->next = temp;
        *pNode = temp;
    }
    else
    {
        target = *pNode;
        for(; j<(i-1); ++j)
        {
            target = target->next;
        }
        //target指向第三个元素的
        temp = (node*)malloc(sizeof(struct CLinkList));
        if(!temp)
        {
            exit(0);
        }   
        temp->data = item;
        p = temp->next;
        target->next = temp;
        temp->next = p;
    }
}

3.4.5.3 删除结点

//删除结点
void ds_delete(node **pNode, int i)
{
    node *target;
    node *temp;
    int j = 1;
    if(i==1)
    {
        //删除的是第一个结点
        //找到的是最后一个结点
        for(target = *pNode; target->next != *pNode; target = target->next)
            ;
        temp = *pNode;
        *pNode = (*pNode)->next;
        target->next = *pNode;
        free(temp);
    }
    else 
    {
        target = *pNode;
        for(; j < i-1; ++j)
        {
            target = target->next;
            target->next = temp->next;
            free(temp);
        }
    }
}

3.4.5.4 返回结点所在位置

//返回结点所在位置
int ds_search(node *pNode, int elem)
{
    node *target;
    int i = 1;
    for(target = pNode; target->data != elem && target->next != pNode; ++i)
    {
        target = target->next;
    }
    if(target->next == pNode)//表中不存在该元素
        return 0;
    else
        return i;
}

3.4.6 约瑟夫环

• 用循环链表模拟约瑟夫问题，把41个人自杀的顺序编号输出

//n个人围圈报数，报m出列，最后剩下的是几号？
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node *next;
} node;
node *create(int n)
{
    node *p = NULL, *head;
    head = (node*)malloc(sizeof(node));
    p = head;
    node *s;
    int i = 1;
    if(0 != n)
    {
        while (i<=n)
        {
            s = (node *)malloc(sizeof(node));
            s->data = i++;
            p->next = s;
            p = s;
        }
        s->next = head->next;
    }
    free(head);
    return s->next;
}
int main()
{
    int n = 41;
    int m = 3;
    int i;
    node *p = create(n);
    node *temp;
    m %= n;
    while(p!=p->next)
    {
        for(i=1; i<m-1; i++)
        {
            p = p->next;
        }
        printf("%d->", p->next->data);
        temp = p->next;
        p->next = temp->next;
        free(temp);
        p = p->next;
    }
    printf("%d\n", p->data);
    return 0;
}

3.4.7 连接A、B两个循环链表为一个循环链表

// 假设A，B为非空循环链表的尾指针
LinkList Connect(LinkList A, LinkList B) 
{
    LinkList p = A->next; //保存A表的头结点位置 
    A->next = B->next->next; //B表的开始结点链接到A表尾
    free(B->next); //释放B表的头结点
    B->next = p;
    return B; //返回新循环链表的尾指针 
}

3.4.8 判断单链表是否有环

• 法一：使用p,q两个指针，p总是往前走，但q每次都从头开始走，对于每个结点，看p走的步数是否和q一样

//比较步数的方法
int HasLoop1(LinkList L) 
{
    LinkList cur1 = L; //定义结点 cur1
    int pos1 = 0; // cur2 的步数
    while(cur1)
    {   //cur1 结点存在
        LinkList cur2 = L; //定义结点 cur2
        int pos2 = 0; // cur2 的步数
        while(cur2)
        {   //cur2 结点不为空
            if(cur2 == cur1)
            {   //当cur1和cur2到达相同结点时，走过的步数一样，说明没有环
                if(pos1 == pos2)
                    break;
                else
                {
                    printf("环的位置在第%d个结点处\n", pos2);
                    return 1; //有环并返回1
                }
            }
            cur2 = cur2->next; //如果发现没有环，继续下一个结点
            pos2++; //cur2步数自增
        }
        cur1 = cur1->next; //cur1继续向后一个结点
        pos1++; //cur1步数自增
    } 
    return 0;
}

• 法二：使用p,q两个指针，p每次向前走一步，q每次向前走两步，若在某个时候p==q，则存在环

//利用快慢指针的方法
int HasLoop2(LinkList L) 
{
    int step1 = 1;
    int step2 = 2；
    LinkList p = L; 
    LinkList q = L; 
    while(p != NULL && q != NULL && q->next != NULL)
    {   
        p = p->next;
        if(q->next != NULL)
            q = q->next->next;
        printf("p:%d, q:%d \n", p->data, q->data);
        if(p==q)
            return 1;
    } 
    return 0;
}

3.4.9 魔术师发牌问题

#include <stdio.h>
#include <stdlib.h>
#define CardNumber 13
typedef struct node
{
    int data;
    struct node *next;
} sqlist, *linklist;
linklist CreateLinkList()
{
    linklist head = NULL;
    linklist s, r;
    int i;
    r = head;
    for(i=1; i<=CardNumber; i++)
    {
        s = (linklist)malloc(sizeof(sqlist));
        s->data = 0;
        if(head == NULL)
            head = s;
        else 
            r->next = s;
        r = s;
    }
    r->next = head;
    return head;
}
//发牌顺序计算
void Magician(linklist head)
{
    linklist p;
    int j;
    int countnumber = 2;
    p = head;
    p->data = 1; //第一张牌放1
    while(1)
    {
        for(j=0; j<countnumber; j++)
        {
            p = p->next;
            if(p->data != 0) //该位置有牌的话，则下一个位置
            {
                p->next;
                j--;
            }
        }
        if(p->data == 0)
        {
            p->data = countnumber;
            countnumber++;
            if(countnumber == 14)
                break;
        }
    }
}
int main()
{
    linklist p;
    int i;
    p = CreateLinkList();
    Magician(p);
    printf("按如下顺序排列： \n");
    for(i=0; i<CardNumber; i++)
    {
        printf("黑桃%d ", p->data);
        p = p->next;
    }
    return 0;
}

3.4.10 双向链表

3.4.10.1 双向链表结点结构

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

3.4.10.2 双向链表的插入操作

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

3.4.10.3 双向链表的删除操作

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);

3.4.11 Caesar

#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)->prior = (*L)->next = 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("请输入一个整数：");
    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;
}