《C语言程序设计》(谭浩强第五版) 第9章 用户自己建立数据类型 习题解析与答案

你也可以上程序咖(https://meta.chengxuka.com)，打开大学幕题板块，不但有答案，讲解，还可以在线答题。

题目1：定义一个结构体变量（包括年、月、日）。计算该日在本年中是第几天，注意闰年问题。

解：

解题思路为：正常年份每个月中的天数是已知的，只要给出日期，算出该日在本年中是第几天是不困难的。如果是闰年且月份在 3 月或 3 月以后时，应再增加 1 天。闰年的规则是：年份能被 4 或 400 整除但不能被 100 整除，例如，2000 年是闰年，2100 年不是闰年。

解法一：

#include 
struct
{
	int year;
	int month;
	int day;
} date; //结构体变量 date中的成员对应于年、月、日

int main()
{
	int days; // days 为天数
	printf("input year,month,day:");
	scanf("%d,%d,%d", &date.year, &date.month, &date.day);
	switch (date.month)
	{
	case 1:
		days = date.day;
		break;
	case 2:
		days = date.day + 31;
		break;
	case 3:
		days = date.day + 59;
		break;
	case 4:
		days = date.day + 90;
		break;
	case 5:
		days = date.day + 120;
		break;
	case 6:
		days = date.day + 151;
		break;
	case 7:
		days = date.day + 181;
		break;
	case 8:
		days = date.day + 212;
		break;
	case 9:
		days = date.day + 243;
		break;
	case 10:
		days = date.day + 273;
		break;
	case 11:
		days = date.day + 304;
		break;
	case 12:
		days = date.day + 334;
		break;
	}
	if ((date.year % 4 == 0 && date.year % 100 != 0 || date.year % 400 == 0) && date.month >= 3)
		days += 1;
	printf("%d/%d is the%dth day in %d.\n", date.month, date.day, days, date.year);
	return 0;
}

运行结果：

2008年8月8日是 2008年中的第 221天。

解法二：

#include 
struct
{
	int year;
	int month;
	int day;
} date;

int main()
{
	int i, days;
	int day_tab[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	printf("input year,month,day:");
	scanf("%d,%d,%d", &date.year, &date.month, &date.day);
	days = 0;
	for (i = 1; i < date.month; i++)
		days = days + day_tab[i];
	days = days + date.day;
	if ((date.year % 4 == 0 && date.year % 100 != 0 || date.year % 400 == 0) && date.month >= 3)
		days = days + 1;
	printf("%d/%d is the %dth day in %d.\n", date.month, date.day, days, date.year);
	return 0;
}

运行结果：

题目2：写一个函数 days，实现第 1 题的计算。由主函数将年、月、日传递给 days 函数，计算后将日子数传回主函数输出。

解：

函数 days的程序结构与第 1 题基本相同。

解法一：

#include 
struct y_m_d
{
	int year;
	int month;
	int day;
} date;

int main()
{
	int days(struct y_m_d date1); //定义 date1为结构体变量，类型为 struct y_m_d
	printf("input year,month,day:");
	scanf("%d,%d,%d", &date.year, &date.month, &date.day);
	printf("%d/%d is the%dth day in %d.\n", date.month, date.day, days(date), date.year);
}

//形参 date1为struct y_m_d类型
int days(struct y_m_d date1)
{
	int sum;
	switch (date1.month)
	{
	case 1:
		sum = date1.day;
		break;
	case 2:
		sum = date1.day + 31;
		break;
	case 3:
		sum = date1.day + 59;
		break;
	case 4:
		sum = date1.day + 90;
		break;
	case 5:
		sum = date1.day + 120;
		break;
	case 6:
		sum = date1.day + 151;
		break;
	case 7:
		sum = date1.day + 181;
		break;
	case 8:
		sum = date1.day + 212;
		break;
	case 9:
		sum = date1.day + 243;
		break;
	case 10:
		sum = date1.day + 273;
		break;
	case 11:
		sum = date1.day + 304;
		break;
	case 12:
		sum = date1.day + 334;
		break;
	}
	if ((date1.year % 4 == 0 && date1.year % 100 != 0 || date1.year % 400 == 0) && date1.month >= 3)
		sum += 1;
	return (sum);
}

运行结果：

在本程序中，days 函数的参数为结构体 struct y_m_d 类型，在主函数的第 2 个 printf 语句的输出项中有一项为 days（date），调用 days 函数，实参为结构体变量 date。通过虚实结合，将实参 date 中各成员的值传递给形参 date1 中各相应成员。在 days 函数中检验其中 month 的值，根据它的值计算出天数 sum ，将 sum 的值返回主函数输出。

解法二：

#include 
struct y_m_d
{
	int year;
	int month;
	int day;
} date;

int main()
{
	int days(int year, int month, int day);
	int days(int, int, int);
	int day_sum;
	printf("input year,month,day:");
	scanf("%d,%d,%d", &date.year, &date.month, &date.day);
	day_sum = days(date.year, date.month, date.day);
	printf("%d/%d is the %dth day in %d.\n", date.month, date.day, day_sum, date.year);
	return 0;
}
int days(int year, int month, int day)
{
	int day_sum, i;
	int day_tab[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	day_sum = 0;
	for (i = 1; i < month; i++)
		day_sum += day_tab[i];
	day_sum += day;
	if ((year % 4 == 0 && year % 100 != 0 || year % 4 == 0) && month >= 3)
		day_sum += 1;
	return (day_sum);
}

运行结果：

题目3：编写一个函数 print，打印一个学生的成绩数组，该数组中有5个学生的数据记录，每个记录包括 num，name，score[3] ，用主函数输入这些记录，用 print 函数输出这些记录。

解：

答案代码：

#include 
#define N 5
struct student
{
	char num[6];
	char name[8];
	int score[4];
} stu[N];
int main()
{
	void print(struct student stu[6]);
	int i, j;
	for (i = 0; i < N; i++)
	{
		printf("\ninput score of student %d:\n", i + 1);
		printf("NO.: ");
		scanf("%s", stu[i].num);
		printf("name:");
		scanf("%s", stu[i].name);
		for (j = 0; j < 3; j++)
		{
			printf("score %d:", j + 1);
			scanf("%d", &stu[i].score[j]);
		}
		printf("\n");
	}
	print(stu);
	return 0;
}

void print(struct student stu[6])
{
	int i, j;
	printf("\n 	NO.	name	score1		score2		score3\n");
	for (i = 0; i < N; i++)
	{
		printf("%5s%10s", stu[i].num, stu[i].name);
		for (j = 0; j < 3; j++)
			printf("%9d", stu[i].score[j]);
		printf("\n");
	}
}

运行结果：

以上是输入数据。下面是输出结果：

题目4：在第 3 题的基础上，编写一个函数 input ，用来输入 5 个学生的数据记录。

解：input 函数的程序结构类似于第 3题中主函数的相应部分。

#include 
#define N 5
struct student
{
	char num[6];
	char name[8];
	int score[4];
} stu[N];

int main()
{
	void input(struct student stu[]);
	void print(struct student stu[]);
	input(stu);
	print(stu);
	return 0;
}

void input(struct student stu[])
{
	int i, j;
	for (i = 0; i < N; i++)
	{
		printf("input scores of student %d:\n", i + 1);
		printf("NO.: ");
		scanf("%s", stu[i].num);
		printf("name: ");
		scanf("%s", stu[i].name);
		for (j = 0; j < 3; j++)
		{
			printf("score %d:", j + 1);
			scanf("%d", &stu[i].score[j]);
		}
		printf("\n");
	}
}

void print(struct student stu[6])
{
	int i, j;
	printf("\n NO.	name	score1	score2	score3\n");
	for (i = 0; i < N; i++)
	{
		printf("%5s%10s", stu[i].num, stu[i].name);
		for (j = 0; j < 3; j++)
			printf("%9d", stu[i].score[j]);
		printf("\n");
	}
}

运行情况与第3题相同。

运行结果：

以上是输入数据。下面是输出结果：

题目5：有10 个学生，每个学生的数据包括学号、姓名、3 门课程的成绩，从键盘输入10 个学生数据，要求输出 3 门课程总平均成绩，以及最高分的学生的数据（包括学号、姓名、3 门课程成绩、平均分数）。

解：N-S图见图 9.1。

答案代码：

#include 
#define N 10
struct student
{
	char num[6];
	char name[8];
	float score[3];
	float avr;
} stu[N];

int main()
{
	int i, j, maxi;
	float sum, max, average;
	//输入数据
	for (i = 0; i < N; i++)
	{
		printf("input scores of student %d:\n", i + 1);
		printf("NO.:");
		scanf("%s", stu[i].num);
		printf("name ");
		scanf("%s", stu[i].name);
		for (j = 0; j < 3; j++)
		{
			printf("score %d:", j + 1);
			scanf("%f", &stu[i].score[j]);
		}
	}
	//计算
	average = 0;
	max = 0;
	maxi = 0;
	for (i = 0; i < N; i++)
	{
		sum = 0;
		for (j = 0; j < 3; j++)
			sum += stu[i].score[j]; //计算第i个学生总分
		stu[i].avr = sum / 3.0;		//计算第i个学生平均分
		average += stu[i].avr;		//找分数最高者
		if (sum > max)
		{
			max = sum;
			maxi = i; //将此学生的下标保存在 maxi
		}
	}
	average /= N; //计算总平均分数
	//输出
	printf("  NO.		name	score1	score2	score3	average\n");
	for (i = 0; i < N; i++)
	{
		printf("%5s%10s", stu[i].num, stu[i].name);
		for (j = 0; j < 3; j++)
			printf("%9.2f", stu[i].score[j]);
		printf("%8.2f\n", stu[i].avr);
	}
	printf("average=%5.2f\n", average);
	printf("The highest score is :student %s,%s\n", stu[maxi].num, stu[maxi].name);
	printf("his scores are:%6.2f,%6.2f,%6.2f,average:%5.2f.\n", stu[maxi].score[0], stu[maxi].score[1], stu[maxi].score[2], stu[maxi].avr);
	return 0;
}

变量说明：max为当前最好成绩; maxi 为当前最好成绩所对应的下标序号; sum 为第i个学生的总成绩。

运行结果：

题目6：13 个人围成一圈，从第1个人开始顺序报号 1，2，3 。凡报到 3 者退出圈子。找出最后留在圈子中的人原来的序号。要求用链表实现。

解：N-S图见图 9.2。

答案代码：

#include 
#define N 13
struct person
{
	int number;
	int nextp;
} link[N + 1];

int main()
{
	int i, count, h;
	for (i = 1; i <= N; i++)
	{
		if (i == N)
			link[i].nextp = 1;
		else
			link[i].nextp = i + 1;
		link[i].number = i;
	}
	printf("\n");
	count = 0;
	h = N;
	printf("sequence that persons leave the circle:\n");

	while (count < N - 1)
	{
		i = 0;
		while (i != 3)
		{
			h = link[h].nextp;
			if (link[h].number)
				i++;
		}
		printf("%4d", link[h].number);
		link[h].number = 0;
		count++;
	}
	printf("\nThe last one is");
	for (i = 1; i <= N; i++)
		if (link[i].number)
			printf("%3d", link[i].number);
	printf("\n");
	return 0;
}

运行结果：

题目7：在第 9 章例 9.9 和例 9.10 的基础上，写一个函数 del ，用来删除动态链表中指定的结点。

解：

题目要求对一个链表，删除其中某个结点。怎样考虑此问题的算法呢?先打个比方：一队小孩（A，B，C，D，E）手拉手，如果某一小孩（C）想离队有事，而队形仍保持不变。只要将 C 的手从两边脱开，B 改为与 D 拉手即可，见图9.3。图 9.3（a）是原来的队伍，图9.3（b）是 C 离队后的队伍。

与此相仿，从一个动态链表中删去一个结点，并不是真正从内存中把它抹掉，而是把它从链表中分离开来，只要撤销原来的链接关系即可。

如果想从已建立的动态链表中删除指定的结点，可以指定学号作为删除结点的标志。例如，输入 10103 表示要求删除学号为 10103 的结点。解题的思路是这样的：从 p 指向的第 1 个结点开始，检查该结点中的 num 的值是否等于输人的要求删除的那个学号。如果相等就将该结点删除，如不相等，就将 p 后移一个结点，再如此进行下去，直到遇到表尾为止。

可以设两个指针变量 p1 和 p2 ，先使 p1 指向第 1 个结点（图9.4（a）。如果要删除的不是第 1 个结点，则使 p1 后指向下一个结点（将 p1->next赋给 p1），在此之前应将 p1 的值赋给 p2 ，使 p2 指向刚才检查过的那个结点，见图 9.4（b）。如此一次一次地使 p 后移，直到找到所要删除的结点或检查完全部链表都找不到要删除的结点为止。如果找到某一结点是??要删除的结点，还要区分两种情况：

①要删的是第 1 个结点（p1 的值等于 head 的值，如图9.4（a）那样），则应将 p1—>next 赋给 head 。见图 9.4（c）。这时 head 指向原来的第 2 个结点。第 1 个结点虽然仍存在，但它已与链表脱离，因为链表中没有一个结点或头指针指向它。虽然 p1 还指向它，它也指向第 2 个结点，但仍无济于事，现在链表的第 1 个结点是原来的第 2 个结点，原来第 1 个结点已"丢失"，即不再是链表中的一部分了。

②如果要删除的不是第 1 个结点，则将 p1一>next 给 p2一>next，见图9.4（d）。p2一>next 原来指向 p1 指向的结点（图中第 2 个结点），现在 p2->next 改为指向 p1->next 所指向的结点（图中第 3 个结点）。p1 所指向的结点不再是链表的一部分。

还需要考虑链表是空表（无结点）和链表中找不到要删除的结点的情况。

图9.5表示解此题的算法。

删除结点的函数del 如下：

#include 
struct student
{
	long num;
	float score;
	struct student *next;
};
int n;
struct student *del(struct student *head, long num)
{
	struct student *p1, *p2;
	if (head == NULL) //是空表
	{
		printf("\nlist null!\n");
		return (head);
	}
	p1 = head;								   //使 p1指向第1个结点
	while (num != p1->num && p1->next != NULL) // p1指向的不是所要找的结点且后面还有结点
	{
		p2 = p1; // p1后移一个结点
		p1 = p1->next;
	}
	if (num == p1->num) //找到了
	{
		if (p1 == head) //若 p1 指向的是首结点，把第 2个结点地址赋予 head
			head = p1->next;
		else
			p2->next = p1->next; //否则将下一结点地址赋给前一结点地址//找不到该结点
		printf("delete:%ld\n", num);
		n = n - 1;
	}
	else
		printf("%ld not been found!\n", num);
	return (head);
}

函数的类型是指向 student 类型数据的指针，它的值是链表的头指针。函数参数为head和要删除的学号 num。head 的值可能在函数执行过程中被改变（当删除第1 个结点时）。

题目8：写一个函数 insert ，用来向一个动态链表插入结点。

解：对链表的插入是指将一个结点插入到一个已有的链表中。

若已建立了学生链表（如前面已进行的工作），结点是按其成员项 num（学号）的值由小到大顺序排列的。今要插入一个新生的结点，要求按学号的顺序插入。

为了能做到正确插入，必须解决两个问题：①怎样找到插入的位置;②怎样实现插入。

如果有一群小学生，按身高顺序（由低到高）手拉手排好队。现在来了一名新同学，要求按身高顺序插入队中。首先要确定插到什么位置。可以将新同学先与队中第 1 名小学生比身高，若新同学比第 1 名学生高，就使新同学后移一个位置，与第 2 名学生比，如果仍比第 2 名学生高，再往后移，与第 3 名学生比……直到出现比第 i 名学生高、比第 i+1名学生低的情况为止。显然，新同学的位置应该在第 i 名学生之后，在第 i+1名学生之前。在确定了位置之后，让第i名学生与第 i+1名学生的手脱开，然后让第 i 名学生的手去拉新同学的手，让新同学另外一只手去拉第 i＋1 名学生的手。这样就完成了插入，形成了新的队列。

根据这个思路来实现链表的插入操作。先用指针变量 p0 指向待插入的结点，p1 指向第 1 个结点。见图9.6（a）。将 p0->num与 p1->num 相比较，如果 p0->num>p1->num，则待插人的结点不应插在 p1 所指的结点之前。此时将 p1 后移，并使 p2 指向刚才p1 所指的结点，见图9.6（b）。再将 p1->num与 p0->num 比。如果仍然是 p0->num大，则应使 p1 继续后移，直到 p0->num≤p1->num 为止。这时将 p0 所指的结点插到 p1 所指结点之前。但是如果 p1 所指的已是表尾结点，p1 就不应后移了。如果 p0->num 比所有结点的 num 都大，则应将 p0 所指的结点插到链表末尾。

如果插入的位置既不在第 1 个结点之前，又不在表尾结点之后，则将 p0 的值赋给 p2->next，使p2->next指向待插入的结点，然后将 p1 的值赋给 p0->next，使得 p0->next 指向 p1 指向的变量。见图9.6（c），在第 1 个结点和第 2 个结点之间已插入了一个新的结点。

如果插入位置为第 1 个结点之前（即 p1 等于head 时），则将 p0 赋给 head，将 p1 赋给 p0->next 。见图9.6（d）。如果要插到表尾之后，应将 p0 赋给 p1->next，NULL 赋给p0->next，见图9.6（e）。

可以写出插入结点的函数 insert 如下。

#include 
struct student
{
	long num;
	float sore;
	struct student *next;
};
int n;

struct student *insert(struct student *head, struct student *stud)
{
	struct student *p0, *p1, *p2;
	p1 = head;		  //使p1指向第1个结点
	p0 = stud;		  //指向要插入的结点
	if (head == NULL) //原来的链表是空表
	{
		head = p0; //使 p0 指向的结点作为头结点
		p0->next = NULL;
	}
	else
	{
		while ((p0->num > p1->num) && (p1->next != NULL))
		{
			p2 = p1;	   //使 p2 指向刚才 p1 指向的结点
			p1 = p1->next; // p1后移一个结点
		}
		if (p0->num <= p1->num)
		{
			if (head == p1)
				head = p0; //插到原来第1个结点之前
			else
				p2->next = p0; //插到 p2指向的结点之后
			p0->next = p1;
		}
		else
		{
			p1->next = p0; //插到最后的结点之后
			p0->next = NULL;
		}
	}
	n = n + 1;
	return (head);
}

函数参数是 head 和 stud。stud 也是一个指针变量，将待插入结点的地址从实参传给stud。语句"p0=stud;" 的作用是使 p0 指向待插入的结点。

函数类型是指针类型，函数返回值是链表起始地址 head。

题目9：综合本章例 9.9（建立链表的函数 creat）、例 9.10（输出链表的函数 print））和本章习题第 7 题（删除链表中结点的函数dei）、第 8 题（插入结点的函数 insert），再编写一个主函数，先后调用这些函数。用以上 5个函数组成一个程序，实现链表的建立、输出、删除和插入，在主函数中指定需要删除和插入的结点的数据。

解：

写一个主函数，调用以上 4个函数 creat，print，del 和 insert。

主函数如下∶

int main()
{
	struct student creat();						  //函数声明
	struct student *del(student *, long);		  //函数声明
	struct student *insert(student *, student *); //函数声明
	void print(student *);						  //函数声明
	student *head, stu;
	long del_num;
	printf("input records:\n");
	head = creat();						   //建立链表并返回头指针
	print(head);						   //输出全部结点
	printf("input the deleted number:");   //提示输入要删除的学号
	scanf("%ld", &del_num);				   //输入要删除的学号
	head = del(head, del_num);			   //删除结点后返回链表的头地址
	print(head);						   //输出全部结点
	printf("input the inserted record:");  //提示输入要插入的结点
	scanf("%ld,%f", &stu.num, &stu.score); //输人要插入的结点的数据
	head = insert(head, &stu);			   //插入结点并返回头地址
	print(head);						   //输出全部结点
	return 0;
}

把主函数和 creat，print，del和 insert 函数再加上全局声明，组织成一个源程序如下：

#include 
#include 
#define LEN sizeof(struct student)
struct student
{
	long num;
	float score;
	struct student *next;
};
int n;

// 主函数
int main()
{
	struct student *creat();									//函数声明
	struct student *del(struct student *, long);				//函数声明
	struct student *insert(struct student *, struct student *); //函数声明
	void print(struct student *);								//函数声明
	struct student *head, stu;
	long del_num;
	printf("input records:\n");
	head = creat();						   //建立链表并返回头指针
	print(head);						   //输出全部结点
	printf("input the deleted number:");   //提示输入要删除的学号
	scanf("%ld", &del_num);				   //输入要删除的学号
	head = del(head, del_num);			   //删除结点后返回链表的头地址
	print(head);						   //输出全部结点
	printf("input the inserted record:");  //提示输入要插入的结点
	scanf("%ld,%f", &stu.num, &stu.score); //输人要插入的结点的数据
	head = insert(head, &stu);			   //插入结点并返回头地址
	print(head);						   //输出全部结点
	return 0;
}

//定义建立链表的 creat 函数
struct student *creat()
{
	struct student *head;
	struct student *p1, *p2;
	n = 0;
	p1 = p2 = (struct student *)malloc(LEN);
	scanf("%ld,%f", &p1->num, &p1->score);
	head = NULL;
	while (p1->num != 0)
	{
		n = n + 1;
		if (n == 1)
			head = p1;
		else
			p2->next = p1;
		p2 = p1;
		p1 = (struct student *)malloc(LEN);
		scanf("%ld,%f", &p1->num, &p1->score);
	}
	p2->next = NULL;
	return (head);
}

//定义删除结点的 del函数
struct student *del(struct student *head, long num)
{
	struct student *p1, *p2;
	if (head == NULL)
	{
		printf("\nlist null! \n");
		return (head);
	}
	p1 = head;
	while (num != p1->num && p1->next != NULL)
	{
		p2 = p1;
		p1 = p1->next;
	}
	if (num == p1->num)
	{
		if (p1 == head)
			head = p1->next;
		else
			p2->next = p1->next;
		printf("delete:%ld\n", num);
		n = n - 1;
	}
	else
		printf("%ld not been found! \n", num);
	return (head);
}

//定义插入结点的 insert 函数
struct student *insert(struct student *head, struct student *stud)
{
	struct student *p0, *p1, *p2;
	p1 = head;
	p0 = stud;
	if (head == NULL)
	{
		head = p0;
		p0->next = NULL;
	}
	else
	{
		while ((p0->num > p1->num) && (p1->next != NULL))
		{
			p2 = p1;
			p1 = p1->next;
		}
		if (p0->num <= p1->num)
		{
			if (head == p1)
				head = p0;
			else
				p2->next = p0;
			p0->next = p1;
		}
		else
		{
			p1->next = p0;
			p0->next = NULL;
		}
	}
	n = n + 1;
	return (head);
}

//定义输出链表的 print 函数
void print(struct student *head)
{
	struct student *p;
	printf("\nNow,These %d records are:\n", n);
	p = head;
	if (head != NULL)
		do
		{
			printf("%ld %5.1f\n", p->num, p->score);
			p = p->next;
		} while (p != NULL);
}

运行结果：

程序正常结束。

以上运行过程是这样的; 先输入3 个学生的数据，建立链表，然后程序输出链表中 3 个结点的数据。输入要删除的结点（学号为 10103），程序输出链表中还存在的两个结点的数据。再输入准备插入到链表中的学生数据，程序再输出链表中已有的3个结点的数据。

---

上面程序运行结果无疑是正确的。但是它只删除一个结点和只插入一个结点。如果想再插入一个结点，可重复程序最后 4 行，共插入两个结点。即 main 函数改写为

// 主函数
int main()
{
	struct student *creat();
	struct student *del(struct student *, long);
	struct student *insert(struct student *, struct student *);
	void print(struct student *);
	struct student *head, stu;
	long del_num;
	printf("input records:\n");
	head = creat();
	print(head);
	printf("input the deleted number:");
	scanf("%ld", &del_num);	   //输入要删除的学号
	head = del(head, del_num); //删除结点
	print(head);
	printf("input the inserted record:");
	scanf("%ld,%f", &stu.num, &stu.score); //输入要插入的结点的数据
	head = insert(head, &stu);			   //插入结点
	print(head);						   //输出全部结点
	printf("input the inserted record:");
	scanf("%ld,%f", &stu.num, &stu.score); //再输入要插入的结点的数据
	head = insert(head, &stu);			   //插入结点
	print(head);
	return 0;
}

运行结果却是错误的。

运行结果：

无终止地输出 10104 的结点数据。?从运行记录可以看到：第1 次删除结点和插入结点都正常，在插入第 2 个结点时就不正常了，一直输出准备插入的结点数据。请读者将 main 与insert 函数结合起来考察为什么会产生以上运行结果。

出现以上结果的原因是：stu 是一个有固定地址的结构体变量。第 1 次把 stu 结点插入到链表中。第 2 次若再用它来插入第 2 个结点，就把第1次结点的数据冲掉了。实际上并没有开辟两个结点。读者可根据 insert 函数画出此时链表的情况。为了解决这个问题，必须在每插入一个结点时新开辟一个内存区。修改 main 函数，使之能删除多个结点（直到输入要删除的学号为 0 ），能插入多个结点（直到输入要插入的学号为 0 ）。

修改后的整个程序如下∶

#include 
#include 
#define LEN sizeof(struct student)
struct student
{
	long num;
	float score;
	struct student *next;
};
int n;

int main()
{
	struct student *creat();									//函数声明
	struct student *del(struct student *, long);				//函数声明
	struct student *insert(struct student *, struct student *); //函数声明
	void print(struct student *);								//函数声明
	struct student *head, *stu;
	long del_num;
	printf("input records:\n");			   //提示输入
	head = creat();						   //建立链表，返回头指针
	print(head);						   //输出全部结点
	printf("\ninput the deleted number:"); //提示用户输入要删除的结点
	scanf("%ld", &del_num);				   //输入要删除的学号
	while (del_num != 0)				   //当输入的学号为0时结束循环
	{
		head = del(head, del_num);			 //删除结点后返回链表的头地址
		print(head);						 //输出全部结点
		printf("input the deleted number:"); //提示用户输入要删除的结点
		scanf("%ld", &del_num);				 //输入要删除的学号
	}
	printf("\ninput the inserted record:");	 //提示输入要插入的结点
	stu = (struct student *)malloc(LEN);	 //开辟一个新结点
	scanf("%ld,%f", &stu->num, &stu->score); //输人要插入的结点
	while (stu->num != 0)					 //当输入的学号为0 时结束循环
	{
		head = insert(head, stu);				 //返回链表的头地址，赋给 head
		print(head);							 //输出全部结点
		printf("input the inserted record:");	 //请用户输入要插入的结点
		stu = (struct student *)malloc(LEN);	 //开辟一个新结点
		scanf("%ld,%f", &stu->num, &stu->score); //输人插入结点的数据
	}
	return 0;
}

//建立链表的函数
struct student *creat()
{
	struct student *head;
	struct student *p1, *p2;
	n = 0;
	p1 = p2 = (struct student *)malloc(LEN); //开辟一个新单元，并使 p1，p2指向它
	scanf("%ld,%f", &p1->num, &p1->score);
	head = NULL;
	while (p1->num != 0)
	{
		n = n + 1;
		if (n == 1)
			head = p1;
		else
			p2->next = p1;
		p2 = p1;
		p1 = (struct student *)malloc(LEN);
		scanf("%ld,%f", &p1->num, &p1->score);
	}
	p2->next = NULL;
	return (head);
}

//删除结点的函数
struct student *del(struct student *head, long num)
{
	struct student *p1, *p2; //若是空表
	if (head == NULL)
	{
		printf("\nlist null! \n");
		return (head);
	}
	p1 = head;								   //使 p1 指向第1个结点
	while (num != p1->num && p1->next != NULL) // pl指向的不是所要找的结点且后面还有结点
	{
		p2 = p1; // p1 后移一个结点
		p1 = p1->next;
	}
	if (num == p1->num) //找到了
	{
		if (p1 == head) //若 p1指向的是首结点，把第2个结点地址赋予head
			head = p1->next;
		else //否则将下一结点地址赋给前一结点地址
			p2->next = p1->next;
		printf("delete:%ld\n", num);
		n = n - 1;
	}
	else
		printf("%ld not been found! \n", num); //找不到该结点
	return (head);
}

//插入结点的函数
struct student *insert(struct student *head, struct student *stud)
{
	struct student *p0, *p1, *p2;
	p1 = head;		  //使 p1 指向第1个结点
	p0 = stud;		  //指向要插入的结点
	if (head == NULL) //原来的链表是空表
	{
		head = p0; //使 p0指向的结点作为头结点
		p0->next = NULL;
	}
	else
	{
		while ((p0->num > p1->num) && (p1->next != NULL))
		{
			p2 = p1;	   //使 p2指向刚才p1指向的结点
			p1 = p1->next; // p1后移一个结点
		}
		if (p0->num <= p1->num)
		{
			if (head == p1) //插到原来第1个结点之前
				head = p0;
			else //插到 p2 指向的结点之后
				p2->next = p0;
			p0->next = p1;
		}
		else
		{
			p1->next = p0;
			p0->next = NULL; //插到最后的结点之后
		}
	}
	n = n + 1; //结点数加1
	return (head);
}

//输出链表的函数
void print(struct student *head)
{
	struct student *p;
	printf("\nNow,These %d records are:\n", n);
	p = head;
	if (head != NULL)
		do
		{
			printf("%ld %5.1f\n", p->num, p->score);
			p = p->next;
		} while (p != NULL);
}

定义 stu 为指针变量，在需要插入时先用 new 开辟一个内存区，将其起始地址赋给 stu ，然后输入此结构体变量中各成员的值。对不同的插入对象，stu 的值是不同的，每次指向一个新的 student 变量。在调用 insert 函数时，实参为 head 和 stu ，将已有的链表起始地址传给 insert 函数的形参 head，将新开辟的单元的地址 stu 传给形参 stud，返回的函数值是经过插入之后的链表的头指针（地址）。

运行结果：

请读者仔细消化这个程序。这个程序只是初步的，用来实现基本的功能，读者可以在此基础上进一步完善和丰富它。

题目10：已有a，b两个链表，每个链表中的结点包括学号、成绩。要求把两个链表合并，按学号升序排列。

解：

答案代码：

#include 
#include 
#define LEN sizeof(struct student)
struct student
{
	long num;
	int score;
	struct student *next;
};
struct student lista, listb;
int n, sum = 0;

int main()
{
	struct student *creat(void);								//函数声明
	struct student *insert(struct student *, struct student *); ///函数声明
	void print(struct student *);								//函数声明
	struct student *ahead, *bhead, *abh;
	printf("input list a:\n");
	ahead = creat(); //调用 creat 函数建立表 A，返回头地址
	sum = sum + n;
	printf("input list b:\n");
	bhead = creat(); //调用 creat 函数建立表 B，返回头地址
	sum = sum + n;
	abh = insert(ahead, bhead); //调用 insert 函数，将两表合并
	print(abh);					// 输出合并后的链表
	return 0;
}

//建立链表的函数
struct student *creat(void)
{
	struct student *p1, *p2, *head;
	n = 0;
	p1 = p2 = (struct student *)malloc(LEN);
	printf("input number &. scores of student:\n");
	printf("if number is O,stop inputing.\n");
	scanf("%ld,%d", &p1->num, &p1->score);
	head = NULL;
	while (p1->num != 0)
	{
		n = n + 1;
		if (n == 1)
			head = p1;
		else
			p2->next = p1;
		p2 = p1;
		p1 = (struct student *)malloc(LEN);
		scanf("%ld,%d", &p1->num, &p1->score);
	}
	p2->next = NULL;
	return (head);
}

//定义 insert 函数，用来合并两个链表
struct student *insert(struct student *ah, struct student *bh)
{
	struct student *pa1, *pa2, *pb1, *pb2;
	pa2 = pa1 = ah;
	pb2 = pb1 = bh;
	do
	{
		while ((pb1->num > pa1->num) && (pa1->next != NULL))
		{
			pa2 = pa1;
			pa1 = pa1->next;
		}
		if (pb1->num <= pa1->num)
		{
			if (ah == pa1)
				ah = pb1;
			else
				pa2->next = pb1;
			pb1 = pb1->next;
			pb2->next = pa1;
			pa2 = pb2;
			pb2 = pb1;
		}
	} while ((pa1->next != NULL) || (pa1 == NULL && pb1 != NULL));
	if ((pb1 != NULL) && (pb1->num > pa1->num) && (pa1->next == NULL))
		pa1->next = pb1;
	return (ah);
}

//输出函数
void print(struct student *head)
{
	struct student *p;
	printf("There are %d records:\n", sum);
	p = head;
	if (p != NULL)
		do
		{
			printf("%ld %d\n", p->num, p->score);
			p = p->next;
		} while (p != NULL);
}

运行结果：

程序提示：输入 a 链表中的结点数据，包括学生的学号和成绩，如果输入的学号为 0 ，就表示输入结束。向 a 链表输入 4 个学生的数据，向 b 链表输入 3 个学生的数据。程序把两个链表合并，按学号从小到大排列。最后输出合并后链表的数据。

请读者仔细分析和理解程序的思路和算法。

题目11：有两个链表 a 和 b，设结点中包含学号、姓名。从 a链表中删去与b链表中有相同学号的那些结点。

解：删除操作的N-S图如图9.7所示。

为减少程序运行时的输人量，先设两个结构体数组 a 和 b，并使用初始化的方法使之得到数据。建立链表时就利用这两个数组中的元素作为结点。

程序如下：

#include 
#include 
#define LA 4
#define LB 5
struct student
{
	int num;
	char name[8];
	struct student *next;
} a[LA], b[LB];

int main()
{
	struct student a[LA] = {{101, "Wang"}, {102, "Li"}, {105, "Zhang"}, {106, "Wei"}};
	struct student b[LB] = {{103, "Zhang"}, {104, "Ma"}, {105, "Chen"}, {107, "Guo"}, {108, "Liu"}};
	int i;
	struct student *p, *p1, *p2, *head1, *head2;
	head1 = a;
	head2 = b;
	printf("list A:\n");
	for (p1 = head1, i = 1; i <= LA; i++)
	{
		if (i < LA)
			p1->next = a + i;
		else
			p1->next = NULL;				   //这是最后一个结点
		printf("%4d%8s\n", p1->num, p1->name); //输出一个结点的数据
		if (i < LA)
			p1 = p1->next; //如果不是最后一个结点，使 p1指向下一个结点
	}
	printf("\n list B:\n");
	for (p2 = head2, i = 1; i <= LB; i++)
	{
		if (i < LB)
			p2->next = b + i;
		else
			p2->next = NULL;
		printf("%4d%8s\n", p2->num, p2->name);
		if (i < LB)
			p2 = p2->next;
	}
	//对 a链表进行删除操作
	p1 = head1;
	while (p1 != NULL)
	{
		p2 = head2;
		while ((p1->num != p2->num) && (p2->next != NULL))
			p2 = p2->next;		//使 p2 后移直到发现与a链表中当前的结点的学号相同或已到b链表中最后一个结点
		if (p1->num == p2->num) //两个链表中的学号相同
		{
			if (p1 == head1)	  // a 链表中当前结点为第1个结点
				head1 = p1->next; //使 head1指向 a链表中第2个结点
			else				  //如果不是第1个结点
			{
				p->next = p1->next; //使p->next指向 pl的下一个结点，即删去 p1当前指向的结点
				p1 = p1->next;		// pl指向 pl的下一个结点；言了
			}
		}
		else // b链表中没有与a链表中当前结点相同的学号
		{
			p = p1; // p1 指向 a 链表中的下一个结点
			p1 = p1->next;
		}
	}
	//输出已处理过的 a链表中全部结点的数据
	printf("\nresult:\n");
	p1 = head1;
	while (p1 != NULL)
	{
		printf("%4d %7s \n", p1->num, p1->name);
		p1 = p1->next;
	}
	return 0;
}

运行结果：

题目12：建立一个链表，每个结点包括∶学号、姓名、性别、年龄。输入一个年龄，如果链表中的结点所包含的年龄等于此年龄，则将此结点删去。

解：N-S图如图9.8所示。

程序如下：

#include 
#include 
#define LEN sizeof(struct student)
struct student
{
	char num[6];
	char name[8];
	char sex[2];
	int age;
	struct student *next;
} stu[10];

int main()
{
	struct student *p, *pt, *head;
	int i, length, iage, flag = 1;
	int find = 0; //找到待删除元素 find=1，否则 find=0
	while (flag == 1)
	{
		printf("input length of list(<10):");
		scanf("%d", &length);
		if (length < 10)
			flag = 0;
	}
	//建立链表
	for (i = 0; i < length; i++)
	{
		p = (struct student *)malloc(LEN);
		if (i == 0)
			head = pt = p;
		else
			pt->next = p;
		pt = p;
		printf("NO.:");
		scanf("%s", p->num);
		printf("name:");
		scanf("%s", p->name);
		printf("sex:");
		scanf("%s", p->sex);
		printf("age:");
		scanf("%d", &p->age);
	}
	p->next = NULL;
	p = head;
	printf("\n NO. name sex age\n"); /*显示*/
	while (p != NULL)
	{
		printf("%4s%8s%6s%6d\n", p->num, p->name, p->sex, p->age);
		p = p->next;
	}
	//删除结点
	printf("input age:"); //输入待删年龄
	scanf("%d", &iage);
	pt = head;
	p = pt;
	if (pt->age == iage) //链头是待删元素
	{
		p = pt->next;
		head = pt = p;
		find = 1;
	}
	else //链头不是待删元素
		pt = pt->next;
	while (pt != NULL)
	{
		if (pt->age == iage)
		{
			p->next = pt->next;
			find = 1;
		}
		else //中间结点不是待删元素
			p = pt;
		pt = pt->next;
	}
	if (!find)
		printf("not found %d.", iage);
	p = head;
	printf("\n NO.name sex age\n"); //显示结果
	while (p != NULL)
	{
		printf("%4s%8s", p->num, p->name);
		printf("%6s%6d\n", p->sex, p->age);
		p = p->next;
	}
	return 0;
}

运行结果：

程序运行开始后，提示用户输入链表的长度（要求小于10）。用户输入 4 ，并输入 4 个学生的学号、姓名、年龄。程序输出已有结点的数据，用户要删除年龄为 19 的学生结点，最后只剩下两个结点。