1267 - C语言11.3
建立一个存储学生学号和成绩信息的动态链表，并参照本书例题11.8至11.11，实现这个动态链表的建立、输出、删除特定节点、插入操作。
结构体student，存储学生的学号、名字、性别和年龄，读入每个学生的所有信息，保存在结构体中，并输出。
动态链表的每个节点存储的结构体student的定义如下：
struct student {
long num;
float score;
struct student * next;
};
本题较为复杂，请参考本书相应的例题进行实现。
Input
输入的前几行为链表的建立过程。每行有一个整数和一个实数，用空格隔开，分别表示学生的学号和成绩。如果读入的学号为0，说明链表的建立过程已经结束，这个学号为0的信息不存入链表。
之后的几行每行包含一个整数，表示删除学号与这个整数相等的学生信息（删除链表节点）。如果输入的整数为0，说明删除过程已经结束，且不需要处理学号为0的节点。
最后的几行每行包含一个整数和一个实数，用空格隔开，分别表示需要插入的学生学号和成绩。如果读入的学号为0，说明插入的过程已经结束，这个学号为0的信息不需要插入链表。
输入保证在任何时刻，链表中不存在有相同学号的学生，建立链表的过程中输入的学号数值保证严格递增且大于0，链表为空时不会再继续删除。输入的总行数不超过100。
Output
首先规定用以下格式输出某一时刻链表的状态：
在一行内输出当前链表的节点数n，并在接下来的n行中按顺序输出每一个节点（学生）的学号和成绩信息，用空格隔开，且成绩保留1位小数。
在链表的建立过程结束之后，输出当前链表状态；在每一次删除操作（不包括用来标记删除过程结束的学号为0的那一次）之后，输出链表状态；在每一次插入操作（不包括用来标记插入过程结束的学号为0的那一次）之后，输出链表状态。
请注意行尾输出换行。
Examples
Input
10101 90 10103 87 10105 77 0 0 10103 10105 0 10104 87 10106 65 0 0
Output
3 10101 90.0 10103 87.0 10105 77.0 2 10101 90.0 10105 77.0 1 10101 90.0 2 10101 90.0 10104 87.0 3 10101 90.0 10104 87.0 10106 65.0
Solution C
#include <stdio.h> #include <stdlib.h> /* 结构体定义 */ struct student { long num; float score; struct student * next; }; /* n是全局变量，表示当前动态链表的节点个数 */ int n; /* 定义建立动态链表的函数，返回值为指向链表头的指针 */ struct student * create(void) { struct student * head, *tail, *p; n = 0; head = NULL; tail = p = (struct student *)malloc(sizeof(struct student)); scanf("%ld %f", &p->num, &p->score); while (p->num != 0) { n++; if (n == 1) head = p; else tail->next = p; tail = p; p = (struct student *)malloc(sizeof(struct student)); scanf("%ld %f", &p->num, &p->score); } tail->next = NULL; free(p); return head; } /* 定义输出链表的函数 */ void print(struct student * head) { struct student * p; p = head; printf("%d\n", n); while (p != NULL) { printf("%ld %.1f\n", p->num, p->score); p = p->next; } } /* 定义删除特定学号节点的函数，返回值为指向链表头的指针 */ struct student * del(struct student * head, long num) { struct student *p1, *p2; if (head == NULL) return head; p1 = head; /* 如果p1指向的不是要找的节点且后面还有节点，则p1后移 */ while (p1->num != num && p1->next != NULL) { p2 = p1; p1 = p1->next; } /* 找到了需要的节点 */ if (num == p1->num) { /* 如果需要的节点是首节点，则首节点后移； 否则将下一节点的地址复制给前一节点的next */ if (p1 == head) head = p1->next; else p2->next = p1->next; free(p1); n--; } return head; } /* 定义插入节点的函数，返回值为指向链表头的指针 */ struct student * insert(struct student * head, struct student * stud) { struct student *p1, *p2; p1 = head; /* 若原来的链表是空的，则使插入的节点为头节点 */ if (head == NULL) { head = stud; head->next = NULL; } else { /* 如果p1指向的节点学号小于要插入的且后面还有节点，则p1后移 */ while (p1->num < stud->num && p1->next != NULL) { p2 = p1; p1 = p1->next; } /* 新节点要插入在p1之前 */ if (p1->num > stud->num) { /* 需要插入在头结点之前的特殊情况 */ if (p1 == head) { head = stud; head->next = p1; } else { p2->next = stud; stud->next = p1; } } else { /* 新节点要插入在p1之后 */ p1->next = stud; stud->next = NULL; } } n++; return head; } /* 主函数 */ int main() { struct student *head, *stud; long num_to_del; head = create(); print(head); scanf("%ld", &num_to_del); while (num_to_del != 0) { head = del(head, num_to_del); print(head); scanf("%ld", &num_to_del); } stud = (struct student *)malloc(sizeof(struct student)); scanf("%ld %f", &stud->num, &stud->score); while (stud->num != 0) { head = insert(head, stud); print(head); stud = (struct student *)malloc(sizeof(struct student)); scanf("%ld %f", &stud->num, &stud->score); } free(stud); return 0; }
Solution C++
#include <stdio.h> #include <stdlib.h> /* 结构体定义 */ struct student { long num; float score; struct student * next; }; /* n是全局变量，表示当前动态链表的节点个数 */ int n; /* 定义建立动态链表的函数，返回值为指向链表头的指针 */ struct student * create(void) { struct student * head, *tail, *p; n = 0; head = NULL; tail = p = (struct student *)malloc(sizeof(struct student)); scanf("%ld %f", &p->num, &p->score); while (p->num != 0) { n++; if (n == 1) head = p; else tail->next = p; tail = p; p = (struct student *)malloc(sizeof(struct student)); scanf("%ld %f", &p->num, &p->score); } tail->next = NULL; free(p); return head; } /* 定义输出链表的函数 */ void print(struct student * head) { struct student * p; p = head; printf("%d\n", n); while (p != NULL) { printf("%ld %.1f\n", p->num, p->score); p = p->next; } } /* 定义删除特定学号节点的函数，返回值为指向链表头的指针 */ struct student * del(struct student * head, long num) { struct student *p1, *p2; if (head == NULL) return head; p1 = head; /* 如果p1指向的不是要找的节点且后面还有节点，则p1后移 */ while (p1->num != num && p1->next != NULL) { p2 = p1; p1 = p1->next; } /* 找到了需要的节点 */ if (num == p1->num) { /* 如果需要的节点是首节点，则首节点后移； 否则将下一节点的地址复制给前一节点的next */ if (p1 == head) head = p1->next; else p2->next = p1->next; free(p1); n--; } return head; } /* 定义插入节点的函数，返回值为指向链表头的指针 */ struct student * insert(struct student * head, struct student * stud) { struct student *p1, *p2; p1 = head; /* 若原来的链表是空的，则使插入的节点为头节点 */ if (head == NULL) { head = stud; head->next = NULL; } else { /* 如果p1指向的节点学号小于要插入的且后面还有节点，则p1后移 */ while (p1->num < stud->num && p1->next != NULL) { p2 = p1; p1 = p1->next; } /* 新节点要插入在p1之前 */ if (p1->num > stud->num) { /* 需要插入在头结点之前的特殊情况 */ if (p1 == head) { head = stud; head->next = p1; } else { p2->next = stud; stud->next = p1; } } else { /* 新节点要插入在p1之后 */ p1->next = stud; stud->next = NULL; } } n++; return head; } /* 主函数 */ int main() { struct student *head, *stud; long num_to_del; head = create(); print(head); scanf("%ld", &num_to_del); while (num_to_del != 0) { head = del(head, num_to_del); print(head); scanf("%ld", &num_to_del); } stud = (struct student *)malloc(sizeof(struct student)); scanf("%ld %f", &stud->num, &stud->score); while (stud->num != 0) { head = insert(head, stud); print(head); stud = (struct student *)malloc(sizeof(struct student)); scanf("%ld %f", &stud->num, &stud->score); } free(stud); return 0; }