数据结构之线性表

 关注
发布于: 2020 年 09 月 27 日
1 线性表的基本概念对于同一个线性表，其每一个数据元素的值虽然不同，但必须具有相同的数据类型；
数据元素之间具有一种线性的或“一对一”的逻辑关系；
第一个数据元素没有前驱，这个数据元素被称为开始节点；
最后一个数据元素没有后继，这个数据元素被称为终端节点；
除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继；
2 线性表抽象数据类型描述基本操作如下：
线性表的置空操作clear()：将一个已经存在的线性表置为空表；
线性表判空操作isEmpty()：判断线性表是否为空，若为空，则返回true；否则，返回为false；
求线性表的长度操作length()：求线性表中的数据元素的个数并返回其值；
取元素操作get(i)：读取并返回线性表中的第i个数据元素的值。其中i的取值范围为0≤i≤length()-1；
插入操作insert(i,x)：在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i的取值范围为0≤i≤length()。当i=0时，在表头插入x；当i=length()时，在表尾插入x；
删除操作remove(i)：删除并返回线性表中第i个数据元素。其中i的取值范围为0≤i≤length()-1；
查找操作indexOf(x)：返回线性表中首次出现的指定的数据元素的位序号，若线性表中不包含此数据元素，则返回-1；
3 线性表的顺序表示和实现3.1 顺序表的定义所谓顺序表就是顺序存储的线性表。顺序存储是用一组地址连续的存储单元依次存放线性表中各个元素的存储结构。
3.2 顺序表的特点在线性表中逻辑上相邻的数据元素，在物理存储上也是相邻的；
存储密度高，但要预先分配“足够应用”的存储空间，这可能会造成存储空间的浪费；
便于随机存储；
不便于插入和删除操作，这是因为在顺序表上进行的插入和删除操作会引起大量数据元素的移动；
3.3 顺序存储结构类的描述
顺序表的存储结构示意图
为了用C语言描述上图的顺序表，定义结构体SeqList如下：
typedef struct
{
  DateType data[MAXSIZE];  /*数组存储数据元素*/
  int size;        /*线性表当前长度*/
}SqList;
【说明】：其中，DataType为数组元素（即数据元素）的数据类型，MaxSize表示数组的最大元素个数，list表示顺序表的数组成员，size表示顺序表中当前存储的数据元素个数成员，且必须满足条件size≤MaxSize，SeqList是结构体名。
3.4 顺序表操作的实现在顺序存储结构下，线性表抽象数据类型定义的各个操作的具体实现方法如下：
初始化ListInitiate(L)
void ListInitiate(SeqList *L)    //初始化顺序表L
 {
     L->size = 0;  //定义初始化数据元素个数
 }
