数据结构（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. 扩展顺序表功能：

进一步扩展顺序表功能，如添加排序功能、批量删除或插入等操作，提升顺序表的实用性。