//////////////////////////////////////////////////////////////////////////////
//
// 41. (合并链表) 已知两个链表 AN={a1,a2,...an}, BN={b1,b2,...bm}, 将其合并
// 为一个链表 CN={a1,b1,a2,b2,...}
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "malloc.h"
struct node
{
    int data;
    node* next;
};

node* create(char ch)
{
    node *p, *q, *head;
    int i,n;
    printf("\ninput the size of link %c:", ch);
    scanf("%d", &n);
    if(!n)
        return NULL;
    printf("\ninput the data's value of each element of link:\n");
    p = head = (node *)malloc(sizeof(node));
    for(i = 0;i < n; i++)
    {
        scanf("%d", &p->data);    
        p->next = (node *)malloc(sizeof(node));
        q = p;
        p = p->next;
    }
    q->next = NULL;
    return head;
}

void print(node *head)
{
    if(!head)
        return;
    node *s = head;
    while(s)
    {
        printf("%5d", s->data);
        s = s->next;
    }
    printf("\n");
}

node* combine(node *la, node *lb)
{
    if(!la)
        return lb;
    if(!lb)
        return la;
    node *p = la, *q = lb;
    node *tp, *tq, *temp;
    while(p && q)
    {
        tp      = p->next;
        tq      = q->next;
        p->next = q;
        q->next = tp;
        temp    = q;
        p       = tp;
        q       = tq;
    }
    temp->next = (q)? q :p;
    return la;
}

void main()
{
    node *la, *lb;
    la = create('A');
    printf("\nlink A is:");
    print(la);
    lb = create('B');
    printf("\nlink B is:");
    print(lb);
    printf("\nafter combined, the link  is:");
    print(combine(la, lb));
}

///////////////////////////////////////////////////////////////////////////
//
// 42. (算术表达式求值) 输入一个由数字、+，-，*，/ 及括号组成的算术表达式，
// 求其值。
///////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "ctype.h"
#include "conio.h"
#include "string.h"
#include "stdlib.h"
#define MAX_LEN  40

struct
{
    char *base;
    char *top;
}optr;
struct
{
    double *base;
    double *top;
}opnd;
int compare(char a,char b)
{
    if((a == '+') || (a == '-'))
    {
        if((b == '+') || (b == '-') || (b == ')') || (b == '='))
            return 1;
        else 
            return -1;
    }
    else if((a == '*') || (a == '/'))
    {
        if(b == '(')
            return -1;
        else 
            return 1;
    }
    else if(a == '(')
    {
        if(b == ')')
            return 0;
        else 
            return -1;
    }
    else if(a == ')')
        return 1;
    else 
        return (b == '=')?0:-1;
}
int isoperator(char ch)
{
    return ((ch == '=') || (ch == '(') || (ch == ')') || (ch == '+') || (ch == '-') || (ch == '*') || (ch == '/'))?1:0;
}

double operate(double a,char b,double c)///calculate the expression
{
    switch (b)
    {
    case '+':
        return c+a;
    case '-':
        return c-a;
    case '*':
        return c*a;
    default:
        return c/a;
    }
}
void main()
{
    char c;
    char temp[10]={'0'};
    int i;
    double a,b;
    
    opnd.top = opnd.base = (double*) malloc(MAX_LEN*sizeof(double));
    optr.base = (char*) malloc(MAX_LEN*sizeof(char));
    *optr.base = '=';
    optr.top = optr.base+1;
    
    c = _getch();    
    while(optr.base != optr.top)
    {
        if(isdigit(c) || c=='.')
        {
            memset(temp, 0, sizeof(temp));
            for(i = 0; isdigit(c) || c=='.'; i++)
            {
                putchar(c);
                temp[i] = c;
                c = _getch();
            }
            *(opnd.top++) = atof(temp);
        }
        else if(isoperator(c))
        {
            switch(compare(*(optr.top-1),c))
//ensure the right order, you can't changed to be "switch(c,compare(*(optr.top-1))) 
//while changing "case -1:" to "case 1:"
            {
            case -1:
                putchar(c);
                *optr.top++ = c;
                c = _getch();
                break;
            case 0:
                putchar(c);
                optr.top--;
                c = _getch();
                break;
            default:
                a = *--opnd.top;
                b = *--opnd.top;
                *opnd.top++ = operate(a, *--optr.top, b);
            }
        }
        else
             c = getch();
    }

    printf("%.4f\n", *(--opnd.top));
}

