编程论坛的作业贴解决合集
目录引用请注明 hzh512
作业贴1：十进制数转二进制数，并判断出有1的位置
作业贴 2：线索二叉树的中序线索化及其遍历
作业贴3：稀疏矩阵的加减乘除转置运算
作业贴4：完全二叉树的判定算法
作业贴5：多项式的相 乘
作业贴6：Huffman 编码
作业贴7：二叉树的操作，创建、各种遍历
作业贴8：［问题描述］设有n个人围坐一圈，现从某个 人开始报数，数到m的人出列，接着从下一个人开始重新开始报数， 数到m的人又
出列，如次下去，直到 所有的人都出列为止。试设计确定他们出列的顺序的程序
1）在顺序存储结构上实现以上过程。
2）在循环链表上实现以上过程。
作业贴9：链表的插入排序
内容
作业贴1：十进制数转二进制数，并判断出有1的位置
例程：
程序代码：/*
十进制数转二进制数，并判断出有1的位置
程序的主要思想是：
按位与的特点是，是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时，结果位才为1，否则为0。
也就是说，按位与运算有3个对象，分别是两个参与运算的两个数和运算有的结果。这个和小学学习的普通加法一样。如：a+b=c，,a,b,c分别是3个对象。同样的，与运算也是一一样的意思：a & b = c.
只不过是与的意思和加法的意思不一样而已。
根据题目要求，我们已经得到了一个参与运算的数据，就是要转换的数，现在我们需要得到转换后的数，根据与运算规则，我们构造一个数，分别和待转换的数进行与运算，得到每一位的值，要么是0，要么是1。
*/
#include <stdio.h>
int main(void)
{
const int iTimes=sizeof(int) * 8;
int x;
int iMask=1;
printf("\nDEC:");
scanf("%d",&x);
int x2[iTimes];
int i;
for( i=0 ; i<iTimes ; i++ )
{
x2[i]=x & iMask;
iMask = iMask << 1;
}
printf("\n(%d)Binary=",x);
for( i=iTimes -1 ; i >=0 ; i-- )
{
printf("%d",x2[i] ? 1 : 0 );
if(i%4==0)
printf(" ");
}
printf("\n 有1的二进制位是：");
for( i=iTimes -1 ; i >=0 ; i-- )
{
if(x2[i])
printf(" %d ",i);
}
printf("\n");
return 0;
}作业贴2：线索二叉树的中序线索化及其遍历例程：
程序代码：#include <stdio.h>//测试值：abc@@de@g@@f@@@
#include <stdlib.h>
#define Link 0
#define Thread 1
typedef char TElemType;
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild;
int LTag,RTag;
}BiThrNode,*BiThrTree;
////////
BiThrTree pre;//全局变量
////////
BiThrTree CreatBiThrTree();//先序创建二叉树
void InThreading(BiThrTree p);//中序遍历二叉树
void InOrderThreading(BiThrTree *Thrt,BiThrTree T);//中序线索化二叉树
void Visit(char c);
void InorderTraverse_Thr(BiThrTree T);//中序遍历二叉树
void main()
{
BiThrTree t;
BiThrTree thrtnode=NULL;
printf("请按先序遍历序列输入二叉树中各个结点的值(字符)，若为空树时输入空格键:\n");
printf("<说明：例如参考数据为:abc@@de@g@@f@@@，则用空格键表示@,输完后再输入一个回车键.>\n");
t=CreatBiThrTree();
printf("中序线索化二叉树:\n");
InOrderThreading(&thrtnode,t);
printf("线索化工作已经完成!\n");
printf("中序遍历线索二叉树:\n");
InorderTraverse_Thr(thrtnode);
}
BiThrTree CreatBiThrTree()//先序创建二叉树
{
TElemType ch;
BiThrTree T;
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else
{
T=(BiThrTree)malloc(sizeof(BiThrNode));
if(!T)
exit(0);
T->data=ch;
T->LTag=Link;
T->RTag=Link;
T->lchild=CreatBiThrTree();
T->rchild=CreatBiThrTree();
}
return T;
}
void InThreading(BiThrTree p)//中序遍历二叉树
{
if(p)
{
InThreading(p->lchild);//左子树线索化
if(!p->lchild)//前驱线索
{
p->LTag=Thread;
p->lchild=pre;
}
if(!pre->rchild)//后继线索
{
pre->RTag=Thread;
pre->rchild=p;
}
pre=p;//保持pre 指向p的前驱
InThreading(p->rchild);//右子树线索化
}
}
void InOrderThreading(BiThrTree *Thrt,BiThrTree T)//中序线索化二叉树
{
if(!((*Thrt)=(BiThrTree)malloc(sizeof(BiThrNode))))
exit(0);
(*Thrt)->LTag=Link;
(*Thrt)->RTag=Thread;
(*Thrt)->rchild=(*Thrt);
if(!T)
(*Thrt)->lchild=(*Thrt);
else
{
(*Thrt)->lchild=T;
pre=(*Thrt);
InThreading(T);//中序遍历进行中序线索化
pre->rchild=(*Thrt);//最后一个结点线索化
pre->RTag=Thread;
(*Thrt)->rchild=pre;
}
}
void Visit(char c)
{
printf(" %c ",c);
}
void InorderTraverse_Thr(BiThrTree T)//中序遍历二叉树
{
BiThrTree p;
p=T->lchild;
while(p!=T)//空树或遍历结束时,p=T
{
while(p->LTag==Link)
p=p->lchild;
Visit(p->data);//访问左子树为空的结点
while(p->RTag==Thread&&p->rchild!=T)//访问后继结点
{
p=p->rchild;
Visit(p->data);
}
p=p->rchild;
}
}作业贴3：稀疏矩阵的加减乘除转置运算例程：
程序代码：#include <iostream>
#include <iomanip>
using namespace std;
const int MAXSIZE=100; // 定义非零元素的对多个数
const int MAXROW=10; // 定义数组的行数的最大值
typedef struct
{ // 定义三元组的元素
int i,j;
int e;
} Triple;
typedef struct
{ // 定义普通三元组对象
Triple data[MAXSIZE+1];
int mu,nu,tu;
} TSMatrix;
typedef struct
{ // 定义带链接信息的三元组对象
Triple data[MAXSIZE+2];
int rpos[MAXROW+1];
int mu,nu,tu;
} RLSMatrix;
typedef struct OLNode
{ // 定义十字链表元素
int i,j;
int e;
struct OLNode *right,*down; // 该非零元所在行表和列表的后继元素
}OLNode,*OLink;
typedef struct
{ // 定义十字链表对象结构体
OLink *rhead,*chead;
int mu,nu,tu; // 系数矩阵的行数，列数，和非零元素个数
}CrossList;
template <class P>
bool InPutTSMatrix(P & T,int y)
{ //输入矩阵，按三元组格式输入
cout<<"输入矩阵的行，列和非零元素个数:"<<endl;
cin>>T.mu>>T.nu>>T.tu;
cout<<"请输出非零元素的位置和值(从1开始记):"<<endl;
int k=1;
for(;k<=T.tu;k++)
cin>>T.data[k].i>>T.data[k].j>>T.data[k].e;
return true;
}
template <class P>
bool OutPutSMatrix(P T)
{ // 输出矩阵，按标准格式输出
int m,n,k=1;
for(m=0;m<T.mu;m++)
{
for(n=0;n<T.nu;n++)
{
if((T.data[k].i-1)==m&&(T.data[k].j-1)==n)
{
cout.width(4);
cout<<T.data[k++].e;
}
else
{
cout.width(4); cout<<"0";
}
}
cout<<endl;
}
return true;
}
// 求矩阵的转置矩阵
bool TransposeSMatrix( )
{
TSMatrix M,T; //定义预转置的矩阵
InPutTSMatrix(M, 0); //输入矩阵
int num[MAXROW+1];
int cpot[MAXROW+1]; // 构建辅助数组
int q,p,t;
T.tu=M.tu; T.mu=M.nu; T.nu=M.mu;
if(T.tu)
{
for(int col=1;col<=M.nu;col++)
num[col]=0;
for(t=1;t<=M.tu;t++)
++num[M.data[t].j];
cpot[1]=1;
for(int i=2;i<=M.nu;i++)
cpot[i]=cpot[i-1]+num[i-1]; // 求出每一列中非零元素在三元组中出现的位置
for(p=1;p<=M.tu;p++)
{
col=M.data[p].j;
q=cpot[col];
T.data[q].i=col;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
++cpot[col];
}
}
cout<<"输入矩阵的转置矩阵为"<<endl;
OutPutSMatrix(T);
return true;
}
bool Count(RLSMatrix &T)
{
int num[MAXROW+1];
for(int col=1;col<=T.mu;col++)
num[col]=0;
for(col=1;col<=T.tu;col++)
++num[T.data[col].i];
T.rpos[1]=1;
for(int i=2;i<=T.mu;i++)
T.rpos[i]=T.rpos[i-1]+num[i-1]; // 求取每一行中非零元素在三元组中出现的位置
return true;
}
// 两个矩阵相乘
bool MultSMatrix ( )
{
RLSMatrix M,N,Q; // 构建三个带“链接信息”的三元组表示的数组
InPutTSMatrix(M,1); // 用普通三元组形式输入数组
InPutTSMatrix(N,1);
Count(M); Count(N);
if(M.nu!=N.mu) return false;
Q.mu=M.mu; Q.nu=N.nu; Q.tu=0; // Q初始化
int ctemp[MAXROW+1]; // 辅助数组
int arow,tp,p,brow,t,q,ccol;
if(M.tu*N.tu)
{ // Q是非零矩阵
for( arow=1;arow<=M.mu;arow++)
{
for(int x=1;x<=N.nu;x++) // 当前行各元素累加器清零
ctemp[x]=0;
Q.rpos[arow]=Q.tu+1; // 当前行的首个非零元素在三元组中的位置为此行前所有非零元素+1
if(arow<M.mu)
tp=M.rpos[arow+1];
else
tp=M.tu+1;
for(p=M.rpos[arow];p<tp;p++)
{ // 对当前行每个非零元素进行操作
brow=M.data[p].j; // 在N中找到i值也操作元素的j值相等的行
if(brow<N.mu)
t=N.rpos[brow+1];
else
t=N.tu+1;
for(q=N.rpos[brow];q<t;q++)
{ // 对找出的行当每个非零元素进行操作
ccol=N.data[q].j;
ctemp[ccol] += M.data[p].e*N.data[q].e; // 将乘得到对应值放在相应的元素累加器里面
}
}
for(ccol=1;ccol<=Q.nu;ccol++) // 对已经求出的累加器中的值压缩到Q中
if(ctemp[ccol])
{
if(++Q.tu>MAXSIZE)
return false;
Q.data[Q.tu].e=ctemp[ccol];
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
}
}
}
OutPutSMatrix(Q);
return true;
}
bool CreateSMatrix_OL(CrossList & M)
{ // 创建十字链表
int x,y,m;
cout<<"请输入矩阵的行，列，及非零元素个数"<<endl;
cin>>M.mu>>M.nu>>M.tu;
if(!(M.rhead=(OLink*)malloc((M.mu+1)*sizeof(OLink)))) exit(0);
if(!(M.chead=(OLink*)malloc((M.nu+1)*sizeof(OLink)))) exit(0);
for(x=0;x<=M.mu;x++)
M.rhead[x]=NULL; // 初始化各行，列头指针，分别为NULL
for(x=0;x<=M.nu;x++)
M.chead[x]=NULL;
cout<<"请按三元组的格式输入数组："<<endl;
for(int i=1;i<=M.tu;i++)
{
cin>>x>>y>>m; // 按任意顺序输入非零元，（普通三元组形式输入）
OLink p,q;
if(!(p=(OLink)malloc(sizeof(OLNode))))
exit(0); // 开辟新节点，用来存储输入的新元素
p->i=x; p->j=y; p->e=m;
if(M.rhead[x]==NULL||M.rhead[x]->j>y)
{
p->right=M.rhead[x]; M.rhead[x]=p;
}
else
{
for(q=M.rhead[x];(q->right)&&(q->right->j<y);q=q->right); // 查找节点在行表中的插入位置
p->right=q->right; q->right=p; // 完成行插入
}
if(M.chead[y]==NULL||M.chead[y]->i>x)
{
p->down=M.chead[y]; M.chead[y]=p;
}
else
{
for(q=M.chead[y];(q->down)&&(q->down->i<x);q=q->down); // 查找节点在列表中的插入位置
p->down=q->down; q->down=p; // 完成列插入
}
}
return true;
}
bool OutPutSMatrix_OL(CrossList T)
{ // 输出十字链表，用普通数组形式输出
for(int i=1;i<=T.mu;i++)
{
OLink p=T.rhead[i];
for(int j=1;j<=T.nu;j++)
{
if((p)&&(j==p->j))
{
cout<<setw(3)<<p->e;
p=p->right;
}
else
cout<<setw(3)<<"0";
}
cout<<endl;
}
return true;
}
//矩阵的加法
bool AddSMatrix()
{
CrossList M,N; // 创建两个十字链表对象，并初始化
CreateSMatrix_OL(M);
CreateSMatrix_OL(N);
cout<<"输入的两矩阵的和矩阵为："<<endl;
OLink pa,pb,pre ,hl[MAXROW+1]; //定义辅助指针，pa，pb分别为M,N当前比较的元素，pre为pa的前驱元素
for(int x=1;x<=M.nu;x++)
hl[x]=M.chead[x];
for(int k=1;k<=M.mu;k++)
{ // 对M的每一行进行操作
pa=M.rhead[k]; pb=N.rhead[k]; pre=NULL;
while(pb)
{ // 把N中此行的每个元素取出，
OLink p;
if(!(p=(OLink)malloc(sizeof(OLNode))))
exit(0); // 开辟新节点，存储N中取出的元素
p->e=pb->e; p->i=pb->i; p->j=pb->j;
if(NULL==pa||pa->j>pb->j)
{ // 当 M此行已经检查完或者pb因该放在pa前面
if(NULL==pre)
M.rhead[p->i]=p;
else
pre->right=p;
p->right=pa;
pre=p;
if(NULL==M.chead[p->j])
{ // 进行列插入
M.chead[p->j]=p;
p->down=NULL;
}
else
{
p->down=hl[p->j]->down;
hl[p->j]->down=p;
}
hl[p->j]=p;
pb=pb->right;
}
else
if((NULL!=pa)&&pa->j<pb->j)
{ // 如果此时的pb元素因该放在pa后面，则取以后的pa再来比较
pre=pa; pa=pa->right;
}
else
if(pa->j==pb->j)
{ // 如果pa，pb位于同一个位置上，则将值相加
pa->e += pb->e;
if(!pa->e)
{ // 如果相加后的和为0，则删除此节点，同时改变此元素坐在行，列的前驱元素的相应值
if(NULL==pre) // 修改行前驱元素值
M.rhead[pa->i]=pa->right;
else
pre->right=pa->right;
p=pa; pa=pa->right;
if(M.chead[p->j]==p)
M.chead[p->j]=hl[p->j]=p->down; // 修改列前驱元素值
else
hl[p->j]->down=p->down;
free(p);
pb=pb->right;
}
else
{
pa=pa->right; pb=pb->right;
}
}
}
}
OutPutSMatrix_OL(M);
return true;
}
int main()
{
cout.fill('*');
cout<<setw(80)<<'*';
cout.fill(' ');
// system("color 0C");
cout<<setw(50)<<"***欢迎使用矩阵运算程序***"<<endl; //输出头菜单
cout.fill('*');
cout<<setw(80)<<'*';
cout.fill(' ');
cout<<"请选择要进行的操作："<<endl;
cout<<"1:矩阵的转置。"<<endl;
cout<<"2:矩阵的加（减）法。"<<endl;
cout<<"3:矩阵的乘法。"<<endl;
cout<<"4:推出程序。"<<endl;
char c=getchar();
if(c=='1')
TransposeSMatrix( ); //调用矩阵转置函数
else
if(c=='2')
AddSMatrix(); //调用矩阵相加函数
else
if(c=='3')
MultSMatrix (); //调用矩阵相乘函数
else
exit(0); //退出
return 0;
} 作业贴4：完全二叉树的判定算法例程：
程序代码：/*对二叉树进行层次遍历,在遍历过程中对每一个结点进行检查:
(1)如果当前结点没有右子树,则剩下的全部结点必须既没有左子树,又没有右子树;
(2)如果当前结点有右子树,则它必须也有左子树.
如果同时满足(1)(2),则是完全二叉树;否则不是.
你看看你那一条不满足。*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//////////////////////////////////////////////队列定义
typedef struct QNode
{
BiTree data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
////////////////////////////////////队列的基本操作
void InitQueue(LinkQueue *Q)
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q->front) exit(0);
Q->front->next=NULL;
}
void DestoryQueue(LinkQueue *Q)
{
while(Q->front)//*******
{
Q->rear=Q->front->next;
free(Q->front);
Q->front=Q->rear;
}
}
void EnQueue(LinkQueue *Q,BiTNode *e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(0);
p->data=e;//说明这个结点的两个域1
p->next=NULL;//2
Q->rear->next=p;
Q->rear=p;
}
void DeQueue(LinkQueue *Q,BiTree *e)
{
QueuePtr p;
if(Q->front==Q->rear) exit(0);
p=Q->front->next;
*e=p->data;
Q->front->next=p->next;
// free(p);
if(Q->rear==p)
Q->rear=Q->front;
free(p);//
}
int QueueEmpty(LinkQueue *Q)
{
QueuePtr tfront = Q->front;
if(Q->front==Q->rear)
return(1);
else
{
while (tfront != Q->rear)
{
if (tfront != NULL)
return 0;
}
return 1;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
BiTree CreatBiTree()//先序建立二叉链表
{
TElemType ch;
BiTree T;
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)
exit(0);
T->data=ch;
T->lchild=CreatBiTree();
T->rchild=CreatBiTree();
}
return T;
}
//判断是否为完全二叉树
int LayerTraverse(BiTree T)//通过层序遍历改编
{
// 对二叉树进行层次遍历,在遍历过程中对每一个结点进行检查:
// (1)如果当前结点没有右子树,则剩下的全部结点必须既没有左子树,又没有右子树;
// (2)如果当前结点有右子树,则它必须也有左子树.
bool flag = true;
bool bcomfine = false;
LinkQueue queue;
InitQueue(&queue);
if(T)
EnQueue(&queue,T);
else
{
printf("该树为空树!\n");
return true;
}
while(!QueueEmpty(&queue))
{
DeQueue(&queue,&T);
if (!T->lchild && T->rchild)
return flag=false;
if (bcomfine && (T->lchild || T->rchild))
return flag = false;
if (T->lchild != NULL)
EnQueue(&queue, T->lchild);
if (T->rchild != NULL)
EnQueue(&queue, T->rchild);
else
bcomfine = true;
}
return(flag);
}
void main()
{
BiTree t;
printf("<------------ 先序建树--------------->\n");
printf("请按先序遍历序列输入二叉树中各个结点的值(字符)，若为空树时输入空格键:\n");
printf("<参考数据:abc@@de@g@@f@@@，则用空格键表示@，输完后再输入一个回车键.>\n");
t=CreatBiTree();
printf("\n");
printf("<------ 判断是否为完全二叉树操作---->\n");
if(LayerTraverse(t))
printf("该二叉树是完全二叉树!\n");
else
printf("该二叉树不是完全二叉树!\n");
} 作业贴5：多项式的相乘例程：
程序代码：/*测试实例：
Input：
2 1 3 2 0 0
Output：
f(x)=2x+3x^2
Input:
1 1 1 0 0 0
Output:
f(x)=x+1
Output:
The Result is :
f(x)=x+5x^2+3x^3
*/
#include <iostream>
using namespace std;
struct list
{
int coef; //系数
int exp; //指数
list *next;
};
list *Creat(); //创建带头结点的链表
void Display(list *h); //输出链表
list *Merge(list *h1); //合并同类项
list *Multiply(list *h1,list *h2); //实现两个链表相乘
int main()
{
list *h1,*h2;
h1=Creat();
Display(h1);
h2=Creat();
Display(h2);
cout<<"The Result is:"<<endl;
h1=Multiply(h1,h2);
Display(h1);
return 0;
}
list *Creat()//创建带头结点的链表
{
list *h,*r,*s;//h是头结点，存放项的个数，指向第一项
r=h=new list;
h->next=NULL;
while(1)
{
s=new list;
cin>>s->coef>>s->exp;
if(s->coef==0 )
break;
if(h->next==NULL)
{
r=s;//r=h->next
h->next=r;
}
else
{
r->next=s;
r=s;
}
r->next=NULL;
}
return h;
}
void Display(list *h)//输出链表
{
list *p;
p=h->next;
cout<<"f(x)=";
while(p)
{
if(p->next!=NULL)
{
switch (p->exp)
{
case 0:
cout<<p->coef<<"+";
break;
case 1:
cout<<"X"<<"+";
break;
default:
cout<<p->coef<<"X^"<<p->exp<<"+";
}
}
else
{
switch (p->exp)
{
case 0:
cout<<p->coef;
break;
case 1:
cout<<"X";
break;
default:
cout<<p->coef<<"X^"<<p->exp;
}
}
p=p->next;
}
cout<<endl;
}
list *Merge(list *h1)//合并同类项
{
list *p1,*q1,*q2;
for(p1=h1->next;p1;p1=p1->next)
{
for(q1=p1,q2=q1->next;q2;q1=q2,q2=q2->next)
{
if(p1->exp==q2->exp)
{
p1->coef+=q2->coef;
q1->next=q2->next;
delete q2;
q2=q1;//q2=q1->next;
}
}
}
//sort
struct list *temp, *cur, *pre, *preindex, *curindex;
for(pre=h1->next, cur=h1->next->next; cur !=NULL; pre=cur, cur=cur->next)
{
preindex=h1;
curindex=h1->next;
while (curindex != cur )
{
if (curindex->exp > cur->exp)
{
temp=cur;
cur=cur->next;
pre->next=cur;
temp->next=curindex;
preindex->next=temp;
break;
}
preindex=curindex;
curindex=curindex->next;
}
}
return h1;
}
list *Multiply(list *h1,list *h2)//实现两个链表相乘
{
// h1 * h2
list *result = new list;
result->next = NULL;
list *temp = result;
list *p1, *p2;
p1 = h1->next;
while (p1)
{
p2 = h2->next;
while (p2)
{
list *q = new list;
q->coef = p1->coef * p2->coef;
q->exp = p1->exp + p2->exp;
temp->next = q;
q->next = NULL;
temp = q;
p2 = p2->next;
}
p1 = p1->next;
}
result = Merge(result);
return result;
} [ 本帖最后由 hzh512 于 2010-5-10 11:15 编辑 ]
怎么只到作业贴5啊...
好