【数据结构】顺序表

weixin_64223285

317人浏览 · 2026-06-12 19:07:26

weixin_64223285 · 2026-06-12 19:07:26 发布

数据结构的关系分为逻辑关系和物理关系：

逻辑关系：集合（无关系）、线性结构（一对一）、树状结构（一对多）和图状结构（多对多）。

物理关系：顺序结构（连续存储）和离散结构（离散存储）。其中顺序结构也称为顺序存储，离散结构也称为链式存储。
线性表中的任何一个数据元素有且只有一个直接前驱，以及有且只有一个直接后继，并且首元素是没有前驱的，尾元素是没有后继的。常见的线性表有数组、链表、栈和队列。

其中顺序表就是逻辑上是线性结构即一对一的关系，物理上也是顺序结构即内存上连续的。因此只要知道顺序表的首地址，就可以对顺序表中任何一个元素进行随机访问。

以下是有关线性表的代码。其中main函数中的show是为了方便修改打印的格式。

/******************************************************************************
 * 文件名：main.c
 * 功能：顺序表（Sequence List）测试程序，演示顺序表的创建、插入（头插/尾插/递增
 *       插入）、删除、遍历打印等基本操作。
 * 作者：不想写代码0
 * 邮箱：xxx@example.com
 *
 * Copyright (c) 2026 6.12 All rights reserved.
 * 本代码仅供学习和教学使用，未经作者许可不得用于商业目的。
 ******************************************************************************/

#include "sequencelist.h"

/*
 * 功能：遍历打印顺序表所有元素及元信息（索引 : 值 - 容量 - 末位置）
 * 参数：sq - 顺序表指针，为 NULL 时输出提示并返回
 * 返回：无
 */
void show(SqList_t *sq)
{
    if(sq == NULL )
    {
        printf("sq is NULL\n");
        return ;
    }

    for(int i = 0;i <= sq->Last;i ++)
    {
        printf("%d :%d-Size:%d-Last:%d\n",i,sq->Addr[i],sq->Size,sq->Last);
    }
    return ;
}

int main()
{
    SqList_t *sq = SequenceList_Create(10);
    SequenceList_TailAdd(sq,15);
    SequenceList_TailAdd(sq,40);
    SequenceList_TailAdd(sq,100);
    // SequenceList_Add_incre(sq,20);
    // SequenceList_Del(&sq,15);
    // SequenceList_Del(&sq,100);
    // SequenceList_Del(&sq,40);
    SequenceList_print(sq,show);
    return 0;
}

#include "sequencelist.h"


/*
 * 功能：检查顺序表是否已满
 * 参数：sq - 顺序表指针
 * 返回：true(满) / false(未满)
 */
bool Check_IsFull(SqList_t *sq)
{
    return (sq->Last + 1 == sq->Size) ? true:false;
}

/*
 * 功能：检查顺序表是否为空
 * 参数：sq - 顺序表指针
 * 返回：true(空) / false(非空)
 */
bool Check_IsEmpty(SqList_t *sq)
{
    return (sq->Last == -1) ? true:false;
}

/*
 * 功能：创建顺序表，在堆上分配 SqList_t 和内部数组 Addr
 * 参数：size - 顺序表容量
 * 返回：创建好的顺序表指针
 */
SqList_t * SequenceList_Create(DataType_t size)
{
    SqList_t *sq = (SqList_t *)calloc(1,sizeof(SqList_t));
    if(sq == NULL)
    {
        perror("calloc SqList_t is failed\n");
        exit(-1);
    }

    sq->Addr = (DataType_t *)calloc(size,sizeof(DataType_t));
    if(sq->Addr == NULL)
    {
        perror("calloc sq->Addr is failed\n");
        exit(-1);
    }

    sq->Size = size;
    sq->Last = -1;
    return sq;
}

/*
 * 功能：在顺序表尾部插入元素
 * 参数：sq   - 顺序表指针
 *       data - 要插入的数据
 * 返回：true(成功) / false(失败，表已满)
 */
bool SequenceList_TailAdd(SqList_t *sq,DataType_t data)
{
    if(Check_IsFull(sq))
    {
        printf("sqlist is full\n");
        return false;
    }
        
    
    sq->Addr[++sq->Last] = data;
    return true;
}

/*
 * 功能：在顺序表头部插入元素，所有已有元素后移一位
 * 参数：sq   - 顺序表指针
 *       data - 要插入的数据
 * 返回：true(成功) / false(失败，表已满)
 */
bool SequenceList_HeadAdd(SqList_t *sq,DataType_t data)
{
    if(Check_IsFull(sq))
    {
        printf("sqlist is full\n");
        return false;
    }
        
    
    for(int i=sq->Last; i >= 0; i--)
    {
        sq->Addr[i+1] = sq->Addr[i];
    }

    sq->Addr[0] = data;
    sq->Last++;
    return true;
}

/*
 * 功能：删除顺序表中第一个值为 data 的元素；表空时释放所有堆内存，将外部指针置为 NULL
 * 参数：sq   - 二级指针，可修改调用者的顺序表指针
 *       data - 要删除的数据值
 * 返回：true(成功) / false(失败，未找到或表空)
 */
bool SequenceList_Del(SqList_t **sq,DataType_t data)
{

    int temp = -1;

    if(Check_IsEmpty(*sq))
    {
        printf("sqlist is empty\n");
        return false;
    }

    for(int i = 0;i <= (*sq)->Last;i ++)
    {
        if((*sq)->Addr[i] == data)
        {

            temp = i;
            break;
        }
    }

    for(int i = temp;i < (*sq)->Last;i ++)
    {
        (*sq)->Addr[i] = (*sq)->Addr[i+1];
    }

    (*sq)->Last--;

    if((*sq)->Last == -1)
    {
        free((*sq)->Addr);
        (*sq)->Addr = NULL;
        free(*sq);
        *sq = NULL;
    }
    return true;

}

