第二次報(bào)告鏈表

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

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

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

4、k *DeletenNode(struct link *head, int n);/第n個(gè)節(jié)點(diǎn)之后刪除新節(jié)點(diǎn)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前面有一個(gè)空格*/ while (c='Y' |

5、 c='y') head = AppendNode(head); DisplyNode(head); /*顯示當(dāng)前鏈表中的各節(jié)點(diǎn)信息*/ printf("Do you want to append a new node(Y/N)?"); scanf(" %c",&c); /* %c前面有一個(gè)空格*/ i+;/計(jì)數(shù)變量，用來統(tǒng)計(jì)新增節(jié)點(diǎn)的數(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個(gè)節(jié)點(diǎn)后，插入一個(gè)新的節(jié)點(diǎn)DisplyNode(head); printf("Input the data

7、of the node to be deleted: "); scanf("%d",&m); head = DeleteNode(head, m);/刪除指定節(jié)點(diǎn)，數(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個(gè)節(jié)點(diǎn)，n由鍵盤輸入DisplyNode(head); head =

8、 DeletealloddNode(head);/刪除鏈表中所有奇數(shù)DisplyNode(head); DeleteMemory(head); /* 釋放所有動(dòng)態(tài)分配的內(nèi)存*/ return 0; /* 函數(shù)功能：新建一個(gè)節(jié)點(diǎn)并添加到鏈表末尾，返回添加節(jié)點(diǎn)后的鏈表的頭指針*/ 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é)點(diǎn)*/

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

10、/ printf("Input node data:"); scanf("%d", &data); /* 輸入節(jié)點(diǎn)數(shù)據(jù)*/ pr->data = data; pr->next = NULL; /* 將新建節(jié)點(diǎn)置為表尾*/ return head; /* 返回添加節(jié)點(diǎn)后的鏈表的頭節(jié)點(diǎn)指針*/ /* 函數(shù)的功能：顯示鏈表中所有節(jié)點(diǎn)的節(jié)點(diǎn)號(hào)和該節(jié)點(diǎn)中數(shù)據(jù)項(xiàng)內(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個(gè)節(jié)點(diǎn)的數(shù)據(jù)*/ p = p->next; /* 讓p指向下一個(gè)節(jié)點(diǎn)*/ j+; /* 函數(shù)功能：釋放head指向的鏈表中所有節(jié)點(diǎn)占用的內(nèi)存*/ void DeleteMemory(struct link *head) struct link *p = head, *pr = NULL; while (p != NULL) /* 若不是表尾，則釋放節(jié)點(diǎn)占用的內(nèi)存*/ pr = p; /* 在pr中保存當(dāng)前節(jié)點(diǎn)的指針*/ p = p->next; /*

12、讓p指向下一個(gè)節(jié)點(diǎn)*/ free(pr); /* 釋放pr指向的當(dāng)前節(jié)點(diǎn)占用的內(nèi)存*/ /* 函數(shù)功能：從head指向的鏈表中刪除一個(gè)節(jié)點(diǎn)，返回刪除節(jié)點(diǎn)后的鏈表的頭指針*/ 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é)點(diǎn)nodeData，則刪除該節(jié)點(diǎn)*/ if (p = head) /* 若待刪除節(jié)點(diǎn)為首節(jié)點(diǎn)，則讓head指向第2個(gè)節(jié)點(diǎn)*/ head = p->next; else /*若待刪除節(jié)點(diǎn)不是首節(jié)點(diǎn)，則將前一節(jié)點(diǎn)的指針指向當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)*/ pr->next = p->next; free(p);/* 釋放為已刪除節(jié)點(diǎn)分配的內(nèi)存*/ else /* 沒有找到待刪除節(jié)點(diǎn)*

14、/ printf("This Node has not been found!n"); return head; /* 返回刪除節(jié)點(diǎn)后的鏈表的頭節(jié)點(diǎn)指針*/ /*函數(shù)功能：刪除鏈表中所有數(shù)據(jù)值為奇數(shù)的節(jié)點(diǎn)，返回操作后鏈表的頭指針*/ 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)。若未到表尾，則移動(dòng)p直到p指向表尾 if(p->data%2=0)/若節(jié)點(diǎn)中的數(shù)據(jù)是偶數(shù)，則跳過此節(jié)點(diǎn)，并將p和 pr都移動(dòng)到下一個(gè)節(jié)點(diǎn) pr=p; p=p->next; else if(p->data%2=1)/若節(jié)點(diǎn)中的數(shù)據(jù)是奇數(shù)，則刪除此節(jié)點(diǎn)，并將p和pr移動(dòng)到下個(gè)節(jié)點(diǎn) if(p=head)/若p是頭指針 head=p->next; /*增強(qiáng)函數(shù)的健壯性*/ else/若不是頭指針 pr->next = p->next; temp=p;/中間指針變量temp來

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

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

18、p->next=pr->next;/將p指向第n+1個(gè)節(jié)點(diǎn)pr->next=p; /將第n個(gè)節(jié)點(diǎn)的pr指向p printf("Input node data:"); scanf("%d", &data); /* 輸入節(jié)點(diǎn)數(shù)據(jù)*/ p->data = data; /* 將新建節(jié)點(diǎn)的數(shù)據(jù)域賦值為輸入的節(jié)點(diǎn)數(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個(gè)節(jié)點(diǎn)，將pr和p移到下個(gè)節(jié)點(diǎn)；直到第n個(gè)節(jié)點(diǎn) pr=p; p=p->next; printf("pr->%d p->%dn",pr->