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