实验四：二叉树的操作 数据结构系统上实验代码.doc

#include#include#include#define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN+1;void get_next(SString T,int next)int i=1,j=0;next1=0;while(iT0)if(j=0|Ti=Tj)i+;j+;nexti=j;elsej=nextj;int main()int nextMAXSTRLEN,n,i,j;char ch;SString S;scanf(%d,&n);ch=getchar();for(i=1;i=n;i+)ch=getchar();for(j=1;j=MAXSTRLEN&(ch!=n);j+)Sj=ch;ch=getchar();S0=j-1;get_next(S,next);printf(NEXT J is:);for(j=1;j=S0;j+)printf(%d,nextj);printf(n);return 0;222222222222222222222222222222222222222222222222222222222222222222222222222222#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASLBLE -1#define OVERFLOW -2#define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN+1;void get_next(SString T,int next)int i=1,j=0;next1=0;while(iT0)if(j=0|Ti=Tj)i+;j+;nexti=j;elsej=nextj;int Index_KMP(SString S,SString T,int pos)int nextMAXSTRLEN,i=pos,j=1;get_next(T,next);while(i=S0&jT0) return i-T0; else return 0;int main()int n,i,j,pos;char ch;SString S,T;scanf(%d,&n);ch=getchar();for(j=1;j=n;j+)ch=getchar();for(i=1;i=MAXSTRLEN&(ch!=n);i+)Si=ch;ch=getchar();S0=i-1;ch=getchar();for(i=1;i=MAXSTRLEN&(ch!=n);i+)Ti=ch;ch=getchar();T0=i-1;pos=Index_KMP(S,T,0);printf(%dn,pos);return 0;实验五实验五实验五实验五实验五实验五实验五实验五实验五实验五实验五实验五实验五111111111111111111111111111111111111111111111111111111111111111111111111111111#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef char ElemType;typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree CreateBiTree(BiTree &T)char ch;scanf(%c,&ch);if(ch=#)T=NULL;elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode)return ERROR;T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);return T;Status Visit(ElemType e)if(e!=#)printf(%c,e);return OK;elsereturn FALSE;Status PreOrderTraverse(BiTree T)if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild)if(PreOrderTraverse(T-rchild)return OK;return ERROR;elsereturn OK;Status InOrderTraverse(BiTree T)if(T)if(InOrderTraverse(T-lchild)if(Visit(T-data)if(InOrderTraverse(T-rchild)return OK;return ERROR;elsereturn OK;Status PostOrderTraverse(BiTree T)if(T)if(PostOrderTraverse(T-lchild)if(PostOrderTraverse(T-rchild)if(Visit(T-data)return OK;return ERROR;elsereturn OK;int main() BiTree T;CreateBiTree(T);PreOrderTraverse(T);printf(n);InOrderTraverse(T);printf(n);PostOrderTraverse(T);printf(n);return 0;222222222222222222222222222222222222222222222222222222222222222222222222222222#include#include#define TRUE 1#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef int ElemType;typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef struct stackBiTree *base;BiTree *top;int stacksize;SqStack;typedef struct queuenodeBiTree ch;struct queuenode *next;queuenode,*queueptr; typedef structqueueptr front;queueptr rear;linkqueue; Status InsertBiT(BiTree *T,int k)BiTNode *q,*p=*T; while(p)if(p-data=k) return ERROR; q=p;p=(kdata)?p-lchild:p-rchild; p=(BiTNode*)malloc(sizeof(BiTNode); p-data=k; p-lchild=p-rchild=NULL; if(*T=NULL) *T=p;else if(kdata) q-lchild=p;else q-rchild=p;return OK; BiTree CreateBiT(int n) BiTree T=NULL; int k,i; for(i=1;idata)if(PreOrderTraverse(T-lchild)if(PreOrderTraverse(T-rchild)return OK;return ERROR;elsereturn OK;Status InOrderTraverse(BiTree T)if(T)if(InOrderTraverse(T-lchild)if(Visit(T-data)if(InOrderTraverse(T-rchild)return OK;return ERROR;elsereturn OK;Status PostOrderTraverse(BiTree T)if(T)if(PostOrderTraverse(T-lchild)if(PostOrderTraverse(T-rchild)if(Visit(T-data)return OK;return ERROR;elsereturn OK;Status Visits(ElemType e,int m,int &t)if(e=m)t=1;return OK;Status Postsearch(BiTree T,int m,int &t)if(T)if(Postsearch(T-lchild,m,t)if(Postsearch(T-rchild,m,t)if(Visits(T-data,m,t)return OK;return ERROR;elsereturn OK;Status InitStack(SqStack &S)S.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree);if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status Push(SqStack &S,BiTree e)if(S.top-S.base=S.stacksize)S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree);if(S.base)return ERROR;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,BiTree &e)if(S.top=S.base)return ERROR;e=*-S.top;return OK;Status StackEmpty(SqStack &S)if(S.top=S.base)return 1;elsereturn 0;Status InOrderTraverses(BiTree T) SqStack s; InitStack(s); BiTree p;p=T; while (p|!StackEmpty(s) while(p) Push(s,p); p=p-lchild; Pop(s,p);Visit(p-data); p=p-rchild; return OK;void initqueue(linkqueue &q)q.front=q.rear=(queueptr)malloc(sizeof(queuenode);q.front-next=NULL;void enqueue(linkqueue &q,BiTree p)queueptr s;s=(queueptr)malloc(sizeof(queuenode);s-ch=p;s-next=NULL;q.rear-next=s;q.rear=s;void dequeue(linkqueue &q,BiTree &p)int data;queueptr s;s=q.front-next; p=s-ch; data=p-data; q.front-next=s-next; if(q.rear=s) q.rear=q.front; free(s); printf(%d ,data);int queueempty(linkqueue q)if(q.front-next=NULL)return 1;return 0;void traverse(BiTree bt)linkqueue q;BiTree p;initqueue(q);p=bt;enqueue(q,p);while(queueempty(q)!=1)dequeue(q,p);if(p-lchild!=NULL)enqueue(q,p-lchild);if(p-rchild!=NULL)enqueue(q,p-rchild);printf(n);int main()int m1,m2,n,i,t=0;BiTree T;scanf(%d,&n);T=CreateBiT(n);scanf(%d%d%d,&m1,&m2,&i);PreOrderTraverse(T);printf(n);InOrderTraverse(T);printf(n);PostOrderTraverse(T);printf(n);Postsearch(T,m1,t);if(t=1)printf(1n);elseprintf(0n);t=0;Postsearch(T,m2,t);if(t=1)printf(1n);elseprintf(0n);InsertBiT(&T,i);PreOrderTraverse(T);printf(n);InOrderTraverse(T);printf(n);PostOrderTraverse(T);printf(n);InOrderTraverses(T);printf(n);traverse(T);return 0;333333333333333333333333333333333333333333333333333333333333333333333333333333#include#include#define TRUE 1#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef int ElemType;typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef struct stackBiTree *base;BiTree *top;int stacksize;SqStack;typedef struct queuenodeBiTree ch;struct queuenode *next;queuenode,*queueptr; typedef structqueueptr front;queueptr rear;linkqueue; Status InsertBiT(BiTree *T,int k)BiTNode *q,*p=*T; while(p)if(p-data=k) return ERROR; q=p;p=(kdata)?p-lchild:p-rchild; p=(BiTNode*)malloc(sizeof(BiTNode); p-data=k; p-lchild=p-rchild=NULL; if(*T=NULL) *T=p;else if(kdata) q-lchild=p;else q-rchild=p;return OK; BiTree CreateBiT(int n) BiTree T=NULL; int k,i; for(i=1;idata)if(PreOrderTraverse(T-lchild)if(PreOrderTraverse(T-rchild)return OK;return ERROR;elsereturn OK;Status InOrderTraverse(BiTree T)if(T)if(InOrderTraverse(T-lchild)if(Visit(T-data)if(InOrderTraverse(T-rchild)return OK;return ERROR;elsereturn OK;Status PostOrderTraverse(BiTree T)if(T)if(PostOrderTraverse(T-lchild)if(PostOrderTraverse(T-rchild)if(Visit(T-data)return OK;return ERROR;elsereturn OK;Status Visits(ElemType e,int m,int &t)if(e=m)t=1;return OK;Status Postsearch(BiTree T,int m,int &t)if(T)if(Postsearch(T-lchild,m,t)if(Postsearch(T-rchild,m,t)if(Visits(T-data,m,t)return OK;return ERROR;elsereturn OK;Status InitStack(SqStack &S)S.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree);if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status Push(SqStack &S,BiTree e)if(S.top-S.base=S.stacksize)S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree);if(S.base)return ERROR;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,BiTree &e)if(S.top=S.base)return ERROR;e=*-S.top;return OK;Status StackEmpty(SqStack &S)if(S.top=S.base)return 1;elsereturn 0;Status InOrderTraverses(BiTree T) SqStack s; InitStack(s); BiTree p;p=T; while (p|!StackEmpty(s) while(p) Push(s,p); p=p-lchild; Pop(s,p);Visit(p-data); p=p-rchild; return OK;void initqueue(linkqueue &q)q.front=q.rear=(queueptr)malloc(sizeof(queuenode);q.front-next=NULL;void enqueue(linkqueue &q,BiTree p)queueptr s;s=(queueptr)malloc(sizeof(queuenode);s-ch=p;s-next=NULL;q.rear-next=s;q.rear=s;void dequeue(linkqueue &q,BiTree &p)int data;queueptr s;s=q.front-next; p=s-ch; data=p-data; q.front-next=s-next; if(q.rear=s) q.rear=q.front; free(s); printf(%d ,data);int queueempty(linkqueue q)if(q.front-next=NULL)return 1;return 0;void traverse(BiTree bt)linkqueue q;BiTree p;initqueue(q);p=bt;enqueue(q,p);while(queueempty(q)!=1)dequeue(q,p);if(p-lchild!=NULL)enqueue(q,p-lchild);if(p-rchild!=NULL)enqueue(q,p-rchild);printf(n);Status Exchange(BiTree &T)BiTree p;if(T)p=T-lchild;T-lchild=T-rchild;T-rchild=p;Exchange(T-lchild);Exchange(T-rchild);return OK;Status Depth(BiTree T)int depthval,depthLeft,depthRight;if(!T)depthval=0;elsedepthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);return depthval;Status countieaf(BiTree T,int &n)if(T)if(T-lchild=NULL&T-rchild=NULL)n+;countieaf(T-lchild,n);countieaf(T-rchild,n);return OK;int main()int m1,m2,n,i,t=0,k=0;BiTree T;scanf(%d,&n);T=CreateBiT(n);scanf(%d%d%d,&m1,&m2,&i);PreOrderTraverse(T);printf(n);InOrderTraverse(T);printf(n);PostOrderTraverse(T);printf(n);Postsearch(T,m1,t);if(t=1)printf(1n);elseprintf(0n);t=0;Postsearch(T,m2,t);if(t=1)printf(1n);elseprintf(0n);InsertBiT(&T,i);PreOrderTraverse(T);printf(n);InOrderTraverse(T);printf(n);PostOrderTraverse(T);printf(n);InOrderTraverses(T);printf(n);traverse(T);Exchange(T);PreOrderTraverse(T);printf(n);InOrderTraverse(T);printf(n);PostOrderTraverse(T);printf(n);Exchange(T);PreOrderTraverse(T);printf(n);InOrderTraverse(T);printf(n);PostOrderTraverse(T);printf(n);printf(%dn,Depth(T);countieaf(T,k);printf(%dn,k);return 0;444444444444444444444444444444444444444444444444444444444444444444444444444444#include#include#includetypedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; typedef char *HuffmanCode;void Select(HuffmanTree &HT,int n,int &s1,int &s2) int i; s1=-1;s2=-1; for (i=1;i=n;i+) if (HTi.parent=0)if (s1=-1)s1=i;else if (s2=-1)if (HTi.weightHTs1.weight)s2=s1;s1=i;e