顺序表（顺序存储结构）及初始化过程详解

顺序表是什么

顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙

看到这种“一一对应”的结构和数组非常相似，其实，顺序表存储数据使用的就是数组

顺序表的初始化

使用顺序表存储数据之前，除了要申请足够大小的物理空间之外，为了方便后期使用表中的数据，顺序表还需要实时记录以下 2 项数据：

顺序表申请的存储容量；
顺序表的长度，也就是表中存储数据元素的个数；

后面实现代码之前，一定要注意这两个关键点，需要我们提前去写好

提前分配空间大小要比顺序表长度要长，正常情况下

typedef struct Table{
    int *head;    //声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length;    //顺序表插入数据后的长度
    int size;   //顺序表初始化的分配的容量
} table;

接下来开始学习顺序表的初始化，也就是初步建立一个顺序表。建立顺序表需要做如下工作：

给 head 动态数据申请足够大小的物理空间；
给 size 和 length 赋初值；

#define Size 5 //对Size进行宏定义，表示顺序表申请空间的大小
table initTable(){
    table t;
    t.head = (int*)malloc(Size * sizeof(int));    //构造一个空的顺序表，动态申请存储空间
    if(t.head == NULL){            //若分配内存空间失败，则返回NULL。所以在使用之前一定要判断是否为NULL
        printf("初始化失败");
        exit(0);                   //关闭程序
    }
    t.length = 0;              //空表的长度初始化为0
    t.size = Size;              //空表的初始存储空间为Size
    return t;        
}

我们看到，整个顺序表初始化的过程被封装到了一个函数中，此函数返回值是一个已经初始化完成的顺序表。这样做的好处是增加了代码的可用性，也更加美观。与此同时，顺序表初始化过程中，要注意对物理空间的申请进行判断，对申请失败的情况进行处理，这里只进行了“输出提示信息和强制退出”的操作，可以根据你自己的需要对代码中的 if 语句进行改进

代码实现顺序表中添加元素并打印元素

#include <stdio.h>
#include <stdlib.h>
#define Size 10
typedef struct Table{
    int *head;
    int length;
    int size;
} table;
table initTable(){
    table t;
    t.head = (int*)malloc(Size * sizeof(int));
    if(!t.head){
        printf("初始化失败");
        exit(0);
    }
    t.length = 0;
    t.size = Size;
    return t;
}
void displsyTable(table t){        #输出顺序表内容
    for(int i=0;i<t.length;i++){
        printf("%d",t.head[i]);
        printf("\n");
    }
}
int main()
{
   table t = initTable();
   for(int i=0;i<Size;i++){        #向顺序表添加内容
    t.head[i] = i;
    t.length++;
   }
   displsyTable(t);            #调用函数
    return 0;
}

运行结果

顺序表的基本操作及C语言实现（详解版）

顺序表插入元素

向已有顺序表中插入数据元素，根据插入位置的不同，可分为以下 3 种情况：

插入到顺序表的表头；
在表的中间位置插入元素；
尾随顺序表中已有元素，作为顺序表中的最后一个元素；

虽然数据元素插入顺序表中的位置有所不同，但是都使用的是同一种方式去解决，即：通过遍历，找到数据元素要插入的位置，然后做如下两步工作：

将要插入位置元素以及后续的元素整体向后移动一个位置；
将元素放到腾出来的位置上；

table addTable(table t,int element,int address){
//先检查所给位置是否超过顺序表容量
    if(address>(t.length+1) && address<1){
        printf("无法存入数据");
        return t;
    }
    //再检查空间是否不足
    if(t.length >= t.size){
        printf("空间不足\n");
        t.head = (int *)realloc(t.head, (t.size + 1) * sizeof(int));
        if(t.head == NULL){
            printf("空间分配失败\n");
            return t;
        }
        t.size+=1;
    }
//先将需要后移的元素进行后移，再把需要添加的元素添加到相应的位置，所以这是分两步走
    for (int i = t.length-1; i > address-1 ; i--) {
        t.head[i+1] = t.head[i];
    }
    t.head[address] = element;
    t.length++;
    return t;
}

顺序表删除元素

table delTable(table t,int address){
//删除元素无需检验空间是否不足
    int i;
    if (address > t.length || address < 1) {
        printf("被删除元素的位置有误");
        exit(0);
    }
    for (int i = t.length; i > address ; i--) {
        t.head[i-1] = t.head[i];
    }
    t.length--;
    return t;
}

我觉得这个代码思想更为合理，因为你要是去删除元素，那自然是要传递元素进来，而不是位置

table delTable(table t,int element){
    int index;
    for (int i = 0; i < t.length ; i++) {
        if ( element == t.head[i]) {
            data  = message;
            printf("元素存在，下标为：%d\n",i);
            index = i;
        }
    }
    for (int i = t.length; i > index ; i--) {
        t.head[i-1] = t.head[i];
    }
    t.length--;
    return t;
    }

