2011級(jí)計(jì)算機(jī)學(xué)院課程設(shè)計(jì)題目及參考程序

1、精選優(yōu)質(zhì)文檔-傾情為你奉上問(wèn)題 A: 整數(shù)排序一時(shí)間限制: 20 Sec  內(nèi)存限制: 128 MB題目描述經(jīng)過(guò)三天的任務(wù)的訓(xùn)練，大家的確辛苦了因此，在任務(wù)開(kāi)始時(shí)，我為大家準(zhǔn)備了一道令人非常愉快的熱身題即將一個(gè)雜亂無(wú)序的整數(shù)序列，按照從小到大的順序排列并輸出輸入測(cè)試數(shù)據(jù)不止一組，每組測(cè)試數(shù)據(jù)：）先輸入無(wú)序序列的整數(shù)個(gè)數(shù)n；(n不超過(guò))）然后連續(xù)輸入n個(gè)整數(shù)；若n的值輸入為值，則輸入結(jié)束輸出與每組輸入的測(cè)試數(shù)據(jù)相對(duì)應(yīng)，輸出其按從小到大排好序后的整數(shù)序列注意：每組輸出占一行樣例輸入109 8 7 6 5 4 3 2 1 -1588 77 66 55 330樣

2、例輸出-1 1 2 3 4 5 6 7 8 933 55 66 77 88提示本題測(cè)試對(duì)第10章“內(nèi)部排序”的理解程度。可采用冒泡排序、插入排序、選擇排序、快速排序、希爾排序、堆排序等方法完成此題。警告：目的是讓大家熟悉內(nèi)部排序的各種算法，因此禁止調(diào)用sort或qsort等函數(shù)！不改正者降最終成績(jī)等級(jí)簡(jiǎn)單排序版：#include<stdio.h>#include<stdlib.h>#define SIZE 10000void fastsort(int a,int n)int i,j,k,temp;for(i=0;i<n-1;i+) k=i;for(j=i+1;j&

3、lt;n;j+)if(aj<ak)k=j;if(i!=k)temp=ai;ai=ak;ak=temp;int main()int sortSIZE;int num,i;while(1)scanf("%d",&num);if(num=0) exit(0);for(i=0;i<num;i+)scanf("%d",&sorti);fastsort(sort,num);for(i=0;i<num;i+)if(i=num-1)printf("%d",sorti);elseprintf("%d &quo

4、t;,sorti);printf("n");return 0;快速排序版：#include<stdio.h>#define SIZE void quick_sort(int a, int low, int high) int i, j, t; if (low < high) i = low; j = high; t = alow; while (i<j) while ( i<j && aj>t) j-; if (i<j) ai = aj; i+; while (i<j && ai<=t)

5、i+; if (i<j)aj = ai; j-; ai = t; quick_sort(a,low,i-1); quick_sort(a,i+1,high); int main()int sortSIZE;int num,i;while(1)scanf("%d",&num);if(num=0) return 0;for(i=0;i<num;i+)scanf("%d",&sorti);quick_sort(sort,0,num-1);for(i=0;i<num;i+)if(i=num-1)printf("%d&q

6、uot;,sorti);elseprintf("%d ",sorti);printf("n");return 0;堆排序版：#define MAX 10000#include<stdio.h>void sift(int *x, int n, int s) int t, k, j; t = *(x+s); k = s; j = 2*k + 1; while (j<n) if (j<n-1 && *(x+j) < *(x+j+1) j+; if (t<*(x+j) *(x+k) = *(x+j); k =

7、j; j = 2*k + 1; else break; *(x+k) = t; void heap_sort(int *x, int n) int i, k, t; int *p; for (i=n/2-1; i>=0; i-) sift(x,n,i); for (k=n-1; k>=1; k-) t = *(x+0); *(x+0) = *(x+k); *(x+k) = t; sift(x,k,0); int main() int *p, i, aMAX,num; while(1) p = a;scanf("%d",&num);if(num=0) re

8、turn 0; for (i=0; i<num; i+) scanf("%d",p+); p = a; heap_sort(p,num); for(i=0;i<num;i+) if(i=num-1) printf("%d",ai); else printf("%d ",ai); printf("n"); return 0;問(wèn)題 B: 整數(shù)排序二時(shí)間限制: 20 Sec  內(nèi)存限制: 128 MB題目描述在完成了任務(wù)的第一個(gè)熱身題后，很多同學(xué)覺(jué)得不過(guò)癮，那就用同樣的