////////////////////////////////////////////////////////////////////////////////
//
// 43. 44. 实现两个整系数一元多项式的加法与乘法。例如, 对于多项式
//     5*X^6＋4*X^3－7*X^4＋1 与多项式 50*X^2＋4*X, 运算结果为：
//                   5*X^6－7*X^4＋4*X^3＋50*X^2＋4*X＋1。
//                   250*x^8+20*x^7-350*x^6+172*x^5+16*x^4+50*x^2+4*x
//
//     程序要求：键盘输入多项式的各项系数及指数，每项系数及指数为一组数据（系
//     数及指数之一可为零），以'0 0'结束一个多项式的输入，结果按降幂排列，同类
//     项要合并（指数最大不超过３０）。
//     上例第一式的输入为：    5 6
//                             4 3
//                            -7 4
//                             1 0
//                             0 0
//     输出结果应为：5*x^6-7*x^4+4*x^3+50*x^2+4*x+1.
//                   250*x^8+20*x^7-350*x^6+172*x^5+16*x^4+50*x^2+4*x.
////////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "malloc.h"
#include "memory.h"
#include "process.h"
typedef struct
{
    int coe;
    int exp;
}elem;

typedef struct node
{
    elem data;
    node *next;
}node;

typedef struct link
{
    node *head, *tail;
    int length;
}link;

bool initial(link &l)
{
    if(!(l.head = (node *)malloc(sizeof(node))))
        return false;
    l.tail = l.head;
    l.length = 0;
    return true;
}

void makenode(link &l, int coe, int exp)
{
    l.tail->next = (node *)malloc(sizeof(node));
    l.tail = l.tail->next;
    l.tail->data.coe  = coe;
    l.tail->data.exp  = exp;
    l.tail->next = NULL;
    ++l.length;
}

void print(link l)
{
    node *p = l.head->next;
    char *s;
    if(!p)
        return;    
    while(p)
    {
        s = (p == l.head->next)? ""
            :((p->data.coe > 0)?" +":" ");
        if(p->data.coe == 1)
        {
            if(p->data.exp == 1)
                printf("%sx", s);
            else if(p->data.exp == 0)
                printf("%s%d", s, p->data.coe);
            else
                printf("%sx^%d", s, p->data.exp);            
        }
        else
        {
            if(p->data.exp == 1)
                printf("%s%d*x", s, p->data.coe);
            else if(p->data.exp == 0)
                printf("%s%d", s, p->data.coe);
            else
                printf("%s%d*x^%d", s, p->data.coe, p->data.exp);
        }

        p = p->next;
    }
    printf("\t length = %d\n", l.length);
}

void create(link &l, char *s)
{
    int coe, exp;
    printf("\ninput the coefficient and exponential of the %s polynomial:\n", s);
    scanf("%d %d", &coe, &exp);
    while(coe)
    {
        makenode(l, coe, exp);
        scanf("%d %d", &coe, &exp);
    }
    printf("the %s polynomial is :\n", s);
    print(l);
}

void sort(elem *a, int size)
{
    elem *p, *q, temp;
    for(p = a; p< a +size -1; p++)
        for(q = p; q < a +size; q++)
            if(q->exp > p->exp)
            {
                temp = *q;
                *q   = *p;
                *p   = temp;
            }
}

