东北大学数据结构实验报告.pdf

《东北大学数据结构实验报告.pdf》由会员分享，可在线阅读，更多相关《东北大学数据结构实验报告.pdf（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、./v .实 验 报 告 一、实验目的（1）掌握线性表的基本操作（插入、删除、查找）以及线性表合并等运算在顺序存储结构、链式存储结构上的实现。重点掌握链式存储结构实现的各种操作。（2）掌握线性表的链式存储结构的应用。二、实验内容与实验步骤（1）实验内容：实现约瑟夫环，约瑟夫环（Joseph）问题的一种描述是：编号为 1、2、3n 的 n 个人按照顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值 m，从第一个人开始按照顺时针的方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他的顺时针方向上的下一个人开始重新从 1

2、报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序。（2）抽象数据类型和设计的函数描述，说明解决设想。首先定义一个链表，用其中的 data 项存储每个人的编号，用 password 项存储每个人所持有的密码，并且声明一个指针。之后使用 CreatList_CL 函数来创建一个循环链表，在其中的 data 和 password 中存入编号和密码，最后使最后一个节点的 next 指向 L，使其能够形成循环队列。定义了函数 Display 来显示链表当中的内容，以确定存储的数据没有错误。定义了函数 Delete_L 来实现约瑟夫环中依次删除的功能，依次比较，如果某个人所持的密码和 m

3、值相等，则删除这个结点，并且输出此时该结点的编号和密码，实现出列的功能。（3）简短明确地写出实验所采用的存储结构，并加以说明。该实验我主要采用的是线性表的链式存储结构，首先定义了链表的结构，其中包括 data项和 password 项，分别存储每个人的编号和所持密码，还声明了指向下一个结点的指针，该指针可以连接各个结点，并且将最后一个结点的指针指向第一个结点使之成为一个循环链表。三、实验环境 操作系统：Windows 7 调试软件名称：Visio Studio2017 上机地点：信息楼 B405 四、实验过程与分析（1）主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明设计的巧

4、妙之处。课程名称：数据结构 班级：实验成绩：实验名称：顺序表和链表的应用 学号：批阅教师签字：实验编号：实验一：实验日期：2017-11-25 指导教师：组号：实验时间：18:3022:30 2 本实验中主要的函数包括创建链表、显示链表内容和出列过程四个部分。主要函数的代码如下：创建链表：typedef int Datatype;typedef struct node/链表的定义 Datatype data;int password;struct node*next;ListNode,*CLinkList;void CreatList_CL(CLinkList*L,int n)/创建一个链表