/*
 * 功能：遍历打印顺序表，通过回调函数 show 自定义输出格式
 * 参数：sq   - 顺序表指针
 *       show - 打印回调函数指针
 * 返回：无
 */
void SequenceList_print(SqList_t *sq,void (*show)(SqList_t *sq))
{
    show(sq);
}


/*
 * 功能：按递增顺序插入元素，找到第一个比 data 大的位置插入，保证表内数据升序
 * 参数：sq   - 顺序表指针
 *       data - 要插入的数据
 * 返回：true(成功) / false(失败，指针为空)
 */
// bool SequenceList_Add_incre(SqList_t *sq,DataType_t data)
// {
//     int temp = -1;

//     if(sq == NULL||sq->Addr == NULL)
//         return false;
//     for(int i = 0; i <= sq->Last; i++)
//     {
//         if((sq->Addr[i])>data)
//         {
//             temp = i;
//             break;
//         }
//     }

//     if(temp == -1)
//     {
//         sq->Addr[++sq->Last] = data;
//         return true;
//     }

//     for(int i = sq->Last; i >= temp; i--)
//     {
//         sq->Addr[i+1] = sq->Addr[i];
//     }
//     sq->Addr[temp] = data;
//     sq->Last++;
//     return true;
// }

#ifndef __SEQUENCELIST_H__
#define __SEQUENCELIST_H__

#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "stdbool.h"

typedef int DataType_t;

typedef struct
{
    DataType_t *Addr;
    int Size;
    int Last;
}SqList_t;


bool Check_IsFull(SqList_t *sq);
bool Check_IsEmpty(SqList_t *sq);
SqList_t * SequenceList_Create(DataType_t size);
bool SequenceList_TailAdd(SqList_t *sq,DataType_t data);
bool SequenceList_HeadAdd(SqList_t *sq,DataType_t data);
bool SequenceList_Del(SqList_t **sq,DataType_t data);
void SequenceList_print(SqList_t *sq,void (*show)(SqList_t *sq));
// bool SequenceList_Add_incre(SqList_t *sq,DataType_t data);

#endif

肯定有很多人有疑问为什么我要在bool SequenceList_Del(SqList_t **sq,DataType_t data)这个函数中使用二级指针的原因。

首先说一下关于二级指针的常用用法。在C++中，函数参数传递采用值传递的方式。当我们将一级指针作为参数传递给函数时，实际上传递给函数的是指针变量中存储的地址值的一个副本。因此，在函数内部操作的是这个指针副本，而无法直接修改原始指针变量本身。如果试图在函数内部改变副本指针的指向，使其指向另一个内存地址，这种修改仅对函数内部的副本有效，不会影响函数外部的原始指针。函数调用结束后，原始指针的指向仍然保持不变。

基于这一特性，若要实现在函数内部修改指针本身的指向（而不仅仅是指针所指向的内存内容），就必须传递一级指针的地址，即使用二级指针作为参数。如此一来，函数便可以通过二级指针间接地修改原始一级指针的指向。这正是一级指针无法替代二级指针的核心原因之一。

同理，在某些动态内存管理函数中，例如需要重新分配内存并返回新内存块地址时，如果希望函数能够更新调用者传入的指针，使其指向新分配的内存地址，就需要接收二级指针作为参数。这样，函数内部可以根据内存分配的结果，通过二级指针修改原始指针的指向，确保调用者能够获得正确的新内存地址。

假设我使用的是一级指针。

bool SequenceList_Del(SqList_t *sq,DataType_t data)
{

    int temp = -1;

    if(Check_IsEmpty(sq))
    {
        printf("sqlist is empty\n");
        return false;
    }

    for(int i = 0;i <= sq->Last;i ++)
    {
        if(sq->Addr[i] == data)
        {

            temp = i;
            break;
        }
    }

    for(int i = temp;i < sq->Last;i ++)
    {
        sq->Addr[i] = sq->Addr[i+1];
    }

    sq->Last--;

    if(sq->Last == -1)
    {
        free(sq->Addr);
        sq->Addr = NULL;
        free(sq);
        sq = NULL;
    }
    return true;

}

在mian函数中SqList_t *sq = SequenceList_Create(10);在堆上创建了一个结构体，则返回来了一个堆地址，假设堆地址为0x1000，因为这个函数SequenceList_Del(sq,data)使用的是一级指针，那么就会把main中的sq的堆地址复制一份给这个函数，因此在这个函数中就是使用的副本sq即在栈上，那么sq=NULL只是在这个函数内变为了NULL，main函数中的sq还是没有变。在SequenceList_Del这个函数中除了sq = NULL以外都没有任何问题，因为只有sq = NULL这个代码在修改sq指针本身。将sq变为NULL的目的是在打印的时候需要判断sq这个顺序表的是否存在。

那为什么可以使用二级指针来操作呢？在使用二级指针时，SequenceList_Del(&sq,data)函数传递的是main函数中sq在栈上的地址，假设栈上地址为0x2000，那么在SequenceList_Del这个函数中通过(*sq)这种方式去找sq本身即main函数中的sq本身，也就是通过地址0x2000，找到那个位置，读写它。(*sq)就是0x1000这个堆地址。(*sq)=NULL就可以将mian中的sq赋值为NULL。