线性表的顺序表示和实现

数据结构 线性表顺序表示

线性表的顺序表示指的是用一组地址连续的存储单元一次存储线性表的数据元素。

以元素在计算机内“物理位置相邻”来表示线性表中元素之间的逻辑关系。

通常用数组来描述数据结构中的顺序存储结构。
由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组。

//-----线性表的动态分配顺序存储结构---
#define LIST_INIT_SIZE 100 //线性表存储空间的出事分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
typedef struct {
    ElemType *elem; //存储空间基址
    int length;  //当前长度
    int listsize;  //当前分配的存储容量（以sizeof(ElemType)为单位）
}SqList;

数组指针elem指示线性表的基地址，length指示线性表的当前长度。
顺序表的初始化操作就是为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度设为“0”。listsize指示顺序表当前分配的存储空间大小，一旦因插入元素而空间不足时，可进行再分配，即为顺序表增加一个大小为存储LISTINCREMENT个数据元素的空间。

Status InitList_Sq(SqList &L) {
    //构造一个空的线性表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 OK;
} //InitList_Sq

顺序线性表的插入元素算法：
一般情况下，在第i（1<=i<=n)个元素之前插入一个元素时，需将第n至第i（共n-i+1)个元素向后移动一个位置，算法如下：

Status ListInsert_Sq(SqList &L, int i, ElemType e) {
//在顺序线性表L中第i个位置之前插入新的元素e，i的合法值为1<=i<=ListLength_Sq(L)+1
    if(i<1||i>L.length+1) return ERROR; //i值不合法
    if(L.length>=L.listsize) { //当前存储空间已满，增加分配
    newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType));
    if(!newbase)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;
} //ListInsert_Sq

反之，线性表的删除操作是使长度为n的线性表变为长度为n-1的线性表。为了删除第4个元素，必须将从第5个至第8个元素都依次向前移动一个位置。

Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
//在顺序线性表L中删除第i个元素，并用e返回其值i的合法值为1<=i<=ListLength_Sq(L)
    if((i<1)||(i>L.length)) return ERROR; //i值不合法
    p = &(L.elem[i-1]); //p为被删除元素的位置
    e = *p; //被删除元素的值赋给e
    q = L.elem+L.length-1;  //表尾元素的位置
    for(++p;p<=q;++p) *(p-1) = *p; //被删除元素之后的元素左移
    --L.length;
    return OK;
} //ListDelete_Sq

顺序表的合并

void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) {
//已知顺序线性表La和Lb的元素按值非递减排列归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列
    pa = La.elem; pb = Lb.elem;
    Lc.listsize = Lc.length = La.length+Lb.length;
    pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType));
    if(!Lc.elem) exit(OVERFLOW);  //存储分配失败
    pa_last = La.elem + La.length -1;
    pb_last = Lb.elem + Lb.length -1;
    while(pa <= pa_last && pb<=pb_last) { //归并
        if(*pa<=*pb) *pc++=*pa++;
        else
        *pc++ = *pb++;
    }
    while(pa<=pa_last) *pc++ = *pa++;//插入La的剩余元素
    while(pb<=pb_last) *pc++ = *pb++;  //插入Lb的剩余元素
} //MergeList_Sq

下面例子转自http://blog.csdn.net/lincyang/article/details/8606682
注意，该博文中的程序有错误，请看该博文评论，出现两处错误，一处为i>index修改为i>=index另一处为在插入数据的时候应该先把该数据之后的数据右移再插入数据，博主刚好把顺序颠倒。
下面为已改正的程序：

//201707
//Charley
//linear list
//Sequence Storage Structure
//
#include <stdio.h>
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define MAXLENGTH 20
struct sequencelist
{
    int data[MAXLENGTH];
    int length;
};
//get list elements
//make sure element is NOT NULL when calling.
int getElement(struct sequencelist list,int index, int *element)
{
    printf("\ngetElement\n");
    int length = list.length;
    printf("length is %d\n",length);
    if(length==0||index<0||index>=length)
        return ERROR;
    *element = list.data[index];
    return OK;
}
//insert operation
//
int insert(struct sequencelist *list, int index, int element)
{
    printf("\ninsert\n");
    int i=0, length = list->length;
    printf("length is %d\n",length);
    if(length==0||index<0||index>length||length>=MAXLENGTH)
        return ERROR;
    for(i=length-1;i>=index;i--)
    {
        list->data[i+1]=list->data[i];
    }
    list->data[index]=element;
    list->length++;
    return OK;
}
//Delete opration
//
int delete(struct sequencelist *list, int index)
{
    printf("\ndelete\n");
    int i=0, length = list->length;
    printf("length is %d\n",length);
    if(length==0||index<0||index>length-1)
        return ERROR;
    for(i=index;i<length-1;i++)
    {
        list->data[i]=list->data[i+1];
    }
    list->data[length-1]='\0';
    list->length--;
    return OK;
}
int main()
{
    struct sequencelist list =
    {
        {3,1,5,7,12,78,34},
        7
    };
    printf("list length : %d\n",list.length);
    //Test get
    int *element = 0, test = 8;
    element = &test;
    if(OK == getElement(list,2,element))
    {
        printf("list get 2:%d\n", *element);
    }
    //Test insert
    if(OK==insert(&list,7,520))
    {
        printf("list insert 7 ok!\n");
    }
    if(OK==getElement(list,7,element))
    {
        printf("list get 7 :%d\n", *element);
    }
    if(OK==insert(&list,3,520))
    {
        printf("list insert 3 ok!\n");
    }
    if(OK==getElement(list,3,element))
    {
        printf("list get 3 :%d\n",*element);
    }
    //Test delete
    if(OK == delete(&list,3))
    {
        printf("list delete 3 ok\n");
    }
    if(OK == getElement(list,3,element))
    {
        printf("list get 3 :%d\n",*element);
    }
    if(OK == delete(&list,6))
    {
        printf("list delete 6 ok\n");
    }
    if(OK == getElement(list,6,element))
    {
        printf("list get 6:%d\n", *element);
    }
    else
    {
        printf("list get ERROR!\n");
    }
}