顺序存储结构线性表基本操作-纯C语言实现.doc

///////////////////////////////////////////////////////////
//---------------------------------------------------------
//            顺序存储结构线性表基本操作 纯C语言实现
//
//            a simple example of Sq_List by C language
//
//                    by wangweinoo1[PG]
//---------------------------------------------------------
///////////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>

//以下为函数运行结果状态代码

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#define LIST_INIT_SIZE 5  //线性表存储空间的初始分配量
#define LISTINCREMENT 1  //线性表存储空间分配增量

typedef int Status; //函数类型，其值为为函数结果状态代码

typedef int ElemType; //假设数据元素为整型

typedef struct
{
    ElemType *elem; //存储空间基址
    int length; //当前长度
    int listsize; //当前分配的存储容量
}Sqlist;
//实现线性表的顺序存储结构的类型定义

static Sqlist L;//为了引用方便，定义为全局变量
static ElemType element;

///////////////////////////////////////
//函数名：InitList()
//参数：SqList L
//初始条件：无
//功能：构造一个空线性表
//返回值：存储分配失败：OVERFLOW
//        存储分配成功：OK
///////////////////////////////////////
Status InitList(Sqlist L)
{
    L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(L.elem==NULL)
        exit(OVERFLOW);
    else
    {
        L.length=0;
        L.listsize=LISTINCREMENT;
        return OK;
    }
}

///////////////////////////////////////
//函数名：DestroyList()
//参数：SqList L
//初始条件：线性表L已存在
//功能：销毁线性表
//返回值：L.elem==NULL:ERROR
//        L.elem!=NULL:OK
///////////////////////////////////////
Status DestroyList(Sqlist L)
{
    if(L.elem==NULL)
        return ERROR;
    else
        free(L.elem);
    return OK;
}

///////////////////////////////////////
//函数名：ClearList()
//参数：SqList L
//初始条件：线性表L已存在
//功能：清空线性表
//返回值：L.elem==NULL:ERROR
//        L.elem!=NULL:OK
///////////////////////////////////////
Status ClearList(Sqlist L)
{
    if(L.elem==NULL)
        exit(ERROR);
    int i;
    ElemType *p_elem=L.elem;
    for(i=0;i<L.length;i++)
    {
        *L.elem=NULL;
        L.elem++;
    }
    L.elem=p_elem;
    return OK;
}

///////////////////////////////////////
//函数名：ListEmpty()
//参数：SqList L
//初始条件：线性表L已存在
//功能：判断线性表是否为空
//返回值：空：TRUE
//        非空：FALSE
///////////////////////////////////////
Status ListEmpty(Sqlist L)
{
    int i;
    ElemType *p_elem=L.elem;
    for(i=0;i<L.length;i++)
    {
        if(*L.elem!=0)
        {
            L.elem=p_elem;
            return FALSE;
        }
        L.elem++;
    }
    return TRUE;
}
///////////////////////////////////////
//函数名：ListLength()
//参数：SqList L
//初始条件：线性表L已存在
//功能：返回线性表长度
//返回值：线性表长度(L.length)
///////////////////////////////////////
int ListLength(Sqlist L)
{
    return L.length;
}

///////////////////////////////////////
//函数名：GetElem()
//参数：SqList L,int i,ElemType *element
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：用e返回线性表中第i个元素的值
//返回值：(i<1)||(i>ListLength(L))：OVERFLOW
//        1<=i<=ListLength(L)：OK
///////////////////////////////////////
Status GetElem(Sqlist L,int i)
{
    int j;
    ElemType *p_elem=L.elem;
    if(i<1||i>L.length)
        return OVERFLOW;
    for(j=1;j<=i;j++)
        L.elem++;
    element=*L.elem;
    L.elem=p_elem;
    return OK;
}

///////////////////////////////////////
//函数名：LocateElem()
//参数：Sqlist L,ElemType element
//初始条件：线性表L已存在
//功能：返回顺序表L中第1个与element相等的元素
//返回值：若在L中存在于element相等的元素：其位序
//        若在L中不存在与element相等的元素：0
///////////////////////////////////////
int LocationElem(Sqlist L,ElemType element)
{
    int i;
    ElemType *p_elem=L.elem;
    for(i=1;i<L.length;i++)
    {
        if(*L.elem==element)
        {
            L.elem=p_elem;
            return i;
        }
        else
            L.elem++;
    }
    return 0;
}

///////////////////////////////////////
//函数名：PriorElem()
//参数：Sqlist L,ElemType cur_e,ElemType *pre_e
//初始条件：线性表L已存在，i>1&&i<=L.length，LocationElem()存在
//功能：用pre_e返回线性表中cur_e的前驱
//返回值：i<=1||i>L.length：OVERFLOW
//        i>1&&i<=L.length：OK
///////////////////////////////////////
Status PriorElem(Sqlist L,ElemType cur_e,ElemType *pre_e)
{
    ElemType *p_elem=L.elem;
    int i,j;
    i=LocationElem(L,cur_e);
    if(i<=1||i>L.length)
        exit(OVERFLOW);
    for(j=1;j<i;j++)
    {
        if(j==(i-1))
        {
            pre_e=L.elem;
            L.elem=p_elem;
            return OK;
        }
        else
            L.elem++;
    }
}

///////////////////////////////////////
//函数名：NextElem()
//参数：Sqlist L,ElemType cur_e,ElemType *next_e
//初始条件：线性表L已存在，i>=1&&i<L.length，LocationElem()存在
//功能：用next_e返回线性表中cur_e的后继
//返回值：i<1||i>=L.length：OVERFLOW
//        i>=1&&i<L.length：OK
///////////////////////////////////////
Status NextElem(Sqlist L,ElemType cur_e,ElemType *next_e)
{
    ElemType *p_elem;
    int i,j;
    i=LocationElem(L,cur_e);
    if(i<1||i>=L.length)
        exit(OVERFLOW);
    for(j=1;j<i;j++)
    {
        if(j==(i-1))
        {
            next_e=L.elem;
            L.elem=p_elem;
            return OK;
        }
        else
            L.elem++;
    }
}

///////////////////////////////////////
//函数名：ListInsert()
//参数：SqList L,int i,ElemType e
//初始条件：线性表L已存在，1<=i<=ListLength(L)+1
//功能：在线性表中第i个数据元素之前插入数据元素e
//返回值：失败：ERROR
//        成功：OK
///////////////////////////////////////
Status ListInsert(Sqlist L,int i,ElemType e)
{
    int *q=&(L.elem[i-1]);
    ElemType *newbase,*p;
    if(i<1||i>(L.length+1))
        return ERROR;
    if(L.length>=L.listsize)
    {
        newbase=(ElemType*)realloc(L.elem,L.listsize+LISTINCREMENT*sizeof(ElemType));
        if(newbase==NULL)
            exit(OVERFLOW);
        L.elem=newbase;
        L.listsize+=LISTINCREMENT;
    }
    for(p=&(L.elem[L.length-1]);p>=q;--p)
        *(p+1)=*p;
    *q=e;
    ++L.length;
    return OK;
}

///////////////////////////////////////
//函数名：ListDelete()
//参数：SqList L,int i,Elemtype e
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：将线性表L中第i个数据元素删除
//返回值：失败：ERROR
//        成功：OK
///////////////////////////////////////
Status ListDelet(Sqlist L,int i,ElemType e)
{
    if(i<1||(i>L.length))
        return ERROR;
    ElemType *p,*q;
    p=&(L.elem[i-1]);
    e=*p;
    q=L.elem+L.length-1;
    for(++p;p<=q;++p)
        *(p-1)=*p;
    --L.length;
    return OK;
}