线性表是数据结构中最简单、最常用的一种线性结构，也是学习数据结构全部内容的基础，其掌握的好坏直接影响着后继课程的学习。线性表的顺序存储结构，即顺序表的概念相对比较简单，因此，本章的主要任务是使用有关单链表的操作来实现通讯录信息系统的管理。
1.1设计要求
本章的设计实验要求使用有关链表的操作来实现通讯录信息系统的管理。为了验证算法，通讯录管理包括单通讯录链表的建立、通讯者的插入、通讯者的删除、通讯者的查询及通讯录表的输出等。主控菜单的设计要求使用数字0—5来选择菜单项，其他输入则不起作用。
程序运行后，给出6个菜单项的内容和输入提示：
1．通讯录链表的建立
2. 通讯者结点的插入
3. 通讯者结点的查询
4. 通讯者结点的删除
5. 通讯录链表的输出
0. 退出管理系统
请选择0—5：
1.2设计分析
1.2.1主控菜单函数设计分析
1.实现循环和功能选择
首先编写一个主控菜单驱动程序，输入0—5以进入相应选择项。假设输入选择用变量sn存储，它作为menu_select函数的返回值给switch语句。使用for循环实现重复选择，并在主函数main()中实现。
实际使用时，只有选择大于5或小于0的值，程序才能结束运行，这就要使用循环控制。这里使用for循环语句实现菜单的循环选择，为了结束程序的运行，使用了“return”语句，也可以使用“exit(0);”语句。
2.得到sn的合理值
如前所述，应该设计一个函数用来输出提示信息和处理输入，这个函数应该返回一个数值sn，以便供给switch语句使用。假设函数名为menu_select,对于sn的输入值，在switch中case语句对应数字1—5，对于不符合要求的输入，提示输入错误并要求重新输入。将该函数与主函数合在一起，编译运行程序，即可检查并验证菜单选择是否正确。
1.2.2功能函数设计分析
1.建立通讯录链表的设计
这里实际上是要求建立一个带头结点的单链表。建立单链表有两种方法，一种称之为头插法，另一种称为尾插法。头插法是每次将新插入的结点插入在链表的表头，而尾插法是将新插入的结点插入在链表的表尾。本次实验用尾插法建立链表的算法设计思想及具体算法实现。
要建立链表，首先要生成结点，因此，尾插法建立链表的算法描述如下：
（1）使链表的头尾指针head、rear指向新生成的头结点（也是尾结点）；
（2）置结束标志为0（假）；
（3）While（结束标志不为真）
{
P指向新生成的结点；
读入一个通讯者数据至新结点的数据域；
将新结点链到尾结点之后；
使尾指针指向新结点；
提示：是否结束建表，读入一个结束标志；
}
（4）尾结点指针域置空值NULL。
2.通讯者信息的插入
链表结点的插入，是要求将一个通讯者数据结点按其编号的次序插入有序通讯录表的相应位置，以保持通讯录表的有序性。插入结点的基本思想是：使用两个指针变量p1和p2分别指向当前刚访问过的结点和下一个待访问的结点，循环顺序查找链表，寻找插入结点的位置，其中p1指向待插入位置的前一个结点。
（1）用p1指向元链表的头结点，p2指向链表的第一个结点；
（2）while(p2 != NULL && p2->data.num < p->data.num)
{
P1=p2;//p1指向刚访问过的结点；
P2=p2->next;//p2指向表的下一个结点；
}
（3）插入新结点。
3.在有序表中查找指定结点
在有序链表中查找指定结点的算法基本思想是：首先输入要查找的通讯者的编号或姓名，从表头顺序访问表中结点。如查找成功，则返回一个指向查找到的通讯者信息的结点；若查找失败，则返回一个空的指针值NULL。
当按编号查找时，如果需要查找的通讯者编号不在表中，则不一定需要循环比较到表尾，因为表是按编号递增有序的；而当按姓名查找时，则要循环比较到表尾，才能确定查不到的情况。
4.通讯者记录的删除
链表上结点的删除是比较简单的，先调用查询函数，查询到要删除的结点，若没有查找到则提示“没有查找到要删除的通讯者”，若查找到根据选择删除结点即可。
5.通讯录链表的输出
通讯录链表的输出只要将表头指针赋给一个指针变量p，然后用p向后扫描，直至表尾，p为空为止。
1.3算法实现
1.菜单选择函数具体算法实现如下：
int menu_select()
{
int sn;
printf(" 通讯录管理系统 \\n");
printf("===============================\\n");
printf(" 1.通讯录链表的建立\\n");
printf(" 2.通讯者链表的插入\\n");
printf(" 3.通讯者链表的查询\\n");
printf(" 4.通讯者链表的删除\\n");
printf(" 5.通讯录链表的输出\\n");
printf(" 0.退出管理系统\\n");
printf("===============================\\n");
printf(" 请 选 择 0--5： ");
for (;;)
{
scanf("%d",&sn);
if (sn<0 || sn>5)
printf("\\n\输入错误，重选0--5: ");
else
break;
}
return sn;
}
2.建立通讯录链表具体算法实现如下：
LinkList CreateList(void)
{
LinkList head=(ListNode *)malloc(sizeof(ListNode));
ListNode *p,*rear;
int flag=0;
rear=head;
while (flag==0)
{
p=(ListNode *)malloc(sizeof(ListNode));
printf("编号(4) 姓名(8) 性别电话(11) 地址(31)\\n");
printf("------------------------------------\\n");
scanf("%s%s%s%s%s",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr);
rear->next=p;
rear=p;
printf("结束建表吗?(1/0):");
scanf("%d",&flag);
}
rear->next=NULL;
return head;
}
3.通讯者信息的插入算法具体实现如下：
void InsertNode(LinkList head,ListNode *p)
{
ListNode *p1,*p2;
p1=head;
p2=p1->next;
while (p2!=NULL && strcmp(p2->data.num,p->data.num)<0)
{
p1=p2;//p1指向刚访问过的结点
p2=p2->next;//p2指向表的下一个结点
}
p1->next=p;//插入p所指向的结点
p->next=p2;//连接表中剩余部分
}
4. 在有序链表中查找指定结点算法具体实现如下：
ListNode * ListFind(LinkList head)
{
ListNode *p;
char num[5];
char name[9];
int xz;
printf("========================\\n");
printf(" 1.按编号查询 \\n");
printf(" 2.按姓名查询 \\n");
printf("========================\\n");
printf(" 请 选 择： ");
p=head->next;//假定通讯录表带头结点
scanf("%d",&xz);
if (xz==1)
{
printf("请输入要查找者的编号：");
scanf("%s",num);
getchar();
while (p&& strcmp(p->data.num,num)<0)
p=p->next;
if (p==NULL||strcmp(p->data.num,num)>0)
p=NULL;//没有查到要查找的通讯者
}
else
if (xz==2)
{
printf("请输入要查找者的姓名：");
scanf("%s",name);
while(p&&strcmp(p->data.name,name)!=0)
p=p->next;
}
return p;
}
5.通讯者记录的删除的算法具体实现如下：
void DelNode(LinkList head)
{
char jx;
ListNode *p,*q;
p=ListFind(head);//调用查找函数
if (p==NULL)
{
printf("没有查到要删除的通讯者!\\n");
return;
}
printf("真的要删除该结点吗?(y/n): ");
scanf("%c",&jx);
if (jx=='y'||jx=='Y')
{
q=head;
while (q!=NULL && q->next!=p)
q=q->next;
q->next=p->next;//删除结点
free(p);//释放被删除的结点空间
printf("通讯者已被删除!\\n");
}
}
6.通讯录链表的输出的算法具体实现如下：
void PrintList(LinkList head)
{
ListNode *p;
p=head->next;//因为带头结点，使指向链表开始结点
printf("编号 姓名 性别 电话 地址\\n");
printf("------------------------------------\\n");
while(p!=NULL)
{
printf("%s%s%s%s%s",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr);
//printf("------------------------------------\\n");
p=p->next;//后移一个结点
}
}
1.4程序代码
源程序如下：
/*****************************/
/*主控菜单处理测试程序main2.c*/
/*****************************/
#include #include #include typedef struct {//通讯录结点类型 char num[5];//编号 char name[9];//姓名 char sex[3];//性别 char phone[13];//电话 char addr[31];//地址 }DataType; typedef struct node{//结点类型定义 DataType data;//结点数据域 struct node * next;//结点指针域 }ListNode; typedef ListNode * LinkList; LinkList head;//定义指向单链表的头指针 ListNode *p;//定义一个指向结点的指针变量 //函数说明 int menu_select();//菜单选择函数 LinkList CreateList(void);//尾插法建立单链表函数 void InsertNode(LinkList head,ListNode *p);//在有序链表中插入结点 ListNode *ListFind(LinkList head);//有序链表上的查找函数 void DelNode(LinkList head);//通讯录链表上结点的删除函数 void PrintList(LinkList head);//通讯录链表的输出函数 //主函数 void main() { for(;;) { switch(menu_select()) { case 1: printf("*********************************\\n"); printf("* 通 讯 录 链 表 的 建 立 *\\n"); printf("*********************************\\n"); head=CreateList(); break; case 2: printf("*********************************\\n"); printf("* 通 讯 者 信 息 的 添 加 *\\n"); printf("*********************************\\n"); printf("编号(4)姓名(8)性别电话(11)地址(31)\\n"); printf("*********************************\\n"); p=(ListNode *)malloc(sizeof(ListNode)); scanf("%s%s%s%s%s",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr); InsertNode(head,p); break; case 3: printf("*********************************\\n"); printf("* 通 讯 录 信 息 的 查 询 *\\n"); printf("*********************************\\n"); p=ListFind(head); if (p!=NULL) { printf("编号 姓 名 性别 电话 地 址\\n"); printf("----------------------------\\n"); printf("%s,%s,%s,%s,%s\\n",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr); printf("----------------------------\\n"); } else printf("没查到要查询的通讯者!\\n"); break; case 4: printf("*********************************\\n"); printf("* 通 讯 录 信 息 的 删 除 *\\n"); printf("*********************************\\n"); DelNode(head); break; case 5: printf("*********************************\\n"); printf("* 通 讯 录 链 表 的 输 出 *\\n"); printf("*********************************\\n"); PrintList(head); break; case 0: printf("\再 见\\n"); return; } } } /*菜单选择函数程序*/ int menu_select() { int sn; printf(" 通讯录管理系统 \\n"); printf("===============================\\n"); printf(" 1.通讯录链表的建立\\n"); printf(" 2.通讯者链表的插入\\n"); printf(" 3.通讯者链表的查询\\n"); printf(" 4.通讯者链表的删除\\n"); printf(" 5.通讯录链表的输出\\n"); printf(" 0.退出管理系统\\n"); printf("===============================\\n"); printf(" 请 选 择 0--5： "); for (;;) { scanf("%d",&sn); if (sn<0 || sn>5) printf("\\n\输入错误，重选0--5: "); else break; } return sn; } /*用尾插法建立通讯录链表函数*/ LinkList CreateList(void) { LinkList head=(ListNode *)malloc(sizeof(ListNode)); ListNode *p,*rear; int flag=0; rear=head; while (flag==0) { p=(ListNode *)malloc(sizeof(ListNode)); printf("编号(4) 姓名(8) 性别电话(11) 地址(31)\\n"); printf("------------------------------------\\n"); scanf("%s%s%s%s%s",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr); rear->next=p; rear=p; printf("结束建表吗?(1/0):"); scanf("%d",&flag); } rear->next=NULL; return head; } /*在通讯链表head中插入结点*/ void InsertNode(LinkList head,ListNode *p) { ListNode *p1,*p2; p1=head; p2=p1->next; while (p2!=NULL && strcmp(p2->data.num,p->data.num)<0) { p1=p2;//p1指向刚访问过的结点 p2=p2->next;//p2指向表的下一个结点 } p1->next=p;//插入p所指向的结点 p->next=p2;//连接表中剩余部分 } /*有序通讯录链表上的查找*/ ListNode * ListFind(LinkList head) { ListNode *p; char num[5]; char name[9]; int xz; printf("========================\\n"); printf(" 1.按编号查询 \\n"); printf(" 2.按姓名查询 \\n"); printf("========================\\n"); printf(" 请 选 择： "); p=head->next;//假定通讯录表带头结点 scanf("%d",&xz); if (xz==1) { printf("请输入要查找者的编号："); scanf("%s",num); getchar(); while (p&& strcmp(p->data.num,num)<0) p=p->next; if (p==NULL||strcmp(p->data.num,num)>0) p=NULL;//没有查到要查找的通讯者 } else if (xz==2) { printf("请输入要查找者的姓名："); scanf("%s",name); while(p&&strcmp(p->data.name,name)!=0) p=p->next; } return p; } /*通讯录链表上的结点删除*/ void DelNode(LinkList head) { char jx; ListNode *p,*q; p=ListFind(head);//调用查找函数 if (p==NULL) { printf("没有查到要删除的通讯者!\\n"); return; } printf("真的要删除该结点吗?(y/n): "); scanf("%c",&jx); if (jx=='y'||jx=='Y') { q=head; while (q!=NULL && q->next!=p) q=q->next; q->next=p->next;//删除结点 free(p);//释放被删除的结点空间 printf("通讯者已被删除!\\n"); } } /*通讯录链表的输出函数*/ void PrintList(LinkList head) { ListNode *p; p=head->next;//因为带头结点，使指向链表开始结点 printf("编号 姓名 性别 电话 地址\\n"); printf("------------------------------------\\n"); while(p!=NULL) { printf("%s,%s,%s,%s,%s",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr); printf("\\n------------------------------------\\n"); p=p->next;//后移一个结点 } } 1.5测试结果 上述源程序编译运行后显示如下菜单，等待用户选择： 选1后按“回车”，显示： 随后系统提示： 输入0继续，输入1退出建立通讯录链表，返回系统主控菜单： 若选择数不在0—5之间，则显示如下提示信息： 选择2实现通讯录链表的插入，插入完成又返回系统主控菜单： 选择3实现通讯录链表的查询，然后根据提示选择“按姓名查询”，完成后又返回系统主控菜单： 选择4实现通讯录链表的删除。删除通讯录信息根据提示选择查找类型，若没有查到要删除的通寻记录系统提示： 查找到系统显示： 完成又返回系统主控菜单： 选择5实现通讯录链表的输出，完成又返回系统主控菜单： 1.6结论分析 通过本章实验的学习，熟悉了使用单链表结构实现链表的应用。对于链表的插入，链表的删除，链表的查询都有了一定的了解。能够熟练掌握有关链表的基本操作。 第二章 赫夫曼编码的应用 2.1设计要求 本章的设计要求是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码进行译码，输出电文字符串。 2.2设计分析 在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已经越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树德分之表示“0”码，指向右子树分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。 假设每种字符在电文中出现次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么∑WiLi恰好为二叉树上带权路径长度。 因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率做权，构造一颗赫夫曼树，次构造过程称为赫夫曼编码。 根据分析，必须实现以下几个功能： （1）赫夫曼树的建立。 （2）赫夫曼编码的生成。 （3）编码文件的译码。 2.3算法实现 要实现赫夫曼树德算法，首先要实现在HT[1.k]中选择parent为0且权值最小的两个根结点的选择算法；另外，还要一个实现统计输入电文字符串中各种字符出现的频率以及字符的种类的算法。假设电文中仅含有大写字母。 1.选择parent为0且权值最小的两个根结点的算法 void selectHT(HuffmanTree T,int k ,int *s1,int *s2){ //在HT[1..k]中选择parent为0且权值最小的两个根结点，其序号分别为s1和s2，//并靠参数待会主调函数 int i,j; int min1 = 32767; for(i = 1;i <= k;i++)//找s1 if(T[i].weight < min1&&T[i].parent == 0){ j = i; min1 = T[i].weight; } *s1 = j; min1 = 32767; for(i = 1;i <= k;i++)//找s2 if(T[i].weight < min1&&T[i].parent == 0&&i != *s1){ j = i; min1 = T[i].weight; } *s2 = j; } 2.统计字符串中字符的种类以及各类字符的个数 int jsq(char *s,int cnt[],char str[]){ //统计各字符串中各种字母的个数以及字符的种类 char * p; int i,j,k; int temp[27]; for(i = 1;i <= 26;i++) temp[i] = 0; for(p = s;*p != '\\0';p++){//统计各种字符个数 if(*p>='A' && *p <= 'Z'){ k = *p - ; temp[k]++; } } j = 0; for(i = 1,j = 0;i <= 26;i++)//统计有多少种字符 if(temp[i] != 0){ j++; str[j] = i + ; //送对应的字母到数组中 cnt[j] = temp[i]; //存入对应字母权值 } return j; } 3.构造构造赫夫曼树 void CreHuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[]){ //构造赫夫曼树HT，cnt中存放每类字符在电文中出现的频率，str存放电文中不同//类的字符 int i,s1,s2; for(i = 1;i <= 2*num -1;i++){ HT[i].lchild = 0; HT[i].rchild = 0; HT[i].parent = 0; HT[i].weight = 0; } for(i = 1;i <= num;i++)//输入num个叶结点的权值 HT[i].weight = cnt[i]; for(i = num + 1;i <= 2*num -1;i++){ //在HT[1...k]中选择parent为0的且权值最小的两个根结点，其序号分别为s1和s2 selectHT(HT,i - 1,&s1,&s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } for(i = 0;i <= num;i++)//输入字符集中的字符 HC[i].ch = str[i]; i = 1; while(i <= num){ printf("字符%c，次数为：%d\\n",HC[i].ch,cnt[i++]); } } 4.赫夫曼编码的算法 void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC){ //根据赫夫曼树HT求赫夫曼编码表HC int c,p,i;//c,p表示HT中孩子和双亲的位置 char cd[n];//临时存放编码串 int start;//指示编码在cd中其实位置 cd[num] = '\\0';//最后一位放上串结束符 for(i = 1;i <= num;i++){ start = num;//初始位置 c = i;//从叶子节点HT[i]开始上溯 while((p = HT[c].parent) > 0) {//知道上溯到HT[c]是树根为止 //若HT[c]是HT[p]的左孩子，则生成0，否则生成代码1 cd[--start] = (HT[p].lchild == c)?'0':'1'; c = p; } strcpy(HC[i].bits,&cd[start]); HC[i].len = num - start; } } 5.建立正文的编码文件 建立编码文件的基本思想是：将要编码的字符创中德字符逐一与预先生成赫夫曼树是保存的字符编码对照表进行比较没找到之后，对该字符的编码写入代码文件，直至所有的字符处理完为止。具体实现算法如下： void HuffmanEncoding(HuffmanTree HT, HuffmanCode HC) { int c, p, i; char cd[n]; int start; cd[num] = '\\0'; for(i = 1; i <= num; i++) { start = num; c = i; while((p = HT[c].parent) > 0) { cd[--start] = (HT[p].lchild == c) ? '0' : '1'; c = p; } strcpy(HC[i].bits, &cd[start]); HC[i].len = num - start; } } void coding(HuffmanCode HC, char *str) { int i,j,q,p; FILE *fp; p=0;//计数换行 fp = fopen("codefile.txt", "w"); printf("输出每个字母的哈弗曼编码：\\n"); while(*str) { for(i = 1; i <= num; i++) if(HC[i].ch == * str) { for(j = 0; j < HC[i].len; j++) fputc(HC[i].bits[j], fp); printf(" "); for(q=0;q printf("%d",HC[i].bits[q]-48); } p++;//输出每个字母的哈弗曼编码 if(p==7) { p=0;printf("\\n"); }//当到达9个时换行 break; } str++; } printf("\\n"); fclose(fp); }6.代码文件的译码 译码的基本思想是：读文件中编码，并于原生成的赫夫曼编码比较，遇到相等时，即取出器对应的字符存入一个新串中。集体算法如下： char * decode(HuffmanCode HC){ //代码文件codefile.txt译码 FILE *fp; char str[254];//假设原文本文件不超过254个字符 char *p; static char cd[n+1]; int i,j,k = 0,cjs; fp = fopen("codefile.txt while(!feof(fp)){ cjs = 0;//一个字符的编码是否读结束 for(i = 0;i < num&&cjs == 0&&!feof(fp);i++){ cd[i] = ' '; cd[i+1] = '\\0';//初始化cd串 cd[i] = fgetc(fp); for(j = 1;j <= num;j++){ if(strcmp(HC[j].bits,cd) == 0){ str[k] = HC[j].ch; k++; cjs = 1; break; } } } } str[k] = '\\0'; p = str; return p; } 2.4程序代码 源程序如下： #include #include #define n 100//叶子结点数 #define m 2*n-1//赫夫曼树中结点总数 typedef struct{ char ch; char bits[9];//存放编码位串 int len;//编码长度 }CodeNode; typedef CodeNode HuffmanCode[n+1]; typedef struct{ int weight;//权值 int lchild,rchild,parent;//左右孩子及双亲指针 }HTNode;//树中结点类型 typedef HTNode HuffmanTree[m+1];//0号单元不用 int num; //建立HuffmanTree的三个函数 void selectHT(HuffmanTree T,int k ,int *s1,int *s2){//在HT[1..K]中选择parent为0且权值最小的两个根结点 int i,j; int min1 = 101; for(i = 1;i <= k;i++) if(T[i].weight < min1&&T[i].parent == 0){ j = i; min1 = T[i].weight; } *s1 = j; min1 = 32767; for(i = 1;i <= k;i++) if(T[i].weight < min1&&T[i].parent == 0&&i != *s1){ j = i; min1 = T[i].weight; } *s2 = j; } int jsq(char *s,int cnt[],char str[]){ //统计各字符串中各种字母的个数以及字符的种类 char * p; int i,j,k; int temp[27]; for(i = 1;i <= 26;i++) temp[i] = 0; for(p = s;*p != '\\0';p++){//统计各种字符个数 if(*p>='A' && *p <= 'Z'){ k = *p - ; temp[k]++; } } j = 0; for(i = 1,j = 0;i <= 26;i++)//统计有多少种字符 if(temp[i] != 0){ j++; str[j] = i + ; //送对应的字母到数组中 cnt[j] = temp[i]; //存入对应字母权值 } return j; } void CreHuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[]){//构造HuffmanTree HT int i,s1,s2; for(i = 1;i <= 2*num -1;i++){ HT[i].lchild = 0; HT[i].rchild = 0; HT[i].parent = 0; HT[i].weight = 0; } for(i = 1;i <= num;i++) HT[i].weight = cnt[i]; for(i = num + 1;i <= 2*num -1;i++){ selectHT(HT,i - 1,&s1,&s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } for(i = 0;i <= num;i++) HC[i].ch = str[i]; i = 1; while(i <= num){ printf("字符%c，次数为：%d\\n",HC[i].ch,cnt[i++]); } } //生成HuffmanCode文件的两个函数 void HuffmanEncoding(HuffmanTree HT, HuffmanCode HC) { int c, p, i; char cd[n]; int start; cd[num] = '\\0'; for(i = 1; i <= num; i++) { start = num; c = i; while((p = HT[c].parent) > 0) { cd[--start] = (HT[p].lchild == c) ? '0' : '1'; c = p; } strcpy(HC[i].bits, &cd[start]); HC[i].len = num - start; } } void coding(HuffmanCode HC, char *str) { int i,j,q,p; FILE *fp; p=0;//计数换行 fp = fopen("codefile.txt", "w"); printf("输出每个字母的哈弗曼编码：\\n"); while(*str) { for(i = 1; i <= num; i++) if(HC[i].ch == * str) { for(j = 0; j < HC[i].len; j++) fputc(HC[i].bits[j], fp); printf(" "); for(q=0;q printf("%d",HC[i].bits[q]-48); } p++;//输出每个字母的哈弗曼编码 if(p==7) { p=0;printf("\\n"); }//当到达9个时换行 break; } str++; } printf("\\n"); fclose(fp); } //电文的译码 char * decode(HuffmanCode HC) { FILE * fp; char str[254]; char * p; static char cd[n + 1]; int i, j, k = 0, cjs; fp = fopen("codefile.txt", "r"); while(!feof(fp)) { cjs = 0; for(i = 0; i < num && cjs == 0 && !feof(fp); i++) { cd[i] = ' '; cd[i + 1] = '\\0'; cd[i] = fgetc(fp); for(j = 1; j <= num; j++) if(strcmp(HC[j].bits, cd) == 0) { str[k] = HC[j].ch; k++; cjs = 1; break; } } } str[k] = '\\0'; p = str; return p; } //测试主控函数 void main(){ char st[254],*s,str[27]; int cn[27]; HuffmanTree HT; HuffmanCode HC; printf("输入需要编码的字符串（假设均为大写字母）：\\n"); gets(st); num = jsq(st,cn,str);//统计字符的种类及各类字符出现的频率 CreHuffmanTree(HT,HC,cn,str);//建立赫夫曼树 HuffmanEncoding(HT,HC);//生成赫夫曼编码 coding(HC,st);//建立电文赫夫曼编码文件 s = decode(HC);//读编码文件译码 printf("译码后的字符串：%s\\n",s);//输出译码后的字符串 printf("字符串长度：%d\\n",strlen(s)); } 2.5测试结果 运行结果如下： 2.6结果分析 本章设计目的主要是对二叉树的遍历及赫夫曼树、赫夫曼编码等概念进行综合练习。以二叉链表作为存储结构，探讨各种非递归的遍历算法以及根结点到任意结点的路径；另外，以一个非常实用的电文编码、译码问题，来加深对赫夫曼树和赫夫曼编码等概念的理解。本次实验在符合要求的基础之上有部分改进，增加了字符个数的统计，此次实验按要求完成。 第三章 交通咨询系统设计（最短路径问题） 3.1设计要求 设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径（里程）或最低花费或最短时间等问题。对于不同咨询要求，可输入城市间的路程或所需时间或所需费用。 3.2设计分析 通过分析可知该设计共分为三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。 1.建立图的存储结构 要实现设计要求，首先要定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点vi的信息。因此，图的邻接矩阵的存储结构定义如下： #definf MVNum 50 //最大定点数 Typedef struct{ VertexType vexs[MVNum];//定点数组，类型假定为char型 Adjmatrix arcs[MVNum] [MVNum];//邻接矩阵，假定为int型 }MGraph; 2.单源最短路径 最短路径问题的提法很多。这里先讨论单源最短路径问题：即已知有向图（带权），是要找出从某个源点S到G中其余各顶点的最短路径。迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸顶点的最短路径算法，称之为迪杰斯特拉算法。 迪杰斯特拉算法可用自然语言描述如下： //初始化S和D，置空最短路径终点集，置最初的最短路径值； S[V1]=TRUE;D[V1]=0;//S集初始时只有源点，源点到源点的最短距离为0； While(S集中顶点数 开始循环，每次求得V1到某个V顶点的最短路径，并加V到S集中； S[V]=TRUE; 更新当前最短路径及距离； } 3.任意一对顶点间最短路径 任意顶点对之间的最短路径问题，是对于给定的有向网络图G=（V,E）,要对G中任意一对顶点有序对“v,w（v和w不重合）”，找出v到w的最短路径。 3.3算法实现 1.建立有向图的存储结构 由于有向图的邻接矩阵是不对称的，所以，只要输入所有有向边及其权值即可，因此建立一个有向图的算法如下： void CreateMGraph(MGraph *G,int n,int e) {//采用邻接矩阵表示法构造有向图G，n、e表示图的当前顶点数和边数 int i,j,k,w; for(i=1;i<=n;i++)//输入顶点信息 G->vexs[i]=(char)i; for(i=1;i<=n;i++) for(j=1;j<=n;j++) G->arcs[i][j]=Maxint;//初始化邻接矩阵 printf("输入%d条边的i（边的起点）,j（边的终点）及w（边的权值）: \\n",e); for(k=1;k<=e;k++){//读入e条边，建立邻接矩阵 scanf("%d,%d,%d",&i,&j,&w); G->arcs[i][j]=w; } printf("有向图的存储结构建立完毕!\\n"); } 2.迪杰斯特拉算法 迪杰斯特拉算法用C语言描述如下： void Dijkstra(MGraph *G,int v1,int n) { //用迪杰斯特拉算法求有向图G的V1顶点到其他顶点V的最短路径P[V]及其权D[v] //设G是有向图的邻接矩阵，若边 //S[V]为真当且仅当V属于S，即已求得从V1到v的最短路径 int D2[MVNum],P2[MVNum]; int v,i,w,min; enum boolean S[MVNum]; for (v=1;v<=n;v++){//初始化S和D S[v]=FALSE;//置空最短路径终点集 D2[v]=G->arcs[v1][v];//置初始的最短路径值 if(D2[v] else P2[v]=0;// V无前驱 } D2[v1]=0;S[v1]=TRUE; for(i=2;i for(w=1;w<=n;w++) if(!S[w]&&D2[w] S[v]=TRUE; for(w=1;w<=n;w++) if(!S[w]&&(D2[v]+G->arcs[v][w] P2[w]=v; } } printf("路径长度 路径\\n"); for(i=1;i<=n;i++){ printf("%5d",D2[i]); printf("%5d",i); v=P2[i]; while(v!=0){ printf("<-%d",v); v=P2[v]; } printf("\\n"); } } 3.弗洛伊德算法 弗洛伊德算法用C语言描述如下： void Floyd(MGraph *G,int n) { int i,j,k,v,w; for(i=1;i<=n;i++)//设置路径长度D和路径path初值 for(j=1;j<=n;j++) { if(G->arcs[i][j]!=Maxint) P[i][j]=j;//j是i的后继 else P[i][j]=0; D[i][j]=G->arcs[i][j]; } for(k=1;k<=n;k++) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(D[i][k]+D[k][j] P[i][j]=P[i][k]; printf("dij=%d,pij=%d\\n",D[i][j],P[i][j]); } } } } 3.4程序代码 源程序如下： #include #include #define MVNum 100 #define Maxint 32767 enum boolean{FALSE,TRUE}; typedef char VertexType; typedef int Adjmatrix; typedef struct{ VertexType vexs[MVNum]; Adjmatrix arcs[MVNum][MVNum]; }MGraph; int D1[MVNum],P1[MVNum]; int D[MVNum][MVNum],P[MVNum][MVNum]; void CreateMGraph(MGraph *G,int n,int e); void Dijkstra(MGraph *G,int v1,int n); void Floyd(MGraph *G,int n); void main() { MGraph *G; int m,n,e,v,w,k; int xz=1; G=(MGraph *)malloc(sizeof(MGraph)); printf("输入图中顶点个数和边数n，e(如7，10): "); scanf("%d,%d",&n,&e); CreateMGraph(G,n,e); while(xz!=0){ printf("******求城市之间的最短路径******\\n"); printf("============================================\\n"); printf("1.求一个城市到所有城市的最短路径\\n"); printf("2.求任意的两个城市之间的最短路径\\n"); printf("============================================\\n"); printf("请选择: 1 或 2,选择 0 退出: "); scanf("%d",&xz); if(xz==2){ Floyd(G,n); printf("输入源点(或称起点)和终点：v,w: "); scanf("%d,%d",&v,&w); k=P[v][w]; if(k==0) printf("顶点%d 到 %d 无路径!\\n",v,w); else { printf("从顶点%d到%d的最短路径是: %d",v,w,v); while(k!=w){ printf("->%d",k); k=P[k][w]; } printf("->%d",w); printf("路径长度: %d\\n",D[v][w]); } } else if(xz==1){ printf("求单源路径,输入源点 v（如1）: "); scanf("%d",&v); Dijkstra(G,v,n); } } printf("结束求最短路径,再见! \\n"); } void CreateMGraph(MGraph *G,int n,int e) {//采用邻接矩阵表示法构造有向图G，n、e表示图的当前顶点数和边数 int i,j,k,w; for(i=1;i<=n;i++)//输入顶点信息 G->vexs[i]=(char)i; for(i=1;i<=n;i++) for(j=1;j<=n;j++) G->arcs[i][j]=Maxint;//初始化邻接矩阵 printf("输入%d条边的i（边的起点）,j（边的终点）及w（边的权值）: \\n",e); for(k=1;k<=e;k++){//读入e条边，建立邻接矩阵 scanf("%d,%d,%d",&i,&j,&w); G->arcs[i][j]=w; } printf("有向图的存储结构建立完毕!\\n"); } void Dijkstra(MGraph *G,int v1,int n) { //用迪杰斯特拉算法求有向图G的V1顶点到其他顶点V的最短路径P[V]及其权D[v] //设G是有向图的邻接矩阵，若边 //S[V]为真当且仅当V属于S，即已求得从V1到v的最短路径 int D2[MVNum],P2[MVNum]; int v,i,w,min; enum boolean S[MVNum]; for (v=1;v<=n;v++){//初始化S和D S[v]=FALSE;//置空最短路径终点集 D2[v]=G->arcs[v1][v];//置初始的最短路径值 if(D2[v] else P2[v]=0;// V无前驱 } D2[v1]=0;S[v1]=TRUE; for(i=2;i for(w=1;w<=n;w++) if(!S[w]&&D2[w] S[v]=TRUE; for(w=1;w<=n;w++) if(!S[w]&&(D2[v]+G->arcs[v][w] P2[w]=v; } } printf("路径长度 路径\\n"); for(i=1;i<=n;i++){ printf("%5d",D2[i]); printf("%5d",i); v=P2[i]; while(v!=0){ printf("<-%d",v); v=P2[v]; } printf("\\n"); } } void Floyd(MGraph *G,int n) { int i,j,k,v,w; for(i=1;i<=n;i++)//设置路径长度D和路径path初值 for(j=1;j<=n;j++) { if(G->arcs[i][j]!=Maxint) P[i][j]=j;//j是i的后继 else P[i][j]=0; D[i][j]=G->arcs[i][j]; } for(k=1;k<=n;k++) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(D[i][k]+D[k][j] P[i][j]=P[i][k]; printf("dij=%d,pij=%d\\n",D[i][j],P[i][j]); } } } } 3.5测试结果 若编译运行主控函数，系统会显示提示： 输入顶点和边数之后，系统又提示输入边及权值： 输入完成后系统会显示： 系统紧接着显示如下菜单： 选择1后程序执行求单源路径的迪杰斯特拉算法，求得结果显示如下： 紧接着菜单又会显示如下菜单： 在选择2后，程序调用弗洛伊德算法，并提示： 显示结果为： 有显示如下菜单： 输入0后系统显示： 3.6结论分析 本章设计主要是针对图的存储结构以及最短路径问题进行综合练习。求最短路径部分是以邻接矩阵作为存储结构，其中用到两个重要算法，一个是迪杰斯特拉算法，另一个是弗洛伊德算法，本次实验基本完成任务。
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
