第 2 章 线性表（学生健康登记表实现）

1. 示例代码

1) status.h

/* DataStructure 预定义常量和类型头文件 */#ifndef STATUS_H
#define STATUS_H/* 函数结果状态码 */
#define TRUE 					1			/* 返回值为真 */
#define FALSE 					0			/* 返回值为假 */
#define RET_OK 					0			/* 返回值正确 */
#define INFEASIABLE    		   	2			/* 返回值未知 */
#define ERR_MEMORY     		   	3			/* 访问内存错 */
#define ERR_NULL_PTR   			4			/* 空指针错误 */
#define ERR_MEMORY_ALLOCATE		5			/* 内存分配错 */
#define ERR_NULL_STACK			6			/* 栈元素为空 */
#define ERR_PARA				7			/* 函数参数错 */
#define ERR_OPEN_FILE			8			/* 打开文件错 */
#define ERR_NULL_QUEUE			9			/* 队列为空错 */
#define ERR_FULL_QUEUE			10			/* 队列为满错 */
typedef int Status;							/* Status 是函数的类型,其值是函数结果状态代码，如 RET_OK 等 */
typedef int Bollean;						/* Boolean 是布尔类型,其值是 TRUE 或 FALSE */#endif // !STATUS_H

2) singleLinkList.h

/* 线性表的单链表存储结构头文件 */#ifndef SINGLELINKLIST_H
#define SINGLELINKLIST_H#include "status.h"#define NAMELEN 20		/* 姓名最大长度 */
#define CLASSLEN 10		/* 班级名最大长度 */
#define HEALTHLEN 10	/* 健康状态字符长度 */
#define N 4		 		/* 学生个数 */typedef struct {char name[NAMELEN];long studentId;char sex;int age;char className[CLASSLEN];int healthState;
} StudentInfo;typedef StudentInfo ElemType;typedef struct LNode {ElemType data;struct LNode *next;
} *LinkList;/* 辅助函数，创建一个新的节点 */
LinkList MakeNewLNode(ElemType e);/* 操作结果：构造一个空的线性表 L */
Status InitList(LinkList *L);/* 初始条件：线性表 L 已存在。操作结果：销毁线性表 L */
Status DestroyList(LinkList *L);/* 初始条件：线性表 L 已存在。操作结果：将 L 重置为空表 */
Status ClearList(LinkList L);/* 初始条件：线性表 L 已存在。操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE */
Status ListEmpty(LinkList L);/* 初始条件：线性表 L 已存在。操作结果：返回 L 中数据元素个数 */
int ListLength(LinkList L);/* 算法 2.8，L 为带头结点的单链表的头指针。当第 i 个元素存在时, 其值赋给 e 并返回 OK,否则返回 ERROR */
Status GetElem(LinkList L, int i, ElemType *e);/* 初始条件: 线性表 L 已存在, compare() 是数据元素判定函数(满足为 1,否则为 0)操作结果: 返回 L 中第 1 个与 e 满足关系 compare() 的数据元素的位序。若这样的数据元素不存在,则返回值为 0 */
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType));/* 算法 2.9，在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e */
Status ListInsert(LinkList L, int i, ElemType e);/* 算法 2.10，在带头结点的单链线性表 L 中，删除第 i 个元素,并由 e 返回其值 */
Status ListDelete(LinkList L, int i, ElemType* e);/* 按学号非降序插入 */
void InsertAscend(LinkList L, ElemType e);#endif

3) singleLinkList.c

