顺序存储线性表实现

顺序存储线性表实现

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

优点：随机存取表中元素。缺点：插入和删除操作需要移动元素。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

给出两种基本实现：

/*
静态顺序存储线性表的基本实现
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIST_INITSIZE 100
#define ElemType int
#define Status int
#define OK     1
#define ERROR  0
typedef struct
{
    ElemType elem[LIST_INITSIZE];
    int length;
}SqList;
//函数介绍
Status InitList(SqList *L); //初始化
Status ListInsert(SqList *L, int i,ElemType e);//插入
Status ListDelete(SqList *L,int i,ElemType *e);//删除
void ListPrint(SqList L);//输出打印
void DisCreat(SqList A,SqList *B,SqList *C);//拆分(按正负)，也可以根据需求改
//虽然思想略简单，但是要写的没有错误，还是需要锻炼coding能力的
Status InitList(SqList *L)
{
    L->length = 0;//长度为0
    return OK;
}
Status ListInsert(SqList *L, int i,ElemType e)
{
    int j;
    if(i<1 || i>L->length+1)
        return ERROR;//判断非法输入
    if(L->length == LIST_INITSIZE)//判满
    {
        printf("表已满");//提示
        return ERROR;//返回失败
    }
    for(j = L->length;j > i-1;j--)//从后往前覆盖，注意i是从1开始
        L->elem[j] = L->elem[j-1];
    L->elem[i-1] = e;//在留出的位置赋值
    (L->length)++;//表长加1
    return OK;//反回成功
}
Status ListDelete(SqList *L,int i,ElemType *e)
{
    int j;
    if(i<1 || i>L->length)//非法输入/表空
        return ERROR;
    *e = L->elem[i-1];//为了返回值
    for(j = i-1;j <= L->length;j++)//从前往后覆盖
        L->elem[j] = L->elem[j+1];
    (L->length)--;//长度减1
    return OK;//返回删除值
}
void ListPrint(SqList L)
{
    int i;
    for(i = 0;i < L.length;i++)
        printf("%d ",L.elem[i]);
    printf("\n");//为了美观
}
void DisCreat(SqList A,SqList *B,SqList *C)
{
    int i;
    for(i = 0;i < A.length;i++)//依次遍历A中元素
    {
        if(A.elem[i]<0)//判断
            ListInsert(B,B->length+1,A.elem[i]);//直接调用插入函数实现尾插
        else
            ListInsert(C,C->length+1,A.elem[i]);
    }
}
int main(void)
{
    //复制的
    SqList L;
    SqList B, C;
    int i;
    ElemType e;
    ElemType data[9] = {11,-22,33,-3,-88,21,77,0,-9};
    InitList(&L);
    InitList(&B);
    InitList(&C);
    for (i = 1; i <= 9; i++)
        ListInsert(&L,i,data[i-1]);
    printf("插入完成后L = : ");
    ListPrint(L);
    ListDelete(&L,1,&e);
    printf("删除第1个后L = : ");
    ListPrint(L);
    DisCreat(L , &B, &C);
    printf("拆分L后B = : ");
    ListPrint(B);
    printf("拆分L后C = : ");
    ListPrint(C);
    printf("拆分L后L = : ");
    ListPrint(L);
}

静态：长度固定

动态：不够存放可以加空间（搬家）

/*
子任务名任务:1_2 动态顺序存储线性表的基本实现
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define Status int
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define ElemType int
typedef struct
{
    ElemType * elem;
    int length;
    int listsize;
}SqList;
//函数介绍
Status InitList(SqList *L); //初始化
Status ListInsert(SqList *L, int i,ElemType e);//插入
Status ListDelete(SqList *L,int i,ElemType *e);//删除
void ListPrint(SqList L);//输出打印
void DeleteMin(SqList *L);//删除最小
Status InitList(SqList *L)
{
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//申请100空间
    if(!L->elem)//申请失败
        return ERROR;
    L->length = 0;//长度0
    L->listsize = LIST_INIT_SIZE;//容量100
    return OK;//申请成功
}
Status ListInsert(SqList *L,int i,ElemType e)
{
    int j;
    ElemType *newbase;
    if(i<1 || i>L->length+1)
        return ERROR;//非法输入
    if(L->length >= L->listsize)//存满了，需要更大空间
    {
        newbase = (ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));//大10的空间
        if(!newbase)//申请失败
            return ERROR;
        L->elem = newbase;//调指针
        L->listsize+= LISTINCREMENT;//新容量
    }
    for(j=L->length;j>i-1;j--)//从后往前覆盖
        L->elem[j] = L->elem[j-1];
    L->elem[i-1] = e;//在留出的位置赋值
    L->length++;//长度+1
    return OK;
}
Status ListDelete(SqList *L,int i,ElemType *e)
{
    int j;
    if(i<1 || i>L->length)//非法输入/表空
        return ERROR;
    *e = L->elem[i-1];//为了返回值
    for(j = i-1;j <= L->length;j++)//从前往后覆盖
        L->elem[j] = L->elem[j+1];
    (L->length)--;//长度减1
    return OK;//返回删除值
}
void ListPrint(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
        printf("%d ",L.elem[i]);
    printf("\n");//为了美观
}
void DeleteMin(SqList *L)
{
    //表空在Listdelete函数里判断
    int i;
    int j=0;//最小值下标
    ElemType *e;
    for(i=0;i<L->length;i++)//寻找最小
    {
        if(L->elem[i] < L->elem[j])
            j=i;
    }
    ListDelete(L,j+1,&e);//调用删除，注意j要+1
}
int main(void)
{
    SqList L;
    int i;
    ElemType e;
    ElemType data[9] = {11,-22,-33,3,-88,21,77,0,-9};
    InitList(&L);
    for (i = 1; i <= 9; i++)
    {
        ListInsert(&L,i,data[i-1]);
    }
    printf("插入完成后 L = : ");
    ListPrint(L);
    ListDelete(&L, 2, &e);
    printf("删除第 2 个后L = : ");
    ListPrint(L);
    DeleteMin(&L);
    printf("删除L中最小值后L = : ");
    ListPrint(L);
    DeleteMin(&L);
    printf("删除L中最小值后L = : ");
    ListPrint(L);
    DeleteMin(&L);
    printf("删除L中最小值后L = : ");
    ListPrint(L);
}