孙魏东_实验一.doc

《孙魏东_实验一.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构预习实验报告1、问题分析实验任务：用指向指针的指针的方法对n个整数排序并输出。要求将排序单独写成一个函数，n和个整数在主函数中输入，最后在主函数中输出。即用键盘输入若干个数据，运用快速排序对输入的数据进行排序，然后将排序后的数据全部的输出到屏幕上。关键问题：（1）如何定义一个指向指针的指针来指向n个整数序列（2）用什么算法进行排序（3）排序时单独定义一个函数，其从主函数中如何将需要排序的参数传递到子函数中去。（4）所采用的算法的时间复杂度如何，以及算法是否会浪费内存空间和运行时耗费大量的时间。数据类型：因为只是对数据进行排

2、序操作，所以程序中的输入的数据的类型为整型变量，输入的数据的范围为整型变量int的取值范围，个数可以从键盘输入任意数。测试数据：第一组：3，2，1预计输出：1,2,3第二组：3,2,1，-2,8预计输出：-2,1,2,3,8第三组：3,2,0，1，4，-1,8,6预计输出：-1,0,1,2,3,4,6,8第四组：j，15，1，m，10，5，6，8预计输出：程序崩溃2、概要设计（1）该算法的主要问题就在于如何定义一个指向指针的指针来指向n个整数序列以及如何对数据进行操作。（2）在这里我们本程序采用快速排序算法，可以将给定的若干个无序

3、的数据数组任选其中的一个元素，比如第一个，首先找到该元素的对应的位置的下标，然后再以该元素的下标为基准，将数组分为两段，再寻找第二个元素的下标位置，依次类推就可以完成所有的数据的排序操作了。（3）本程序主要包含3个函数1）主函数main()2）快速排序函数Quicksort()3）找到第一个元素下标函数Quickpass()（4）函数调用关系如下：1、详细设计（1）由于本程序只是一个排序的算法，所以在程序的数据结构上可以采用数组这种顺序存储结构，首先定义一个长度为n的数组，再定义int*a，a为指向该数组的指针变量，然后输入n的值

4、，a=newint[n];此时a为指向数组的首地址的指针变量。再定义一个指向a指针变量的指针数组q,可以先对其数组的大小赋初值int*q[100];再把指针a的地址传递给q，用指针q数组来分别指向a指针，从而实现指向指针的指针指向了整数序列。（2）在排序上利用快速排序算法来实现对整型数据的排序操作，首先定义一个函数voidQuicksort(int*r[],intlow,inthigh);函数的形参部分（int*r[]）传递了指针数组q，和数组的第一个元素下标（low）和最后一个元素的下标（high）。再定义一个可以找到元素某位置

5、下标的函数intQuickpass(int*r[],intlow,inthigh)，函数的形参部分（int*r[]）传递了指针数组q，和数组的第一个元素下标（low）和最后一个元素的下标（high）。（3）首先在这组无序的整型数据中找到第一个数据正确排序后所对应的下标。再以刚刚找到的元素的下标为基准把数据分为两段，分别找出这两段数据中第一个元素所对应的数据的下标，最终当所有的元素位置都找到时，循环结束，输出整型数据的排序。2、调试分析（1）程序中遇到的一些问题和解决办法:在编写程序的过程中基本都很顺利，唯一一个遇到的问题就是在输出

6、结果的时候出现过结果全部都是类似随机数随机数的值，也就是在指针传递数据的过程中发生了错误，导致输出的指针所对应的值出现类似随机数的值，即指针为空，经过一些调试发现在输出语句中，printf("%d",*q[h]);中的‘*’忘记写了，导致输出的结果并不是该指针对应的数据，而是该指针的地址，也就是一串类似于随机数的值。（1）算法的时空分析：1）空间性能：在整个程序中，由于利用了指向指针的指针指向的数组，所以在存储空间上造成了一定的浪费，但是相对是比较少的。2）时间性能：本程序采用的是快速排序算法来进行对数据的排序操作，所以在对数据的

7、操作上相对于普通的冒泡排序等算法快了很多，经过大量的数据测试发现，当数据量越大时，快速排序在时间上的优越性体现的越明显。（2）经验体会：通过本次的程序编写，让我第一次对于程序的时间和空间性能有了新的理解，懂得了在程序开发中，我们不仅仅要实现程序预期的功能，同时也应该注重程序在时间和空间上性能。1、用户使用说明（1）程序运行的环境为dos环境下，程序执行开始时显示如图1所示：图1开始程序（2）输入需要排序的数据的个数，按回车键结束。（3）按提示输入该组数据中第几个元素的数据，按回车键结束。（4）输入完成后自动打印出排序结果。（5）程

8、序结束，按任意键退出程序。2、测试结果（1）输入排序数据个数3，分别输入（3,2,1）几个测试数据，所得排序后数据为（1,2,3），运行结果如下：（2）输入测试输入排序数据个数5，分别输入（3,2,1，-2,8）几个测试数据，所得排序后数据为（-2