數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)范圍總結(jié)

1、第一章對(duì)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的理解邏輯結(jié)構(gòu)：實(shí)體數(shù)據(jù)元素間邏輯關(guān)系即實(shí)體性質(zhì)理解基礎(chǔ)進(jìn)行抽象模型物理結(jié)構(gòu)：數(shù)據(jù)元素計(jì)算機(jī)存儲(chǔ)即計(jì)算機(jī)數(shù)據(jù)理解邏輯結(jié)構(gòu)計(jì)算機(jī)語言映射數(shù)據(jù)對(duì)象，數(shù)據(jù)元素，數(shù)據(jù)項(xiàng)的概念理解數(shù)據(jù)元素:是數(shù)據(jù)集合中的一個(gè)“個(gè)體”，數(shù)據(jù)結(jié)構(gòu)中的基本單位，在程序中通常作為一個(gè)整體來進(jìn)行考慮和處理， 也被稱為記錄。數(shù)據(jù)對(duì)象:是必須由軟件理解的復(fù)合信息表示。數(shù)據(jù)對(duì)象可能是外部實(shí)體、事物、偶發(fā)事件或事件、角色、組織單位、 地點(diǎn)或結(jié)構(gòu)等。數(shù)據(jù)項(xiàng):數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)的名稱有編號(hào)、別名、簡(jiǎn)述、數(shù)據(jù)項(xiàng)的長(zhǎng)度、類型、數(shù)據(jù)項(xiàng)的 取值范圍。數(shù)據(jù)項(xiàng)是數(shù)據(jù)記錄中最基本的、不可分的有名數(shù)據(jù)單位，是

