數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言)第二版慕課版王海艷課后習(xí)題答案

知識(shí)創(chuàng)造未來(lái)數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言）第二版慕課版王海艷課后習(xí)題答案第一章：緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。1.2數(shù)據(jù)結(jié)構(gòu)的分類(lèi)數(shù)據(jù)結(jié)構(gòu)可以分為線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)兩種。線(xiàn)性結(jié)構(gòu)包括順序表、鏈表、棧、隊(duì)列等。非線(xiàn)性結(jié)構(gòu)包括樹(shù)、圖等。1.3抽象數(shù)據(jù)類(lèi)型（AbstractDataType，ADT）ADT是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組基本操作。ADT包括三個(gè)要素：數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作。第二章：線(xiàn)性表2.1線(xiàn)性表的定義和特點(diǎn)線(xiàn)性表是指n個(gè)數(shù)據(jù)元素的有限序列。線(xiàn)性表的特點(diǎn)：數(shù)據(jù)元素之間存在一對(duì)一的線(xiàn)性關(guān)系。2.2順序表順序表是指用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線(xiàn)性結(jié)構(gòu)。2.2.1順序表的結(jié)構(gòu)順序表的結(jié)構(gòu)包括兩部分：表頭信息和表元素區(qū)。表頭信息包括表長(zhǎng)和表容量?jī)蓚€(gè)屬性。表元素區(qū)包括具體存儲(chǔ)的數(shù)據(jù)元素。2.2.2順序表的基本操作初始化順序表：InitList(&L)判斷順序表是否為空：ListEmpty(L)獲取順序表長(zhǎng)度：ListLength(L)插入數(shù)據(jù)元素到順序表：ListInsert(&L,i,e)刪除順序表中的數(shù)據(jù)元素：ListDelete(&L,i,&e)獲取順序表中的數(shù)據(jù)元素：GetElem(L,i,&e)查找順序表中元素的位置：LocateElem(L,e)清空順序表：ClearList(&L)銷(xiāo)毀順序表：DestroyList(&L)2.3鏈表鏈表是通過(guò)一組地址不連續(xù)的存儲(chǔ)單元來(lái)存儲(chǔ)數(shù)據(jù)元素的線(xiàn)性結(jié)構(gòu)。2.3.1鏈表的結(jié)構(gòu)鏈表的結(jié)構(gòu)包括兩部分：頭結(jié)點(diǎn)和數(shù)據(jù)結(jié)點(diǎn)。頭結(jié)點(diǎn)保存鏈表的基本信息，數(shù)據(jù)結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)元素本身以及指向下一個(gè)結(jié)點(diǎn)的指針。2.3.2鏈表的基本操作初始化鏈表：InitList(&L)判斷鏈表是否為空：ListEmpty(L)獲取鏈表長(zhǎng)度：ListLength(L)插入數(shù)據(jù)元素到鏈表：ListInsert(&L,i,e)刪除鏈表中的數(shù)據(jù)元素：ListDelete(&L,i,&e)獲取鏈表中的數(shù)據(jù)元素：GetElem(L,i,&e)查找鏈表中元素的位置：LocateElem(L,e)清空鏈表：ClearList(&L)銷(xiāo)毀鏈表：DestroyList(&L)第三章：棧和隊(duì)列3.1棧棧是一種只能在表頭進(jìn)行插入和表頭刪除操作的線(xiàn)性表。棧的特點(diǎn)是后進(jìn)先出（LIFO）。3.2棧的基本操作初始化棧：InitStack(&S)判斷棧是否為空：StackEmpty(S)獲取棧中元素的個(gè)數(shù)：StackLength(S)將元素壓入棧：Push(&S,e)將棧頂元素彈出：Pop(&S,&e)獲取棧頂元素的值：GetTop(S,&e)清空棧：ClearStack(&S)銷(xiāo)毀棧：DestroyStack(&S)3.3隊(duì)列隊(duì)列是一種只能在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作的線(xiàn)性表。隊(duì)列的特點(diǎn)是先進(jìn)先出（FIFO）。3.4隊(duì)列的基本操作初始化隊(duì)列：InitQueue(&Q)判斷隊(duì)列是否為空：QueueEmpty(Q)獲取隊(duì)列中元素的個(gè)數(shù)：QueueLength(Q)將元素插入隊(duì)列：EnQueue(&Q,e)將隊(duì)頭元素刪除：DeQueue(&Q,&e)獲取隊(duì)頭元素的值：GetHead(Q,&e)清空隊(duì)列：ClearQueue(&Q)銷(xiāo)毀隊(duì)列：DestroyQueue(&Q)第四章：串4.1串的定義和特點(diǎn)串是由零個(gè)或多個(gè)字符組成的有限序列，又叫字符串。串的特點(diǎn)是同一串中的字符在邏輯結(jié)構(gòu)上是有序的。4.2串的基本操作初始化串：InitString(&S)判斷串是否為空：StrEmpty(S)獲取串的長(zhǎng)度：StrLength(S)比較兩個(gè)串是否相等：StrCompare(S,T)拷貝一個(gè)串到另一個(gè)串：StrCopy(&S,T)連接兩個(gè)串：StrConcat(&S,T)截取一個(gè)子串：SubString(&Sub,S,pos,len)在串中查找子串：Index(S,T,pos)替換字符串：Replace(&S,T,V)插入一個(gè)子串：StrInsert(&S,pos,T)刪除一個(gè)子串：StrDelete(&S,pos,len)清空串：ClearString(&S)銷(xiāo)毀串：DestroyString(&S)第五章：數(shù)組和廣義表5.1數(shù)組數(shù)組是一種用于存儲(chǔ)一組相同類(lèi)型數(shù)據(jù)元素的結(jié)構(gòu)。數(shù)組的特點(diǎn)是元素類(lèi)型相同，大小相等。5.2數(shù)組的基本操作初始化數(shù)組：InitArray(&A,m,n)獲取數(shù)組元素的值：GetValue(A,i,j,&e)設(shè)置數(shù)組元素的值：SetValue(&A,i,j,e)獲取數(shù)組的行數(shù)：GetRow(A)獲取數(shù)組的列數(shù)：GetColumn(A)5.3廣義表廣義表是一種類(lèi)似于多層次的線(xiàn)性表，既可以是單個(gè)數(shù)據(jù)元素，也可以是其他廣義表。廣義表的特點(diǎn)是每個(gè)元素可能是獨(dú)立的數(shù)據(jù)元素，也可能是廣義表。5.4廣義表的基本操作初始化廣義表：InitGList(&L)判斷廣義表是否為空：GListEmpty(L)獲取廣義表的長(zhǎng)度：GListLength(L)獲取廣義表的深度：GListDepth(L)獲取廣義表的表頭元素：GetHead(L,&e)獲取廣義表的表尾元素：GetTl(L,&subList)插入一個(gè)元素到廣義表：GListInsert(&L,e)刪除廣義表中的一個(gè)元素：GListDelete(&L,e)清空廣義表：ClearGList(&L)銷(xiāo)毀廣義表：DestroyGList(