9、題目讓大家再交一次原來(lái)已經(jīng)的程序，看是什么樣的結(jié)果，應(yīng)該怎樣應(yīng)對(duì)？題目跟第一個(gè)熱身題是一樣的（但我已經(jīng)大幅增加了測(cè)試數(shù)據(jù)），還是要求將一個(gè)雜亂無(wú)序的整數(shù)序列，按照從小到大的順序排列并輸出輸入測(cè)試數(shù)據(jù)不止一組，每組測(cè)試數(shù)據(jù)：）先輸入無(wú)序序列的整數(shù)個(gè)數(shù)n；(n不超過(guò))）然后連續(xù)輸入n個(gè)整數(shù)；若n的值輸入為值，則輸入結(jié)束輸出與每組輸入的測(cè)試數(shù)據(jù)相對(duì)應(yīng)，輸出其按從小到大排好序后的整數(shù)序列注意：每組輸出占一行樣例輸入109 8 7 6 5 4 3 2 1 -1588 77 66 55 330樣例輸出-1 1 2 3 4 5 6 7 8 933 55 66 77 88提示本題測(cè)試對(duì)第10章“內(nèi)部排序”的理

10、解程度。但要考慮算法的優(yōu)化及排序方法的選擇(排序速度要快才行)。警告：目的是讓大家熟悉內(nèi)部排序的各種算法，因此禁止調(diào)用sort或qsort等函數(shù)！不改正者降最終成績(jī)等級(jí)#define MAX #include<stdio.h> void sift(int *x, int n, int s) int t, k, j;  t = *(x+s);  k = s;   j = 2*k + 1;   while (j<n)    if(j<n-1 &a

