數(shù)據(jù)結(jié)構(gòu)北大與算法

一、信 課程（課程講義、算法源代碼等 二、數(shù)據(jù)結(jié)構(gòu)的一般問(wèn) 中多處提到logn是以10為底的對(duì)數(shù)嗎 關(guān)于算 第1版第1次印刷p19倒數(shù)L1，P21，P62等處的“算子”一詞，本身是 p24算法2.1，插入之前curr的值不確定 第26頁(yè)鏈表部分first指針的含義 為什么要自己定義一個(gè)String類 KMP算法疑 關(guān)于第96頁(yè)的二叉樹非遞歸后序周游的算 第139頁(yè)樹的鏈?zhǔn)剑褐羔槨⑺饕拖聵?biāo) 關(guān)于中第146頁(yè)算法5.7的PrevSibling函數(shù)中while(pointer)循 第181頁(yè)中的DFS中寫了PreVisit和 圖的題 關(guān)于第218頁(yè)的算法7.11 第231頁(yè)優(yōu)化的歸并排序“if(right<=left)return;”冗余吧 B樹/B+樹為什么那樣定義 p347B樹關(guān)鍵碼個(gè)數(shù)問(wèn)題 關(guān)于347頁(yè)圖10.9的疑 七 usingnamespacestd是什么意思 怎樣使用STL中的隊(duì)列啊 關(guān)于STL中的 文件流操 九 社，2004年7月。主勘誤表。 高等教育，2005年10月。ISBN7-04-017829-X。輔助勘誤表。 高教社網(wǎng)上訂購(gòu)URL：http: 章（第203-253頁(yè)，第294-332頁(yè)，第359-468頁(yè)）由主筆。輔助第、、、、、章（第162-215、244-279、280-303、324-503頁(yè)）5、6、8章（第48-161、226-243頁(yè)）由蛟主筆。 請(qǐng)到 請(qǐng)不要給作者發(fā)詢問(wèn)問(wèn)題，作者非常忙，很可能沒(méi)有時(shí)間直接回答您的問(wèn)題。我BBS： /agorithm/pseuoco.hm給偽定偽代碼(seudcod)是一種算法描述語(yǔ)言。使用為代的目的是為了使被描述的算法可以容易地以任何一種編程語(yǔ)言(asca,+,aa,e像第38頁(yè)中綴轉(zhuǎn)后綴算法（注意第一次印刷版該算法有錯(cuò)，勘誤表已經(jīng)糾正）那loganlogbnlogbanab，loganlogbn只相差常數(shù)因子logba，而與n的值無(wú)關(guān)。中的大多數(shù)代價(jià)分析都忽略常數(shù)因子，因此答:兩個(gè)層面：記住最基本的算法的時(shí)間/空間代價(jià)和會(huì)推導(dǎo)一些不算太復(fù)雜的算法效率。抽象數(shù)據(jù)類型是定義了一組運(yùn)算的數(shù)學(xué)模型。它與物理結(jié)構(gòu)無(wú)關(guān)，使軟件系統(tǒng)從抽象數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)來(lái)看，對(duì)數(shù)據(jù)結(jié)構(gòu)的一切都是通過(guò)函數(shù)來(lái)進(jìn)行的。不主張把屬性直接public，讓外界直接。請(qǐng)不要拘泥于抽象數(shù)據(jù)類型的具體形式，它只是描述數(shù)據(jù)結(jié)構(gòu)的一種理論工具。不一定要用Interface或者抽象類來(lái)表示。C++語(yǔ)言的類定義形式，在定義抽象數(shù)據(jù)類型時(shí)，不過(guò)，如果期中、期末兩次考試都沒(méi)有上50的學(xué)生，期末絕對(duì)不能及格?？荚囘€是一708.55×0.85，那么期評(píng)成績(jī)就是76?？偡挚梢蕴岣咭淮蠼?。11次印刷p19L1，P21，P62等處的 list::list(constint //Constructor:{msize= curr_len=curr=0;nodelist=newELEM[size];assertDebug版本起作用，用于檢查“不應(yīng)邊界判斷是算法的重要組成部分。本中使用的assert，并沒(méi)有損壞算法的完整P242.12.2中assert2.1insert2.2remove函上frs->nk才向一結(jié)。frt指的首結(jié)點(diǎn)算是數(shù)元素，這個(gè)點(diǎn)有什么意義？這與我們通常的編程習(xí)慣不同。請(qǐng)問(wèn)考試時(shí)是否默認(rèn)采用中的規(guī)定？表，頭結(jié)點(diǎn)的data域用來(lái)整個(gè)鏈表的簡(jiǎn)單信息。因此尋找第i個(gè)結(jié)點(diǎn)的算法2.3FindIndex(i)中，變量first的指向的是一個(gè)特殊的首結(jié)點(diǎn)。first->link才是。2.3iiC/C++數(shù)組下標(biāo)編號(hào)0到n-10first->link，即鏈表真正的第一個(gè)有效rear指向下一個(gè)該插入信息的位置。有些用rear指向循環(huán)隊(duì)列最后一個(gè)元素，而且鏈?zhǔn)疥?duì)列的rear往往指向隊(duì)列的最后一個(gè)有效元素（例如第53頁(yè)算法。如果循環(huán)隊(duì)列帶上了當(dāng)前的長(zhǎng)度信息，那么可以利用所有的結(jié)點(diǎn)空間，如就寫著：……anyrecursiveproblemcanalsoberesolvedi 構(gòu)與算法分析——C++版》上，關(guān)于Hanoi塔的問(wèn)題，寫的是：并不是所有的遞歸問(wèn)題都可以用迭代來(lái)解決……Hanoi塔問(wèn)題就不能用迭代來(lái)解決。我感的是，Hanoi塔答：翻譯的《數(shù)據(jù)結(jié)構(gòu)與算法分析——C++（電子社2002年版）第81頁(yè)，"并不是所有的遞歸問(wèn)題都可以用迭代來(lái)解決"ition4.2那種簡(jiǎn)單循環(huán)遞推。遞歸問(wèn)題都可以用棧來(lái)化解為非遞歸的形式。如果是類似于二叉樹地對(duì)問(wèn)題空架。例如，Hanoi塔問(wèn)題可以采用中序非遞歸深度優(yōu)先周游框架來(lái)消除遞歸（注意修改進(jìn)出棧參數(shù)，修改算法中的Visit語(yǔ)句。推薦參考講義：2002年http://w 推薦參考書：等《數(shù)據(jù)結(jié)構(gòu)》或者等《數(shù)據(jù)結(jié)構(gòu)》1985年版。end1end1比如rand()函數(shù)（產(chǎn)生隨機(jī)數(shù)）等。#include<string.h>后，字符串變量“strings1”會(huì)報(bào)錯(cuò)undeclaredidentifier？但是其中的一些函數(shù)如strlen卻可以使用？難道要自己編寫string類？答：(a)如果沒(méi)有編寫自己的string類，#include<string.h>之后，不能直接strings1。因常用函數(shù)（strlen()string類，可以敲出來(lái)，并#include"string.h"（注意，是“”而不是<>。意，沒(méi)有“h”。然后，需要usingnamespace或者using與STL的string類略有差別。用，單獨(dú)strlen()則是調(diào)用標(biāo)準(zhǔn)C的函數(shù)。String intlen 或者lenfunctionstrlen()C++時(shí)用到的、看到的都是用length()，所以我覺(jué)得應(yīng)該用length()更為恰當(dāng)一些。們沿用strlen()。答：string&的&表示，返回的是一個(gè)值，所謂指的是對(duì)一個(gè)對(duì)象的。如果一個(gè)函數(shù)返回的是一個(gè)類型，那么該函數(shù)可以被當(dāng)作左值使用。如果一個(gè)對(duì)象或表答：定義String類是為了詳細(xì)解釋串的實(shí)現(xiàn)細(xì)節(jié)、運(yùn)算符重載等。我們?cè)谥v解新的數(shù)的String類。局部對(duì)象在語(yǔ)句塊結(jié)束執(zhí)行后將被釋放。算法3.9returntemp答：語(yǔ)句顯然不符合邏輯。temp是語(yǔ)句塊內(nèi)的局部對(duì)象，語(yǔ)句塊結(jié)束執(zhí)行后將被釋放，返回其結(jié)果（return語(yǔ)句并不能返回對(duì)象的值，它只能返回一個(gè)標(biāo)準(zhǔn)表達(dá)式的值）將導(dǎo)致系統(tǒng)錯(cuò)誤（C++中實(shí)際測(cè)一下即可，我已經(jīng)實(shí)際測(cè)試過(guò)了。此算法需要在退出前重新分配str空間，然后將temp.str回str；態(tài)空間。return語(yǔ)句完全可以返回對(duì)象，包括（臨時(shí)變量）對(duì)象的內(nèi)存空間和值。解決方案只需要把析構(gòu)函數(shù)~String的“deletestr;”語(yǔ)句刪除掉就可以了。本教材在第4次印刷時(shí)修改了P74算法3.8。//destructor{ delete[]}析構(gòu)函數(shù)~String什么也不做。Stringdelete釋放。3.9temp的對(duì)象空間必須返回到上一級(jí)。如果在析構(gòu)函數(shù)中銷毀tempstr空間，則調(diào)用算法3.9時(shí)將出現(xiàn)錯(cuò)誤。KMP問(wèn)：在算特征向量的時(shí)候，按04年版新的全都是非負(fù)整數(shù)，我感覺(jué)沒(méi)有－1的話在匹552.4然后再作append操作。答：等價(jià)于p34的gettop操作,取出棧頂元素但不pop。maze(j,k)=0maze(j-1,k)、maze(j-1,k-1)、maze(j-1,k+1)、如果是0就可以繼續(xù)走下去？552.183.1StringA"http://A.strlength()。答：FindLast在66頁(yè)。3.3SP中的字符間有沒(méi)有空格？第88頁(yè)給出了兩個(gè)重要的性質(zhì)：滿二叉樹定理和滿二叉樹定理推論。1159GetParent()是私有的，不能這temppointer的父結(jié)點(diǎn)。tempparentNULLpointer的左孩子無(wú)右子樹的情直接掛到pointer->left，也就是把temppointer這一個(gè)結(jié)點(diǎn)脫鏈。temte<classT>voidBinarySearchTree<T>::DeleteNodeEx(BinaryTreeNode<T>*pointer){if(pointer==NULL BinaryTreeNode<T>*temppointer; BinaryTreeNode<T>*tempparent=NULL; BinaryTreeNode<T>*parent=GetParent(root,pointerifpointer->leftchildNULL//如果待刪結(jié)點(diǎn)的左子樹空，就將它的右子樹代替它temppointer=pointer->rightchild(); temppointer=pointer->leftchild();{tempparent=temppointer; //endofif(tempparent==NULL)刪除替換結(jié)點(diǎn) //endofif(parent==NULL)elseif(parent->leftchild()==pointer)deletepointer;}以后，還只是建立了一個(gè)初始堆，要像第233頁(yè)算法7.16那樣，充分調(diào)用n-1次n個(gè)結(jié)點(diǎn)的不同形態(tài)二叉樹的數(shù)目bn，等價(jià)于{1,2,…,n}順序進(jìn)棧、出棧所得序列數(shù)目，等價(jià)于前序序列為{a1, nbncncn1 1n

n 又說(shuō)以結(jié)點(diǎn)的下標(biāo)表示。請(qǐng)問(wèn)這里的索引究竟是指向結(jié)點(diǎn)的T*型還是表示下標(biāo)的int(((，中的while(pointer)是一樣的。temte<class using if((current==NULL)||(pointer==NULL)||(current==pointer))returnwhile(pointer!=NULL||{if(pointer) returnprev; }//endofelse}}//endwhile}

問(wèn) 如果圖是一個(gè)有向樹的話，PreVisit就是先根周游，PostVisit就是后根周游。可以根據(jù)實(shí)后處理。例如，第186頁(yè)Do_topsort()中，實(shí)質(zhì)上就是用到了后PostVisit。Dijkstra算法怎么保證從第二組所有的頂點(diǎn)中選取到源入堆中；到s的距離變小的頂點(diǎn)，都將會(huì)被再次插入堆中（以前的值還在堆中，但for(Edgee=G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(e)){}6.15中提到了有向連通圖的概念，而我們?cè)陔x散數(shù)學(xué)中學(xué)到的是：有向圖的連通分為弱連通、單向連通、強(qiáng)連通這三種情況，沒(méi)有單獨(dú)的連通這個(gè)概念，而這本6.20是什么意思？好像書上都實(shí)現(xiàn)了啊。那這道題是要我們做什么與書上實(shí)現(xiàn)得6.21權(quán)值為負(fù)的路徑是什么意思？一個(gè)圖的權(quán)值為負(fù)，那么怎么定義它的路徑長(zhǎng)賺錢，還不包括手續(xù)費(fèi)，A[i,j]*A[j,i]<1。 3,1算法以后，對(duì)于不同的n，增量序列有可能是不一樣的？問(wèn)：S排序的代碼下標(biāo)傳遞正確嗎？以上圖7.4作為例子n=8，Array[]={45,34,78,12,34,32,29,64}。當(dāng)delta=4時(shí)，主函數(shù)sort()里的ModifiedInsertsort(&Array[j],n-j,delta”語(yǔ)句所傳的參數(shù)依次為(&Array[0],8,4)，()Array[0],此次比較正確。當(dāng)參數(shù)為(&Array[1],7,4)時(shí)，子函數(shù)比較的仍然是Array[4]與時(shí)，比較的仍然是Array[4]與Array[0]，而正確的比較應(yīng)當(dāng)分別為Array[6]與Array[2],Array[7]Array[3]。難道是我哪里理解錯(cuò)了？答：的算法是正確的。當(dāng)參數(shù)為(&Array[1],7,4)時(shí)，注意ModifiedInsertsort函數(shù)的形參RecordArray[]數(shù)組的首地址被置為&Array[1]，即Array[1]的地址，所以比較的還是Array[5]Array[1]。SSorter（）Arrayjj的的范圍從0~deltadeltaModifiedInsertji到j(luò)僅僅是一個(gè)變量，在兩個(gè)函數(shù)中表示不同的含義。問(wèn)：設(shè)有關(guān)鍵碼序列Q,H,C,Y,Q',A,M,S,R,D,F,X若采用以第一個(gè)元素為分界元素的快速排序法，則一趟掃描的結(jié)果是(F,H,C,D,Q',A,M,Q,R,S,Y,X)還是之；左右兩個(gè)下標(biāo)匯合、交叉到A、M，則交換(Q,M)。最后，得到的答案則是問(wèn)：qsort調(diào)用中的比較函數(shù)為什么要用下面兩個(gè)函數(shù)中的后者？原先我把排序的比較函數(shù)intcmp(constvoid*elem1,constvoid*elem2 return(*((int*)elem1)<*((int*)elem2));0三種比較結(jié)果。所以排序出錯(cuò)。intcmp(constvoid*elem1,constvoid*elem2 return(*((int*)elem2)-*((int*)elem1));return*((int*)elem1)*((int*)elem2))elem1<elem21，其它情況返回0；)-)第231頁(yè)優(yōu)化的歸并排序“if(right<=left)rightleftTHRESHOLD可能不一定取16，客觀上也可以防止閾值取比較怪的值如－1等意外的發(fā)生。new空間之后，int*pnewint。容錯(cuò)性比較好的代碼，通7,8,9。結(jié)論，P234正確。1-41-8-58-答：這里確實(shí)有插入順序不一致的問(wèn)題。當(dāng)時(shí)舉這個(gè)例子，想說(shuō)明“LSD的基數(shù)排序第一8-88-n1,n2,...,nkkk路歸并后，形成一個(gè)長(zhǎng)度為(n1+n2+...+nk)的更大順串，請(qǐng)參考290-291，圖8.17。問(wèn)：對(duì)序列21000442205864:用分界折疊的方法是 呢?還是 答：比較運(yùn)算根據(jù)算法的需要，有些是KEY-KEY型，有些是KEY-ELEM算散列地址，基本是通過(guò)KEY來(lái)算，如果傳入?yún)?shù)為ELEM，那么使用#includeintmain(intargc,char*{shortintsi,high,low;//2bytecout<<"inputacharacter"<<endl;cin>>highchar;while(highchar!='q'){//enter'q'toquitif(highchar&0x80){//iscin>>lowchar;low=low=low&si=high|low;//getthekeyofcharactercout<<si<<endl;}cout<<"inputa character"<<endl;cin>>highchar;return}問(wèn)：log3nlognlog23？那么他們的時(shí)間代價(jià)是否一樣？DONALDE.knuth"TheArtofComputerProgramming"《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》第3卷。的K個(gè)記錄都已不屬于當(dāng)前初始順串，于是當(dāng)前初順串生成結(jié)束，開始生成下一個(gè)初始順串(即把下一個(gè)初始順串稱為當(dāng)前初始順串)。敗KK個(gè)記錄都屬于新的當(dāng)前初始順串，因而都參加處理，放在緩沖區(qū)；20〉10，放在L[3]的位置。22，24，18，26，90，100，因此，我覺(jué)得18應(yīng)該輸出到第一個(gè)順串中。答：習(xí)題集答案是正確的。是你的理解與的不同。實(shí)際上，9小于10（10是剛輸出的L1、2、4-82個(gè)順串的基礎(chǔ)敗者 這三個(gè)槽還是可以被探測(cè)到。最后兩個(gè)桶中第200-215這16個(gè)槽作為測(cè)，以解決。如果第0桶滿了，就把這個(gè)記錄放到文件溢出區(qū)域。扇區(qū)的記錄個(gè)數(shù)可得到總的記錄個(gè)數(shù)，正如習(xí)題10.1,10.2那樣。B樹B+/短。B樹/B+樹非根的內(nèi)部節(jié)點(diǎn)有m/2至m個(gè)子結(jié)點(diǎn)，可以折衷 如果根結(jié)點(diǎn)不空，也不是獨(dú)根，B樹/B+樹根結(jié)點(diǎn)的子結(jié)點(diǎn)數(shù)據(jù)范圍在2~m之間。太浪費(fèi)B樹進(jìn)行比較大的調(diào)整，m的上限，不需要遵守內(nèi)部結(jié)點(diǎn)的子結(jié)點(diǎn)數(shù)目下限2的約束。k-1個(gè)關(guān)鍵碼；其內(nèi)部結(jié)點(diǎn)和葉結(jié)點(diǎn)允許的關(guān)鍵碼個(gè)數(shù)限制范圍葉可以不一樣。這種p347B樹關(guān)鍵碼個(gè)數(shù)問(wèn)題答：是正確的。在m階B樹中，子結(jié)點(diǎn)個(gè)數(shù)在m/2至m之間，關(guān)鍵碼個(gè)數(shù)在m/2-1至m-1之間。討論的是刪除時(shí)下溢出的情況，本來(lái)結(jié)點(diǎn)中只有m/2-1個(gè)關(guān)鍵碼，刪15 3517。判斷出根結(jié)點(diǎn)中只有一個(gè)35后，導(dǎo)致下溢出，無(wú)法從3515,1717，則進(jìn)行換位，根結(jié)17* 10 B（記錄數(shù))。如果考慮讀記錄的那一次操作，B樹讀操作也要加1。NN+1個(gè)樹葉”，我們?cè)撛趺蠢斫?？答：早期很多認(rèn)為B樹的擴(kuò)充外部結(jié)點(diǎn)是葉層。因此，中葉結(jié)點(diǎn)的表述確實(shí)有點(diǎn)個(gè)擴(kuò)展的外部結(jié)點(diǎn)，這些外部結(jié)點(diǎn)都在第I層?！?20122m2假設(shè)我們選擇小的放到父結(jié)點(diǎn)，這里是400，那么父結(jié)點(diǎn)變成490。T指針指向“T”結(jié)點(diǎn)，則“S”繞“R”旋轉(zhuǎn)以后變成了第二個(gè)圖，此次操作正確，在執(zhí)行了“T=T->parent”后，T指針指向“S”結(jié)點(diǎn)，然后是“q”繞“p”旋轉(zhuǎn)，變成了第三個(gè)圖，此次操作也正確，在執(zhí)行了“T=T->parent”后,T指針指向“q”結(jié)點(diǎn)，此答：圖12.47(b)的文字標(biāo)注錯(cuò)了（勘誤表中已改正本來(lái)是連續(xù)兩次T的情況。前三個(gè)子圖為第一次T時(shí)發(fā)生兩次旋轉(zhuǎn)的示意。第四個(gè)子圖表示對(duì)子圖三第二次Tusingnamespacestd名字空間std中聲名的名字。果要用STL中的類如string等，應(yīng)該如下引入：#include<string>;#include#include比如rand()函數(shù)（產(chǎn)生隨機(jī)數(shù)）等。#include<string.h>后，字符串變量“strings1”會(huì)報(bào)錯(cuò)undeclaredidentifier？但是其中的一些函數(shù)如strlen卻可以使用？難道要自己編寫string類？答：(a)如果沒(méi)有編寫自己的string類，#include<string.h>之后，不能直接strings1。因strlen()意需要#include"string.h"（注意，是“”而不是<>。意，沒(méi)有“h”。然后，需要usingnamespace或者using與STL的string類略有差別。用，單獨(dú)strlen()則是調(diào)用標(biāo)準(zhǔn)C的函數(shù)。String intlen 或者len 用system命令system("notepad.exea.txt");就可以打開a.txt文件了 Execute(0,"open","",NULL,NULL,問(wèn)：為什么按照上的usingstd::queue;總是報(bào)錯(cuò)說(shuō)'std':isnotaclassornamespace<問(wèn)：第94－95頁(yè)二叉樹非遞歸前序和后序周游的算法中為什么用到aStack.top();操作例如：我覺(jué)得pointer=aStack.pop();pointer=aStack.top();和aStack.pop();這種寫法是問(wèn)什么呢？是為了使算法更容易看懂和理解？STLtop函數(shù)表示取棧頂，poCTimetCTime::GetCurrentTime();整的例子。使用APIGetLocalTime也可以獲得當(dāng)前的日期和時(shí)間。如： #include<windows.h>intt=//coutGetTickCountt //#include#includeusingnamespaceofstreamifcerr<<“cannotopenthisfile.ifstreaminfile(“name_of_file”);if(!infile)cerr<<”cannotopenthis輸入，并輸出到屏幕。斷開與文件的連接，用成員函數(shù)close()。#include<iostream>#include<fstream>usingnamespacestd;intmain(){”,if(!outFile){ cerr<<”cannotopenthisfile.”<<endl;return-1;}charwhile(cin.get(ch)) ifstreaminFile(“record.txt”); if(!inFile){ cerr<<”cannotopenthisfile.”<<endl;return-1;}while }可以在上面的程序中注意到，ofstream的兩個(gè)參數(shù)分別指定了要打開的文件名和打開模式。程序中使用的打開模式是附加模式(ios_base::app)，與此模式相對(duì)的模式是輸出模式 ios_base::nocreate：不建立文件，所以文件不存在時(shí)打開失敗 如果文件存在，把文件長(zhǎng)度設(shè)為0read( *_Str, _Countwrite(const *_Str, _Countfstreamio(“word.out”,ios_base::in);io.seekg(20, errorC2872:'ifstream':ambiguous答：這是一個(gè)二義性的錯(cuò)誤：Thecompilercouldnotdeterminewhichsymbolyouarereferringtofstream.husingnamespacestd這樣編譯器無(wú)法判斷你到底用的是fstream.h中的定義，還是名字空間的定義，于是產(chǎn)生二義性錯(cuò)誤，＃include<fstream>usingnamespace#include問(wèn)：我用了#include<fstream>usingnamespacestd;來(lái)包含頭文件。結(jié)果在'nocreateisnotamemberofbasic_ios<char,structstd::char_traits<char'nocreate':undeclaredidentifier'nocreate':isnotamemberof'basic_ios<char,structstd::char_traits<char>我發(fā)現(xiàn)用#include<fstream.h>就沒(méi)事了這究竟是怎么回事??？采用的是舊庫(kù)中以為舊iostream庫(kù)元素的函數(shù)、常數(shù)和枚舉數(shù)不是新iostream庫(kù)的元素filebuf、fstreamifstreamofstreamattach成員函數(shù)fileb