数据结构课程设计.doc

数据结构课程设计【题目一】约瑟夫环【问题描述】约瑟夫（Joseph）问题的一种描述是：编号为1，2，n的个人按顺时针方向围坐一圈，没人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。【基本要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。【测试数据】M的初值为20；n=7，7个人的密码一次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序应为6，1，4，7，2，3，5）。【程序分析】一、需求分析1本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（既n个人的编号和密码）初始密码和每个人的密码为120，人数为17，先输入初始密码m，再输入人数n，接下来输入n个正整数，数与数之间用逗号隔开，作为这n个人的密码。 2演示程序以用户和计算机的对话方式执行，即在计算机终端上显示提示信息之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。 3程序执行的命令包括： 1）构造单向循环链表；2）提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。4测试数据 m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序为6，1，4，7，2，3，5）。 二、概要设计1单向循环链表的抽象数据类型定义为： ADT List 数据对象：D=ai | ai正整数，I=1，2，.，n,n0 数据关系：R1=< ai-1，ai > |，ai-1，aiD,I=1，2，.，n 基本操作： InitList(&L)操作结果：构造一个最大长度ms内容为空的有序表L。ClearList(&L)初始条件：线性表L已经存在。操作结果：将L重置为空表。EmptyList(L)初始条件：线性表L已经存在。操作结果：若L为空表返回TRUE，否则返回FALSE。ListLength(L)初始条件：线性表L已经存在。操作结果：返回L中数据元素个数。GetElem(L, pos, &e)初始条件：线性表L已经存在，1iListLength(L)。操作结果：用e返回L中第i个数据元素的值。LocateElem(L, e)初始条件：线性表L已经存在。操作结果：返回L中第1个与e相同的元素的位序。若不存在返回0。ListInsert (L, i, e)初始条件：线性表L已经存在。操作结果：在L中的第i个元素的位置之前插入新元素 e,L的长度加1。ListDelete(L, pos, e)初始条件：线性表L已经存在，1iListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ListTraverse(L)初始条件：线性表L已经存在。操作结果：依次对L的每个数据元素进行访问。ADT SqList本程序包含以下模块：（1）主程序模块：其中又包括建立线性表和模拟约瑟夫环处理两大过程void main() 初始化； 输入数据； 执行功能；显示结果；（2）线性表模块：实现线性表的抽象数据类型（3）元素结构单元模块：定义线性表每个元素的结构（2）各功能模块实现顺序表的各项功能。各模块的调用关系：主程序 各功能模块三、详细设计#include #include typedef struct data /定义一个结构体data int num; /用于存放人的序号 int val; /用于存放密码 typedata; typedef struct node /定义一个结构体（结点），其中包含一个数据域和一个指针域 typedata data; /结构体的嵌套 struct node *next; listnode; typedef listnode *linklist; linklist head; void main() / 进入主函数 int n,i,b,m,j; linklist head=(listnode *)malloc(sizeof(listnode); /申请一个空间 listnode *p,*q; /定义两个可以指向结点的指针 printf(输入总人数：); scanf(%d,&n); q=head; /用指针q指向头结点 for(j=1;jnext=(listnode *)malloc(sizeof(listnode); /将头结点的next域指向刚生成的一个结点 q=q-next; q-data.val=b; /输入密码 q-data.num=j; /输入序号 q-next=head-next; /将尾结点的next域指向第一个结点，构成循环链表 printf(请任意输入一个数m：); scanf(%d,&m); if(mnext; i+; p=q-next; /p指向输出结点 q-next=p-next; /将输出结点的前结点的next域指向输出结点的后结点 printf(号码:%dt密码:%dn,p-data.num,p-data.val); /输出 m=p-data.val; /取得输出结点的密码 free(p); while(q-next!=q); /剩最后一个结点时结束 printf(号码:%dt密码:%dn,q-data.num,q-data.val); /最后一个结点 free(head); /释放头结点 free(q); /释放最后一个结点 printf(约瑟夫环结束n); /程序结束四、调试分析：1、调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析 ：调试时没有运行结果，后来发现没有在主程序里加上getch（）函数，加上后正确。m 的初值(上限值)为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，m值为6结果为：6，1，4，7，2，3，5。 2、算法的时空分析 ：在init（）中共循环了n次。在约瑟夫函数中最坏的情况下要n次，所以时间复杂度为0（n）改进方法：我认为要使用双向循环链表可以更好的降低事件复杂度，而循环链表就能很好的节省空间。五、测试结果【题目二】Huffman编/译码器【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的通道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。【基本要求】一个完整的系统应具有以下功能：（1） I:初始化。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2） E:编码。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3） D:译码。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4） P：印代码文件。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。（5） T：印哈夫曼树。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件CodePrin中。【数据测试】（1）利用下面的数据调试程序：已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05，0.29，0.07,0.08,0.14,0.23,0.03,0.11。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161【程序分析】一、需求分析 1 本演示程序中，利用数组存储结构存储哈夫曼数数据（即字符使用频度），先输入总字符个数为，再输入字符使用频度，数与数之间用空格或逗号隔开。 2 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示提示信息之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。 3 程序执行的命令包括： 1)构造哈夫曼树；2)提供用户从键盘输入哈夫曼树的必要数据；3) 对哈夫曼树进行编译，并显示出哈夫曼编码。二、概要设计 1树的抽象数据类型定义为：1、树节点的抽象数据结构：template class TreeNode public: TreeNode(const T&);/拷贝构造函数 virtual TreeNode(); /析构函数 bool isLeaf(); /如果结点是叶，返回true T Value(); /返回结点的值 TreeNode* LeftMostChild(); /返回第一个左孩子 TreeNode* RightSibling(); /返回右兄弟 void setValue(T&); /设置结点的值 void setChild(TreeNode* pointer);/设置左子结点 void setSibling(TreeNode* pointer);/设置右兄弟 void InsertFirst(TreeNode* node);/以第一个左子结点身份插入结点 void InsertNext(TreeNode* node);/以右兄弟的身份插入结点;2、树/森林的抽象数据结构：template class Tree public: Tree(); /构造函数 virtual Tree(); /析构函数 TreeNode* getRoot();/返回树中的根结点 void CreateRoot(const T& rootValue);/创建树中的根结点，使根结点元素的值为rootValue bool isEmpty();/判断是否为空树，如果是则返回true TreeNode* Parent(TreeNode* current);/返回current结点的父结点 TreeNode* PrevSibling(TreeNode* current);/返回current结点的前一个邻居结点 void DeleteSubTree(TreeNode* subroot);/删除以subroot为根的子树的所有结点 void RootFirstTraverse(TreeNode* root);/先根深度优先周游树 void RootLastTraverse(TreeNode* root);/后根深度优先周游树 void WidthTraverse(TreeNode* root);/宽度优先周游树;本程序包含以下模块：（1）主程序模块：其中又包括建立哈夫曼树和哈夫曼编码的编译两大过程void main() 初始化； 输入数据； 执行功能；显示结果；（2）哈夫曼树模块：实现树的抽象数据类型（3）元素结构单元模块：定义哈夫曼树每个元素的结构（2）各功能模块实现哈夫曼树的的各项功能。各模块的调用关系：主程序 各功能模块三、详细设计#include #include #include #include #include typedef structfloat weight; /结点权值unsigned int parent,lchild,rchild; /结点的父指针，左右孩子指针HTNode,*HuffmanTree; /动态分配数组存储哈夫曼树typedef char *HuffmanCode; /动态分配数组存储哈夫曼编码表void CreateHuffmanTree(HuffmanTree &,float*,int ); /生成哈夫曼树void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); /对哈夫曼树进行编码void PrintHuffmanCode(HuffmanCode,float*,int); /显示哈夫曼编码void Select(HuffmanTree,int,int&,int&); /在数组中寻找权值最小的两个结点void main()HuffmanTree HT; /哈夫曼树HTHuffmanCode HC; /哈夫曼编码表HCint n,i; /n是哈夫曼树叶子结点数float *w; /w存放叶子结点权值char j=y;while(j!=N&j!=n)printf(请输入字符数目:);scanf(%d,&n); /输入字符数目if(n=1) printf(该数不合理!n);continue;w=(float*)malloc(n*sizeof(unsigned int); /开辟空间存放权值printf(请输入各字符出现的次数/权值:n);for(i=0;in;i+) scanf(%f,&wi); /输入各字符出现的次数/权值CreateHuffmanTree(HT,w,n); /生成哈夫曼树HuffmanCoding(HT,HC,n); /进行哈夫曼编码PrintHuffmanCode(HC,w,n); /显示哈夫曼编码printf(哈夫曼树构造完毕!);scanf( %c,&j);void CreateHuffmanTree(HuffmanTree &HT,float *w,int n)/w存放n个结点的权值，将构造一棵哈夫曼树HTint i,m;int s1,s2;HuffmanTree p;if(n=1) return;m=2*n-1; /n个叶子结点的哈夫曼树，有2*n-1个结点HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /开辟2*n各结点空间for(p=HT+1,i=1;iweight=*w;p-parent=0;p-lchild=0;p-rchild=0;for(;iweight=0;p-parent=0;p-lchild=0;p-rchild=0;for(i=n+1;i=m;+i) /建哈夫曼树Select(HT,i-1,s1,s2); /从HT1.i-1中选择parent为0且weight最小的两个结点，其序号分别为s1和s2HTs1.parent=i; HTs2.parent=i; /修改s1和s2结点的父指针parentHTi.lchild=s1; HTi.rchild=s2; /修改i结点的左右孩子指针HTi.weight=HTs1.weight+HTs2.weight; /修改权值void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)/将有n个叶子结点的哈夫曼树HT进行编码， 所编的码存放在HC中 /方法是从叶子到根逆向求每个叶子结点的哈夫曼编码int i,c,f,start;char *cd;HC=(HuffmanCode)malloc(n+1)*sizeof(char *); /分配n个编码的头指针向量cd=(char *)malloc(n*sizeof(char); /开辟一个求编码的工作空间cdn-1=0; /编码结束符for(i=1;i=n;+i) /逐个地求哈夫曼编码start=n-1; /编码结束位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /从叶子到根逆向求编码if(HTf.lchild=c) cd-start=0; /若是左孩子编为0else cd-start=1; /若是右孩子编为1 HCi=(char *)malloc(n-start)*sizeof(char); /为第i个编码分配空间strcpy(HCi,&cds