登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 业界 ›线性表-顺序存储

线性表-顺序存储

仟仞 昨天 19:22
顺序表的实现与测试-C语言版

一、顺序表概念

顺序表（Sequential List）是线性表的一种存储方式，指的是采用顺序存储结构的线性表。在顺序表中，数据元素按照它们的逻辑顺序依次存放在一段地址连续的存储单元中。这种存储方式允许通过数学计算快速定位到任何一个元素的位置，从而支持随机访问。但是，顺序表的插入和删除操作可能需要移动大量元素以保持数据元素的连续存放。
总结特点如下：

  • 元素在内存中连续存储
  • 可以通过下标快速访问元素（时间复杂度 O (1)）
  • 插入和删除元素可能需要移动大量元素（时间复杂度 O (n)）
1.png

二、顺序表实现代码

顺序表的关键参数

为了管理顺序表，需要记录三个参数：

  • 存储元素的数组地址（Primary_Addr）
  • 顺序表的最大容量（Size）
  • 最后一个元素的下标（Last，初始值为 - 1 表示空表）
我们用结构体封装这些参数：
  1. // 定义元素类型（方便后续修改为其他类型，如float）
  2. typedef int DataType_t;
  4. // 顺序表管理结构体
  5. typedef struct SequenceList
  6. {
  7.     DataType_t *Primary_Addr; // 元素存储地址
  8.     unsigned int Size;        // 最大容量
  9.     int          Last;        // 最后一个元素下标
  10. } SequenceList_t;
复制代码
初始化函数

初始化是使用顺序表的第一步，作用是申请内存并初始化参数：
  1. // 初始化顺序表，参数为容量大小
  2. SequenceList_t* SequenceList_init(unsigned int size)
  3. {
  4.     // 1. 申请管理结构体的内存
  5.     SequenceList_t *SeqList_manager = (SequenceList_t *)calloc(1,sizeof(SequenceList_t));
  6.     if(SeqList_manager == NULL){
  7.         perror("申请管理结构体失败！");
  8.         exit(-1);
  9.     }
  11.     // 2. 申请存储元素的数组内存
  12.     SeqList_manager->Primary_Addr = (DataType_t *)calloc(size,sizeof(DataType_t));
  13.     if(SeqList_manager->Primary_Addr == NULL){
  14.         perror("申请元素数组失败！");
  15.         free(SeqList_manager); // 先释放已申请的结构体
  16.         exit(-1);
  17.     }
  19.     // 3. 初始化参数
  20.     SeqList_manager->Size = size;
  21.     SeqList_manager->Last = -1; // 空表标记
  23.     return SeqList_manager;
  24. }
复制代码
状态判断函数

插入 / 删除前需要先判断表是否满 / 空：
  1. // 判断顺序表是否已满
  2. bool SeqListIsfull(SequenceList_t *SeqList_manager)
  3. {
  4.     // 最后一个元素下标+1 等于 容量时，表满
  5.     return (SeqList_manager->Last +1 == SeqList_manager->Size)?true:false;
  6. }
  8. // 判断顺序表是否为空
  9. bool SeqListIsEmpty(SequenceList_t *SeqList_manager)
  10. {
  11.     // 最后一个元素下标为-1时，表空
  12.     return (SeqList_manager->Last == -1)?true:false;
  13. }
复制代码
插入功能

1. 尾部插入

尾部插入最简单，直接在最后一个元素后添加：
  1. // 尾部添加元素
  2. bool SeqList_TailAdd(SequenceList_t *SeqList_manager,DataType_t data)
  3. {   
  4.     // 先判断是否已满
  5.     if(SeqListIsfull(SeqList_manager)){
  6.         printf("顺序表已满，无法添加！\n");
  7.         return false;
  8.     }
  10.     // Last先+1，再赋值（空表时Last从-1变为0）
  11.     SeqList_manager->Primary_Addr[++SeqList_manager->Last] = data;
  12.     return true;
  13. }
复制代码
2. 头部插入

头部插入需要先将所有元素后移一位，再在头部插入：
  1. // 头部添加元素
  2. bool SeqList_HeadAdd(SequenceList_t *SeqList_manager,DataType_t data)
  3. {
  4.     if(SeqListIsfull(SeqList_manager)){
  5.         printf("顺序表已满，无法添加！\n");
  6.         return false;
  7.     }
  9.     // 所有元素后移一位（从最后一个元素开始）
  10.     for(int i = SeqList_manager->Last;i >= 0;i--){
  11.         SeqList_manager->Primary_Addr[i+1] = SeqList_manager->Primary_Addr[i];
  12.     }
  14.     // 头部插入新元素
  15.     SeqList_manager->Primary_Addr[0] = data;
  16.     SeqList_manager->Last++; // 更新最后一个元素下标
  17.     return true;
  18. }
