编程论坛的作业贴解决合集 (II)

#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;
}
}

/*测试用例：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;
}

#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 ;
}

#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;
}