数据结构实验报告.doc

数据结构实验报告 数据结构实验报告 实验一：约瑟夫环一、 上机实验的问题和要求：问题描述：编号是1,2,n(n0)的n个人按照顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值m，从某个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。令n最大值取30。设计一个程序来求出出列顺序，并输出结果。基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。测试数据：n为7，m的初值为20，密码：3、1、7、2、4、8、4，正确的结果应为：6、1、4、7、2、3、5。二、 程序设计的基本思想，原理和算法描述： 本程序包含了三个模块：主程序模块、构造链表并输入每个人信息模块和释放结点模块。ABC首先，要先定义一个线性表的单链表存储结构，利用构造一个空的线性链表，将题目所给数据用指针实现依次输入。并将表中最后一个结点的指针指向头结点以实现循环链表。如图所示：若成功构造空链表，则初始化每个人的相关信息。根据题目的描述，需要对该循环链表的对象进行循环查找直到第m个人，此人报完自己的密码后，应该出列，所以需要构造删除链表元素的函数ListDelete_L(LinkList L,int key,int n)。要注意，应该先将此人的编号输出，将他的密码赋给报数，然后再将次数后面的指针依次向前移动一个位置，并将新的最后一个结点指针指向头结点，再释放该指针，完成该元素的删除。三、 源程序及注释： #include#includetypedef struct LNode /结点类型int password,num; /分别指示元素的密码和编号struct LNode *next;LNode,*LinkList;LinkList creatList_L(int n) /构造一个新的线性链表LinkList p,head,q;int i,key;if(!(head=(LinkList)malloc(sizeof(LNode) printf(error);p=head;for(i=1;inum=i; p-password=key; q-next=p;p-next=head-next;free(head);head=p-next;return(head);void ListDelete_L(LinkList L,int key,int n) /构造一个删除链表元素的函数LinkList p,s;int j;while(n0) p=L;for(j=1;jnext; /将找到的元素以后的每一个元素向前移动一个位置key=p-password; /将找到的元素的密码作为下一次循环的报数值printf(%dn,p-num); /将找到的元素输出s-next=p-next;L=p-next;free(p); /释放找到元素的结点，完成删除n-; /循环人数减一 void main() /主函数模块LinkList s;int n,m;printf(input the total people N and the limit number M:);/M为第一个报数值scanf(%d,%d,&n,&m);printf(input the keys:n);s=creatList_L(n); /调用构造新链表的函数printf(the result is:n);ListDelete_L(s,m,n); /调用删除链表元素的函数getch();四、 运行输出结果：运行结果如下截图所示五、 调试和运行程序过程中产生的问题及采取的措施： 对于本实验，线性链表的构造以及各元素相关值的输入相对比较简单，主要要考虑怎么样去删除已经报过数的元素。特别是当m的初值为1时，情况比较特殊，容易出错。还有各个指针的变化也比较容易因为混乱而出错。所以，在调试过程中，可以利用Break/Watch的功能设置Watch进行查看更方便。 六、 对算法的程序的讨论，分析，改进设想： 对于以上的算法，能基本完成约瑟夫环的计算，但还需要对m的初值为1时的情况进行进一步的优化。另外，对于被删除掉的元素，可以再建立一个数组将其一一保存起来，可以有利于在此算法要求上的进一步拓展，例如，可以回调在第几次被删除的元素，再进行插入操作等等。七、 对实验方式、组织、设备、题目的意见和建议： 实验二：用顺序栈计算表达式一、 上机实验的问题和要求：问题描述：利用栈的基本操作实现一个算术表达式的求值的程序。基本要求：（1） 定义栈的顺序存取结构。（2） 分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。（3） 定义一个函数用来计算表达式结果，并且可以显示表达式的后缀表示。（4） 设计一个测试主函数进行测试。二、 程序设计的基本思想，原理和算法描述：栈是限定仅在表尾（栈顶）进行插入或删除的线性表，它是后进先出的线性表。在初始化设空栈时要注意不应该限定空栈的最大容量，因为栈在使用过程中所需最大空间是无法估计的，只需要先为栈分配一个基本容量即可。对于用顺序栈来计算表达式，首先要遵守算术四则运算的规则，也就是算符之间的优先关系。对于各个小功能模块用子程序函数实现再在主函数里面一一调用。对于本实验，可按照以下步骤进行实现：从键盘输入表达式，分析该表达式是否合法：（1）是数字，则判断该数字的合法性。若合法，则将数据压入到堆栈段中；（2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值；（3）若是其他字符，则返回错误信息。若上述处理过程中没有发现错误，则认为该表达式合法，可以对其进行以后的操作。三、 源程序及注释：#include#include#include#includetypedef struct char fun; int grade;Functor; /定义算符栈结构体Functor FUNCTOR20;float NUM20; /定义算符栈和对象栈char ch100;int sub=0; /存放输入的字符串float Char_To_Num() /将表示数据的字符串转化为数据int flag=0, i=-1;float value=0.0;while(chsub=48 & chsub=2) /判断对象栈中元素个数 switch(FUNCTORj-1.fun) case *: NUMi-2=NUMi-2*NUMi-1; break; case /: NUMi-2=NUMi-2/NUMi-1; break; case %: NUMi-2=(int)(NUMi-2)%(int)(NUMi-1); break; case +: NUMi-2=NUMi-2+NUMi-1; break; case -: NUMi-2=NUMi-2-NUMi-1; break; NUMi-1=0; FUNCTORj-1.fun=0; else Error(); /若对象栈只剩下一个数据，则输入的表达式有误floatChar_Transform() int i=0, j=0, grade, flag=0;while( chsub!= | j!=0 ) if(chsub=) /输入的字符是否取完 Calculate(i, j); i-; j-; else if(chsub=48 & chsub=40 & chsubFUNCTORj-1.grade) /第一个或级别比栈内算符高的进栈 FUNCTORj.fun=chsub; FUNCTORj.grade=In_Grade(chsub); if(j=0 & FUNCTORj.fun=-) flag=1; j+; sub+; else Calculate(i, j); i-; j-; else Error(); /表达式中有非算术字符，则表达式有误return NUMi-1;void main() float result; clrscr();printf(*n); printf(input the expression and over with =:n); printf(*n); gets(ch); result=Char_Transform(); printf(%s%.2fn, ch, result); printf(npress any key to quit); getch();四、 运行输出结果：五、 调试和运行程序过程中产生的问题及采取的措施：对于本实验，过程比较复杂。首先对栈的顺序存储定义以及顺序栈的一系列基本操作，只要参考教科书都还可以比较好操作。之后对于利用顺序栈计算表达式，则需要在调试过程中不断修正。因为为了方便输入，把输入放在了字符数组中，而进行计算的是整数，首先就必须要将数据的字符串转化为数据，（字符0-9对应的ASCII值分别为48-57）。另外对于四则运算必须要考虑各符号之间的优先权。并且通过调试之后发现，一定要分别定义算符在栈内和栈外的优先级别。另外，在程序中可以看到有很多处判断语句，例如，判断是否在输入数据中存在负数，若是，则需要先进行变换。若缺少这样的判断，则有可能会导致运行结果错误。这些问题都是能在调试过程中可以逐一发现的。另外，怎么样对栈在运行过程中的处理也需要经过多次调试。对元素的进栈以及运算完之后的出栈处理都很容易出错。例如，对完成运算之后，要“NUMi-1=0; FUNCTORj-1.fun=0;”，否则程序运行错误。 六、 对算法的程序的讨论，分析，改进设想：对于比较简单的四则运算，我们一般就只需要考虑整型数据之间的运算。如果要能实现对浮点型数据的同样处理，则要考虑对“.”处理，虽然程序更加复杂，但算法的适用性得到很大的提高。另外，对于输入数据的处理，一般我们都采用scanf或其他单个输入语句，在这里使用字符型数组来存储输入数据。虽然要在运算之前对数据进行转换，但更有利于使用者的数据输入。另外还可以在算符在栈内外级别定义中加入“平方”的级别，在运算函数中加入平方的算法，就还可以对输入数据进行平方的处理。七、 对实验方式、组织、设备、题目的意见和建议：因为栈是一种重要的线性结构，在很多场合的编程问题中都可以利用到栈的一些基本操作。但是，当算法比较复杂的时候，对栈的掌握程度也要求很高。例如，如果一个程序中要到两个栈，为了不发生上溢错误就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？怎么样将两个栈进行联接等等。这样一些类似的问题我们都可以通过实验，在调试运行过程进行探索和解决相关的疑问。 实验三：串的基本操作一、 上机实验的问题和要求：问题描述：采用顺序存储结构，完成串的联接和子串定位操作。基本要求：（1） 定义串的顺序存取结构。（2） 分别定义串的联接和子串定位的基本操作。（3） 设计一个测试主函数进行测试。测试数据：有两个串，分别为s1=ababbaabaa，s2=aab。输出串s1与串s2联接的结果，以及在串s1中对串s2定位的结果。二、程序设计的基本思想，原理和算法描述：串是由零个或多个字符组成的有限序列。串的顺序存储结构类似线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。关于串的基本操作，串的联结和子串的定位可以分别使用函数Concat(&T,S1,S2)（用T返回由S1和S2联结而成的新串）和Index（S，T，pos）(函数返回在主串S中第pos个字符之后跟串T相同的子串第一次出现的位置)实现两项功能。该实验的设计思想是：因为对于串的联接需要考虑到串的长度，所以需要先计算出串的长度再能利用Concat函数进行串联接。开始联接之前要先对两个子串的长度进行判断，而新串的产生也因子串长度的不同有三种情况：（1）两子串（S1、S2）长度和=已定义的最大串长，则只需要分别对两个子串进行“串值复制”即可；（2）若长度和大于最大串长，而第一个子串S1长度小于最大串长，则将第二个子串S2的一部分截断；（3）若第一个子串的长度已经超过最大串长，则需要将第一个子串截断。之后，再进行S2在S1中的位置定位处理：从S1的第pos个字符开始和S2的第一个字符开始比较。若相等，则继续逐个比较后续字符，否则从主串字符的下一个字符起重新和S2的字符比较，直到S2中的每一个字符依次和S2中的一个连续的字符相等为止，否则返回匹配失败。三、 源程序及注释 #include#define MAX 255 /定义最大串长typedef unsigned char strMAX;/定义数组类型strlen(char strMAX) /构造计算数组长度的函数int m;m=0;while(strm!=0) m+;return m; void Concat(char TMAX,char S1MAX,char S2MAX) /构造联接函数，用T返回新串int i,j,a,b; a=strlen (S1); b=strlen(S2); if (a+b=MAX) /两个子串都未被截断 for(i=0; ia; i+)Ti=S1i; for (j=a,i=0; ib,ja+b; i+,j+)Tj=S2i;else if (aMAX) /串S2被截断 for(i=0; ia; i+)Ti=S1i;for (j=a,i=0; iMAX-a,j=MAX; i+,j+)Tj=S2i;else /仅取串S1的部分for(i=0; i=MAX; i+) Ti=S1i; printf(The connective string is %s,T); int Index(char S1MAX,char S2MAX,int pos) /构造子串定位函数，并返回子串的位置 int a,b,c,i,j; i=pos-1; j=0; a=strlen(S1); b=strlen(S2); while (ia&jb) if(S1i=S2j ) i+; j+;/继续比较以后的字符 if (j=b) c=i-b+1;printf(The result of index is %d,c); /返回子串的位置 else i=i-j+1; j=0; /指针后退重新开始匹配 if (i=a & jb) printf(Cant find the substring from the postion %d ,pos); /无法从主串指定的位置找到子串 main() char S1MAX,S2MAX,TMAX; int pos; clrscr(); printf(please input the S1:); gets(S1); printf(please input the S2:); gets(S2); Concat(T,S1,S2); printf(nplease input the position of Index:); scanf(%d,&pos); Index(S1,S2,pos); getch(); 四、 运行输出结果： 五、 调试和运行程序过程中产生的问题及采取的措施：本次实验主要考查的是对于两个串之间的一些基本操作。首先要考虑的是串的长度计算问题。按照教科书上指导，我们可以预先把字符串长度存放在第0个单元里，但是事实证明，这样使得输入操作很不方便，也不利于长字符的输入。因此，我们构造了一个字符串长度的计算函数，这样使得程序更具灵活性。对于两个子串的联接问题，调试过程中出现问题比较少，只要对于两个子串的长度的不同情况逐一分析即可。主要针对子串的定位问题，值得一提的是，我们在键盘输入的“position of Index”是大家平时习惯的从1开始的数数，所以，在编程时，我们要从主串的pos-1处开始匹配子串。否则会导致运行结果错误。另外，我们还要针对无法在主串中找到和子串相匹配的字符的情况进 行分析处理。六、 对算法的程序的讨论，分析，改进设想以及对实验的建议：本实验考查了对串的一些基本操作。因为串属于有限序列，而且在串的操作中，通常以“串的整体”作为操作对象，相比于线性表中以“单个元素”作为操作对象要略微简单。对于串的联接，不管用怎样的函数进行实现，其实现的思路就是按照上述三种情况进行。子串的操作则可以进行一系列的拓展：用SubString（&Sub，S，pos,len）函数返回找到的子串；对于子串的定位可以先建立一个比较函数，然后再在定位函数里面调用该比较函数以增加整个算法的灵活性。实验还可以考查关于串的顺序存储结构、堆分配存储表示和块链存储结构之间的差异以及两种结构在进行功能实现时的复杂度。 实验四：二叉树的基本操作一、 上机实验的问题和要求：问题描述：采用二叉链表作为存储结构，完成图1的二叉树的建立和遍历操作。基本要求：（1）基于先序遍历的构造算法。输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。（2）利用中序顺序遍历所建的二叉树，将遍历结果打印输出。测试数据 ： 图1. 二叉树二、 程序设计的基本思想，原理和算法描述：lchilddatarchlid二叉树的特点是每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，其次序不能颠倒。对于二叉树的链式存储结构，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包括3个域：数据域和左、右指针域，如图： 遍历二叉树，即按照某条搜索路径巡访树中的每一个结点，使得每个结点均被访问一次，而且仅被访问一次。若限定先左后右，遍历就只有三种情况：先（根）序遍历，中（根）序遍历、后（根）序遍历。而对于各种遍历的实现，可以采用递归算法，也可以采用非递归对栈进行处理的算法。 在本次实验中，二叉树的链表建立和数据的初始化可以用构造函数BinTree CreateBinTree()实现。在输入数据之前应该为结点开辟空间，开辟成功，才能进行后面的操作，依次构造根结点，左子树和右子树。对于中序遍历，本次实验采用递归算法，构造BinTree InOrder(BinTree T)函数。三、 源程序及注释： #include#includechar ch20; /定义一个存储输入数据的数组int i=0;typedef struct BiTNode /二叉树的二叉链表存储表示 char data; /数据类型 struct BiTNode *lchild; /左右孩子指针 struct BiTNode *rchild;BiTNode, *BinTree;BinTree T1; /定义全局变量BinTree CreateBinTree() /按照先序序列建立二叉树 BinTree T; char c; c=chi; i+; if(c=#) T=NULL; /用#代替空格表示虚结点更有利于输入和检查输入 else T=(BiTNode*)malloc(sizeof(BiTNode); /为结点开辟空间 T-data=c; /从存放输入数据的数组中取出第一个数据生成根节点 T-lchild=CreateBinTree(); /构造左子树 T-rchild=CreateBinTree(); /构造右子树 return(T); / 返回指针T BinTree InOrder(BinTree T) /中序遍历的二叉树的递归算法 if(T) if(InOrder(T-lchild) printf(%c,T-data); if( InOrder(T-rchild) return (1); return(0); void main() BinTree T;T=(BinTree)malloc(sizeof(BiTNode);clrscr(); printf(Input the char in preorder:); gets(ch);T1=CreateBinTree(T);printf(nThe inorder is:);InOrder(T1);getch();四、 运行输出结果： 五、 调试和运行程序过程中产生的问题及采取的措施：本实验的程序虽然比较短，但在调试过程中体现的问题却不少。首先，在对二叉树的二叉链表进行先序次序输入时，不同的输入函数有不同的运行效果。如果采用scanf（&ch）或是getchar()等单个字符输入函数，可以不用在函数之前定义数组以暂时存储输入数据，可以直接进行复制给各个孩子。但是输入操作起来比较麻烦。相对比，用gets()函数一次性输入实验数据方便的多。另外在定义各指针时，一定要注意指针类型的正确性。在分别构造左子树和右子树时，要返回指针T，否则在构造完左子树之后，指针不回到相对应的右子树位置，则输入数据之后会发生错误。在中序遍历算法中，也可以只要判断二叉树是否为空就可。若不为空，则可以直接递归调用中序遍历左子树函数，输出数据，中序遍历右子树函数，不用再进行判断和返回值。加上判断，只是可以增强算法的稳定性。在主函数中，因为要调用到BinTree CreateBinTree()函数，所以要事先定义一个同类型的全局变量二叉树指针。另外，如果不再一次为T开辟空间，程序编译时会出现警告：T可能在主函数定义之前就被使用了。六、 对算法的程序的讨论，分析，改进设想：本次实验主要考查的是基于其链表存储结构是一些操作，主要宗旨就是递归算法。无论是建立二叉树链表还是对二叉树的遍历都可以通过遍历很方便的进行实现。对于二叉树链表的建立主要要考虑到指针的变化情况，二叉树的遍历的递归过程则相对要复杂一些。另外，还可以根据递归算法过程中递归工作栈的状态获得非递归算法：将根指针入栈，若栈顶指针非空，则遍历左子树，即指向左子树的指针入栈；若栈顶指针为空，则应退至上一层，若是从左子树返回则访问当前层的根结点；若从右子树返回，则表明当前层的遍历结束，应继续退栈。对于运行结果输出的改进，本次实验中虽然采用#代替空格键使虚结点更明显，但还可以考虑在输出的时候能用可以识别的其他字符代替虚结点输出，那样，对于实验二叉树的具体结构也更加明朗。七、 对实验方式、组织、设备、题目的意见和建议：“遍历”是二叉树的各种操作的基础，我们可以尝试在遍历过程中对结点进行各种操作，例如：对于一棵已知树求结点的双亲，求结点的孩子结点，判定结点所在层次等等。反之，也可以在遍历过程中生成结点，建立二叉树的不同的存储结构，以及比较各存储结构实现相同功能的复杂度。也还可以考查其他不同次序的输入和遍历操作。 实验五：排序算法设计和比较一、 上机实验的问题和要求：问题描述：利用直接插入排序、冒泡排序、快速排序对数列进行排序。基本要求：（1） 能随机生成30个值为0到100的数。（2） 用于排序的输入数列可以是要求（1）中随机生成的，也可以是键盘输入。（3） 输出结果为利用三种方法排序后的结果，并能显示三种算法时间、空间性能参数值。二、 程序设计的基本思想，原理和算法描述：排序是将一个数据元素的任意序列重新排列成一个按关键字有序的序列。 排序方法主要分为内部排序和外部排序，一般主要考虑内部排序。通常，排序过程需要进行两种基本操作：比较两个关键字的大小；将记录从一个位置移动到另一个位置。前一个操作，对于多数排序方法来说都是必要的，后一个操作就可以因不同的记录存储方式而不同。本次实验考查比较常见的三种排序：直接插入排序、冒泡排序和快速排序法。直接插入排序简单，即先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成非递减序列为止。冒泡排序的过程也比较简单：先将第一个数据跟第二个数据比较，若为逆序，则交换两个数据，然后再比较第二个数据和第三个数据。依此类推，直至第n-1个数据跟第n个数据进行对比为止。而快速排序是对冒泡排序的一种改进，它是先通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的数据都比另一部分的数据要小，则可分别对两部分继续进行排序，运用到了递归算法。三、 源程序及注释 #include #include int a50; /定义存放输入数据的数组 int suiji() /构造随机产生数据的函数 int i;for(i=1;i=30;i+) ai=random(100);printf(%d ,ai); /输出随机产生的数据int shuru() /构造从键盘输入数据的函数 int i;printf(Please input 30 numbers:); for(i=1;i=30;i+) scanf(%d,&ai); void insertsort(int n) /直接插入排序函数，待排序数组有n个元素 int i,j,t;for(i=2;i=1)&(taj) aj+1=aj; j-; /顺序比较和移动aj+1=t; printf(nnThe result of insertsort is:); for(i=1;i=2;-i) / i为排序次数 for(j=1;jaj+1) /若为逆序，交换两个数据 b=aj+1; aj+1=aj; aj=b; printf(nThe rusult of maopao is:); for(i=1;i=n;i+) /输出排序之后的数据数组 printf(%d ,ai);int kuaisu(int d,int g) int t,m; t=ad; /取枢轴数据 m=ad; /取监视哨 while(d=t&gd) -g; ad=ag; /将比枢轴数据小的数据移到低端 while(add) +d; ag=ad; /将比枢轴数据大的数据移到高端 ad=m; /监视哨到位 return(d); /返回枢轴位置 int quick(int d,int g) /快速排序函数 int p; if(dg) p=kuaisu(d,g); /将待排序数组一分为二 quick(d,p-1); /对低端数据递归排序，p为枢轴位置 quick(p+1,g); /对高端数据递归排序 shuchu(int n) int i,d,g;printf(nThe result of quick is:);/将快速排序后的数组输出 for(i=1;i=n;i+) printf(%d ,ai);main()char ch;int m;clrscr(); printf(Please