void combine(elem *a, int size)
{
    int i, j;
    for(i = 0; i < size; i = j)
    {
        for(j = i+1; a[j].exp == a[i].exp && j < size; j++)
        {
            a[i].coe += a[j].coe;
            a[j].coe =  0;
        }
    }
}

void clearlink(link &l)
{
    node *p = l.head->next, *temp;
    while(p)
    {
        temp = p->next;
        free(p);
        p    = temp;
    }
    l.length = 0;
    l.head->next = NULL;
    l.tail = l.head;
}

void tidy(link &l)
{
    int size = l.length, i;
    elem *a  = new elem[size];
    memset(a, 0, size*sizeof(elem));

    node *p = l.head->next;
    for(i = 0; p; i++, p = p->next)
    {
        a[i].coe = p->data.coe;
        a[i].exp = p->data.exp;
    }

    sort(a, size);
    combine(a, size);
    clearlink(l);

    for(i = 0; i < size; i++)
    {
        if(a[i].coe == 0)
            continue;
        makenode(l, a[i].coe, a[i].exp);
    }
}

void multiply(link la, link lb)
{
    node *p, *q;
    link lc;
    if(!initial(lc))
    {
        printf("Initial false...\n");
        exit(-1);
    }

    for(p = la.head->next; p; p = p->next)
    {
        for(q = lb.head->next; q; q = q->next)
            makenode(lc, p->data.coe *q->data.coe, p->data.exp +q->data.exp);
    }
    printf("\nthe multi-polynomial is :\n");
    tidy(lc);
    print(lc);
    clearlink(lc);
}

//////////////////////////////////////////////////////////////////////////////
//
// 47. 某些密码由 N 个英文字母组成(N〈26), 每个字母的平均使用率为:W1,W2,...
//     ,Wn, 要求编程完成下列任务：
//
//      ① 依次键入Ｎ个英文字母英文字母及出现次数；
//      ② 用二进制数对该Ｎ个英文字母进行编码（最短，无二义性）；
//      ③ 键入字母短文（单词用空格区分），输出相应编码；
//      ④ 键入二进制编码短文，输出译文。
//////////////////////////////////////////////////////////////////////////////


#include "stdio.h"
#include "string.h"
#include "malloc.h"
#pragma warning(disable:4305)
#define MAX_LEN  100

typedef struct
{
    char letter;
    float weight;
    char *code;
}HuffNode;

typedef struct
{
    float weight;
    int   parent, lchild, rchild;
}HuffTNode;

void CreateHuffNode(HuffNode*, int);
void HuffCoding(HuffNode*, const int);
void SelectMin2(HuffTNode*, int&, int&, const int);
void Inorder(HuffTNode*, int);
void EtoH(char*, HuffNode*);
void HtoE(char*, HuffNode*, const int);

void main()
{
    int n;
    printf("input the count of letter-kinds:");
    scanf("%d", &n);
    HuffNode* huff = new HuffNode[n];
    CreateHuffNode(huff, n);
    char str[MAX_LEN];
    printf("Get the English String:\n");
    fflush(stdin);
    gets(str);
    EtoH(str, huff);
    printf("Get the Huffman String:\n");
    fflush(stdin);
    gets(str);
    HtoE(str, huff, n);
}

void CreateHuffNode(HuffNode *huff, int n)
{
    int i;
    float sum = 0;
    printf("input the letter and used-tiimes in turn:\n\n");
    for(i = 0; i < n; i++)
    {
        fflush(stdin);
        printf("input the letter:");
        scanf("%c", &huff[i].letter);
        printf("input the used-times of letter '%c':", huff[i].letter);
        scanf("%f", &huff[i].weight);
        sum += huff[i].weight;
    }
    for(i = 0; i < n; i++)
        huff[i].weight /= sum;
    HuffCoding(huff, n);
}

