顺序表的实现

   以下代码在VC6.0编译通过

status.h

/******************************************************************
      程序中要用到的 函数结果状态代码
******************************************************************/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行

typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等

typedef int Boolean;

list.h

/******************************************************************
               变量定义及函数声明
******************************************************************/
#include "status.h"

#define LIST_INIT_SIZE 10
#define LISTINCREMENT 2

typedef int ElemType ;


typedef struct
{
    ElemType *elem; //存储空间基地址

    int length; //当前长度

    int listsize; //当前分配的存储容量（以sizeof(Elemtype)为单位）

}SqList;



/******************************************************************
            函数声明
******************************************************************/
SqList InitList(); //顺序表初始化函数

int ListLength(SqList L); //求顺序表的长度

Status ListInsert(SqList *L,int i,ElemType e);//在位置i钱插入元素e

Status ClearList(SqList *L); //清空顺序表

Status ListEmpty(SqList L);//判断L是否为空

Status GetElem(SqList L,int i,ElemType *e);//获取某元素

int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType));//LocateElem函数

Status PriorElem(SqList L,ElemType cur_e,ElemType *Pre_e);//获取前驱元素

Status NextElem(SqList L,ElemType cur_e,ElemType *next_e);//求后继元素

Status ListDelete(SqList *L,int i, ElemType *e);//删除元素

Status ListTraverse(SqList L,void(*vi)(ElemType *));//访问每个元素
Status DestroyList(SqList *L);//销毁顺序表


include.h

/******************************************************************
      程序中要用的头文件
******************************************************************/
 #include<string.h>
 #include<ctype.h>
 #include<malloc.h> // malloc()等

 #include<limits.h> // INT_MAX等

 #include<stdio.h> // EOF(=^Z或F6),NULL

 #include<stdlib.h> // atoi()

 #include<io.h> // eof()

 #include<math.h> // floor(),ceil(),abs()

 #include<process.h> // exit()

 #include<iostream.h> // cout,cin




/******************************************************************
      自定义头文件
******************************************************************/
#include "status.h"


list.c

/******************************************************************
                   在List.h中声明函数的实现
                 线性表的基本操作 有12个
******************************************************************/
#include "include.h"
#include "List.h"

//----------------------初始化函数-------------------------------

SqList InitList()
{//线性表的初始化函数

 //操作结果：构造一个空的顺序线性表

    SqList L;
    L.elem = (ElemType*)malloc( LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem)
        exit(OVERFLOW);//存储空间分配失败

    L.length=0; //空表长度为0

    L.listsize=LIST_INIT_SIZE; //初始化存储容量

    return L ;
}
//----------------------求顺序表的长度-------------------------

int ListLength(SqList L)
{//返回顺序表的长度

    return L.length;
}

//--------------------在i位置前插入元素------------------------

Status ListInsert(SqList *L,int i,ElemType e)
{//在顺序线性表L中第i个位置前插入新的元素e；

//i的合法值为1≤i≤ListLength(L)+1

    ElemType *newbase,*p,*q;
    if(i<1||i>(*L).length+1)
        return ERROR;
    if((*L).length>=(*L).listsize)
    {
        if(!(newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType))))
            exit(OVERFLOW); //分配失败

        (*L).elem=newbase;
        (*L).listsize +=LISTINCREMENT; // 增加存储容量

    }
    q=(*L).elem + i-1;//q为插入位置

    for(p=(*L).elem+(*L).length-1;p>=q;--p) // 插入位置及之后的元素右移

        *(p+1)=*p;
    *q=e; // 插入e

    ++(*L).length; // 表长增1

    return OK;

}

//--------------------顺序表清空--------------------

Status ClearList(SqList *L)
{//L已存在，清空L

    (*L).length=0;
    return OK;
}

//-----------------判断L是否为空--------------------

Status ListEmpty(SqList L)
 { // 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE

   if(L.length==0)
     return TRUE;
   else
     return FALSE;
 }

//--------------获取某元素-------------------------

Status GetElem(SqList L,int i,ElemType *e)
{ // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)

   // 操作结果：用e返回L中第i个数据元素的值

   if(i<1||i>L.length)
     exit(ERROR);
   *e=*(L.elem+i-1);
   return OK;
}

//---------------LocateElem------------------------

int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))
{//初始条件：顺序表已存在，compare()是数据元素判定函数（满足为1，不满足为0）

//操作结果：返回L中第一个与e满足compare()关系的元素的位置，不存在返回0

    ElemType *p;
    int i=1; //初始化为第一个元素的位置

    p=L.elem; //初始化为第一个元素的存储位置

    while(i<=L.length&&!compare(*p++,e))
        i++;
    if(i<=L.length)
        return i;
    else
        return 0;
}

//---------------求前驱函数------------------------

Status PriorElem(SqList L,ElemType cur_e,ElemType *Pre_e)
{//初始条件：顺序表L已存在

//操作结果：用Pre_e返回Cur_e的前驱元素

    int i=2; //第一个元素无前驱

    ElemType *p=L.elem +1;//指向第二个元素

    while(i<=L.length&&*p!=cur_e)
    {
        p++;
        i++;
    }
    if(i>L.length)
     return INFEASIBLE;
   else
   {
     *Pre_e=*--p;
     return OK;
   }
}

//---------------求后继元素函数-------------------

