昨天我发布了关于数据结构线性表的学习知识（【数据结构】顺序表-CSDN博客）。所谓“纸上得来终觉浅”，光看不练可不行，下面我们来看一下顺序表的习题。

 题目链接

【深基15.例1】询问学号 - 洛谷

题目解读

        题目描述了一个场景，有 <code>n 名同学陆续进入教室，我们知道他们的学号，学号在 1 到 10^9 之间。按同学进入教室的顺序给出学号。

我们需要完成以下几个主要任务：

定义一个结构体 SeqList 来表示存储学号的顺序表，其中包含学号数组 number 、最大容量 capacity 和有效数字个数 size 。编写 init 函数来初始化顺序表。编写 checkcapacity 函数来检查顺序表的容量，如果容量不足则进行扩容。编写 insert 函数向顺序表中插入（尾插）学号。

听起来不难，那么下面开始写代码。

代码详解

    1.定义SeqList结构体

        结构体的定义和初始化都不难，咱们不过多解释，有问题可以在评论区讨论。

typedef struct SeqList

{

int* number;//学号

int capacity;//最大容量

int size;//有效数字个数

}SL;

   2.初始化函数

void init(SL* p)

{

p->number=NULL;

p->capacity=0;

p->size=0;

}

    3.检测容量足够与否并扩容

        整体来说不难理解，看一下注释应该不成问题。唯一的难点可能是有些同学不懂realloc的用法，博主将它的用法放在了疑难解答，大家可以自行学习。

/**

* 检查并调整顺序表的容量

* p 指向顺序表结构体的指针

*/

void checkcapacity(SL* p)

{

// 如果指针为空，输出错误信息并退出程序

if(p == NULL)

{

cout << "未检查到指针所指向数据" << endl;

exit(1);

}

// 如果当前容量等于元素个数

if(p->capacity == p->size)

{

// 计算新的容量，如果当前容量为 0，则新容量为 4，否则新容量为当前容量的 2 倍

int newcapacity = p->capacity == 0? p->capacity = 4 : 2 * p->capacity;

// 重新分配内存空间

int* ps = (int*)realloc(p->number, newcapacity * sizeof(int));

// 如果重新分配内存失败

if(ps == NULL)

{

perror("realloc fail");

exit(1);

}

// 更新顺序表的指针和容量

p->number = ps;

p->capacity = newcapacity;

}

}

    4.尾插函数

参数含义：

p：是指向顺序表结构体的指针，用来操作顺序表的相关数据。x：要添加到顺序表末尾的数据。

/**

* 向顺序表中插入一个元素

* p 指向顺序表结构体的指针

* x 要插入的元素值

*/

void insert(SL* p, int x)

{

// 如果指针为空，输出错误信息并退出程序

if(p == NULL)

{

cout << "初始化失败" << endl;

exit(1);

}

// 检查并调整顺序表的容量

checkcapacity(p);

// 将元素插入到顺序表中，并增加元素个数

p->number[p->size++] = x;

}

 完整代码

#include<bits/stdc++.h>

#include<assert.h>

using namespace std;

typedef struct SeqList

{

int* number;//学号

int capacity;//最大容量

int size;//有效数字个数

}SL;

void init(SL* p)

{

p->number=NULL;

p->capacity=0;

p->size=0;

}

void checkcapacity(SL* p)

{

if(p==NULL)

{

cout<<"未检查到指针所指向数据"<<endl;

exit(1);

}

if(p->capacity==p->size)

{

int newcapacity=p->capacity==0?p->capacity=4:2*p->capacity;

int* ps=(int*)realloc(p->number,newcapacity*sizeof(int));

if(ps==NULL)

{

perror("realloc fail");

exit(1);

}

p->number=ps;

p->capacity=newcapacity;

}

}

void insert(SL* p,int x)

{

if(p==NULL)

{

cout<<"初始化失败"<<endl;

exit(1);

}

checkcapacity(p);

p->number[p->size++]=x;

}

main()

{

SL s;

init(&s);

int n;

int m;

cin>>n>>m;

for(int i=0;i<n;i++)

{

int x;

cin>>x;

insert(&s,x);

}

for(int i=0;i<m;i++)

{

int x;

cin>>x;

cout<<s.number[x-1]<<endl;

}

}

    AC 

 疑难解答

     realloc的用法

realloc 函数用于重新分配内存块的大小。

函数原型：void *realloc(void *ptr, size_t size);

参数含义：

ptr：指向之前通过 malloc、calloc 或 realloc 分配的内存块的指针。size：新的所需内存大小。

用法及作用：

如果 ptr 为 NULL，则 realloc 的功能类似于 malloc，分配指定大小的内存。如果 size 为 0 且 ptr 不为 NULL，则相当于释放 ptr 指向的内存，类似于 free 函数。否则，realloc 尝试改变之前分配的内存块的大小。如果有足够的连续空间可扩展现有内存块，会在原地进行扩展并返回原指针。如果没有足够的连续空间，会分配新的内存块，将原有数据复制到新位置，并释放旧的内存块，然后返回新的指针。

例如：

<code>#include <stdio.h>

#include <stdlib.h>

int main()

{

int *ptr = (int *)malloc(sizeof(int) * 5); // 分配 5 个整数的内存

// 填充一些数据

for (int i = 0; i < 5; i++)

{

ptr[i] = i;

}

int *newPtr = (int *)realloc(ptr, sizeof(int) * 10); // 重新分配为 10 个整数的内存

if (newPtr!= NULL)

{

ptr = newPtr; // 更新指针

// 继续使用扩展后的内存

for (int i = 5; i < 10; i++)

{

ptr[i] = i;

}

// 输出数据

for (int i = 0; i < 10; i++)

{

printf("%d ", ptr[i]);

}

printf("\n");

free(ptr); // 释放内存

}

else

{

printf("Reallocation failed!\n");//创建失败提示信息

}

return 0;

}