共计 20386 个字符,预计需要花费 51 分钟才能阅读完成。
你也能够上程序咖 (https://meta.chengxuka.com),关上大学幕题板块,岂但有答案,解说,还能够在线答题。
题目 1:定义一个构造体变量(包含年、月、日)。计算该日在本年中是第几天,留神平年问题。
解:
解题思路为:失常年份每个月中的天数是已知的,只有给出日期,算出该日在本年中是第几天是不艰难的。如果是平年且月份在 3 月或 3 月当前时,应再减少 1 天。平年的规定是:年份能被 4 或 400 整除但不能被 100 整除,例如,2000 年是平年,2100 年不是平年。
解法一:
#include <stdio.h>
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 <stdio.h>
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 <stdio.h>
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 <stdio.h>
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 <stdio.h>
#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 <stdio.h>
#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 <stdio.h>
#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 <stdio.h>
#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 <stdio.h>
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 <stdio.h>
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 <stdio.h>
#include <malloc.h>
#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 <stdio.h>
#include <malloc.h>
#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 <stdio.h>
#include <malloc.h>
#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 <stdio.h>
#include <string.h>
#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 <stdio.h>
#include <malloc.h>
#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 的学生结点,最初只剩下两个结点。