题目:
每个学生的信息卡片包括学号, 姓名和成绩三项. 定义存储学生信息的单向链表的结点类型; 编写函 数, 由文件依次读入 n(n≥0) 个学生的信息, 创建一个用于管理学生信息的单向链表; 编写函数, 对 该链表进行整理, 保证该单向链表的结点顺序满足学号从小到大的顺序.
算法的设计与分析:
定义学生类型结构体 (含有分量 id,name,score), 定义链表节点结构体 (含有分量 student 结构体 stu 和指向下一个节点的指针 next)
从文件读取, 采用 fopen 方法返回 FILE 指针, 用 fscanf 方法读取数据并创建节点组成链表
还可以使用 freopen 的方法, 直接 scanf 即可
或者用我一开始的土方法, 用 fgets 函数读取一行, 用 stroke 分割该行字符串, 将字符串转化成 int, 创建结构体. 比上面的方法复杂多了.
按学号排序, 采用插入排序的方法, 插入排序, 以 sorted(初始为第一个元素) 为边界, 将 sorted 后的一个节点插在前面已经排好的链表中, 直到 sorted 后没有节点
注意:
char* 结构体 * 等指针要用必须分配空间
分配空间通常使用 malloc 函数, A* a=(*A)malloc(sizeof(A))
malloc 申请的空间要 free 掉, free(a)
malloc 和 free 这一对与 new 和 delete 这一对非常像, c++ 里动态分配空间用 new,c 里要用 malloc
源代码 (talk is cheap,show me the code)(屁话少说, 放码过来)
- #include <stdio.h>
- #include<malloc.h>
- #define NAME_MAX 20 // 名字的最长长度
- typedef struct my_student {
- int id;
- char* name;
- int score;
- } student;
- typedef struct my_list_node {
- student stu;
- struct my_list_node *next;
- } Node;
- Node* getStuFromFile(char *path) {
- // 从文件中读取学生数据创建单链表并返回头指针
- FILE *stu_file;
- stu_file = fopen(path, "r");
- if (stu_file == NULL) {// 如果路径不正确
- printf("file path error!");
- return 0;
- }
- // 循环从文件中读取数据创建节点
- Node* head = (Node*)malloc(sizeof(Node));// 哨兵节点
- Node* current_node = head;// 用于循环赋值时表示当前节点
- while (!feof(stu_file)) {
- Node* temp = (Node*)malloc(sizeof(Node));
- //id ,name,score 分别表示临时节点的 student 的 id 等
- int* id =&( temp->stu.id);
- temp->stu.name = (char*)malloc(sizeof(char)*NAME_MAX);
- char* name = temp->stu.name;
- int* score = &(temp->stu.score);
- // 从文件中读取临时节点的各个数据并赋值
- fscanf(stu_file, "%d %s %d", id, name, score);
- // 将临时节点设为当前节点的子节点
- current_node->next = temp;
- current_node = current_node->next;
- }
- current_node->next = 0;
- fclose(stu_file);
- return head;
- }
- void showStuInfor(Node* node) {
- // 递归打印每个学生的信息
- if (node != 0) {
- printf("%d %s %d\n", node->stu.id, node->stu.name, node->stu.score);
- if (node->next != 0) {
- // 递归
- showStuInfor(node->next);
- }
- }
- }
- void insertNode(Node* preL, Node* preR) {
- // 在 preL 节点后插入 preR 后的节点
- Node* insert= preR->next;
- preR->next = preR->next->next;
- insert->next = preL->next;
- preL->next = insert;
- }
- void sortListByStuId(Node *head) {
- // 插入排序, 以 sorted 为边界, 将 sorted 后的一个节点插在前面已经排好的链表中, 直到 sorted 后没有节点
- // 初始化 sorted 有一个节点, 算是已经排好序
- Node* sorted = head->next;
- // 将 sorted 后的一个节点插到前面
- while (sorted->next != 0) {
- Node* insert = sorted->next;
- Node* loc = head;
- // 从 head 开始遍历该插入到什么地方
- while (insert->stu.id> loc->next->stu.id) {
- loc = loc->next;
- }
- // 如果 loc 与 sorted 不相等执行插入, 如果相等说明要插入的元素比 sorted 之前的都大, 直接让 sorted 后移即可
- if (loc != sorted) {
- insertNode(loc, sorted);
- }
- else {
- sorted = sorted->next;
- }
- }
- }
- void freeNodes(Node* head) {
- // 递归释放 malloc 申请的空间
- if (head != 0) {
- if (head->next != 0) {
- // 释放 name 占用的空间
- free(head->next->stu.name);
- // 递归释放
- freeNodes(head->next);
- }
- free(head);
- }
- }
- void test() {
- // 测试函数
- // 从文件中读取学生数据并打印
- char path[] = "D:\\student.txt";
- Node* students = getStuFromFile(path);
- showStuInfor(students->next);
- printf("\n sorted:\n");
- // 按学号排序后打印学生数据
- sortListByStuId(students);
- showStuInfor(students->next);
- freeNodes(students);
- }
- int main() {
- test();
- }
- The end
来源: http://www.bubuko.com/infodetail-2880133.html