第一次上機(jī)實(shí)驗(yàn)鏈表

1、第一次上機(jī)實(shí)驗(yàn)一、 上機(jī)實(shí)驗(yàn)題目針對(duì)線性表、棧、隊(duì)列，編程實(shí)現(xiàn)選擇順序和鏈?zhǔn)浇Y(jié)構(gòu)下數(shù)據(jù)結(jié)構(gòu)建立、元素、刪除等基本操作，并演示實(shí)際例子運(yùn)行結(jié)果。二、相關(guān)技術(shù)或知識(shí)依靠鏈表實(shí)現(xiàn)對(duì)對(duì)象的處理，并通過對(duì)子函數(shù)的調(diào)用實(shí)現(xiàn)各子功能，例如在線性表中和刪除元素，棧的出入棧操作和隊(duì)列的進(jìn)隊(duì)出隊(duì)操作。三、算法及數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)設(shè)線性表采用帶表頭附加結(jié)點(diǎn)的單鏈表結(jié)構(gòu)，編寫線性表抽象數(shù)據(jù)類型各基本操作的實(shí)現(xiàn)函數(shù)。同時(shí)建立一個(gè)驗(yàn)證操作實(shí)現(xiàn)的主函數(shù)文件“鏈表.cpp”，編譯并調(diào)試程序，直到正確運(yùn)行。提示： 單向鏈表的結(jié)構(gòu)定義如下：typedef struct Nodedata; /數(shù)據(jù)域struct Node * pNext

2、; /指針域NODE 為線性表設(shè)計(jì)基本操作：PNODE create_list(void);/創(chuàng)建鏈表/遍歷鏈表/判斷鏈表是否為空/求鏈表長(zhǎng)度/*在 pHead 所指向鏈表void booltraverse_list(PNODE pHead); is_empty(PNODE pHead); length_list(PNODE); insert_list(PNODE pHead,void);的第個(gè)節(jié)點(diǎn)的前面一個(gè)新的結(jié)點(diǎn)，該節(jié)點(diǎn)的值是 val， 并且的值是從 1 開始*/bool delete_list(PNODE pHead,* pVal);/*刪除鏈表第個(gè)節(jié)點(diǎn)，并將刪除的結(jié)點(diǎn)的值存入 pVal

3、 所指向的變量中, 并且的值是從 1 開始*/void sort_list(PNODE);/對(duì)鏈表進(jìn)行排序四、上機(jī)環(huán)境上機(jī)環(huán)境：VC 6.0五、源程序和運(yùn)行結(jié)果源程序：# include # include # include typedef struct Node使用語(yǔ)言： C操作系統(tǒng)：win7 旗艦版data; /數(shù)據(jù)域struct Node * pNext; /指針域NODE, *PNODE;/函數(shù)PNODE create_list(void);/創(chuàng)建鏈表void traverse_list(PNODE pHead);/遍歷鏈表bool is_empty(PNODE pHead);/判斷

4、鏈表是否為空 length_list(PNODE);/求鏈表長(zhǎng)度);/*在 pHead 所指向鏈表的第個(gè)節(jié)點(diǎn)的前面插void insert_list(PNODE pHead,入一個(gè)新的結(jié)點(diǎn)，該節(jié)點(diǎn)的值是 val， 并且的值是從1開始*/bool delete_list(PNODE pHead,* pVal);/*刪除鏈表第個(gè)節(jié)點(diǎn)，并將刪除,的結(jié)點(diǎn)的值存入 pVal 所指向的變量中,并且的值是從1開始*/void sort_list(PNODE);/對(duì)鏈表進(jìn)行排序/*主界面*/_select()sn;prpr pr pr pr pr pr pr prf(=n);1.鏈2.數(shù)刪輸0.退表建數(shù)排數(shù)數(shù)

