【文章內(nèi)容簡介】 sdata = x。 } else { for (j = 1。 j i 1。 j++) p = pnext。 s = (snode *)malloc(sizeof(snode))。 snext = pnext。 pnext = s。 sdata = x。 } 數(shù)據(jù)結(jié)構(gòu) 與算法分析 課程設(shè)計 15 return 1。 } int delnode(snode *head, int i)//刪除鏈表中第 i 個結(jié)點 { snode *p = headnext, *q = head。 if(i 1 || i length(head)) return 0。 else if (i == 1) { headnext = pnext。 free(p)。 } else { for (int j = 1。 j i。 j++) { p = pnext。 q = qnext。 } qnext = pnext。 free(p)。 } return 1。 數(shù)據(jù)結(jié)構(gòu) 與算法分析 課程設(shè)計 16 } void sort(snode *head) //把鏈表中每個結(jié)點的值按從小到大排列 { snode *p, *q。 int k。 for(p = headnext。 p != NULL。 p = pnext) for(q = pnext。 q != NULL。 q = qnext) if (pdata qdata) { k = pdata。 pdata = qdata。 qdata = k。 } } void insert(snode *head, int x) //在有序鏈表中插入 x,插入后仍保持有序 { snode *p = headnext, *s, *q = head。 while (p != NULL amp。amp。 pdata x) { q = qnext。 p = pnext。 數(shù)據(jù)結(jié)構(gòu) 與算法分析 課程設(shè)計 17 } s = (snode *)malloc(sizeof(snode))。 snext = qnext。 sdata = x。 qnext = s。 } void del_min_max(snode *head, int min, int max) //刪除有序鏈表中值 min 到值 max 中的結(jié)點 { snode *p = headnext, *q = head。 while (p != NULL amp。amp。 pdata = min) { q = p。 p = pnext。 } while (p != NULL amp。amp。 pdata max) { qnext = pnext。 free(p)。 p = qnext。 } } 數(shù)據(jù)結(jié)構(gòu) 與算法分析 課程設(shè)計 18 void del_min(snode *head) { snode *p = headnext, *q = head。 snode *p_min, *q_min。 p_min = p。 q_min = q。 while (p != NULL) { q = p。 p = pnext。 if (p != NULL amp。amp。 pdata p_mindata) { q_min = p_min。 p_min = p。 } } q_minnext = p_minnext。 free(p_min)。 } int main() { int min, max。 snode *headl = creat()。 //創(chuàng)建鏈表 數(shù)據(jù)結(jié)構(gòu) 與算法分析 課程設(shè)計 19 printf(最初的鏈表如下： )。 display(headl)。 printf(\n\n)。 int num, location。 printf(請輸入您要查找的數(shù)： )。 scanf(%d, amp。num)。 if (locate(headl, num)) printf(數(shù)字 %d 在鏈表中的位置為： %d\n\n, num, locate(headl, num))。 else printf(數(shù)字 %d 在鏈表中不存在 !\n\n, num)。 printf(請分別輸入您要插入到鏈表中的數(shù)以及想插入的位置（用空格號間隔開）： )。 scanf(%d %d, amp。num, amp。location)。 if (insnode(headl, num, location)) { printf(插入新值以后的鏈表如下： )。 display(headl)。 printf(\n\n)。 } else printf(輸入有誤 !\n\n)。 printf(請輸入您想刪除的結(jié)點位置： )。 數(shù)據(jù)結(jié)構(gòu) 與算法分析 課程設(shè)計 20 scanf(%d, amp。location)。 if (delnode(headl, location)) { printf(刪除第 %d 個結(jié)點后的鏈表如下： , location)。 display(headl)。 printf(\n\n)。 } else printf(輸入有誤 ! \n\n)。 } 【運 行截圖演示】 ①、如下面的運行截圖所示，創(chuàng)建帶有頭結(jié)點且長度為 8 的單鏈表： 1。 輸入要查詢的數(shù)“ 6”，則查詢到單鏈表中數(shù)“ 6”的存儲位置為“ 5”的下標(biāo)號。 輸入要插入的數(shù)和插入數(shù)的位置下標(biāo)，便可以進(jìn)行插入操作。程序中要求插入 的 數(shù)是“ 3”，插入數(shù)的位置下標(biāo)為“ 5”，兩者之間用空格號隔開，則插入后的新單鏈表為： 1。 同理當(dāng)輸入要執(zhí)行刪除操作的數(shù)位置下標(biāo)，可以對該數(shù)刪除出線數(shù)據(jù)結(jié)構(gòu) 與算法分析 課程設(shè)計 21 性表。程序中要求刪除的數(shù) 下標(biāo)是 7，則執(zhí)行該刪除操作之后的新單鏈表為 ： 1。 ②、 如下面的運行截圖所示，創(chuàng)建帶有頭結(jié)點且長度為 8 的單鏈表，要查詢的數(shù)“ 3”不在該單鏈表中，所以程序執(zhí)行“ error”。 數(shù)據(jù)結(jié)構(gòu) 與算法分析 課程設(shè)計 22 ③、 如下面的運行截圖所示，創(chuàng)建帶頭結(jié)點且長度為 8 的單鏈表，要插入數(shù) 的 位置下標(biāo)“ 1”不在該單鏈表中，所以程序執(zhí)行“ error”。 ④ 、 如下面的運行截圖所示，創(chuàng)建帶頭結(jié)點且長度為 8 的單鏈表，要插入的 位置下標(biāo)“ 9” 為 單鏈表 最大 長度 ，所以程序執(zhí)行插入 操作。 數(shù)據(jù)結(jié)構(gòu) 與算法分析 課程設(shè)計 23 ⑤ 、 如下面的運行截圖所示，創(chuàng)建帶頭結(jié)點且長度為 8 的單鏈表，要插入的 位置下標(biāo)“ 10”超出單鏈表長度，所以程序不執(zhí)行 插入 操作。 ⑥ 、 如下面的運行截圖所示，創(chuàng)建帶頭結(jié)點且長度為 8 的單鏈表，要 刪除 數(shù) 的 位置下標(biāo)“ 2”不在該單鏈表中，所以程序執(zhí)行“ error”。 數(shù)據(jù)結(jié)構(gòu) 與算法分析 課程設(shè)計 24 ⑦ 、 如下面的運行截圖所示，創(chuàng)建帶頭結(jié)點且長度為 8 的單鏈表，要刪除數(shù) 的 位置下標(biāo)“ 10”超出單鏈表長度，所以程序執(zhí)行“ error”。 數(shù)據(jù)結(jié)構(gòu) 與算法分析 課程設(shè)計 25 三、 順序棧的操作 在順序棧上實現(xiàn)將非負(fù)十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)。 【 數(shù)值轉(zhuǎn)換 原理】 十進(jìn)制數(shù) N 和其他 d 進(jìn)制數(shù)的轉(zhuǎn)換 時計算機(jī)實現(xiàn)計算的基本問題，其解決方法很多，其中一個簡單算法基 于下列原理： ( ) m odN N di v d d N d? ? ? ? ? ? ? （其中： div 為整除運算， mod 為求余運算） 假設(shè)現(xiàn)在要編制一個滿足下列要求的程序：對于輸入的任意一個非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的二進(jìn)制數(shù)。 由于上述計算過程是從低位到高位順序產(chǎn)生二進(jìn)制數(shù)的各個數(shù)位，而打印