顺序表

定义

顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素。通常都用数组来描述数据结构中的顺序存储结构。

代码

数据结构

# include <stdio.h>
# include <stdlib.h>
# define LIST_INIT_SIZE 100
# define OK 1
# define ERROR -1

typedef int ElemType;
typedef int Status;
typedef struct {
    ElemType elem[LIST_INIT_SIZE];    //顺序表大小，可根据实际需要而定
    int length;                       //线性表长度
    int listsize;                     //数组长度（以ElemType为单位）
} SqList;       //由于c语言中数组的下标从0开始，因此线性表的第一个元素a1和最后一个元素a0分别存储在L.elem[0]和L.elem[L.length-1]
Status InitList_Sq(SqList & L);
Status ListInsert_Sq(SqList & L, int i, ElemType e);
Status ListDelete_Sq(SqList & L, int i, ElemType & e);
int LocateElem_Sq(SqList L, ElemType e, Status (* compare)(ElemType, ElemType));
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc);
Status ShowList_Sq(SqList & L);
Status compare(ElemType a, ElemType b);

/*******************
Status InitList(SqList &L)
功能：初始化顺序线性表
参数：
    SqList &L：顺序线性表L
返回值:
    Status类型：OK为执行正确，ERROR为出错
*******************/
Status InitList_Sq(SqList & L)            //&L  对线性表L的引用
{
    //算法2.3   List_Size
    L.elem = new ElemType[LIST_INIT_SIZE];  //elem 数组的名称是一个指针，(ElemType *)返回一个指针
    if(!L.elem) {
        exit(OVERFLOW);
    }
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return OK;
}
/*******************
Void DestroyList_Sq(SqList)
功能：销毁顺序表：
*******************/
void DestroyList_Sq(SqList) {
//释放顺序表L所占用的存储空间
    delete []L.elem;
    L.length=0;
    L.listsize=0;
}
/*******************
Status ListEmpty(SqList L)
功能：
    检测是否为空表
限制：
    初始条件：顺序线性表L已存在
参数：
    SqList L：顺序线性表L
返回值:
    Status类型：TRUE表示L为空表，否则返回FALSE
*******************/
Status ListEmpty(SqList L)
{
    if(L.length == 0) return TRUE;
    else   return FALSE;
}
/*******************
Status ClearList(SqList *L)
功能：
    将L重置为空表
限制：
    初始条件：顺序线性表L已存在
参数：
    SqList &L：顺序线性表L
返回值:
    Status类型：OK表示执行正确
*******************/
Status ClearList(SqList &L)
    L->length=0;
    return OK;
}
/*******************
int ListLength(SqList L)
功能：
    获取L中数据元素个数
限制：
    初始条件：顺序线性表L已存在
参数：
    SqList L：顺序线性表L
返回值:
    int类型：返回L中数据元素个数
*******************/
int ListLength(SqList L) {
    return L.length;
}
/*******************
Status GetElem(SqList L,int i,ElemType *e)
功能：
    用e返回L中第i个数据元素的值（注意i是指位置）
限制：
    初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
参数：
    SqList L：顺序线性表L
    int i：要取出元素的位置
    ElemType *e：所取出的元素
返回值:
    Status类型：OK表示执行正确，ERROR为出错
*******************/
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0 || i<1 || i>L.length) return ERROR;
     *e=L.elem[i-1];
     return ok;
}
/*******************
Status ListInsert(SqList &L,int i,ElemType x)
功能：
     在L中第i个位置前插入新的数据元素x
限制：
     初始条件：顺序线性表L已存在，,1≤i≤ListLength(L)
参数：
     SqList &L：顺序线性表L
     int i：位置i ElemType x：新的数据元素x
返回值:
     Status类型：OK表示执行正确，ERROR为出错
*******************/
Status ListInsert_Sq(SqList & L, int i, ElemType x)
{
    //算法2.4
    //在顺序线性表L中第i个元素之前插入x
    if(i < 1 || i > L.length + 1)  return ERROR;
    if(L.length >= L.listsize)  return ERROR;
    ElemType *q = & (L.elem[i - 1]);
    for(ElemType *p = & (L.elem[L.length - 1]); p >= q; --p) {
        *(p + 1) = *p;              //元素后移
    }
    *q = x;
    ++L.length;              //长度加1
    return OK;
}
/*******************
Status ListDelete(SqList —L,int i,ElemType e)
功能：
    删除L的第i个数据元素
限制：
    初始条件：顺序线性表L已存在，,1≤i≤ListLength(L)
参数：
    SqList —L：顺序线性表L
    int i：位置i
返回值:
    Status类型：OK表示执行正确，ERROR为出错
*******************/
Status ListDelete_Sq(SqList &L, int i)
{
    //算法2.5
    if(i < 1 || i > L.length)    return ERROR;    //输出错误
    ElemType *p = & (L.elem[i - 1]);
    ElemType *q = L.elem + L.length - 1;
    for(++p; p <= q; ++p) {
        * (p - 1) = * p;      //元素前移
    }
    --L.length;
    return OK;
}
/*******************
int LocateElem_Sq(SqList L,ElemType x)
功能：
    找出L中第1个与x满足相等关系的数据元素的位序
限制：
    初始条件：顺序线性表L已存在
参数：
    SqList L：顺序线性表L
    ElemType x：元素x
返回值:
    int类型：返回L中第1个与e满足相等关系的数据元素的位序；若这样的数据元素不存在，则返回值为0 *******************/
int LocateElem_Sq(SqList L, ElemType x)
{
    //算法2.6
    //指向函数的指针的使用
    int i = 1;
    ElemType * p = L.elem;
    while((i <= L.length )&& (*p++ != x))  ++i;
    if(i <= L.length) {
        return i;
    } else {
        return 0;
}

测试代码

int main(void)
{
    //测试函数
    SqList L;
    InitList_Sq(L);
    for(int i = 10; i > 0; i--) {
        ListInsert_Sq(L, 1, i);
    }
    ShowList_Sq(L);    //print L
    int e;
    ListDelete_Sq(L, 4, e);
    ShowList_Sq(L);    //print L
    printf("%d\n", LocateElem_Sq(L, 3, * compare));    //print location of 3
    //函数做参数如何传值呢？？
    SqList Lb;
    InitList_Sq(Lb);
    for(int i = 10; i > 0; i--) {
        ListInsert_Sq(Lb, 1, 2 * i);
    }
    ShowList_Sq(Lb);    //print Lb
    SqList Lc;
    InitList_Sq(Lc);
    ShowList_Sq(Lc);    //print Lc
    MergeList_Sq(L, Lb, Lc);
    ShowList_Sq(Lc);    //print Lc
    return 0;
}

缺点

线性表的顺序存储结构，最大的缺点就是插入和删除时需要移动大量的元素，这显然需要耗费时间。导致这个问题的原因是在于相邻元素的存储位置具有邻居关系，它们在内存中的位置是紧挨着的，中间没有间隙，当然无法快速插入和删除。