數(shù)據(jù)結(jié)構(gòu)--3章棧和隊(duì)(編輯修改稿)
2024-09-01 07:33 本頁面
【文章內(nèi)容簡介】 = =StackSize1，棧滿時(shí)，不能入棧 。 否則出現(xiàn)空間溢出，引起錯(cuò)誤，這種現(xiàn)象稱為上溢。 2. 出棧和讀棧頂元素操作，先判斷棧是否為空，為空時(shí)不能操作，否則產(chǎn)生錯(cuò)誤。通常?？諘r(shí)常作為一種控制轉(zhuǎn)移的條件。 使用不帶表頭結(jié)點(diǎn)的單鏈表 (1)結(jié)點(diǎn)和指針的定義 struct node { ElemType data； //data為抽象元素類型 struct node *next； //next為指針類型 } *top=NULL； //初始化 ,置 top為 空棧 (2)非空鏈?zhǔn)綏?的一般形式 an a(n1) a1 ^ data next top 棧頂 棧底 (3)鏈?zhǔn)綏５?進(jìn)棧算法 ： //壓入元素 e到 top為頂指針的鏈?zhǔn)綏? struct node *push_link(struct node *top,Elemtype e) { struct node *p； int leng=sizeof(struct node)； //確定新結(jié)點(diǎn)空間的大小 p=(struct node *)malloc(leng)； //生成新結(jié)點(diǎn) pdata=e； //裝入元素 e pnext=top； //插入新結(jié)點(diǎn) top=p； //top指向新結(jié)點(diǎn) return top； //返回指針 top } an a1 ^ 棧底 top e p X an a1 ^ 棧底 top e ... ... 棧頂 棧頂 (1)插入 e之前： (2)插入 e之后： 棧的應(yīng)用舉例 棧的基本用途 保存暫時(shí)不用 的數(shù)據(jù)或存儲(chǔ)地址。 數(shù)制轉(zhuǎn)換問題 例 . 給定十進(jìn)制數(shù) N=1348,轉(zhuǎn)換為八進(jìn) 制數(shù) R=2504 ,并送入棧中： (1) r1=1348%8=4 //求余 n1=1348/8=168 //整除 (2) r2=168%8=0 //求余 n2=168/8=21 //整除 (3) r3=21%8=5 //求余 n3=21/8=2 //整除 (4) r4=2%8=2 //求余 n4=2/8=0 //整除 ,得 R=2504 4 0 4 5 0 4 2 5 0 4 (1) 4進(jìn)棧 (2) 0進(jìn)棧 (3) 5進(jìn)棧 (4) 2進(jìn)棧 十進(jìn)制數(shù) N轉(zhuǎn)換為 B進(jìn)制數(shù) 算法思想： N＞ 0 r=N%B r入棧 N=N/B 算法： typedef int DataType。 void szzh( int N,int B ) { int i。 SeqStack s。 InitStack(amp。s)。 //初始化棧 while( N ){ //N=0轉(zhuǎn)換結(jié)束 push( amp。s,N%B )。 //余數(shù)入棧 N=N/B。 } while( !StackEmpty( amp。s )){ i=Pop( amp。s )。 printf(“%d”,i)} } y n 棧非空，出棧顯示 隊(duì)列（排隊(duì) ,queue) 隊(duì)列及其操作 ▲ 隊(duì)列 只允許在表的一端刪除元素 ,在另一端插入元素 的線性表 。 ▲ 空隊(duì)列 不含元素的隊(duì)列 。 ▲ 隊(duì)首 隊(duì)列中只允許刪除元素的一端 。 head,front ▲ 隊(duì)尾 隊(duì)列中只允許插入元素的一端 。 rear,tail ▲ 隊(duì)首元素 處于隊(duì)首的元素 。 ▲ 隊(duì)尾元素 處于隊(duì)尾的元素 。 ▲ 進(jìn)隊(duì) 插入一個(gè)元素到隊(duì)列中 。 又稱：入隊(duì) 。 ▲ 出隊(duì) 從隊(duì)列刪除一個(gè)元素 。 : “ 先進(jìn)先出”，“ First In First Out” 隊(duì)列的別名 : “ 先進(jìn)先出 ” 表， “ FIFO” 表，排隊(duì) ,queue 隊(duì)列示意圖 a1, a2 ,......, an ↑ ↑ head(fro
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1