第二次報告鏈表

1、高級語言課程設(shè)計報告序號姓名成績學(xué)號E-MAIL及電話實習(xí)題目第二次報告:鏈表l 本題不在系統(tǒng)中提交，直接編程即可。l 學(xué)習(xí)課本p358 12.8節(jié)全部內(nèi)容，要求讀懂程序。l 完成以下內(nèi)容，使用教材節(jié)點結(jié)構(gòu)和主要功能代碼者提供答疑。主要代碼來歷不明者自行解決所有疑問。l 要求迭代開發(fā)，即先編寫核心代碼塊，驗證無誤后再逐步添加新的功能。l 要求界面友好，給出功能菜單，用戶可選擇下一步操作。1. 完成p367思考題之（1），（2），（3）2. 編寫函數(shù)，完成在第n個節(jié)點之后增加新節(jié)點的功能，n值由鍵盤輸入。（注意健壯性）。3. 編寫函數(shù)，完成在第n個節(jié)點之后刪除新節(jié)點的功能，n值由鍵盤輸入。（注意

2、健壯性）。4. 編寫函數(shù)，刪除所有數(shù)據(jù)值為奇數(shù)的節(jié)點。（注意健壯性）。5. 要求每次增刪節(jié)點后可以顯示更新后的鏈表元素個數(shù)及每個節(jié)點的信息。l 假設(shè)兩個單鏈表分別有序，請將兩個鏈表合并成一個有序鏈表。（選做）評閱意見： 評閱人： 2015年 月 日1.你的代碼、注釋及運行結(jié)果貼圖。2.設(shè)計及調(diào)試過程遇到的問題及解決方案。3.心得體會和自我對程序的評價。代碼：#include <stdio.h> #include <stdlib.h> struct link *AppendNode(struct link *head);/添加一個鏈表void DisplyNode(str

3、uct link *head);/顯示更新后的鏈表元素個數(shù)及每個節(jié)點的信息void DeleteMemory(struct link *head);/釋放head指向的鏈表中，所有節(jié)點占用的內(nèi)存struct link *DeleteNode(struct link *head, int nodeData);/刪除鏈表中的某一節(jié)點struct link *DeletealloddNode(struct link *head);/刪除鏈表中的所以奇數(shù)節(jié)點struct link *AppendNodeN(struct link *head,int n);/第n個節(jié)點之后增加新節(jié)點struct lin

