西電機(jī)電院自動化專業(yè)軟件技術(shù)基礎(chǔ)上機(jī)報告.doc

上機(jī)報告一、 上機(jī)目的（1） 掌握鏈表的基本運(yùn)算：建立，查找，刪除，排序等。（2） 掌握樹的基本運(yùn)算。二、 上機(jī)內(nèi)容 1設(shè)有一個由正整數(shù)組成的無序單鏈表，編寫完成下列功能的算法： 找出最小值結(jié)點，且打印該數(shù)值； 若該數(shù)值是奇數(shù)，則將其與直接后繼結(jié)點的數(shù)值交換； 若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點刪除。2編一程序：建立一個數(shù)據(jù)域為1至10的帶頭結(jié)點的鏈表； 將此鏈表就地逆轉(zhuǎn)。3設(shè)有一個含有數(shù)字、英文字母和其它字符的單鏈表，試編寫一個算法將該單鏈表拆分為三個單鏈表，使每個單鏈表中只包含同一類的字符，要求利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可以另辟空間。4某百貨公司倉庫中有一批電視機(jī)，試按價格從高到低的次序建立一個循環(huán)鏈表，每個結(jié)點有價格、數(shù)量和指針三個域。現(xiàn)新到10臺價格為4000元的電視機(jī)，修改原鏈表并輸出修改后鏈表的所有內(nèi)容。5假設(shè)稱正讀反讀都相同的字符序列為回文。例如，abba，abcba都是回文， ababab不是回文，試編寫程序判別從標(biāo)準(zhǔn)輸入讀入的以為結(jié)束符的字符序列是否是回文。6試設(shè)計一個程序，求二叉樹的結(jié)點數(shù)目和葉子結(jié)點數(shù)目。三、 設(shè)計說明：寫出數(shù)據(jù)結(jié)構(gòu)的定義和算法流程第一題：（1）使用尾插法建立帶有頭結(jié)點的單鏈表:因為題目要求為正整數(shù)，故以數(shù)字0最為結(jié)束符。（2）查找過程中，首先定義兩個結(jié)點類型的變量p、s，p指向頭結(jié)點，s指向第一個結(jié)點，然后將p依次后移，并且每移動一次就將p的值與s的值進(jìn)行比較，若p-datadata，則將p賦給s;否則p繼續(xù)后移，直至鏈尾。（3）刪除結(jié)點過程：刪除結(jié)點就需要找到此結(jié)點的前驅(qū)結(jié)點，然后將此結(jié)點的前驅(qū)的后繼指向此結(jié)點的后繼結(jié)點即可。（4）結(jié)點交換過程：定義一個中間結(jié)點，先將要交換的結(jié)點中的一個A賦給中間結(jié)點保存，然后將結(jié)點B的值賦給結(jié)點A，再將中間結(jié)點的值賦給結(jié)點B即可完成結(jié)點的交換。（5）打印結(jié)點過程：首先定義局部結(jié)點變量p,并且使其指向要打印的鏈表的頭結(jié)點，然后將p結(jié)點后移，每移動一次就打印當(dāng)前p的值，直至p的后續(xù)結(jié)點為NULL。第二題：(1)使用尾插法建立帶有頭結(jié)點的單鏈表:因為題目要求數(shù)字為1到10，故當(dāng)數(shù)字小于1或者大于10時就停止輸入。(2)打印結(jié)點過程：首先定義局部結(jié)點變量p,并且使其指向要打印的鏈表的頭結(jié)點，然后將p結(jié)點后移，每移動一次就打印當(dāng)前p的值，直至p的后續(xù)結(jié)點為NULL。(3)逆置過程：首先定義兩個結(jié)點p、q，p結(jié)點指向第一個結(jié)點，q結(jié)點始終指向p的后續(xù)結(jié)點然后將p的后續(xù)指向q的后續(xù)，并且將q的后續(xù)指向p,再將頭結(jié)點指向q，因為p的位置不變，q依次后移，每次移動都將q插在head之后，故可以實現(xiàn)鏈表的逆置。第三題：(1) 使用尾插法建立帶有頭結(jié)點的單鏈表:當(dāng)遇到回車符時結(jié)束字符的輸入。(2) 打印結(jié)點過程：首先定義局部結(jié)點變量p,并且使其指向要打印的鏈表的頭結(jié)點，然后將p結(jié)點后移，每移動一次就打印當(dāng)前p的值，直至p的后續(xù)結(jié)點為NULL。(3)對鏈表的分類整理：考慮到分類之后要返回給不同的三個鏈表，故使用全局變量，在函數(shù)調(diào)用時直接對全局變量進(jìn)行操作。在查找過程中根據(jù)ASCII碼的不同依次將他們連接在相應(yīng)的鏈表之后。通過將頭結(jié)點的地址傳給PRINT函數(shù)就可以將相應(yīng)的鏈表打印出來。第四題：(1)使用尾插法建立帶有頭結(jié)點的單鏈表:當(dāng)遇到price和number均為0時結(jié)束輸入。(2)排序過程：首先定義兩個中間結(jié)點p、q,p結(jié)點指向鏈表的第一個結(jié)點，q結(jié)點指向p的后續(xù)結(jié)點，將q結(jié)點的price與p結(jié)點的price進(jìn)行比較，如果p-priceprice，則將兩者進(jìn)行交換，直至q指向鏈表的最后一個元素。然后將p后移，重復(fù)以上步驟執(zhí)行。(3)插入過程：在執(zhí)行插入過程中，要先進(jìn)行查找操作，即將要插入的元素s的s-price與原來鏈表中的元素逐個進(jìn)行比較，插入到第一個比s-price大的數(shù)據(jù)前。第五題：方法一：基本思想：將字符存入數(shù)組，然后對數(shù)組進(jìn)行首尾兩端的元素進(jìn)行比較，若相等，則將前標(biāo)號后移一位，同時后標(biāo)號前移一位。方法二：基本思想：采用堆棧的思想：先將數(shù)據(jù)存入鏈表，然后計算鏈表長度，將鏈表的前一半壓入堆棧，若長度為則需先將鏈表當(dāng)前指向后移一個，在將堆棧數(shù)據(jù)彈出，與鏈表后半部分?jǐn)?shù)據(jù)進(jìn)行比較；若長度為偶數(shù)，則直接將鏈堆、棧中數(shù)據(jù)彈出與鏈表中的后半部分進(jìn)行比較。第六題：（1）樹的建立：樹的建立是借用隊列先入先出的原則，隊尾指向當(dāng)前輸入的結(jié)點，對頭指向當(dāng)前在這個結(jié)點的雙親結(jié)點，當(dāng)尾結(jié)點是偶數(shù)時，當(dāng)前結(jié)點作為左孩子與雙親結(jié)點鏈接，當(dāng)尾結(jié)點為奇數(shù)時，當(dāng)前結(jié)點作為右孩子與雙親結(jié)點進(jìn)行鏈接，若當(dāng)前結(jié)點為虛結(jié)點（即為）時，則無須鏈接。（2）結(jié)點的查找：只要當(dāng)前的結(jié)點不是虛結(jié)點即為有效結(jié)點。（3）葉子結(jié)點的查找：只要當(dāng)前結(jié)點沒有左右孩子即可認(rèn)為該結(jié)點是葉子結(jié)點。四、 調(diào)試分析在編寫程序中使用的集成開發(fā)工具：Code：blocks 12.11使用的編譯器：GNU GCC compile遇見的問題：（1）Mian函數(shù)返回類型在使用void時編譯器提示返回類型不正確，在缺省時，main函數(shù)默認(rèn)返回值類型為int,會出現(xiàn)warning信息。解決辦法：使main函數(shù)的返回int類型，然后在最后加上“return 1”語句。（2）在有時括號的配對不正確，導(dǎo)致程序編譯時不通過。解決辦法：養(yǎng)成好的編程習(xí)慣，規(guī)范的格式有助于查找錯誤。（3）在設(shè)計算法時經(jīng)常忽略了特殊元素的處理：比如在第四題插入新的數(shù)據(jù)，查找插入位置時，當(dāng)p指向第一個元素是要進(jìn)行特殊處理。在第五題中當(dāng)字符串的長度是奇數(shù)時，將前一半元素壓入堆棧以后，要先將p后移一次，在逐個出棧進(jìn)行比較。解決辦法：在設(shè)計算法之前，應(yīng)該先將算法進(jìn)行合理的推演，將所有的情況都要考慮進(jìn)去，養(yǎng)成嚴(yán)謹(jǐn)?shù)暮昧?xí)慣。改進(jìn)之處：在第一題中，如果鏈表中的最小值有多個時，只能找到第一個，針對第一個進(jìn)行處理。經(jīng)驗與體會：通過這幾次上機(jī)，覺得將一個算法設(shè)計出來并不是難事，但是能否在計算機(jī)上正確運(yùn)行是最關(guān)鍵的問題，有時編譯時并不會報錯，但是程序就是不能按照預(yù)期的結(jié)果運(yùn)行，這時就需要進(jìn)行調(diào)試，單步調(diào)試來觀察能夠判斷算法正誤的變量的值，然后對算法進(jìn)行改進(jìn)，最終使算法按照預(yù)期模式運(yùn)行。覺得調(diào)試完一個程序之后對算法有了新的認(rèn)識和更深刻的了解，收獲遠(yuǎn)比編寫出一個算法大得多。五、 測試結(jié)果 第一題：當(dāng)最小值是偶數(shù)時：當(dāng)最小值是奇數(shù)時：第二題：第三題：第四題：第五題：方法一：方法二:第六題：當(dāng)輸入為ABCDEFG# 時當(dāng)輸入為ABCDE#六、 帶注釋的源程序第一題：/*設(shè)有一個由正整數(shù)組成的無序單鏈表，編寫完成下列功能的算法： 找出最小值結(jié)點，且打印該數(shù)值； 若該數(shù)值是奇數(shù)，則將其與直接后繼結(jié)點的數(shù)值交換； 若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點刪除。*/#include#include#includetypedef struct node /*結(jié)點聲明*/int data;struct node *next;linklist;linklist *head,*p;/*使用尾插法建立單鏈表，并且以0作為結(jié)束符*/linklist *CREAT()int data1;linklist *head,*s,*r;head=(linklist*)malloc(sizeof(linklist);r=head;printf(Please input the numbers:n);scanf(%d,&data1);while(data1!=0)s=(linklist*)malloc(sizeof(linklist); s-data=data1; r-next=s; r=s; scanf(%d,&data1);r-next=NULL;return head;/*打印當(dāng)前鏈表的所有結(jié)點數(shù)值*/void PRINT(linklist *head) /*打印單鏈表*/ linklist *p; int j=0; p=head-next; while(p!=NULL) j+; printf(nnumber %d=%d,j,p-data); p=p-next;/*找到當(dāng)期單鏈表中的最小值，并且將該最小值打印出來*/linklist *SEARCH(linklist *head) linklist *p,*s; p=s=head-next; while(p-next!=NULL) p=p-next; if(p-data)data) s=p; printf(nthe minimum is：%dn,s-data); return s;/*刪除當(dāng)前結(jié)點*/void DELETE(linklist *head,linklist *p) /*刪除結(jié)點p*/ linklist *q; q=head-next; while(q-next!=p) q=q-next; q-next=p-next;/*將當(dāng)前結(jié)點和其后面的結(jié)點進(jìn)行交換*/void EXCHANG(linklist *p) int x; x=p-data; p-data=(p-next)-data; (p-next)-data=x;int main() linklist *head,*p,*q; head=CREAT(); /使用尾插法建立鏈。 printf(The Array is:); /打印當(dāng)前鏈表。 PRINT(head); p=SEARCH(head); /查找最小值結(jié)點。 q=p-next; if(p-data%2=1) EXCHANG(p);/如果最小值為奇數(shù)，則將最小值結(jié)點與其后繼結(jié)點交換 else DELETE(head,q); /如果最小值為偶數(shù)，則刪除后繼結(jié)點。 printf(nnnthe final numbers are:n); PRINT(head); return 1; 第二題：/*編一程序：建立一個數(shù)據(jù)域為1至10的帶頭結(jié)點的鏈表； 將此鏈表就地逆轉(zhuǎn)。*/#include#include#includetypedef int datatype;typedef struct node datatype data; struct node *next;linklist; /定義結(jié)點結(jié)構(gòu)體。linklist *head,*p; /對結(jié)點進(jìn)行聲明。/*使用尾插法建立帶有頭結(jié)點的鏈表。*/linklist *CREATLSTER() int a; linklist *head,*s,*r; head=(linklist*)malloc(sizeof(linklist); r=head; printf(Please input the numbers between 1 to 10:n); scanf(%d,&a); while(a=1)&(adata=a; r-next=s; r=s; scanf(%d,&a); r-next=NULL; /最后一個結(jié)點的后續(xù)結(jié)點置空。 return head;/*打印鏈表：將元素諸葛打印直至最后一個結(jié)點.*/void PRINT(linklist *head) linklist *p; int j=0; p=head-next; while(p!=NULL) j+; printf(nnumber%d=%d,j,p-data); p=p-next; /*將當(dāng)前鏈表逆置，并且不開辟新空間，逆置之后將當(dāng)鏈表頭結(jié)點返回*/linklist *REVERSEL(linklist *head) linklist *p,*q; p=head-next; while(p-next!=NULL) q=p-next; p-next=q-next; q-next=head-next; head-next=q; return head;int main() linklist *head; head=(linklist*)malloc(sizeof(linklist); head=CREATLSTER(); /尾插法建立鏈表。 printf(n*nthe original numbers are : n); PRINT(head); /打印當(dāng)前鏈表。 printf(n*n); REVERSEL(head); /將鏈表逆置。 printf(nn*nthe numbers after reversel are : n); PRINT(head); /打印逆置以后的鏈表。 printf(n*n); return 1; 第三題：/*3設(shè)有一個含有數(shù)字、英文字母和其它字符的單鏈表，試編寫一個算法將該單鏈表拆分為三個單鏈表，使每個單鏈表中只包含同一類的字符，要求利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可以另辟空間。*/#include#include#includetypedef char datatype;typedef struct node datatype data; struct node *next;linklist;/定義結(jié)點結(jié)構(gòu)體linklist *NUM,*CHAR,*STRING,*head; /定義全局變量，以便函數(shù)調(diào)用之后能夠?qū)⒄{(diào)用結(jié)果返回linklist *CREATLSTER() /創(chuàng)建鏈表，將數(shù)據(jù)讀入 datatype ch; linklist *head,*r,*s; head=(linklist *)malloc(sizeof(linklist); r=head; ch=getchar(); while(ch!=n) s=(linklist *)malloc(sizeof(linklist); s-data=ch; r-next=s; r=s; ch=getchar(); r-next=NULL; return head;/*刪除頭結(jié)點為head的鏈表中的結(jié)點p*/linklist *DELETE(linklist *p,linklist *head) linklist *q=head; while(q-next!=p) q=q-next; q-next=p-next; return p;/*對鏈表數(shù)據(jù)進(jìn)行查找分類*/void FIND(linklist *head) linklist *p; linklist *s_NUM=NUM,*s_CHAR=CHAR,*s_STRING=STRING; /定義局部變量，以便將結(jié)果傳給全局變量 p=head-next; s_NUM-next=NULL; s_CHAR-next=NULL; s_STRING-next=NULL; while(p!=NULL) if(p-data=0)&(p-datanext=DELETE(p,head); s_NUM=s_NUM-next; p=p-next; else if(p-data=A)&(p-datanext=DELETE(p,head); /將字母結(jié)點鏈接在s_CHAR之后 s_CHAR=s_CHAR-next; p=p-next; else s_STRING-next=DELETE(p,head); s_STRING=s_STRING-next; /將其他字符結(jié)點鏈接在s_STRING之后 p=p-next; s_NUM-next=NULL; s_CHAR-next=NULL; s_STRING-next=NULL;/*打印當(dāng)前鏈表*/void PRINT(linklist *head) linklist *p; int j=0; p=head-next; while(p!=NULL) j+; printf(nVALUE %d = %c,j,p-data); p=p-next; int main() head=(linklist *)malloc(sizeof(linklist); /為head結(jié)點分配空間 NUM=(linklist *)malloc(sizeof(linklist); /為數(shù)字鏈表的頭結(jié)點分配空間。 CHAR=(linklist *)malloc(sizeof(linklist); /為字母鏈表的頭結(jié)點分配空間。 STRING=(linklist *)malloc(sizeof(linklist); /為其他字符鏈表的頭結(jié)點分配空間。 printf(n*nPlease input characters:n); head=CREATLSTER(); /尾插法建立鏈表 printf(n*n); printf(nn*nthe input are:n); PRINT(head); /打印當(dāng)前鏈表 printf(n*n); FIND(head); /為當(dāng)前鏈表整理分類 printf(nn*nthe numbers are:n); PRINT(NUM); /打印數(shù)字鏈表 printf(n*n); printf(nn*nthe characters are:n); PRINT(CHAR); /打印字母鏈表 printf(n*n); printf(nn*nthe others are:n); PRINT(STRING); /打印其他字符鏈表 printf(n*n); return(1);第四題：/*某百貨公司倉庫中有一批電視機(jī)，試按價格從高到低的次序建立一個循環(huán)鏈表，每個結(jié)點有價格、數(shù)量和指針三個域?，F(xiàn)新到10臺價格為4000元的電視機(jī)，修改原鏈表并輸出修改后鏈表的所有內(nèi)容。*/#include#include#includetypedef struct node int number; float price; struct node *next;linklist;/*用尾插法創(chuàng)建鏈表*/linklist *CREAT() int number1; float price1; linklist *head,*r,*s; head=(linklist *)malloc(sizeof(linklist); r=head; printf(Please Input the number And The Price:n); scanf(%d%f,&number1,&price1); while(number1!=0)&(price1!=0) s=(linklist *)malloc(sizeof(linklist); s-number=number1; s-price=price1; r-next=s; r=s; scanf(%d%f,&number1,&price1); r-next=head; return head;/*打印鏈表*/void PRINT(linklist *head) linklist *p; int i=0; p=head-next; while(p!=head) i+; printf(nNO.%d THE NUMBER IS %d AND THE PRICE IS %f ,i,p-number,p-price); p=p-next; /*對鏈表進(jìn)行從高到低排序*/linklist *SORT(linklist *head) linklist *p,*q; int number2; float price2; p=head-next; while(p-next!=head) q=p-next; while(q!=head) if(p-priceprice) number2=p-number; price2=p-price; p-number=q-number; p-price=q-price; q-number=number2; q-price=price2; q=q-next; p=p-next; return head;/*按照由高到低的順序先尋找插入位置，然后將節(jié)點插入鏈表*/linklist *INSERT(linklist *head,linklist *s) linklist *q,*p; p=head-next; q=p-next; if(s-pricep-price) s-next=p; head-next=s; if(s-priceprice) p=p-next; q=q-next; s-next=q; p-next=s; return head;/*主函數(shù)*/int main() linklist *head,*s; s=(linklist *)malloc(sizeof(linklist); head=CREAT(); printf(n*nthe old table is:n); PRINT(head); printf(n*); SORT(head); printf(n*nthe sorted table is:n); PRINT(head); printf(n*); s=(linklist *)malloc(sizeof(linklist); printf(n*nInput the node need to insert:n); scanf(%d%f,&s-number,&s-price); printf(n*); INSERT(head,s); printf(n*nthe new sorted table after insert is:n); PRINT(head); printf(n*); return(1);第五題：方法一：/*假設(shè)稱正讀反讀都相同的字符序列為回文。例如，abba，abcba都是回文， ababab不是回文，試編寫程序判別從標(biāo)準(zhǔn)輸入讀入的以為結(jié)束符的字符序列是否是回文。假設(shè)稱正讀反讀都相同的字符序列為回文。例如，abba，abcba都是回文， ababab不是回文，試編寫程序判別從標(biāo)準(zhǔn)輸入讀入的以為結(jié)束符的字符序列是否是回文。編譯環(huán)境：GCC開發(fā)軟件：Codeblocks基本思想：將字符存入數(shù)組，然后對數(shù)組進(jìn)行首尾兩端的元素進(jìn)行比較，若相等，則將前標(biāo)號后移一位，同時后標(biāo)號前移一位。*/#include#include#include#define maxsize 1024 int main() char amaxsize;int n=0,Flag=0;int i,j;printf(Please Input The String:n);an=getchar();while(an!=$) n+;an=getchar();printf(The string is:n);for(i=0;in;i+)printf(the character %d is %c n ,i+1,ai);for(i=0,j=n-1;(ij)&(i!=j);i+,j-)if(ai=aj) Flag+;else break;if(Flag=n/2)printf(nthe string is Palindromen);elseprintf(nthe string isnt Palindromen);return (1);方法二:/*假設(shè)稱正讀反讀都相同的字符序列為回文。例如，abba，abcba都是回文， ababab不是回文，試編寫程序判別從標(biāo)準(zhǔn)輸入讀入的以為結(jié)束符的字符序列是否是回文。編譯環(huán)境：GCC開發(fā)軟件：Codeblocks基本思想：采用堆棧的思想：先將數(shù)據(jù)存入鏈表，然后計算鏈表長度，將鏈表的前一半壓入堆棧，若長度為則需先將鏈表當(dāng)前指向后移一個，在將堆棧數(shù)據(jù)彈出，與鏈表后半部分?jǐn)?shù)據(jù)進(jìn)行比較；若長度為偶數(shù)，則直接將鏈堆、棧中數(shù)據(jù)彈出與鏈表中的后半部分進(jìn)行比較。*/#include#include#include#define maxsize 1024typedef char datatype;int con=0;typedef struct Stack datatype elementmaxsize; int Top;Stack; /定義棧體typedef struct node datatype data; struct node *next;linklist; /定義鏈表，存儲待判定字符void SETNULL(Stack *s )/將棧體置空 s-Top=-1;int EMPTY(Stack *s) / 判斷棧體是否是空 if(s-Top=-1) return (1); else return (0); Stack *PUSH(Stack *s,datatype E) /入棧 if(s-Top=maxsize-1) printf(Stack Overflow); return (NULL); else s-Top+; s-elements-Top=E; return s;datatype *POPS(Stack *s) /出棧 datatype *temp; if(EMPTY(s) printf(Stack is emptyn); return (NULL); else s-Top-; temp=(datatype *)malloc(sizeof(datatype); *temp=s-elements-Top+1; return temp;datatype *GETTOPS(Stack *s) /取棧頂元素 datatype *temp; if (EMPTY(s) printf(Stack is empty); return (NULL); else temp=(datatype *)malloc(sizeof(datatype); *temp=s-elements-Top; return (temp); linklist *CREAT() /尾插法建立鏈表 datatype ch; linklist *head,*r,*s; head=(linklist *)malloc(sizeof(linklist); r=head; ch=getchar(); while(ch!=$) s=(linklist *)malloc(sizeof(linklist); s-data=ch; r-next=s; r=s; ch=getchar(); r-next=NULL; printf(n); return head;int main() int i=1; linklist *head,*p; Stack *s; s=(Stack *)malloc(sizeof(Stack); head=(linklist *)malloc(sizeof(linklist); printf(nPlease Input The Strings:n); head=CREAT(); p=head; SETNULL(s); while(p-next!=NULL) /計算待判定字符（鏈表）長度 con+; p=p-next; p=head-next; for(i=1;idata); p=p-next; while(con%2=1) p=p-next; while(p!=NULL) if(p-data)=*GETTOPS(s) POPS(s); p=p-next; else break; if(EMPTY(s) printf(nn$nThe string is Palindrome;n$);else printf(nn$nThe s