顺序表查找元素

table findTable (table t,int element){
    //检查需要查询的位置是否合理
    for (int i = 0; i < t.length; i++) {
        if(element == t.head[i]){
            printf("元素存在，下标为%d",i);
            printf("\n");
        }
    }
}

顺序表更改元素

顺序表更改元素的实现过程是：

找到目标元素；
直接修改该元素的值； ```c table replaceTable(table t,int newelement,int address){

int i; if (address > t.length || address < 1) {
```
printf("被删除元素的位置有误");
exit(0);
```
} printf(“该地址原数据：%d\n”,t.head[address]); t.head[address] = newelement; return t; }



完整代码

```c

#include <stdio.h>
#include <stdlib.h>
#define Size 10

typedef struct Table{

    int *head;
    int length;
    int size;


} table;

table initTable(){

    table t;
    t.head = (int*)malloc(Size * sizeof(int));
    if(!t.head){

        printf("初始化失败");
        exit(0);

    }
    t.length = 0;
    t.size = Size;
    return t;

}

void displsyTable(table t){

    for(int i=0;i<t.length;i++){

        printf("%d",t.head[i]);
        printf("\n");
    }

}

table addTable(table t,int element,int address){

//先检查所给位置是否超过顺序表容量

    if(address>(t.length+1) && address<1){

        printf("无法存入数据");
        return t;
    }

    //再检查空间是否不足

    if(t.length >= t.size){

        printf("空间不足\n");
        t.head = (int *)realloc(t.head, (t.size + 1) * sizeof(int));
        if(t.head == NULL){
            printf("空间分配失败\n");

            return t;
        }
        t.size+=1;

    }

//先将需要后移的元素进行后移，再把需要添加的元素添加到相应的位置，所以这是分两步走

    for (int i = t.length-1; i > address-1 ; i--) {

        t.head[i+1] = t.head[i];

    }

    t.head[address] = element;

    t.length++;

    return t;

}


table delTable(table t,int address){

//删除元素无需检验空间是否不足
    int i;
    if (address > t.length || address < 1) {
        printf("被删除元素的位置有误");
        exit(0);
    }

    for (int i = t.length; i > address ; i--) {
        t.head[i-1] = t.head[i];
    }
    t.length--;
    return t;

}

table findTable (table t,int element){

    //检查需要查询的位置是否合理


    for (int i = 0; i < t.length; i++) {

        if(element == t.head[i]){

            printf("元素存在，下标为%d",i);
            printf("\n");
        }
    }

}

table replaceTable(table t,int newelement,int address){

    int i;
    if (address > t.length || address < 1) {
        printf("被删除元素的位置有误");
        exit(0);
    }
    printf("该地址原数据：%d\n",t.head[address]);
    t.head[address] = newelement;
    return t;
}


int main()
{
    table t = initTable();

    for(int i=0;i<Size;i++){

        t.head[i] = i;
        t.length++;

    }
    delTable(t,7);
    addTable(t,20,5);
    findTable(t,3);
    replaceTable(t,20,3);
    displsyTable(t);
    return 0;
}

顺序表的应用

顺序表创建和就地逆置

本题要求

本题要求实现顺序表的创建和就地逆置操作函数。L是一个顺序表，函数ListCreate_Sq(SqList &L)用于创建一个顺序表，函数ListReverse_Sq(SqList &L)是在不引入辅助数组的前提下将顺序表中的元素进行逆置，如原顺序表元素依次为1,2,3,4，则逆置后为4,3,2,1

函数接口定义

Status ListCreate_Sq(SqList &L);
void ListReverse_Sq(SqList &L);

裁判测试程序样例

//库函数头文件包含
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//函数状态码定义
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2

typedef int  Status;

//顺序表的存储结构定义
#define LIST_INIT_SIZE  100
#define LISTINCREMENT   10
typedef int ElemType;  //假设线性表中的元素均为整型
typedef struct{
    ElemType* elem;   //存储空间基地址
    int length;       //表中元素的个数
    int listsize;     //表容量大小
}SqList;    //顺序表类型定义

Status ListCreate_Sq(SqList &L);
void ListReverse_Sq(SqList &L);

int main() {
    SqList L;
    ElemType *p;

    if(ListCreate_Sq(L)!= OK) {
        printf("ListCreate_Sq: 创建失败！！！\n");
        return -1;
    }

    ListReverse_Sq(L);

    if(L.length){
    for(p=L.elem;p<L.elem+L.length-1;++p){
        printf("%d ",*p);
    }
    printf("%d",*p); 
    }
    return 0;
}
/* 请在这里填写答案 */

本题答案

