1、.wd.wd.wd.實驗1 ADT表的編程與實現(xiàn)C語言，是一種通用的、過程式的編程語言，廣泛用于系統(tǒng)與應用軟件的開發(fā)。具有高效、靈活、功能豐富、表達力強和較高的可移植性等特點，在程序員中備受青睞。Microsoft Visual C+是Microsoft公司推出的開發(fā)Win32環(huán)境程序具有集成開發(fā)環(huán)境，可提供編輯C語言，C+以及C+/CLI語言等可視化集成編程系統(tǒng)。它不但具有程序框架自動生成、靈活方便的類管理、代碼編寫和界面設計集成交互操作、可開發(fā)多種程序等優(yōu)點，而且通過簡單的設置就可使其生成的程序框架支持數(shù)據(jù)庫接口、OLE2，WinSock網(wǎng)絡、3D控制界面。 本課程實驗要求學生運用C語言編

2、程完成數(shù)據(jù)構(gòu)造課程中抽象數(shù)據(jù)類型及排序算法的編程實現(xiàn)，加深對教學內(nèi)容的理解。實驗目的：加深對抽象數(shù)據(jù)類型ADT表的理解；實驗原理：參照課本p.44-49，及Figure3.6-3.13.實驗內(nèi)容：編寫程序?qū)崿F(xiàn)ADT表的定義，及常用操作：判斷表是否為空；獲取第i個節(jié)點的內(nèi)容刪除插入實驗要求：1復習C語言相關知識；2實現(xiàn)完整的ADT表構(gòu)造及操作，并給出應用。實驗源程序：#include stdafx.h #include stdio.h #include stdlib.h #include malloc.htypedef struct node int data; struct node *pNe

3、xt; /pNext為指向下一個節(jié)點的指針Node,*pNode; pNode CreateLinkList(); /創(chuàng)立鏈表函數(shù)bool IsEmpty(pNode); /定義IsEmpty(pNode)為布爾值，判斷鏈表是否為空int FindTheNode(pNode pHead,int a,int length); /找出某一個節(jié)點的值void TraverseLinkList(pNode pHead); /遍歷鏈表，獲取鏈表中的數(shù)值int GetLengthLinklist(pNode pHead);/獲取鏈表長度int Delete(pNode pHead,int x) ;/刪除元

4、素int Insert(pNode pHead,int b,int c);/插入元素void FreeLinkList(pNode pHead); /釋放鏈表空間/int main() /主函數(shù) int a,b,c,x,length; pNode pHead = NULL; /初始化頭節(jié)點pHead為NULL pHead = CreateLinkList(); / 創(chuàng)立一個非循環(huán)單鏈表，并將該鏈表的頭結(jié)點的地址賦給pHeadif (IsEmpty(pHead) / 判斷鏈表是否為空 printf (鏈表為空！n); return 0;else TraverseLinkList(pHead);

5、/遍歷鏈表 printf (鏈表為非空！n); length=GetLengthLinklist(pHead);/獲取鏈表長度while(1) printf(獲取第i個節(jié)點的內(nèi)容，i=); scanf(%d,&a);if(FindTheNode(pHead,a,length)break; /找出第i個節(jié)點的值while(1) printf(請輸入要刪除的元素:); scanf(%d,&x); if(Delete(pHead,x) /在鏈表中將元素x刪除 printf(刪除元素%d后,x);break; printf(未找到該元素，刪除失敗n); TraverseLinkList(pHead);

6、while(1) printf(請輸入插入節(jié)點的位置:); scanf(%d,&b); printf(請輸入插入節(jié)點的數(shù)值:); scanf(%d,&c);if(Insert(pHead,b,c) /在鏈表中插入元素printf(在位置%d插入元素%d后,b,c);break;printf(未找到該位置，插入失敗n);TraverseLinkList(pHead);FreeLinkList(pHead); /釋放鏈表空間 return 0; /pNode CreateLinkList() /創(chuàng)立鏈表函數(shù) int LEN,a; pNode pHead = (pNode)malloc(sizeof

7、(Node); /動態(tài)分配內(nèi)存 pNode pTail = pHead; pTail-pNext = NULL; /令鏈尾指向NULL printf(請輸入創(chuàng)立的單向鏈表的節(jié)點個數(shù):); scanf(%d,&LEN); for(int i = 0; i data = a; pTail-pNext = pNew; /pTail中的指針pNext指向pNew pNew-pNext = NULL; pTail = pNew; /新建的節(jié)點變?yōu)殒溛?return pHead; /bool IsEmpty(pNode pHead) / 判斷列表是否為空 return pHead-pNext=NULL;

8、/int FindTheNode(pNode pHead,int a,int length) /找出某一個節(jié)點的值 if(alength)/判斷要查找的節(jié)點位置是否正確 printf(鏈表中沒有此節(jié)點n);return 0;else pNode p = pHead-pNext; for(int i = 0; i data);/當找到該節(jié)點時輸出它的值 p = p-pNext; printf(n); return 1; /void TraverseLinkList(pNode pHead)/遍歷鏈表，獲取鏈表中的數(shù)值 printf(鏈表中各節(jié)點的值依次為：); pNode p = pHead-p

9、Next; while(p!=NULL) /知道最后一個節(jié)點循環(huán)才停頓 printf(%d ,p-data); p = p-pNext; printf(n); /int GetLengthLinklist(pNode pHead)/獲取鏈表長度 int length=0; pNode p=pHead-pNext; while(p!=NULL) length+; p = p-pNext; return length;/int Delete(pNode pHead,int x) /刪除元素 pNode p,q; q=p=pHead; p=p-pNext; /p指向頭結(jié)點后第一個元素while(p)

10、 if(p-data=x) /找到要刪除的元素 q-pNext=p-pNext; free(p); /釋放該元素所在節(jié)點的空間 return 1; else q=p; /q始終指向p上一個節(jié)點 p=p-pNext; return 0; /int Insert(pNode pHead,int b,int c)/插入元素 pNode p,q; q=p=pHead; p=p-pNext; if(b0 & bi;i+) q=p; /q始終指向p上一個節(jié)點 p=p-pNext; pNode pNew = (pNode)malloc(sizeof(Node); /創(chuàng)立新節(jié)點并動態(tài)分配內(nèi)存 pNew-dat

11、a=c; pNew-pNext=p; q-pNext=pNew; return 1;else return 0;/void FreeLinkList(pNode pHead) /釋放鏈表空間 pNode p,q ; p=pHead-pNext; while (p != NULL) q=p-pNext; free(p); /釋放各節(jié)點的空間p=q; pHead-pNext=NULL;實驗結(jié)果：1)判斷表是否為空= 1 * GB3創(chuàng)立鏈表，鏈表不為空。鏈表為空。2獲取第i個節(jié)點的內(nèi)容輸入要求獲取的節(jié)點內(nèi)容的位置正確，比方i=2，那么得到第2個節(jié)點的內(nèi)容為22。輸入要求獲取的節(jié)點內(nèi)容的位置不在鏈表中，比方i=8，那么顯示鏈表中沒有此節(jié)點。假設輸入節(jié)點位置不在鏈表中，那么需繼續(xù)輸入正確位置，不然系統(tǒng)會一直要求輸入節(jié)點i的值直到我們輸入正確的節(jié)點位置。3刪除輸入要刪除的元素在鏈表中，比方刪除元素44，那么鏈表中剩下的元素有11、22、33、55、66.假設輸入要刪除的元素不在鏈表中，比方要刪除元素77，那么顯示未找到該元素，刪除失敗。假設輸入要刪除的元素不在鏈表中，那么需繼續(xù)輸入在鏈