PTA 学生成绩链表处理（线性表之链表描述） —— C

150 阅读 0 评论 99 点赞

我是靠谱客的博主迷路蜻蜓，这篇文章主要介绍PTA 学生成绩链表处理（线性表之链表描述） —— C，现在分享给大家，希望可以做个参考。

本题要求实现两个函数，一个将输入的学生成绩组织成单向链表；另一个将成绩低于某分数线的学生结点从链表中删除。

函数接口定义：

复制代码

1
2
3
struct stud_node *createlist();
struct stud_node *deletelist( struct stud_node *head, int min_score );

函数createlist利用scanf从输入中获取学生的信息，将其组织成单向链表，并返回链表头指针。链表节点结构定义如下：

复制代码

1
2
3
4
5
6
7
struct stud_node {
    int              num;      /*学号*/
    char             name[20]; /*姓名*/
    int              score;    /*成绩*/
    struct stud_node *next;    /*指向下个结点的指针*/
};

输入为若干个学生的信息（学号、姓名、成绩），当输入学号为0时结束。

函数deletelist从以head为头指针的链表中删除成绩低于min_score的学生，并返回结果链表的头指针。

裁判测试程序样例：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <stdlib.h>

struct stud_node {
     int    num;
     char   name[20];
     int    score;
     struct stud_node *next;
};

struct stud_node *createlist();
struct stud_node *deletelist( struct stud_node *head, int min_score );

int main()
{
    int min_score;
    struct stud_node *p, *head = NULL;

    head = createlist();
    scanf("%d", &min_score);
    head = deletelist(head, min_score);
    for ( p = head; p != NULL; p = p->next )
        printf("%d %s %dn", p->num, p->name, p->score);

    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

1 zhang 78
2 wang 80
3 li 75
4 zhao 85
0
80

输出样例：

2 wang 80
4 zhao 85

思路：若第一个元素 head 小于 min_score ，则删除，直到满足第一个元素大于 min_score ；遍历链表，并记录当前访问结点 temnode 的前节点 prenode，若 temnode < min_score ，删除该节点，>= min_score，继续以此方法访问下一节点。

注意：初始情况下，head tail 指针为空，添加元素后 tail ->next 为 null（一定要写这句话，不然 tail ->next 不为空）；使用 temnode= (struct stud_node *)malloc(sizeof(struct stud_node)); 创建的空间，需要用 free(temnode) 来释放空间，不能用 delete。

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
struct stud_node *createlist(){
	int thenum;
	struct stud_node *temnode, *tail, *head;
	head = tail = NULL;
	while (scanf("%d", &thenum) && thenum) {
		temnode= (struct stud_node *)malloc(sizeof(struct stud_node));
		temnode->num = thenum;
		temnode->next = NULL;
		scanf("%s %d", temnode->name, &temnode->score);
		if (head==NULL)
			head = temnode;
		else 
			tail->next = temnode;
		tail = temnode;
	}
	return head;
}

struct stud_node *deletelist(struct stud_node *head, int min_score) {
	struct stud_node *temnode, *prenode;
	while (head!=NULL&&head->score<min_score) {
		temnode = head;
		head = head->next;
		free(temnode);
	}
	if (head == NULL)
		return NULL;
	prenode = head;
	temnode = head->next;
	while (temnode != NULL) {
		if (temnode->score < min_score) {
			prenode->next = temnode->next;
			free(temnode);
		}
		else 
			prenode = temnode;
		temnode = prenode->next;
	}
	return head;
}