你也可以上程序咖(https://meta.chengxuka.com)悲酷，打開大學(xué)幕題板塊夺荒，不但有答案账蓉，講解籍茧，還可以在線答題。
題目1：定義一個結(jié)構(gòu)體變量（包括年户侥、月镀琉、日）峦嗤。計算該日在本年中是第幾天蕊唐，注意閏年問題。
解：
解題思路為：正常年份每個月中的天數(shù)是已知的烁设，只要給出日期替梨，算出該日在本年中是第幾天是不困難的。如果是閏年且月份在 3 月或 3 月以后時装黑，應(yīng)再增加 1 天副瀑。閏年的規(guī)則是：年份能被 4 或 400 整除但不能被 100 整除，例如，2000 年是閏年，2100 年不是閏年羊精。
解法一：
#include <stdio.h>
struct
{
int year;
int month;
int day;
} date; //結(jié)構(gòu)體變量 date中的成員對應(yīng)于年盹沈、月、日
int main()
{
int days; // days 為天數(shù)
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;
}
運行結(jié)果：
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;
}
運行結(jié)果：
題目2：寫一個函數(shù) days，實現(xiàn)第 1 題的計算。由主函數(shù)將年均抽、月、日傳遞給 days 函數(shù)其掂，計算后將日子數(shù)傳回主函數(shù)輸出油挥。
解：
函數(shù) days的程序結(jié)構(gòu)與第 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為結(jié)構(gòu)體變量款熬，類型為 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);
}
運行結(jié)果：
在本程序中深寥，days 函數(shù)的參數(shù)為結(jié)構(gòu)體 struct y_m_d 類型，在主函數(shù)的第 2 個 printf 語句的輸出項中有一項為 days（date）贤牛，調(diào)用 days 函數(shù)惋鹅，實參為結(jié)構(gòu)體變量 date。通過虛實結(jié)合盔夜，將實參 date 中各成員的值傳遞給形參 date1 中各相應(yīng)成員负饲。在 days 函數(shù)中檢驗其中 month 的值堤魁，根據(jù)它的值計算出天數(shù) sum ，將 sum 的值返回主函數(shù)輸出返十。
解法二：
#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);
}
運行結(jié)果：
題目3：編寫一個函數(shù) print妥泉，打印一個學(xué)生的成績數(shù)組，該數(shù)組中有5個學(xué)生的數(shù)據(jù)記錄洞坑，每個記錄包括 num盲链，name，score[3] 迟杂，用主函數(shù)輸入這些記錄刽沾，用 print 函數(shù)輸出這些記錄。
解：
答案代碼：
#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");
}
}
運行結(jié)果：
以上是輸入數(shù)據(jù)排拷。下面是輸出結(jié)果：
題目4：在第 3 題的基礎(chǔ)上侧漓，編寫一個函數(shù) input ，用來輸入 5 個學(xué)生的數(shù)據(jù)記錄监氢。
解：input 函數(shù)的程序結(jié)構(gòu)類似于第 3題中主函數(shù)的相應(yīng)部分布蔗。
#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題相同。
運行結(jié)果：
以上是輸入數(shù)據(jù)浪腐。下面是輸出結(jié)果：
題目5：有10 個學(xué)生纵揍，每個學(xué)生的數(shù)據(jù)包括學(xué)號、姓名议街、3 門課程的成績泽谨，從鍵盤輸入10 個學(xué)生數(shù)據(jù)，要求輸出 3 門課程總平均成績特漩，以及最高分的學(xué)生的數(shù)據(jù)（包括學(xué)號吧雹、姓名、3 門課程成績拾稳、平均分?jǐn)?shù)）吮炕。
解：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;
//輸入數(shù)據(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("%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個學(xué)生總分
stu[i].avr = sum / 3.0; //計算第i個學(xué)生平均分
average += stu[i].avr; //找分?jǐn)?shù)最高者
if (sum > max)
{
max = sum;
maxi = i; //將此學(xué)生的下標(biāo)保存在 maxi
}
}
average /= N; //計算總平均分?jǐn)?shù)
//輸出
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為當(dāng)前最好成績; maxi 為當(dāng)前最好成績所對應(yīng)的下標(biāo)序號; sum 為第i個學(xué)生的總成績访得。
運行結(jié)果：
題目6：13 個人圍成一圈龙亲，從第1個人開始順序報號 1，2悍抑，3 鳄炉。凡報到 3 者退出圈子。找出最后留在圈子中的人原來的序號搜骡。要求用鏈表實現(xiàn)拂盯。
解：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;
}
運行結(jié)果：
題目7：在第 9 章例 9.9 和例 9.10 的基礎(chǔ)上记靡，寫一個函數(shù) del 谈竿，用來刪除動態(tài)鏈表中指定的結(jié)點团驱。
解：
題目要求對一個鏈表，刪除其中某個結(jié)點空凸。怎樣考慮此問題的算法呢?先打個比方：一隊小孩（A嚎花，B，C呀洲，D紊选，E）手拉手，如果某一小孩（C）想離隊有事道逗，而隊形仍保持不變兵罢。只要將 C 的手從兩邊脫開，B 改為與 D 拉手即可滓窍，見圖9.3卖词。圖 9.3（a）是原來的隊伍，圖9.3（b）是 C 離隊后的隊伍贰您。
與此相仿坏平，從一個動態(tài)鏈表中刪去一個結(jié)點，并不是真正從內(nèi)存中把它抹掉锦亦，而是把它從鏈表中分離開來，只要撤銷原來的鏈接關(guān)系即可令境。
如果想從已建立的動態(tài)鏈表中刪除指定的結(jié)點杠园，可以指定學(xué)號作為刪除結(jié)點的標(biāo)志。例如舔庶，輸入 10103 表示要求刪除學(xué)號為 10103 的結(jié)點抛蚁。解題的思路是這樣的：從 p 指向的第 1 個結(jié)點開始，檢查該結(jié)點中的 num 的值是否等于輸人的要求刪除的那個學(xué)號惕橙。如果相等就將該結(jié)點刪除瞧甩，如不相等，就將 p 后移一個結(jié)點弥鹦，再如此進(jìn)行下去肚逸，直到遇到表尾為止。
可以設(shè)兩個指針變量 p1 和 p2 彬坏，先使 p1 指向第 1 個結(jié)點（圖9.4（a）朦促。如果要刪除的不是第 1 個結(jié)點，則使 p1 后指向下一個結(jié)點（將 p1->next賦給 p1）栓始，在此之前應(yīng)將 p1 的值賦給 p2 务冕，使 p2 指向剛才檢查過的那個結(jié)點，見圖 9.4（b）幻赚。如此一次一次地使 p 后移禀忆，直到找到所要刪除的結(jié)點或檢查完全部鏈表都找不到要刪除的結(jié)點為止臊旭。如果找到某一結(jié)點是要刪除的結(jié)點，還要區(qū)分兩種情況：
①要刪的是第 1 個結(jié)點（p1 的值等于 head 的值箩退，如圖9.4（a）那樣）巍扛，則應(yīng)將 p1—>next 賦給 head 。見圖 9.4（c）乏德。這時 head 指向原來的第 2 個結(jié)點撤奸。第 1 個結(jié)點雖然仍存在，但它已與鏈表脫離喊括，因為鏈表中沒有一個結(jié)點或頭指針指向它胧瓜。雖然 p1 還指向它，它也指向第 2 個結(jié)點郑什，但仍無濟(jì)于事府喳，現(xiàn)在鏈表的第 1 個結(jié)點是原來的第 2 個結(jié)點，原來第 1 個結(jié)點已"丟失"蘑拯，即不再是鏈表中的一部分了钝满。
②如果要刪除的不是第 1 個結(jié)點，則將 p1一>next 給 p2一>next申窘，見圖9.4（d）弯蚜。p2一>next 原來指向 p1 指向的結(jié)點（圖中第 2 個結(jié)點），現(xiàn)在 p2->next 改為指向 p1->next 所指向的結(jié)點（圖中第 3 個結(jié)點）剃法。p1 所指向的結(jié)點不再是鏈表的一部分碎捺。
還需要考慮鏈表是空表（無結(jié)點）和鏈表中找不到要刪除的結(jié)點的情況。
圖9.5表示解此題的算法贷洲。
刪除結(jié)點的函數(shù)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個結(jié)點
while (num != p1->num && p1->next != NULL) // p1指向的不是所要找的結(jié)點且后面還有結(jié)點
{
p2 = p1; // p1后移一個結(jié)點
p1 = p1->next;
}
if (num == p1->num) //找到了
{
if (p1 == head) //若 p1 指向的是首結(jié)點收厨，把第 2個結(jié)點地址賦予 head
head = p1->next;
else
p2->next = p1->next; //否則將下一結(jié)點地址賦給前一結(jié)點地址//找不到該結(jié)點
printf("delete:%ld\n", num);
n = n - 1;
}
else
printf("%ld not been found!\n", num);
return (head);
}
函數(shù)的類型是指向 student 類型數(shù)據(jù)的指針，它的值是鏈表的頭指針优构。函數(shù)參數(shù)為head和要刪除的學(xué)號 num诵叁。head 的值可能在函數(shù)執(zhí)行過程中被改變（當(dāng)刪除第1 個結(jié)點時）。
題目8：寫一個函數(shù) insert 钦椭，用來向一個動態(tài)鏈表插入結(jié)點拧额。
解：對鏈表的插入是指將一個結(jié)點插入到一個已有的鏈表中。
若已建立了學(xué)生鏈表（如前面已進(jìn)行的工作）玉凯，結(jié)點是按其成員項 num（學(xué)號）的值由小到大順序排列的势腮。今要插入一個新生的結(jié)點，要求按學(xué)號的順序插入漫仆。
為了能做到正確插入捎拯，必須解決兩個問題：①怎樣找到插入的位置;②怎樣實現(xiàn)插入。
如果有一群小學(xué)生，按身高順序（由低到高）手拉手排好隊∈鹫眨現(xiàn)在來了一名新同學(xué)祸泪，要求按身高順序插入隊中。首先要確定插到什么位置建芙∶话可以將新同學(xué)先與隊中第 1 名小學(xué)生比身高，若新同學(xué)比第 1 名學(xué)生高禁荸，就使新同學(xué)后移一個位置右蒲，與第 2 名學(xué)生比，如果仍比第 2 名學(xué)生高赶熟，再往后移瑰妄，與第 3 名學(xué)生比……直到出現(xiàn)比第 i 名學(xué)生高、比第 i+1名學(xué)生低的情況為止映砖。顯然间坐，新同學(xué)的位置應(yīng)該在第 i 名學(xué)生之后，在第 i+1名學(xué)生之前邑退。在確定了位置之后竹宋，讓第i名學(xué)生與第 i+1名學(xué)生的手脫開，然后讓第 i 名學(xué)生的手去拉新同學(xué)的手地技，讓新同學(xué)另外一只手去拉第 i＋1 名學(xué)生的手蜈七。這樣就完成了插入，形成了新的隊列乓土。
根據(jù)這個思路來實現(xiàn)鏈表的插入操作宪潮。先用指針變量 p0 指向待插入的結(jié)點，p1 指向第 1 個結(jié)點趣苏。見圖9.6（a）。將 p0->num與 p1->num 相比較梯轻，如果 p0->num>p1->num食磕，則待插人的結(jié)點不應(yīng)插在 p1 所指的結(jié)點之前。此時將 p1 后移喳挑，并使 p2 指向剛才p1 所指的結(jié)點彬伦，見圖9.6（b）。再將 p1->num與 p0->num 比伊诵。如果仍然是 p0->num大单绑，則應(yīng)使 p1 繼續(xù)后移，直到 p0->num≤p1->num 為止曹宴。這時將 p0 所指的結(jié)點插到 p1 所指結(jié)點之前搂橙。但是如果 p1 所指的已是表尾結(jié)點，p1 就不應(yīng)后移了笛坦。如果 p0->num 比所有結(jié)點的 num 都大区转，則應(yīng)將 p0 所指的結(jié)點插到鏈表末尾苔巨。
如果插入的位置既不在第 1 個結(jié)點之前，又不在表尾結(jié)點之后废离，則將 p0 的值賦給 p2->next侄泽，使p2->next指向待插入的結(jié)點，然后將 p1 的值賦給 p0->next蜻韭，使得 p0->next 指向 p1 指向的變量悼尾。見圖9.6（c），在第 1 個結(jié)點和第 2 個結(jié)點之間已插入了一個新的結(jié)點肖方。
如果插入位置為第 1 個結(jié)點之前（即 p1 等于head 時）闺魏，則將 p0 賦給 head，將 p1 賦給 p0->next 窥妇。見圖9.6（d）舷胜。如果要插到表尾之后，應(yīng)將 p0 賦給 p1->next活翩，NULL 賦給p0->next烹骨，見圖9.6（e）。
可以寫出插入結(jié)點的函數(shù) 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個結(jié)點
p0 = stud; //指向要插入的結(jié)點
if (head == NULL) //原來的鏈表是空表
{
head = p0; //使 p0 指向的結(jié)點作為頭結(jié)點
p0->next = NULL;
}
else
{
while ((p0->num > p1->num) && (p1->next != NULL))
{
p2 = p1; //使 p2 指向剛才 p1 指向的結(jié)點
p1 = p1->next; // p1后移一個結(jié)點
}
if (p0->num <= p1->num)
{
if (head == p1)
head = p0; //插到原來第1個結(jié)點之前
else
p2->next = p0; //插到 p2指向的結(jié)點之后
p0->next = p1;
}
else
{
p1->next = p0; //插到最后的結(jié)點之后
p0->next = NULL;
}
}
n = n + 1;
return (head);
}
函數(shù)參數(shù)是 head 和 stud沮焕。stud 也是一個指針變量，將待插入結(jié)點的地址從實參傳給stud拉宗。語句"p0=stud;" 的作用是使 p0 指向待插入的結(jié)點峦树。
函數(shù)類型是指針類型，函數(shù)返回值是鏈表起始地址 head旦事。
題目9：綜合本章例 9.9（建立鏈表的函數(shù) creat）魁巩、例 9.10（輸出鏈表的函數(shù) print））和本章習(xí)題第 7 題（刪除鏈表中結(jié)點的函數(shù)dei）、第 8 題（插入結(jié)點的函數(shù) insert）姐浮，再編寫一個主函數(shù)谷遂，先后調(diào)用這些函數(shù)。用以上 5個函數(shù)組成一個程序卖鲤，實現(xiàn)鏈表的建立肾扰、輸出、刪除和插入蛋逾，在主函數(shù)中指定需要刪除和插入的結(jié)點的數(shù)據(jù)集晚。
解：
寫一個主函數(shù)，調(diào)用以上 4個函數(shù) creat区匣，print偷拔，del 和 insert。
主函數(shù)如下∶
int main()
{
struct student creat(); //函數(shù)聲明
struct student *del(student *, long); //函數(shù)聲明
struct student *insert(student *, student *); //函數(shù)聲明
void print(student *); //函數(shù)聲明
student *head, stu;
long del_num;
printf("input records:\n");
head = creat(); //建立鏈表并返回頭指針
print(head); //輸出全部結(jié)點
printf("input the deleted number:"); //提示輸入要刪除的學(xué)號
scanf("%ld", &del_num); //輸入要刪除的學(xué)號
head = del(head, del_num); //刪除結(jié)點后返回鏈表的頭地址
print(head); //輸出全部結(jié)點
printf("input the inserted record:"); //提示輸入要插入的結(jié)點
scanf("%ld,%f", &stu.num, &stu.score); //輸人要插入的結(jié)點的數(shù)據(jù)
head = insert(head, &stu); //插入結(jié)點并返回頭地址
print(head); //輸出全部結(jié)點
return 0;
}
把主函數(shù)和 creat，print条摸，del和 insert 函數(shù)再加上全局聲明悦污，組織成一個源程序如下：
#include <stdio.h>
#include <malloc.h>
#define LEN sizeof(struct student)
struct student
{
long num;
float score;
struct student *next;
};
int n;
// 主函數(shù)
int main()
{
struct student *creat(); //函數(shù)聲明
struct student *del(struct student *, long); //函數(shù)聲明
struct student *insert(struct student *, struct student *); //函數(shù)聲明
void print(struct student *); //函數(shù)聲明
struct student *head, stu;
long del_num;
printf("input records:\n");
head = creat(); //建立鏈表并返回頭指針
print(head); //輸出全部結(jié)點
printf("input the deleted number:"); //提示輸入要刪除的學(xué)號
scanf("%ld", &del_num); //輸入要刪除的學(xué)號
head = del(head, del_num); //刪除結(jié)點后返回鏈表的頭地址
print(head); //輸出全部結(jié)點
printf("input the inserted record:"); //提示輸入要插入的結(jié)點
scanf("%ld,%f", &stu.num, &stu.score); //輸人要插入的結(jié)點的數(shù)據(jù)
head = insert(head, &stu); //插入結(jié)點并返回頭地址
print(head); //輸出全部結(jié)點
return 0;
}
//定義建立鏈表的 creat 函數(shù)
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);
}
//定義刪除結(jié)點的 del函數(shù)
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);
}
//定義插入結(jié)點的 insert 函數(shù)
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 函數(shù)
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);
}
運行結(jié)果：
程序正常結(jié)束。
以上運行過程是這樣的; 先輸入3 個學(xué)生的數(shù)據(jù)钉蒲，建立鏈表切端，然后程序輸出鏈表中 3 個結(jié)點的數(shù)據(jù)。輸入要刪除的結(jié)點（學(xué)號為 10103）顷啼，程序輸出鏈表中還存在的兩個結(jié)點的數(shù)據(jù)踏枣。再輸入準(zhǔn)備插入到鏈表中的學(xué)生數(shù)據(jù)，程序再輸出鏈表中已有的3個結(jié)點的數(shù)據(jù)钙蒙。
上面程序運行結(jié)果無疑是正確的茵瀑。但是它只刪除一個結(jié)點和只插入一個結(jié)點。如果想再插入一個結(jié)點躬厌，可重復(fù)程序最后 4 行马昨，共插入兩個結(jié)點。即 main 函數(shù)改寫為
// 主函數(shù)
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); //輸入要刪除的學(xué)號
head = del(head, del_num); //刪除結(jié)點
print(head);
printf("input the inserted record:");
scanf("%ld,%f", &stu.num, &stu.score); //輸入要插入的結(jié)點的數(shù)據(jù)
head = insert(head, &stu); //插入結(jié)點
print(head); //輸出全部結(jié)點
printf("input the inserted record:");
scanf("%ld,%f", &stu.num, &stu.score); //再輸入要插入的結(jié)點的數(shù)據(jù)
head = insert(head, &stu); //插入結(jié)點
print(head);
return 0;
}
運行結(jié)果卻是錯誤的扛施。
運行結(jié)果：
無終止地輸出 10104 的結(jié)點數(shù)據(jù)鸿捧。從運行記錄可以看到：第1 次刪除結(jié)點和插入結(jié)點都正常，在插入第 2 個結(jié)點時就不正常了疙渣，一直輸出準(zhǔn)備插入的結(jié)點數(shù)據(jù)匙奴。請讀者將 main 與insert 函數(shù)結(jié)合起來考察為什么會產(chǎn)生以上運行結(jié)果。
出現(xiàn)以上結(jié)果的原因是：stu 是一個有固定地址的結(jié)構(gòu)體變量妄荔。第 1 次把 stu 結(jié)點插入到鏈表中泼菌。第 2 次若再用它來插入第 2 個結(jié)點，就把第1次結(jié)點的數(shù)據(jù)沖掉了啦租。實際上并沒有開辟兩個結(jié)點哗伯。讀者可根據(jù) insert 函數(shù)畫出此時鏈表的情況。為了解決這個問題篷角，必須在每插入一個結(jié)點時新開辟一個內(nèi)存區(qū)笋颤。修改 main 函數(shù)，使之能刪除多個結(jié)點（直到輸入要刪除的學(xué)號為 0 ）内地，能插入多個結(jié)點（直到輸入要插入的學(xué)號為 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(); //函數(shù)聲明
struct student *del(struct student *, long); //函數(shù)聲明
struct student *insert(struct student *, struct student *); //函數(shù)聲明
void print(struct student *); //函數(shù)聲明
struct student *head, *stu;
long del_num;
printf("input records:\n"); //提示輸入
head = creat(); //建立鏈表赋除，返回頭指針
print(head); //輸出全部結(jié)點
printf("\ninput the deleted number:"); //提示用戶輸入要刪除的結(jié)點
scanf("%ld", &del_num); //輸入要刪除的學(xué)號
while (del_num != 0) //當(dāng)輸入的學(xué)號為0時結(jié)束循環(huán)
{
head = del(head, del_num); //刪除結(jié)點后返回鏈表的頭地址
print(head); //輸出全部結(jié)點
printf("input the deleted number:"); //提示用戶輸入要刪除的結(jié)點
scanf("%ld", &del_num); //輸入要刪除的學(xué)號
}
printf("\ninput the inserted record:"); //提示輸入要插入的結(jié)點
stu = (struct student *)malloc(LEN); //開辟一個新結(jié)點
scanf("%ld,%f", &stu->num, &stu->score); //輸人要插入的結(jié)點
while (stu->num != 0) //當(dāng)輸入的學(xué)號為0 時結(jié)束循環(huán)
{
head = insert(head, stu); //返回鏈表的頭地址阱缓，賦給 head
print(head); //輸出全部結(jié)點
printf("input the inserted record:"); //請用戶輸入要插入的結(jié)點
stu = (struct student *)malloc(LEN); //開辟一個新結(jié)點
scanf("%ld,%f", &stu->num, &stu->score); //輸人插入結(jié)點的數(shù)據(jù)
}
return 0;
}
//建立鏈表的函數(shù)
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);
}
//刪除結(jié)點的函數(shù)
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個結(jié)點
while (num != p1->num && p1->next != NULL) // pl指向的不是所要找的結(jié)點且后面還有結(jié)點
{
p2 = p1; // p1 后移一個結(jié)點
p1 = p1->next;
}
if (num == p1->num) //找到了
{
if (p1 == head) //若 p1指向的是首結(jié)點荆针，把第2個結(jié)點地址賦予head
head = p1->next;
else //否則將下一結(jié)點地址賦給前一結(jié)點地址
p2->next = p1->next;
printf("delete:%ld\n", num);
n = n - 1;
}
else
printf("%ld not been found! \n", num); //找不到該結(jié)點
return (head);
}
//插入結(jié)點的函數(shù)
struct student *insert(struct student *head, struct student *stud)
{
struct student *p0, *p1, *p2;
p1 = head; //使 p1 指向第1個結(jié)點
p0 = stud; //指向要插入的結(jié)點
if (head == NULL) //原來的鏈表是空表
{
head = p0; //使 p0指向的結(jié)點作為頭結(jié)點
p0->next = NULL;
}
else
{
while ((p0->num > p1->num) && (p1->next != NULL))
{
p2 = p1; //使 p2指向剛才p1指向的結(jié)點
p1 = p1->next; // p1后移一個結(jié)點
}
if (p0->num <= p1->num)
{
if (head == p1) //插到原來第1個結(jié)點之前
head = p0;
else //插到 p2 指向的結(jié)點之后
p2->next = p0;
p0->next = p1;
}
else
{
p1->next = p0;
p0->next = NULL; //插到最后的結(jié)點之后
}
}
n = n + 1; //結(jié)點數(shù)加1
return (head);
}
//輸出鏈表的函數(shù)
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 開辟一個內(nèi)存區(qū)，將其起始地址賦給 stu 航背，然后輸入此結(jié)構(gòu)體變量中各成員的值喉悴。對不同的插入對象，stu 的值是不同的玖媚，每次指向一個新的 student 變量箕肃。在調(diào)用 insert 函數(shù)時，實參為 head 和 stu 今魔，將已有的鏈表起始地址傳給 insert 函數(shù)的形參 head勺像，將新開辟的單元的地址 stu 傳給形參 stud，返回的函數(shù)值是經(jīng)過插入之后的鏈表的頭指針（地址）错森。
運行結(jié)果：
請讀者仔細(xì)消化這個程序吟宦。這個程序只是初步的，用來實現(xiàn)基本的功能涩维，讀者可以在此基礎(chǔ)上進(jìn)一步完善和豐富它殃姓。
題目10：已有a，b兩個鏈表瓦阐，每個鏈表中的結(jié)點包括學(xué)號蜗侈、成績。要求把兩個鏈表合并垄分，按學(xué)號升序排列宛篇。
解：
答案代碼：
#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); //函數(shù)聲明
struct student *insert(struct student *, struct student *); ///函數(shù)聲明
void print(struct student *); //函數(shù)聲明
struct student *ahead, *bhead, *abh;
printf("input list a:\n");
ahead = creat(); //調(diào)用 creat 函數(shù)建立表 A，返回頭地址
sum = sum + n;
printf("input list b:\n");
bhead = creat(); //調(diào)用 creat 函數(shù)建立表 B薄湿，返回頭地址
sum = sum + n;
abh = insert(ahead, bhead); //調(diào)用 insert 函數(shù)叫倍，將兩表合并
print(abh); // 輸出合并后的鏈表
return 0;
}
//建立鏈表的函數(shù)
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 函數(shù)，用來合并兩個鏈表
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);
}
//輸出函數(shù)
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);
}
運行結(jié)果：
程序提示：輸入 a 鏈表中的結(jié)點數(shù)據(jù)豺瘤，包括學(xué)生的學(xué)號和成績吆倦，如果輸入的學(xué)號為 0 ，就表示輸入結(jié)束坐求。向 a 鏈表輸入 4 個學(xué)生的數(shù)據(jù)蚕泽，向 b 鏈表輸入 3 個學(xué)生的數(shù)據(jù)。程序把兩個鏈表合并桥嗤，按學(xué)號從小到大排列须妻。最后輸出合并后鏈表的數(shù)據(jù)。
請讀者仔細(xì)分析和理解程序的思路和算法泛领。
題目11：有兩個鏈表 a 和 b荒吏，設(shè)結(jié)點中包含學(xué)號、姓名渊鞋。從 a鏈表中刪去與b鏈表中有相同學(xué)號的那些結(jié)點绰更。
解：刪除操作的N-S圖如圖9.7所示瞧挤。
為減少程序運行時的輸人量，先設(shè)兩個結(jié)構(gòu)體數(shù)組 a 和 b儡湾，并使用初始化的方法使之得到數(shù)據(jù)特恬。建立鏈表時就利用這兩個數(shù)組中的元素作為結(jié)點。
程序如下：
#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; //這是最后一個結(jié)點
printf("%4d%8s\n", p1->num, p1->name); //輸出一個結(jié)點的數(shù)據(jù)
if (i < LA)
p1 = p1->next; //如果不是最后一個結(jié)點徐钠，使 p1指向下一個結(jié)點
}
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鏈表進(jìn)行刪除操作
p1 = head1;
while (p1 != NULL)
{
p2 = head2;
while ((p1->num != p2->num) && (p2->next != NULL))
p2 = p2->next; //使 p2 后移直到發(fā)現(xiàn)與a鏈表中當(dāng)前的結(jié)點的學(xué)號相同或已到b鏈表中最后一個結(jié)點
if (p1->num == p2->num) //兩個鏈表中的學(xué)號相同
{
if (p1 == head1) // a 鏈表中當(dāng)前結(jié)點為第1個結(jié)點
head1 = p1->next; //使 head1指向 a鏈表中第2個結(jié)點
else //如果不是第1個結(jié)點
{
p->next = p1->next; //使p->next指向 pl的下一個結(jié)點癌刽，即刪去 p1當(dāng)前指向的結(jié)點
p1 = p1->next; // pl指向 pl的下一個結(jié)點；言了
}
}
else // b鏈表中沒有與a鏈表中當(dāng)前結(jié)點相同的學(xué)號
{
p = p1; // p1 指向 a 鏈表中的下一個結(jié)點
p1 = p1->next;
}
}
//輸出已處理過的 a鏈表中全部結(jié)點的數(shù)據(jù)
printf("\nresult:\n");
p1 = head1;
while (p1 != NULL)
{
printf("%4d %7s \n", p1->num, p1->name);
p1 = p1->next;
}
return 0;
}
運行結(jié)果：
題目12：建立一個鏈表丹皱，每個結(jié)點包括∶學(xué)號妒穴、姓名、性別摊崭、年齡讼油。輸入一個年齡，如果鏈表中的結(jié)點所包含的年齡等于此年齡呢簸，則將此結(jié)點刪去矮台。
解：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;
}
//刪除結(jié)點
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 //中間結(jié)點不是待刪元素
p = pt;
pt = pt->next;
}
if (!find)
printf("not found %d.", iage);
p = head;
printf("\n NO.name sex age\n"); //顯示結(jié)果
while (p != NULL)
{
printf("%4s%8s", p->num, p->name);
printf("%6s%6d\n", p->sex, p->age);
p = p->next;
}
return 0;
}
運行結(jié)果：
程序運行開始后瘦赫，提示用戶輸入鏈表的長度（要求小于10）。用戶輸入 4 蛤迎，并輸入 4 個學(xué)生的學(xué)號确虱、姓名、年齡替裆。程序輸出已有結(jié)點的數(shù)據(jù)校辩，用戶要刪除年齡為 19 的學(xué)生結(jié)點，最后只剩下兩個結(jié)點辆童。
