编程论坛的作业贴解决合集 (II)
作业贴6：Huffman 编码
例程：
程序代码：#include <iostream>
#include <string.h>
#define MAXSIZE 15
using namespace std;
typedef struct
{
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree &HT, int n, int &s1, int &s2);
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n);
int main()
{
HuffmanTree HT;
HuffmanCode HC; //typedef char **HuffmanCode
int w[MAXSIZE]={5,29,7,8,14,23,3,11}, n=8;
/* cout << "请输入字符数目\n";
cin >> n;
cout << "请输入各字符的权值\n";
for (int i = 0; i < n; i++)
cin >> w[i];
*/
HuffmanCoding(HT, HC, w, n);
return 0;
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
//建立哈夫曼树，求哈夫曼编码
HuffmanTree p;
char *cd;
int i, s1, s2, start;
unsigned int c, f;
if (n <= 1)
return;
int m = 2 * n - 1;
HT = (HuffmanTree) malloc((m + 1) * sizeof(HTNode));
p=HT;
for (++p, i = 1; i <= n; ++i, ++p, ++w)
{
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for (; i <= m; ++i, ++p)
{
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for (i = n + 1; i <= m; ++i)
{
Select(HT, i-1, s1, s2);
HT[s1].parent = i;
HT[s2].parent = i;
if(s1<s2)
{
HT[i].lchild = s1;
HT[i].rchild = s2;
}
else
{
HT[i].lchild = s2;
HT[i].rchild = s1;
}
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
cd = (char *) malloc(n * sizeof(char));
cd[n-1] = '\0';
for (i = 1; i <= n; ++i)
{
start = n - 1;
for (c = i, f = HT[c].parent; f != 0; c = f, f = HT[f].parent)
if (HT[f].lchild == c)
cd[--start] = '0';
else
cd[--start] = '1';
HC[i] = (char *) malloc((n - start) * sizeof(char));
strcpy(HC[i], &cd[start]);
printf("%s\n", HC[i]);
}
free(cd);
}
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
{
//选择HT[1..n]中 parent为0且weight最小的两个结点
//序号分别赋值给 s1，s2
for (int i = 1; i <= n; i++)
{
if (HT[i].parent == 0)
{
s1 = i;
break;
}
}
for (; i <= n; i++)
{
if (HT[i].weight < HT[s1].weight && HT[i].parent == 0)
s1 = i;
}
for (i=1; i <= n; i++)
{
if (HT[i].parent == 0 && i != s1)
{
s2 = i;
break;
}
}
for (; i <= n; i++)
{
if (HT[i].weight < HT[s2].weight && HT[i].parent == 0 && i != s1)
s2 = i;
}
}作业贴7：二叉树的操作，创建、各种遍历
例程：
程序代码：/*测试用例：A B C # # D E # G # # F # # #*/
#include <iostream>
#include<string>
using namespace std;
template <class T>
struct BiNode
{
T data;
BiNode<T> *lchild, *rchild;
};
template <class T>
class BiTree
{
public:
BiTree(){ } // 构造函数 重载后，就取消默认构造函数
BiTree(BiNode<T>*root);
~BiTree();
BiNode<T>* Getroot();
void PreOrder(BiNode<T>*root);
void NpreOrder(BiNode<T>*root);
void InOrder(BiNode<T>*root);
void PostOrder(BiNode<T>*root);
void LevelOrder(BiNode<T>*root);
private:
BiNode<T> *root;
BiNode<T>* Creat(BiNode<T>*root);
void Release(BiNode<T>*root);
};
template<class T> //构造树
BiTree<T>::BiTree(BiNode<T>*root)
{
cout<<"请输入创建一棵二叉树的结点数据"<<endl;
this->root=Creat(root);
}
template <class T>
BiNode<T>* BiTree<T>::Creat(BiNode<T>*root)
{
T ch;
cin>>ch;
if(ch=="#")
root=NULL;
else{
root=new BiNode<T>;
root->data=ch;
root->lchild=Creat(root->lchild);
root->rchild=Creat(root->rchild);
}
return root;
}
template<class T>
void BiTree<T>::Release(BiNode<T>*root)
{
if(root!=NULL){
Release(root->lchild);
Release(root->rchild);
delete root;
}
}
template <class T> //析构树
BiTree<T>::~BiTree()
{
Release(root);
}
template<class T> //得到树顶
BiNode<T>* BiTree<T>::Getroot( )
{
return root;
}
//树的遍历算法
template <class T> //前序递归算法
void BiTree<T>::PreOrder(BiNode<T>*root)
{
if(root==NULL) return;
else{
cout<<root->data;
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}
/*
template <class T> //前序非递归算法 程序有语法错误，自己改正吧
void BiTree<T>::NpreOrder(BiNode<T>*root)
{
top=-1;
while(root!=NULL||top!=-1)
{
while(root!=NULL)
{
cout<<root->data;
s[++top]=root;
root=root->lchild;
}
if(top!=-1){
root=s[top--];
root=root->rchild;
}
}
}
*/
template<class T> //中序递归算法
void BiTree<T>::InOrder(BiNode<T>*root)
{
if(root==NULL) return;
else{
InOrder(root->lchild);
cout<<root->data;
InOrder(root->rchild);
}
}
template <class T> //后序递归算法
void BiTree<T>::PostOrder(BiNode<T>*root)
{
if(root==NULL) return;
else{
PostOrder(root->lchild);
PostOrder(root->rchild);
cout<<root->data;
}
}
template<class T> //层序遍历算法
void BiTree<T>::LevelOrder(BiNode<T>*root)
{
const int MaxSize = 100;
int front;
int rear;
BiNode<T> *q;
BiNode<T> *Q[MaxSize];
front=rear=0;
if(root==NULL) return;
Q[++rear]=root;
while(front!=rear)
{
q=Q[++front];
cout<<q->data;
if(q->lchild!=NULL) Q[++rear]=q->lchild;
if(q->rchild!=NULL) Q[++rear]=q->rchild;
}
}
int main()
{
BiTree<string> tree(NULL);
BiNode<string>* root = tree.Getroot( );
cout<<"------前序遍历------ "<<endl;
tree.PreOrder(root);
cout<<endl;
cout<<"------前序非递归遍历------ "<<endl;
// tree.NpreOrder(root);
cout<<"------中序遍历------ "<<endl;
tree.InOrder(root);
cout<<endl;
cout<<"------后序遍历------ "<<endl;
tree.PostOrder(root);
cout<<endl;
cout<<"------层序遍历------ "<<endl;
tree.LevelOrder(root);
cout<<endl;
return 0;
}作业贴8：［问题描述］设有n个人围坐一圈，现从某个人开始报数，数到m的人出列，接着从下一个人开始重新开始报数， 数到m的人又出列，如次下去，直到所有的人都出列为止。试设计确定他们出列的顺序的程序
1）在顺序存储结构上实现以上过程。
2）在循环链表上实现以上过程。
例程：
程序代码：#include <stdio.h>
int main(void)
{
int n, m, i, s=0;
printf ("N M = "); scanf("%d%d", &n, &m);
for (i=2; i<=n; i++) s=(s+m)%i;
printf ("The winner is %d\n", s+1);
}
//方法二 循环链表
#include <stdio.h>
#include <stdlib.h>
typedef struct list
{
int num ;
struct list *next ;
}LIST ;
int main(void)
{
LIST *head=NULL,*pre=NULL,*post=NULL, *start=NULL, *temp=NULL;
long i, m, n, x;
printf("n=");
scanf("%ld",&n);
printf("\nm=");
scanf("%ld",&m) ;
printf("\n");
if( n <= 1)
{
printf("1 ");
return 0;
}
/**//*建立循环链表*/
pre = (LIST *)malloc(sizeof(LIST));
pre->num = 1 ;
pre->next = NULL ;
head = pre ;
post = pre ;
for(i=2 ; i<= n; i++)
{
pre = (LIST *)malloc(sizeof(LIST));
pre->num = i;
pre->next= NULL ;
post->next=pre ;
post = pre ;
}
post -> next = head ; /**//*将最后一个结点的指向头，这样就构成了循不链表*/
pre= head ;
i--;
while(i>0)
{
printf(" %d ",pre->num);
pre=pre->next;
i--;
}
printf("\n");
printf("\n从第几个人开始：");
scanf("%d",&x);
int count=n;
while(count>0)
{
if(head->num==x)
{
pre=post;
start=head;
break;
}
if(pre->next->num==x)
{
start=pre->next;
break;
}
pre=pre->next;
count--;
}
if(count==0)
{
printf("\n 开始人错误\n");
system("pause");
exit(1);
}
while (start->next != start)
{
for(i=1; i < m ; i++)
{
pre = start ;
start = start->next;
}
temp=start;
start=start->next;
pre->next=start;
delete temp;
}
printf("last=%d \n",pre->num);
return 0 ;
}作业贴9：链表的插入排序
例程：
程序代码：#include <iostream>
using namespace std;
struct list
{
int coef; //ϵÊý
int exp; //Ö¸Êý
list *next;
};
int main()
{
struct list *head=new struct list;
head->coef = 0;
head->exp=0;
head->next=NULL;
struct list *p=new struct list;
p->coef=5;
p->exp=2;
p->next=NULL;
head->next=p;
p=new struct list;
p->coef=2;
p->exp=1;
p->next=NULL;
head->next->next=p;
p=new struct list;
p->coef=3;
p->exp=3;
p->next=NULL;
head->next->next->next=p;
struct list *temp, *cur, *pre, *preindex, *curindex;
for(pre=head->next, cur=head->next->next; cur !=NULL; pre=cur, cur=cur->next)
{
preindex=head;
curindex=head->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 0;
}[ 本帖最后由 hzh512 于 2010-5-25 13:37 编辑 ]
