数据结构(Day16)
一、学习内容
1、有关顺序表的操作(功能函数)
1、创建顺序表
Plist create_list(){
Plist L = malloc(sizeof(list)); // 为顺序表分配内存空间
if(NULL == L){
printf("申请空间失败\n");
return NULL; // 如果内存分配失败,返回 NULL
}
L->len = 0; // 初始化表的长度为0
printf("创建成功\n");
return L; // 返回顺序表的指针
}
2、顺序表的判满
int full(Plist L){
if(L->len == MAX){ // 如果学生数量等于最大容量,返回1表示已满
return 1;
}
return 0;
}
3、顺序表的判空
int empty(Plist L){
if(L->len == 0){ // 如果表长为0,表示顺序表为空
return 1;
}
return 0;
}
4、顺序表增加数据
int input_list(Plist L){
int n;
printf("要输入学生的个数:\n");
scanf("%d",&n); // 输入学生数量
for(int i=0; i<n; i++){
printf("请输入第%d个学生信息:", i+1);
printf("请输入学号:");
scanf("%d",&L->data[i].id); // 输入学号
printf("请输入姓名:");
scanf("%s",L->data[i].name); // 输入姓名
printf("请输入专业:");
scanf("%s",L->data[i].major); // 输入专业
printf("请输入年龄:");
scanf("%d",&L->data[i].age); // 输入年龄
L->len++; // 学生数量增加
}
return 0;
}
5、顺序表的遍历
int output_list(Plist L){
for(int i=0; i<L->len; i++){
// 按格式输出每个学生的信息
printf("学号:%d\t姓名:%s\t专业:%s\t年龄:%d\n",L->data[i].id,L->data[i].name,L->data[i].major,L->data[i].age);
}
return 0;
}
6、顺序表任意位置插入数据
int insert_stu(Plist L, int pos, student e){
int sub = pos -1; // 转换为数组下标
if(sub<0 || sub>L->len || L==NULL || full(L)){ // 检查插入位置合法性和顺序表是否已满
printf("插入失败\n");
return -1;
}
for(int i=L->len-1; i>=sub; i--){ // 将元素后移,给插入新学生腾出位置
L->data[i+1] = L->data[i];
}
L->data[sub] = e; // 插入新学生信息
L->len++; // 学生数量增加
printf("插入成功\n");
return 0;
}
7、 顺序表任意位置删除操作
int delete_stu(Plist L, int pos){
int sub = pos - 1; // 转换为数组下标
if(sub < 0 || sub > L->len-1 || L == NULL || empty(L)){ // 检查删除位置合法性和是否为空表
printf("删除失败\n");
return -1;
}
for(int i=sub; i<L->len; i++){ // 将后面的元素前移,覆盖要删除的元素
L->data[i] = L->data[i+1];
}
L->len--; // 学生数量减少
printf("删除成功\n");
return 0;
}
8、按位置修改函数
int change_stu(Plist L, int pos, student e){
int sub = pos - 1; // 转换为数组下标
if(sub < 0 || sub > L->len-1 || L == NULL || empty(L)){ // 检查修改位置合法性和是否为空表
printf("查找失败\n");
return -1;
}else{
// 修改学生信息
L->data[sub] = e;
printf("修改成功\n");
return 0;
}
}
9、按值修改函数
int delete_stu(Plist L, int pos){
int sub = pos - 1; // 转换为数组下标
if(sub < 0 || sub > L->len-1 || L == NULL || empty(L)){ // 检查删除位置合法性和是否为空表
printf("删除失败\n");
return -1;
}
for(int i=sub; i<L->len; i++){ // 将后面的元素前移,覆盖要删除的元素
L->data[i] = L->data[i+1];
}
L->len--; // 学生数量减少
printf("删除成功\n");
return 0;
}
10、 按值查找返回位置
int find_stu_all(Plist L, char key[20]){
int i, sub = -1;
for(i=0; i<L->len; i++){
// 输出所有符合条件的学生信息
if(strcmp(L->data[i].name, key) == 0){
printf("位置:%d\t是%s\n",i+1,L->data[i].name);
sub = i;
}
}
if(sub == -1){
return -1; // 没有找到则返回 -1
}
return sub + 1;
}
11、查找指定位置上的元素
int find_stu(Plist L, char key[20]){
int i, sub = -1;
for(i=0; i<L->len; i++){
// 找到符合条件的学生
if(strcmp(L->data[i].name, key) == 0){
sub = i; // 记录找到的位置
}
}
if(sub == -1){
return -1; // 没有找到则返回 -1
}
return sub + 1; // 返回学生在表中的位置,位置从1开始计数
}
12、顺序表去重
nt delete_repeat(Plist L){
int i, j;
for(i=0; i<L->len; i++){
for(j=i+1; j<L->len; j++){
// 如果发现两个学生姓名相同,则删除后者
if(strcmp(L->data[i].name, L->data[j].name) == 0){
delete_stu(L, j+1); // 删除重复的学生信息
j--; // 调整索引,继续检查下一个
}
}
}
return 0;
}
二、作业
制作部分学生管理系统
实现的功能有:
1、输入学生信息
2、任意位置插入一个学生
3、任意位置删除一个学生
4、任意位置查找一个学生
5、任意位置修改一个学生
6、表头插入一个学生
7、表尾插入一个学生
8、表头删除一个学生
t9、表尾删除一个学生
10、去除重复的学生
11、按照姓名查找返回位置
12、查找输出所有的学生
代码解答 :
头文件:
#ifndef LIST_H_ // 防止头文件被重复包含,定义预处理宏 LIST_H_
#define LIST_H_
#include <myhead.h> // 包含自定义头文件 "myhead.h"
#define MAX 30 // 定义顺序表的最大容量为 30,表示最多可以存储 30 个学生信息
// 定义学生信息的结构体
typedef struct {
int id; // 学号,用整数表示
char name[20]; // 姓名,最多存储 20 个字符
char major[20]; // 专业,最多存储 20 个字符
int age; // 年龄,用整数表示
} student; // 结构体类型 student,用于表示单个学生的信息
// 定义顺序表的结构体
typedef struct {
student data[MAX]; // 存储学生信息的数组,最多包含 MAX 个 student 结构体
int len; // 统计学生个数,表示顺序表中当前已存储的学生数量
} list, *Plist; // 定义顺序表类型 list,并定义 Plist 为指向 list 结构体的指针类型
// 函数声明区域
// 创建一个顺序表并返回指向该表的指针
Plist create_list();
// 输入学生信息并存储到顺序表中
int input_list(Plist);
// 输出顺序表中的所有学生信息
int output_list(Plist);
// 判断顺序表是否已满(即学生数量是否达到 MAX)
int full(Plist);
// 在顺序表的指定位置插入一个学生信息
int insert_stu(Plist, int, student);
// 判断顺序表是否为空
int empty(Plist);
// 删除顺序表中指定位置的学生
int delete_stu(Plist, int);
// 查找顺序表中指定位置的学生
int inserach_stu(Plist, int);
// 修改顺序表中指定位置的学生信息
int change_stu(Plist, int, student);
// 在顺序表的表头插入一个学生
int insert_front(Plist, student);
// 在顺序表的表尾插入一个学生
int insert_rear(Plist, student);
// 删除顺序表的表头学生
int delete_front(Plist);
// 删除顺序表的表尾学生
int delete_rear(Plist);
// 删除顺序表中重复的学生信息
int delete_repeat(Plist);
// 根据学生姓名查找并返回其在顺序表中的位置
int find_stu(Plist, char *);
// 根据学生姓名查找并输出所有符合条件的学生信息
int find_stu_all(Plist, char *);
#endif // 结束宏定义 LIST_H_
函数文件:
#include "list.h"
// 创建顺序表,分配内存并初始化表长为0
Plist create_list(){
Plist L = malloc(sizeof(list)); // 为顺序表分配内存空间
if(NULL == L){
printf("申请空间失败\n");
return NULL; // 如果内存分配失败,返回 NULL
}
L->len = 0; // 初始化表的长度为0
printf("创建成功\n");
return L; // 返回顺序表的指针
}
// 输入学生信息并存储到顺序表中
int input_list(Plist L){
int n;
printf("要输入学生的个数:\n");
scanf("%d",&n); // 输入学生数量
for(int i=0; i<n; i++){
printf("请输入第%d个学生信息:", i+1);
printf("请输入学号:");
scanf("%d",&L->data[i].id); // 输入学号
printf("请输入姓名:");
scanf("%s",L->data[i].name); // 输入姓名
printf("请输入专业:");
scanf("%s",L->data[i].major); // 输入专业
printf("请输入年龄:");
scanf("%d",&L->data[i].age); // 输入年龄
L->len++; // 学生数量增加
}
return 0;
}
// 输出顺序表中的所有学生信息
int output_list(Plist L){
for(int i=0; i<L->len; i++){
// 按格式输出每个学生的信息
printf("学号:%d\t姓名:%s\t专业:%s\t年龄:%d\n",L->data[i].id,L->data[i].name,L->data[i].major,L->data[i].age);
}
return 0;
}
// 判断顺序表是否已满
int full(Plist L){
if(L->len == MAX){ // 如果学生数量等于最大容量,返回1表示已满
return 1;
}
return 0;
}
// 在顺序表的指定位置插入一个学生信息
int insert_stu(Plist L, int pos, student e){
int sub = pos -1; // 转换为数组下标
if(sub<0 || sub>L->len || L==NULL || full(L)){ // 检查插入位置合法性和顺序表是否已满
printf("插入失败\n");
return -1;
}
for(int i=L->len-1; i>=sub; i--){ // 将元素后移,给插入新学生腾出位置
L->data[i+1] = L->data[i];
}
L->data[sub] = e; // 插入新学生信息
L->len++; // 学生数量增加
printf("插入成功\n");
return 0;
}
// 判断顺序表是否为空
int empty(Plist L){
if(L->len == 0){ // 如果表长为0,表示顺序表为空
return 1;
}
return 0;
}
// 删除顺序表中指定位置的学生信息
int delete_stu(Plist L, int pos){
int sub = pos - 1; // 转换为数组下标
if(sub < 0 || sub > L->len-1 || L == NULL || empty(L)){ // 检查删除位置合法性和是否为空表
printf("删除失败\n");
return -1;
}
for(int i=sub; i<L->len; i++){ // 将后面的元素前移,覆盖要删除的元素
L->data[i] = L->data[i+1];
}
L->len--; // 学生数量减少
printf("删除成功\n");
return 0;
}
// 查找顺序表中指定位置的学生信息
int inserach_stu(Plist L, int pos){
int sub = pos - 1; // 转换为数组下标
if(sub < 0 || sub > L->len-1 || L == NULL || empty(L)){ // 检查查找位置合法性和是否为空表
printf("查找失败\n");
return -1;
}else{
// 输出找到的学生信息
printf("该学生存在\n");
printf("学号:%d\t姓名:%s\t专业:%s\t年龄:%d\n",L->data[sub].id,L->data[sub].name,L->data[sub].major,L->data[sub].age);
return 0;
}
}
// 修改顺序表中指定位置的学生信息
int change_stu(Plist L, int pos, student e){
int sub = pos - 1; // 转换为数组下标
if(sub < 0 || sub > L->len-1 || L == NULL || empty(L)){ // 检查修改位置合法性和是否为空表
printf("查找失败\n");
return -1;
}else{
// 修改学生信息
L->data[sub] = e;
printf("修改成功\n");
return 0;
}
}
// 在顺序表的表头插入一个学生信息
int insert_front(Plist L, student e){
if(L == NULL || full(L)){ // 检查表是否已满或顺序表为空
printf("表头插入失败\n");
return -1;
}
for(int i=L->len-1; i>=0; i--){ // 将所有学生信息后移
L->data[i+1] = L->data[i];
}
L->data[0] = e; // 将新学生信息插入表头
L->len++; // 学生数量增加
printf("表头插入成功\n");
return 0;
}
// 在顺序表的表尾插入一个学生信息
int insert_rear(Plist L, student e){
if(L == NULL || full(L)){ // 检查表是否已满或顺序表为空
printf("表尾插入失败\n");
return -1;
}
L->data[L->len] = e; // 将新学生信息插入表尾
L->len++; // 学生数量增加
printf("表尾插入成功\n");
return 0;
}
// 删除顺序表的表头学生信息
int delete_front(Plist L){
if(L == NULL || empty(L)){ // 检查是否为空表
printf("表头删除失败\n");
return -1;
}
for(int i=0; i<L->len; i++){ // 将表中的学生信息前移
L->data[i] = L->data[i+1];
}
L->len--; // 学生数量减少
printf("表头删除成功\n");
return 0;
}
// 删除顺序表的表尾学生信息
int delete_rear(Plist L){
if(L == NULL || empty(L)){ // 检查是否为空表
printf("表尾删除失败\n");
return -1;
}
L->len--; // 表尾元素直接被忽略,相当于删除最后一个元素
printf("表尾删除成功\n");
return 0;
}
// 删除顺序表中重复的学生信息
int delete_repeat(Plist L){
int i, j;
for(i=0; i<L->len; i++){
for(j=i+1; j<L->len; j++){
// 如果发现两个学生姓名相同,则删除后者
if(strcmp(L->data[i].name, L->data[j].name) == 0){
delete_stu(L, j+1); // 删除重复的学生信息
j--; // 调整索引,继续检查下一个
}
}
}
return 0;
}
// 根据学生姓名查找并返回其在顺序表中的位置
int find_stu(Plist L, char key[20]){
int i, sub = -1;
for(i=0; i<L->len; i++){
// 找到符合条件的学生
if(strcmp(L->data[i].name, key) == 0){
sub = i; // 记录找到的位置
}
}
if(sub == -1){
return -1; // 没有找到则返回 -1
}
return sub + 1; // 返回学生在表中的位置,位置从1开始计数
}
// 根据学生姓名查找并输出所有符合条件的学生信息
int find_stu_all(Plist L, char key[20]){
int i, sub = -1;
for(i=0; i<L->len; i++){
// 输出所有符合条件的学生信息
if(strcmp(L->data[i].name, key) == 0){
printf("位置:%d\t是%s\n",i+1,L->data[i].name);
sub = i;
}
}
if(sub == -1){
return -1; // 没有找到则返回 -1
}
return sub + 1;
}
主函数文件:
#include <myhead.h>
#include "list.h"
int main(int argc, const char *argv[])
{
// 创建一个顺序表,并将其地址存储在指针 L 中
Plist L = create_list();
int ch; // 用于存储用户的选择
student e; // 用于插入或修改的学生信息
int pos; // 用于指定操作的位置
char name[20]; // 用于存储查找时输入的学生姓名
// 无限循环,直到用户选择退出(或通过外部手段中断)
while(1) {
// 提示用户选择要执行的操作
printf("\t\t1、输入学生信息\n");
printf("\t\t2、任意位置插入一个学生\n");
printf("\t\t3、任意位置删除一个学生\n");
printf("\t\t4、任意位置查找一个学生\n");
printf("\t\t5、任意位置修改一个学生\n");
printf("\t\t6、表头插入一个学生\n");
printf("\t\t7、表尾插入一个学生\n");
printf("\t\t8、表头删除一个学生\n");
printf("\t\t9、表尾删除一个学生\n");
printf("\t\t10、去除重复的学生\n");
printf("\t\t11、按照姓名查找返回位置\n");
printf("\t\t12、查找输出所有的学生\n");
printf("\t\t请输入你的选择:\n");
// 读取用户输入的选择
scanf("%d", &ch);
// 根据用户的选择执行相应的操作
switch(ch) {
case 1:
// 输入学生信息并输出整个学生列表
input_list(L);
output_list(L);
break;
case 2:
// 在指定位置插入一个学生
printf("请输入要插入的学生位置:\n");
scanf("%d", &pos); // 读取要插入的学生位置
printf("请输入学生ID、姓名、专业、年龄:\n");
scanf("%d %s %s %d", &e.id, e.name, e.major, &e.age); // 读取学生信息
insert_stu(L, pos, e); // 在指定位置插入学生
output_list(L); // 输出更新后的学生列表
break;
case 3:
// 在指定位置删除一个学生
printf("请输入要删除的学生位置:\n");
scanf("%d", &pos); // 读取要删除的学生位置
delete_stu(L, pos); // 删除指定位置的学生
output_list(L); // 输出更新后的学生列表
break;
case 4:
// 在指定位置查找一个学生
printf("请输入要查找的学生位置:\n");
scanf("%d", &pos); // 读取要查找的学生位置
inserach_stu(L, pos); // 查找并输出指定位置的学生信息
break;
case 5:
// 修改指定位置的学生信息
printf("请输入要修改的学生位置:\n");
scanf("%d", &pos); // 读取要修改的学生位置
printf("请输入新的学生ID、姓名、专业、年龄:\n");
scanf("%d %s %s %d", &e.id, e.name, e.major, &e.age); // 读取新的学生信息
change_stu(L, pos, e); // 修改指定位置的学生信息
output_list(L); // 输出更新后的学生列表
break;
case 6:
// 在表头插入一个学生
printf("请输入学生ID、姓名、专业、年龄:\n");
scanf("%d %s %s %d", &e.id, e.name, e.major, &e.age); // 读取学生信息
insert_front(L, e); // 将学生插入表头
output_list(L); // 输出更新后的学生列表
break;
case 7:
// 在表尾插入一个学生
printf("请输入学生ID、姓名、专业、年龄:\n");
scanf("%d %s %s %d", &e.id, e.name, e.major, &e.age); // 读取学生信息
insert_rear(L, e); // 将学生插入表尾
output_list(L); // 输出更新后的学生列表
break;
case 8:
// 删除表头的学生
delete_front(L); // 删除表头学生
output_list(L); // 输出更新后的学生列表
break;
case 9:
// 删除表尾的学生
delete_rear(L); // 删除表尾学生
output_list(L); // 输出更新后的学生列表
break;
case 10:
// 删除重复的学生
delete_repeat(L); // 删除学生列表中重复的学生
output_list(L); // 输出更新后的学生列表
break;
case 11:
// 按照姓名查找学生,并返回位置
printf("请输入要查找的学生姓名:\n");
scanf("%s", name); // 读取要查找的学生姓名
pos = find_stu(L, name); // 查找学生
if(pos == -1) { // 如果找不到学生
printf("查找失败\n");
} else { // 如果找到学生
printf("查找成功,该学生位于第%d个位置\n", pos);
}
break;
case 12:
// 查找并输出所有匹配的学生
printf("请输入要查找的学生姓名:\n");
scanf("%s", name); // 读取要查找的学生姓名
find_stu_all(L, name); // 查找并输出所有符合条件的学生
break;
default:
// 输入无效的选择时提示用户重新输入
printf("无效的选择,请重新输入。\n");
break;
}
}
return 0;
}
成果展现:
三、总结
学习内容概述
编写了一个基于顺序表管理学生信息的项目。项目包括以下功能:创建顺序表、检查顺序表是否满或空、增加学生信息、遍历顺序表、在任意位置插入或删除学生、按位置或按值修改学生信息、按值查找学生、删除重复学生信息。代码实现了顺序表的基础操作,采用数组存储学生数据。
学习难点
1. 顺序表操作边界检查:
在插入和删除操作时,必须检查位置是否合法以及顺序表是否为空或已满。这些边界检查确保顺序表操作的稳定性。
2. 内存管理:
创建顺序表时需要动态分配内存,内存分配失败时要正确处理。
3. 删除和插入操作中的数据移动:
插入数据时需要将插入位置后的所有元素后移;删除数据时,需要将被删除位置后的元素前移。
4. 去重功能的实现:
通过两层嵌套循环比较学生姓名来删除重复信息,且删除时需要调整索引。
主要事项
1. 数组长度和顺序表长度的关系:
顺序表长度不能超过数组长度。每次增加或删除学生信息后,都需要更新顺序表长度。
2. 位置和下标的转换:
在对顺序表进行插入、删除和查找操作时,用户输入的位置要转换为数组下标(即位置-1)。
3. 动态内存分配:
需要确保动态分配内存成功,否则可能会导致程序崩溃或出现未定义行为。
4. 字符串操作:
在查找和去重操作中,使用`strcmp`函数比较学生姓名,需要确保字符串的正确输入和处理。
未来学习的重点
1. 异常处理:
可以增加更多的异常处理逻辑,确保顺序表操作的健壮性。例如,在操作过程中如果顺序表出现错误,及时提示并处理。
2. 内存管理:
深入学习动态内存分配与释放,避免内存泄漏的问题。
3. 优化查找和去重算法:
目前的查找和去重操作时间复杂度较高,可以考虑优化查找算法,如引入二分查找或哈希查找。
4. 扩展顺序表功能:
进一步扩展顺序表功能,如添加排序功能、批量删除或插入等操作,提升顺序表的实用性。