线性表的类型定义

线性表是一种最常用且最简单的一种数据结构。概括地说，线性表是n个数据元素的有限序列。举例来说，26个英文字母表就是一个简单的线性表：

(A,B,C......Z)

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（但是注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

线性表中元素的个数n定义为线性表的长度，n=0时是称为空表。而在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，而ai就是第i个数据元素，i就是ai在线性表中的位序。

线性表是一个相当灵活的数据结构，它的长度可以根据需要进行增大或者减少，同时还可以对线性表中的元素进行访问，插入和删除等。

线性表按照存储结构的不同可以分为顺序表和链表，它们的主要特点如下：
（1）顺序表：它的顺序存储结构的特点是逻辑关系上相领的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，它的存储位置可用一个简单、直观的公式来表示。但正是这个特点也铸成了这种存储结构的弱点：在作插入或者删除操作时，需要移动大量的元素。
（2）链表：它的链式存储结构的特点是数据元素之间的逻辑关系是由结点中的指针指示的，因此它就没有顺序存储结构所具有的弱点，但同时也失去了顺序表可以随机存取的优点。

线性表的类型

抽象数据类型线性表的定义如下：

ADT List{
  数据对象；
  数据关系；
  基本操作：
    InitList(&L)
     操作结果：构造一个空的线性表

    DestroyList(&L)
      初始条件：存在线性表
      操作结果：销毁线性表

     ClearList(&L)
        初始条件：存在线性表
        操作结果：将L重置为空表

    ListEmpty(L)
        初始条件：存在线性表
        操作结果：若L为空表，则返回TRUE，否则返回FALSE

      ListLength(L)
        初始条件：存在线性表
        操作结果：返回L中数据的元素的个数

      GetElem(L,i,&e)
        初始条件：存在线性表，且1<=i<=ListLength
        操作结果：用e返回L中第i个数据元素的值

      LocateElem(L,e,compare())
        初始条件：存在线性表，且compare()是数据元素判定函数
        操作结果：返回L中第一个与e满足关系compare()的数据元素的位序。若不存在，则返回0

      PriorElem(L,cur_e,&pre_e)
        初始条件：存在线性表
        操作结果：若cur_e是L中的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作无意义，pre_e无意义

      NextElem(L,cur_e,&next_e)
        初始条件：存在线性表
        操作结果：若cur_e是L中的数据元素，且不是最后一个，则next_e返回它的后继，否则操作失败，next_e无意义

      ListInsert(&L,i,e)
        初始条件：存在线性表，1<=i<=ListLength(L)+1
        操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1

      ListDelete(&L,i,&e)
        初始条件：存在线性表,1<= i<=ListLength(L)
        操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1

      ListTraverse(L,visit())
        初始条件：存在线性表
        操作结果：依次对L中的数据元素调用函数visit(),一旦调用失败，则操作失败 
   }

1.顺序表

顺序表基本操作的实现

1.宏定义解释

/* ElemType ：线性表数据元素数据类型
LIST_INIT_SIZE : 线性表初始数据元素容量
Status ：函数返回值（一般替换int型）
error ：0
INFEASIBLE ：0
OK ：0 */

2.顺序表结构体

typedef struct{
  ElemType *elem;  //存储空间基址
  int length;  //当前长度
  int listsize;  //当前分配的存储容量  
}SqList；

3.基本操作的实现

（1）创建一个空的线性表InitList

Status InitList(SqList &L)
{
    L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    //申请存储空间
    if(!L.elem)  //如果没有申请成功
    exit(0);  //返回0
    L.length=0;//空表的长度为0
    L.listsize=LIST_INT_SIZE;//初始数据元素存储容量
    return OK;
 }

（2）销毁线性表Destroy

Status Destroy(SqList &L)
{
    free(L.elem);  //释放线性表的基址
    L.elem=NULL;   //初始化
    L.length=0;  //线性表长度为0
    L.listsize=0;  //线性表的存储容量为0
    return OK;
}

（3）重置线性表ClearList

Status ClearList(SqList &L)
{
    L.length=0;  //将线性表长度置为0
    return Ok;
}

（4）判空线性表ListEmpty

Status ListEmpty(SqList L){  //不需要对线性表的成员变量进行改变，所以不使用引用
    return (L.length==0)?TRUE:FALSE;
}

（5）获取线性表当前元素个数ListLength

Status ListLength(SqList L){
      return L.length;
}

（6）获得指定位置的数据元素GetElem

Status GetElem(SqList L,int i, ElemType &e)
{
    if(i<1||i>L.length)  //如果超出范围
    exit(error);
    e=*(L.elem+i-1);  //（基址+i-1）即为第i个元素的地址
    return OK;
}

（7）定位元素（获得符合一定条件的数据元素的位序）LocateElem