5、立n);據(jù)n);序n);據(jù)n);據(jù)n);f(f(f(f(f(f(據(jù)除出出n);f(=n);f(請(qǐng)選擇0-5:n);for(;)scanf(%d,&sn); if (sn5)prf(nt 輸入錯(cuò)誤，重選0-5n); elsebreak;return sn;/*主函數(shù)*/ void main()PNODE pHead = NULL;val; j,k;while(1) switenu_select()case 1:pr pr prf(*n);鏈表的建立f(n);f(*n);pHead = create_list();break; case 2:prf(*n); prf(添加數(shù)據(jù)n);prf(請(qǐng)輸入要

6、的位置：n); fflush(stdin);scanf(%d,&k); insert_list(pHead, k); traverse_list(pHead); break;case 3:prf(*n); prf(數(shù) 據(jù) 排 序n);prf(*n); sort_list(pHead);traverse_list(pHead); break;case 4:prf(*n); prf(刪除數(shù)據(jù)n);prf(*n); prf(請(qǐng)輸入要?jiǎng)h除的位置：n);fflush(stdin); scanf(%d,&j);if ( delete_list(pHead, j ,&val) )prf(刪除成功，您刪除的元

7、素是: %dn, val);elseprf(刪除失敗!您刪除的元素不存在!n);traverse_list(pHead);break;case 5:prf(*n); prf(輸出所有數(shù)據(jù)n);prf(*n); traverse_list(pHead);break; case 0:prf(再見！n); getchar();return;/*建立鏈表*/ PNODE create_list(void)len;/用來存放有效節(jié)點(diǎn)的個(gè)數(shù) i;val; /用來臨時(shí)存放用戶輸入的結(jié)點(diǎn)的值 PNODE pHead = (PNODE)malloc(sizeof(NODE); if (NULL = pHead)

8、prf(分配失敗, 程序終止!n); exit(-1);PNODE pTail = pHead; pTail-pNext = NULL;prf(請(qǐng)輸入您需要生成的鏈表節(jié)點(diǎn)的個(gè)數(shù): len = ); scanf(%d, &len);for (i=0; idata = val; pTail-pNext = pNew; pNew-pNext = NULL; pTail = pNew;return pHead;/*遍歷鏈表*/ void traverse_list(PNODE pHead)PNODE p = pHead-pNext; while (NULL != p)prf(%d, p-data);

9、p = p-pNext;prf(n); return;bool is_empty(PNODE pHead)if (NULL = pHead-pNext) return true;elsereturn false;/*鏈表求長(zhǎng)*/ length_list(PNODE pHead)PNODE p = pHead-pNext; len = 0;while (NULL != p)+len;p = p-pNext;return len;/*鏈表排序*/ void sort_list(PNODE pHead)i, j, t;len = length_list(pHead); PNODE p, q;for

10、(i=0,p=pHead-pNext; ipNext)for (j=i+1,q=p-pNext; jdata q-data)t = p-data;p-data = q-data;q-data = t;-pNext)return;/在 pHead 所指向鏈表的第個(gè)節(jié)點(diǎn)的前面一個(gè)新的結(jié)點(diǎn)，該節(jié)點(diǎn)的值是 val，并且的值是從1開始/*元素*/void insert_list(PNODE pHead,i = 0;PNODE p = pHead;while (NULL!=p & ipNext;+i;)if (i-1 | NULL=p)prf(錯(cuò)誤n);/分配新的結(jié)點(diǎn)PNODE pNew = (PNODE

11、)malloc(sizeof(NODE); if (NULL = pNew)prf(動(dòng)態(tài)分配內(nèi)存失敗!n); exit(-1);prf(請(qǐng)輸入一個(gè)數(shù)據(jù)n); scanf(%d,&pNew-data) ;/將新的結(jié)點(diǎn)存入 p 節(jié)點(diǎn)的后面PNODE q = p-pNext; p-pNext = pNew; pNew-pNext = q;prf(成功n);/*元素刪除*/bool delete_list(PNODE pHead,i = 0;PNODE p = pHead;,* pVal)while (NULL!=p-pNext & ipNext;+i;if (i-1 | NULL=p-pNext)r

12、eturn false;PNODE q = p-pNext;/q 指向待刪除的結(jié)點(diǎn)*pVal = q-data;/刪除 p 節(jié)點(diǎn)后面的結(jié)點(diǎn)p-pNext = p-pNext-pNext;/q 所指向的節(jié)點(diǎn)所占的內(nèi)存free(q);q = NULL;return true;窗口運(yùn)行結(jié)果為;=1.鏈 表 建 立2.數(shù) 據(jù)數(shù)刪輸0.退據(jù)除出出排數(shù)數(shù)序據(jù)據(jù)=請(qǐng)選擇0-5:1*鏈表的建立*請(qǐng)輸入您需要生成的鏈表節(jié)點(diǎn)的個(gè)數(shù): len = 10請(qǐng)輸入第1個(gè)節(jié)點(diǎn)的值:請(qǐng)輸入第2個(gè)節(jié)點(diǎn)的值:請(qǐng)輸入第3個(gè)節(jié)點(diǎn)的值:請(qǐng)輸入第4個(gè)節(jié)點(diǎn)的值:請(qǐng)輸入第5個(gè)節(jié)點(diǎn)的值:請(qǐng)輸入第6個(gè)節(jié)點(diǎn)的值:請(qǐng)輸入第7個(gè)節(jié)點(diǎn)的值:請(qǐng)輸入第8個(gè)

13、節(jié)點(diǎn)的值:請(qǐng)輸入第9個(gè)節(jié)點(diǎn)的值:1223432214543653414請(qǐng)輸入第10個(gè)節(jié)點(diǎn)的值: 123=1.鏈2.數(shù)刪輸0.退表建數(shù)排數(shù)數(shù)立據(jù)序據(jù)據(jù)據(jù)除出出=請(qǐng)選擇0-5:5*輸出所有數(shù)據(jù)* 12 23 432 21 45 43 65 34 14 123=1.鏈2.數(shù)刪輸0.退表建數(shù)排數(shù)數(shù)立據(jù)序據(jù)據(jù)據(jù)除出出=請(qǐng)選擇0-5:3*數(shù) 據(jù) 排 序* 12 14 21 23 34 43 45 65 123 432=1.鏈2.數(shù)刪輸0.退表建數(shù)排數(shù)數(shù)立據(jù)序據(jù)據(jù)據(jù)除出出=請(qǐng)選擇0-5:4*刪除數(shù)據(jù)*請(qǐng)輸入要?jiǎng)h除的位置：3刪除成功，您刪除的元素是: 2112 14 23 34 43 45 65 123 432=1.鏈2.數(shù)刪輸0.退表建數(shù)排數(shù)數(shù)立據(jù)序據(jù)據(jù)據(jù)除出出=請(qǐng)選擇0-5:2*添加數(shù)據(jù)請(qǐng)輸入要6的位置：請(qǐng)輸入一個(gè)數(shù)據(jù)1234成功12 14 23 34 43 1234 45 65 123 432=1.鏈2.3.數(shù)表建數(shù)排立據(jù)序據(jù)刪輸0.退除 數(shù) 據(jù)出 數(shù) 據(jù)