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