void HuffCoding(HuffNode *huff, const int n)
{
    int i, s1 = 0, s2 = 0, m = 2*n-1;
    HuffTNode *hufft = new HuffTNode[m];
    for(i = 0; i < n; i++)
    {
        hufft[i].weight = huff[i].weight;
        hufft[i].parent = 0;
        hufft[i].lchild = 0;
        hufft[i].rchild = 0;
    }
    for(; i < m; i++)
    {
        hufft[i].weight = 0;
        hufft[i].parent = 0;
        hufft[i].lchild = 0;
        hufft[i].rchild = 0;
    }
    for(i = n; i < m; i++)
    {
        SelectMin2(hufft, s1, s2, i);
        hufft[i].lchild  = s1;
        hufft[i].rchild  = s2;
        hufft[i].weight  = hufft[s1].weight + hufft[s2].weight;
        hufft[s1].parent = hufft[s2].parent = i;
    }

    printf("\n***************Huffman Code*************\n");
    printf("\nLetter\tFrequency\tHuffman Code\n");
    char *cd = new char[n];
    int start, cur;
    memset(cd, 0, n*sizeof(char));
    for(i = 0; i < n; i++)
    {
        start = n-1;
        cur = i;
        while(hufft[cur].parent)
        {
            cd[--start] = (hufft[hufft[cur].parent].lchild == cur)?'0':'1';
            cur = hufft[cur].parent;
        }
        huff[i].code = new char[n - start];
        strcpy(huff[i].code, cd+start);
        printf("%c\t%.5f\t\t%s\n", huff[i].letter, huff[i].weight, huff[i].code);
    }
    delete[] cd;
    delete[] hufft;
}

void SelectMin2(HuffTNode hufft[], int &s1, int &s2, const int n)
{
    float min = 1.0;
    int i;
    for(i = 0; i < n; i++)
    {
        if(!(hufft[i].parent) && hufft[i].weight < min)
        {
            min = hufft[i].weight;
            s1  = i;
        }
    }
    for(i = 0, min = 1.0; i < n; i++)
    {
        if(!(hufft[i].parent) && (i != s1) && hufft[i].weight < min)
        {
            min = hufft[i].weight;
            s2  = i;
        }
    }
}

void Inorder(HuffTNode hufft[], int n)
{
    if(n)
    {
        Inorder(hufft, hufft[n].lchild);
        printf("%-5.2f", hufft[n].weight);
        Inorder(hufft, hufft[n].rchild);
    }
}

void EtoH(char str[], HuffNode huff[])
{
    int i, j;
    printf("The homologous Huffman-String is:\n");
    for(i = 0; str[i]; i++)
    {
        for(j = 0; huff[j].letter != str[i]; j++);
        printf("%s", huff[j].code);
    }
    putchar(10);
}

void HtoE(char str[], HuffNode huff[], const int n)
{
    int i, j, k;
    char *temp = new char[n];
    memset(temp, 0, n*sizeof(char));
    printf("The homologous Enlish-String is:\n");
    for(i = 0, j = 0; str[i]; i++)
    {    
        temp[j] = str[i];
        j++;
        for(k = 0; k < n; k++)
        {
            if( (strlen(temp)==strlen(huff[k].code))
                && !strcmp(temp, huff[k].code) )
            {
                putchar(huff[k].letter);
                memset(temp, 0, n*sizeof(char));
                j = 0;
            }
        }
    }
    putchar(10);
}

//////////////////////////////////////////////////////////////////////////////
//
// 48. 将４个红球，３个白球与３个黄球排成一排，共有多少种排法？
//////////////////////////////////////////////////////////////////////////////

#include "stdio.h"

char* color[3] = {"RED", "WHITE", "YELLOW"};
int colorcount[3] = {4, 3, 3};
static int count;

void trial(int n, int array[], int status[])
{
    if(n == 10)
    {
        printf("\n%d\n", ++count);
        for(n = 0; n < 10; n++)
            printf("%s\t", color[array[n]]);
    }
    else
    {
        for(int i = 0; i < 3; i++)
        {
            array[n] = i;
            ++status[i];
            if(status[i] <= colorcount[i])
                trial(n+1, array, status);
            --status[i];
        }
    }
}