/* 线性表的单链表存储结构源文件实现 */#include "singleLinkList.h"
#include <stdlib.h>
#include <stdio.h>
#include <math.h>/* 辅助函数，创建一个新的节点 */
LinkList MakeNewLNode(ElemType e)
{LinkList newLNode = (LinkList)malloc(sizeof(struct LNode));if (!newLNode) {printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_MEMORY_ALLOCATE);return NULL;}newLNode->data = e;newLNode->next = NULL;return newLNode;
}/* 操作结果：构造一个空的线性表 L */
Status InitList(LinkList *L)
{*L = (LinkList)malloc(sizeof(struct LNode));if (!(*L)) {printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_MEMORY_ALLOCATE);return ERR_MEMORY_ALLOCATE;}(*L)->next = NULL;return RET_OK;
}/* 初始条件：线性表 L 已存在。操作结果：销毁线性表 L */
Status DestroyList(LinkList *L)
{LinkList q;while (*L) {q = (*L)->next;free(*L);*L = q;}return RET_OK;
}/* 初始条件：线性表 L 已存在。操作结果：将 L 重置为空表 */
Status ClearList(LinkList L)
{LinkList p, q;p = L->next;while (p) {q = p->next;free(p);p = q;}L->next = NULL;return RET_OK;
}/* 初始条件：线性表 L 已存在。操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE */
Status ListEmpty(LinkList L)
{if (L->next) {return FALSE;}return TRUE;
}/* 初始条件：线性表 L 已存在。操作结果：返回 L 中数据元素个数 */
int ListLength(LinkList L)
{int count = 0;LinkList p = L->next;while (p) {++count;p = p->next;}return count;
}/* 算法 2.8，L 为带头结点的单链表的头指针。当第 i 个元素存在时, 其值赋给 e 并返回 RET_OK,否则返回 ERROR */
Status GetElem(LinkList L, int i, ElemType *e)
{int j = 1;LinkList p = L->next;while (p && j < i) {p = p->next;++j;}if (!p || j > i) {			/* j > i 适用于 i < 1 时，如 i = 0 */printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_PARA);return ERR_PARA;}*e = p->data;return RET_OK;
}/* 初始条件: 线性表 L 已存在, compare() 是数据元素判定函数(满足为 1,否则为 0)操作结果: 返回 L 中第 1 个与 e 满足关系 compare() 的数据元素的位序。若这样的数据元素不存在,则返回值为 0 */
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType))
{int i = 0;LinkList p = L->next;while (p) {++i;if (compare(p->data, e)) {return i;}p = p->next;}return 0;
}/* 算法 2.9，在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e */
Status ListInsert(LinkList L, int i, ElemType e)
{int j = 0;LinkList p = L;while (p && j < i - 1) {++j;p = p->next;}if (!p || j > i - 1) {				/* 超出表长或者 i < 1 */printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_PARA);return ERR_PARA;}LinkList newLNode = MakeNewLNode(e);if (!newLNode) {printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_MEMORY_ALLOCATE);return ERR_MEMORY_ALLOCATE;}newLNode->next = p->next;p->next = newLNode;return RET_OK;
}/* 算法 2.10，在带头结点的单链线性表 L 中，删除第 i 个元素,并由 e 返回其值 */
Status ListDelete(LinkList L, int i, ElemType *e)
{int j = 0;LinkList p = L;while (p->next && j < i - 1) {++j;p = p->next;}if (!p->next || j > i - 1) {	/* 理论上 j 最多只能等于 i - 1, 但此处当参数不合法时可用， 建议单独判断参数合法性 */printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_PARA);return ERR_PARA;}LinkList q = p->next;p->next = q->next;*e = q->data;free(q);return RET_OK;
}/* 初始条件：线性表 L 已存在操作结果:依次对 L 的每个数据元素调用函数 vi()。一旦 vi() 失败,则操作失败 */
Status ListTraverse(LinkList L, void(*vi)(ElemType))
{LinkList p = L->next;while (p) {vi(p->data);p = p->next;}return RET_OK;
}/* 按学号非降序插入 */
void InsertAscend(LinkList L, ElemType e)
{LinkList q = L, p = L->next;while (p && e.studentId > p->data.studentId) {q = p;p = p->next;}q->next = MakeNewLNode(e);q->next->next = p;
}

4) studentHealthRecord.h

/* 学生健康登记表定义头文件 */#ifndef STUDENTSHEALTHRECORD_H
#define STUDENTSHEALTHRECORD_H#include "status.h"
#include "singleLinkList.h"
#include <stdio.h>/* 打印学生信息 */
void PrintStuentInfo(char healthState[][HEALTHLEN], int arrayLen, ElemType e);/* 读入学生信息 */
void ReadIn(char healthState[][HEALTHLEN], int arrayLen, ElemType *e);/* 将学生信息写入指定文件 */
void WriteToFile(ElemType e, FILE *fp);/* 由 fp 指定文件读取学生信息到 e */
Status ReadFromFile(ElemType *e, FILE *fp);/* 查找表中学号为 studentId 的结点,如找到,q 指向此结点, p 指向 q 的前驱并返回 TRUE; 如无此元素,则返回 FALSE */
Status FindByStudentId(LinkList L, long studentId, LinkList *p, LinkList *q);/* 查找表中姓名为 name 的结点,如找到,q 指向此结点, p 指向 q 的前驱并返回 TRUE; 如无此元素,则返回 FALSE */
Status FindByName(LinkList L, char name[], LinkList *p, LinkList *q);/* 删除表中学号为 studentId 的元素，并返回 TRUE；如无此元素，则返回 FALSE */
Status DeleteByStudentId(LinkList L, long studentId);/* 删除表中姓名为 name 的元素，并返回 TRUE；如无此元素，则返回 FALSE */
Status DeleteByName(LinkList L, char name[]);/* 修改学生信息 */
void ModifyStudentInfo(char healthState[][HEALTHLEN], int arrayLen, ElemType *e);/* 显示操作选项 */
void ShowMenu(void);#endif // !STUDENTSHEALTHRECORD_H

