#include<stdlib.h>
#define Maxsize 5
//////////////////////////// joseph環的函數 /////////////////////////////////////////////////////////
typedef struct data//定義壹個結構體“data”
{
int num; //用於存放人的序號
int val; //用於存放密碼
}typedata;
typedef struct node//定義壹個結構體（結點），其中包含壹個數據域和壹個指針域
{
struct data da; //結構體的嵌套
struct node *next;
}linknode;
linknode *head;
void huan()
{
head=(linknode*)malloc(sizeof(linknode));//申請壹個空間（頭結點 head）
int n,i,b,m,j;
linknode *p,*q,*temp;//定義兩個可以指向結點的指針
printf("輸入總人數：");
scanf("%d",&n);
p=head;
for(j=1;j<=n;j++)//本次循環主要是將每壹個人的數據（包括序號、密碼）存入循環鏈表中
{
q=(linknode*)malloc(sizeof(linknode));
p->next=q;
q->da.num=j;
printf("請輸入%d的密碼：",j);
scanf("%d",&m);
q->da.val=m;
p=p->next;
}
p->next=head->next;
p=p->next;
printf("請任意輸入壹個數m：");
scanf("%d",&m);
if(m<=0)
printf("輸入錯誤");
printf("出列順序是：");
while(p->next!=p)
{
for(i=1;i<m;i++)
{
q=p;
p=p->next;
}
b=p->da.num;
m=p->da.val;
printf("num:%-2dval:%-2d",p->da.num,p->da.val);
q->next=p->next;
temp=p;
p=p->next;
free(temp);
}
printf("num:%d\tval:%d\n",q->da.num,q->da.val); //輸出最後壹個結點
free(q); //釋放最後壹個結點
free(head); //釋放頭結點
printf("約瑟夫環結束，歡迎下次光臨~·~\n");
}
/////////////////////////////////////////// 哈夫曼樹的建立 ////////////////////////////////////////////////////////////////////
typedef struct
{
char data;
int weight;
int parent;
int lchild;
int rchild;
}HTNode;//哈夫曼樹結點的定義
HTNode ht[2*Maxsize-1];
void createHF(HTNode ht[],int n)
{
int i,k,lnode,rnode;
int min1,min2;
for(i=0;i<2*n-1;i++) //所有結點的parent lchild rchild 域賦值為-1
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for(i=n;i<2*n-1;i++)
{
min1=min2=32767;
lnode=rnode=-1;
for(k=0;k<=i-1;k++)//隨著i的變化，非葉子節點也進入搜索範圍
if(ht[k].parent==-1)//在尚未構造二叉樹的結點中查找
if(ht[k].weight<min1)
{
min2=min1; rnode=lnode;
min1=ht[k].weight; lnode=k;
}
else if(ht[k].weight<min2)
{
min2=ht[k].weight; rnode=k;
}
ht[lnode].parent=i; ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode; ht[i].rchild=rnode;
}
}
/*哈夫曼樹輸出函數此函數的輸出是根據構造的具體結構而做的，采用括號表示法輸出*/
void putHF(HTNode ht[],int n)
{
int flag=0,i=2*n-2;
printf("哈夫曼樹:\n");
printf("%2d",ht[i].weight);
for(;i>=0;i--)
if(ht[i].lchild!=-1)
{
printf("(%2d,%2d",ht[ht[i].lchild].weight,ht[ht[i].rchild].weight);
flag++;
}
else break;
for(i=flag;i>0;i--)
printf(")");
}
void main()
{
int n;
printf(" -*-*-*-*-*-*-*-*--進入哈夫曼樹創建模塊--*-*-*-*-*-*-*-*-*-*\n\n");
printf("Please input the number of nodes:\n");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("please input node %d weight:\n",i+1);
scanf("%d",&ht[i].weight);
}
createHF(ht,n);
putHF(ht,n);
printf("\n");
}
註冊個號這麽費勁~！！！