數(shù)據(jù)結(jié)構(gòu)編程.pdf

二 叉 樹 的 相 關(guān) 操 作 # in clu d e # in clu d e# in clu d e /* mallo c()等 * / # in clu d e /* INT_ MAX等 * /# in clu d e /* EOF(=Z或 F6 ),NULL * / # in clu d e /* ato i() * /# in clu d e /* eo f() * / # in clu d e /* flo o r(),ceil(),ab s() * /# in clu d e /* ex it() * / /* 函 數(shù) 結(jié) 果 狀 態(tài) 代 碼 * /# d efin e TRUE 1 # d efin e FALSE 0# d efin e OK 1 # d efin e ERROR 0# d efin e INFEASIBLE -1 /* # d efin e OVERFLOW -2 因 為 在 math .h 中 已 定 義 OVERFLOW的 值 為 3 ,故 去 掉 此 行 * / ty p ed ef in t Statu s; /* Statu s是 函 數(shù) 的 類 型 ,其 值 是 函 數(shù) 結(jié) 果 狀 態(tài) 代 碼 ， 如OK等 * / ty p ed ef in t Bo o lean ; /* Bo o lean 是 布 爾 類 型 ,其 值 是 TRUE或 FALSE * / ty p ed ef ch ar Telemty p e;ty p ed ef stru ct BiNo d e Telemty p e d ata; stru ct BiNo d e * lch ild ,* rch ild ; BiTNo d e,* BiTree; ty p ed ef BiTree QElemTy p e; ty p ed ef stru ct QNo d e QElemTy p e d ata; stru ct QNo d e * n ex t; QNo d e,* Qu eu ePtr; ty p ed ef stru ct Qu eu ePtr fro n t,rear; /* 隊(duì) 頭 、 隊(duì) 尾 指 針 * / Lin k Qu eu e; Statu s In itQu eu e(Lin k Qu eu e * Q) /* 構(gòu) 造 一 個(gè) 空 隊(duì) 列 Q * / (* Q).fro n t=(* Q).rear=(Qu eu ePtr)mallo c(sizeo f(QNo d e); if(!(* Q).fro n t) ex it(OVERFLOW); (* Q).fro n t-n ex t=NULL; retu rn OK; Statu s Qu eu eEmp ty (Lin k Qu eu e Q) /* 若 Q為 空 隊(duì) 列 ,則 返 回 TRUE,否 則 返 回 FALSE * / if(Q.fro n t=Q.rear) retu rn TRUE; else retu rn FALSE; Statu s En Qu eu e(Lin k Qu eu e * Q,QElemTy p e e) /* 插 入 元 素 e為 Q的 新 的 隊(duì) 尾 元 素 * / Qu eu ePtr p =(Qu eu ePtr)mallo c(sizeo f(QNo d e); if(!p ) /* 存 儲(chǔ) 分 配 失 敗 * / ex it(OVERFLOW); p -d ata=e; p -n ex t=NULL; (* Q).rear-n ex t=p ; (* Q).rear=p ; retu rn OK; Statu s DeQu eu e(Lin k Qu eu e * Q,QElemTy p e * e) /* 若 隊(duì) 列 不 空 ,刪 除 Q的 隊(duì) 頭 元 素 ,用 e返 回 其 值 ,并 返 回 OK,否 則 返 回 ERROR * / Qu eu ePtr p ; if(* Q).fro n t=(* Q).rear) retu rn ERROR; p =(* Q).fro n t-n ex t; * e=p -d ata; (* Q).fro n t-n ex t=p -n ex t; if(* Q).rear=p ) (* Q).rear=(* Q).fro n t; free(p ); retu rn OK; v o id CreateBiTree(BiTree * T) /先 序 建 立 二 叉 樹 ch ar ch ; scan f(%c, g etch ar(); if(ch =# ) * T=NULL; else * T=(BiTree)mallo c(sizeo f(BiTNo d e); (* T)-d ata=ch ;p rin tf(請(qǐng) 輸 入 %c的 左 孩 子 :,(* T)-d ata); CreateBiTree( p rin tf(請(qǐng) 輸 入 %c的 右 孩 子 :,(* T)-d ata); CreateBiTree( v o id PreOrd erTrav erse(BiTree T) /先 序 遍 歷 if(T) p rin tf(%c,T-d ata);PreOrd erTrav erse(T-lch ild ); PreOrd erTrav erse(T-rch ild ); v o id In Ord erTrav erse(BiTree T) /中 序 遍 歷 if(T) In Ord erTrav erse(T-lch ild ); p rin tf(%c,T-d ata); In Ord erTrav erse(T-rch ild ); v o id Po stOrd erTrav erse(BiTree T) /后 序 遍 歷 if(T) Po stOrd erTrav erse(T-lch ild ); Po stOrd erTrav erse(T-rch ild ); p rin tf(%c,T-d ata); v o id Lev elTrav erse(BiTree T) /層 次 遍 歷 BiTree p ; Lin k Qu eu e Q;In itQu eu e( if (T) En Qu eu e(wh ile (!Qu eu eEmp ty (Q) DeQu eu e( p rin tf(%c,p -d ata); if(p -lch ild ) En Qu eu e( if(p -rch ild ) En Qu eu e( in t h eig h t(BiTree T) /求 二 叉 樹 T的 高 度in t m,n ; if(!T) retu rn 0 ;else m=h eig h t(T-lch ild ); n =h eig h t(T-rch ild ); retu rn (mn ?m:n )+1 ; in t LeafCo u n t(BiTree T) /求 二 叉 樹 中 葉 子 結(jié) 點(diǎn) 的 數(shù) 目 if(!T) retu rn 0 ; else if(!T-lch ild else retu rn LeafCo u n t(T-lch ild )+LeafCo u n t(T-rch ild ); v o id Bitree_ Rev o lu te(BiTree T) /交 換 所 有 結(jié) 點(diǎn) 的 左 右 子 樹 BiTree p ; if (T) p =T-lch ild ; T-lch ild =T-rch ild ;T-rch ild =p ; if(T-lch ild ) Bitree_ Rev o lu te(T-lch ild ); if(T-rch ild ) Bitree_ Rev o lu te(T-rch ild ); in t main () BiTree T; p rin tf(請(qǐng) 輸 入 樹 根 :); CreateBiTree( p rin tf(n 先 序 遞 歸 遍 歷 序 列 :); PreOrd erTrav erse(T); p rin tf(n 中 序 遞 歸 遍 歷 序 列 :); In Ord erTrav erse(T); p rin tf(n 后 序 遞 歸 遍 歷 序 列 :); Po stOrd erTrav erse(T); p rin tf(n 層 次 遍 歷 序 列 :); Lev elTrav erse(T); p rin tf(n 二 叉 樹 的 高 度 為 :%d ,h eig h t(T); p rin tf(n 二 叉 樹 中 葉 子 結(jié) 點(diǎn) 數(shù) 為 :%d ,LeafCo u n t(T); Bitree_ Rev o lu te(T); p rin tf(n 左 右 子 樹 交 換 后 中 序 遞 歸 遍 歷 序 列 :); In Ord erTrav erse(T); p rin tf(n ); retu rn OK; 串 的 相 關(guān) 操 作 # in clu d e # d efin e o k 1 # d efin e ERROR 0 u sin g n amesp ace std ; ty p ed ef stru ct ch ar * ch ; in t len g th ; h strin g ; in t strin sert(h strin g if(p o ss.len g th ) retu rn ERROR; if(T.len g th ) if(!(s.ch =(ch ar * )reallo c(s.ch ,(s.len g th +T.len g th )* sizeo f(ch ar) retu rn ERROR; fo r(i=s.len g th -1 ;i=p o s-1 ;-i) s.ch i+T.len g th =s.ch i; fo r(i=0 ;i<=T.len g th -1 ;i+) s.ch i+p o s-1 =T.ch i; s.len g th +=T.len g th ; retu rn o k ; in t Strassig n (h strin g ch ar * c; if(m.ch ) free(m.ch ); fo r(i=0 ,c=ch ars;ci!=0 ;i+); if(!i)m.ch =NULL;m.len g th =0 ; else if(!(m.ch =(ch ar * )mallo c(i* sizeo f(ch ar) retu rn ERROR; fo r(j=0 ;j<=i-1 ;j+) m.ch j=ch arsj; m.len g th =i; retu rn o k ; v o id p rin f(h strin g fo r(i=0 ;i<=h .len g th -1 ;i+) co u t<<h .ch i; co u t<< <<該 字 符 串 的 長(zhǎng) 度 為 ： <<h .len g th ; co u t<<en d l; in t main () ch ar a1 0 0 ,b 1 0 0 ; co u t<ab ; h strin g s,T; Strassig n (s,a); p rin f(s); Strassig n (T,b ); p rin f(T); in t p o s; co u t<p o s; strin sert(s,p o s,T); co u t<<把 字 符 串 T插 入 s后 得 到 的 新 字 符 串 為 ： ; p rin f(s); retu rn 0 ; 整 數(shù) 的 加 減 乘 除 運(yùn) 算 # in clu d e # d efin e o k 1 # d efin e ERROR 0 u sin g n amesp ace std ; # d efin e STACK_ INIT_ SIZE 1 0 0# d efin e STACKINCREMENT 1 0 ty p ed ef stru ct ch ar * b ase; ch ar * to p ; in t stack size; Sq stack ; in t In (ch ar c) if(c=+) retu rn 1 ; if(c=-) retu rn 1 ; if(c=* ) retu rn 1 ; if(c=/) retu rn 1 ; if(c=() retu rn 1 ; if(c=) retu rn 1 ; if(c=# ) retu rn 1 ; else retu rn 0 ; ch ar Preced e(ch ar a,ch ar b ) if(a=+) if(b =+) retu rn ; if(b =-) retu rn ; if(b =* ) retu rn < if(b =/) retu rn ; if(a=-) if(b =+) retu rn ; if(b =-) retu rn ; if(b =* ) retu rn < if(b =/) retu rn ; if(a=* ) if(b =+) retu rn ; if(b =-) retu rn ; if(b =* ) retu rn ; if(b =/) retu rn ; if(b =# ) retu rn ; if(a=/) if(b =+) retu rn ; if(b =-) retu rn ; if(b =* ) retu rn ; if(b =/) retu rn ; if(b =# ) retu rn ; if(a=# ) if(b =+) retu rn < if(b =-) retu rn < if(b =* ) retu rn < if(b =/) retu rn =s.stack size) s.b ase=(ch ar* )reallo c(s.b ase,(s.stack size+STACKINCREMENT )* sizeo f(ch ar); if(!s.b ase) retu rn ERROR; s.to p =s.b ase+s.stack size; s.stack size+=STACKINCREMENT; * s.to p +=e; retu rn o k ; in t Po p (Sq stack e=* (-s.to p ); retu rn 1 ; in t main () Sq stack OPTR,OPND; ch ar c1 0 0 ,a,b ,th eta,n ; in t f,i;In itstack (OPTR); Pu sh (OPTR,# ); In itstack (OPND); cin c;fo r(i=0 ;ci!=# |Getto p (OPTR)!=# ;) if(!In (ci) Pu sh (OPND,ci);i+; else switch (Preced e(Getto p (OPTR),ci) case:Po p (OPTR,th eta);Po p (OPND,b );Po p (OPND,a);Pu sh (OPND,Op erate(a,th eta,b );b reak ; n =Getto p (OPND); f=(in t) n -4 8 ; co u t<<f<<en d l; 數(shù) 字 轉(zhuǎn) 換 # in clu d e u sin g n amesp ace std ;# in clu d ec1 .h ty p ed ef in t SElemTy p e;# in clu d ezh an .h # in clu d ezh an h an sh u .cp p in t main () Sq Stack s; In itStack (s); in t N;in t e; cin N; wh ile(N) Pu sh (s,N%8 ); N=N/8 ; wh ile(!Stack Emp ty (s) Po p (s,e);co u t<<e<=(S).stack size) /* 棧 滿 ， 追 加 存 儲(chǔ) 空 間 * / (S).b ase=(SElemTy p e * )reallo c(S).b ase,(S).stack size+STACKINCREMENT)* sizeo f(SElemTy p e); if(!(S).b ase) ex it(OVERFLOW); /* 存 儲(chǔ) 分 配 失 敗 * / (S).to p =(S).b ase+(S).stack size; (S).stack size+=STACKINCREMENT; * (S).to p )+=e; retu rn OK; Statu s Po p (Sq Stack e=* -(S).to p ; retu rn OK; Statu s Stack Emp ty (Sq Stack S) /* 若 棧 S為 空 棧 ， 則 返 回 TRUE， 否 則 返 回 FALSE * / if(S.to p =S.b ase) retu rn TRUE; else retu rn FALSE; /* c1 .h (程 序 名 ) * /# in clu d e # in clu d e# in clu d e /* mallo c()等 * / # in clu d e /* INT_ MAX等 * /# in clu d e /* EOF(=Z或 F6 ),NULL * / # in clu d e /* ato i() * /# in clu d e /* eo f() * / # in clu d e /* flo o r(),ceil(),ab s() * /# in clu d e /* ex it() * / /* 函 數(shù) 結(jié) 果 狀 態(tài) 代 碼 * /# d efin e TRUE 1 # d efin e FALSE 0 # d efin e OK 1# d efin e ERROR 0 # d efin e INFEASIBLE -1/* # d efin e OVERFLOW -2 因 為 在 math .h 中 已 定 義 OVERFLOW的 值 為 3 , 故 去 掉 此 行 * /ty p ed ef in t Statu s; /* Statu s是 函 數(shù) 的 類 型 ,其 值 是 函 數(shù) 結(jié) 果 狀 態(tài) 代 碼 ， 如 OK等 * /ty p ed ef in t Bo o lean ; /* Bo o lean 是 布 爾 類 型 ,其 值 是 TRUE或 FALSE * / /* c3 -1 .h 棧 的 順 序 存 儲(chǔ) 表 示 * / # d efin e STACK_ INIT_ SIZE 1 0 /* 存 儲(chǔ) 空 間 初 始 分 配 量 * /# d efin e STACKINCREMENT 2 /* 存 儲(chǔ) 空 間 分 配 增 量 * / ty p ed ef stru ct Sq Stack SElemTy p e * b ase; /* 在 棧 構(gòu) 造 之 前 和 銷 毀 之 后 ， b ase的 值 為 NULL * / SElemTy p e * to p ; /* 棧 頂 指 針 * / in t stack size; /* 當(dāng) 前 已 分 配 的 存 儲(chǔ) 空 間 ， 以 元 素 為 單 位 * /Sq Stack ; /* 順 序 棧 * / 完 整 的 四 則 運(yùn) 算 算 法 # in clu d e # d efin e o k 1 # d efin e ERROR 0 u sin g n amesp ace std ; # d efin e STACK_ INIT_ SIZE 1 0 0# d efin e STACKINCREMENT 1 0 ty p ed ef stru ct ch ar * b ase; ch ar * to p ; in t stack size; Sq stack ; ty p ed ef stru ct in t * b ase; in t * to p ; in t stack size; Sq stack 1 ; in t In (ch ar c) if(c=+) retu rn 1 ; if(c=-) retu rn 1 ; if(c=* ) retu rn 1 ; if(c=/) retu rn 1 ; if(c=() retu rn 1 ; if(c=) retu rn 1 ; if(c=# ) retu rn 1 ; else retu rn 0 ; ch ar Preced e(ch ar a,ch ar b ) if(a=+) if(b =+) retu rn ; if(b =-) retu rn ; if(b =* ) retu rn < if(b =/) retu rn ; if(a=-) if(b =+) retu rn ; if(b =-) retu rn ; if(b =* ) retu rn < if(b =/) retu rn ; if(a=* ) if(b =+) retu rn ; if(b =-) retu rn ; if(b =* ) retu rn ; if(b =/) retu rn ; if(b =# ) retu rn ; if(a=/) if(b =+) retu rn ; if(b =-) retu rn ; if(b =* ) retu rn ; if(b =/) retu rn ; if(b =# ) retu rn ; if(a=# ) if(b =+) retu rn < if(b =-) retu rn < if(b =* ) retu rn < if(b =/) retu rn =s.stack size) s.b ase=(ch ar* )reallo c(s.b ase,(s.stack size+STACKINCREMENT)* sizeo f(ch ar); if(!s.b ase) retu rn ERROR; s.to p =s.b ase+s.stack size; s.stack size+=STACKINCREMENT; * s.to p +=e; retu rn o k ; in t Pu sh (Sq stack 1 if(!s.b ase) retu rn ERROR; s.to p =s.b ase+s.stack size; s.stack size+=STACKINCREMENT; * s.to p +=e; retu rn o k ; in t Po p (Sq stack e=* (-s.to p ); retu rn 1 ; in t Po p (Sq stack 1 e=* (-s.to p ); retu rn 1 ; in t Zh u an (ch ar b ) in t c; c=(in t)b -4 8 ; retu rn c; in t main () Sq stack OPTR,ONE,TWO; Sq stack 1 OPND; ch ar c1 0 0 ,th eta,k ; in t i,a,b ,m,n ,j,o ,r,sh ;In itstack (OPTR); Pu sh (OPTR,# ); In itstack (OPND);In itstack (ONE);In itstack (TWO); cin c; n =0 ; r=0 ; fo r(i=0 ;ci!=# |Getto p (OPTR)!=# ;) if(!In (ci) Pu sh (ONE,ci);n =n +1 ;i+;sh =1 ; else if(sh =1 ) fo r(j=1 ;j<=n ;j+) Po p (ONE,k );Pu sh (TWO,k ); fo r(j=1 ;j<=n ;j+) Po p (TWO,k );o =Zh u an (k );r=r* 1 0 +o ; Pu sh (OPND,r); switch (Preced e(Getto p (OPTR),ci) case:Po p (OPTR,th eta);Po p (OPND,b );Po p (OPND,a);Pu sh (OPND,Op erate(a,th eta,b );sh =0 ;b reak ; n =0 ; r=0 ; m=Getto p (OPND); co u t<<m<<en d l; retu rn 0 ;