5) studentHealthRecord.c

/* 学生健康登记表实现源文件 */#include "studentHealthRecord.h"
#include <string.h>
#include <stdlib.h>/* 打印学生信息 */
void PrintStuentInfo(char healthState[][HEALTHLEN], int arrayLen, ElemType e)
{if (e.healthState > arrayLen - 1) {printf("Error: Parameter out of bounds!\n");return;}printf("%-10s%-10ld", e.name, e.studentId);if (e.sex == 'm') {printf(" Man");}else {printf(" Female");}printf("%10d%10s%10s\n", e.age, e.className, healthState[e.healthState]);
}/* 读入学生信息 */
void ReadIn(char healthState[][HEALTHLEN], int arrayLen, ElemType *e)
{printf("Please input name(No more than %d characters): ", NAMELEN);scanf_s("%s", e->name, (unsigned int)sizeof(e->name));getchar();printf("Please input the student ID: ");scanf_s("%ld", &e->studentId);getchar();printf("Please input the gender: ");scanf_s("%c", &e->sex, 1);getchar();printf("Please input the age: ");scanf_s("%d", &e->age);getchar();printf("Please input the class name: ");scanf_s("%s", e->className, (unsigned int)sizeof(e->className));getchar();printf("Please input the health state(");for (int i = 0; i < arrayLen; ++i) {printf("%d: %s ", i, healthState[i]);}printf("): ");scanf_s("%d", &e->healthState);getchar();
}/* 将学生信息写入指定文件 */
void WriteToFile(ElemType e, FILE *fp)
{fwrite(&e, sizeof(StudentInfo), 1, fp);
}/* 由 fp 指定文件读取学生信息到 e */
Status ReadFromFile(ElemType *e, FILE *fp)
{size_t ret = fread(e, sizeof(StudentInfo), 1, fp);return (ret == 1) ? 1 : 0;
}/* 查找表中学号为 studentId 的结点,如找到,q 指向此结点, p 指向 q 的前驱并返回 TRUE; 如无此元素,则返回 FALSE */
Status FindByStudentId(LinkList L, long studentId, LinkList *p, LinkList *q)
{*p = L;while (*p) {*q = (*p)->next;if (*q && (*q)->data.studentId > studentId) {break;}if (*q && (*q)->data.studentId == studentId) {return TRUE;}*p = *q;}return FALSE;
}/* 查找表中姓名为 name 的结点,如找到,q 指向此结点, p 指向 q 的前驱并返回 TRUE; 如无此元素,则返回 FALSE */
Status FindByName(LinkList L, char name[], LinkList *p, LinkList *q)
{*p = L;while (*p) {*q = (*p)->next;if (*q && !strcmp((*q)->data.name, name)) {return TRUE;}*p = *q;}return FALSE;
}/* 删除表中学号为 studentId 的元素，并返回 TRUE；如无此元素，则返回 FALSE */
Status DeleteByStudentId(LinkList L, long studentId)
{LinkList p, q;if (FindByStudentId(L, studentId, &p, &q)) {p->next = q->next;free(q);return TRUE;}return FALSE;
}/* 删除表中姓名为 name 的元素，并返回 TRUE；如无此元素，则返回 FALSE */
Status DeleteByName(LinkList L, char name[])
{LinkList p, q;if (FindByName(L, name, &p, &q)) {p->next = q->next;free(q);return TRUE;}return FALSE;
}/* 修改学生信息 */
void ModifyStudentInfo(char healthState[][HEALTHLEN], int arrayLen, ElemType *e)
{PrintStuentInfo(healthState, arrayLen, *e);printf("Please input the content you want to modify, or click Enter to cancel\n");char str[100];printf("Please input name(No more than %d characters): ", NAMELEN);if (gets_s(str, sizeof(str)) == NULL) {printf("%s, line: %d: Error: Get string failed!\n", __func__, __LINE__);}if (strlen(str)) {strcpy_s(e->name, sizeof(e->name), str);	/* 第二个参数为目标缓冲区大小 */}printf("Please input student ID: ");if (gets_s(str, sizeof(str)) == NULL) {printf("%s, line: %d: Error: Get string failed!\n", __func__, __LINE__);}if (strlen(str)) {e->studentId = atol(str);}printf("Please input gender(m: Man f: Female): ");if (gets_s(str, sizeof(str)) == NULL) {printf("%s, line: %d: Error: Get string failed!\n", __func__, __LINE__);}if (strlen(str)) {e->sex = str[0];}printf("Please input age: ");if (gets_s(str, sizeof(str)) == NULL) {printf("%s, line: %d: Error: Get string failed!\n", __func__, __LINE__);}if (strlen(str)) {e->age = atoi(str);}printf("Please input class name(No more than %d characters): ", CLASSLEN);if (gets_s(str, sizeof(str)) == NULL) {printf("%s, line: %d: Error: Get string failed!\n", __func__, __LINE__);}if (strlen(str)) {strcpy_s(e->className, sizeof(e->className), str);}printf("Please input the health state(");for (int i = 0; i < arrayLen; ++i) {printf("%d: %s ", i, healthState[i]);}printf("): ");if (gets_s(str, sizeof(str)) == NULL) {printf("%s, line: %d: Error: Get string failed!\n", __func__, __LINE__);}if (strlen(str)) {e->healthState = atoi(str);}
}void ShowMenu(void)
{printf("1:  将结构体数组 student 中的记录按学号非降序插入链表\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");printf("10: 显示所有记录\n");printf("11: 将链表中的所有记录存入文件\n");printf("12: 结束\n");printf("    请选择操作命令: ");
}