复制代码
3. 有序插入（考研题目）

原题目：已经知道一个顺序表，其中的元素递增有序排列，设计一个算法，插入一个元素x(x是int型)后保持该顺序表依然递增有序
  1. void SeqList_Insert(SequenceList_t *SeqList_manager,int x)
  2. {
  3.     // 先判断是否已满
  4.     if (SeqListIsfull(SeqList_manager)) {
  5.         printf("顺序表已满，无法插入！\n");
  6.         return;
  7.     }
  8.     // 1. 找到插入位置（第一个比x大的元素下标）
  9.     int Temp = -1; // 初始为-1，表示x是最大元素
  10.     for(int i = 0;i <= SeqList_manager->Last;i++ ){
  11.         if(SeqList_manager->Primary_Addr[i] >= x){
  12.             Temp = i;
  13.             break;
  14.         }
  15.     }
  16.     // 2. 如果x是最大元素，直接插在尾部
  17.     if(Temp == -1){
  18.         SeqList_manager->Primary_Addr[++SeqList_manager->Last] = x;
  19.         return ;
  20.     }
  21.     // 3. 否则，插入位置后的元素后移
  22.     for(int i= SeqList_manager->Last;i>= Temp;i--){
  23.         SeqList_manager->Primary_Addr[i+1] = SeqList_manager->Primary_Addr[i];
  24.     }
  25.     // 4. 插入元素并更新下标
  26.     SeqList_manager->Primary_Addr[Temp] = x;
  27.     SeqList_manager->Last++;
  28. }
复制代码
删除功能

1. 按值删除

删除第一个匹配的值，需要先查找位置，再前移元素：
  1. // 删除第一个值为DestVal的元素
  2. bool SeqList_Del(SequenceList_t *SeqList_manager,DataType_t DestVal)
  3. {
  4.     int Temp = -1; // 记录目标元素下标
  5.     // 先判断是否为空表
  6.     if(SeqListIsEmpty(SeqList_manager)){
  7.         printf("顺序表为空，无法删除！\n");
  8.         return false;
  9.     }
  10.     // 1. 查找目标元素
  11.     for(int i = 0;i <= SeqList_manager->Last;i++ ){
  12.         if(SeqList_manager->Primary_Addr[i] == DestVal){
  13.             Temp = i;
  14.             break;
  15.         }
  16.     }
  17.     // 2. 未找到元素
  18.     if(Temp == -1){
  19.         printf("未找到元素，删除失败！\n");
  20.         return false;
  21.     }
  22.     // 3. 目标元素后的元素前移一位
  23.     for(int i = Temp;i < SeqList_manager->Last;i++){
  24.         SeqList_manager->Primary_Addr[i] = SeqList_manager->Primary_Addr[i+1];
  25.     }
  26.     // 4. 更新最后一个元素下标
  27.     --SeqList_manager->Last;
  28.     return true;
  29. }
复制代码
2. 按位置删除（考研题目）

原题目：删除顺序表中下表为p(0≤p≤length-1)的元素，成功返回1，否则返回0 */
  1. int SeqList_Remove(SequenceList_t *SeqList_manager,int p)
  2. {
  3.     // 1. 判断是否为空表
  4.     if(SeqListIsEmpty(SeqList_manager)){
  5.         printf("顺序表为空，无法删除！\n");
  6.         return 0;
  7.     }
  9.     // 2. 判断下标是否合法（0 ≤ p ≤ Last）
  10.     if (p < 0 || p > SeqList_manager->Last) {
  11.         printf("下标不合法，删除失败！\n");
  12.         return 0;
  13.     }
  15.     // 3. 下标p后的元素前移一位
  16.     for(int i = p;i < SeqList_manager->Last;i++){
  17.         SeqList_manager->Primary_Addr[i] = SeqList_manager->Primary_Addr[i+1];
  18.     }
  20.     // 4. 更新最后一个元素下标
  21.     SeqList_manager->Last--;
  22.     return 1;
  23. }
复制代码
辅助功能

1. 遍历打印

打印所有元素，方便查看顺序表状态：
  1. // 打印所有元素
  2. void SeqList_Print(SequenceList_t *SeqList_manager)
  3. {
  4.     for(int i = 0;i <= SeqList_manager->Last;i++ ){
  5.         printf("%d\n",SeqList_manager->Primary_Addr[i]);
  6.     }
  7. }
