数据结构题目及c语言代码

《数据结构》课程设计题目

(程序实现采用C语言)

题目1：猴子选王（学时：3）

一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表

#include #include // 链表节点

typedef struct _RingNode {

int pos;

struct _RingNode *next; }RingNode, *RingNodePtr;

// 创建约瑟夫环，pHead:链表头指针，count:链表元素个数 void CreateRing(RingNodePtr pHead, int count) {

RingNodePtr pCurr = NULL, pPrev = NULL;

int i = 1; pPrev = pHead; while(--count > 0) {

pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++;

pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; }

pCurr->next = pHead; // 构成环状链表 }

void KickFromRing(RingNodePtr pHead, int n) {

RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) {

if (i == n)

{

// 踢出环

printf(\"\\n%d\ // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr);

pCurr = pPrev->next; i = 1; }

pPrev = pCurr;

pCurr = pCurr->next; if (pPrev == pCurr) {

// 最后一个

printf(\"\\nKing is %d\ free(pCurr); break; } i++; } }

// 显示出圈循序

int main() {

int n = 0, m = 0;

RingNodePtr pHead = NULL; printf(\"M(person count) = \"); scanf(\"%d\

printf(\"N(out number) = \"); scanf(\"%d\if(m <= 0 || n <= 0) {

printf(\"Input Error\\n\"); return 0; }

// 建立链表

pHead = (RingNodePtr)malloc(sizeof(RingNode)); pHead->pos = 1; pHead->next = NULL; CreateRing(pHead, m); // 开始出圈

printf(\"\\nKick Order: \");

KickFromRing(pHead, n); printf(\"\\n\"); system(\"pause\"); return 0; }

//数组做： #include #include #include

void SelectKing(int MonkeyNum, int CallNum); void main() {

int MonkeyNum; int CallNum; /* 输入猴子的个数 */ printf(\"Monkey Num = \"); scanf(\"%d\/* 输入M的值 */ printf(\"Call Num = \"); scanf(\"%d\

SelectKing(MonkeyNum, CallNum); }

void SelectKing(int MonkeyNum, int CallNum) {

int *Monkeys; // 申请一个数组，表示所有的猴子；

int counter = 0; //计数，当计数为猴子个数时表示选到最后一个猴子了； int position = 0; // 位置，数组的下标，轮流遍历数组进行报数； int token = 0; // 令牌，将报数时数到M的猴子砍掉； // 申请猴子个数大小的数组，把桌子摆上。

Monkeys = (int *)malloc(sizeof(int)* MonkeyNum); if (NULL == Monkeys) {

printf(\"So many monkeys, system error.\\n\"); return; }

// 将数组的所有内容初始化为0，被砍掉的猴子设置为1 memset(Monkeys, 0, sizeof(int)*MonkeyNum); // 循环，直到选中大王

while(counter != MonkeyNum) {

// 如果这个位置的猴子之前没有砍掉，那么报数有效 if (Monkeys[position] == 0) {

token++; // 成功报数一个，令牌+1，继续报数直到等于M // 如果报数到M，那么将这个猴子砍去 if (token == CallNum) {

Monkeys[position] = 1; // 设置为1，表示砍去 counter++; // 计数增加

token = 0; // 设置为0，下次重新报数

// 如果是最后一个猴子，把它的位置打印，这个就是大王了 if (counter == MonkeyNum) {

printf(\"The king is the %d monkey.\\n\ } } }

// 下一个猴子报数

position = (position + 1)%MonkeyNum; }

// 释放内存，开头为所有猴子创建的桌子 free(Monkeys); return; }

题目2 ：字符逆转（学时：3）

从键盘读入一个字符串，把它存入一个链表（每个结点存储1个字符），并按相反的次序将字符串输出到显示屏。

#include #include struct node {

struct node *prev; char c;

struct node *next; };

struct node *input(struct node *top); int main(void) {

struct node T,*top=&T,*bottom=&T,*p=NULL; T.prev=NULL; T.next=NULL;

T.c='\\0';

bottom=input(top); p=bottom->prev; while(p!=NULL) {

printf(\"%c\p=p->prev; } return 0; }

struct node *input(struct node *top) {

struct node *t; char x;

while((x=getchar())!='\\n') {

top->c=x;

t=(struct node *)malloc(sizeof(struct node)); top->next=t; t->prev=top;

t->next=NULL; t->c='\\0'; top=top->next; }

return top; }

题目3 ：工资核算（学时：3）

设有一个单位的人员工资有如下信息：name、department、 base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。

#include #include #define SIZE 2

#define LENTH sizeof(struct stuff) struct stuff {

char name[100]; char department[100]; int basepay; int allowance; int total;

}stuff[SIZE]; main() { FILE *fp; int i;

printf(\"Please enter name department basepay allowance：\\n\"); for(i=0;iscanf(\"%s %s %f %f\.allowance);

if((fp=fopen(\"paydata.dat\ {

printf(\"Can't open file\\n\"); return 0; }

for(i=0;iif(fwrite(&stuff[i],LENTH,1,fp)!=1) printf(\"文件写入出错\\n\"); fclose(fp);

if((fp=fopen(\"paydata.dat\ {

printf(\"Can't open file\\n\");

}

printf(\"修改过后的结果：\\n\"); for(i=0;ifread(&stuff[i],LENTH,1,fp);

stuff[i].total=stuff[i].basepay+100+stuff[i].allowance;

printf(\"%-10s%-10s %f %f %f\\nuff[i].allowance,stuff[i].total);

}

fclose(fp); return 0; }

题目4：满足条件的有序表生成（学时：3）

已知三个有序表A、B、C，它们皆由同一类元素构成，现要求对于表A作以下运算而获得有序表D：排出A中所有的既在B中又在C中出现的元素。另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。

#include void main() {

int a[7],b[5],c[6],d[7];

int i,j,k,t,m;

printf(\"\\nPlease enter 7 numbers of A:\"); for(i=0;i<7;i++) scanf(\"%d\for(j=0;j<6;j++) for(i=0;i<6-j;i++) if(a[i]>a[i+1])

{t=a[i];a[i]=a[i+1];a[i+1]=t;} printf(\"the sorted numbers：\\n\"); for(i=0;i<7;i++) printf(\"%5d\

printf(\"\\nPlease enter 5 numbers of B:\"); for(i=0;i<5;i++) scanf(\"%d\printf(\"\\n\"); for(j=0;j<4;j++) for(i=0;i<4-j;i++) if(b[i]>b[i+1])

{t=b[i];b[i]=b[i+1];b[i+1]=t;} printf(\"the sorted numbers:\\n\");

for(i=0;i<5;i++) printf(\"%5d\

printf(\"\\nPlease enter 6 numbers of C:\"); for(i=0;i<6;i++) scanf(\"%d\for(j=0;j<5;j++) for(i=0;i<5-j;i++) if(c[i]>c[i+1])

{t=c[i];c[i]=c[i+1];c[i+1]=t;} printf(\"the sorted numbers：\\n\"); for(i=0;i<6;i++) printf(\"%5d\printf(\"\\n\"); for(i=0;i<5;i++) {

for(j=0;j<6;j++) {

if(b[i]==c[j]) {

for(k=0;k<7;k++)

{

if(b[i]==a[k]) a[k]=m; } } } }

printf(\"\\n\"); k=0;

for(i=0;i<7;i++) if(a[i]!=m) { d[k]=a[i]; k++; }

printf(\"生成的有序表d为 \"); for(i=0;i题目5：一元 多项式的减法（学时：6）

设有两个一元多项式A(x),B(x)，请完成运算A(x)+B(x)、A(x)-B(x)，要求多项式采用链表进行存储。另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。

#include struct Polynode { int coef; int exp; Polynode *next; }Polynode,*Polylist;

void Polycreate(Polylist head) {

Polynode *rear,*s; int c,e;

rear=head;printf(\"请输入多项式的系数项和指数项\"); scanf(\"%d,%d\while(c!=0) {

s=(Polynode*)malloc(sizeof(Polynode)); s->coef=c; s->exp=e;

rear->next=s; rear=s;

scanf(\"%d,%d\}

rear->next=NULL; }

void Polyadd(Polylist polya,Polylist polyb) {

Polynode *p,*q,*tail,*temp; int sum; p=polya->next; q=polyb->next; tail=polya;

while(p!=NULL&&q!=NULL) {

if(p->expexp) {

tail->next=p; tail=p; p=p->next;

}

else if(p->exp=q->exp) {

sum=p->coef+q->coef; if(sum!=0) {

p->coef=sum; tail->next=p; tail=p; p=p->next; temp=q; q=q->next; free(temp); } else { temp=p; p=p->next; free(temp); q=q->next;

free(temp); } } else {

tail->next=q; tail=q; q=q->next; } }

if(p!=NULL) tail->next=p; else

tail->next=q; }

void Polysubstract(Polylist polya,Polylist polyb) {

Polylist h=polyb; Polylist p=pb->next; Polylist pd;

while(p) {p->coef*=-1; p=p->next; }

pd=Polyadd(pa,h);

for(p=h->next;p;p=p->next) p->coef*=-1; return pd； }

void PrintPolyn(Polyn P)

void printfPolyn(Polynode *head) {

Polynode *p=head->next; while(p)

{printf(\"%dx^%d\if(p->next)

printf(\"+\");p=p->next;} }

int main() {

Polynode *La,Lb; La=Polycreate(); Lb=Polycreate(); PrintPolyn(La); printf(\"/n\"); PrintPolyn(Lb); printf(\"/n\");

Polyadd(polya,polyb); printPolyn(polya); return 0; }

题目6：床位分配（学时：6）

某客店有N个等级的房间，第k级客房有A（k）个，每个房间有B（k）个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；分配不成功时，允许更改房间等级，若不更改等级，印出“满客”提示。

#include #include #include #include #define N 3

typedef struct Room {

int roomlevel; int roomnum; int bednum; int peoplenum; int bed[N]; int sex; char name[10]; struct Room *next; }Room;

Room *creat(int roomlevel,int room[],int bed[]) {

Room *head,*p,*q; int i=1,j,h,num=1;

head=(Room *)malloc(sizeof(Room)); head->peoplenum=0; q=head;

while (i<=roomlevel) {

for(j=1; j<=room[i]; j++) {

p=(Room *)malloc(sizeof(Room));

p->roomlevel=i; p->roomnum=num++; p->peoplenum=0;

p->sex=-1; for(h=0; hnext=p; q=p; } i++; }

p->next=NULL; return(head); }

void Init(Room *head) {

Room *p; int i; p=head; while(p!=NULL)

p->bed[h]=0;

{

p->peoplenum=0; p->sex=-1; for(i=0;ibed[i]=0; p=p->next; }

printf(\"\\n\\n 操作成功 \\n\"); }

void Getin(Room *head) {

Room *p; int i,s,lev,age; char name[10]; int number=0; int bednumber=0;

printf(\"\\n\\n 欢迎使用订房系统 \\n\\n\"); printf(\"请输入性别（1为男，2为女）：\"); scanf(\"%d\

printf(\"\\n\\n 请输入想入住的房间等级：\");

scanf(\"%d\p=head->next; while(p!=NULL) {

if((p->roomlevel==lev)&&((p->sex==s)||(p->sex==-1))) {

for(i=0;ibed[i]==0) {

number=p->roomnum; bednumber=i+1; p->bed[i]=1; p->sex=s;

p->peoplenum++; break; }

if(number!=0)break; }

p=p->next; }

if(number==0&&bednumber==0) printf(\"\\n 满客 \\n\"); else {

head->peoplenum++;

printf(\"\\n订单已下，请输入客人信息: \\n\"); printf(\"名字:\\n\"); scanf(\"%s\ printf(\"年龄 :\\n\"); scanf(\"%d\ printf(\"您的订单3:\\n\");

printf(\"名字 年龄 性别 到达时间 房间等级 房间号 床位号\\n\");

if (s==1) printf(\"%s

%d

male

11-19 %d %d %d\\n\m,bednumber);

else printf(\"%s

%d

formale

11-19 %d %d %d \\n\

printf(\"\\n\"); }

}

void Checkout(Room *head) {

Room *p;

int number,bednumber,i,s; printf(\"欢迎使用退房系统：\"); printf(\"\\n\\n 请输入房间号：\"); scanf(\"%d\

printf(\"\\n\\n 请输入性别（1为男，0为女）：\"); scanf(\"%d\

printf(\"请输入床位号：\"); scanf(\"%d\p=head->next; while(p!=NULL) {

if(p->roomnum==number) for(i=0;iroomlevel;i++) if(i+1==bednumber) {

p->bed[i]=0;

p->peoplenum--; if(p->peoplenum<0) p->peoplenum=0; if(p->peoplenum==0) p->sex=-1;

printf(\"您已退房，欢迎下次光临\"); break; }

p=p->next; } }

void Display(Room *head) {

Room *p; int i=0; p=head->next;

printf(\"\\n\\n已订房间查询\"); if (head->peoplenum==NULL) {

printf(\"所有等级房间空房\");

return; }

while(p->peoplenum!=NULL) {

if(p->sex==1)

printf(\"\\n 房间号：%d，房间等级：%d，已住人数：%d，住房人性别：男\

else

printf(\"\\n 房间号：%d，房间等级：%d，已住人数：%d，住房人性别：女\

while (ipeoplenum) if (p->bed[i]==1) {

printf(\"，已住床位号：%d\ i++; }

printf(\"\\n\"); p=p->next; } }

void main()

{

int n,k=1,i,roomlevel,room[10],bed[10],sum=0; Room *head;

printf(\"请输入房间等级数:\\n\");

printf(\"Roomlevel:\"); scanf(\"%d\for (i=1; i<=roomlevel; i++) {

printf(\"\\n %d等级房间数:\ scanf(\"%d\printf(\"\\n %d房间内床位数:\ scanf(\"%d\sum+=room[i]*bed[i]; }

head=creat(roomlevel,room,bed); while(k==1) {

printf(\" \\n欢迎光临 :\\n\");

printf(\"1:订房\\n2:退房\\n3:查询\\n4:退出系统\\n\"); printf(\"请输入您的选择:\\n\"); scanf(\"%d\

switch(n) {

case 1: Getin(head); break; case 2: Checkout(head); break; case 3: Display(head);break; case 4: k=0; break;

default : printf(\"Error!! please input again:\"); break; } } }

题目7：文本文件单词的检索及计数（学时：6）

要求编程建立一个文本文件，每个单词不包括空格及跨行，单词由字符序列构成且区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首次出现的行号及位置。

#include #include #include typedef struct StringWord {

char ch[100]; }SW;

void CreatTextFile() {

char filename[10],ch; FILE*fp;

printf(\"请输入所用的文件名:\"); scanf(\"\\n%s\fp=fopen(filename,\"w\");

printf(\"请输入一段文字，以$号结束:\\n\"); scanf(\"%s\while(ch!='$') {

fwrite(&ch,sizeof(ch),1,fp); scanf(\"%c\} fclose(fp); }

void CountWord() { FILE *fp; SW S,T;

char ch;

char filename[10]; int i=0,number=0;

printf(\"输入文本文件名：\"); scanf(\"%s\fp=fopen(filename,\"r\");

printf(\"输入要统计计数的单词：\"); scanf(\"%s\ while(!feof(fp)) {

ch= fgetc(fp); if(ch==' ') { if(i!=0) {

S.ch[i]='\\0'; i=0;

if (strcmp(S.ch,T.ch)==0) number++; }

}

else if (ch=='\\n') {

if (i!=0)

{ S.ch[i]='\\0';

i=0; if (strcmp(S.ch,T.ch)==0) number++; } } else {

S.ch[i]=ch; i++; } }

if (number==0)

printf(\"单词不在文本中 \\n\"); else

printf(\"单词%s在文件%s出现了%d次:\

fclose(fp); }

void SearchWord() { FILE*fp; SW S,T;

char filename[10]; int i,i_r,line,flag=0; char ch;

printf(\"\\n输入文本文件名：\"); scanf(\"%s\fp=fopen(filename,\"r\");

printf(\"输入要统计计数的单词：\"); scanf(\"%s\ i=i_r=0; line=1; while(!feof(fp)) {

ch=fgetc(fp); if (ch==' ')

{ if (i!=0) {

i_r++; S.ch[i]='\\0'; i=0;

if (strcmp(T.ch,S.ch)==0) {

printf(\"%s单词第一次出现是在 %d 行,%d列\\n\flag=1; break; } } }

else if (ch=='\\n') {

if (i!=0) {

i_r++; S.ch[i]='\\0'; if (strcmp(T.ch,S.ch)==0) {

printf(\"%s单词第一次出现是在 %d 行,%d列\\n\ flag=1; break; }

i=0; i_r=0; line++; } else {

line++; i_r=0; } } else {

S.ch[i]=ch; i++; } }

if (flag==0)

printf(\"%s单词不在文本中\\n\fclose(fp); } int main()

{

CreatTextFile(); CountWord(); SearchWord(); }

题目8：二叉树的遍历（学时：6）

二叉树以lson-rson链接方式存储，以菜单方式设计并完成功能任务：建立并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度，其中对于中序、后序的遍历运算要求采用非递归方式。

#include

#include

#define M 100

typedef struct node//定义二叉树结点

{

char data;

struct node *lchild,*rchild;

}BTNode;

BTNode *CreatBTree()//创建二叉树 (先序递归)

{

char ch;

BTNode *b;

scanf(\"%c\

if(ch=='#')//递归结束控制符

b=NULL;

else

{

b=(BTNode *)malloc(sizeof(BTNode));

b->data=ch;

b->lchild=CreatBTree();//递归先序建立左子树

b->rchild=CreatBTree();//递归先序建立右子树

}

return b;

}

void PreOrder(BTNode *b)//递归先序遍历二叉树函数

{

if(b!=NULL)

{

printf(\"%c \

PreOrder(b->lchild);

PreOrder(b->rchild);

}

}

void InOrder(BTNode *b)//非递归中序遍历二叉树函数

{

BTNode *stack[M],*p;

int top=-1;

if(b!=NULL)

{

p=b;

while(top>-1||p!=NULL)

{

while(p!=NULL)//扫描p的所有左结点并入栈

{

top++;

stack[top]=p;

p=p->lchild;

}

if(top>-1)

{

p=stack[top];//出栈访问结点

top--;

printf(\"%c \

p=p->rchild;//扫描p的右结点

}

}

printf(\"\\n\");

}

}

void PostOrder(BTNode *b)//非递归后序遍历二叉树函数

{

BTNode *stack[M],*p;

int sign,top=-1;

if(b!=NULL)

{

do

{

while(b!=NULL)// b所有左结点入栈

{

top++;

stack[top]=b;

b=b->lchild;

}

p=NULL; // p指向栈顶前一个已访问结点

sign=1; //置b为已访问

while(top!=-1 && sign)

{

b=stack[top];//取出栈顶结点

if(b->rchild==p) //右孩子不存在或右孩子已访问则访问b

{

printf(\"%c \

top--;

p=b; //p指向被访问的结点

}

else

{

b=b->rchild;//b指向右孩子结点

sign=0;//置未访问标记

}

}

}while(top!=-1);

printf(\"\\n\");

}

}

void change(BTNode *b) //左右子树交换(递归)

{

BTNode *r;

r=(BTNode *)malloc(sizeof(BTNode));

int f1=0,f2=0;

if(b==0) return ; //树为空时，跳出

if(b->lchild)

{

change(b->lchild);

r->lchild=b->lchild;

f1++; }

if(b->rchild)

{

change(b->rchild);

r->rchild=b->rchild;

f2++; }

//有左子树，符号位不为空

//有右子树，符号位不为空

if(f1==0) r->lchild=NULL; //否则，给中间变量赋空值

if(f2==0) r->rchild=NULL;

if(f1||f2)

{

b->rchild=r->lchild; b->lchild=r->rchild;

}

}

int max(int m,int n)

{

if(m>n)

return m;

else return n;

//左右子树交换

}

int count(BTNode *b) //计算树高(递归)

{

if(b==NULL)

return 0;

else return (1+max(count(b->lchild),count(b->rchild)));

}

int main()

{

BTNode *root = NULL;

printf(\"-----------------二叉树的遍历-----------------\\n\\n\");

printf(\"请按先序递归顺序创建二叉树 (结束符 #):\\n\");

root = CreatBTree();

printf(\"\\n递归先序遍历结果:\\n\");

PreOrder(root);

printf(\"\\n非递归中序遍历结果:\\n\");

InOrder(root);

printf(\"非递归后序遍历结果:\\n\");

PostOrder(root);

printf(\"\\n树高: %d\\n\

printf(\"\\n左右子树交换位置:\");

change(root);

printf(\"\\n递归先序遍历结果:\\n\");

PreOrder(root);

printf(\"\\n非递归中序遍历结果:\\n\");

InOrder(root);

printf(\"非递归后序遍历结果:\\n\");

PostOrder(root);

return 0;

题目9：创建二叉排序树（学时：3）

二叉排序树以lson-rson链接方式存储，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。

#include #include typedef struct node { int data;

struct node *lchild ,*rchild; }BSTNode,*BSTTree;

//二叉排序树的插入（递归算法） void InsertBST(BSTTree *BST , int key) {

if((*BST)==NULL) {

(*BST)=(BSTNode*)malloc(sizeof(BSTNode));

(*BST)->data=key; (*BST)->lchild=NULL; (*BST)->rchild=NULL; }

else if((*BST)->data>key)//如果待插入的元素比根结点元素值小 InsertBST(&((*BST)->lchild),key);//插入在根结点的左子树 else

InsertBST(&((*BST)->rchild),key);//插入在根结点的右子树上 }

//创建一棵二叉排序树 BSTTree CreateBSTTree() {

BSTTree bst=NULL; int x; while(1) {

scanf(\"%d\if(x==00)break; InsertBST(&bst,x); }

return bst; }

//中序遍历

void InOrder(BSTTree BST) {

if(BST!=NULL) {

InOrder(BST->lchild); printf(\"%5d\InOrder(BST->rchild); } }

void main() {

BSTTree BST;

printf(\"建立二叉排序树，请输入序列:\\n\"); BST=CreateBSTTree();

printf(\"中序遍历后输出的该序列为:\"); InOrder(BST); printf(\"\\n\");

}

题目10：霍夫曼编码应用（学时：3）

假设一串由大写字母构成的电文，采用霍夫曼规则对其进行编码，以菜单方式设计并完成功能任务：建立霍夫曼树、霍夫曼编码生成、编码文件译码。

#include #include #include #define n 100 #define m 2*n-1 typedef struct {

int weight; char ch;

int parent,lchild,rchild; }HTNode; typedef struct{ char ch; char bits[n+1]; }CodeNode; typedef struct {

char cha; int number; }COUNTER;

int Init( HTNode ht[])//初始化函数，为每一个字母信息赋权值 { int i,s=1;

COUNTER counter[27]; char ch;

printf(\"请输入字符：\\n\"); scanf(\"%c\counter[1].cha='A'; counter[2].cha='B'; counter[3].cha='C'; counter[4].cha='D'; counter[5].cha='E'; counter[6].cha='F'; counter[7].cha='G'; counter[8].cha='H'; counter[9].cha='I'; counter[10].cha='J';

counter[11].cha='K'; counter[12].cha='L'; counter[13].cha='M'; counter[14].cha='N'; counter[15].cha='O'; counter[16].cha='P'; counter[17].cha='Q'; counter[18].cha='R'; counter[19].cha='S'; counter[20].cha='T'; counter[21].cha='U'; counter[22].cha='V'; counter[23].cha='W'; counter[24].cha='X'; counter[25].cha='Y'; counter[26].cha='Z'; for(i=1;i<=26;i++) counter[i].number=0; while(ch!=' ') {

switch(ch) {

case 'A':counter[1].number++;break; case 'B':counter[2].number++;break; case 'C':counter[3].number++;break; case 'D':counter[4].number++;break; case 'E':counter[5].number++;break; case 'F':counter[6].number++;break; case 'G':counter[7].number++;break; case 'H':counter[8].number++;break; case 'I':counter[9].number++;break; case 'J':counter[10].number++;break; case 'K':counter[11].number++;break; case 'L':counter[12].number++;break; case 'M':counter[13].number++;break; case 'N':counter[14].number++;break; case 'O':counter[15].number++;break; case 'P':counter[16].number++;break; case 'Q':counter[17].number++;break; case 'R':counter[18].number++;break;

case 'S':counter[19].number++;break; case 'T':counter[20].number++;break; case 'U':counter[21].number++;break; case 'V':counter[22].number++;break; case 'W':counter[23].number++;break; case 'X':counter[24].number++;break; case 'Y':counter[25].number++;break; case 'Z':counter[26].number++;break; }

scanf(\"%c\}

for(i=1;i<=26;i++) {

if(counter[i].number!=0) {

ht[s].weight=counter[i].number; ht[s].ch=counter[i].cha; s++; } }

s=s-1; return s; }

void select(HTNode ht[],int q,int *p1,int *p2) //select函数 {

int i,j,x=0,y=0; for(j=1;j<=q;++j) {

if(ht[j].parent==0) { x=j; break; } }

for(i=j+1;i<=q;++i) {

if(ht[i].weightx=i; //选出最小结点 }

}

for(j=1;j<=q;++j) {

if(ht[j].parent==0&&x!=j) { y=j; break; } }

for(i=j+1;i<=q;++i) {

if(ht[i].weighty=i; //选出第二小结点 } } if(x>y) { *p1=y; *p2=x;

} else { *p1=x; *p2=y; } }

void huffman_setup(HTNode ht[],int s) { int i,a; int p1,p2; a=2*s-1;

for(i=1;i<=a;i++) { if(i<=s) {

ht[i].weight=ht[i].weight; } else {

ht[i].weight=0; }

ht[i].parent=ht[i].lchild=ht[i].rchild=0; }

for(i=s+1;i<=a;++i) //建立赫夫曼树 {

select(ht,i-1,&p1,&p2); ht[p1].parent=i; ht[p2].parent=i; ht[i].lchild=p1; ht[i].rchild=p2;

ht[i].weight=ht[p1].weight+ht[p2].weight; } }

void huffman_show(CodeNode hc[],HTNode ht[],int s)//给字符编码 {

char q[n]; int i,p,c,f; q[s-1]='\\0';

for(i=1;i<=s;i++)

{ p=s-1;

for(c=i,f=ht[i].parent;f;c=f,f=ht[f].parent) {

if(ht[f].lchild==c) {

q[--p]='0'; } else {

q[--p]='1'; }

strcpy(hc[i].bits,&q[p]); }

hc[i].ch=ht[i].ch; } }

//-----------------编码

void huffman_code(CodeNode hc[]) {

int i=1; char ch,ah;

printf(\"请输入编码的信息：\\n\"); scanf(\"%c\printf(\"编码是：\\n\"); while(ch!=' ') {

ah=hc[i].ch; while(ch!=ah) { i++; ah=hc[i].ch; }

printf(\"%s\ scanf(\"%c\i=1; } }

//-----------------解码

void huffman_read(HTNode ht[],int s)//根据编码来返回字母信息

{ int i,j,t; char b; t=2*s-1; i=t;

printf(\"进行解码\\n\"); fflush(stdin); scanf(\"%c\

printf(\"解码后的信息是：\\n\"); while(b!=' ') {

if(b=='0') i=ht[i].lchild; else i=ht[i].rchild; if(ht[i].lchild==0) {

printf(\"%c\j=i; i=t; }

scanf(\"%c\} }

int main() {

int flag=1,choice; int s,i;

HTNode ht[m]; CodeNode hc[n]; printf(\"霍夫曼树：\\n\"); s=Init(ht);

huffman_setup(ht,s); huffman_show(hc,ht,s); for(i=1;i<=s;i++) {

printf(\"%c ---> %s\\n\}

while(flag) {

printf(\"请输入您想要进行的操作：\\n 1 编码\\n 2 解码\\n 3 退出\\n\");

fflush(stdin);

scanf(\"%d\switch(choice) { case 1:

huffman_code(hc); printf(\"\\n\"); break; case 2: huffman_read(ht,s); printf(\"\\n\"); break; case 3: flag=0; } } return 0; }

题目11：关键路径寻找（学时：6）

对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。

#include #include struct Node //邻接点 {

int vex;//顶点信息 int weight;//权值 struct Node *next; };

struct Hnode //头结点 {

int vex2; int id; //入度 struct Node *link; }A[20];

void create(struct Hnode A[20],int n,int e) {

int i,j,k,l; struct Node * p;

for(i=1;i<=n;i++)//建立顶点表 {

A[i].vex2=i; A[i].id=0; A[i].link=NULL; }

for(k=1;k<=e;k++)//建图 {

printf(\"\\n请输入边及其权值:\\n\"); scanf(\"%d\ scanf(\"%d\scanf(\"%d\

p=(struct Node *)malloc(sizeof(struct Node)); p->vex=j; p->weight=l; p->next=A[i].link; A[i].link=p; }

for(i=1;i<=n;i++)//完善入度 {

p=A[i].link; while(p!=NULL)

{

k=p->vex; A[k].id=A[k].id+1; p=p->next; } } }

void find(struct Hnode A[20],int n) {

int i,j,m,front,rear; int k=0;

int ve[20],vl[20],e[20],l[20]; int tpord[20]; struct Node *p;

for(i=1;i<=n;i++) //初始化顶点（事件）的最早发生时间和最迟发生时间 { ve[i]=0; vl[i]=0; }

front=0;

rear=0;

for(i=1;i<=n;i++) {

if(A[i].id==0)//找到入度为零顶点，准备拓扑排序 {

rear++; tpord[rear]=i; } } m=0;

while(front!=rear)//堆栈不为空 {

front++; j=tpord[front];

m++; //记录访问了多少个顶点 p=A[j].link;

while(p!=NULL) {

k=p->vex;

A[k].id=A[k].id-1; //访问之后入度减一

if(ve[j]+(p->weight)>ve[k])

ve[k]=ve[j]+(p->weight);//顶点最早发生时间，取最大值 if(A[k].id==0) {

rear++; tpord[rear]=k; }

p=p->next; } } if(mprintf(\"\\n网中存在回路，不能进行拓扑排序!\"); return; }

for(i=1;i<=n;i++)

vl[i]=ve[n];//顶点的最早发生时间赋给顶点的最迟发生时间 for(i=n-1;i>=1;i--)//进行逆拓扑排序 {

j=tpord[i];

p=A[j].link; while(p!=NULL) {

k=p->vex;

if((vl[k]-p->weight)vl[j]=vl[k]-(p->weight);//确定顶点最迟发生时间 p=p->next; } } i=0;

for(j=1;j<=n;j++) {

p=A[j].link; while(p!=NULL) {

k=p->vex; i++;

e[i]=ve[j]; //活动最早发生时间

l[i]=vl[k]-(p->weight);//活动最迟发生时间 printf(\"\\n <%d ,%d>:\j].vex2,A[k].vex2);

if(l[i]==e[i]) {

printf(\"是关键活动!\"); } else {

printf(\"不是关键活动!\"); }

p=p->next; } } }

void main() { int n,e;

printf(\"\\n请输入顶点总数:\"); scanf(\"%d\

printf(\"\\n请输入边的总数: \"); scanf(\"%d\create(A,n,e);

find(A,n); }

题目12：堆排序实现（学时：3）

假设有一个数据类型为整型的一维数组A，A 中的数据元素呈无序状态，编写一个采用堆排序法将A中的数据元素按由小到大进行排序的程序。

#include #define MAX 255 int A[MAX];

void creatdui(int l,int m) //建初始堆过程函数 { int i,j,x; i=l;

j=2*i; //R[j]是R[i]的左孩子 x=A[i]; while(j<=m) {

if(jA[i]=A[j]; //将A[j]调到父亲的位置上

i=j; //修改i和j的值，以便继续向下筛选 j=2*i; }

else j=m+1; //起结束作用 }

A[i]=x; //被筛结点的值存入最终的位置 }

void sortdui(int n) { int i; int m;

for(i=n/2;i>=1;i--)

creatdui(i,n); //建立初始堆，遍布所有的根结点 for(i=n;i>=2;i--)

{ //进行n-1次循环完成堆排序 m=A[i];

A[i]=A[1]; //将第一个元素同当前区域的最后一个元素对换 A[1]=m; creatdui(1,i-1);

} //筛选A[1]结点，得到i-1个结点的堆，仅有A[1]可能违反堆性质

}

void main() { int i,n;

printf(\"---------------------堆排序---------------------\\n\\n\"); printf(\"输入整型一维数组A中数字总数:\"); scanf(\"%d\if(n<=0||n>MAX) {

printf(\"\\n输入的数据有误\"); return; }

printf(\"\\n请输入整型无序序列:\\n\"); for(i=1;i<=n;i++) {

scanf(\"%d\}

printf(\"\\n该序列为:\\n\"); for(i=1;i<=n;i++) {

printf(\"%4d\}

sortdui(n);

printf(\"\\n堆排序后的序列为:\\n\"); for(i=1;i<=n;i++) {

printf(\"%4d\}

printf(\"\\n\"); }

题目13基数排序的实现（学时：3）

A为每个关键字不超过3位的十进制整数关键字集合，试编写一个采用静态链表组织模式实现的基数排序程序将A进行由小到大的排序。