数据结构算法

《数据结构算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录1.树的递归和非递归的先，中，后序遍历算法22.KMP算法及其改进算法C语言43.全排列算法54.C(n,k)求所有的组合种数6火车出站问题71.树的递归和非递归的先，中，后序遍历算法#include#include#include#includeusingnamespacestd;typedefstructBiTNode{chardata;structBiTNode*lchild;structBiTNode*rchild;}BiTNode,*BiTree;BiTree

2、creatBiTree(){charch;BiTreeT=NULL;ch=getchar();if(ch!='#'){T=(BiTree)malloc(sizeof(BiTNode));T->data=ch;T->lchild=creatBiTree();//注意T->rchild=creatBiTree();}returnT;}voidfirstTraverse(BiTreeT){if(T){printf("%c",T->data);firstTraverse(T->lchild);firstTraverse(T->rchild);}}voi

3、dmiddleTraverse(BiTreeT){if(T){middleTraverse(T->lchild);printf("%c",T->data);middleTraverse(T->rchild);}}voidlastTraverse(BiTreeT){if(T){lastTraverse(T->lchild);lastTraverse(T->rchild);printf("%c",T->data);}}voidfirstTraverse_stask(BiTreeT){stacks;while(T

4、

5、!s.empty(

6、)){if(T){s.push(T);cout<data;T=T->lchild;}else{T=s.top();s.pop();T=T->rchild;}}cout<s;while(T

7、

8、!s.empty()){if(T){s.push(T);T=T->lchild;}else{T=s.top();s.pop();cout<data;T=T->rchild;}}cout<

9、task(BiTreeT){stacks;BiTreeb;while(T

10、

11、!s.empty()){if(T){s.push(T);T=T->lchild;}else{b=s.top();while(T==b->rchild){//如果空或者出栈的节点是原来的右孩子的话，就打印，继续出栈判断cout<data;T=b;s.pop();if(!s.empty()){b=s.top();}else{cout<rchild;//不是右孩子的话，继续往右边走}}}intmain(){BiT

12、reeT=NULL;T=creatBiTree();cout<<"递归先序遍历:t";firstTraverse(T);cout<

13、verse_stask(T);system("pause");}2.KMP算法及其改进算法C语言#include#include#includevoidget_nextval(char*s,int*next){inti=0,j=-1;next[0]=-1;while(s[i+1]){if(j==-1

14、

15、s[i]==s[j]){++i;++j;if(s[i]!=s[j])next[i]=j;elsenext[i]=next[j];}else{j=next[j];}}}voidget_nex

16、t(char*s,int*next){inti=0,j=-1;next[0]=-1;while(s[i+1]){if(j==-1

17、

18、s[i]==s[j