编辑代码

//2.3.1 双链表的定义
typedef struct DLinkNode
{
    ElemType data;
    struct DLinkNode * prior;                           //指向前驱结点
    struct DLinkNode * next;                            //指向后继结点
}DLinkNode                                              //声明双链表结点的类型

//2.3.2 采用头插法建立双链表
void CreateListF(DLinkNode * &L,ElemType a[],int n)
{
    DLinkNode * s;
    int i;
    L = (DLinkNode * )malloc(sizeof(DLinkNode));        //创建头结点
    L -> next = L -> prior = NULL;                      //建立一个空的双链表
    for(i = 0;i < n;i++)
    {
        s = (DLinkNode * )malloc(sizeof(DLinkNode));    //创建新结点
        s -> data = a[i];
        s -> next = L -> next;                          //将 s 插在表头
        if(L -> next != NULL)                           //双链表 L 非空时
            L -> next -> prior = s;
        L -> next = s;
        L -> prior = L;
    }
}

//2.3.3 采用尾插法建立双链表
void CreateListR(DLinkNode * &L,ElemType a[],int n)
{
    DLinkNode * s, * r;
    int i;
    L = (DLinkNode * )malloc(sizeof(DLinkNode));        //创建头结点
    r = L;                                              //r 始终指向尾结点
    for(i = 0;i < n;i++)
    {
        s = (DLinkNode * )malloc(sizeof(DLinkNode));    //创建新结点
        s -> data = a[i];
        r -> next = s;                                  //将结点 s 插入结点 r 之后
        s -> prior = r;
        r = s;
    }
    r -> next = NULL;                                   //尾结点 next 域置为 NULL
}

//2.3.4 查找指定元素值的结点
int LocateElem(DLinkNode * L,ElemType x)
{
    LinkNode * p = L -> next;
    int i = 1;
    while(p != NULL && p -> data != x)
    {
        i++;
        p = p -> next;
    }
    if(p == NULL)
        return 0;                                       //未找到时返回 0
    else
        return i;                                       //找到时返回其序号
}

//2.3.5 插入结点操作
s -> next = p -> next;                                  //将结点 s 插入结点 p 之后
p -> next -> prior = s;
s -> prior = p;
p -> next = s;

//      在双链表 L 中第 i 个位置上插入值域为 e 的结点的算法
int ListInsert(DLinkNode * &L,int i,ElemType e)
{
    int j = 0
    DLinkNode * p = L, * s;
    while(j < i - 1 && p != NULL)                       //查找第 i - 1 个结点
    {
        j++;
        p = p -> next;
    }
    if(p == NULL)                                       //未找到第 i - 1 个结点
        return 0;
    else                                                //找到第 i - 1 个结点 p
    {
        s = (DLinkNode * )malloc(sizeof(DLinkNode));
        s -> data = e;
        s -> next = p -> next;                          //将结点 s 插入到结点 p 之后
        if(p -> next != NULL)                           //若存在 p 的后继结点，将其前驱指向 s
            p -> next -> prior = s;
        s -> prior = p;
        p -> next = s;
        return 1;
    }
}

//2.3.6 删除结点的操作
p -> next = q -> next;
q -> next -> prior = p;

//      在双链表 L 中删除第 i 个结点的算法
int ListDelete(DLinkNode * &L,int i;ElemType &e)
{
    DLinkNode * p = L, * q;
    int j = 0;
    while(j < i - 1 && p != NULL)                       //查找第 i - 1 个结点
    {
        j++;
        p = p -> next;
    }
    if(p == NULL)                                       //不存在第 i - 1 个结点
        return 0;
    else                                                //找到第 i - 1 个结点 p
    {
        q = p -> next;                                  //q 指向要删除的结点
        if(q == NULL)                                   //不存在第 i 个结点
            return 0;
        p -> next = q -> next;                          //从双链表中删除结点 q
        if(p -> next != NULL)
            p -> next -> prior = p;
        free(q);                                        //释放结点 q
        return 1;
    }
}