11、mp;& *(x+j) < *(x+j+1) j+;   if (t<*(x+j)        *(x+k) = *(x+j);    k = j;     j = 2*k + 1;      else break;    *(x+k) = t;   void heap_sor

12、t(int *x, int n) int i, k, t; int *p;  for (i=n/2-1; i>=0; i-)  sift(x,n,i);     for (k=n-1; k>=1; k-)   t = *(x+0);   *(x+0) = *(x+k);  *(x+k) = t;  sift(x,k,0);     int mai

13、n()  int *p, i, aMAX,num;   while(1)      p = a;     scanf("%d",&num);     if(num=0) return 0;     for (i=0; i<num; i+)      sca

14、nf("%d",p+);      p = a;     heap_sort(p,num);      for(i=0;i<num;i+)           if(i=num-1)      printf("%d"

15、;,ai);      else      printf("%d ",ai);         printf("n");     return 0;  問(wèn)題 C: 時(shí)間復(fù)雜度的估算時(shí)間限制: 1 Sec  內(nèi)存限制: 128 MB題目描述在

16、數(shù)據(jù)結(jié)構(gòu)里面，時(shí)間復(fù)雜度是決定算法效率的一項(xiàng)重要指標(biāo)，常見(jiàn)的時(shí)間復(fù)雜度格式有三種：1、O(n)2、O(lg(n)3、O(sqrt(n)一個(gè)算法往往有多種解法，每種解法的復(fù)雜度由上述常見(jiàn)的的復(fù)雜度組合成，例如排序的兩種算法：1、 快速排序：時(shí)間復(fù)雜度為O(n*lg(n)2、冒泡排序：時(shí)間復(fù)雜度為O(n*n)現(xiàn)在先給定n的值，然后輸入一個(gè)值m，隨后輸入m行數(shù)據(jù)表示有m個(gè)算法的復(fù)雜度。請(qǐng)確定這些復(fù)雜度是否會(huì)超時(shí)。若復(fù)雜度計(jì)算結(jié)果大于，則為超時(shí)(TLE)，否則輸出計(jì)算的復(fù)雜度，輸出的結(jié)果保留兩位小數(shù)。( lg(n)表示求以2為底數(shù)的n的對(duì)數(shù) )輸入第一行輸入n (1n), m(1m

17、100), 其中n為表示問(wèn)題規(guī)模的數(shù)，m為算法復(fù)雜度的個(gè)數(shù)。接下來(lái)m行，每行為一個(gè)串，每個(gè)串都包含O( )，其中，字符'O'后的括號(hào)里面的字符串保證僅由n,lg(n),sqrt(n),*組成并且合法。如sample input所示。注意：lg()或sqrt()中只會(huì)出現(xiàn)字符'n'，不會(huì)再嵌套lg()或sqrt()。如果想做得難一點(diǎn)，可以去做編號(hào)為1049的題，1049題要考慮嵌套。輸出對(duì)于每個(gè)串，若計(jì)算出來(lái)的復(fù)雜度大于，則輸出TLE，否則輸出該復(fù)雜度的計(jì)算結(jié)果。樣例輸入10000 5O(n*n)O(n*n*n)O(sqrt(n)O(lg(n)O(n*l

18、g(n)樣例輸出.00TLE100.0013.29.12提示本題主要測(cè)試三個(gè)方面：1）對(duì)于時(shí)間復(fù)雜度的理解。2）字符串處理及數(shù)組的合理使用。3）編碼能力。#include<stdio.h>#include<math.h>#define MAX 100 int main()    int N_NUM, L_NUM, S_NUM;    int num;    char stringMAX;    doub

19、le s;    int i,p,n;     while(scanf("%d %d",&n,&num)!=EOF)         for(s=1.0,N_NUM=0,L_NUM=0,S_NUM=0,p=0;p<num;p+)             &#

20、160; scanf("%s",string);          s=1.0;          N_NUM=0;          L_NUM=0;          

21、;S_NUM=0;            for( i=2 ; stringi!='0' i+ )                 if(stringi='n')         

22、0;            N_NUM+;            i+;                    if(stringi='l')&

23、#160;                      L_NUM+;             i=i+5;            

24、        if(stringi='s')                       S_NUM+;             i=i+7;

25、                        for(i=0;i<N_NUM;i+)           s=s*n;        for(i=0;i<L_NUM;

26、i+)           s=s*(log(n)/log(2.0);       for(i=0;i<S_NUM;i+)           s=s*sqrt(n);           &#

27、160;  if(s>)          printf("TLEn");        else          printf("%.2fn",s);        &#

28、160;問(wèn)題 D: 車站調(diào)度時(shí)間限制: 1 Sec  內(nèi)存限制: 128 MB題目描述有順序排列的1,2, 3,n節(jié)車廂在入站口等待調(diào)度。車站設(shè)置了一個(gè)棧作為緩沖，這樣的話只可能進(jìn)行下列兩個(gè)操作之一：      （1）如果還有車廂在入站口，將最前面的入棧緩沖      （2）將棧頂?shù)能噹偝鲕囌?#160;   給定一個(gè)1至n的排列，問(wèn)其作為出站序列是否合法。注意：入站順序?yàn)?,2, 3,n，即1先入棧.，n最后入棧

29、。輸入輸入包含若干測(cè)試用例。每一個(gè)測(cè)試用例由多行組成。第一行是兩個(gè)整數(shù)n（1<=n <= 100）和m，n表示入站序列為1至n。m表示隨后有m行出站序列。當(dāng)n，m均為0時(shí)表示輸入結(jié)束。輸出對(duì)應(yīng)每一個(gè)出站序列，合法則輸出一行YES，否則輸出一行NO。樣例輸入3 61 2 31 3 22 1 32 3 13 1 23 2 10 0樣例輸出YESYESYESYESNOYES提示參見(jiàn)習(xí)題集p21 題3.1。本題主要測(cè)試對(duì)棧的理解及靈活運(yùn)用。解本題推薦采用模擬入棧出棧的方式，以訓(xùn)練對(duì)棧的運(yùn)用熟練程度。當(dāng)然也有其它方法，如推導(dǎo)出規(guī)律（出棧序列中存在“大小中”的組合是不行的）后編程求解。#inc

30、lude<stdio.h>#define MAX 100#define SIZE 100 int clear(int a,int p)   int i;   for(i=0;i<p-1;i+)         if(ai<ai+1)        return 0;     retur

31、n 1; int Judge(int a,int num)   int judgeSIZE;   int p;   int i,k,j;    for(i=0;i<num-2;i+)       for(k=i+1,p=0;k<num;k+)          if(ai>

32、;ak)               judgep+=ak;               if(clear(judge,p)     continue;    else    &#

33、160;           printf("NOn");         return -1;            printf("YESn"); return 0;    int ma

34、in()    int num,time;    int aMAX;    int i,j;    while(1)        scanf("%d %d",&num,&time);    if(num=0 && time=0) return 0; 

35、60;     for(i=0;i<time;i+)                  for(j=0;j<num;j+)             scanf("%d",&aj); 

36、0;           Judge(a,num);              return 0;問(wèn)題 E: Acmers Love AC時(shí)間限制: 1 Sec  內(nèi)存限制: 128 MB題目描述We hate WA! We hate TLE! We hate RE! We hate PE.! The onl

37、y thing we love is AC!Because we are ACMers! Now we give you a task that you should find how many strings"AcmersLoveAc" are there in a string that we input.輸入  The input contains several testcases. Each testcase consists of one string(only contains capital letter and Lowercase letter)

38、 which is at most 100 characters. Input is terminated by EOF.輸出 For each testcase output, print an integer which stands for that how many strings"AcmersLoveAc" are there in the inputstring.樣例輸入IKnowAcmersLoveAcAcmersDontLoveAcAcmersLoveAcAndAcmersLoveAc樣例輸出102提示本題是今天的熱身題，主要測(cè)試對(duì)字符串的處理#i

39、nclude <stdio.h>#include<string.h>#define MAX 100#define SIZE 13 int Equals(char a)    char strSIZE="AcmersLoveAc"    return strcmp(str,a); int NumofAC(char a,int num)    int i,j,k=0,p;    

40、;char bSIZE;    for(i=0,j=0;i+SIZE-2<num;i+)            if(ai='A')                    p=i;   &

41、#160;        for(j=0;j<SIZE-1;)                          bj+=ap+;           &

42、#160;             bj='0'            if(Equals(b)=0)                  k+; 

43、;               return k; int main()    int num;    char strMAX;    while(scanf("%s",str)!=EOF)         &

44、#160;       for(num=0;strnum!='0'num+);      printf("%dn",NumofAC(str,num);        return 0; 問(wèn)題 F: 二叉樹(shù)遍歷時(shí)間限制: 1 Sec  內(nèi)存限制: 128 MB題目描述對(duì)于二叉樹(shù)T，可以有先序遍歷、中序遍歷

45、和后序遍歷三種遍歷方式。我們知道，任意給定一顆二叉樹(shù)的兩種遍歷方式，就可以唯一確定該樹(shù)。現(xiàn)在我們要求給出一棵二叉樹(shù)的先序遍歷序列和中序遍歷序列，輸出它的廣度優(yōu)先遍歷序列。 輸入第一行為一個(gè)整數(shù)t（0<t<10），表示測(cè)試用例個(gè)數(shù)。 以下t行，每行輸入一個(gè)測(cè)試用例，包含兩個(gè)字符序列s1和s2，其中s1為一棵二叉樹(shù)的先序遍歷序列，s2為中序遍歷序列。s1和s2之間用一個(gè)空格分 隔。序列只包含大寫(xiě)字母，并且每個(gè)字母最多只會(huì)出現(xiàn)一次。 輸出為每個(gè)測(cè)試用例單獨(dú)一行輸出廣度優(yōu)先遍歷序列。樣例輸入2DBACEGF ABCDEFGBCAD CBAD樣例輸出D

46、BEACGFBCAD提示本題主要測(cè)試對(duì)二叉樹(shù)遍歷的理解.#include <stdio.h>#include<malloc.h>#include<string.h>#define SIZE 150#define MAX 150 typedef struct BiTree char data; struct BiTree *lchild,*rchild;BiTree; BiTree *CreateBT(char *pre,char *in,int n)    BiTree *s;&

47、#160;   char *p;    int k;    if(n<=0) return NULL;    s=(BiTree *)malloc(sizeof(BiTree);    s->data=*pre;    for(p=in;p<in+n;p+)        

48、;    if(*p=*pre) break;        k=p-in;    s->lchild=CreateBT(pre+1,in,k);    s->rchild=CreateBT(pre+k+1,p+1,n-k-1);    return s; void BFS(BiTree *p)  BiTree *q

49、ueueMAX;  int front=-1,rear=-1;  front=(front+1)%MAX;  queuefront=p;   while(front!=rear)           rear=(rear+1)%MAX;      p=queuerear;      pri

50、ntf("%c",p->data);      if(p->lchild!=NULL)                front=(front+1)%MAX;          queuefront=p->lchild;  

51、;          if(p->rchild!=NULL)                front=(front+1)%MAX;          queuefront=p->rchild;   

52、;          printf("n"); int main()    int t,i,j;    char str1SIZE,str2SIZE;    char *p,*q;     BiTree *k;     scanf("%d"

53、,&t);     for(i=0;i<t;i+)          scanf("%s",str1);     scanf("%s",str2);     j=strlen(str1);     p=str1;   

54、;  q=str2;     k=CreateBT(p,q,j);     BFS(k);             問(wèn)題 G: Faulty Odometer（非ACMer做）時(shí)間限制: 1 Sec  內(nèi)存限制: 33 MB題目描述You are given a car odometer which displays

55、the miles traveled as an integer. The odometer has a defect, however: it proceeds from the digit 2 to the digit 4 and from the digit 7 to the digit 9, always skipping over the digit 3 and 8. This defect shows up in all positions (the one's, the ten's, the hundred's, etc.). For example, i

56、f the odometer displays 15229 and the car travels one mile, odometer reading changes to 15240 (instead of 15230).輸入Each line of input contains a positive integer in the range 1. which represents an odometer reading. (Leading zeros will not appear in the input.) The end of input is indicated by a lin

57、e containing a single 0. You may assume that no odometer reading will contain the digit 3 and 8.輸出Each line of input will produce exactly one line of output, which will contain: the odometer reading from the input, a colon, one blank space, and the actual number of miles traveled by the car. 樣例

58、輸入15200525015000樣例輸出15: 122005: 1028250: 1601500: 768: 提示數(shù)據(jù)沒(méi)有超過(guò)int類型的取值范圍，但要注意，消耗時(shí)間長(zhǎng)的算法是過(guò)不了的看我用下面程序生成的測(cè)試數(shù)據(jù)至少個(gè)我寫(xiě)的測(cè)試數(shù)據(jù)生成程序如下:#include <stdio.h>#include <time.h>#include <stdlib.h>int a8=0,1,2,4,5,6,7,9;int main()     int count=;/設(shè)置欲生成的測(cè)試數(shù)據(jù)個(gè)數(shù)    

59、; int n,i;     int weishu=0;     int num=0;     freopen("c:10.in","w",stdout);     srand(time(NULL);     while(count-)           &

60、#160;   num=0;          n=rand()%7+1;          num=num*10+an;/第1位數(shù)字不為0，單獨(dú)算          weishu=rand()%9+1;/隨機(jī)確定測(cè)試數(shù)據(jù)的位數(shù)       

61、;   for(i=2;i<=weishu;i+)/生成完整的測(cè)試數(shù)據(jù)，避免用數(shù)字3和8                            n=rand()%8;            &#

62、160;     num=num*10+an;                    printf("%dn",num);          printf("0n");     return 0;#includ

63、e <stdio.h>#define SIZE 9 int sSIZE=1,2,36,488,5904,67232,;int kSIZE=1,10,100,1000,10000,; int Judge(int num,int p,int j)    int i;    if(num0>3 && num0<8)        p-;    

64、if(num0>8)        p=p-2;    for(i=1;i<j;i+)            if(numi<3)            p=p-numi*si;   

65、0;    if(numi>3 && numi<8)            p=p-(numi-1)*si-ki;        if(numi>8)            p=p-(numi-2)*si-

66、2*ki;        return p;   int main()    int n,temp,i;    int numSIZE;    while(1)            scanf("%d",&n);

67、0;       if(n=0) return 0;        temp=n;        i=0;        do             

68、0;      numi=temp%10;            temp=temp/10;            i+;        while(temp>0);    

69、    printf("%d: %dn",n,Judge(num,n,i);        問(wèn)題 I: 簡(jiǎn)單查找時(shí)間限制: 3 Sec  內(nèi)存限制: 22 MB題目描述給定一個(gè)集合，查找元素是否在集合中出現(xiàn)。輸入每個(gè)測(cè)試用例由多行組成，第一行是兩個(gè)整數(shù)n和m，這2個(gè)數(shù)的取值在1到3 000 000之間。自第二行起一共有n+m個(gè)整數(shù)，其中前面n個(gè)整數(shù)代表集合的元素，隨后的m個(gè)整數(shù)是待查詢的數(shù)。n+m個(gè)整數(shù)的取值在范圍1到10 0

70、00 000之間。輸出對(duì)于每個(gè)待查詢的數(shù)，如果在集合中則輸出yes,否則輸出no.樣例輸入5 345 56 23 6 56633 66 63 22934 235 555555 230 0樣例輸出nonoyesyesno提示是問(wèn)題1073的加強(qiáng)版，寫(xiě)算法時(shí)，注意內(nèi)存分配及時(shí)間效率。數(shù)組請(qǐng)定義全局?jǐn)?shù)組#include<stdio.h>#include<iostream>using namespace std;#include<algorithm>#define SIZE  int aSIZE; int main()  &#

71、160; int m,n,i,j,k;    int low,high,mid;    while(1)            scanf("%d %d",&n,&m);        if(n=0 && m=0) return 0;  

72、      for(i=0;i<n;i+)        scanf("%d",&ai);        sort(a,a+n);        for(j=0;j<m;j+)       

73、         scanf("%d",&k);          low=0,high=n-1;          while(low<=high)          

74、60;             mid=(low+high)/2;               if(amid=k)                 

75、               printf("yesn");                 break;             

76、;                   if(amid>k)                 high=mid-1;          

77、;      else                 low=mid+1;                    if(low>high)  

78、         printf("non");                return 0; 問(wèn)題 J: 赫夫曼編碼時(shí)間限制: 1 Sec  內(nèi)存限制: 128 MB題目描述赫夫曼編碼能夠產(chǎn)生最短的報(bào)文。以報(bào)文“ABCDABCDABCABDABAA”為例，A編為0，B對(duì)應(yīng)10

79、，C對(duì)應(yīng)110，D對(duì)應(yīng)111，整體的報(bào)文長(zhǎng)度為35位二進(jìn)制。相比于定長(zhǎng)的ASCII碼，壓縮比達(dá)到了18*8/35=4.1。輸入輸入有一系列的字符串組成，每個(gè)字符串占據(jù)一行。字符串僅包含大寫(xiě)字母和下劃線。字符串“END” 表示處理結(jié)束，不應(yīng)對(duì)其處理。輸出對(duì)每一個(gè)字符串，輸出其ASCII編碼的比特位長(zhǎng)度，赫夫曼編碼的比特位長(zhǎng)度，以及二者之比，精確到小數(shù)點(diǎn)后一位。樣例輸入ABCDABCDABCABDABAAAAAAAAAAAAAAAAAAAAEND樣例輸出144 35 4.1144 18 8.0提示#include <stdio.h>#include<string.h&g

80、t;#define N 100#define MAX 1000#define OK 1typedef struct /huffman節(jié)點(diǎn)char data;int weight;/權(quán)值int parent;/記錄父結(jié)點(diǎn)下標(biāo)int lchild;/左孩子int rchild;/右孩子HTNode;int CreateHT(HTNode ht,int n)/構(gòu)造huffman樹(shù)的代碼沒(méi)有一點(diǎn)錯(cuò)誤int i,k,lnode,rnode;int min1,min2;for(i=0;i<2*n-1/*一共2*n-1個(gè)節(jié)點(diǎn)*/;i+)hti.parent=hti.lchild=hti.rchild=

81、-1;/*初始化，所有節(jié)點(diǎn)的相關(guān)域?yàn)?1*/for(i=n;i<2*n-1;i+)min1=min2=32767;lnode=rnode=-1;/lnode和rnode為最小權(quán)重的兩個(gè)節(jié)點(diǎn)的位置for(k=0;k<=i-1;k+)if(htk.parent=-1)/只在尚未構(gòu)造二叉樹(shù)的結(jié)點(diǎn)中查找if(htk.weight<min1)/在節(jié)點(diǎn)中找到兩個(gè)最小的，min1和min2記錄下標(biāo)min2=min1;rnode=lnode;min1=htk.weight;lnode=k;/記錄下最小權(quán)重的下標(biāo)else if(htk.weight<min2)min2=htk.weigh

82、t;rnode=k;htlnode.parent=i;htrnode.parent=i;/更新父結(jié)點(diǎn)以及子節(jié)點(diǎn)的下標(biāo)hti.weight=htlnode.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;return OK;int AddNum(HTNode ht,int hcd,int k)int i,f;if(k=1)/結(jié)點(diǎn)分兩種情況，一種是只有一個(gè)結(jié)點(diǎn)hcd0=1;return 0;else/另一種是大于等于兩個(gè)結(jié)點(diǎn) for(i=0;i<k;i+) hcdi=0; f=hti.parent; while(f!=-1)/向

83、上回溯尋找父結(jié)點(diǎn)，直至找到整棵樹(shù)的根節(jié)點(diǎn) hcdi+;/父結(jié)點(diǎn)不為空，那數(shù)目就自增1（Huffman編碼長(zhǎng)度增1） f=htf.parent; return OK;int main() char str1MAX; HTNode nodeMAX;int hcdMAX;/用于記錄每個(gè)編碼的長(zhǎng)度int i,j,k,m;float s;while(1) k=0; scanf("%s",str1); if(strcmp(str1,"END")=0) continue; for(i=0;str1i!='0'i+) nodei.weight=0; fo

84、r(j=0;j<k;j+)/從第一位開(kāi)始搜索，如果找到了相同的字符，那么該字符權(quán)值增1 if(nodej.data=str1i) nodej.weight=nodej.weight+1; break;/找到了就不必再循環(huán),讀下一個(gè)字符 if(j=k)/沒(méi)找到，就加入node數(shù)組 nodek.data=str1i; nodek.weight=nodek.weight+1; k+; /最后得到的k為字符的種類數(shù)目 m=i;/記錄下i的值，i為輸入的總字符的個(gè)數(shù) CreateHT(node,k);/構(gòu)建一棵Huffman樹(shù)AddNum(node,hcd,k);/獲取個(gè)個(gè)字符HUffman編碼的

85、長(zhǎng)度f(wàn)or(i=0,s=0.0;i<k;i+)s=s+hcdi*nodei.weight;/獲取用Huffman編碼時(shí)總字符長(zhǎng)度printf("%d %.0f %.1fn",m*8,s,m*8/s);return 0;問(wèn)題 K: 最短路徑時(shí)間限制: 1 Sec  內(nèi)存限制: 128 MB題目描述求帶權(quán)有向圖中任意2個(gè)頂點(diǎn)之間的最短路徑。輸入先輸入頂點(diǎn)個(gè)數(shù)及邊的條數(shù)；然后依次輸入各條邊的信息，包括起點(diǎn)，終點(diǎn)，權(quán)值。輸出輸出任意2點(diǎn)間的路徑長(zhǎng)度信息。1）如果存在路徑，則輸出路徑長(zhǎng)度，如“1->2:2”表示頂點(diǎn)1至頂點(diǎn)2的路徑長(zhǎng)

86、度為2；2）如果不存在路徑，則輸出No Path。如“1->2:No Path”。樣例輸入3,50,1,41,0,61,2,20,2,112,0,3樣例輸出0->1:40->2:61->0:51->2:22->0:32->1:7提示數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）算法7.16_最短路徑Floyd算法#include <stdio.h>#include<string.h>   #define MAX_NAME 5 typedef int VRType;    &#

87、160;  #define OK 1 #define FALSE 0 #define TRUE 1   #define INFINITY  #define MAX_VERTEX_NUM 20  typedef int DistancMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;     typedef struct    int arcsMAX_VERTEX_NUMMAX_VERTEX_NUM

88、;    int vexnum,arcnum; MGraph;  int CreateDN(MGraph *G)     int i,j,k,b;   scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);     for(i=0;i<(*G).vexnum;+i)      for(j=0;j<(*G).vexnum;+j)             (*G).arcsij=INFINITY;          for(k=0;k<(*G).arcnum;k+)