int LocateElem(SqList L,ElemType e,status(*compare)(ElemType,ElemType))
{
    Elem *p=L.elem; //P的初值为第一个元素的存储位置
    int i=1;//i的初值为第一个元素的位序
    while(i<=L.length&&!compare(*p++,e))//越界或已找到满足条件的元素
    //i的最大可能值为L.length+1
    {
        if(i<=L.length)
        return i;
        else
        return 0;
    }

（8）返回前驱PriorElem

Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e)
{
   int a;
   a=LocateElem(L,cur_e,equal);
   if(!a||a==1)  //如果没有找到
   {
    cout<<"查找失败"<<endl;
    return error;
   }
   pre_e=*(L.elem+a-2);  //如果找到了，则则将其值赋给pre_e
   return OK;
 }

（9）返回后继NextElem

Status NextElem(SqList L,ElemType cur_e,ElemType &next_e)
{
    int a;
    a=LocateElem(L,cur_e,equal);
    if(!a||a==L.length)
    {
      cout<<"查找失败"<<endl;
      return error;
    }
    next_e=*(L.elem+a);
    return OK;
 }

（10）插入一个数据元素ListInsert

Status ListInsert(SqList &L,int i,ElemType e)
{
    ElemType *newbase,*q,*p;
    if(i<1||i>L.length+1)//i值不合法
    return error;
    if(L.length>=L.listsize) //当前存储空间已满，增加分配
    {
        if(!(newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType))))
        exit(0);//分配存储空间失败
        L.elem=newbase;//新基址
        L.listsize+=LISTINREMENT;//增加存储容量
    }
        q=L.elem+i-1;//q为插入位置
        for(p=L.elem+L.length-1;p>=q;--p)
        { *(p+1)=*p;//给插入位置之后的元素赋值达到之后元素后移一位的效果
        }
        *q=e;//插入e
        ++L.length;
        return OK;
 }

（11）删除元素ListDelete

Status ListDelete(SqList &L,int i,ElemType &e)
{
    ElemType *p,*q;
    if(i<1||i>L.length)//i值不合法
    return error;
    p=L.elem+i-1;//p为被删除元素的位置
    e=*p;//被删除元素的值赋给e
    q=L.elem+L.length-1;//表尾元素的位置
    for(++p;p<=q;++p)
    *(p-1)=*p;
    L.length--;
    return OK;
}    

（12）遍历线性表ListTraverse

Status ListTraverse(SqList L, void(*f)(ElemType&))
{
    ElemType *p=L.elem;
    int i;
    for(i=1;i<=L.length;i++)
    f(*p++);
    cout<<endl;
    return OK;
  }

2.链表

链表主要是分为3种，即单链表，循环单链表，双向链表。

链表

单链表

首先介绍单链表，单链表中的每一个结点是由数据域与指针域组成的，数据域存放所要存储的数据，而指针域是存放该结点后继元素的存储地址，正是由于这样的结构，使得单链表能够按照逻辑顺序来存储每一个数据。同时由于单链表的第一个结点的没有直接前驱，所以一般单链表都需要一个头结点来指向第一个结点。最后一个结点没有直接后继，所以它的指针是直接指向NULL的。

单链表

单链表的基本操作的实现

（1）宏定义解释

/* ElemType ：线性表数据元素数据类型
Status ：函数返回值（一般替换int型）
error ：0
INFEASIBLE ：0
OK ：0 */

（2）链表的结构体

typedef struct Node{
    ElemType data;  //用来存储数据的数据域 
    struct Node *next;  //用来指向下一个结点的指针域 
}ListNode,*LinkList; 

（3）基本操作的实现

（1）建立链表InitList

Status InitList(LinkList *head){
    if((*head=(LinkList)malloc(sizeof(ListNode)))==NULL)  //为头结点申请一个空间 
    exit(-1);
    (*head)->next==NULL;  //头结点开始是指向空 
} 

（2）清空链表Destroy

Status DestroyList(LinkList head){
    ListNode *p,*q;
    p=head;
    while(p!=NULL){
        q=p;
        p=p->next;  //p指向下一个结点 
        free(q);  //释放先前p的空间 
    }
} 

（3）判断链表是否是空ListEmpty

Status ListEmpty(LinkList head){
    if(head->next==NULL)  //若链表为空 
    return TRUE;  //返回1 
    else
    return FALSE;  //返回0
} 

（4）求表长ListLength

Status ListLength(LinkList head){
    ListNode *p;
    int count=0;
    p=head;
    while(p->next!=NULL){
        p=p->next;
        count++;
    }
    return count;
} 

（5）按序号查找Get

ListNode *Get(LinkList head,int i){
//按照序号查找单链表中第i个结点。查找成功则返回该结点的指针，否则返回NULL
    ListNode *p;
     int j;
     if(ListEmpty(head)){  //如果是空表，则返回NULL 
        return NULL;
     }
     if(i<1){  //如果输入要查找的结点不合法，则返回NULL 
        return NULL;
     } 
     j=0;  //赋初值 
     p=head;
     while(p->next!=NULL&&j<i){  //开始查找，p一直开始移动 
        p=p->next;
        j++;
     }
     if(j==i){  //如果找到，则返回指针 
        return p;
     }
     else{
        return NULL;
     }
}

