1、第2、3章 復(fù)習(xí),基本內(nèi)容 線性表的定義和基本操作 棧的定義和基本操作 隊列的定義和基本操作,退出,#define MAXSIZE 100 typedef struct datatype dataMAXSIZE; int last; SeqList;,一、順序表,定義：,x,插入操作：,刪除操作：,順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn) 優(yōu)點(diǎn) 邏輯相鄰，物理相鄰 可隨機(jī)存取任一元素 存儲空間使用緊湊 缺點(diǎn) 插入、刪除操作需要移動大量的元素 預(yù)先分配空間需按最大空間分配，利用不充分 表容量難以擴(kuò)充,二、單鏈表,typedef struct node datatype data; struct node *next

2、; LNode，*LinkList；,定義：,s-next=p-next;,p-next=s;,插入操作：,S=p-next;p-next=s-next,刪除操作：,鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn),優(yōu)點(diǎn) 它是一種動態(tài)結(jié)構(gòu) 不需預(yù)先分配空間,缺點(diǎn) 指針占用額外存儲空間 不能隨機(jī)存取，查找速度慢,圖 3-1,三、順序棧,特點(diǎn)：后進(jìn)先出,定義：,#define MAXSIZE 100 typedef struct datatype dataMAXSIZE; int top; SeqStack；,x,入棧操作：,出棧操作：,e,s-datas-top=x; s-top+;,s-top-; *x=s-datas-

3、top;,四、鏈棧,typedef struct node datatype data; struct node *next; StackNode，* LinkStack;,定義：,入棧操作：,s-next=top; top=s;,出棧操作：,*x=top-data; top=top-next;,五、順序隊,define MAXSIZE 100 typedef struct datatype dataMAXSIZE; int rear,front; SeQueue;,特點(diǎn)：先進(jìn)先出,a1,a2,an,e, ,入隊操作：,出隊操作：,a1,a2,an, ,sq-rear=(sq-rear+1)%

4、MAXSIZE; sq-datasq-rear=x;,sq-front=(sq-front+1)%MAXSIZE; *x=sq-datasq-front;,typedef struct node/結(jié)點(diǎn)類型 datatype data; struct node *next; QNode;,六、鏈隊,typedef struct / 鏈隊列類型 QNode *front; / 隊頭指針 QNode * rear; / 隊尾指針 LinkQueue;,空隊列,入隊操作：,q-rear-next=p; q-rear=p;,a1,an,q-rear,a2,出隊操作：,q-front-next=p-next;,p,例1：設(shè)一順序表中元素遞增有序。寫一算法，將元素x插入到表中適當(dāng)位置，并保持順序表的有序性。,1 3 6 9,插入4,11,例2：已知單鏈表H，寫一算法刪除其