#include<世裂陵stdio.h>
#include<stdlib.h>
#define MAX 100
//定义二叉树链表
struct Bitree
{
char c
struct Bitree *lchild,*rchild
}
//定义队列
struct Quene
{
struct Bitree *p//指向数的节点的指针
struct Quene *next
}
//定义哈夫曼树的结构
struct Huffman
{
int weight//权值
int tag
int parent,lchild,rchild
char ch
}
struct Bitree *creatBt()
{
struct Bitree *btree
char ch
cin>>ch
// "访问" *** 作为生成根结点
if(ch!='#')
{
btree=(struct Bitree * )malloc(sizeof(struct Bitree ))
btree->c=ch
btree->lchild=creatBt()// 递归建(遍历)左子树
btree->rchild=creatBt()// 递归建(遍历)右子树
}
if(ch=='#')
{
btree=NULL
}
return btree
}
//先序遍历递归
void preOrder1(struct Bitree *btree)
{
struct Bitree *p
p=btree
if(p!=NULL)
{
cout<<p->c<<" "
preOrder1(p->lchild)
preOrder1(p->rchild)
}
}
//中序遍历递归
void inOrder1(struct Bitree *btree)
{
struct Bitree *p
p=btree
if(p->lchild!=NULL)
inOrder1(p->lchild)
cout<<p->c<<" "
if(p->rchild!=NULL)
inOrder1(p->rchild)
}
//后序遍历递归
void postOrder1(struct Bitree *btree)
{
struct Bitree *p
p=btree
if(p->lchild!=NULL)
postOrder1(p->lchild)
if(p->rchild!=NULL)
postOrder1(p->rchild)
cout<<p->c<<" "
}
//非递归先序遍历
void preOrder2(struct Bitree *btree)
{
struct Bitree *p, *node[MAX]
int top=0
p=btree
do
{
while(p!=NULL)
{
cout<<p->c<<" "
node[top]=p
top++
p=p->lchild
}
if(top>0)
{
top--
p=node[top]
p=p->rchild
}
}
while(top>0||p!=NULL)
}
//非递归中序遍历
void inOrder2(struct Bitree *btree)
{
struct Bitree *p, *node[MAX]
int top=0
p=btree
do// while(top>搜戚0||p!=NULL)
{
while(p!=NULL)
{
node[top]=p
top++
p=p->lchild
}
if(top>0)
{
top--
p=node[top]
cout<<p->c<<" "
p=p->rchild
}
} while(top>0||p!=NULL)
}
//非递归源没后序遍历
void postOrder2(struct Bitree *btree)
{
struct Bitree *p, *node[MAX]
int top=0
p=btree
while(top>0||p!=NULL)
{
while(p!=NULL)
{
node[top]=p
top++
p=p->lchild
}
if(top>0)
{
top--
p=node[top]
if(p->rchild==NULL)
cout<<p->c<<" "
p=p->rchild
}
}
p=btree
cout<<p->c<<" "
}
//二叉树的高度
int btHeigh(struct Bitree *btree)
{
struct Bitree *p
p=btree
int hl=0, h2=0, max=0
if(p!=NULL)
{
hl=btHeigh(p->lchild) //求左子树的深度
h2=btHeigh(p->rchild) //求右子树的深度
max=hl>h2?hl: h2
return(max+1)// 返回树的深度
}
else
return 0
}
//求二叉树的叶子个数
int numLeave(struct Bitree *btree)
{
struct Bitree *p
p=btree
int static n=0//静态变量计数
if(p!=NULL)
{
if(p->lchild==NULL&&p->rchild==NULL)
n++//若root所指结点为叶子, 则累加
numLeave(p->lchild)
numLeave(p->rchild)
return n
}
else
return 0
}
//借助队列实现二叉树的层次遍历。
void btQuene(struct Bitree *btree)
{
struct Quene *head,*rear,*temp
head=(struct Quene*)malloc(sizeof(struct Quene))//给队列头指针分配器空间
head->p=btree
head->next=NULL
rear=head
while(head!=NULL)
{
if(head->p->lchild!=NULL)
{
temp=(struct Quene *)malloc(sizeof(struct Quene))//中间变量暂时保存数的结点
temp->p=head->p->lchild
temp->next=NULL
rear->next=temp//将新结点连接在前一个结点的后面
rear=temp
}
if(head->p->rchild!=NULL)
{
temp=(struct Quene *)malloc(sizeof(struct Quene))
temp->p=head->p->rchild
temp->next=NULL
rear->next=temp
rear=temp
}
temp=head
cout<<head->p->c
head=head->next
free(temp)
}
}
//建立哈夫曼树
void creatHfm()
{
struct Huffman *HF
int num
int i,j,x1,x2,m1,m2
cout<<"输入字符个数；"
cin>>num
if(num<=1)
{
cout<<"不能建立哈夫曼树！"<<endl
return
}
HF=new struct Huffman[2*num-1]
char c
//构造叶子结点数为num,权值为weight的哈夫曼树HF[]
for(i=0i<numi++)
{
cout<<"请输入第"<<i+1<<"个字符值:"
cin>>c
HF[i].ch=c
cout<<"请输入该字符的权值:"
cin>>HF[i].weight
HF[i].parent=-1
HF[i].lchild=-1
HF[i].rchild=-1
HF[i].tag=0
}
//构造非叶子结点
for(i=0i<num-1i++)//合并n-1次
{
m1=m2=32767//m1是最小值单元，m2为次小值
x1=x2=0//x1，x2为下标号
for(j=0j<num+1j++)//找最小权值和次小权值
{
if(HF[i].weight<m1&&HF[j].tag==0)
{
m2=m1
x2=x1
m1=HF[j].weight
x1=j
}
else if(HF[j].weight<m2&&HF[j].tag==0)
{
m2=HF[j].weight
x2=j
}
}
//将两棵子树合并成一棵新树
HF[x1].parent=num+i//x1,x2对应的子树分别作为n+i的左右子树
HF[x2].parent=num+i
HF[x1].tag=1
HF[x2].tag=1
HF[num+i].weight=HF[x1].weight+HF[x2].weight//新书跟的权值为左右树根的权值之和
HF[num+i].lchild=x1//n+i的做孩子是x1
HF[num+i].rchild=x2
}
cout<<"哈夫曼树创建成功!"<<endl
}
//删除值为x的结点，并释放相应的空间
void btFree(struct Bitree *btree,char x)
{
struct Bitree *p
p=btree
if(p!=NULL)
{
if(p->c==x)
{
free(p)
cout<<"释放成功！"<<endl
}
else
{
btFree(p->lchild,x)
btFree(p->rchild,x)
}
}
else
cout<<"空间释放失败！"<<endl
}
void main()
{
int key
int depth
int numLea
struct Bitree *btree
cout<<"输入数的节点，'#'表示空节点:"<<endl
btree=creatBt()
cout<<"二叉树创建成功!"<<endl
cout<<endl
cout<<"***********************************"<<endl
cout<<"选择菜单 "<<endl
cout<<"1、递归先序遍历二叉树 "<<endl
cout<<"2、递归中序遍历二叉树 "<<endl
cout<<"3、递归后序遍历二叉树 "<<endl
cout<<"4、非递归先序遍历二叉树 "<<endl
cout<<"5、非递归中序遍历二叉树 "<<endl
cout<<"6、非递归后序遍历二叉树 "<<endl
cout<<"7、求二叉树的高度 "<<endl
cout<<"8、求二叉树的叶子结点个数 "<<endl
cout<<"9、队列实现二叉树层次遍历"<<endl
cout<<"10、建立哈夫曼树 "<<endl
cout<<"11、释放空间 "<<endl
cout<<"***********************************"<<endl
for(key!=0)
{
cout<<"输入选项，(0表示结束 *** 作):"
cin>>key
switch(key)
{
case 1:
cout<<"递归先序遍历结果是:"
preOrder1(btree)
cout<<endl
break
case 2:
cout<<"递归中序遍历结果是:"
inOrder1(btree)
cout<<endl
break
case 3:
cout<<"递归后序遍历结果是:"
postOrder1(btree)
cout<<endl
break
case 4:
cout<<"非递归先序遍历结果是:"
preOrder2(btree)
cout<<endl
break
case 5:
cout<<"非递归中序遍历结果是:"
inOrder2(btree)
cout<<endl
break
case 6:
cout<<"非递归后序遍历结果是:"
postOrder2(btree)
cout<<endl
break
case 7:
depth=btHeigh(btree)
cout<<"二叉树的高度为"
cout<<depth<<endl
break
case 8:
numLea=numLeave(btree)
cout<<"二叉树的叶子结点数为"
cout<<numLea<<endl
break
case 9:
cout<<"层次遍历的结果为:"
btQuene(btree)
cout<<endl
break
case 10:
creatHfm()
break
case 11:
char c
cout<<"输入要释放的结点:"
cin>>c
btFree(btree,c)
break
default:
printf("\n输入选项错误！\n ")
}
}
}
1.//存储结构：deque//多项式相加的基本过程：(1)、两个多项消丛式的最高次幂较高的那个，存入endPower；
// (2)、从ix=0开始，对多项式的对裂桥态应项做运算；
// (3)、递增，如果ix>=endPower，结束；否则，重复2和3。
#include <deque>
#include <iostream>
using namespace std
class Expression {
public:
Expression() { int highestPower=0factors=deque<double>(0.0)}
~Expression() { factors.clear()}
bool create()
void display()
Expression &add( Expression &another )
Expression &subtract( Expression &another )
int HighestPower() const
double Factor( int index ) const
private:
int highestPower//最高次幂
deque<double>factors//系数（从最高次幂~0的系数都保存，如果某次幂不存在，则肆源系数为0）
}
bool
Expression::
create() {
cout<<"Enter the highest power: "
cin>>highestPower
double dTemp
for( int ix=highestPowerix>=0--ix ) {
cout<<"Enter the factor of x^"<<ix<<" (double): "
cin>>dTemp
factors.push_front( dTemp )
}
return true
}
void
Expression::
display() {
for( int ix=highestPowerix>=0--ix ) {
if( ix<highestPower &&factors.at(ix)>0 )
cout<<"+"
if( factors.at(ix)!=0 ) {
cout<<factors.at(ix)
if( ix>0 )
cout<<"x"<<"^"<<ix
}
}
cout<<endl
}
Expression &
Expression::
add( Expression &another ) {
int endPower = (highestPower>another.HighestPower()) ? highestPower : another.HighestPower()
for( int ix=0ix<=endPower++ix ) {
if( ix>highestPower ) {
factors.push_back( another.Factor(ix) )
highestPower=ix
} else if( ix<=another.HighestPower() ){
factors.at(ix) += another.Factor(ix)
}
}
return *this
}
Expression &
Expression::
subtract( Expression &another ) {
int endPower = (highestPower>another.HighestPower()) ? highestPower : another.HighestPower()
for( int ix=0ix<=endPower++ix ) {
if( ix>highestPower ) {
factors.push_back( (-1)*another.Factor(ix) )
highestPower=ix
} else if( ix<=another.HighestPower() ){
factors.at(ix) -= another.Factor(ix)
}
}
return *this
}
int
Expression::
HighestPower() const {
return highestPower
}
double
Expression::
Factor( int index ) const {
return factors.at(index)
}
int main() {
Expression aExpression, bExpression
if( aExpression.create() )
aExpression.display()
if( bExpression.create() )
bExpression.display()
cout<<"aExpression.add( bExpression ): "<<endl
aExpression.add( bExpression )
aExpression.display()
cout<<"aExpression.subtract( bExpression ): "<<endl
aExpression.subtract( bExpression )
aExpression.display()
}
2.char *a
int m
cout<<"输入猴子个数:"<<endl
cin>>m
a=new char[m]
cout<<"输入N:"<<endl
int n
cin>>n
if(n>m)
{
cout<<"输入错误,必须小于M="<<m<<,重输入:"<<endl
cin>>n
}
for(int i=0i<mi++)
{
a[i]=1
}
bool c=true
for (int j=0j++)
{
for(int k=0k<mk++)
{
if(a[k]!=0)
{
c=false
break
}
else c=true
}
if(c!=true)//判断退出
break
if(j%n==0)
a[j%m]=0
}
int result=j%m
cout<<"最后猴子的序号是:"<<result<<endl
---------------2-----------------
insert(int arry[],int address,int data)
{
int l=arry.length()
for(int i=l-1i>addressi--)
{
arry[i]=arry[i-1]
}
arry[i]=data
}
sort01(int a[])
{
int temp
int l=a.length()
temp=a[0]
for(int i=1i<li++)
{
if(a[i]<temp)
insert(a,i-1,temp)
temp=a[i]
}
}
------------------------------------
swap(int *x,int *y)
{
int temp
temp=*x
*y=temp
*x=*y
}
l=a.length
temp1=a[0]temp2=a[1]
for(int k=0k<lk++)
for(int i=ki<li++)
{
if(a[i]>a[i+1])
swap(a[i],a[i+1)
}
3.//二叉树
struct node {
int key
node* left
node* right
}
//链表
struct list {
node* data
list* next
}
//队列
struct queue {
list* front
int count
list* rear
}
//Enqueue for Breadth-First Traversal
queue* BST::_enqueue (queue* Q, node* n) //进队
{
list* pNew = new list
pNew->data = n
pNew->next = NULL
if (Q->count == 0)
Q->front = pNew
else
Q->rear->next = pNew
Q->rear = pNew
Q->count++
return Q
}
//Dequeue for Breadth-First Traversal
node* BST::_dequeue (queue* &Q) //出队
{
if (Q->count == 1)
Q->rear = NULL
list* pDel = Q->front
node* temp = pDel->data
Q->front = Q->front->next
Q->count--
delete pDel
pDel = NULL
return temp
}
//Breadth-First Traversal (层序遍历）
void BST::_traverse (const node* T)
{
queue* Q = new queue
Q->front = Q->rear = NULL
Q->count = 0
while (T != NULL)
{
cout <<T->key <<" "
if (T->left != NULL)
Q = _enqueue (Q, T->left)//左孩子进队
if (T->right != NULL)
Q = _enqueue (Q, T->right)//右孩子进队
if (Q->count != 0) //排队输出下一个将要处理的节点
T = _dequeue (Q)
else //队列为空，跳出
T = NULL
}
return
}
你看看这个行不
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）