void main()
{
    int array[10], status[3] = {0};
    trial(0, array, status);
}

//////////////////////////////////////////////////////////////////////////////
//
//  49. 有面值为 M..N 的邮票各一枚，共能拼出多少不同的面额。
//////////////////////////////////////////////////////////////////////////////

#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define  N   4
int i = 0;
bool find(int count[], int e)
{
    for(int i = 0; count[i]; i++)
        if(count[i] == e)
            return true;
    return false;
}

void trial(int ai, int array[], int count[], int sum)
{
    if(ai == N)
    {
        if(!find(count, sum))
            count[i++] = sum;
        return;
    }
    else
    {
        sum += array[ai];
        trial(ai+1, array, count, sum);
        sum -= array[ai];
        trial(ai+1, array, count, sum);
    }
}

void main()
{
    int array[N], count[100] = {0}, i;
    srand((unsigned)time(NULL));
    for(i = 0; i < N; i++)
    {
        array[i] = rand()%30;
        printf("%5d", array[i]);
    }
    printf("\n");
    trial(0, array, count, 0);
    for(i = 0; count[i]; i++)
        printf("%5d", count[i]);
}

/////////////////////////////////////////////////////////////////////////////////
//
//  51. 微型蓝球赛. 甲,乙两队进行蓝球比赛,结果甲队以S:T 获胜.(T<S<=10, S,T由
//      键盘输入). 比赛中, 甲队得分始终领先(严格大于乙队). 规定以任何方式进一
//      球都只得一分. 编程序打印该比赛的每一种可能的不同的得分过程, 以及所有不同
//      过程的总数.
/////////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "assert.h"

int s = 6, t = 4, ord = 0;

struct rate
{
    int s;
    int t;
}array[50];

void trial(rate rate[], int i)
{
    if(rate[i].s == s && rate[i].t == t)
    {
        for(int j = 0; j <=i; j++)
            printf("%d:%d\t", rate[j].s, rate[j].t);
        printf("ORDER = %d\n\n", ++ord);
    }
    else
    {
        rate[i+1].s = rate[i].s + 1;
        rate[i+1].t = rate[i].t;
        if(rate[i+1].s <= s && rate[i+1].s > rate[i+1].t)
            trial(rate, i+1);
        rate[i+1].t = rate[i].t + 1;
        rate[i+1].s = rate[i].s;
        if(rate[i+1].t <= t && rate[i+1].s > rate[i+1].t)
            trial(rate, i+1);
    }
}

void main()
{
    array[0].s = array[0].t = 0;
    trial(array, 0);
}

//////////////////////////////////////////////////////////////////////////////
//
// 65. ( NOI'94.1_1 ) 键盘输入一个仅由小写字母组成的字符串，输出以该串中任
//     取Ｍ个字母的所有排列及排列总数。
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "time.h"
#define MAX_LEN 50
#define M       7 //if m > 10, the execution of this program will take you a long wait time

char s[MAX_LEN] = "", sub[M+1] = "", array[M+1] = "";
int used[M] = {0}, order = 0;
void trace(char* sub, char *array, int j, FILE* fp)
{
    if(j == M)
        fprintf(fp, "%s\t ORDER = %d\n", array, ++order);
    else
        for(int i = 0; i < M; i++)
            if(!used[i])
            {
                used[i] = 1;
                array[j] = sub[i];
                trace(sub, array, j+1, fp);
                used[i] = 0;
            }
}

void main()
{
    int i, len;
    FILE* fp = fopen("result.txt", "w");
    gets(s);
    len = strlen(s);
    srand(unsigned(time(NULL)));
    for(i = 0; i < M; i++)
        sub[i] = s[rand()%len];
    printf("%s\n", sub);
    trace(sub, array, 0, fp);
}