6) main.c

/* 入口程序源文件 */#include "studentHealthRecord.h"
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>int main(void)
{char healthState[3][10] = { "Health", "Normal", "Unhealth" };StudentInfo student[N] = {{ "王小林", 790631, 'm', 18, "计91", 0 },{ "陈红", 790632, 'f', 20, "计91", 1 },{ "刘建平", 790633, 'm', 21, "计91", 0 },{ "张立立", 790634, 'm', 17, "计91", 2 }};bool flag = true;int choose;LinkList studentList;InitList(&studentList);ElemType e;char fileName[30];long studentId;char name[30];LinkList p, q;while (flag) {ShowMenu();scanf_s("%d", &choose);switch (choose) {case 1:for (int i = 0; i < N; ++i) {InsertAscend(studentList, student[i]);}break;case 2: printf("Please input file name: ");scanf_s("%s", fileName, (unsigned int)sizeof(fileName));FILE* fp;errno_t err_ret = fopen_s(&fp, fileName, "rb");if ( err_ret != 0) {printf("Open file failed!\n");}else {while (ReadFromFile(&e, fp)) {InsertAscend(studentList, e);}fclose(fp);}break;case 3: ReadIn(healthState, 3, &e);InsertAscend(studentList, e);break;case 4: printf("Please input the student ID to delete: ");scanf_s("%ld", &studentId);if (!DeleteByStudentId(studentList, studentId)) {printf("Error: No record of student ID of %ld.\n", studentId);}break;case 5:printf("Please input the name of the student of record to be deleted: ");scanf_s("%s", name, (unsigned int)sizeof(name));if (!DeleteByName(studentList, name)) {printf("Error: No record of student name of %s.", name);}break;case 6:printf("Please input the student ID of the record to be modified: ");scanf_s("%ld", &studentId);getchar();if (!FindByStudentId(studentList, studentId, &p, &q)) {printf("No record of the student Id of %ld\n", studentId);}else {ModifyStudentInfo(healthState, 3, &q->data);if (q->data.studentId != studentId) {p->next = q->next;InsertAscend(studentList, q->data);free(q);}}break;case 7:printf("Please input the name of the student of record to be deleted: ");scanf_s("%s", name, (unsigned int)sizeof(name));if (!FindByName(studentList, name, &p, &q)) {printf("No record of name of student %s.\n", name);}else {studentId = q->data.studentId;ModifyStudentInfo(healthState, 3, &q->data);if (q->data.studentId != studentId) {p->next = q->next;InsertAscend(studentList, q->data);free(q);}}break;case 8:printf("Please input the student ID of the record to be found: ");scanf_s("%ld", &studentId);if (!FindByStudentId(studentList, studentId, &p, &q)) {printf("No record of the student ID of %ld\n", studentId);}else {PrintStuentInfo(healthState, 3, q->data);}break;case 9:printf("Please input the name of the student of the record to be found: ");scanf_s("%s", name, (unsigned int)sizeof(name));if (!FindByName(studentList, name, &p, &q)) {printf("No record of the student name of %s.\n", name);}else {PrintStuentInfo(healthState, 3, q->data);}break;case 10:p = studentList->next;while (p) {PrintStuentInfo(healthState, 3, p->data);p = p->next;}break;case 11:printf("Please input the file name: ");scanf_s("%s", fileName, (unsigned int)sizeof(fileName));err_ret = fopen_s(&fp, fileName, "wb+");if (err_ret != 0) {printf("Open file failed!\n");}else {LinkList p = studentList->next;while (p) {WriteToFile(p->data, fp);p = p->next;}}fclose(fp);break;case 12:flag = false;}}int ret = DestroyList(&studentList);if (ret != RET_OK) {printf("Error: Destroy list failed!\n");}return 0;
}

 

2. 输出示例