C语言中,使用单链表存储若干个学生信息,包括姓名、性别和成绩,并在用户输入成绩后对学生根据成绩由高到低的顺序进行排序,使用快速排序算法。学生数量由用户输入确认,单链表为动态链表
时间: 2024-05-27 18:14:35 浏览: 101
C语言程序设计——学生成绩管理系统(链表).zip
。具体实现过程如下:
1. 定义学生信息的结构体,包括姓名、性别和成绩等字段。
typedef struct Student{
char name[20];
char gender;
int score;
struct Student* next;
}Student;
2. 定义单链表的头指针和尾指针,并初始化为空。
Student* head = NULL;
Student* tail = NULL;
3. 实现向单链表中添加学生信息的函数,每次添加都是在链表末尾进行的。
void addStudent(){
Student* newStudent = (Student*)malloc(sizeof(Student));
printf("Please input student name, gender and score: ");
scanf("%s %c %d", newStudent->name, &(newStudent->gender), &(newStudent->score));
newStudent->next = NULL;
if(head == NULL){
head = newStudent;
tail = newStudent;
}
else{
tail->next = newStudent;
tail = newStudent;
}
}
4. 实现快速排序算法,根据学生的成绩进行排序。具体实现过程如下:
void swap(Student* a, Student* b){
Student temp = *a;
*a = *b;
*b = temp;
}
Student* partition(Student* left, Student* right){
Student* pivot = right;
Student* i = left;
Student* j = left;
while(j != right){
if(j->score > pivot->score){
swap(i, j);
i = i->next;
}
j = j->next;
}
swap(i, right);
return i;
}
void quickSort(Student* left, Student* right){
if(left == NULL || right == NULL || left == right || left == tail){
return;
}
Student* pivot = partition(left, right);
quickSort(left, pivot->next);
quickSort(pivot->next, right);
}
5. 调用上述函数对单链表中的学生信息进行排序。
void sort(){
quickSort(head, tail);
}
6. 完整代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Student{
char name[20];
char gender;
int score;
struct Student* next;
}Student;
Student* head = NULL;
Student* tail = NULL;
void addStudent(){
Student* newStudent = (Student*)malloc(sizeof(Student));
printf("Please input student name, gender and score: ");
scanf("%s %c %d", newStudent->name, &(newStudent->gender), &(newStudent->score));
newStudent->next = NULL;
if(head == NULL){
head = newStudent;
tail = newStudent;
}
else{
tail->next = newStudent;
tail = newStudent;
}
}
void swap(Student* a, Student* b){
Student temp = *a;
*a = *b;
*b = temp;
}
Student* partition(Student* left, Student* right){
Student* pivot = right;
Student* i = left;
Student* j = left;
while(j != right){
if(j->score > pivot->score){
swap(i, j);
i = i->next;
}
j = j->next;
}
swap(i, right);
return i;
}
void quickSort(Student* left, Student* right){
if(left == NULL || right == NULL || left == right || left == tail){
return;
}
Student* pivot = partition(left, right);
quickSort(left, pivot->next);
quickSort(pivot->next, right);
}
void sort(){
quickSort(head, tail);
}
void display(){
Student* p = head;
printf("Name\tGender\tScore\n");
while(p){
printf("%s\t%c\t%d\n", p->name, p->gender, p->score);
p = p->next;
}
}
int main(){
int n;
printf("Please input the number of students: ");
scanf("%d", &n);
for(int i=0; i<n; i++){
addStudent();
}
sort();
display();
return 0;
}
阅读全文