（6）按内容查找与元素LocateElem

ListNode *LocateElem(LinkList head,ElemType e){
//按照内容查找链表中符合e的值的元素，如果找到则返回它的指针，否则返回NULL 
    ListNode *p;
    p=head->next;
    while(p){  //当p不为空时 
        if(p->data!=e){
            p=p->next;
        }
        else{
            break;
        }
    }
    return p;
} 

（7）定位操作LocatePos

Status LocatePos(LinkList head,ElemType e){
//查找线性表中元素值为e的元素，如果找到则返回其序号，否则返回0
    ListNode *p;
    int i=1;
    if(ListEmpty(head)){  //如果表是空的，则返回0 
        return 0;
    } 
    p=head->next;  //赋初值 
    while(p){
        if(p->data!=e){  //如果没有找到 
            p=p->next;  
            i++;  //i增加 
        }
        else{
            return i;  //如果找到，则返回序号i 
        }
    }
    if(!p){  //如果在p中没有找到 
        return 0;  //返回 0
    } 
} 

（8）插入ListInsert

Status LinkInsert(LinkList head,int i,ElemType e){
//将数值为e的元素插入到链表中第i个位置，如果插入成功返回1，否则返回0 
    LinkNode *pre,*p;
    int j=0;
    pre=head;  //赋初值 
    while(pre->next!=NULL&&j<i-1){  //开始查找是否有位置i的结点 
        pre=pre->next;  //没有则指向下一个 
        j++;
    }
    if(j!=i-1){  //如果没有找到位置i 
        return 0;  //返回0 
    }
    if((p=(ListNode*)malloc(sizeof(ListNode)))==NULL){  //为插入的结点申请内存 
        exit(-1);
    }
    else{  //开始插入 
        p->data=e;  //将元素e赋值给要插入结点的数值域 
        p=pre->next;
        pre->next=p;
        return 1;
    }
} 

（9）删除DeleteList

Status DeleteList(LinkList head,int i){
//删除链表中第i个位子元素，如果成功返回1，否则返回0
    LinkNode *pre,*p;
    int j=0;
    pre=head;  //赋初值 
    while(pre->next!=NULL&&j<i-1){  //开始查找位置i 
        pre=pre->next;
        j++;
    }
    if(j!=i-1){  //没有找到位置i，则返回0 
        return 0;
    }
    p=pre->next;
    pre->next=p->next;
    free(p);  //释放掉该结点 
    return 1;
} 

循环单链表

循环单链表是指收尾相连的单链表，是另一种形式的单链表。即将它的最后一个结点的指针域由空指针改为指向头结点或第一个结点，这样整个链表就形成了一个环状。

循环单链表
循环单链表的基本操作和单链表的操作基本上都是一样的，就是要注意在判断链表是否为空的条件上，单链表为空的条件是head->next==NULL而循环单链表的条件是head->next==head。

双向链表

双向链表的特殊之处在于它的每一个结点都有两个指针域：一个指向直接前驱结点，一个指向直接后继结点。双向链表每一个结点都有data域，prior域（存放前驱结点的存储地址）与next域三个。

双向链表也可以在第一个结点之前加上一个头结点。在判断双向链表为空的条件则有p=p->prior->next=p->next->prior

双向链表的结点存储结构如下：

typedef struct Node{
    DataType data;
    struct Node *prior;
    struct Node *next;
}DListNode,*DLinkList; 

双向链表的插入和删除操作

（1）插入InsertDList

Status InsertDList(DListLink head,int i,DataType e){
//在双向链表中第i个位置插入元素为e的结点，若成功返回1，否则返回0
    DListNode *p,*s;  //p为i位置的结点，s为新插入的结点 
    int j=0;
    p=head;  //p先为头结点 
    while(p->next!=head&&j<i-1){
        p=p->next;
        j++; 
    } 
    if(j!=i-1){
        return 0;
    }
    if(s=(DListNode*)malloc(sizeof(DListNode))==NULL){  //申请创建新的结点 
        exit(-1);
    }
    s->data=e;  //开始插入 
    s->prior=p->prior;
    p->prior->next=s;
    s->next=p;
    p->prior=s;
    return 1;
}

（2）删除DeleteDList

Status DeleteDList(DListLink head,int i){
//删除链表中第i个位置的结点，若成功返回1，否则返回0
    DListNode *p;  //p指向第i个位置的结点 
    int j=0;
    p=head;
    while(p->next!=NULL&&j<i-1){
        p=p->next;
        j++;
    } 
    if(j!=i-1){
        return 0;
    }
    p->prior->next=p->next;  //修改p的前驱结点的next域使之指向p的后继 
    p->next->prior=p->prior;  //修改p的后继结点的prior域使之指向p的的前驱 
    free(p);  //释放结点p 
    return 1;
}