复制代码
2. 内存释放

使用完顺序表后必须释放内存，避免内存泄漏：
  1. // 释放顺序表内存
  2. void SeqList_Destroy(SequenceList_t *SeqList_manager)
  3. {
  4.     if (SeqList_manager != NULL) {
  5.         free(SeqList_manager->Primary_Addr); // 先释放元素数组
  6.         free(SeqList_manager);               // 再释放管理结构体
  7.     }
  8. }
复制代码
三、完整测试代码
  1. int main(int argc, char const *argv[])
  2. {
  3.     // 1. 测试初始化
  4.     printf("===== 测试初始化 =====\n");
  5.     SequenceList_t *seqList = SequenceList_init(5); // 容量为5
  6.     if (seqList != NULL)
  7.     {
  8.         printf("初始化成功！容量：%u，元素个数：%d\n",
  9.                seqList->Size, seqList->Last + 1); // 空表个数为0
  10.     }
  12.     // 2. 测试尾部插入
  13.     printf("\n===== 测试尾部插入 =====\n");
  14.     SeqList_TailAdd(seqList, 10);
  15.     SeqList_TailAdd(seqList, 20);
  16.     SeqList_TailAdd(seqList, 30);
  17.     printf("插入10、20、30后元素：\n");
  18.     SeqList_Print(seqList); // 预期：10、20、30
  19.     printf("元素个数：%d（预期3）\n", seqList->Last + 1);
  21.     // 3. 测试头部插入
  22.     printf("\n===== 测试头部插入 =====\n");
  23.     SeqList_HeadAdd(seqList, 5); // 头部插入5
  24.     printf("插入5后元素：\n");
  25.     SeqList_Print(seqList); // 预期：5、10、20、30
  26.     printf("元素个数：%d（预期4）\n", seqList->Last + 1);
  28.     // 4. 测试有序插入
  29.     printf("\n===== 测试有序插入 =====\n");
  30.     SeqList_Insert(seqList, 15); // 插入15（应在10和20之间）
  31.     printf("插入15后元素：\n");
  32.     SeqList_Print(seqList); // 预期：5、10、15、20、30
  33.     printf("元素个数：%d（预期5）\n", seqList->Last + 1);
  35.     // 测试满表插入（容量5，已插入5个元素）
  36.     printf("\n尝试插入35（已满）：\n");
  37.     SeqList_Insert(seqList, 35); // 预期提示"已满"
  39.     // 5. 测试按值删除
  40.     printf("\n===== 测试按值删除 =====\n");
  41.     printf("删除15：\n");
  42.     bool delResult = SeqList_Del(seqList, 15);
  43.     if (delResult)
  44.     {
  45.         printf("删除成功，剩余元素：\n");
  46.         SeqList_Print(seqList); // 预期：5、10、20、30
  47.         printf("元素个数：%d（预期4）\n", seqList->Last + 1);
  48.     }
  50.     // 测试删除不存在的元素
  51.     printf("\n删除99（不存在）：\n");
  52.     SeqList_Del(seqList, 99); // 预期提示"未找到"
  54.     // 6. 测试按位置删除
  55.     printf("\n===== 测试按位置删除 =====\n");
  56.     printf("删除下标1的元素（值为10）：\n");
  57.     int removeResult = SeqList_Remove(seqList, 1);
  58.     if (removeResult == 1)
  59.     {
  60.         printf("删除成功，剩余元素：\n");
  61.         SeqList_Print(seqList); // 预期：5、20、30
  62.         printf("元素个数：%d（预期3）\n", seqList->Last + 1);
  63.     }
  65.     // 测试非法下标删除（当前最大下标为2）
  66.     printf("\n删除下标5（非法）：\n");
  67.     SeqList_Remove(seqList, 5); // 预期提示"不合法"
  69.     // 7. 测试边界情况
  70.     printf("\n===== 测试边界情况 =====\n");
  71.     SequenceList_t *emptyList = SequenceList_init(3); // 空表
  72.     printf("删除空表元素：\n");
  73.     SeqList_Del(emptyList, 10); // 预期提示"为空"
  74.     SeqList_Destroy(emptyList); // 及时释放
  76.     // 8. 释放内存
  77.     printf("\n===== 测试结束 =====\n");
  78.     SeqList_Destroy(seqList);
  79.     printf("内存释放完成！\n");
  80.     return 0;
  81. }
复制代码
测试结果

运行程序后，输出如下:
2.png

3.png


来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
仟仞
昨天 19:22

0

粉丝关注

13

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