C语言-数据结构-可变长顺序表的初始化，插入和输出

问题描述:

实现可变长顺序表的建表过程。任务要求：通过顺序表的初始化、插入算法，实现顺序表的建表，并依次输出顺序表元素。

【输入形式】

第一行输入整数N(1<=N<=100)，表示创建长度为N的顺序表；

第二行输入N个整数，表示顺序表的N个元素，依次放入表中；

【输出形式】

依次输出顺序表的全部元素。(以空格分隔）

【样例输入】

5

1 2 3 4 5

【样例输出】

1 2 3 4 5

采用可变长顺序表，顺序表长度可根据数据存储需要，动态增加存储空间。

实现可变长顺序表要定义：常量INIT_SIZE表示顺序表初始化的初始长度；常量INCREM表示当存储空间不够，每次增加的单元数；顺序表可以存放任意数据类型的数据，上述定义中，名称ElemType表示此处代表基本类型int。

#include <stdio.h>
#include <stdlib.h>
#define INIT_SIZE 5       //初始分配的存储空间长度
#define INCREM 3          //存储空间再分配的增量
#define OK 1
#define ERROR 0

下面定义结构体类型

typedef int ElemType;
/*顺序表结构*/
typedef struct Sqlist{
	ElemType *slist;
	int length;
	int listsize;
}Sqlist;

顺序表的初始化：

注意：顺序表结构定义时，并未分配存储空间，因此需要进行初始化为顺序表分配存储空间。初始化空间大小为listsize,和表长length。

顺序表的初始化就是为顺序表分配连续的一组存储单元。初始化好的顺序表的初始表长为0。

注意：函数malloc由头文件<malloc.h>提供。向系统申请分配存储单元，并不能保证一定申请成功，因此初始化有可能因未申请到空间而导致失败（符号OK表示常量1，ERROR表示常量0）。

int initSq(Sqlist *L)
{
    L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));
    if(!L->slist)return 0;     //初始化失败返回0
    L->length=0;               //置为空表长度为0
    L->listsize=INIT_SIZE;     //设置初始空间容量
    return 1;
}

接下来是插入和输出操作：

顺序表的插入算法：

在顺序表的某个位置插入一个元素，顺序表中元素的前后逻辑关系会发生变化，例如在顺序表第i个位置处插入一个新元素。

 基本步骤：

（1）先移动元素，需要从线性表最后一个元素开始向后移动；

（2）插入新元素；

（3）修改表长加一；（容易忘记）

/*在i位置插入元素：插入成功返回1，不成功返回0*/
int insertSq(Sqlist *L, int i,ElemType e)
{
   if(i<0||i>L->length+1)return 0;     //插入位置不正确返回0
    if(L->length+1>L->listsize)        //当前储存空间已满，进行空间增量
    {
        L->slist=(ElemType*)realloc(L->slist,(L->listsize+INCREM)*sizeof(ElemType));
        if(!L->slist)return 0;         //申请存储空间失败
        L->listsize+=INCREM;
    }
    int j;
    for(j=L->length;j>i;j--)     //插入位置后数据元素依次后移
    {
        L->slist[j]=L->slist[j-1];
    }
    L->slist[i]=e;     //插入新数据元素
    L->length++;       //当前表长加一
    return 1;
}
/*输出顺序表元素*/
void printSq(Sqlist *L)
{
    int i;
    for(i=0;i<L->length;i++)
    {
        printf("%d ",L->slist[i]);     //依次输出表中元素
    }
    printf("\n");
}

最后实现完整代码查看结果

#include <stdio.h>
#include <stdlib.h>
#define INIT_SIZE 5       //初始分配的存储空间长度
#define INCREM 3          //存储空间再分配的增量
#define OK 1
#define ERROR 0
typedef int ElemType;
/*顺序表结构*/
typedef struct Sqlist{
	ElemType *slist;
	int length;
	int listsize;
}Sqlist;
int initSq(Sqlist *L)
{
    L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));
    if(!L->slist)return 0;     //初始化失败返回0
    L->length=0;               //置为空表长度为0
    L->listsize=INIT_SIZE;     //设置初始空间容量
    return 1;
}
/*在i位置插入元素：插入成功返回1，不成功返回0*/
int insertSq(Sqlist *L, int i,ElemType e)
{
   if(i<0||i>L->length+1)return 0;     //插入位置不正确返回0
    if(L->length+1>L->listsize)        //当前储存空间已满，进行空间增量
    {
        L->slist=(ElemType*)realloc(L->slist,(L->listsize+INCREM)*sizeof(ElemType));
        if(!L->slist)return 0;         //申请存储空间失败
        L->listsize+=INCREM;
    }
    int j;
    for(j=L->length;j>i;j--)     //插入位置后数据元素依次后移
    {
        L->slist[j]=L->slist[j-1];
    }
    L->slist[i]=e;     //插入新数据元素
    L->length++;       //当前表长加一
    return 1;
}
/*输出顺序表元素*/
void printSq(Sqlist *L)
{
    int i;
    for(i=0;i<L->length;i++)
    {
        printf("%d ",L->slist[i]);     //依次输出表中元素
    }
    printf("\n");
}
int main()
{
    Sqlist sq;
    ElemType e;
    int n;
    if(initSq(&sq)){
       scanf("%d",&n);
       /*补充代码，实现n个元素顺序表的创建*/
       int i;
       for(i=0;i<n;i++)
       {
           scanf("%d",&e);
           insertSq(&sq,i,e);
       }
       printSq(&sq);
    }
    return 0;
}

运行结果如下：