月份：2018年3月

线性表

线性结构的特点是：在数据元素的非空有限集中，（1）存在唯一一个被称作“第一个”的数据元素；（2）存在唯一的一个被称作“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合中的每个数据元素均只有一个后继。

1.线性表的实现

sqlist.h下载

在实现之前先把需要使用到的库和头文件进行包含
所需的头文件sqlist.h已经在上方提供 

#include <stdio.h>  
#include <stdlib.h>  
#include "sqlist.h"
1）构造一个空的线性表L
Status InitList_Sq(struct Sqlist &L){
     //构造一个空的顺序表L
     L.elem = (ElemType )malloc(LIST_INIT_SIZEsizeof(struct Sqlist));
     if(!L.elem)
         return (OVERFLOW);// 存储分配失败
     L.length = 0;//空表长度为0
     L.listsize = LIST_INIT_SIZE;//初始存储容量
     return OK;
 }//InitList_Sq
2） 销毁顺序表L ， 要求顺序表L存在 
void DestoryList_Sq(struct Sqlist &L){
     //销毁顺序表L
     //要求顺序表L存在
     free(L.elem);
     L.elem = NULL;
 }//DestoryList_Sq
3） 将L重置为空表，要求顺序表L存在
4）判断是否为空表 
Status ListEmpty_Sq(struct Sqlist L){
     //若L为空表，返回TRUE,否则返回FALSE
     //要求顺序表L存在
     if(0==L.length)
         return TRUE;
     else
         return FALSE;
 }//LsitEmpty_Sq
5）获取表元素个数
Status ListLength(struct Sqlist L){
     //要求顺序表L存在
     //返回L中数据元素的个数
     return L.length;
 }//ListLength_Sq
6）取表中指定位置元素的值
void GetElem_Sq(struct Sqlist L,int i,ElemType &e){
     //要求顺序表L存在，1<=i<=ListLength_Sq(L)
     //e返回L中第i个数据元素的值
     e = *(L.elem + i - 1);
 }//GetElem_Sq
7） 判断两个数据元素是否相等 
Status compare_equal_Sq(ElemType e1,ElemType e2){
     //判断两个数据元素是否相等，相等返回TRUE,否则返回FALSE
     if(e1==e2)
         return TRUE;
     else
         return FALSE;
 }//compare_equal_Sq
8） 返回L中第一个与e满足关系的compare()的数据元素的位序 
Status LocateElem_Sq(struct Sqlist L,ElemType e,Status (*compare)(ElemType,ElemType)){
     //顺序表L已存在，compare()是数据元素判定函数
     //返回L中第一个与e满足关系的compare()的数据元素的位序,若这样的元素不存在，返回0
     ElemType *p = L.elem;
     int i;//位序
     for(i=1;i<=L.length;i++)
     {
         if(compare(e,*(p+i-1)))
             return i;
     }
     return 0;
 }//LocateElem_Sq
9）求指定元素前驱
Status PriorElem_Sq(struct Sqlist L,ElemType cur_e,ElemType &pre_e){
     //要求顺序表L存在
     //若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义
     int pos;
     pos = LocateElem_Sq(L,cur_e,compare_equal_Sq);
     if(!pos || 1==pos)
         return NOTEXIT;
     else
         return *(L.elem+pos-2);
 }//PriorElem_Sq
10）求指定元素后继
Status NextElem_Sq(struct Sqlist L,ElemType cur_e,ElemType &next_e){
     //要求顺序表L存在
     //若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义
     int pos;
     pos = LocateElem_Sq(L,cur_e,compare_equal_Sq);
     if(!pos || pos==L.length)
         return NOTEXIT;
     else
         return *(L.elem+pos);
 }//NextElem_Sq
11）指定位置插入元素
void ListInsert_Sq(struct Sqlist &L,int i,ElemType e){
     //要求顺序表存在，1<=i<=ListLength_Sq(L)      
     //在第i个位置之前插入数据元素e,L的长度加1    
     int j;      
    ElemType *  newbase;     if(L.length+1>L.listsize) 
     {
         newbase = (ElemType )realloc(L.elem, (L.listsize+LISTINCREMENT)sizeof(ElemType));
         if(!newbase)
             exit(OVERFLOW);//存储分配失败
         L.elem = newbase;//新基址
         L.listsize += LISTINCREMENT;
     }
     for(j=L.length;j>=i;j++)
     {
         *(L.elem+j) = *(L.elem+j-1);
     }
     *(L.elem+i-1) = e;
     L.length++;
 }//ListInsert_Sq
12）删除指定元素
void ListDelete_Sq(struct Sqlist &L,int i,ElemType &e){
     //顺序表存在且非空，1<=i<=ListLength_Sq(L)
     //删除L的第i个元素，并用e返回其值，L的长度减1
     int j;
     e = *(L.elem+i-1);
     for(j=1;j<L.length;j++){
         *(L.elem+j-1) = *(L.elem+j);
     }
     L.length--;
 }//ListDelete_Sq
13）调用visit函数遍历线性表
Status visit_display_Sq(ElemType e){
     printf("%d",e);
     printf("\n");
     return TRUE;
 }//visit_display_Sq 
Status ListTraverse_Sq(struct Sqlist L,Status (visit)(ElemType)){      
   //要求顺序表存在     
   //依次对L的每个元素调用函数visit()， 
   一旦visit()失效，则操作失败，返回FALSE,否则返回TRUE     
   int i;     
    for(i=0;i(L.elem)));  
     }
     return TRUE;
 }//ListTraverse_Sq