Status NextElem(SqList L,ElemType cur_e,ElemType *next_e)
{//初始条件：顺序表L已存在

//操作结果：若cur_e不是最后一个元素，则用next_e返回它的后继，否则操作失败next_e无定义

    int i=1;//第一个元素

    ElemType *p=L.elem; //基地址指向第一个元素

    while(i<L.length&&*p!=cur_e)
    {
        p++;
        i++;
    }
    if(i=L.length)
        return INFEASIBLE;
    else
    {
        *next_e=*++p;
        return OK;
    }
}

//-----------------删除元素---------------------

Status ListDelete(SqList *L,int i, ElemType *e)
{//初始条件：L已存在

//操作结果：删除L中第i个元素用e返回，L长度减1

    ElemType *p,*q;
    if(i<1||i>(*L).length)
        return ERROR;
    p=(*L).elem+i-1;// 要删除元素的位置

    *e=*p;//删除元素赋给e

    q=(*L).elem+(*L).length-1;//最后一个元素

    for(++p;p<=q;++p)
        *(p-1)=*p;
    (*L).length--;
    return OK;
}

//---------------访问每个元素------------------

Status ListTraverse(SqList L,void(*vi)(ElemType *))
{//初始条件：L存在

//操作结果：依次对L中的每个元素调用vi()函数，vi()调用失败，操作失败

    ElemType *p;
    int i;
    p=L.elem;//定位到第一个元素

    for(i=1;i<=L.length;i++)
        vi(p++);
    return OK;
}

//--------------销毁表-------------------------
Status DestroyList(SqList *L)
{ // 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L
   free((*L).elem);
   (*L).elem=NULL;
   (*L).length=0;
   (*L).listsize=0;
   return OK;
}


main.c

/******************************************************************
                       主函数
******************************************************************/
#include "include.h"
#include "List.h"


Status comp(ElemType c1,ElemType c2)
{
    if(c1==c2*c2)
        return TRUE;
    else
        return FALSE;
}

Status visit(ElemType *e)
{
    printf("%d ",*e);
    printf("\n");
    return OK;
}

void main()
{
    SqList L;
    int length;
    int i;
    int result;//函数的返回状态值

    ElemType e;
    //------------------初始化函数测试---------------------

    printf("初始化顺序表\n");
    L=InitList();
    printf("初始化后的结果：\n");
    printf("L.elem=%u L.length=%d L.listsize=%d\n\n",L.elem,L.length,L.listsize);
    //-----------------------------------------------------

    //------------------求顺序表长度函数测试---------------

    length=ListLength(L);
    printf("表的长度为：%d\n",length);
    //-----------------------------------------------------

    //------------------求顺序表是否为空函数测试-----------

    result=ListEmpty(L);
    if(result)
        printf("顺序表为空表\n");
    else
        printf("不是空表\n");
    //-----------------------------------------------------

    //------------------在i位置前插入元素------------------

    printf("在表头依次插入1--10\n");
    for(i=1;i<=10;i++)
        result=ListInsert(&L,1,i);
    printf("L.elem=%u L.length=%d L.listsize=%d\n\n",L.elem,L.length,L.listsize);
    printf("插入的内容为：\n");
    for(i=1;i<=10;i++)
        printf("%d ",*(L.elem+i-1));
    //-----------------------------------------------------

    //------------------求顺序表是否为空函数测试-----------

    result=ListEmpty(L);
    if(result)
        printf("顺序表为空表\n");
    else
        printf("\n不是空表\n");
    //-----------------------------------------------------

    //------------------求顺序表长度函数测试---------------

    length=ListLength(L);
    printf("\n表的长度为：%d\n",length);
    //-----------------------------------------------------

    //-----------------获取某元素函数测试------------------

    result=GetElem(L,3,&e);
    printf("第三个元素为：%d\n",e);
    //-----------------------------------------------------

    //-----------------LocateElem函数测试------------------

    for(i=3;i<=4;i++)
    {    
        result=LocateElem(L,i,comp);
        if(result)
            printf("第%d个元素的值为%d的平方\n",result,i);
        else
            printf("没有值为%d的平方的元素\n",i);
    }
    //-----------------------------------------------------

    //------------------获取前驱函数测试-------------------

      result=PriorElem(L,3,&e);
     if(result)
         printf("元素3的前驱是：%d\n",e);
    //-----------------------------------------------------

    //------------------获取后继函数测试-------------------

      result=NextElem(L,5,&e);
     if(result)
         printf("元素5的后继是：%d\n",e);
    //-----------------------------------------------------

    //------------------删除元素函数测试-------------------

     printf("删除第4个元素\n");
     result=ListDelete(&L,4,&e);
     if(result)
     {
         printf("删除的元素为：%d\n",e);
         printf("删除后顺序表的内容为：\n");
         for(i=1;i<=L.length;i++)
             printf("%d ",*(L.elem+i-1));
         printf("\n");
     }
    //-----------------------------------------------------

    //------------------访问元素函数测试-------------------

     result=ListTraverse(L,visit);
    //-----------------------------------------------------
    //-------------------销毁表L---------------------------
   result=DestroyList(&L);
   if(result)
    printf("销毁L后：L.elem=%u L.length=%d L.listsize=%d\n",L.elem,L.length,L.listsize);
   //-------------------------------------------------------
}