线性表的顺序表示和实现

/***********************************
线性表的顺序表示和实现
  by Rowandjj
  date 2014/3/27
***********************************/
#include<iostream>
using namespace std;

#define LIST_INIT_SIZE    100//线性表空间的初始分配量
#define LIST_INCREMENT    10//线性表空间的分配增量


#define OK    1//成功状态码
#define TRUE 1 
#define FALSE 0
#define ERROR    2//失败状态码
#define OVERFLOW -1//内存分配失败状态码

typedef int Status;//返回结果,OK或者ERROR
typedef int Bool;
typedef int ElemType;//元素类型
/*线性表动态分配顺序存储结构*/
typedef struct _SQLIST_
{
    ElemType *elem;//存储空间基址
    int length;//当前长度
    int listsize;//当前分配的存储容量
}Sqlist;

/* 操作定义 */
Status InitList_Sq(Sqlist&);//构造一个空的线性表
Status DestroyList_Sq(Sqlist&);//销毁线性表
Status ClearList_Sq(Sqlist&);//将线性表重置为空表
Bool ListEmpty_Sq(Sqlist);//判断是否为空表
int ListLength_Sq(Sqlist);//返回线性表长度
void GetElem_Sq(Sqlist,int,ElemType&);//获取并返回线性表中指定位置的元素(1<=index<=ListLength)
void PriorElem_Sq(Sqlist,ElemType,ElemType&);//返回指定元素的前驱元素,若是第一个元素,则前驱未定义
void NextElem_Sq(Sqlist,ElemType,ElemType&);//返回指定元素的后继，若是最后一个元素,则后继未定义
Status ListInsert_Sq(Sqlist&,int,ElemType);//在指定位置上插入元素
Status ListDelete_Sq(Sqlist&,int,ElemType&);//删除指定位置上的元素
void ListTraverse_Sq(Sqlist);//遍历顺序表

/*具体实现*/
Status DestroyList_Sq(Sqlist &L)
{
    L.length = 0;
    L.listsize = 0;
    free(L.elem);
    L.elem = NULL;
    return OK;
}
Status ClearList_Sq(Sqlist &L)
{
    L.length = 0;
    return OK;
}
Status InitList_Sq(Sqlist &L)
{
    L.elem = (ElemType*)malloc(sizeof(ElemType)*LIST_INIT_SIZE);
    if(!L.elem)
    {
        exit(OVERFLOW);
    }
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return OK;
}
void ListTraverse_Sq(Sqlist L)
{
    for(int i = 0; i < L.length; i++)
    {
        cout<<L.elem[i]<<" ";
    }
    cout<<endl;
}
int ListLength_Sq(Sqlist L)
{
    return L.length;
}
Bool ListEmpty_Sq(Sqlist L)
{
    return L.length==0 ? TRUE : FALSE;
}
Status ListInsert_Sq(Sqlist &L,int i,ElemType e)// 1<=i<=length+1 
{
    if(i<1 || i>L.length+1)//参数判断
    {
        return ERROR;
    }
    if(L.length>=L.listsize)//扩容
    {
        ElemType *newbase = (ElemType*)realloc(L.elem,(L.listsize+LIST_INCREMENT)*sizeof(ElemType));
        if(!newbase)
        {
            exit(OVERFLOW);
        }
        L.elem = newbase;
        L.listsize += LIST_INCREMENT;
    }
    //插入
    ElemType* q = &L.elem[i-1];
    for(ElemType* p = &L.elem[L.length-1];p >= q; p--)
    {
        *(p+1) = *p;
    }
    *q = e;
    L.length++;
    return OK;
}
Status ListDelete_Sq(Sqlist &L,int i,ElemType &e)
{
    ElemType *p = &L.elem[i-1];
    e = *p;
    for(++p; p <= &L.elem[L.length-1]; p++)
    {
        *(p-1) = *p;
    }
    L.length--;
    return OK;
}
void PriorElem_Sq(Sqlist L,ElemType e,ElemType& i)
{
    int index = 0;
    while(L.elem[index] != e && index < L.length)
    {
        index++;
    }
    if(index >= L.length || index==0)
    {
        return;
    }
    i = L.elem[index-1];
}
void NextElem_Sq(Sqlist L,ElemType e,ElemType &i)
{
    int index = 0;
    while(L.elem[index]!=e && index<L.length)
    {
        index++;
    }
    if(index>=L.length || index== L.length-1)
    {
        return;
    }
    i = L.elem[index+1];
}    
void GetElem_Sq(Sqlist L,int i,ElemType &e)
{
    if(i<1 || i>L.length)
    {
        return;
    }
    e = L.elem[i-1];
}

测试：

int main()
{
    Sqlist l;
    ElemType e,e2;
    int num,index;

    //init
    InitList_Sq(l);
    cout<<"length:"<<ListLength_Sq(l)<<endl;
    cout<<"EMPTY:"<<ListEmpty_Sq(l)<<endl;
    ListTraverse_Sq(l);
    
    //insert
    cin>>num;
    for(int i = 0; i < num; i++)
    {
        cin>>e;
        cin>>index;
        ListInsert_Sq(l,index,e);        
    }
    cout<<"length:"<<ListLength_Sq(l)<<endl;
    cout<<"EMPTY:"<<ListEmpty_Sq(l)<<endl;
    ListTraverse_Sq(l);
    //delete
    cin>>index;
    ListDelete_Sq(l,index,e);
    cout<<"e = "<<e<<endl;
    cout<<"length:"<<ListLength_Sq(l)<<endl;
    cout<<"EMPTY:"<<ListEmpty_Sq(l)<<endl;
    ListTraverse_Sq(l);
    //get
    cin>>index;
    GetElem_Sq(l,index,e);
    cout<<"e = "<<e<<endl;
    cout<<"length:"<<ListLength_Sq(l)<<endl;
    cout<<"EMPTY:"<<ListEmpty_Sq(l)<<endl;
    ListTraverse_Sq(l);
    //get prior
    cin>>e;
    PriorElem_Sq(l,e,e2);
    cout<<"e2 = "<<e2<<endl;
    ListTraverse_Sq(l);
    //get next 
    cin>>e;
    NextElem_Sq(l,e,e2);
    cout<<"e2 = "<<e2<<endl;
    ListTraverse_Sq(l);
    system("pause"); 
    return 0;
}

线性表的顺序表示和实现,布布扣,bubuko.com

线性表的顺序表示和实现

原文：http://blog.csdn.net/chdjj/article/details/22331191