线性结构是较简单、常用的一种数据结构,其特点为:除第一个元素无直接前驱、最后一个元素无直接后继外,集合中其余元素均有唯一的直接前驱和直接后继。而线性结构的存储方式有两种:顺序存储和链式存储。

顺序存储结构

用一组地址连续的存储单元一次存储表中的各个元素,表在逻辑结构上相邻的元素在物理结构上也是相邻的,例如:

{a1, a2, a3, ..., an}

实现代码

定义

使用结构体来定义顺序表。

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 20

typedef int ElemType;
typedef int Status;
typedef struct
{
    ElemType data[MAXSIZE]; // 线性表最大长度
    int length; // 线性表实际内容最后一个的位置
}SqList;

创建顺序表

/* 创建表 */
Status CreateList(SqList *L)
{
    int L_length;

    printf("输入表的长度:");
    scanf("%d", &L_length);
    printf("输入 %d 个元素:\n", L_length);

    int i = 0;
    while(i < L_length)
    {
        scanf("%d", &L->data[i]);
        i++;
    }
    L->length = L_length - 1;
    return OK;
}

打印顺序表

/* 打印表 */
Status Print(SqList L)
{
    if(L.length >= 0)
    {
        printf("\n表中的元素为:");
        for(int i = 0; i <= L.length; i++)
        {
            printf("%d ", L.data[i]);
        }
        return OK;
    }
    else
    {
        printf("表为空!!!");
        return ERROR;
    }
}

元素的插入

要做到插入运算,要弄清楚两个关键问题:

  1. 插入不成功的情况该怎么办?

  2. 插入成功后,表发生了什么变化?

    /* 插入元素 */
    Status ListInsert(SqList *L, int i, ElemType e)
    {
     /* 判断表是否满了 */
     if(L->length == MAXSIZE -1)    // L->length 为最后一个元素的下标,而 MAXSIZE 非从 0 开始,所以 -1
     {
         printf("表内元判断表是否满了素已达到最大数量,无法插入...");
         return ERROR;
     }
    
     /* 判断插入的位置是否合法 */
     if(i < 1 || i > L->length + 2)  // i 位置从 1 开始算,小于 1 为非法,L->length 应 +1,考虑到在表最后一位追加,所以 +2
     {
         printf("插入的位置不合法...");
         return ERROR;
     }
    
     /* 把要插入元素的位置腾空,其他元素往后挪,应该先挪最后一个 */
     for(int k = L->length; k >= i - 1; k--)
     {
         L->data[k + 1] = L->data[k];
     }
     L->data[i - 1] = e;
     L->length++;    // 插入了一个元素,自然长度需要 +1
     return OK;
    }

删除元素

/* 删除元素 */
Status DeleteElem(SqList *L, int i, ElemType *e)
{
    if(L->length < 0)
    {
        printf("表内为空...");
        return ERROR;
    }

    if(i < 1 || i > L->length + 1)
    {
        printf("删除的位置不合法!!!");
        return ERROR;
    }

    *e = L->data[i - 1];    // 将要删除的元素返回

    /* 位移 */
    for(int k = i; k <= L->length; k++)
    {
        L->data[k - 1] = L->data[k];    // 从后往前覆盖实现删除
    }
    L->length--;
    return OK;
}

查找元素

/* 查找元素 */
Status GetElem(SqList L, ElemType e)
{
    for(int k = 0; k <= L.length; k++)
    {
        if(e == L.data[k])
            return k + 1;
        else
        {
            printf("该元素不存在...");
            return ERROR;
        }
    }
    return OK;
}

测试代码

int main()
{
    SqList L;   // 定义一个顺序表
    CreateList(&L);     // 创建表
    ElemType e;

    while(1)
    {
        printf("\n1. 浏览表中的数据\n");
        printf("2. 插入元素\n");
        printf("3. 删除元素\n");
        printf("4. 查找元素\n");
        printf("5. 退出\n");
        printf("\n输入序号:");

        int select;
        scanf("%d", &select);

        if(select == 5)
            return 0;

        switch(select)
        {
            case 1:
                Print(L);
                break;
            case 2:
                printf("\n输入要插入的位置:");
                int insPosition, insElem;
                scanf("%d",&insPosition);
                printf("\n输入要插入的元素:");
                scanf("%d",&insElem);
                if(ListInsert(&L, insPosition, insElem) == OK)
                    printf("插入成功!");
                break;
            case 3:
                printf("\n输入要删除元素的位置:");
                int deletePosition;
                scanf("%d", &deletePosition);
                if(DeleteElem(&L, deletePosition, &e) == OK)
                    printf("删除成功,删除的元素为 %d", e);
                break;
            case 4:
                printf("输入要查找的元素:");
                int FindElem, FindElemPosition;
                scanf("%d", &FindElem);
                FindElemPosition = GetElem(L, FindElem);
                if(FindElemPosition == OK)
                    printf("查找成功,位置为:%d", FindElemPosition);
                break;
            default:
                printf("选择失败...");
                break;
        }
    }
    return 0;
}

顺序存储优缺点

优点:

  • 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速存取表中任意位置的元素

缺点:

  • 插入和删除操作需要移动大量的元素
  • 当线性表长度变化较大时,难以确定存储空间的容量
  • 容易造成存储控件的「碎片」