4、k *DeletenNode(struct link *head, int n);/第n個節(jié)點之后刪除新節(jié)點struct link int data; struct link *next; ; int main() int i = 0; int n,m; char c; struct link *head = NULL; /*鏈表頭指針*/ printf("Do you want to append a new node(Y/N)?"); scanf(" %c",&c); /* %c前面有一個空格*/ while (c='Y' |

5、 c='y') head = AppendNode(head); DisplyNode(head); /*顯示當(dāng)前鏈表中的各節(jié)點信息*/ printf("Do you want to append a new node(Y/N)?"); scanf(" %c",&c); /* %c前面有一個空格*/ i+;/計數(shù)變量，用來統(tǒng)計新增節(jié)點的數(shù)量 printf("%d new nodes have been apended!n", i);printf("do you want add a node at a

6、ny position in the list?(Y/N):"); scanf(" %c",&c); if(c='Y' | c='y') printf("nInput the position of the node to be added:n"); scanf("%d",&n);/n由鍵盤輸入head = AppendNodeN(head,n);/在鏈表中第n個節(jié)點后，插入一個新的節(jié)點DisplyNode(head); printf("Input the data

7、of the node to be deleted: "); scanf("%d",&m); head = DeleteNode(head, m);/刪除指定節(jié)點，數(shù)據(jù)域中的數(shù)據(jù)m由鍵盤輸入DisplyNode(head); printf("nInput the location of the node to be deleted: "); scanf("%d",&n); head = DeletenNode(head,n);/刪除鏈表的第n個節(jié)點，n由鍵盤輸入DisplyNode(head); head =

8、 DeletealloddNode(head);/刪除鏈表中所有奇數(shù)DisplyNode(head); DeleteMemory(head); /* 釋放所有動態(tài)分配的內(nèi)存*/ return 0; /* 函數(shù)功能：新建一個節(jié)點并添加到鏈表末尾，返回添加節(jié)點后的鏈表的頭指針*/ struct link *AppendNode(struct link *head) struct link *p = NULL; struct link *pr = head; int data; p = (struct link *)malloc(sizeof(struct link); /* 讓p指向新建節(jié)點*/

9、if (p = NULL) printf("No enough memory to allocate!n"); exit(0); if (head = NULL) /* 若原鏈表為空表，則將新建節(jié)點置為首節(jié)點*/ head = p; else /* 若原鏈表為非空，則將新建節(jié)點添加到表尾*/ while (pr->next != NULL)/* 若未到表尾，則移動pr直到pr指向表尾*/ pr = pr->next; /* 讓pr指向下一個節(jié)點*/ pr->next = p; /* 將新建節(jié)點添加到鏈表的末尾*/ pr = p; /* 讓pr指向新建節(jié)點*

10、/ printf("Input node data:"); scanf("%d", &data); /* 輸入節(jié)點數(shù)據(jù)*/ pr->data = data; pr->next = NULL; /* 將新建節(jié)點置為表尾*/ return head; /* 返回添加節(jié)點后的鏈表的頭節(jié)點指針*/ /* 函數(shù)的功能：顯示鏈表中所有節(jié)點的節(jié)點號和該節(jié)點中數(shù)據(jù)項內(nèi)容*/ void DisplyNode(struct link *head) struct link *p = head; int j = 1; while (p != NULL) /*

11、 若不是表尾，則循環(huán)打印*/ printf("%5d%10dn", j, p->data);/* 打印第j個節(jié)點的數(shù)據(jù)*/ p = p->next; /* 讓p指向下一個節(jié)點*/ j+; /* 函數(shù)功能：釋放head指向的鏈表中所有節(jié)點占用的內(nèi)存*/ void DeleteMemory(struct link *head) struct link *p = head, *pr = NULL; while (p != NULL) /* 若不是表尾，則釋放節(jié)點占用的內(nèi)存*/ pr = p; /* 在pr中保存當(dāng)前節(jié)點的指針*/ p = p->next; /*

12、讓p指向下一個節(jié)點*/ free(pr); /* 釋放pr指向的當(dāng)前節(jié)點占用的內(nèi)存*/ /* 函數(shù)功能：從head指向的鏈表中刪除一個節(jié)點，返回刪除節(jié)點后的鏈表的頭指針*/ struct link *DeleteNode(struct link *head, int nodeData) struct link *p = head, *pr = head; if (head = NULL) /* 若鏈表為空表，則退出程序*/ printf("Linked Table is empty!n"); return(head); while (nodeData != p->da

13、ta && p->next != NULL)/* 未找到且未到表尾*/ pr = p; p = p->next; if (nodeData = p->data) /* 若找到節(jié)點nodeData，則刪除該節(jié)點*/ if (p = head) /* 若待刪除節(jié)點為首節(jié)點，則讓head指向第2個節(jié)點*/ head = p->next; else /*若待刪除節(jié)點不是首節(jié)點，則將前一節(jié)點的指針指向當(dāng)前節(jié)點的下一節(jié)點*/ pr->next = p->next; free(p);/* 釋放為已刪除節(jié)點分配的內(nèi)存*/ else /* 沒有找到待刪除節(jié)點*

14、/ printf("This Node has not been found!n"); return head; /* 返回刪除節(jié)點后的鏈表的頭節(jié)點指針*/ /*函數(shù)功能：刪除鏈表中所有數(shù)據(jù)值為奇數(shù)的節(jié)點，返回操作后鏈表的頭指針*/ struct link *DeletealloddNode(struct link *head) struct link *p = head,*pr = head,*temp=NULL;/*temp為中間指針變量*/ if(head = NULL)/若原鏈表為空 printf("Linked Table is empty!n"

15、;); return(head); for(;p->next!=NULL;)/遍歷循環(huán)。若未到表尾，則移動p直到p指向表尾 if(p->data%2=0)/若節(jié)點中的數(shù)據(jù)是偶數(shù)，則跳過此節(jié)點，并將p和 pr都移動到下一個節(jié)點 pr=p; p=p->next; else if(p->data%2=1)/若節(jié)點中的數(shù)據(jù)是奇數(shù)，則刪除此節(jié)點，并將p和pr移動到下個節(jié)點 if(p=head)/若p是頭指針 head=p->next; /*增強函數(shù)的健壯性*/ else/若不是頭指針 pr->next = p->next; temp=p;/中間指針變量temp來

16、記錄奇數(shù)節(jié)點的位置pr=p; p=p->next; /p和pr都跳過奇數(shù)節(jié)點，移動到下個節(jié)點free(temp);/釋放奇數(shù)節(jié)點temp的動態(tài)存儲空間 if(p->data%2=1)/如果最后一個節(jié)點是奇數(shù)，則進(jìn)行刪除 pr->next=NULL;/令倒數(shù)第二個節(jié)點的next為NULL free(p); printf("all odd nodes has been deletedn"); return head;/返回鏈表的頭指針 /*函數(shù)功能：在鏈表中第n個節(jié)點后新增一個節(jié)點，返回增加后的鏈表的頭指針的值*/ struct link *AppendNod

17、eN(struct link *head,int n)/形參：當(dāng)前鏈表的頭指針head和節(jié)點位置n struct link *p=NULL,*pr=head; int data; int k=0; p = (struct link *)malloc(sizeof(struct link);/讓p指向新建節(jié)點if(p = NULL)/若為新建節(jié)點申請內(nèi)存失敗 printf("NO enough memory to allocate! n"); for(k=0;k<n-1;k+)/循環(huán)，若未到第n個節(jié)點，將pr移到下個節(jié)點；直到第n個節(jié)點 pr=pr->next;

18、p->next=pr->next;/將p指向第n+1個節(jié)點pr->next=p; /將第n個節(jié)點的pr指向p printf("Input node data:"); scanf("%d", &data); /* 輸入節(jié)點數(shù)據(jù)*/ p->data = data; /* 將新建節(jié)點的數(shù)據(jù)域賦值為輸入的節(jié)點數(shù)據(jù)值*/ return head; struct link *DeletenNode(struct link *head, int n) struct link *p = head, *pr = head; int k=0; if (head = NULL) /* 若鏈表為空表，則退出程序*/ printf("Linked Table is empty!n"); return(head); for(k=0;k<n-1;k+)/循環(huán)，若未到第n個節(jié)點，將pr和p移到下個節(jié)點；直到第n個節(jié)點 pr=p; p=p->next; printf("pr->%d p->%dn",pr->