数据结构之线性表（顺序表、单链表、双链表）（四）-阿里云开发者社区

双向链表
和单向链表相比有以下优势：
插入删除不需要移动元素外，可以原地插入删除
可以双向遍历
结构体定义如下：
typedef struct Node
{
DateType data;
struct Node *next,*prior;
}Node,*LinkList;
双向循环链表的操作实现：
在双向循环链表中，有如下指针关系：设指针p指向双向循环链表中的第i个结点，则p->next指向第i+1个结点，p->next->prior仍指向第i个结点，即p->next->prior==p；同样地，p->prior指向第i-1个结点，p->prior->next仍指向第i个结点，即p->prior->next==p。双向循环链表的上述指针关系可以方便算法设计。
双向循环链表指针关系
初始化
int InitList(DLNode **head)
{
*head = (DLNode *)malloc(sizeof(DlNode));
(*head)->prior = *head;
(*head)->next = *head;
return 1;
}
插入数据元素
和单链表相比，双向循环链表的插入算法指针p可以直接指在第i个结点上，而不需要让指针p指在第i-1个结点上。
双向循环链表的插入过程
删除数据元素
和单链表相比，双向循环链表的删除算法指针p可以直接指在第i个结点上，而不需要让指针p指在第i-1个结点上。
循环双向链表的删除过程
双向链表的C语言实现:
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
// 用到的库文件
#include <stdio.h>  // printf();scanf()
#include <stdlib.h> // exit()
#include <malloc.h> // malloc()
#include <time.h>   // srand((unsigned)time(NULL));
// 函数结果状态代码
#define TRUE    1
#define FALSE   0
#define OK      1
#define ERROR   0
#define INFEASIBLE  -1
#define OVERFLOW    -2
// Status是函数的类型，其值是函数结果状态代码
typedef int Status;
// #define ElemType int  // 也可以用宏定义确定ElemType类型
typedef int ElemType;
// -----双向链表-----
typedef struct  DuLNode {
    ElemType data;                  // 数据域
    struct DuLNode *prior;          // 指向前驱
    struct DuLNode *next;           // 指向后继
} DuLNode, *DuLinkList;
// 操作结果：构造一个空的线性表L。
Status InitList_DuL(DuLinkList &L) {
    if(L != NULL)
    {
        printf("线性表已存在！！！");
        return INFEASIBLE;          // 返回-1
    }
    L = (DuLinkList)malloc(sizeof(DuLNode));
    if(!L) {                        // 存储分配失败
        printf("初始化失败！！！");
        exit(OVERFLOW);             // exit(-2)程序异常退出
    }
    L->next = L;                    // 先建立一个带头结点的双向链表，
    L->prior = L;                   // 并使头结点2个指针域指向本身（即头指针L）
    return OK;
}// InitList_DuL
// 操作结果：销毁线性表L。
Status DestroyList_DuL(DuLinkList &L) {
    if(!L)
    {
        printf("线性表未初始化。");
        return INFEASIBLE;
    }
    DuLinkList p = L->next, ptmp;   // p指向线性表第一个结点(线性表为空表时，指向头结点)
    while(p != L) {                 // p指向头结点时，循环停止
        ptmp = p->next;
        free(p);                    // 释放每个数据结点的指针域
        p = ptmp;
    }
    free(L);                        // 释放头结点
    L = NULL;
    return OK;
}// DestroyList_DuL
// 操作结果：将L重置为空表。
Status ClearList_DuL(DuLinkList &L) {
    if(!L)
    {
        printf("线性表未初始化。");
        return INFEASIBLE;
    }
    if(L->next == L)
    {
        printf("线性表本已空！！！");
        return INFEASIBLE;
    }
    DuLinkList p = L->next, ptmp;   // p指向线性表第一个结点
    while(p != L) {                 // p指向头结点时，循环停止
        ptmp = p->next;
        free(p);                    // 释放每个结点的指针域
        p = ptmp;
    }
    L->next = L;                    // 头结点指针域指向本身
    return OK;
}// ClearList_DuL
// 操作结果：若L为空表，返回TRUE，否则返回FALSE
Status ListEmpty_DuL(DuLinkList L) {
    if(!L)
    {
        printf("线性表未初始化。");
        return INFEASIBLE;          // 返回-1
    }
    else if(L->next == L)
    {
        printf("线性表为空。");
        return TRUE;                // 返回1
    }
    else
    {
        printf("线性表非空。");
        return FALSE;               // 返回0
    }
}// ListEmpty_DuL
// 操作结果：返回L中数据元素个数。
int ListLength_DuL(DuLinkList L) {
    if(!L)
    {
        printf("线性表未初始化。");
        return INFEASIBLE;          // 返回-1
    }
    int nElem = 0;
    DuLinkList p = L->next;         // p指向第一个结点(空表时，指向头结点)
    while(p != L) {
        nElem ++;
        p = p->next;
    }
    return nElem;
}// ListLength
// 操作结果：用e返回L中第i个数据元素的值。1≤i≤ListLength(L) 。
Status GetElem_DuL(DuLinkList L, int i, ElemType &e) {
    if(!L) {
        printf("线性表未初始化。");
        return INFEASIBLE;          // 返回-1
    }
    DuLinkList p = L->next;         // p指向第一个结点(空表时，指向头结点)
    int j = 1;                      // j为计数器，统计当p指向第i个数据时，表中已有元素个数
    while ( (p->next != L) && j<i ) // 顺指针向后查找，直到p指向第i个元素或p指向头结点
    {
        p = p->next;
        ++j;
    }
    if ( p==L || j<i || i<1 )       // p == L 指向头结点，说明表为空表。j<i  i的值大于表中现有元素个数。  i<1  传入参数有问题。
    {
        return ERROR;               // 第i个元素不存在
    }
    e = p->data;                    // 取第i个元素
    return OK;
}// GetElem_DuL 算法2.8更改
// 操作结果：用p返回L中第i个数据元素的指针。1≤i≤ListLength(L)。
DuLinkList GetElemP_DuL(DuLinkList L, int i) {
    DuLinkList p = L;               // p指向头结点
    int j = 0;                      // j为计数器，统计当p指向第i个结点时，表中已有元素个数
    // p->next == L，表为空。i>j，超出查找范围
    while ( (p->next != L) && j<i ) // 顺指针向后查找，直到p指向第i个元素或p指向头结点
    {
        p = p->next;
        ++j;
    }
    if ( i<1 || i>j+1 )             // i>j+1  i的值大于表长+1。  i<1  传入参数有问题。
    {
        return NULL;                // i大于表长加1时，p=NULL
    }
    // 插入时：i=表长加1，返回头结点;
    if ( i==j+1 )
    {
        return L;
    }
    return p;                       // i<表长加1时，p指向第i个结点;
}// GetElem_DuL 更改
// 操作结果：返回L中第1个与e满足compare()(数据元素判定函数)的数据元素的位序，若这样的数据元素不存在，则返回值为0。
Status compare(ElemType listElem, ElemType e) {
    return listElem == e ? TRUE : FALSE;
}// Compare
int LocateElem_DuL(DuLinkList L, ElemType e, Status (*pfn_compare)(ElemType, ElemType)) {
    if(!L) {
        printf("线性表未初始化。");
        return INFEASIBLE;          // 返回-1
    }
    int pos = 1;
    DuLinkList p = L->next;         // p指向第一个结点(空表时，指向头结点)
    while( (p != L) && !(*pfn_compare)(p->data, e) ) {
        ++ pos;
        p = p->next;                // 指针后移p->next = L时，循环回到头结点
    }
    // p == L 指向头结点，说明表为空表。pos>ListLength_DuL(L)  pos的值大于表中现有元素个数。
    if( (p == L) || pos>ListLength_DuL(L) )
    {
        return ERROR;               // 返回0
    }
    return pos;
}// LocateElem_DuL
// 操作结果：若cur_e是L的数据元素，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
Status PriorElem_DuL(DuLinkList L, ElemType cur_e, ElemType &pre_e) {
    int i = LocateElem_DuL(L, cur_e, compare);
    // cur_e为第一个元素，其前驱为最后一个元素
    if(i==0 || i==1)
    {
        GetElem_DuL(L, ListLength_DuL(L), pre_e);
        return OK;
    }
    GetElem_DuL(L, i-1, pre_e);
    return OK;
}// PriorElem_DuL
// 操作结果：若cur_e是L的数据元素，则用next_e返回它的后继，否则操作失败，pre_e无定义。
Status NextElem_Sq(DuLinkList L, ElemType cur_e, ElemType &next_e) {
    int i = LocateElem_DuL(L, cur_e, compare);
    // cur_e为最后一个元素，其后继为第一个元素
    if(i==0 || i==ListLength_DuL(L))
    {
        GetElem_DuL(L, 1, next_e);
        return OK;
    }
    GetElem_DuL(L, i+1, next_e);
    return OK;
}// NextElem_Sq
// 操作结果：在L中第pos个位置插入新的元素e，L的长度加1。1≤pos≤ListLength(L)+1。
Status ListInsert_DuL(DuLinkList &L, int pos, ElemType e) {
    if(!L) {                        // 线性表是否存在
        printf("线性表未初始化。");
        return INFEASIBLE;
    }
    DuLinkList p, s;
    if( !(p = GetElemP_DuL(L, pos) ) ) { // 在L中确定插入位置指针p
        printf("插入位置不合法。");
        return ERROR;               // i等于表长加1时，p指向头结点;i大于表长加1时，p=NULL
    }
    if( !(s = (DuLinkList)malloc(sizeof(DuLNode)) ) ) {// 生成新结点
        printf("存储分配失败。");
        return ERROR;
    }
    s->data = e;                    // 将插入的元素值 赋给 新生成结点的数据域
    s->prior = p->prior;            // 插入结点 反向指向 前驱
    p->prior->next = s;             // 前驱 指向 插入结点
    s->next = p;                    // 插入结点 指向 后继
    p->prior = s;                   // 后继 反向指向 插入结点
    printf("插入的位置：%d, 插入的元素：%d", pos, e);
    return OK;
}// ListInsert_DuL 算法2.18更改
// 操作结果：删除L的第pos个数据元素，并用e返回其值,L的长度减1。1≤pos≤ListLength(L)。
Status ListDelete_DuL(DuLinkList &L, int pos, ElemType &e) {
    if(!L) {                        // 线性表是否存在
        printf("线性表未初始化。");
        return INFEASIBLE;
    }
    DuLinkList p;
    if( !(p = GetElemP_DuL(L, pos)) || p==L) { // 在L中确定第i个元素的位置指针p
        return ERROR;               // p=NULL或p=L时，即第pos个元素不存在
    }
    e = p->data;                    // 要删除结点的数据域，赋给e
    p->prior->next = p->next;       // 删除结点前驱 指向 删除结点后继
    p->next->prior = p->prior;      // 删除结点后继 指向 删除结点前驱
    free(p);                        // 释放指针变量p
    return OK;
}// ListDelete_DuL 算法2.19更改
// 操作结果：依次对L的每个数据元素调用函数visit()。一旦vistit()失败，刚操作失败。
Status visit(ElemType e) {
    printf("%d <-> ", e);
    return OK;
}
Status ListTraverse_DuL(DuLinkList L, Status (*pfn_visit)(ElemType)) {
    if(!L) {
        printf("线性表未初始化。");
        return INFEASIBLE;
    }
    if(L->next == L) {
        printf("线性表为空表。");
        return ERROR;
    }
    DuLinkList p = L->next;          // p指向第一个结点
    while(p != L) {
        visit(p->data);
        p = p->next;
    }
    return OK;
}// ListTraverse
// 创建随机表,包含10个随机数（头插法）。
void CreateList_DuL_10(DuLinkList &L) {
    // 提供随机数种子
    srand((unsigned)time(NULL));
    // 生成头结点
    L = (DuLinkList)malloc(sizeof(DuLNode));
    if(!L) {
        printf("存储分配失败！！！");
        exit(OVERFLOW);             // exit(-1)程序异常退出
    }
    L->next = L;                    // 头结点指针域指向本身
    L->prior = L;
    for (int i=0; i<10; i++) {      // 生成新结点
        DuLinkList p = (DuLinkList)malloc(sizeof(DuLNode));
        // scanf("%d", &p->data);      // 输入元素值 赋给新生成结点的数据域
        p->data = rand()%100;
        // 插入到表头
        p->next = L->next;          // 插入结点 指向 后继
        p->prior = L;               // 插入结点 反向指向 头结点
        L->prior->next = p;         // 后继 反向指向 插入结点
        L->next = p;                // 头结点 指向 插入结点
        //printf("%d ", p->data);     // 查看是否插入了新的元素
    }
}// CreateList_DuL_10
// 逆位序输入(随机产生)n个元素的值，建立带表头结点的线性表L（头插法）。
void CreateList_DuL_Head(DuLinkList &L, int n) {
    srand((unsigned)time(NULL));    // 初始化随机数种子
    // 先建立一个带头结点的单链表
    L = (DuLinkList)malloc(sizeof(DuLNode));
    if(!L) {
        printf("存储分配失败！！！");
        exit(OVERFLOW);             // exit(-1)程序异常退出
    }
    L->next = L;                    // 头结点指针域指向本身
    L->prior = L;
    L->data = 5201314;
    for (int i=n; i>0; --i) {
        DuLinkList p = (DuLinkList)malloc(sizeof(DuLNode));// 生成新结点
        // scanf("%d", &p->data);    // 输入元素值
        // 随机生成100以内的数字
        p->data = rand()%100;       // 将生成的元素值赋给新生成结点的数据域
        // p->data = i;             // 将生成的元素值赋给新生成结点的数据域
        // 插入到表头
        p->next = L->next;          // 插入结点 指向 第一个结点
        L->next->prior = p;         // 第一个结点 反向指向 插入结点
        p->prior = L;               // 插入结点 反向指向 头结点
        L->next = p;                // 头结点 指向 插入结点
    }
}// CreateList_DuL 算法2.11更改
// 顺位序输入(随机产生)n个元素的值，建立带表头结点的线性表L（尾插法）。
void CreateList_DuL_Tail(DuLinkList &L, int n) {
    srand((unsigned)time(NULL));    // 初始化随机数种子
    // 先建立一个带头结点的单链表
    L = (DuLinkList)malloc(sizeof(DuLNode));
    if(!L) {
        printf("存储分配失败！！！");
        exit(OVERFLOW);             // exit(-1)程序异常退出
    }
    L->next = L;                    // 头结点指针域指向本身
    L->prior = L;
    for (int i=0; i<n; ++i) {
        DuLinkList p = (DuLinkList)malloc(sizeof(DuLNode));
        // scanf("%d", &p->data);    // 输入元素值
        // 随机生成100以内的数字
        p->data = rand()%100;       // 将生成的元素值赋给新生成结点的数据域
        // 插入到表尾
        p->prior = L->prior;        // 插入结点 反向指向 表尾结点
        L->prior->next = p;         // 表尾结点 指向 插入结点
        p->next = L;                // 插入结点 指向 头结点
        L->prior = p;               // 头结点 反向指向 插入结点
    }
}
// 初始化菜单
void initMenu() {
    printf("\n\t\t*****************************************\n");
    printf("\n\t\t\t\t  循环双向链表\n");
    printf("\n\t\t  1.创建随机表\t\t  2.构造空线性表\n\t\t  3.销毁线性表\t\t  4.清空线性表\n\t\t  5.线性表是否为空\t  6.线性表的长度");
    printf("\n\t\t  7.查找表中元素\t  8.插入新元素\n\t\t  9.删除某个元素\t 10.遍历线性表\n\t\t 11.回到主菜单\t\t  0.退出");
}
// 回到主菜单
void mainMenu() {
    printf("\n\t\t*****************************************\n");
    printf("\n\t\t\t\t  循环双向链表\n");
    printf("\n\t\t  1.创建随机表\t\t  2.构造空线性表\n\t\t  3.销毁线性表\t\t  4.清空线性表\n\t\t  5.线性表是否为空\t  6.线性表的长度");
    printf("\n\t\t  7.查找表中元素\t  8.插入新元素\n\t\t  9.删除某个元素\t 10.遍历线性表\n\t\t 11.回到主菜单\t\t  0.退出");
}
int main() {
    DuLinkList L = NULL;
    initMenu();
    int select = -1;
    while(select != 0)
    {
        printf("\n\n请选择你的操作：");
        scanf("%d", &select);
        switch(select)
        {
        case 1:// 创建随机表
          {  
          int nCreateOption = -1;
          while(nCreateOption!=0 && nCreateOption!=11)
          {
            printf("\n1.头插法  2.尾插法  3.10个元素的随机表  11.回到主菜单  0.退出查找\n请选择你的操作：");
      scanf("%d", &nCreateOption);
      switch(nCreateOption)
        {
                 case 1:// 1.头插法
     {
       printf("请输入要创建的随机表元素个数：");
       int nElem;
       scanf("%d", &nElem);
       CreateList_DuL_Head(L, nElem);
       printf("头插法创建随机链表：");
             ListTraverse_DuL(L, visit);
           }
          break;
    case 2:// 2.尾插法
    {
      printf("请输入要创建的随机表元素个数：");
      int nElem;
      scanf("%d", &nElem);
      CreateList_DuL_Tail(L, nElem);
            printf("尾插法创建随机链表：");
                  ListTraverse_DuL(L, visit);
          }
    break;
          case 3:// 3.10个元素的随机表
          CreateList_DuL_10(L);
          printf("10个元素的随机表：");
          ListTraverse_DuL(L, visit);
    break;
          case 11:// 11.回到主菜单
          mainMenu();
    break;
    case 0:// 0.退出查找
          break;
    default:
    printf("请输入正确的数字!!!\n");
    break;
          }
      }
        }
            break;
        case 2:// 构造空线性表
            printf("构造一个空的线性表L。");
            InitList_DuL(L);
            break;
        case 3:// 销毁线性表
            printf("销毁线性表L。");
            DestroyList_DuL(L);
            break;
        case 4:// 清空线性表
            printf("将L重置为空表。");
            ClearList_DuL(L);
            break;
        case 5:// 线性表是否为空
            ListEmpty_DuL(L);
            break;
        case 6:// 线性表的长度
            {
                int lLength = ListLength_DuL(L);
                if(lLength != -1) printf("线性表的长度为: %d ", lLength);
            }
            break;
        case 7:// 查找表中元素
            {
                int nSearchOption = -1;
                while(nSearchOption!=0 && nSearchOption!=11)
                {
                    printf("1.按位置查找\t  2.按元素查找\t  11.回到主菜单\t  0.退出查找\n请选择你的操作：");
                    scanf("%d", &nSearchOption);
                    switch(nSearchOption)
                    {
                    case 1:// 1.按位置查找
                        {
                            int pos;
                            ElemType e;
                            printf("请输入要查找的位置：");
                            scanf("%d", &pos);
                            int ret = GetElem_DuL(L, pos, e);
                            if (ret == -1) {
                                printf("\n");
                                break;
                            } else if (ret == 0) {
                                printf("查找位置不正确！\n");
                                break;
                            }
                            printf("第%d个元素的值为：%d ", pos, e);
                            ElemType pre_e, next_e;
                            if(PriorElem_DuL(L, e, pre_e))
                                printf("前一个元素为：%d ", pre_e);
                            if(NextElem_Sq(L, e, next_e))
                                printf("后一个元素为：%d", next_e);
                            printf("\n");
                        }
                        break;// 2.按元素查找
                    case 2:
                        {
                            printf("请输入要查找的元素：");
                            ElemType e;
                            scanf("%d", &e);
                            int pos = LocateElem_DuL(L, e, compare);
                            if (pos == -1) {
                                printf("\n");
                                break;
                            } else if (pos == 0) {
                                printf("没有值为%d的元素。\n", e);
                                break;
                            }
                            printf("值为%d是表中的第%d个元素。\n", e, pos);
                        }
                        break;
                    case 11:// 11.回到主菜单
                        mainMenu();
                        break;
                    case 0:// 0.退出查找
                        break;
                    default:
                        printf("请输入正确的数字!!!\n");
                        break;
                    }
                }
            }
            break;
        case 8:// 插入新元素
            {
                ElemType e;
                int pos;
                int nInsertOption = -1;
                while(nInsertOption)
                {
                    printf("请输入要插入的元素位置和元素的值：");
                    scanf("%d %d", &pos, &e);
                    int ret = ListInsert_DuL(L, pos, e);
                    // 线性表未初始化，中断循环，回到主界面
                    if(ret == -1)
                        break;
                    // 插入位置不合法，结束本次循环，继续下次循环
                    else if(!ret)
                    {
                        printf("\n");
                        continue;
                    }
                    // 插入元素
                    printf("\n现在线性表为：");
                    ListTraverse_DuL(L, visit);
                    printf("\n1.是  0.否  是否继续: ");
                    scanf("%d", &nInsertOption);
                }
            }
            break;
        case 9:// 删除某个元素
            {
                int nDeleteOption = -1;
                while(nDeleteOption!=0 && nDeleteOption!=11)
                {
                    printf("1.按位置删除\t  2.按元素删除\t  11.回到主菜单\t  0.退出删除\n请选择你的操作：");
                    scanf("%d", &nDeleteOption);
                    switch(nDeleteOption)
                    {
                    case 1: // 1.按位置删除
                        {
                            ElemType e;
                            int pos;
                            printf("请输入要删除的位置：");
                            scanf("%d", &pos);
                            int ret = ListDelete_DuL(L, pos, e);
                            if (ret == -1) {
                                printf("\n");
                                break;
                            } else if (ret == 0) {
                                printf("删除位置不正确！\n");
                                break;
                            }
                            printf("现在线性表为：");
                            ListTraverse_DuL(L, visit);
                            printf("\n");
                        }
                        break;
                    case 2: // 2.按元素删除
                        {
                            printf("请输入要删除的元素：");
                            ElemType e;
                            scanf("%d", &e);
                            // 删除的将是第一个出现的元素
                            int pos = LocateElem_DuL(L, e, compare);
                            if (pos == -1) {
                                printf("\n");
                                break;
                            } else if (pos == 0) {
                                printf("没有值为%d的元素。", e);
                                break;
                            }
                            printf("值为%d是表中的第%d个元素。", e, pos);
                            ListDelete_DuL(L, pos, e);
                            printf("\n现在线性表为：");
                            ListTraverse_DuL(L, visit);
                            printf("\n");
                        }
                        break;
                    case 11:// 11.回到主菜单
                        mainMenu();
                        break;
                    case 0:// 0.退出查找
                        break;
                    default:
                        printf("请输入正确的数字!!!\n");
                        break;
                    }
                }
            }
            break;
        case 10:// 遍历线性表
            printf("遍历线性表：");
            ListTraverse_DuL(L, visit);
            break;
        case 11:// 回到主菜单
            mainMenu();
            break;
        case 0:// 退出
            break;
        default:
            printf("请输入正确的数字!!!");
            break;
        }
    }
    return 0;
}
数据结构之线性表（顺序表、单链表、双链表）（四）

热门文章

最新文章

相关课程

相关电子书