5、int i,pin;CLinkList p,q;(*L)=(CLinkList)malloc(sizeof(ListNode);if(*L)=NULL)printf(errorn);else (*L)-next=NULL;q=*L;for(i=0;idata=i+1;p-password=pin;q-next=NULL;q-next=p;q=p;q-next=(*L)-next;/指向 L 结点，形成 创建这个链表的时间复杂度为 O(n)，空间复杂度为 O（n2）。显示链表中的信息内容：void Display(CLinkList*L,int n)int i;CLinkList p;p=(*L

6、)-next;printf(n 显示链表内容n);3 for(i=0;idata,p-password);p=p-next;该算法的时间复杂度为 O（n）,空间复杂度为 O(n2)。删除结点，完成出列功能：void Delete_L(CLinkList*L,int n,int m)int i=0,j;CLinkList p,q;q=(*L);p=(*L)-next;printf(n 删除的顺序：n);while(in)for(j=0;jnext;printf(编号：%d 密码：%dn,p-data,p-password);m=p-password;q-next=p-next;free(p);p

7、=q-next;n-;该算法的时间复杂度为 O(n2)，空间复杂度为 O(n2)。该设计的巧妙之处在于并不需要额外的空间来存储数据，因而空间复杂度较低，而且线性表的链式存储结构可以用物理位置上的邻接关系来表示结点间的逻辑关系，这样使读者在阅读代码的过程中可以更加方便和便于理解。它可以随机存取表中的任一结点，还可以免插入和删除操作带来的大量的结点的移动，能给结点动态分配内存，这样就不存在存储空间不足的情况，而且循环链表还可以方便的从链表的最后一个结点遍历到链表的第一个结点。使操作更加方便。（2）你在调试过程中发现了怎样的问题？又做了怎样的改进 1）在最开始的调试阶段，我发现链表插入结束之后，不能

8、按照正常情况下输出链表的内容，只能正常显示第一个人的数据,在显示第二个人的信息是数据为乱码。之后我发现，在插入链表的过程中，我是在执行循环插入数据的循环中将结点的指针指向了第一个结点，因而，在进行链表显示的过程中，第二个结点的内容不是正常的数据。之后我将q-next=(*L)-next;这条指令放到了整个插入循环的外部，这样表示在插入所有数据之后，4 最后一个结点的指针指向了第一个结点，形成了一个循环队列，此时链表的数据显示正确。2）再次调试时，我发现人员出列时，只有第一个人出列正常，在第二个人出列时程序自动终止，不能正常显示之后出列的人的信息，并且程序自动终止运行，经过检查我发现在经过一次删

9、除后，没有将指针指向下一个结点，因而出现问题。经过更改，程序运行正常。3）在实验的开始阶段，数据遍历总是出现问题，经过查找资料我发现了约瑟夫环头结点的特殊性，因此我不再使用头结点，程序便恢复正常了。（2）测试结果 五、实验结果总结 回答以下问题：（1）你的测试充分吗？为什么？你是怎样考虑的？答：我认为我的测试充分，因为我随机选用了很多组不同的数据进行测试，并且每次测试的结果都是正确的答案，这样选取的数据具有很强的随机性，具有代表性，因而我认为我的测试比较充分。（2）你的存储结构的选取是不是很适合这个应用？为什么？答：我认为我选取的线性链式存储结构适合这个应用，因为首先此题中描述的情景中表示人们

10、按照顺时针的方向进行排队，此时头尾相连，这与循环链表的结构十分相似，使用循环链表的结构，这样可以很方便的从链表的最后一个结点访问到链表的第一个结点，并且这样的存储方式是用物理位置上的邻接关系来表示结点间的逻辑关系，根据这个特点，该种结构可以随机存取表中的任一结点，而且它也可以避免插入和删除操作带来的大量结点的移动，并且可以随时分配空间和释放空间，这样可以减少空间的使用量，并且可以做到灵活的扩充空间，这样的结构很适合这个应用。（3）用一段简短的代码及说明论述你的应用中有关插入和删除元素是如何做的？答：插入元素：首先定义了两个临时指针 p 和 q 来分别表示新插入结点的指针和第一个结点的指针，在每

11、次插入之前应该动态的分配内存，输入要输入的信息，并且将各种数据存储到链表中相应的项里，将前一个结点的 next 赋值为空，再将前一个结点的指针指向下一个结点，此时完成一个元素的插入。依次类推，运用循环来实现所有人的数据的插入，关键代码如下：5 p=(CLinkList)malloc(sizeof(ListNode);if(p=NULL)printf(errorn);printf(请输入第%d 个人的密码：,i+1);scanf(%d,&pin);p-data=i+1;p-password=pin;q-next=NULL;q-next=p;q=p;删除元素：进行循环来实现每个元素出列的功能，首先

12、每个人进行循环，一次进行报数，在报到 m-1 之前都不进行删除元素这个动作，在 m 时，把此时结点中的password 中的数值赋给 m 然后运用 q-next=p-next;将结点删除，同时释放结点 p,将人数减 1，以此类推完成所有的删除操作，直到所有的元素出列，关键代码如下：while(in)for(j=0;jnext;printf(编号：%d 密码：%dn,p-data,p-password);m=p-password;q-next=p-next;free(p);p=q-next;n-;（4）在你的应用中是否用到了头结点？你觉得使用头结点为你带来方便了吗？答：在我的应用中我没有用到头结

13、点。在实验的一开始，我使用了头结点，但是使用头结点给数据的遍历带来了困难，因此我便放弃使用头结点。（5）源程序的大致的执行过程是怎样的？答：首先用编译器编写一个.c 的文件，然后编译生成.obj 的文件，通过连接将目 标文件连接生成一个.exe 文件，之后运行文件就可以执行了。六、附录（1）实验设想和建议 这次实验提高了我对数据结构中关于循环链表和顺序表的理解，提高了我的编程能力，学校以后最好可以增加实验课的课时，这样我们可以更大程度的提高自己的编程能力。另外我认为该实验不仅可以使用使用链表指针来实现，还可以使用数组来模拟链表来实现约瑟夫环，用数组的下标来指向前一个和后一个元素，之后进行删除来

14、实现约瑟夫环。（2）参考资料：数据结构（第二版）闫玉宝编著 清华大学出版社 6 实 验 报 告 一、实验目的（1）掌握栈、队列、串和数组的抽象数据类型的特征。（2）掌握栈、队列、串和数组的抽象数据类型在计算机中的实现方法。（3）学会使用栈、队列来解决一些实际的应用问题。二、实验内容与实验步骤（1）实验内容：假设表达式中除了变量名、常量和运算符外，还可以允许两种括号：圆括号和中括号，其嵌套的次序随意，编写程序检验输入的表达式中括号的的顺序是否合法。（2）描述抽象数据类型或设计的函数描述，说明为什么要使用这种抽象数据类型，并说明解决设想。抽象数据类型或函数描述：首先定义了一个结构体并且声明为栈类型

15、，在其中定义了空间基地址的指针、栈顶指针以及栈存储空间的大小。之后设计了 Creat _Stack 的函数，用此函数来创建一个空栈，这样可以使用堆栈来实现括号匹配的功能，又设计了一个名为Stack_Full 的函数了来判断栈是否已满，若栈未满才可继续之后的压栈功能，如果堆栈已满，则需要使用 realloc 来动态分配空间，扩大栈的存储空间。我还设计了一个名为 empty 的函数，用它来判断堆栈是否为空，堆栈为空或不为空时分别返回 0 或 1。之后设计了名为 push和 pop 的函数来实现括号的入栈和出栈，之后设计了名为 Match 的函数，来判断括号是否匹配，设计了名为 clean 的函数来

16、清空堆栈，这样可以连续判断不同的多项式的括号是否匹配。解决设想：对于本题，首先我使用了栈结构，利用栈中数据“先进后出”的特点来实现对括号是否匹配的检验。实现过程基本如下：从左到右依次扫描多项式，如果遇到左括号便将左括号入栈，在所有左括号入栈之后便可以扫描到右括号，如果扫描到的右括号和栈顶的左括号可以匹配时，将左括号出栈，以此类推，最后判断栈是否为空，若为空，则括号匹配，否则括号不匹配。三、实验环境 操作系统：Windows 7 调试软件名称：Visio Studio2017 上机地点：信息楼 B405 四、实验过程与分析 课程名称：数据结构 班级：实验成绩：实验名称：栈、队列、字符串和数组 学

17、号：批阅教师签字：实验编号：实验二：实验日期：2017-11-20 指导教师：组号：实验时间：18:3022:30 7（1）实现时，主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明设计的巧妙之处。主要函数或操作内部的主要算法：typedef struct/栈的声明 char*base;/指示存储数据元素的空间基地址的指针 char*top;/栈顶指针 int stacksize;/栈存储空间大小，以数据元素为单位 SStack;void Creat_Stack(SStack*s)/创建空栈 s-base=(char*)malloc(sizeof(char)*size);if(

18、s-base=NULL)printf(errorn);else s-top=s-base;s-stacksize=size;上面的算法用来建立栈，该算法的时间复杂度为 O(1)，空间复杂度为 O（n）。int Stack_Full(SStack*s)/判断栈是否为满 if(s-top-s-base=100)return 1;else return 0;int empty(SStack*s)/判断栈是否为空 if(s-base=s-top)return 0;else return 1;上面的算法分别用来判断栈是否已满，栈是否为空栈，上面两个算法的时间复杂度和空间复杂度均为 O（1）。void p

19、ush(SStack*s,char*str)/入栈 if(Stack_Full(s)!=0)8 printf(fulln);else *s-top+=*str;void pop(SStack*s,char*str)/出栈 if(s-base=s-top)printf(The stack is emptyn);else *str=*-s-top;上面两个算法用来实现数据的入栈和出栈，时空复杂度均为 O（1）。void Match(SStack*s,char*str)int i,j;char t;j=strlen(str);for(i=0;ij;i+)if(stri=(|stri=)push(s,

20、str);for(i=0;itop=()pop(s,&t);else s-top=s-top-1;if(stri=)if(*s-top=)pop(s,&t);else s-top=s-top-1;9 if(empty(s)=0)printf(括号匹配!n);else printf(括号不匹配!n);该 Match 函数的作用即判断括号是否匹配，是本程序的核心函数，若假设输入的表达式的长度为 n，则此函数中进行了两次循环，一次为扫描左括号使其全部入栈，另外一次为扫描右括号并且判断新扫描出来的右括号与栈顶的左括号是否匹配。在整个过程中执行了2n 次循环，因此此程序的时间复杂度为 O(n)。对于空间

21、复杂度，本算法存储了长度为 n 的表达式，因而该算法的空间复杂度为 O(n)。设计的巧妙之处：在本程序中我使用了栈这种抽象数据类型，栈的“先进后出”的特点与检验括号是否匹配的“期限待的急迫程度相吻合，设计顺序栈来解决括号匹配问题。如果单从括号检验这个目的考虑可以有多种方法来实现该实验目的，而使用栈来实现括号匹配的检测，简化了程序的设计，比较容易理解和实现，并且可以提高时间效率。（2）你在调试过程中发现了怎样的问题？又做了怎样的改进？1）在开始程序编译时，编译器总是提醒函数的形式参数的写法有问题，之后我发现，我在栈声明时将 SStack 未声明为指针类型，而我在形式参数中将参数写成了 SStac

22、k s，因而出现错误，所以我将其更改为 SStack*s，这个问题得以解决。2）之后，编译器进行编译时，编译器提醒我在调用 empty，match 等函数时，实际参数的输入有问题，使得编译不能够通过，经过检查我发现我在写这些函数时，形式参数定义为 char*s，因而我便在实际参数中代表字符串的参数前加取地址&符号，这个问题便解决了。3）在进行编译时还出现了这样的警告，说我的小于号没有定义或者没有匹配，经过检查我发现我在循环中将其中一个条件写成strlen(str)，之后，我定义了一个新的局部变量 j，用 j 等于 str 的长度，这样警告便消除了。（3）你的抽象数据类型的实现是否具有可扩展性？

23、我的抽象数据类型具有可扩展性，因为栈的大小可以修改，如果栈已满，则可以增加空间，因此具有可扩展性。（4）测试结果 10 五、实验结果总结 回答以下问题：（1）你的测试充分吗？为什么？你是怎样考虑的？答：我认为我的测试充分，因为我的表达式是随机给出的，这样选择的数据具有随机性，具有很强的代表性，并且每次的结果正确，因此我认为我的测试比较充分。（2）为什么你要选用栈或队列或字符串或数组等抽象数据类型作为你应用的数据结构？答：我使用了栈这种抽象数据类型作为我应用的数据结构，栈是一个只能访问表的尾端数据的数据集合，是一种在表的一端进行插入和删除操作的线性表，数据具有“先进后出”的特点，而这种特点和括号

24、匹配中检验括号的“期限待的极限程度”这个特点相符合，因此选用栈这种数据结构可以简化程序，更好的理解和实现程序，提高了程序运行的时间效率。（3）用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。答：下面的代码部分为 Match 函数中的主要处理部分，使用了两个循环来处理输入的表达式，第一个循环是用来从左到右扫描表达式遇到“（”或者“”就将括号入栈，第二个循环是用来扫描表达式，如果遇到“）”或“”就将其与栈顶的括号进行匹配，如果匹配，就将栈顶的左括号弹出，如果不匹配就将栈顶指针向下移动，直到所有的括号操作完成，如果栈为空，那么该表达式的括号是匹配的，否则括号不匹配。j=strlen(s

25、tr);for(i=0;ij;i+)if(stri=(|stri=)push(s,str);for(i=0;itop=()pop(s,&t);else s-top=s-top-1;if(stri=)if(*s-top=)pop(s,&t);else 11 s-top=s-top-1;（4）你的应用中采用的是顺序的还是链式的存储结构？为什么要选用这种存储结构。答：我的应用中采用的是顺序的链式存储结构，因为对于栈这种抽象的数据类型，有着“先进后出”的特点，这种特性和表达式中括号匹配的过程相符合，因此我采用了这种存储结构。（5）源程序的大致的执行过程是怎样的？答：先用编译器编写一个.c 的文件，然后

26、编译生成.obj 的文件，通过连接将目标文件连接生成一个.exe 文件，之后运行文件就可以执行了。六、附录 实验参考的资料 数据结构（第二版）闫玉宝编著 清华大学出版社 思考题（a）栈和队列在计算机系统中有哪些应用？写出你知道的系统中，这两种抽象数据类型的应用。答：在计算机系统中，使用栈的应用有表达式的计算，迷宫以及括号匹配等。使用队列的应用有打印文档，售票系统，解决主机与外部设备之间速度不匹配问题，解决多用户引起的资源竞争问题等（b）在程序调用的时侯，需要进行函数的切换，你认为函数在进行切换时系统要做那些工作？答：对于函数的切换，主要是一个压栈的过程，先以一种约定的方式把参数压栈，然后根据函

27、数地址调用函数，函数执行后根据约定的方式出栈取得参数。12 实 验 报 告 一、实验目的（1）理解分治法的思想。（2）掌握用分治法解决问题 二、实验内容（1）仔细阅读备选实验的题目，选择一个（可选多个）作为此次实验题目，设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用 C的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。（2）归并排序 问题描述 目前的网上拍卖系统会显示很多待拍卖的物品，通常这些系统具有按照某个关键字对打出的广告进行排序列出的功能，并且能够按照用户输入的某个关键字进行过虑，找到某些特定的物品。编程任务 定义一个 Ad

28、vertisement 类，该类中至少包含该物品的数量，名称，联系人，最好有开拍时间及关闭时间，根据用户输入的关键字比如名称，mail，时间等，利用非递归的归并排序对所有的广告进行排序，并列出所有排好序的广告。数据输入 由文件 input.txt 提供输入的所有广告信息。程序中由用户输入要排序的关键字。结果输出 程序运行结束时，排好序的广告输出到文件 output.txt 中，并为每个广告添加序号。输入文件示例 输出文件示例 input.txt output.txt 课程名称：数据结构 班级：实验成绩：实验名称：栈、队列、字符串和数组 学号：批阅教师签字：实验编号：实验三：实验日期：2017-

29、12-7 指导教师：组号：实验时间：18:3022:30 13 Coat(物品名称)3（数量）amail.Skirt 5 bmail.Cap 7 cmail.Bag 12 amail.Title（用户输入按照title排序）1 Bag 12 amail.2 Cap 7 cmail.3 Coat(物品名称)3（数量）amail.4 Skirt 5 bmail.三、实验环境 操作系统：Windows 7 调试软件名称：Visio Studio2017 上机地点：信息楼 B405 四、问题分析（1）分析要解决的问题，给出你的思路，可以借助图表等辅助表达。答：归并操作的工作原理如下：1.申请空间，使其

30、大小为两个已经排序序列之和，该空间用来存放合并后的序列 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指 4.针到下一位置 5.重复步骤 3 直到某一指针达到序列尾 6.将另一序列剩下的所有元素直接复制到合并序列尾 （2）分析利用你的想法解决该问题可能会有怎样的时空复杂度。时间 O(nlogn)空间 O(n)14 五、问题解决（1）描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述.算法设计：void MergeSort(int*dat

31、a,int n)int step=1;while(step n)for(int i=0;i=n-1)right=n-b;else right=length;int*temp=new intlength+right;int i=0,j=0;while(i=length-1&j=right-1)if(dataa+i=datab+j)tempi+j=dataa+i;i+;else tempi+j=datab+j;j+;if(j=right)/a 中还有元素，且全都比 b 中的大,ai还未使 memcpy(data+a+i+j,data+a+i,(length-i)*sizeof(int);memcp

32、y(data+a,temp,(i+j)*sizeof(int);delete temp;时间复杂度：时空复杂度：如果输入数据本来就是按非降次序排列的，则根 15 本不会进入 while 循环，这就是最好情况，计算时间是 O(n)。（2）针对你所选的问题，你认为应该特别注意哪些方面的处理？比如循环何时结束等。答：对于什么时候将 i 和 i+step 这两个有序序列进行合并以及当 i 以后的长度小于或者等于 step 时退出要注意处理。（3）你在调试过程中发现了怎样的问题？又做了怎样的改进？在调试过程中，我发现对于相同值的两个物品无法进行排序，这是由于我的算法在设计过程中没有考虑到这种情况，所以在

33、设计标记数组的时候我就设计了能将两个相同值的物品区分开来。六、实验结果总结 本次实验从写归并排序到实现广告类的排序，都是由自己独立完成，有一整晚没有睡觉都在写这个实验，所以对本次实验的实现过程比较熟悉，而且还增加了对于商品时间的显示和排序。很久没有用 C+的我有点儿生疏，刚开始写起来有点慢，但是还是很好得完成了任务，程序中几乎没有任何的 BUG。但是通过本次实验我既加深了对于 C+的熟悉程度，也了解到了很多关于归并排序的知识，这些知识对于我以后的程序开发会有比较大的作用，所以我觉得这次实验对我的作用是比较大的。1.程序运行截图：16 实 验 报 告 一、实验目的（1）熟练掌握动态规划思想及教材

34、中相关经典算法。（2）掌握用动态规划解题的基本步骤，能够用动态规划解决一些问题。二、实验内容与实验步骤（1）仔细阅读备选实验的题目，选择一个（可选多个）作为此次实验题目，设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，课程名称：数据结构 班级：实验成绩：实验名称：栈、队列、字符串和数组 学号：批阅教师签字：实验编号：实验四：实验日期：2017-12-18 指导教师：组号：实验时间：18:3022:30 17 效率较高，利用 C的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。（2）可供选择的题目有以下 2 个：(i）找零钱问题（难度系数为 3）问

35、题描述 设有 n 种不同面值的硬币，各硬币的面值存于数组 T1:n中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值 T1,T2,Ti时，可找出钱数 j 的最少硬币个数记为 C(i,j)。若只用这些硬币面值，找不出钱数 j 时，记 C(i,j)=。编程任务 设计一个动态规划算法，对 1jL，计算出所有的 C(n,j)。算法中只允许实用一个长度为 L 的数组。用 L 和 n 作为变量来表示算法的计算时间复杂性 数据输入 由文件 input.txt 提供输入数据。文件的第 1 行中有 1 个正整数n（n1 时，若jTn,即 第n种 钱 币 面 值 比 所 兑 换 零

36、钱 数 小,因 此 有1),(),(min1kTjnCjnCnk。当 k 为n)i(1k0时，C(n,j)达到最小值，有P(T(k0),j)=P(T(0k)，j-T(0k)+1 若 j=Tn，即用 n 种钱币兑换零钱，第 n 种钱币面值与兑换零钱数 j 相等，此时有 C(n,j)=C(n,Tn)=1；,1,0),(),(nTinTinTiPjiP 若 jTn，即第 n 种钱币面值比所兑换零钱数大，因此兑换零钱只需考虑前 n-1 种钱币即可，故有 C(n,j)=C(n-1,j)，且 P(T(n-1),j)=0。从以上讨论可知该问题具有重叠子问题性质。根据分析建立正确的递归关系。01%01%TjT

37、j1/),1(TjjC01%01%TjTj1/),1(TjjC 19 答：Ti;j0 j)1,-C(iTij 1)Ti)-jC(i,j),1,-min(C(ij)C(i,分析利用你的想法解决该问题可能会有怎样的时空复杂度。答：算法的时间复杂度主要取决于程序的两个循环，所以算法的时间复杂度为)O(n2；算法执行过程中引入了一个二维数组，随着输入规模的增大，所需要的空间复杂度为：)O(n2 五、问题解决（1）根据对问题的分析，写出解决办法。答：设数组 T中存放的是 n 种钱币递增的不同面值，所要找的钱数为 M,M由用户输入；数组 Cj表示利用数 Tn兑换零钱数为 j 时所用的最少钱币个数，即最优值

38、；Pij(1=i=n)表示按照上述最优值兑换零钱 J 时用到钱币面值为第 i 种钱币的个数。（2）描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。#include using namespace std;int main()int c;int a25=0,a10=0,a5=0,a2=0,a1=0;cout请输入要找的零钱:c;a25=(c/25);20 a10=(c%25)/10;a5=(c%25)%10/5;a2=(c%25)%10%5/2;a1=(c%25)%10%5%2;cout需要找以下几种零钱:endl

39、;cout25 分的a25枚endl;cout10 分的a10枚endl;cout5 分的a5枚endl;cout2 分的a2枚endl;cout1 分的a1枚endl;时间复杂度：从上面算法可知，最优值 c的计算过程中，最外层为循环for(j=1;j1&flag=0)循环，而while(k1&flag=0)循环中又嵌套着三个并列的 for 循环。因此本算法最坏情况下的复杂度是 O(M*2n)；最好的情况当然是里面 for 循环的条件不满足而不执行，此时的复杂度为 O(M*n)。其中：M 表示需要兑换的零钱数，对于 M 来说，该值一般不是很大，对于钱币来说，M 会小于 100 元，即 10 0

40、00 分；n 表示钱币的种类，n 值一般不会很大如钱币总的有 13 种(从 1 分，2 分，100 元)。经过以上分析，如是最坏情况时的复杂度应为 O(M*2n),则该值对于内存和运行速度较小的自动售货机等的应用前景则不会很好。但本算法中的递归结构在 MTn时，有1),(j),C(nmink1kTjnCn。可见对于钱币 j=M 时，求 c(n,j)时，并不要求对从 1ij，的所有情况都要求 c(n,i)+1，而是只求1),(kTjnC。其中：1kn。钱币一般只有13 种左右，因此其效 21 率大为上升。最坏的情况下需要执行)O(n)nO(M32，而 M 小于 100元即 10000 分，远大于

41、 n。本算法的动态规划算法的时间复杂性比该问题的一般动态规划算法的效率要好得多。该算法的时间复杂性是310数量级的 对于应用于自动售货机等运行速度较慢的机器来说是不成问题的。空间复杂度：从上面算法可知，用到了三个数组，分别为 Tn，cj，Pij。其中：i=n,j=M。空间复杂性主要由 P1j决定，为 O(Mn)。P(i,j)中的 i 指的 Tn中的值对于钱币来说一般 n 为 13 左右。该算法的空间复杂度为 O(M x n)=O(f)，而 M 小于 100 元即 10 000 分，远大于 n。该算法动态规划的空间复杂性比该问题的一般动态规划的效率要好得多。该算法的空间复杂性为210数量级，这对

42、于应用到小内存的自动售货机来说是没有任何问题的。（3）你在调试过程中发现了怎样的问题？又做了怎样的改进？答：在调试过程中，我发现对于该算法最主要的在于矩阵 Ci,j的求解，而算法的递归关系没有弄明白，所以在求解 Ci,j时总是出现问题，后来在查询了资料后，将 Ci,j递归关系的实现改为cj=temptotal/Tj;temptotal=temptotal-Tj*cj;tempcount=tempcount+cj;解决了该问题。（4）写出用你的测试数据按照算法的流程填写的算法中的存储结构。C1,2,3=0,2,9。六、实验结果总结 1.程序运行截图：22 2.回答以下问题：（2）算法实现的复杂度

43、在问题规模很大时可以接受吗？答：可以接受，因为动态规划算法有很好的效率，所以当问题复杂度很大时，就不会影响到算法的运行时间。（3）如果不用动态规划方法还能想到其他的解决方式吗？和动态规划相比会有更好的效率吗？答：对于找硬币问题，有时候贪心算法也能解决，但不如动态规划求解有效率，所以采用动态规划方法是一个很好的选择。（4）所选用的数据结构合适吗？答：采用了数组的数据结构，合适，因为该数据结构能够支持对于数组中的元素的随机访问，而且方便查询。（5）该算法都存在哪几类可能出现的情况，你的测试完全覆盖了你所想到的这些情况吗，测试结果如何？（6）叙述通过实验你对动态规划方法的理解及其优缺点 答：优点：动态规划方法有效利用了子问题的重叠性，减少了大量的计算。而且动态规划的使用也非常简单，只需要问题满足最优子结构、子问题重叠性、无后效性即可。通常可以利用分置思想构造出子问 23 题的分解方法，就可以利用动态规划。缺点：动态规划的缺点并不是最快的方法，只是解决某一类型的问题的工具或者优化某些 NPC 问题的时间效率。动态规划的很重要的一点就是用大量空间换取时间上的优化，所以这并不是一个完美的方法。