2、具有獨(dú)立含義的最小標(biāo)識(shí)單位。邏輯結(jié)構(gòu)分為？對(duì)應(yīng)的物理結(jié)構(gòu)分為？邏輯結(jié)構(gòu)：線性表，樹。物理結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。線性表和數(shù)都是包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。算法的概念及特征？算法：計(jì)算機(jī)處理信息的本質(zhì)，因?yàn)橛?jì)算機(jī)程序本質(zhì)上是一個(gè)算法來告訴計(jì)算機(jī)確切的步驟來執(zhí)行一個(gè)指定的任務(wù)。 算法的五大特性：1.輸入2.輸出3.有窮性4.確定性5.可行性時(shí)間復(fù)雜度的理解及簡(jiǎn)單計(jì)算。例:下列程序段的時(shí)間復(fù)雜度為(C)。for(i=2;i=n;+i)for(j=i;jnext;TifhiletpNULL&jnext;j+；q= (LNode +) nalloc( sizeof(LNode): q-da

3、ta= j ;q-nest=p-neKt;p_neKt-q;leturnthead);鏈表插入第i個(gè)位置：LITode +deletl(Ukde + , int i) LKq de +pj =head;Lilt J=0；liead=p=;UFkLile(pJ=NULL&jneKt;j+；q=p_neKt;p-next=q_next;free(q);return (head.);鏈表查找第i個(gè)位置：int find(LNode 寺 int 】)LNode 如次q； int j=0; p= -/next;while (p l=NULL&.p-datal = ) p=p_nezt;j+；l tp-d

4、ata=L) return j;單鏈表的逆置：?jiǎn)捂湵砟嬷?，是一種輸入命令。在插入時(shí)候選擇頭插法（上面是尾插，實(shí)現(xiàn)頭插去掉p=q；）。 單鏈表的合并：（設(shè)置指針pc進(jìn)行記錄合并的位置）大致過程如下：合并算法:LNode *Merge_LinkList(LNode *La, LNode *Lb)/*合并以La, Lb為頭結(jié)點(diǎn)的兩個(gè)有序單鏈表*/( LNode *Lc, *pa , *pb , *pc, *ptr ;Lc=La ; pc=La ; pa=La-next ; pb=Lb-next ; while (pa!=NULL & pb!=NULL) ( if (pa-datadata) TOC

5、o 1-5 h z ( pc-next=pa ; pc=pa ; pa=pa-next ;/*將pa所指的結(jié)點(diǎn)合并，pa指向下一個(gè)結(jié)點(diǎn)*/ if (pa-datapb-data)( pc-next=pb ; pc=pb ; pb=pb-next ;/*將pa所指的結(jié)點(diǎn)合并，pa指向下一個(gè)結(jié)點(diǎn)*/ if (pa-data=pb-data)( pc-next=pa ; pc=pa ; pa=pa-next ; ptr=pb ; pb=pb-next ; free(ptr) ;/*將pa所指的結(jié)點(diǎn)合并，pb所指結(jié)點(diǎn)刪除*/if (pa!=NULL) pc-next=pa ;else pc-next=

6、pb ;/*將剩余的結(jié)點(diǎn)鏈上*/free(Lb);return (Lc) ;循環(huán)鏈表：是一種頭尾相接的鏈表。其特點(diǎn)是最后一個(gè)結(jié)點(diǎn)的指針域指向鏈表的頭結(jié)點(diǎn)，整個(gè)鏈表的指針域鏈 接成一個(gè)環(huán)。在初始化時(shí)候設(shè)置head-next=head即可。（如下圖）雙向鏈表：typedef struct Dulnode ( ElemType data ;struct Dulnode *prior , *next ;/prior 前驅(qū)和 next 后繼 DulNode ;雙向鏈表的插入：鉤鏈時(shí)必須注意先后次序是：“先右后左”。部分語句組如下： S=(DulNode *)malloc(sizeof(DulNode);

7、Sdata=e;S-next=p-next; p-next-prior=S;p-next=S; S-prior=p; /* 鉤鏈次序非常重要 */雙向鏈表的刪除：p-prior-next=p-next;p-next-prior=p-prior;free(p);順序結(jié)構(gòu)與鏈表結(jié)構(gòu)的區(qū)別與聯(lián)系。順序表:空間連續(xù),支持隨機(jī)訪問1.中間或前面部分的插入刪除時(shí)間復(fù)雜度O(N)2.增容的代價(jià)比較大鏈表:以節(jié)點(diǎn)為單位存儲(chǔ)，不支持隨機(jī)訪問1.任意位置插入刪除時(shí)間復(fù)雜度為O(N)2.沒有增容問題，插入一個(gè)開辟一 個(gè)空間 作 第二章棧的概念和操作。概念：是一種運(yùn)算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪

8、除運(yùn)算。這一端被稱為棧頂，相對(duì)地， 把另一端稱為棧底。向一個(gè)棧插入新元素又稱作進(jìn)棧、入?；驂簵＃前研略胤诺綏ｍ斣氐纳厦?，使之成為 新的棧頂元素；從一個(gè)棧刪除元素又稱作出?；蛲藯＃前褩ｍ斣貏h除掉，使其相鄰的元素成為新的棧頂元素。 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct BiTree *base;BiTree *top;int stacksize;SqStack;int Init(SqStack &S) /建立一個(gè)棧S.base = (SElemType*)malloc(STACK_IN

9、IT_SIZE*sizeof (SElemType);if (!(S.base) exit(-1);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return 0;int Push(SqStack &S, SElemType e)/將元素 e 插入棧中 if (S.top - S.base = S.stacksize)if(!(S.base = (SElemType*)realloc(S.base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(SElemType)exit(-1);S.top = S.bas

10、e + STACKINCREMENT;S.stacksize += STACKINCREMENT;*S.top+ = e;return 0;int Pop(SqStack &S, SElemType &e)/出棧，將棧頂元素賦值給e返回 if (S.base = S.top) return false;e =*-S.top;return 0;隊(duì)列一尤其是循環(huán)隊(duì)列的概念和操作。如，循環(huán)隊(duì)列的判空條件？隊(duì)滿判斷條件?當(dāng)前隊(duì)列中的元素個(gè)數(shù)?Tail隊(duì)列期辭f循環(huán)隊(duì)列：將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量。存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)列。 這種循環(huán)隊(duì)列可以以單鏈表的方式來在實(shí)際編程

11、應(yīng)用中來實(shí)現(xiàn)。隊(duì)列結(jié)構(gòu)體中有對(duì)頭對(duì)尾，通過隊(duì)尾的變化來進(jìn)行插入操作。typedef int Status;typedef int QElemType;typedef struct(QElemType *base;Ik迎隊(duì)冽頭播計(jì)int front;/頭int rear;/尾SqQueue;Status InitQueue(SqQueue &Q)(/構(gòu)造if (!(Q.base=(QElemType*)malloc(MAX*sizeof (QElemType) exit(OVERFLOW);Q.front=Q.rear=0;return OK;Status EnQueue(SqQueue &Q,

12、 QElemType e, int n)(/尾插，n 為隊(duì)列長(zhǎng)度 if(Q.rear+1)%MAX= Q.front) return ERROR; /判斷隊(duì)滿條件 if (Q.rear=n) Q.rear=0;Q.rear+;Q.baseQ.rear=e;return OK;Status DeQueue(SqQueue &Q, QElemType &e, int n)(/返回隊(duì)頭if(Q.front = Q.rear) return ERROR;/判斷隊(duì)空條件if (Q.front=n) Q.front=0;e=Q.baseQ.front;Q.front+;return OK;Status D

13、eQueue(SqQueue &Q)(/隊(duì)中現(xiàn)有元素個(gè)數(shù) if (Q.front = Q.rear) return Q.front-Q.rear;else return Q.rear-Q.front;第四章串的基本概念和理解串的理解：字符串就簡(jiǎn)稱為“串”，是由零個(gè)或多個(gè)字符組成的有窮序列。串中的字符可以是數(shù)字，字母，其他字 符等，串中的字符個(gè)數(shù)稱為串的長(zhǎng)度對(duì)于零個(gè)字符的串通常稱為空串，空串的長(zhǎng)度為0，一般是用中符號(hào)表示在表 示一個(gè)串時(shí)，通常記為s = a1a2an”的形式，每個(gè)ai代表一個(gè)字符，其中i表示字符在串中的位置(1Wi Wn)。串的其他概念：串相等就是當(dāng)兩個(gè)串的長(zhǎng)度相等并且各個(gè)對(duì)應(yīng)位

14、置上的字符都相同，稱兩個(gè)串相等。例如：“abc”與“abc”，長(zhǎng)度相等，字符的位置也相等，因此這兩個(gè)串相等。“abc”和“acb”，長(zhǎng)度相等，但是字符的位置不相等，這兩個(gè)串不相等“abc”和“a bc”，長(zhǎng)度不相等，字符的位置也不相等，這兩個(gè)串不相等子串就是在一個(gè)串中任意個(gè)連續(xù)字符組成的子序列(含空串)，稱為該串的子串。例如：“a”、“ab”、“abc” 和“abcd”等都是“abcde”的子串。2. KMP算法中的next數(shù)組的計(jì)算方法？例：根據(jù)字符串的KMP算法，模式串a(chǎn)baabcac的next值為(C )。A. 01211221 B. 01212221 C. 01122312 D. 01

15、122321KMP算法next數(shù)組計(jì)算詳細(xì)解析：1.前兩位一定為0和1計(jì)算第三位的時(shí)候，看第二位b的next值，為1,則把b和1對(duì)應(yīng)的a進(jìn)行比較，不同，則第三位a的next的值 為1,因?yàn)橐恢北鹊阶钋耙晃?，都沒有發(fā)生比較相同的現(xiàn)象。計(jì)算第四位的時(shí)候，看第三位a的next值，為1,則把a(bǔ)和1對(duì)應(yīng)的a進(jìn)行比較，相同，則第四位a的next的 值為第三位a的next值加上1。為2。因?yàn)槭窃诘谌粚?shí)現(xiàn)了其next值對(duì)應(yīng)的值與第三位的值相同。計(jì)算第五位的時(shí)候，看第四位a的next值，為2,則把a(bǔ)和2對(duì)應(yīng)的b進(jìn)行比較，不同，則再將b對(duì)應(yīng)的next值 1對(duì)應(yīng)的a與第四位的a進(jìn)行比較，相同，則第五位的next值

16、為第二位b的next值加上1,為2。因?yàn)槭窃诘诙?實(shí)現(xiàn)了其next值對(duì)應(yīng)的值與第四位的值相同。計(jì)算第六位的時(shí)候，看第五位b的next值，為2,則把b和2對(duì)應(yīng)的b進(jìn)行比較，相同，則第六位c的next值為 第五位b的next值加上1,為3，因?yàn)槭窃诘谖逦粚?shí)現(xiàn)了其next值對(duì)應(yīng)的值與第五位相同。計(jì)算第七位的時(shí)候，看第六位c的next值，為3,則把c和3對(duì)應(yīng)的a進(jìn)行比較，不同，則再把第3位a的next 值1對(duì)應(yīng)的a與第六位c比較，仍然不同，則第七位的next值為1.計(jì)算第八位的時(shí)候，看第七位a的next值，為1.則把a(bǔ)和1對(duì)應(yīng)的a進(jìn)行比較，相同，則第八位c的next值為 第七位a的next值加上1.

17、為2.因?yàn)槭窃诘谄呶缓蛯?shí)現(xiàn)了其next值對(duì)應(yīng)的值與第七位相同。有上述推論可以得出next數(shù)組算法(理解)：void get_next(Str , int next )int m=0,j=1;next1=0;while (jT.length)if (m= 0|*(T.ch+m-1)=*(T.ch+j-1)+m;+j;nextjm;else m=nextm;printf(連接字符串的next數(shù)組是：);for (int i=1; i% l,n 1k=01 n(ii+l)/2-L存儲(chǔ)表下標(biāo)從。開始存儲(chǔ)第T元素a。i（i+l）/2+j （回）（存儲(chǔ)下：角元素）k前面有i行的三角元素JG+l）/2+i（

18、ij）（存儲(chǔ)上頊I元素）三角矩陣:i*(i-l)/2+j-l (目)k=n*(n+l)/2 ij例：若一個(gè)6階的上三角矩陣A按列優(yōu)先的順序壓縮存儲(chǔ)，已知元素A00的起始地址是1000,每 個(gè)元素占相鄰的4個(gè)字節(jié)，試計(jì)算元素A34的起始地址。答案：（1052）0呂目口解：A00=1000+（4！ +3）*4=1052由此可以推出三角矩陣的地址計(jì)算方法稀疏矩陣的表示一帶輔助向量的鏈表存儲(chǔ)結(jié)構(gòu)。帶行指針向量的單鏈表表示法：將矩陣的每一行的非零元素鏈接成一個(gè)單鏈表，每個(gè)結(jié)點(diǎn)包括三個(gè)域：列下標(biāo)、非零元素值、指針。附設(shè)一個(gè)行指 針向量作為m個(gè)單鏈表的表頭指針向量。例：量的單鏈表示法。300000-101-

19、2000002用類似方法也可組織成帶列指針向稀疏矩陣的轉(zhuǎn)置（理解）：AB矩陣M的向量IHim和cpot的值如下表:cpot1 = 1；for (col=2; col=M.nu; col +) cpotcol = cpotcol-1 + numcol-1;轉(zhuǎn)置的算法：typedef structint i,j;QElemType e;Triple;typedef struct (Triple dataMAXSIZE+1;int mu,nu,tu;TSMatrix;int FasTransposeSMatrix(TSMatrix M,TSMatrix &T)(T.mu=M.nu; T.nu=M.m

20、u; T.tu=M.tu;int col,q;int num100,cpot100;if (T.tu)(for (col=1;col=M.nu;+col) numcol=0;for (int t=1;t=T.tu;t+) +numM.datat.j;cpot1=1;for (col=2;col=T.tu;col+) cpotcol=cpotcol-1+numcol-1;for (int p=1;pdata);p = p-lchild;elsePop(S, p);p = p-rchild;return 0;void InOrderTraverse(BiTree T)/二叉樹的中序遍歷(遞歸)if(T=NULL)return ;InOrderTraverse(T-lchi