![算法與數(shù)據(jù)結(jié)構(gòu)C語言版課后習(xí)題答案(機械工業(yè)出版社)第1章-緒論-習(xí)題參考答案課案_第1頁](http://file2.renrendoc.com/fileroot_temp3/2021-6/11/37d6e404-a019-4dd8-ba5d-2be99644f025/37d6e404-a019-4dd8-ba5d-2be99644f0251.gif)
![算法與數(shù)據(jù)結(jié)構(gòu)C語言版課后習(xí)題答案(機械工業(yè)出版社)第1章-緒論-習(xí)題參考答案課案_第2頁](http://file2.renrendoc.com/fileroot_temp3/2021-6/11/37d6e404-a019-4dd8-ba5d-2be99644f025/37d6e404-a019-4dd8-ba5d-2be99644f0252.gif)
![算法與數(shù)據(jù)結(jié)構(gòu)C語言版課后習(xí)題答案(機械工業(yè)出版社)第1章-緒論-習(xí)題參考答案課案_第3頁](http://file2.renrendoc.com/fileroot_temp3/2021-6/11/37d6e404-a019-4dd8-ba5d-2be99644f025/37d6e404-a019-4dd8-ba5d-2be99644f0253.gif)
![算法與數(shù)據(jù)結(jié)構(gòu)C語言版課后習(xí)題答案(機械工業(yè)出版社)第1章-緒論-習(xí)題參考答案課案_第4頁](http://file2.renrendoc.com/fileroot_temp3/2021-6/11/37d6e404-a019-4dd8-ba5d-2be99644f025/37d6e404-a019-4dd8-ba5d-2be99644f0254.gif)
![算法與數(shù)據(jù)結(jié)構(gòu)C語言版課后習(xí)題答案(機械工業(yè)出版社)第1章-緒論-習(xí)題參考答案課案_第5頁](http://file2.renrendoc.com/fileroot_temp3/2021-6/11/37d6e404-a019-4dd8-ba5d-2be99644f025/37d6e404-a019-4dd8-ba5d-2be99644f0255.gif)
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、第1章 概論 習(xí)題參考答案、基礎(chǔ)知識題1. 簡述下列概念數(shù)據(jù),數(shù)據(jù)元素,數(shù)據(jù)類型,數(shù)據(jù)結(jié)構(gòu),邏輯結(jié)構(gòu),存儲結(jié)構(gòu),算法?!窘獯稹繑?shù)據(jù)是信息的載體,是描述客觀事物的數(shù)、字符,以及所有能輸入到計 算機中并被計算機程序識別和處理的符號的集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。 在不同的條件下,數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄等。數(shù)據(jù)類型是對數(shù)據(jù)的取值范圍、數(shù)據(jù)元素之間的結(jié)構(gòu)以及允許施加操作的一種總 體描述。每一種計算機程序設(shè)計語言都定義有自己的數(shù)據(jù)類型?!皵?shù)據(jù)結(jié)構(gòu)”這一術(shù)語有兩種含義,一是作為一門課程的名稱;二是作為一個科 學(xué)的概念。作為科學(xué)概念,目前尚無公認(rèn)定義,一般認(rèn)為,討論數(shù)據(jù)結(jié)構(gòu)要包括 三個方面
2、,一是數(shù)據(jù)的邏輯結(jié)構(gòu),二是數(shù)據(jù)的存儲結(jié)構(gòu),三是對數(shù)據(jù)進(jìn)行的操作(運算)。而數(shù)據(jù)類型是值的集合和操作的集合, 可以看作是已實現(xiàn)了的數(shù)據(jù)結(jié) 構(gòu),后者是前者的一種簡化情況。數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系(即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”),數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示,包括數(shù)據(jù)元素 的表示及其關(guān)系的表示。數(shù)據(jù)的運算是對數(shù)據(jù)定義的一組操作,運算是定義在邏 輯結(jié)構(gòu)上的,和存儲結(jié)構(gòu)無關(guān),而運算的實現(xiàn)則依賴于存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計算機中的表示稱為物理結(jié)構(gòu), 又稱存儲結(jié)構(gòu)。是邏輯結(jié)構(gòu)在存儲器 中的映像,包括數(shù)據(jù)元素的表示和關(guān)系的表示。邏輯結(jié)構(gòu)與計算機無關(guān)。算法是對特定問題求解步驟的
3、一種描述,是指令的有限序列。其中每一條指令表 示一個或多個操作。一個算法應(yīng)該具有下列特性:有窮性、確定性、可行性、輸 入和輸出。2. 數(shù)據(jù)的邏輯結(jié)構(gòu)分哪幾種,為什么說邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面?【解答】數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。(也可以分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形即網(wǎng)狀結(jié)構(gòu))。邏輯結(jié)構(gòu)是數(shù)據(jù)組織的某種“本質(zhì)性”的東西:(1)邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)。(2)邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對位置無關(guān)。(3)邏輯結(jié)構(gòu)與所含數(shù)據(jù)元素的個數(shù)無關(guān)。3. 試舉一個數(shù)據(jù)結(jié)構(gòu)的例子,敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三方面的內(nèi)容?!窘獯稹咳鐚W(xué)生成績表,邏輯結(jié)構(gòu)是線性結(jié)構(gòu),可以順序存儲(也
4、可以鏈?zhǔn)酱鎯Γ?,運算可以有插入、刪除、查詢、等等。4. 簡述算法的五個特性,對算法設(shè)計的要求?!窘獯稹克惴ǖ奈鍌€特性是:有窮性、確定性、可行性、零至多個輸入和一 至多個輸出。對算法設(shè)計的要求:正確性,易讀性,健壯性,和高的時空間效率(運算速度快, 存儲空間小)。5. 設(shè)n是正整數(shù),求下列程序段中帶 己號的語句的執(zhí)行次數(shù)。(1)i=1;k=0; i=1;j=0;while (in)while (i+jj)j+;else i+; x=y=0;(4)x=91;y=100;for (i=0;i0)for (j=0;j100)x+;x=x-10; y-;for (k=0;kn;k+) y+;else x
5、+;【解答】(1)n-1(2)n為偶數(shù)時,均為n div 2;你為奇數(shù)時,分別為:(n div 2)+1 和n div 2(3) n+1, n(n+1), n2,(n+1)n 2, n 3(4) 100, 10006. 有實現(xiàn)同一功能的兩個算法 A1和A2,其中A1的時間復(fù)雜度為Tl=O(2n),A2 的時間復(fù)雜度為T2=O(m,僅就時間復(fù)雜度而言,請具體分析這兩個算法哪 一個好?【解答】對算法A1和A2的時間復(fù)雜度T1和T2取對數(shù),得nlog2和2logn。顯 然,當(dāng)n4 時,算法A2好于A1。7. 選擇題:算法分析的目的是()A、找出數(shù)據(jù)結(jié)構(gòu)的合理性B、研究算法中的輸入和輸出的關(guān)系C、分析
6、算法的效率以求改進(jìn)D 、分析算法的易懂性和文檔特點【解答】C二、算法設(shè)計題8. 已知輸入x,y,z三個不相等的整數(shù),設(shè)計一個“高效”算法,使得這三個 數(shù)按從小到大輸出?!案咝А钡暮x是用最少的元素比較次數(shù)、元素移動次數(shù)和輸出次數(shù)。void Best() /按序輸出三個整數(shù)的優(yōu)化算法int a,b,c,t;sca nf( “ d%d%d,&a,&b,&c);if(ab)t=a; a=b; b=t: /a和 b 已正序if(bc)t=c; c=b;/c已到位if(at) b=a; a=t; /a和 b 已正序else b=t;/ifprintf( “%d,%d,%dn ,a,b,c);/最佳2次比
7、較,無移動;最差3次比較,7個賦值9 在數(shù)組An中查找值為k的元素,若找到則輸出其位置i(1 i =1)&(Ai!=k) i-;if(i=1) return i;else return 0;當(dāng)查找不成功時,總的比較次數(shù)為 n+1次,所以最壞情況下時間復(fù)雜度為 0( n)。第2章線性表習(xí)題參考答案一、基礎(chǔ)知識題2.1試述頭指針、頭結(jié)點、元素結(jié)點、首元結(jié)點的區(qū)別,說明頭指針和頭結(jié)點的作【解答】指向鏈表第一個結(jié)點(或為頭結(jié)點或為首元結(jié)點)的指針稱為頭指針。“頭指針”具有標(biāo)識一個鏈表的作用,所以經(jīng)常用頭指針代表鏈表的名字,如鏈表L既是指鏈表的名字是L,也是指鏈表的第一個結(jié)點的地址存儲在指針變量L中,頭
8、指針為“ NULL ”則表示一個空表。有時,我們在整個線性鏈表的第一個元素結(jié)點之前加入一個結(jié)點,稱為頭結(jié)點,它的數(shù)據(jù)域可以不存儲任何信息(也可以做監(jiān)視哨或存放線性表的長度等附加信息),指針域中存放的是第一個數(shù)據(jù)結(jié)點的地址,空表時為空?!邦^結(jié)點”的加入,使插入和刪除等操作方便統(tǒng)。元素結(jié)點即是數(shù)據(jù)結(jié)點,至少包括元素自身信息和其后繼元素的地址兩個域。首元結(jié)點是指鏈表中第一個數(shù)據(jù)元素的結(jié)點;為了操作方便,通常在鏈表的首元結(jié)點之前附設(shè)一個結(jié)點,稱為頭結(jié)點。2.2分析順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點,說明何時應(yīng)該利用何種結(jié)構(gòu)?!窘獯稹繌目臻g上來看,當(dāng)線性表的長度變化較大,難以估計其規(guī)模時,選用動態(tài)的鏈表
9、作為存儲結(jié)構(gòu)比較合適,但鏈表除了需要設(shè)置數(shù)據(jù)域外, 還要額外設(shè)置指針域,因此當(dāng)線性 表長度變化不大,易于事先確定規(guī)模時,為了節(jié)約存儲空間,宜采用順序存儲結(jié)構(gòu)。從時間上看,順序表具有按元素序號隨機訪問的特點,在順序表中按序號訪問數(shù)據(jù)元素的時間復(fù)雜度為 0(1);而鏈表中按序號訪問的時間復(fù)雜度為0(n)。所以如果經(jīng)常按序號訪問數(shù)據(jù)元素,使用順序表優(yōu)于鏈表。在順序表中做插入刪除操作時,平均移動大約表中一半的元素,因此n較大時順序表的插入和刪除效率低。在鏈表中作插入、刪除,雖然也要找插入位置,但操作主要是比較操作。從 這個角度考慮顯然鏈表優(yōu)于順序表??傊瑑煞N存儲結(jié)構(gòu)各有長短,選擇那一種存儲結(jié)構(gòu),由實
10、際問題中的主要因素決定。2.3分析在順序存儲結(jié)構(gòu)下插入和刪除結(jié)點時平均需要移動多少個結(jié)點?!窘獯稹科骄苿颖碇写蠹s一半的結(jié)點,插入操作平均移動 個結(jié)點,刪除操作平均移動個結(jié)點。具體移動的次數(shù)取決于表長和插入、刪除的結(jié)點的位置。2.4為什么在單循環(huán)鏈表中常使用尾指針,若只設(shè)頭指針,插入元素的時間復(fù)雜度如何?【解答】單循環(huán)鏈表中無論設(shè)置尾指針還是頭指針都可以遍歷表中任一個結(jié)點。設(shè)置尾指針時,若在表尾進(jìn)行插入元素或刪除第一元素,操作可在0(1)時間內(nèi)完成;若只設(shè)置頭指針,表尾進(jìn)行插入或刪除操作,需要遍歷整個鏈表,時間復(fù)雜度為0(n)。2.5在單鏈表、雙鏈表、單循環(huán)鏈表中,若知道指針p指向某結(jié)點,能否
11、刪除該結(jié)點,時間復(fù)雜度如何?【解答:】以上三種鏈表中,若知道指針p指向某結(jié)點,都能刪除該結(jié)點。雙鏈表刪除p所指向的結(jié)點的時間復(fù)雜度為0(1),而單鏈表和單循環(huán)鏈表上刪除p所指向的結(jié)點的時間復(fù)雜度均為0(n)。2.6下面算法的功能是什么?Lin kedList Unknown(Lin kedList la)LNode *q , *p;if(la & la- next)q=la; la=la-n ext; p=la; while(p-n ext) p=p-n ext;p-n ext=q; q-n ext =nu II;return la;【解答】將首元結(jié)點刪除并插入到表尾(設(shè)鏈表長度大于2.7選擇
12、題:在循環(huán)雙鏈表的*p結(jié)點之后插入*s結(jié)點的操作是(la、p-n ext=s;s-prior=p;p-n ext-prior=s;s-n ext=p-n ext;B、p-n ext=s; p-n ext-prior=s;s-prior=p;s-n ext=p-n ext;lc、s-prior=p; s-n ext=p-n ext;p-n ext:=s;p-n ext-prior=s;D、s-prior=p; sn ext=p n ext;pn ext-prior =s;p-n ext=s;【解答】D2.8選擇題:若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除 運算,則利用
13、()存儲方式最節(jié)省時間。D 單循環(huán)鏈表la.順序表B.雙鏈表lc.帶頭結(jié)點的雙循環(huán)鏈表【解答】la二、算法設(shè)計題將這兩2.9設(shè)ha和hb分別是兩個帶頭結(jié)點的非遞減有序單鏈表的頭指針,試設(shè)計算法, 個有序鏈表合并成一個非遞增有序的單鏈表。要求使用原鏈表空間,表中無重復(fù)數(shù)據(jù)?!绢}目分析】因為兩鏈表已按元素值非遞減次序排列,將其合并時,均從第一個結(jié)點起進(jìn)行比較,將小的鏈入鏈表中,同時后移鏈表工作指針,若遇值相同的元素,則刪除之。該問題 要求結(jié)果鏈表按元素值非遞增次序排列,故在合并的同時,將鏈表結(jié)點逆置。Lin kedList Union(Lin kedList ha,hb)/ ha,hb分別是帶頭結(jié)
14、點的兩個單鏈表的頭指針,鏈表中的元素值按遞增序排列/本算法將兩鏈表合并成一個按元素值遞減次序排列的單鏈表,并刪除重復(fù)元素 pa=ha-n ext;pb=hb-n ext;ha-n ext=n ull;/ pa是鏈表ha的工作指針/ pb是鏈表hb的工作指針/ ha作結(jié)果鏈表的頭指針,先將結(jié)果鏈表初始化為空/當(dāng)兩鏈表均不為空時作while(pa!=null & pb!=null)while(pa-n ext & pa-data=pa-n ext-data)u=pa-next; pa-next=u-next; free(u) 刪除 pa 鏈表中的重復(fù)元素while(pb-n ext & pb-da
15、ta=pb-n ext-data)u=pb-next; pb-next=u-next; free(u)/刪除 pb 鏈表中的重復(fù)元素if(pa-datadata)r=pa-n ext;pa-n ext=ha-n ext;ha-n ext=pa;/將pa的后繼結(jié)點暫存于r/將pa結(jié)點鏈于結(jié)果表中,同時逆置/恢復(fù)pa為當(dāng)前待比較結(jié)點pa=r;else if(pb-datadata)/將pb的后繼結(jié)點暫存于rr=pb-n ext;pb-n ext=ha-n ext; ha-n ext=pb;pb=r;/恢復(fù)pb為當(dāng)前待比較結(jié)點/將pb結(jié)點鏈于結(jié)果表中,同時逆置elseu=pb;pb=pb-next;
16、free(u) /刪除鏈表 pb 和 pa 中的重復(fù)元素/ while(pa!=null & pb!=null)if(pa) pb=pa;/避免再對pa寫下面的 while語句while(pb!=null)/將尚未到尾的表逆置到結(jié)果表中r=pb-n ext; pb-n ext=ha-n ext; ha-n ext=pb; pb=r; return ha /算法Union結(jié)束2.11 設(shè)p指向頭指針為la的單鏈表中某結(jié)點,試編寫算法,刪除結(jié)點*p的直接前驅(qū)結(jié)點。 【題目分析】設(shè)*p是單鏈表中某結(jié)點,刪除結(jié)點 *p的直接前驅(qū)結(jié)點,要找到*p的前驅(qū)結(jié)點 的前驅(qū) *pre。進(jìn)行如下操作: u=pre-
17、next; pre-next=u-next;free(u);LinkedList LinkedListDel(LinkedList la , LNode *p) /刪除單鏈表la上的結(jié)點*p的直接前驅(qū)結(jié)點,假定*p存在pre=la;if(pre-n ext=p)printf( “*p是鏈表第一結(jié)點,無前驅(qū) n”); exit(0) ; while(pre- next-next !=p)pre=pre-n ext;u=pre-n ext; pre-n ext=u-n ext; free(u);return(la); 2.12設(shè)計一算法,將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式,使這兩個多
18、項 式各自僅有奇次幕或偶次幕項,并要求利用原鏈表中的結(jié)點空間來構(gòu)造這兩個鏈表?!绢}目分析】設(shè)循環(huán)鏈表表示的多項式的結(jié)點結(jié)構(gòu)為:typedef struct nodeint power;幕float coef;/系數(shù)ElemType other;/其他信息struct n ode *n ext; /指向后繼的指針PNode,*PolyLi nkedList;則可以從第一個結(jié)點開始,根據(jù)結(jié)點的幕是奇數(shù)或偶數(shù)而將其插入到奇次幕或偶次幕項的鏈表中。假定用原鏈表保存偶次幕,要為奇次幕的鏈表生成一個表頭,為了保持鏈表中結(jié)點的原來順序,用一個指針指向奇次幕鏈表的表尾,注意鏈表分解時不能“斷鏈”。void P
19、olyDis(PolyLi nkedList poly)/將poly表示的多項式鏈表分解為各含奇次幕或偶次幕項的兩個循環(huán)鏈表PolyLi nkedList poly2=(PolyLi nkedList)malloc(sizeof(PNode);/ poly2表示只含奇次幕的多項式r2=poly2;/ r2是只含奇次幕的多項式鏈表的尾指針r仁poly;/ r1是只含偶次幕的多項式鏈表當(dāng)前結(jié)點的前驅(qū)結(jié)點的指針p=poly-next;/鏈表帶頭結(jié)點,p指向第一個元素while(p!=poly)if(p-power % 2) / 處理奇次幕r=p-n ext;/暫存后繼r2- next=p; /結(jié)點鏈
20、入奇次幕鏈表r2=p;/尾指針后移p=r;/恢復(fù)當(dāng)前待處理結(jié)點else /處理偶次幕r1- n ext=p; r1=p; p=p-n ext;r-n ext=poly2; r1- next=poly;/構(gòu)成循環(huán)鏈表 / PolyDis2.14設(shè)單向鏈表的頭指針為head,試設(shè)計算法,將鏈表按遞增的順序就地排序。【題目分析】本題中的“就地排序”,可理解為不另辟空間,這里利用直接插入原則把鏈表整理成遞增有序鏈表。Lin kedList Lin kListI nsertSort(L in kedList head)/ head是帶頭結(jié)點的單鏈表,本算法利用直接插入原則將鏈表整理成遞增的有序鏈表if(
21、head- next!=null)/鏈表不為空表p=head-next-next; / p指向第一結(jié)點的后繼head-n ext- n ext=n ull;/直接插入原則認(rèn)為第一元素有序,然后從第二元素起依次插入while(p!=null)r=p-next;/暫存p的后繼q=head;while(q-next & q-n ext-datadata)q=q-next; /查找插入位置p-next=q-next; /將 p結(jié)點鏈入鏈表q_n ext=p;p=r; 2.15已知遞增有序的三個單鏈表分別代表集合A , B和C,設(shè)計算法實現(xiàn) A=A U ( B n C),并使結(jié)果鏈表仍保持遞增。要求算法
22、的時間復(fù)雜度為O(|A|+|B|+|C|)。其中,|A|為集合A的元素個數(shù)?!绢}目分析】本題首先求B和C的交集,即求B和C中共有元素,再與 A求并集,同時刪除重復(fù)元素,以保持結(jié)果A遞增。Lin kedList un io n(Li nkedList A,B,C)/ A、B和C均是帶頭結(jié)點的遞增有序的單鏈表,本算法實現(xiàn)A=A U (B n C)/使結(jié)果表A保持遞增有序pa=A-n ext;pb=B-n ext;pc=C-n ext;設(shè)置三個工作指針pre=A; / pre指向結(jié)果鏈表中當(dāng)前待合并結(jié)點的前驅(qū)A-data=MaxElemType; /同類型元素最大值,起監(jiān)視哨作用while(pa |
23、 pb & pc)while(pb & pc)if(pb-datadata) pb=pb-n ext;else if(pb-datapc-data) pc=pc- n ext;else break; / B表和C表有公共元素if(pb & pc)while(pa & pa-datadata) /先將 A中小于B , C公共元素部分鏈入pre _n ext=pa;pre=pa;pa=pa-n ext;if(pre-data!=pb-data)pre _n ext=pb;pre=pb;pb=pb-n ext;pc=pc- n ext;elsepb=pb-n ext;pc=pc- n ext;/若A
24、中已有B , C公共元素,則不再存入結(jié)果表 / while(pa|pb&pc)if(pa) pre_n ext=pa;else pre-next =null;/當(dāng)B , C無公共元素,將 A中剩余鏈入 /算法Union結(jié)束2.16順序表la與lb非遞減有序,順序表空間足夠大。試設(shè)計一種高效算法,將lb中元素合到la中,使新的la的元素仍保持非遞減有序。高效指最大限度地避免移動元素?!绢}目分析】順序存儲結(jié)構(gòu)的線性表的插入,其時間復(fù)雜度為0(n),平均移動近一半的元素。線性表la和lb合并時,若從第一個元素開始,一定會造成元素后移,這不符合本題“高效算法”的要求。應(yīng)從線性表的最后一個元素開始比較,
25、大者放到最終位置上。設(shè)兩線性表的長度各為m和n ,則結(jié)果表的最后一個元素應(yīng)在 m+n位置上。這樣從后向前,直到第一 個元素為止。SeqList Union( SeqList la, SeqList lb)/ la和lb是順序存儲的非遞減有序線性表,本算法將lb合并到la中,元素仍非遞減有序 m=la.last;n=lb.last; / m, n分別為線性表la和lb的長度k=m+n-1;/ k為結(jié)果線性表的工作指針(下標(biāo))i=m-1;j=n-1;/ i, j分別為線性表la和lb的工作指針(下標(biāo))while(i=0 & j=0)if(la.datai=lb.dataj) la.datak-=l
26、a.datai-;else la.datak-=lb.dataj-; while(j=0) la.datak-=lb.dataj-; la.last=m+n;return la;【算法討論】算法中數(shù)據(jù)移動是主要操作。在最佳情況下(lb的最小元素大于la的最大元素),僅將lb的n個元素移(拷貝)到la中,時間復(fù)雜度為 O (n),最差情況,la的所有 元素都要移動,時間復(fù)雜度為O (m+n)。因數(shù)據(jù)合并到la中,所以在退出第一個while循環(huán)后,只需要一個 while循環(huán),處理lb中剩余元素。第二個循環(huán)只有在lb有剩余元素時才執(zhí)行,而在la有剩余元素時不執(zhí)行。本算法“最大限度的避免移動元素”,是
27、“一種高效算法”。2.17已知非空線性鏈表由head指出,試寫一算法,將鏈表中數(shù)據(jù)域值最小的那個結(jié)點移到鏈表的最前面。要求:不得額外申請新的鏈結(jié)點?!绢}目分析】本題要求將鏈表中數(shù)據(jù)域值最小的結(jié)點移到鏈表的最前面。首先要查找最小值結(jié)點。將其移到鏈表最前面,實質(zhì)上是將該結(jié)點從鏈表上摘下(不是刪除并回收空間),再插入到鏈表的最前面。Lin kedListDeli nsert(L in kedListhead)/本算法將非空線性鏈表head中數(shù)據(jù)域值最小的那個結(jié)點移到鏈表的最前面p=head-next ;/ p是鏈表的工作指針pre=head ;q=p ;/ pre指向鏈表中數(shù)據(jù)域最小值結(jié)點的前驅(qū)/
28、q指向數(shù)據(jù)域最小值結(jié)點,初始假定是第一結(jié)點while ( p-next)if (p-next-datadata ) pre=p ; q=p-next; / 找至U新的最小值結(jié)點 p=p-next;if(q!=head- next)/若最小值是第一元素結(jié)點,則不需再操作pre-next=q-next ;/將最小值結(jié)點從鏈表上摘下q-next=head-next ;/將q結(jié)點插到鏈表最前面head-next=q; / Delinsert2.19三個帶頭結(jié)點的線性鏈表 存在兩個以上值相同的結(jié)點)表中均包含的數(shù)據(jù)元素的結(jié)點,la、lb和lc中的結(jié)點均依元素值自小至大非遞減排列(可能 ,編寫算法對la表進(jìn)行如下操作:使操作后的la中僅留下三個且沒有值相同的結(jié)點, 并釋放所有無用結(jié)點。 限定算法的時間復(fù)雜度為O (m+n+p),其中m、n和p分別為三個表的長度?!绢}目分析】留下三個鏈表中公共數(shù)據(jù),首先查找兩表la和B中公共數(shù)據(jù),再去lc中找O (m+n+p),在查找每個鏈有無該數(shù)據(jù)。要消除重復(fù)元素,應(yīng)記住前驅(qū),要求時間復(fù)雜度 表時,指針不能回溯。LinkedList lcommon(LinkedList la , lb, lc)/本算法使la表留下la、lb和lc三個非遞減有
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年海南從業(yè)資格證貨運題庫答案
- 電力損耗管理合同(2篇)
- 晉教版地理七年級下冊9.5《極地地區(qū)──冰封雪裹的世界》聽課評課記錄
- 小學(xué)五年級下冊數(shù)學(xué)《同分母分?jǐn)?shù)加減法》聽評課記錄
- 2024年春五年級語文下冊第一單元3冬不拉課文原文素材語文S版
- 2024-2025學(xué)年高中政治課時分層作業(yè)19培育和踐行社會主義核心價值觀含解析新人教版必修3
- 2024-2025學(xué)年新教材高中地理第一單元從宇宙看地球第一節(jié)地球的宇宙環(huán)境第1課時宇宙和太陽課后篇鞏固提升含解析魯教版必修第一冊
- 專業(yè)技術(shù)人員年終工作總結(jié)
- 初中歷史社團活動總結(jié)
- 教師戶外活動總結(jié)
- 河南2025年河南職業(yè)技術(shù)學(xué)院招聘30人筆試歷年參考題庫附帶答案詳解
- 2024年湖南有色金屬職業(yè)技術(shù)學(xué)院高職單招職業(yè)技能測驗歷年參考題庫(頻考版)含答案解析
- 生物-遼寧省大連市2024-2025學(xué)年高三上學(xué)期期末雙基測試卷及答案
- 《民營企業(yè)清廉建設(shè)評價規(guī)范》
- 智能RPA財務(wù)機器人開發(fā)教程-基于來也UiBot 課件 第2章-常用機器人流程自動化
- 品管圈PDCA改善案例-降低住院患者跌倒發(fā)生率
- 讀書分享《給教師的建議》課件
- 《中小學(xué)校園食品安全和膳食經(jīng)費管理工作指引》專題講座
- 廣東省茂名市2023-2024學(xué)年高一上學(xué)期物理期末試卷(含答案)
- 江蘇省蘇州市昆山、太倉、常熟、張家港四市2024-2025學(xué)年八年級上學(xué)期期中陽光測評生物學(xué)試卷(含答案)
- 沙發(fā)市場需求與消費特點分析
評論
0/150
提交評論