⑴ 确定表示问题所需的数据及其特性；
⑵ 确定必须支持的基本 *** 作，并度量每种 *** 作所受的时、空资源限制；
⑶ 选择（或设计）最接近这些开销的数据结构。
/* 二叉树应用 */#include "stdio.h"#include "stdlib.h"typedef char ElemType /* 结点数据的类型 */
typedef struct BiTNode{
ElemType data
struct BiTNode *lchild,*rchild
}BiTNode /* 树结点类型 *//*栈的定义及基本 *** 作*/
#define MaxSize 100
typedef BiTNode* SElemType /* 栈和队列的结点类型，用于存放树结点 */
typedef struct {
SElemType elem[MaxSize]
int top
}SqStack /* 栈 */void InitStack(SqStack *pS) /* 初始化栈,开始时栈为空 */
{
pS->top=0/* top指向栈顶的上一个元素 */
}int Push(SqStack *pS,SElemType e) /* 进栈 */
{
if (pS->top==MaxSize-1) /* 栈满 */
return 0 pS->elem[pS->top]=e
pS->top=pS->top+1
return 1
}int Pop(SqStack *pS,SElemType *pe)/* 出栈 */
{
if (pS->top==0) /* 栈空 */
return 0 pS->top = pS->top - 1
*pe = pS->elem[pS->top]
return 1
}/*队列（循环队列）的定义及基本 *** 作*/typedef struct {
SElemType elem[MaxSize]
int front,rear
}SqQueue /* 队列 */void InitQueue(SqQueue* pQ) /* 初始化队列,开始时队列为空 */
{
pQ->front=pQ->rear=0
}int EnQueue(SqQueue* pQ,SElemType e) /* 进队 */
{
if ((pQ->rear+1)%MaxSize == pQ->front) /* 队满 */
return 0
pQ->elem[pQ->rear] = e
pQ->rear = (pQ->rear+1)%MaxSize
return 1
}int DeQueue(SqQueue* pQ,SElemType* pe) /* 出队 */
{
if (pQ->rear == pQ->front)/* 队空 */
return 0
*pe = pQ->elem[pQ->front]
pQ->front = (pQ->front+1)%MaxSize
return 1
}
/* 先根遍历 */
void preorder(BiTNode *bt)
{ if(bt!=NULL)
{ printf("%c ",bt->data)
preorder(bt->lchild)
preorder(bt->rchild)
}
} /* 中根遍历 */
void inorder(BiTNode *bt)
{ if(bt!=NULL)
{ inorder(bt->lchild)
printf("%c ",bt->data)
inorder(bt->rchild)
}
}
/* 后根遍历 */
void postorder(BiTNode *bt)
{ if(bt!=NULL)
{ postorder(bt->lchild)
postorder(bt->rchild)
printf("%c ",bt->data)
}
}/* 非递归算法的中根遍历（后进先出，用了栈的思想） */
void inorder_fdg(BiTNode *bt)
{
BiTNode *p
SqStack s
InitStack(&s)
p=bt
do
{ while(p!=NULL)
{ Push(&s,p)
p=p->lchild
}
if(s.top!=0)
{ Pop(&s,&p)
printf("%c ",p->data)
p=p->rchild
}
}while(s.top!=0||p!=NULL)
}/* 用队列实现层次遍历 */
void lev_traverse(BiTNode* bt)
{
SqQueue q
BiTNode *p
p=bt
InitQueue(&q)
EnQueue(&q,p)
while(!(q.rear==q.front)) { /* 当队列不空 */
DeQueue(&q,&p)
printf("%c ",p->data) if(p->lchild!=NULL)
EnQueue(&q,p->lchild) if(p->rchild!=NULL)
EnQueue(&q,p->rchild)
}
}
/* 利用先根序列建立二叉树，空的子树也要输入，用空格表示,建立的树通过函数返回,避免使用指针的指针 */
BiTNode *crt_bt_pre()
{ char ch
BiTNode *bt
scanf("%c",&ch) if(ch==' ') bt=NULL
else
{ bt=(BiTNode *)malloc(sizeof(BiTNode))
bt->data=ch
bt->lchild=crt_bt_pre()
bt->rchild=crt_bt_pre()
}
return(bt)
}/* 利用先根序列建立二叉树，空的子树也要输入，用空格表示,建立的树通过参数返回,注意和上述方法比较，想想还有什么办法？ */
void crt_bt_pre_2(BiTNode **bt)
{ char ch
scanf("%c",&ch) if(ch==' ') (*bt)=NULL
else
{ (*bt)=(BiTNode *)malloc(sizeof(BiTNode))
(*bt)->data=ch
crt_bt_pre_2(&(*bt)->lchild)
crt_bt_pre_2(&(*bt)->rchild)
}
}
/* 求叶子数 */
int leaf(BiTNode *bt)
{
if (bt==NULL) return 0
else {
if (bt->lchild==NULL&&bt->rchild==NULL) return 1
else
return leaf(bt->lchild)+leaf(bt->rchild)
}}/* 求树的高度 */
int high(BiTNode *bt)
{
if (bt==NULL) return 0
else {
return max(high(bt->lchild),high(bt->rchild))+1
}}
/* 二叉树的释放*/
void freetree(BiTNode *bt)
{ if(bt!=NULL)
{ freetree(bt->lchild)
freetree(bt->rchild)
free(bt)
bt=NULL
}
}main()
{
BiTNode *T,*temp[20] /* 笨方法建立二叉树 */
/* temp[0]=(BiTNode*)malloc(sizeof(BiTNode))
temp[0]->data = '-' temp[1]=(BiTNode*)malloc(sizeof(BiTNode))
temp[1]->data = '+'
temp[0]->lchild = temp[1] temp[2]=(BiTNode*)malloc(sizeof(BiTNode))
temp[2]->data = '/'
temp[0]->rchild = temp[2] temp[3]=(BiTNode*)malloc(sizeof(BiTNode))
temp[3]->data = 'a'
temp[3]->lchild=NULLtemp[3]->rchild=NULL
temp[1]->lchild = temp[3] temp[4]=(BiTNode*)malloc(sizeof(BiTNode))
temp[4]->data = '*'
temp[1]->rchild = temp[4] temp[5]=(BiTNode*)malloc(sizeof(BiTNode))
temp[5]->data = 'e'
temp[5]->lchild=NULLtemp[5]->rchild=NULL
temp[2]->lchild = temp[5] temp[6]=(BiTNode*)malloc(sizeof(BiTNode))
temp[6]->data = 'f'
temp[6]->lchild=NULLtemp[6]->rchild=NULL
temp[2]->rchild = temp[6] temp[7]=(BiTNode*)malloc(sizeof(BiTNode))
temp[7]->data = 'b'
temp[7]->lchild=NULLtemp[7]->rchild=NULL
temp[4]->lchild = temp[7] temp[8]=(BiTNode*)malloc(sizeof(BiTNode))
temp[8]->data = '-'
temp[4]->rchild = temp[8] temp[9]=(BiTNode*)malloc(sizeof(BiTNode))
temp[9]->data = 'c'
temp[9]->lchild=NULLtemp[9]->rchild=NULL
temp[8]->lchild = temp[9] temp[10]=(BiTNode*)malloc(sizeof(BiTNode))
temp[10]->data = 'd'
temp[10]->lchild=NULLtemp[10]->rchild=NULL
temp[8]->rchild = temp[10] T=temp[0] */
/*输出树和各种遍历、叶子数、树的高度*/
/*printf("\ntree:\n")
printf(" -\n")
printf(" +/\n")
printf(" a *e f\n")
printf("0 0b - 0 00 0\n")
printf(" 0 0c d\n") printf("\n\nPreOrder:\n")
preorder(T) printf("\nInOrder:\n")
inorder(T) printf("\nPostOrder:\n")
postorder(T) printf("\ninorder_fdg:\n")
inorder_fdg(T) printf("\nlev_traverse:\n")
lev_traverse(T)
printf("\nleaf num:%d",leaf(T))
printf("\nTree high:%d",high(T))
freetree(T) */ /* 按先序列建树，用空格表示空子树*/ printf("\n\nplease input inorder:such as 'abc de g f '\n")
/*T = crt_bt_pre()*/
crt_bt_pre_2(&T) printf("\n\nPreOrder:\n")
preorder(T) printf("\nInOrder:\n")
inorder(T) printf("\nPostOrder:\n")
postorder(T) printf("\ninorder_fdg:\n")
inorder_fdg(T) printf("\nlev_traverse:\n")
lev_traverse(T)
printf("\nleaf num:%d",leaf(T))
printf("\nTree high:%d",high(T))
freetree(T)
getch()
}
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条）