目录
实验一 线性表的基本操作
一、实验目的
二、实验内容
三、实验提示
四、实验要求
五、实验代码如下：
（一）顺序表的构建及初始化
（二）检查顺序表是否需要扩容
（三）根据指定学生个数，逐个输入学生信息
（四）逐个显示学生表中所有学生的相关信息
（五）根据姓名进行查找，返回此学生的学号和成绩
（六）根据指定的位置可返回相应的学生信息（学号，姓名，成绩）；
（七） 给定一个学生信息，插入到表中指定的位置
检查插入位置的有效性
检查并扩容
将插入位置及之后的元素后移
在指定位置插入新元素
更新顺序表长度
（八）删除指定位置的学生记录
（九）main函数
六、整体代码如下：
实验一 线性表的基本操作
一、实验目的
1、掌握线性表的定义；
2、掌握线性表的基本操作，如建立、查找、插入和删除等。
二、实验内容
定义一个包含学生信息（学号，姓名，成绩）的顺序表和链表，使其具有如下功能：
(1) 根据指定学生个数，逐个输入学生信息；
(2) 逐个显示学生表中所有学生的相关信息；
(3) 根据姓名进行查找，返回此学生的学号和成绩；
(4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）；
(5) 给定一个学生信息，插入到表中指定的位置；
(6) 删除指定位置的学生记录；
(7) 统计表中学生个数。
三、实验提示
学生信息的定义：
typedef struct {
char no[8]; //8位学号
char name[20]; //姓名
int grade; //成绩
}Student;
顺序表的定义
typedef struct {
Student *elem; //指向数据元素的基地址
int length; //线性表的当前长度
}SqList；
链表的定义：
typedef struct LNode{
Student data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
四、实验要求
(1) 程序要添加适当的注释，程序的书写要采用缩进格式。
(2) 程序要具有一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。
(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。
(4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。
五、实验代码如下：
（一）顺序表的构建及初始化
-
动态内存分配：使用
malloc函数为elem分配内存空间，空间大小为MAX_SIZE乘以sizeof(Student)，即足够存储MAX_SIZE个Student类型的数据。MAX_SIZE是一个宏定义，表示顺序表的初始容量。 -
内存分配失败检查：如果
malloc返回NULL，表示内存分配失败。此时，程序打印错误信息并通过exit(1)退出。 -
初始化顺序表属性：将
length设置为0，表示顺序表当前没有任何元素。将capacity设置为MAX_SIZE，表示顺序表的当前容量为MAX_SIZE个元素。 -
内存清零：使用
memset函数将新分配的内存区域全部清零。这是一种预防措施，确保所有的Student记录从一开始就处于一个定义良好的状态（即所有位都是0），避免了使用未初始化的内存。
typedef struct {
char no[8]; // 8位学号
char name[20]; // 姓名
double grade; // 成绩
}Student;
// 顺序表的定义
typedef struct SqList
{
Student* elem; // 指向数据元素的基地址
int length; // 线性表的当前长度
int capacity; // 线性表的容量
}SL;
typedef Student ElemType;
void SeqListInit(SL* ps)
{
// 动态分配一个固定大小的数组用于存储学生信息
ps->elem = (Student*)malloc(MAX_SIZE * sizeof(Student));
if (!ps->elem) {
// 如果内存分配失败，打印错误信息并退出程序
printf("建立顺序表失败\n");
exit(1);
}
ps->length = 0; // 初始化顺序表当前长度为0
ps->capacity = MAX_SIZE; // 设置顺序表的容量为MAX_SIZE
memset(ps->elem, 0, sizeof(Student) * MAX_SIZE); // 将分配的内存区域清零
}（二）检查顺序表是否需要扩容
-
检查是否需要扩容：首先，函数检查顺序表
ps的当前长度（ps->length）是否等于其容量（ps->capacity）。等于容量意味着顺序表已满，没有多余的空间来存储新的元素，因此需要扩容。 -
计算新容量：如果顺序表需要扩容，函数计算新的容量
newcapacity。新容量被设置为当前容量的两倍，这是一种常见的扩容策略，旨在平衡扩容操作的次数和每次扩容增加的空间。特殊情况是，如果当前容量为0（意味着顺序表尚未初始化或特殊设计），则初始化为4。 -
重新分配内存：通过
realloc函数尝试重新分配内存。realloc不仅能够扩展或缩减已分配的内存块大小，还会保留原内存块的内容（在新内存块中复制原有数据），这对于顺序表的扩容操作是非常必要的。新内存的大小是newcapacity * sizeof(ElemType)，ElemType是顺序表存储元素的类型，这里是Student结构体。 -
检查内存分配结果：如果
realloc返回NULL，意味着内存分配失败，函数会打印错误信息并退出程序。。 -
更新顺序表属性：如果内存分配成功，
realloc会返回新分配内存的地址，函数会将这个新地址赋给ps->elem，以此更新顺序表的基地址。同时，更新顺序表的容量为newcapacity。
void SeqListCheckCapacity(SL* ps)
{
// 如果当前长度达到容量限制，则需要扩容
if (ps->length == ps->capacity) {
// 新容量是当前容量的两倍，特殊情况下从0开始则初始化为4
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
// 尝试重新分配内存
ElemType* tmp = (ElemType*)realloc(ps->elem, newcapacity * sizeof(ElemType));
if (tmp == NULL) {
// 如果内存分配失败，打印错误信息并退出程序
perror("realloc fail!");
exit(1);
}
ps->elem = tmp; // 更新顺序表的元素指针
ps->capacity = newcapacity; // 更新顺序表的容量
}
}（三）根据指定学生个数，逐个输入学生信息
void Input(ElemType* e)
{
提示用户输入一个学生的学号、姓名和成绩
//printf("请输入要读入的学生信息(包括学号, 姓名, 成绩):");
//scanf("%s %s %lf", e->no, e->name, &e->grade);
printf("学号:"); scanf("%s", e->no);
printf("姓名:"); scanf("%s", e->name);
printf("成绩:"); scanf("%lf", &e->price);
printf("输入完成\n\n");
}
// 根据指定学生个数，逐个输入学生信息
printf("请输入要输入的学生个数:\n"); scanf("%d", &n);
while (n--)
{
if (ps->length >= ps->capacity)
{
SeqListCheckCapacity(ps);
}
ps->length++;
printf("请输入第 %d 个学生:\n", ps->length);
Input(&ps->elem[ps->length]);
}（四）逐个显示学生表中所有学生的相关信息
void Output(ElemType* e)
{
// 格式化输出学生的学号、姓名和成绩
printf(" 学号:%-10s\n 姓名:%-20s\n 成绩:%-10.2f\n\n", e->no, e->name, e->grade);
}
// 显示学生表信息
for (i = 1; i <= ps->length; i++) {
Output(&ps->elem[i]);
}
break;（五）根据姓名进行查找，返回此学生的学号和成绩
int Search(SqList* ps, char str[])
{
// 遍历顺序表中的每个元素，查找姓名匹配的学生
int i = 1; // 注意这里的索引从1开始，为了用户友好
for (; i <= ps->length; i++)
{
if (strcmp(ps->elem[i].name, str) == 0)
return i; // 如果找到，返回学生的位置
}
return 0;
}
printf("请输入要查找的学生姓名:");
scanf("%s", str);
//根据姓名进行查找，返回此学生的学号和成绩；
if (t = Search(ps, str))
Output(&ps->elem[Search(ps, str)]);
else
printf("没有此学生信息！\n");
*str = NULL;（六）根据指定的位置可返回相应的学生信息（学号，姓名，成绩）；
void Output(ElemType* e)
{
// 格式化输出学生的学号、姓名和成绩
printf(" 学号:%-10s\n 姓名:%-20s\n 成绩:%-10.2f\n\n", e->no, e->name, e->grade);
}
printf("请输入显示的位置:\n");
scanf("%d", &id1);
Output(&ps->elem[id1]);（七） 给定一个学生信息，插入到表中指定的位置
检查插入位置的有效性
- 函数首先检查提供的位置
i是否在合法范围内。有效的插入位置从1开始，到ps->length + 1结束（含）。 - 如果
i小于1或大于ps->length + 1，函数返回false，表示插入操作失败。
检查并扩容
- 如果顺序表的当前长度加
1大于等于其容量（ps->length + 1 >= ps->capacity），意味着顺序表没有足够的空间来容纳新元素，因此需要扩容。 SeqListCheckCapacity函数被调用来处理可能的扩容。如果需要，这个函数会增加顺序表的容量，保证有足够的空间插入新元素。
将插入位置及之后的元素后移
- 为了在指定位置
i插入新元素，从该位置开始到顺序表末尾的所有元素都需要向后移动一位。这通过一个从ps->length开始，向下到i的逆序循环完成。循环中的每一步都将元素从j位置移动到j + 1位置。 - 这个过程为新元素腾出了位置
i。
在指定位置插入新元素
- 新元素通过解引用
e指针（*e）获得，并被插入到顺序表的位置i。由于函数用户友好性考虑，位置i是从1开始计数的。
更新顺序表长度
- 成功插入新元素后，顺序表的长度
ps->length增加1，以反映新元素的添加。
返回值
- 函数最后返回
true，表示插入操作成功执行。
bool ListInsert(SqList* ps, int i, ElemType* e)
{
// 检查插入位置的有效性
if ((i < 1) || (i > ps->length + 1)) return false;
// 检查并扩容
if (1 + ps->length >= ps->capacity)
{
SeqListCheckCapacity(ps);
}
// 将插入位置及之后的元素后移
for (int j = ps->length; j >= i; j--)
{
ps->elem[j + 1] = ps->elem[j];
}
// 在指定位置插入新元素
ps->elem[i] = *e;
ps->length++; // 更新顺序表长度
return true;
}
//给定一个学生信息，插入到表中指定的位置；
printf("请输入要插入的位置:");
scanf("%d", &id2);
printf("输入要插入的人数:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
printf("请输入第 %d 个学生:\n", i);
Input(&a);
if (ListInsert(ps, id2, &a))
{
puts("插入成功");
}
else
{
puts("插入失败\n");
}
}（八）删除指定位置的学生记录
- 在执行删除操作之前，函数首先检查提供的索引
i是否有效。索引有效的条件是它必须在1和顺序表当前长度ps->length之间（包含这两个值） - 如果
i无效（即小于1或大于ps->length），函数立即返回false，表示删除操作失败。
- 如果索引
i有效，函数通过将从位置i+1开始的所有元素向前移动一位来删除位于位置i的元素。这通过一个for循环实现，循环的迭代变量j从i开始，直到ps->length（包含）。 - 循环内部的操作
ps->elem[j] = ps->elem[j + 1];将每个后续元素复制到其前一个位置上，实际上是将位置i上的元素“覆盖”，从而实现删除效果。
bool ListDelete(SqList* ps, int i)
{
// 首先检查给定的索引i是否有效。
if ((i < 1) || (i > ps->length))return false;
for (int j = i; j <= ps->length; j++)
{
ps->elem[j] = ps->elem[j + 1];
}
--ps->length;
return true;
}
//删除指定位置的学生记录；
printf("请输入要删除的位置:");
int id3;
scanf("%d", &id3);
if (ListDelete(ps, id3))
{
puts("删除成功");
}
else
{
puts("删除失败");
}（九）main函数
int main()
{
SL* ps = (SL*)malloc(sizeof(SL));
ElemType a;
printf("\n1.构造顺序表\n");
printf("2.输入学生信息\n");
printf("3.显示学生表信息\n");
printf("4.根据姓名进行查找\n");
printf("5.显示指定的位置学生信息\n");
printf("6.在指定位置插入学生信息\n");
printf("7.删除指定位置的学生记录\n");
printf("8.统计学生人数\n");
printf("9.退出\n\n");
int choose, n = 0; char str[20]; int id1, t = 0, id2 = 0, i = 1;
while (1) {
printf("请选择：");
scanf("%d", &choose);
if (choose == 9) break;
switch (choose) {
......
}
}
return 0;
}六、整体代码如下：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_SIZE 10
#define Case break;case
typedef struct {
char no[8]; // 8位学号
char name[20]; // 姓名
double grade; // 成绩
}Student;
// 顺序表的定义
typedef struct SqList
{
Student* elem; // 指向数据元素的基地址
int length; // 线性表的当前长度
int capacity; // 线性表的容量
}SL;
typedef Student ElemType;
void SeqListInit(SL* ps)
{
// 动态分配一个固定大小的数组用于存储学生信息
ps->elem = (Student*)malloc(MAX_SIZE * sizeof(Student));
if (!ps->elem) {
// 如果内存分配失败，打印错误信息并退出程序
printf("建立顺序表失败\n");
exit(1);
}
ps->length = 0; // 初始化顺序表当前长度为0
ps->capacity = MAX_SIZE; // 设置顺序表的容量为MAX_SIZE
memset(ps->elem, 0, sizeof(Student) * MAX_SIZE); // 将分配的内存区域清零
}
void SeqListCheckCapacity(SL* ps)
{
// 如果当前长度达到容量限制，则需要扩容
if (ps->length == ps->capacity) {
// 新容量是当前容量的两倍，特殊情况下从0开始则初始化为4
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
// 尝试重新分配内存
ElemType* tmp = (ElemType*)realloc(ps->elem, newcapacity * sizeof(ElemType));
if (tmp == NULL) {
// 如果内存分配失败，打印错误信息并退出程序
perror("realloc fail!");
exit(1);
}
ps->elem = tmp; // 更新顺序表的元素指针
ps->capacity = newcapacity; // 更新顺序表的容量
}
}
void Input(ElemType* e)
{
void Input(ElemType* e)
{
提示用户输入一个学生的学号、姓名和成绩
//printf("请输入要读入的学生信息(包括学号, 姓名, 成绩):");
//scanf("%s %s %lf", e->no, e->name, &e->grade);
printf("学号:"); scanf("%s", e->no);
printf("姓名:"); scanf("%s", e->name);
printf("成绩:"); scanf("%lf", &e->price);
printf("输入完成\n\n");
}
}
void Output(ElemType* e)
{
// 格式化输出学生的学号、姓名和成绩
printf(" 学号:%-10s\n 姓名:%-20s\n 成绩:%-10.2f\n\n", e->no, e->name, e->grade);
}
int Search(SqList* ps, char str[])
{
// 遍历顺序表中的每个元素，查找姓名匹配的学生
int i = 1; // 注意这里的索引从1开始，为了用户友好
for (; i <= ps->length; i++)
{
if (strcmp(ps->elem[i].name, str) == 0)
return i; // 如果找到，返回学生的位置
}
return 0;
}
bool ListInsert(SqList* ps, int i, ElemType* e)
{
// 检查插入位置的有效性
if ((i < 1) || (i > ps->length + 1)) return false;
// 检查并扩容
if (1 + ps->length >= ps->capacity)
{
SeqListCheckCapacity(ps);
}
// 将插入位置及之后的元素后移
for (int j = ps->length; j >= i; j--)
{
ps->elem[j + 1] = ps->elem[j];
}
// 在指定位置插入新元素
ps->elem[i] = *e;
ps->length++; // 更新顺序表长度
return true;
}
bool ListDelete(SqList* ps, int i)
{
// 首先检查给定的索引i是否有效。
if ((i < 1) || (i > ps->length))return false;
// 将删除位置之后的元素前移
for (int j = i; j <= ps->length; j++)
{
ps->elem[j] = ps->elem[j + 1];
}
--ps->length;// 更新顺序表长度
return true;
}
int main()
{
SL* ps = (SL*)malloc(sizeof(SL));
ElemType a;
printf("\n1.构造顺序表\n");
printf("2.输入学生信息\n");
printf("3.显示学生表信息\n");
printf("4.根据姓名进行查找\n");
printf("5.显示指定的位置学生信息\n");
printf("6.在指定位置插入学生信息\n");
printf("7.删除指定位置的学生记录\n");
printf("8.统计学生人数\n");
printf("9.退出\n\n");
int choose, n = 0; char str[20]; int id1, t = 0, id2 = 0, i = 1;
while (1) {
printf("请选择：");
scanf("%d", &choose);
if (choose == 9) break;
switch (choose) {
case 1:// 初始化顺序表
SeqListInit(ps);
Case 2:
// 根据指定学生个数，逐个输入学生信息
printf("请输入要输入的学生个数:\n"); scanf("%d", &n);
while (n--)
{
if (ps->length >= ps->capacity)
{
SeqListCheckCapacity(ps);
}
ps->length++;
printf("请输入第 %d 个学生:\n", ps->length);
Input(&ps->elem[ps->length]);
}
Case 3:
// 显示学生表信息
for (i = 1; i <= ps->length; i++) {
Output(&ps->elem[i]);
}
break;
Case 4:
printf("请输入要查找的学生姓名:");
scanf("%s", str);
//根据姓名进行查找，返回此学生的学号和成绩；
if (t = Search(ps, str))
Output(&ps->elem[Search(ps, str)]);
else
printf("没有此学生信息！\n");
*str = NULL;
Case 5:
//根据指定的位置可返回相应的学生信息（学号，姓名，成绩）；
printf("请输入显示的位置:\n");
scanf("%d", &id1);
Output(&ps->elem[id1]);
Case 6:
//给定一个学生信息，插入到表中指定的位置；
printf("请输入要插入的位置:");
scanf("%d", &id2);
printf("输入要插入的人数:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
printf("请输入第 %d 个学生:\n", i);
Input(&a);
if (ListInsert(ps, id2, &a))
{
puts("插入成功");
}
else
{
puts("插入失败\n");
}
}
Case 7:
//删除指定位置的学生记录；
printf("请输入要删除的位置:");
int id3;
scanf("%d", &id3);
if (ListDelete(ps, id3))
{
puts("删除成功");
}
else
{
puts("删除失败");
}
Case 8:
//统计表中学生个数。
printf("表中学生个数有%d人\n", ps->length);
break;
default:
printf("无效选项\n");
break;
}
}
return 0;
}
运行截图：
今天就先到这了！！！
看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！
你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。
![HCIP[GRE和MGRE]](https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=file%3A%2F%2F%2FC%3A%5CUsers%5C%E9%AB%98%E6%97%AD%E8%81%AA%5CAppData%5CLocal%5CTemp%5Cksohtml15804%5Cwps15.jpg&pos_id=Ww0belcA)