【说明】由于函数中要改变参数L的size域的值，所以参数L应设计为输出型参数，即参数L设计为SeqList的指针类型。否则，size域的修改值将不能带回去。
求当前数据元素个数ListLength(L)
int ListInitiate(SeqList L)    //返回顺序表L的当前数据元素个数
{
    return L.size;
}
插入数据元素ListInsert(L, i, x)
顺序表插入过程
代码实现：
int ListInsert(SqList *L, int i, DateType x)
{
  int k;
  if (L->size== MAXSIZE)  /*顺序线性表已满*/
  {
    printf("顺序表已满无法插入！\n");
    return 0;
  }
  if (i<1 || i>L->size)  /*i不在范围内*/
  {
    return 0;
  }
  if (i <= L->size-1)  /*插入位置不在表尾*/
  {
    //从后向前依次后移数据，为插入做准备
    for (k = L->size; k >=i-1 ; k--)
    {
      L->list[k] = L->list[k-1];
    }
  }
  L->list[i] = x;    //插入x
  L->size++;         //元素个数加1
  return 1;
}
【说明】：
如果线性表长度大于等于数组长度，抛出异常
如果插入位置不合理，抛出异常
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置
表长加1
删除数据元素ListDelete(L, i, x)
顺序表删除过程
代码实现：
int ListDelete(SequenceList *L, int i, DateType *x)
{
/*删除顺序表L中位置i（0 ≤ i ≤ size - 1）的数据元素值并存放到参数x中*/
/*删除成功返回1，删除失败返回0*/
    int j;
    if(L->size <= 0)
    {
        printf("顺序表已空无数据元素可删! \n");
        return 0;
    }
    else if(i < 0 || i > L->size-1)
    {
        printf("参数i不合法");
        return 0;
    }
    else
    {
        *x = L->list[i];  //保存删除的元素到参数x中
         //从i位置的后一位开始，依次往前移一位，直到最后
        for(j = i+1; j <= L->size-1; j++)
        {
          L->list[j-1] = L->list[j];
        }
        L->size--;        //数据元素个数减1
        return 1;
    }
}
﻿
【说明】：
如果为空表，抛出异常
如果删除位置不合理，抛出异常
从删除元素位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置
表长减1
取数据元素ListGet(L, i, x)
/*取顺序表L中第i个数据元素的值存于x中，成功则返回1，失败返回0*/
int ListGet(SequenceList L, int i, DateType *x)
{
    if(i < 0 || i > L.size-1)
    {
        printf("参数i不合法! \n");
        return 0;
    }
    else
    {
        *x = L.list[i];
        return 1;
    }
}
实例设计1、编程实现如下任务：建立一个线性表，首先依次输入数据元素1, 2, 3,…,10，然后删除数据元素5，最后依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个。要求使用顺序表。
#include<stdio.h>
#define MaxSize 100
typedef int ElemType;
#include"sequencelist.h"
void main(void)
{
    SequenceList myList; //声明
    
    int i, x;
    ListInitialize(&myList); //初始化
    
    for(i = 0; i<10; i++)
    {
        ListInsert(&myList, i, i+1); //插入
    }
    ListDelete(&myList, 4, &x); //删除5即下标为4
    
    for(i = 0; i<ListLength(myList); i++)
    {
        ListGet(myList, i, &x); //获取
        printf("%d ", x);
    }
}
2、设计一个顺序表的删除函数，把顺序表L中的数据元素x删除。
//成功返回1，不成功返回0
int ListDeleteX(SequenceList *L, ElemType x)
{
    int i, j;
    for(i=0; i<L->size; i++)
    {
        if(x == L->list[i])
        {
            break; //找到x则退出循环 ，此时x下标已被记录
        }
    }
    if(i == L->size) return 0;
    for(j = i; j<L->size; j++)
    {
        L->list[j] = L->list[j+1];  //向前移动一位
    }
    L->size--;
    return 1;
}
3、编写算法实现顺序表逆置，要求把顺序表A中数据元素序列（a0,a1,a2,…..an-1）逆置为（an-1, ….. a2, a1,a0）存储到顺序表B中。
void Converse(SequenceList la, SequenceList *lb)
{
    int i;
    ListInitialize(lb);
    for(i = 0; i<la.size; i++)
    {
        lb->list[i] = la.list[la.size-i-1];
        lb->size++;
    }
}
4、自身逆置
void ConverseSelf(SequenceList *la)
{
    SequenceList lb;
    int i, j;
    ListInitialize(&lb);
    for(i = 0; i<la->size; i++)
    {
        lb.list[i] = la->list[la->size-i-1];
        lb.size++;
    }
    for(j = 0; j<lb.size; j++)
    {
        la->list[j] = lb.list[j];
    }
}
4 线性表的链式表示和实现单链表中，构成链表的结点只有一个指向直接后继结点的指针域。
单链表的表示方法:
单链表存储结构
可以定义单链表结点的结构体如下：
/*线性表的单链表存储结构*/
typedef int ElemType;
typedef struct Node
{
  ElemType data;
  struct Node *next;
} Node;
typedef struct Node *LinkList;
其中，data域用来存放数据元素，next域用来存放指向下一个结点的指针。单链表有带头结点结构和不带头结点结构两种。我们把指向单链表的指针称作头指针。头指针所指的不存放数据元素的第一个结点称作头结点。存放第一个数据元素的结点称作第一个数据元素结点。第一个数据元素结点在带头结点的单链表中是链表中的第二个结点，在不带头结点的单链表中是链表中的第一个结点。一个带头结点的单链表下图所示。
单链表空单链表空连和非空链和非空链
单链表的操作实现1、C语言的动态申请内存空间函数
C语言提供了动态申请内存空间函数malloc()和动态释放函数内存空间的函数free()。这些函数包含在头文件malloc.h中。malloc()函数的原型是：
void malloc(unsigned size)`
malloc()函数用于向系统动态申请size个字节的内存单元空间，函数返回值为所申请内存空间的首地址。free()函数的原型是：
void free(void *p)
2、单链表的结点定义
单链表是由一个个结点链接而成的，单链表中每个结点的结构体定义如下：
typedef struct node
{ //结点类型定义
  DataType data; //结点的数据域
  struct node *next;//结点的指针域
}ListNode;
3、单链表的操作实现
在带头结点的单链存储结构下，线性表抽象数据类型定义的各个操作的具体实现方法如下。
单链表的创建
//初始化
 int InitList(LinkList &L)
{
     //构造一个单链表
     L=new LNode;  //生成头结点，用头指针L指向头结点
     L->next =NULL;
     return 1;
 }
单链表的读取
在单链表中读取第i个元素，我们无法一开始知道，必须从头开始找。
typedef int DateType;
/*初始条件：顺序线性表L已经存在，1<=i<=ListLength(L)*/
/*操作结果：用e返回L中第i个数据元素的值*/
int GetDate(LinkList L, int i, DateType *x)
{
  int j;
  LinkList p;
  p = L->next;  /*让指针p指向链表L的第一个节点*/
  j = 1;
  while (p && j<i)  /*p不为空且计数器j还没有等于i时，循环继续*/
  {
    p = p->next;
    ++j;
  }
  if (!p || j > i)
  {
    return 0;   /*第i个节点不存在*/
  }
  *x = p->data;  /*取第i个节点的数据*/
  return 1;
}
单链表的插入
单链表的插入过程
【说明】：
1、要在带头结点的单链表第i（0≤i≤size）个结点前插入一个存放数据元素x的结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后动态申请一个结点存储空间并由指针q指示，并把数据元素x的值赋予新结点的数据元素域（即q->data=x），最后修改新结点的指针域指向ai结点（即q->next=p->next），并修改ai-1结点的指针域使之指向新结点q（即p->next= q）。插入过程如上图所示。
2、循环条件由两个子条件逻辑与组成，其中子条件p->next != NULL保证指针所指结点存在，子条件j<i-1保证最终让指针p指向ai-1结点。
代码实现：
int ListInsert(SLNode *head,int i,DataType x)
{
   //在带头结点的单链表head的第i(0<=i<=size)个结点前
    //插入一个存放数据元素x的结点。插入成功则返回1，失败则返回0
    SLNode *p,*q;
    int j;
    p=head;
    j=-1;
    while(p->next!=NULL&&j<i-1)
    //最终让指针p指向第i-1个结点
    {
        p=p->next;
        j++;
    }
    if(j!=i-1)
    {
        printf("插入元素位置参数错！");
        return 0;
    }
    
    //生成新结点，并赋值
    q=(SLNode *)malloc(sizeof(SLNode));
    q->data=x;
    //插入步骤
    q->next=p->next;
    p->next=q;
    return 1;
}
单链表的删除ListDelete
﻿
【说明】：
1、要在带头结点的单链表中删除第i（0≤i≤size-1）个结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向ai结点（即s=p->next），并把数据元素a i的值赋予x（即*x=s->data），最后把ai结点脱链（即p->next=p->next->next），并动态释放ai结点的存储空间，即free(s)。删除过程如上图所示。
2、循环条件由三个子条件逻辑与组成，其中子条件p->next!=NULL保证ai-1结点存在，子条件p->next->next!=NULL保证ai结点存在，子条件j<i-1保证最终让指针p指向ai-1结点。与插入函数相比，删除函数的循环条件多了子条件p->next->next!=NULL。这是因为删除函数要删除ai结点，若没有子条件p->next->next!=NULL保证ai结点存在，则当ai结点不存在时，动态释放语句free(s)将因指针s为空而出错。
注意：在循环条件中，前两个子条件的次序不能颠倒，否则在ai-1结点不存在时，会因指针p->next->next不存在而出错
代码实现：
int ListDelete(SLNode *head,int i,DataType *x)
{
    SLNode *p,*s;
    int j;
    p=head;
    j=-1;
    while(p->next!=NULL&&p->next->next!=NULL&&j<i-1)
        //循环结束时指针p指向第i-1个结点
    {
        p=p->next;
        j++;
    }
    if(j!=i-1)
    {
        printf("删除元素位置参数错！");
        return 0;
    }
    s=p->next;
    *x=s->data;
    p->next=p->next->next;//删除
    free(s);        //释放指针s所指向结点的内存空间
    return 1;
}
单链表取数据元素
取数据元素函数和删除函数基本类同，主要差别是，取数据元素函数的循环条件改为j<i，并且不删除ai结点。
代码实现：
int ListGet(SLNode *head,int i,DataType *x)
{
    SLNode *p;
    int j;
    p=head;
    j=-1;
    while(p->next!=NULL && j<i)
    {
        p=p->next;
        j++;
    }
    if(j!=i)
    {
        printf("取元素位置出错！");
        return 0;
    }
    *x=p->data;
    return 1;
}
撤销单链表
单链表的结点空间是在程序运行时动态申请的，而系统只负责自动回收程序中静态分配的内存空间，所以，和顺序表相比，单链表要增加一个撤销单链表操作，释放动态申请的内存空间。
代码实现：
void Destroy(SLNode **head)
{
    SLNode *p,*p1;
    p=*head;
    while(p!=NULL)
    {
        p1=p;
        p=p->next;
        free(p1);
    }
    *head=NULL;
}
单链表实例1、编程实现建立一个线性表，首先依次输入数据元素1, 2, 3,…,10，然后删除数据元素5，最后依次显示当前表中的数据元素。要求使用单链表。
代码如下：
include <stdio.h>      //包含printf()函数
#include <stdlib.h>     //包含exit()函数
#include <malloc.h>     //包含malloc()等函数
//2020.05。04  微信公众号：C语言与CPP编程
typedef int DataType;   //定义DataType为int
#include "LinList.h"    //包含单链表文件
int main(int argc, char* argv[])
{
    SLNode *head;   //定义头指针变量
    int i,x;
    ListInitiate(&head);    //初始化
    for(i = 0;i < 10; i++)      //插入10个数据元素
    {
        if(ListInsert(head,i,i+1) == 0)
        {
            printf("错误！\n");
            return ;
        }
    }
    for(i = 0;i < ListLength(head); i++)    //显示当前的数据元素中的值
    {
        if(ListGet(head,i,&x) == 0) //取元素值到x变量中
        {
            printf("错误！\n");
            return ;
        }
        else
        {
            printf("%d ",x);    //显示
        }
    }
    printf("\n");
    if(ListDelete(head,4,&x) == 0)  //删除下标为四(值为5)的数据元素
    {
        printf("错误！\n");
        return ;
    }
    for(i = 0;i < ListLength(head); i++)    //显示当前的数据元素中的值
    {
        if(ListGet(head,i,&x) == 0) //取元素值到x变量中
        {
            printf("错误！\n");
            return ;
        }
        else
        {
            printf("%d ",x);    //显示
        }
    }
    printf("\n");
    Destroy(&head);     //撤消单链表
    return 0;
}
2、设头指针为head,并设带头结点单链表中的数据元素递增有序，编写算法将数据 元素x插入到带头结点单链表的适当位置上，要求插入后保持单链表数据元素的递增有序。
算法思路：从链表的第1个数据元素结点开始，逐个比较每个结点的data域值和x的值，当data小于等于x时，进行下一个结点的比较；否则，就找到了插入结点的合适位置，此时申请新结点把x存入，然后把新结点插入；当比较到最后一个结点仍有data小于等于x时，则把新结点插入单链表尾。
﻿
代码如下：
void LinListInsert(SLNode*head,DataType x)
{
    SLNode*curr,*pre,*q;
    //循环初始化
    curr = head->next;      //curr指向第一个数据元素结点
    pre = head;             //pre指向头结点
    //循环定位插入位置
    while(curr != NULL && curr->data <= x)
    {
        pre = curr;
        curr = curr->next;
    }
    //申请一个结点并把x存入data域
    if((q = (SLNode*)malloc(sizeof(SLNode))) == NULL) exit(1);
    q->data = x;
    //把新结点插入pre所指结点后
    q->next = pre->next;
    pre->next = q;
}
3、设head为单链表的头指针，并设单链表带有头结点，编写算法将单链表中的数据元素按照其值递增有序的顺序进行就地排序。
代码如下：
void LinListSort(SLNode *head)
{
    SLNode*curr,*pre,*p,*q;
    p = head->next;
    head->next = NULL;
    while(p != NULL)
    {
        curr = head->next;
        pre = head;
        while(curr != NULL && curr->data <= p->data)
        {
            pre = curr;
            curr = curr->next;
        }
        q = p;
        p = p->next;
        q->next = pre->next;
        pre->next = q;
    }
}
双向链表和单向链表相比有以下优势：
插入删除不需要移动元素外，可以原地插入删除
可以双向遍历
结构体定义如下：
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;
}
﻿