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

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

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

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

5、立n);據n);序n);據n);據n);f(f(f(f(f(f(據除出出n);f(=n);f(請選擇0-5:n);for(;)scanf(%d,&sn); if (sn5)prf(nt 輸入錯誤，重選0-5n); elsebreak;return sn;/*主函數*/ 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(添加數據n);prf(請輸入要

6、的位置：n); fflush(stdin);scanf(%d,&k); insert_list(pHead, k); traverse_list(pHead); break;case 3:prf(*n); prf(數 據 排 序n);prf(*n); sort_list(pHead);traverse_list(pHead); break;case 4:prf(*n); prf(刪除數據n);prf(*n); prf(請輸入要刪除的位置：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(輸出所有數據n);prf(*n); traverse_list(pHead);break; case 0:prf(再見！n); getchar();return;/*建立鏈表*/ PNODE create_list(void)len;/用來存放有效節點的個數 i;val; /用來臨時存放用戶輸入的結點的值 PNODE pHead = (PNODE)malloc(sizeof(NODE); if (NULL = pHead)

8、prf(分配失敗, 程序終止!n); exit(-1);PNODE pTail = pHead; pTail-pNext = NULL;prf(請輸入您需要生成的鏈表節點的個數: 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;/*鏈表求長*/ 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 所指向鏈表的第個節點的前面一個新的結點，該節點的值是 val，并且的值是從1開始/*元素*/void insert_list(PNODE pHead,i = 0;PNODE p = pHead;while (NULL!=p & ipNext;+i;)if (i-1 | NULL=p)prf(錯誤n);/分配新的結點PNODE pNew = (PNODE

11、)malloc(sizeof(NODE); if (NULL = pNew)prf(動態分配內存失敗!n); exit(-1);prf(請輸入一個數據n); scanf(%d,&pNew-data) ;/將新的結點存入 p 節點的后面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 指向待刪除的結點*pVal = q-data;/刪除 p 節點后面的結點p-pNext = p-pNext-pNext;/q 所指向的節點所占的內存free(q);q = NULL;return true;窗口運行結果為;=1.鏈 表 建 立2.數 據數刪輸0.退據除出出排數數序據據=請選擇0-5:1*鏈表的建立*請輸入您需要生成的鏈表節點的個數: len = 10請輸入第1個節點的值:請輸入第2個節點的值:請輸入第3個節點的值:請輸入第4個節點的值:請輸入第5個節點的值:請輸入第6個節點的值:請輸入第7個節點的值:請輸入第8個

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