數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題要點(diǎn)(整理版)(編輯修改稿)
2025-05-14 01:46 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 應(yīng)采用順序存儲(chǔ)表示。因?yàn)轫樞虼鎯?chǔ)表示的存取速度快，但修改效率低。若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)采用順序存儲(chǔ)表示較好。第三章 棧和隊(duì)列1. 棧（1） 棧的結(jié)構(gòu)與定義定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表。結(jié)構(gòu)：typedef struct list{ int listsize。 //棧的容量 struct list *head。 //棧頂指針 struct list *base。 //棧底指針}（2） 順序棧操作算法：入棧、出棧、判斷?？盏龋ㄟ@個(gè)是使用數(shù)組進(jìn)行操作的，具體內(nèi)容參照書(shū)本P4647）（3） 鏈棧的結(jié)構(gòu)與定義2. 隊(duì)列（1） 隊(duì)列的定義定義：只允許在表的一端進(jìn)行插入，而在另一端刪除元素。補(bǔ)充內(nèi)容：一個(gè)棧的入棧序列為“ABCDE”，則以下不可能的出棧序列是（B）A. BCDAE B. EDACB C. BCADE D. AEDCB棧的順序表示中，用TOP表示棧頂元素，那么?？盏臈l件是（D）A. TOP==STACKSIZE B. TOP==1 C. TOP==0 D. TOP==1允許在一端插入，在另一端刪除的線性表稱為隊(duì)列。插入的一端為表頭，刪除的一端為表尾。棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出。對(duì)于棧和隊(duì)列，無(wú)論他們采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度都是O(1)（即與已有元素N無(wú)關(guān)）。已知鏈棧Q，編寫(xiě)函數(shù)判斷?？?，如果?？談t進(jìn)行入棧操作，否則出棧并輸出。（要求判斷?？?、出棧、入棧用函數(shù)實(shí)現(xiàn)）（詳看考點(diǎn)2）：出隊(duì)就是刪除對(duì)頭的數(shù)據(jù)元素，取隊(duì)頭元素是獲取對(duì)頭的數(shù)據(jù)元素值，不需要?jiǎng)h除。，比較明顯的優(yōu)點(diǎn)是：（D） 考點(diǎn)1：隊(duì)列的編程：結(jié)構(gòu)：typedef struct QNode{ int date。 struct QNode *next。 }QNode,*QueuePtr。typedef struct{ QueuePtr front。 QueuePtr rear。 }LinkQueue。創(chuàng)建：LinkQueue InitQueue(LinkQueue Q){ ==(QueuePtr)malloc(sizeof(QNode))。 next=NULL。 return (Q)。}入隊(duì)：LinkQueue EnQueue(LinkQueue Q,int e){ QueuePtr p。 p=(QueuePtr)malloc(sizeof(QNode))。 pdate=e。 pnext=NULL。 next=p。 =p。 return (Q)。 }出隊(duì)：LinkQueue DeQueue(LinkQueue Q){ int e。 QueuePtr p。 p=next。 e=pdate。 =pnext。 printf(%d,e)。 if(==p)==NULL。 free(p)。 return (Q)。} 考點(diǎn)2：棧的編程：創(chuàng)建：struct list *creat(){ struct list *p。 p=(struct list *)malloc(LEN)。 pnext=NULL。 return(p)。} 入棧：struct list *push(struct list *head,int a){ struct list *p。 p=(struct list *)malloc(LEN)。 pnum=a。 pnext=head。 return(p)。}出棧：struct list *pop(struct list *head){ struct list *p。 p=headnext。 free(head)。 return(p)。}判斷?？眨篿nt listempty(struct list *head){if(headnext)return 0。else return 1。}第四章 串 （不是重點(diǎn)內(nèi)容）：x=’abc’。或x[ ]=’abc’。第五章 數(shù)組和廣義表 （不是重點(diǎn)內(nèi)容）1. 多維數(shù)組中某數(shù)組元素的position求解。一般是給出數(shù)組元素的首元素地址和每個(gè)元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個(gè)元素所在的位置。2. 明確按行存儲(chǔ)和按列存儲(chǔ)的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲(chǔ)方式求解1中類(lèi)型的題。3. 將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括：對(duì)稱矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲(chǔ)方式：三元組，帶輔助行向量的二元組，十字鏈表存儲(chǔ)。掌握
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1