简单来说，不管数据元素是奇数还是偶数，先是第一个元素和最后一个互换，然后第一个元素向后递增，后面一个元素向前递减

何时停止？ 数组长度/2 即为分界线

有人会问，数组元素长度为奇数，结果为多少，比如5，其结果运算后为2，而非2.5更不是3

这道题细分下来就两个知识点考察

顺序表创建和初始化
就地逆置的核心运算思想（L.elem[i]=L.elem[L.length-i-1]）

Status ListCreate_Sq(SqList &L)
{
    int n;
    scanf("%d",&n);
    if(n<0)
    return FALSE;
    L.elem =new ElemType[n+1];
    if(!L.elem)
        return ERROR;
    L.length =n;
    for(int i=0;i<n;i++)
    scanf("%d",&L.elem[i]);
    return OK;
}
void ListReverse_Sq(SqList &L)
{
    for(int i=0;i<L.length/2;i++)
    {
        int t=L.elem[i];
        L.elem[i]=L.elem[L.length-i-1];
        L.elem[L.length-i-1]=t;
    }
    return ;
}

有序顺序表的插入

本题要求

本题要求实现递增顺序表的有序插入函数。L是一个递增的有序顺序表，函数Status ListInsert_SortedSq(SqList &L, ElemType e)用于向顺序表中按递增的顺序插入一个数据。比如：原数据有：2 5，要插入一个元素3，那么插入后顺序表为2 3 5。要考虑扩容的问题

函数接口定义

Status ListInsert_SortedSq(SqList &L, ElemType e);

裁判测试程序样例

//库函数头文件包含
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//函数状态码定义
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2

typedef int  Status;

//顺序表的存储结构定义
#define LIST_INIT_SIZE  100
#define LISTINCREMENT   10
typedef int ElemType;  //假设线性表中的元素均为整型
typedef struct{
    ElemType* elem;   //存储空间基地址
    int length;       //表中元素的个数
    int listsize;     //表容量大小
}SqList;    //顺序表类型定义

//函数声明
Status ListInsert_SortedSq(SqList &L, ElemType e);

//顺序表初始化函数
Status InitList_Sq(SqList &L)
{
    //开辟一段空间
    L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    //检测开辟是否成功
    if(!L.elem){
        exit(OVERFLOW);
    }
    //赋值
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;

    return OK;
}

//顺序表输出函数
void ListPrint_Sq(SqList L)
{
    ElemType *p = L.elem;//遍历元素用的指针


    for(int i = 0; i < L.length; ++i){
        if(i == L.length - 1){
            printf("%d", *(p+i));
        }
        else{
            printf("%d ", *(p+i));
        }
    }
}
int main()
{
    //声明一个顺序表
    SqList L;
    //初始化顺序表
    InitList_Sq(L);

    int number = 0;
    ElemType e;

     scanf("%d", &number);//插入数据的个数 

    for(int i = 0; i < number; ++i)
    {
    scanf("%d", &e);//输入数据
        ListInsert_SortedSq(L, e);
    }

    ListPrint_Sq(L);

    return  0;
}


/* 请在这里填写答案 */

本题答案

本题考察两点

顺序表用户自定义输入
插入排序

#include<stdio.h>

int main(){

    int a[5] = {1,3,2,7,4};
    int length = 5;

    for (int i = 1; i < length; i++) {

        for (int j = 0; j < i; j++) {
            if(a[i] < a[j]){
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }

    }

    for (int i = 0; i < length; i++) {
        printf("%d\n",a[i]);
    }


}

顺序表区间元素删除

我自己写的代码，无法通过，因为这里要求空间复杂度和时间复杂度，唉……

写了半天，还是要抄别人的

#include<stdio.h>
#include<math.h>
int main()
{
    int n,x,y;
    scanf("%d",&n);
    int a[n],temp,i,j,b[n];
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    scanf("%d %d",&x,&y);
    int count=0,flag=0;
    i=0,j=0;
    while(i<n)
    {
        if(a[i]>=x&&a[i]<=y)
        i++;
        else
        a[j++]=a[i++];
    }
    for(i=0;i<j;i++)
    {
        if(flag==0)
        {
            printf("%d",a[i]);flag=1;
        }
        else
        printf(" %d",a[i]);
    }
}

数据结构（C语言版）

02--顺序表

顺序表（顺序存储结构）及初始化过程详解

顺序表是什么

顺序表的初始化

代码实现顺序表中添加元素并打印元素

顺序表的基本操作及C语言实现（详解版）

顺序表插入元素

顺序表删除元素

顺序表查找元素

顺序表更改元素

顺序表的应用

顺序表创建和就地逆置

本题要求

函数接口定义

裁判测试程序样例

本题答案

有序顺序表的插入

本题要求

函数接口定义

裁判测试程序样例

本题答案

顺序表区间元素删除