顺序表

依次存储，依次输出。

一：思路(重要代码)

定义：常量

#define INIT_SIZE 100//线性表存储空间的初始分配量
#define INCREMENT 10//线性表存储空间的分配增量
typedef int ElemType;//定义ElemType名称来替代数据类型int
typedef struct{
    ElemType *elem;//存储空间基址
    int length;//当前长度
    int listsize;//当前分配的储存容量
}SqList;

---

初始化：最长长度listsize （申请空间并判断空间是否申请成功） 当前长度 length 空间基址 *elem

int InitSqList(SqList *L)
{
    L->elem=(ElemType *)malloc(INIT_SIZE*sizeof(ElemType));
    //存储空间分配失败，返回-1
    if(!L->elem) return -1;
    //空间分配成功
    L->length=0;
    L->listsize=INIT_SIZE;
    return 1;
}

---

添加数据：（1）判断空间是否够用
（2）添加数据（elem[]）

for(i=0;i<n;i++)
{
    scanf("%d",&L->elem[i]);    
}
L->length=n;
}

---

显示数据：通过循环输出

for(i=0;i<L->length;i++)
    {
        printf("%d ",L->elem[i]);

    }

---

插入数据：（1）判断位置是否合法
（2）若length=listsize 则需要重新分配空间（realloc:两个参数，第一个是原来的地址，第二个是重新分配的地址）
(3)通过循环找到需要插入的位置 插入即可

for(j=L->length-1;j>=i-1;j--)
    {
        L->elem[j+1]=L->elem[j];
    }

    L->elem[i-1]=e;
    
    L->length++;

---

删除数据：（1）判断位置是否合法
（2）通过循环将值覆盖了

for(j=i-1;j<L->length-1;j++)
    {
        L->elem[j]=L->elem[j+1];
    }

    L->length--;

---

查找数据：（1）判断位置是否合法
（2）循环依次找出

while(i<=L.length&&L.elem[i-1]!=e)  i++;

    if(i<=L.length) return i;

（二）

不足：（1）易产生未使用的内存块，空间利用率低
（2）查找的复杂度过高

（三）完整源代码

#include <stdio.h>
#include <stdlib.h>
//常量定义最好用大写
#define INIT_SIZE 100//线性表存储空间的初始分配量

#define INCREMENT 10//线性表存储空间的分配增量

typedef int ElemType;//定义ElemType名称来替代数据类型int

typedef struct{

    ElemType *elem;//存储空间基址
    
    int length;//当前长度
    
    int listsize;//当前分配的储存容量
                //（以sizeof(ElemType)为单位）
}SqList;//顺序表

//创建顺序表：分配初始空间可以存100个数据、当前顺序表长度length设置为0.当前分配的存储容量Listsize设置为初始空间值100

//初始化顺序表，成功返回1，失败返回-1
int InitSqList(SqList *L)
{
    //利用malloc函数分配INIT_SIZE个数据储存空间，并且把储存空间的起始位置利用顺序表SqList
    L->elem=(ElemType *)malloc(INIT_SIZE*sizeof(ElemType));

    //存储空间分配失败，返回-1
    if(!L->elem) return -1;
    //空间分配成功

    L->length=0;

    L->listsize=INIT_SIZE;

    return 1;
}
//输入n个数据到顺序表中
void inputSqList(SqList *L)
{
    int n;
    int i;

    printf("请输入添加顺序表中数据的总个数:");

    scanf("%d",&n);
    
    //超界重新输入总个数n
    while(n>L->listsize)
    {
        printf("超界！");

        scanf("%d",&n);
    }
    //从键盘输入n个数据到顺序表L中
    printf("请输入%d个数据",n);

    for(i=0;i<n;i++)
    {
        scanf("%d",&L->elem[i]);    
    }
    L->length=n;
}
//显示顺序表L已存放的数据

void outputSqList(SqList *L)
{

    int i;
    for(i=0;i<L->length;i++)
    {
        printf("%d ",L->elem[i]);

    }
    printf("\n");
}

//向顺序表指定位置插入数据，成功返回1，失败返回-1
int InsertSqList(SqList *L,int i,ElemType e)
{
    
    ElemType *newbase;//暂存扩容后的新地址
    
    int j;//搬数据时用
    //判断插入数据位置是否正确

    if(i>L->listsize||i<0) return -1;

    //检查容量空间是否够用

    if(L->length==L->listsize) 
    {
        //扩充容量：利用realloc重新分配空间
        newbase=(ElemType*)realloc(L->elem,(L->listsize+INCREMENT)*sizeof(ElemType));//两个参数，第一个是原来的地址，第二个是重新分配的地址

        if(!newbase) return -1;

        L->elem=newbase;

        L->listsize=L->listsize+INCREMENT;
    }

    //位置正确，容量充足，插入数据到顺序表中
    for(j=L->length-1;j>=i-1;j--)
    {
        L->elem[j+1]=L->elem[j];
    }

    L->elem[i-1]=e;
    
    L->length++;
    return 1;
}
//删除指定位置的数据元素，成功返回1，失败返回-1
int DeleteSqList(SqList *L,int i,ElemType *e)
{
    int j;

    if(i<1||i>L->length) return -1;
    
    *e=L->elem[i-1];
    //从待删除数据之后依次向前移一个数据
    
    for(j=i-1;j<L->length-1;j++)
    {
        L->elem[j]=L->elem[j+1];
    }

    L->length--;
    return 1;

}
//查找指定元素 成功返回在L中的顺序，失败返回0

int LoateSqList(SqList L,ElemType e)
{

    int i=1;//i的初值为第一个元素的位序

    while(i<=L.length&&L.elem[i-1]!=e)  i++;

    if(i<=L.length) return i;

    else return 0;
}

int main()
{
    SqList L;

    int flag;

    int a,x,loc,i;

    ElemType e;

    flag=InitSqList(&L);

    if(flag==1)

        printf("顺序表L分配空间成功\n");

    else

        printf("顺序表L分配空间失败\n");

    inputSqList(&L);

    printf("顺序表L中的数据：");

    outputSqList(&L);

    printf("请输入需要删除元素的值:");

    scanf("%d",&loc);

    flag=DeleteSqList(&L,loc,&e);

    printf("删除%d后线性表的元素依次为:",e);

    outputSqList(&L);

    printf("请输入需要插入的位置:");
    
    scanf("%d",&i);

    InsertSqList(&L,i,100);
    
    outputSqList(&L);

    printf("请输入需要查找元素的值:");

    scanf("%d",&x);

    a=LoateSqList(L,x);

    printf("顺序表L中%d的位置%d\n",x,a);

    return 0;
}