【正文】 2022/2/16 1 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)及應(yīng)用練習(xí) 2022/2/16 2 內(nèi)容及目標(biāo) 內(nèi)容選取的價值原則 比較常用、易于使用、容易想起的內(nèi)容。 內(nèi)容選取的精簡原則 簡潔的內(nèi)容容易立即、易于記憶，增加應(yīng)用機會；復(fù)雜內(nèi)容難于理解、容易忘記，增加應(yīng)用障礙，減少應(yīng)用機會。 內(nèi)容掌握的熟練原則 小知識、小技能難度低，容易熟練掌握，大知識、復(fù)雜方法難度高，難以熟練掌握。 2022/2/16 3 第 1章 緒論 ADT的一般定義形式 2022/2/16 4 第 1章 緒論 ADT的一般定義形式是 ： ADT 抽象數(shù)據(jù)類型名 { 數(shù)據(jù)對象： 數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系： 數(shù)據(jù)關(guān)系的定義 基本操作： 基本操作的定義 } ADT 抽象數(shù)據(jù)類型名 – 其中數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述。 – 基本操作的定義是： 基本操作名 (參數(shù)表 ) 初始條件： 初始條件描述 操作結(jié)果： 操作結(jié)果描述 2022/2/16 5 第 2章 線性表 線性表的動態(tài)分配順序存儲結(jié)構(gòu) 線性表的靜態(tài)分配順序存儲結(jié)構(gòu) 線性表的插入（基于靜態(tài)分配順序存儲結(jié)構(gòu)） 線性表的刪除（基于靜態(tài)分配順序存儲結(jié)構(gòu)） 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 動態(tài)分配結(jié)點空間及賦值 動態(tài)釋放結(jié)點空間 靜態(tài)分配結(jié)點空間及賦值 從表頭指針 head出發(fā)尋找表尾 在單鏈表表尾插入一個結(jié)點 2022/2/16 6 第 2章 線性表 1從表頭到表尾依次輸出單鏈表各個結(jié)點值 1將單鏈表中的結(jié)點數(shù)據(jù)從表頭到表尾依次存儲在數(shù)組中 1刪除單鏈表的表尾結(jié)點 1單鏈表表空條件 1循環(huán)鏈表表空條件 1單鏈表表尾條件 1 循環(huán)鏈表表尾條件 1計算單鏈表中結(jié)點數(shù)目算法 2022/2/16 7 第 2章 線性表 線性表的動態(tài)分配順序存儲結(jié)構(gòu) typedef int ElemType 。 typedef struct sq { ElemType *Elem_array。//存儲數(shù)據(jù)元素 int length 。//存儲線性表長度 } sqList 。 2022/2/16 8 第 2章 線性表 定義一個動態(tài)分配順序存儲結(jié)構(gòu)的線性表 sqList sq。 分配存儲空間 =( ElemType * )malloc(MAX_SIZE*sizeof( ElemType ) ) 。 = 0。 2022/2/16 9 第 2章 線性表 線性表的靜態(tài)分配順序存儲結(jié)構(gòu) define MAX_SIZE 100 typedef int ElemType 。 typedef struct ssq { ElemType Elem_array[MAX_SIZE]。//存儲數(shù)據(jù)元素 int length 。//存儲線性表長度 } ssqList 。 2022/2/16 10 第 2章 線性表 定義一個靜態(tài)分配順序存儲結(jié)構(gòu)的線性表 ssqList ssq。//存儲空間已獲得 線性表的插入（基于靜態(tài)分配順序存儲結(jié)構(gòu)） 向整型線性表中連續(xù)插入 6個元素： 1）插入方法一、初始化時直接賦值（若已經(jīng)知道插入的數(shù)值）： ssqList ssq={{7, 4, 2, 19, 13, 6},6}。 2022/2/16 11 第 2章 線性表 插入方法二、從外界獲取插入數(shù)據(jù)（事先不知道要插入的數(shù)據(jù)）： ssqList ssq。 int i。 for(i=0。i6。i++) scanf(“ %d” ,amp。[i])。 =i。 2022/2/16 12 第 2章 線性表 在線性表下標(biāo)位置 k（ 0=k=）處插入 1個元素 e： int j。 for ( j=–1。 j=k。 j ) [j+1]=[j]。 /* k+1下標(biāo) 位置以后的 元素后移 */ [k]=e。 /*在 k位置插入結(jié)點 */ ++ 。 畫圖分析在空表中插入一個元素時上述算法是否正確，在表尾插入一個元素時該算法是否正確。 2022/2/16 13 第 2章 線性表 線性表的刪除（基于靜態(tài)分配順序存儲結(jié)構(gòu)） 刪除線性表下標(biāo)位置 k（ 0=k）處的 1個元素 e并返回該值： int j,e。 e=[k] 。 for ( j=k。j 。 j++) [j]=[j+1]。 /* i位置以后的所有結(jié)點前移 */ 。 return (e)。 2022/2/16 14 第 2章 線性表 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) typedef int ElemType 。 typedef struct Lnode { ElemType data。/*數(shù)據(jù)域，保存結(jié)點的值 */ struct Lnode *next。 /*指針域 */ }LNode,*LinkList。 /*結(jié)點的類型 */ 動態(tài)分配結(jié)點空間及賦值 LNode *p。 p=(LNode*)malloc(sizeof(LNode))。 pdata=20。 pnext=NULL 。 2022/2/16 15 第 2章 線性表 動態(tài)釋放結(jié)點空間 free(p)。 靜 態(tài)分配 結(jié)點空間及賦值 LNode p。 =20。 =NULL 。 從表頭指針 head出發(fā)尋找表尾 LNode *q=head。 while (qnext) q=qnext。/*循環(huán)結(jié)束時 q指向表尾結(jié)點 */ 2022/2/16 16 第 2章 線性表 在單鏈表表尾插入一個結(jié)點 LNode *p,*q=head。/*head為頭指針 */ while (qnext) q=qnext。/*q指向表尾結(jié)點 */ p= (LNode*)malloc(sizeof(LNode))。/*分配一個結(jié)點空間 */ scanf(―%d‖,amp。pdata)。//輸入結(jié)點值 */ pnext=qnext。/*結(jié)點 p指針域置為空 */ qnext=p。/*結(jié)點 p接到表尾 */ q=p 。/*q指向新的表尾結(jié)點 */ 2022/2/16 17 第 2章 線性表 1從表頭到表尾依次輸出單鏈表各個結(jié)點值（假設(shè)數(shù)據(jù)域為整型） LNode *q=headnext。/*head為頭指針 */ while (q) { printf(―%d ‖,qdata)。//輸出結(jié)點值 */ q=qnext。 } 2022/2/16 18 第 2章 線性表 1將單鏈表中的結(jié)點數(shù)據(jù)從表頭到表尾依次存儲在數(shù)組中 LNode *q=headnext。/*head為頭指針 */ ssqList ssq。 int i=0。 while (q) { [i++]=qdata。 q=qnext。 } =i。 2022/2/16 19 第 2章 線性表 1刪除單鏈表的表尾結(jié)點 LNode *p=head,*q=head。/*head為頭指針 */ while (qnext) { p=q。 q=qnext。 }/*q指向表尾結(jié)點 ,p指向 q的前驅(qū) */ if(p==q) printf(“空表 \n” )。 else {pnext=NULL。 free(q)。 }/*表不空 ,則刪除表尾結(jié)點 */ 2022/2/16 20 第 2章 線性表 1單鏈表表空條件 headnext==NULL 1循環(huán)鏈表表空條件 headnext==head 1單鏈表表尾條件 pnext==NULL 1 循環(huán)鏈表表尾條件 pnext==head 2022/2/16 21 第 2章 線性表 1計算單鏈表中結(jié)點數(shù)目算法 LNode *q=headnext。/*head為頭指針 */ int i=0。 while (q) { i++ q=qnext。 } return i。 2022/2/16 22 第 3章 棧和隊列 棧的概念 棧的動態(tài)順序存儲表示 申請棧空間，初始化棧頂、棧底指針和棧容量 動態(tài)順序棧的入棧 動態(tài)順序棧的出棧 棧的靜態(tài)順序存儲表示 靜態(tài)順序棧的初始化 靜態(tài)順序棧的入棧 靜態(tài)順序棧的出棧 隊列的概念 1靜態(tài)順序隊列的存儲結(jié)構(gòu) 1靜態(tài)順序循環(huán)隊列為空的判斷條件 2022/2/16 23 第 3章 棧和隊列 1靜態(tài)順序循環(huán)隊列為滿的判斷條件 1靜態(tài)順序循環(huán)隊列入隊操作 1靜態(tài)順序循環(huán)隊列出隊操作 1利用棧實現(xiàn)單鏈表結(jié)點值逆序輸出功能 2022/2/16 24 第 3章 棧和隊列 棧的概念 棧 是僅在表尾進(jìn)行 插入 和 刪除 操作的 線性表 。又稱為 后進(jìn)先出 LIFO 或 先進(jìn)后出 FILO線性表 。 棧頂 ：允許進(jìn)行插入、刪除操作的一端，又稱為 表尾 。 棧底 ：是 固定端 ，又稱為 表頭 。 2022/2/16 25 第 3章 棧和隊列 棧 的 動態(tài)順序存儲表示 define STACK_SIZE 100 /* 棧大小 */ typedef int SElemType 。 typedef struct { SElemType *base。 /*棧底 */ SElemType *top。 /* 棧頂指針 */ int stacksize 。 /*當(dāng)前已分配空間 */ }SqStack 。 2022/2/16 26 第 3章 棧和隊列 申請?？臻g，初始化棧頂、棧底指針和棧容量 SqStack S。 =(SElemType*)malloc(STACK_SIZE *sizeof(SElemType))。/*申請?？臻g */ = 。 /*?？諘r棧頂和棧底指針相同 */ S. stacksize=STACK_SIZE。 /*置棧容量 */ 2022/2/16 27 第 3章 棧和隊列 動態(tài)順序棧的入棧 int Push(SqStack amp。S , SElemType e) { if (=) {=(SElemType *)realloc((*S).base, ((*S).stacksize+STACKINCREMENT) *sizeof(SElemType))。/*棧滿 ,追加存儲空間 */ if (! ) exit(1)。 =+ 。 S. stacksize+=STACKINCREMENT 。} *()=e。 ++ 。 /*棧頂指針加 1,e成為新的棧頂 */ return 1。} 2022/2/16 28 第 3章 棧和隊列 動態(tài)順序棧的出棧 int Pop( SqStack amp。S, SElemType *e ) /*彈出棧頂元素 */ { if (== ) return 1 。 /* 棧空 ,返回失敗標(biāo)志 */ 。 *e=*(S. top) 。 return 1 。 } 2022/2/16 29 第 3章 棧和隊列 棧 的 靜態(tài)順序存儲表示 define STACK_SIZE 100 /* 棧大小 */ typedef int SElemType 。 typedef struct { SElemType stack[STACK_SIZE]。 /*棧空間 */ int top。 /* 棧頂指針 */ int stacksize 。 /* ?？臻g大小 */ }SSqStack 。 2022/2/16 30 第 3章 棧和隊列 靜態(tài)順序棧的初始化 SSqStack ssq。 =0。 =STACK_SIZE。 2022/2/16 31 第 3章 棧和隊列 靜態(tài)順序棧的入棧 int Push(SSqStack amp。ssq, SElemType e) { if (=){ printf(“棧滿 ,無法入?！?)。 exit(1)。} ssq. stack[++]=e。 return 1。} 2022/2/16 32 第 3章 棧和隊列 靜態(tài)順序棧的出棧 int Pop(SSqStack amp。ssq, SElemType *e) { if (==0){ printf(“棧空