阅读:0       作者:解学武

顺序表(顺序存储结构)详解

顺序表又称顺序存储结构,是线性表的一种,专门存储逻辑关系为“一对一”的数据。

顺序表存储数据的具体实现方案是:将数据全部存储到一整块内存空间中,数据元素之间按照次序挨个存放。

举个简单的例子,将 {1,2,3,4,5} 这些数据使用顺序表存储,数据最终的存储状态如下所示:


图 1 顺序存储结构示意图

顺序表的建立

使用顺序表存储数据,除了存储数据本身的值以外,通常还会记录以下两样数据:
  • 顺序表的最大存储容量:顺序表最多可以存储的数据个数;
  • 顺序表的长度:当前顺序表中存储的数据个数。

C 语言中,可以定义一个结构体来表示顺序表:
typedef struct{
    int * head; //定义一个名为head的长度不确定的数组,也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size; //记录顺序表的存储容量
}Table;

尝试建立一个顺序表,例如:
#define Size 5 //对Size进行宏定义,表示顺序表的最大容量
void initTable(Table * t) {
    //构造一个空的顺序表,动态申请存储空间
    t->head = (int*)malloc(Size * sizeof(int));
    //如果申请失败,作出提示并直接退出程序
    if (!t->head)
    {
        printf("初始化失败");
        exit(0);
    }
    //空表的长度初始化为0
    t->length = 0;
    //空表的初始存储空间为Size
    t->size = Size;
}
如上所示,整个建立顺序表的过程都封装在一个函数中,建好的顺序表可以存储 5 个逻辑关系为“一对一”的整数。

通常情况下,malloc() 函数都可以成功申请内存空间,当申请失败时,示例程序中进行了“输出失败信息和强制程序退出”的操作,您可以根据实际需要修改代码。

顺序表的使用

通过调用 initTable() 函数,就可以成功地创建一个顺序表,还可以往顺序表中存储一些元素。

例如,将 {1,2,3,4,5} 存储到顺序表中,实现代码如下:
#include <stdio.h>
#include <stdlib.h>
#define Size 5 //对Size进行宏定义,表示顺序表的最大容量
typedef struct{
    int* head;
    int length;
    int size;
}Table;
void initTable(Table * t) {
    //构造一个空的顺序表,动态申请存储空间
    t->head = (int*)malloc(Size * sizeof(int));
    //如果申请失败,作出提示并直接退出程序
    if (!t->head)
    {
        printf("初始化失败");
        exit(0);
    }
    //空表的长度初始化为0
    t->length = 0;
    //空表的初始存储空间为Size
    t->size = Size;
}
//输出顺序表中元素的函数
void displayTable(Table t) {
    int i;
    for (i = 0; i < t.length; i++) {
        printf("%d ", t.head[i]);
    }
    printf("\n");
}
int main() {
    int i;
    Table t = { NULL,0,0 };
    initTable(&t);
    //向顺序表中添加{1,2,3,4,5}
    for (i = 1; i <= Size; i++) {
        t.head[i - 1] = i;
        t.length++;
    }
    printf("顺序表中存储的元素分别是:\n");
    displayTable(t);
    free(t.head);//释放申请的堆内存
    return 0;
}
程序运行结果如下:

顺序表中存储的元素分别是:
1 2 3 4 5