数据结构课程设计个人设计报告.doc

数据结构课程设计-个人设计报告目 录1 课程设计目的.22 课程设计内容和要求.23 任务完成情况.24 设计报告.34.1顺序表的应用.34.1.1 设计目的.34.1.2 设计内容及要求.34.1.3 需求分析.34.1.4 概要设计.44.1.5 详细代码.44.1.6 使用说明.44.1.7 测试结果与分析.54.1.8 参考文献.74.2链表的应用.84.2.1 设计目的.84.2.2 设计内容及要求.84.2.3 概要设计.94.2.4 需求分析 .94.2.5 详细代码.94.2.6 使用说明.104.2.7 测试结果与分析.114.2.8 参考文献.124.3选做题.124.3.1 设计目的.124.3.2 设计内容及要求.134.3.3 需求分析.134.3.5 详细代码.134.3.6 使用说明.134.3.7 测试结果与分析.134.3.8 参考文献.145 体会与感想.14附录：.14附件一 顺序表的运用代码.14附件二 链表的运用代码.22附件三 选做题代码.311 课程设计目的1、 学习获取知识的方法；2、 提高发现问题、分析问题和解决实际问题的能力；3、 加强创新意识和创新精神；4、 加强团队的分工与合作；5、掌握面向实际背景思考问题的方法。2 课程设计内容和要求内容：前言第一章 顺序表与链表第二章 栈和队列第三章 树和二叉树要求：（1）完成线性结构的设计任务，其中选做题不是必须完成的任务（2）每人必须在完成个人任务的基础上提交个人任务的设计报告，内容包括：任务名称、目的、具体内容、需求分析、概要设计、主要代码分析、测试结果、收获与体会。3 任务完成情况任务完成情况介绍，如表3-1.（仅供参考，请根据实际完成情况填写）表3-1 任务完成情况表完成任务名称顺序表的应用链表的应用选做题4 设计报告4.1顺序表的应用4.1.1 设计目的熟悉线性表的应用， 包括线性表的存储结构；向线性表中删除，插入元素；栈的操作，进栈，出栈；队列的操作，循环队列的操作。增加动手、编程能力。4.1.2 设计内容及要求（1） 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。要求：线性表元素个数n很大，而值为item的数据元素个数很少，要求移动元素个数尽量少；删除后的数组元素与原数组元素不必保持顺序一致。（2）编写一个函数将一个顺序表A（有n个元素，且任何元素均不为0）分拆成两个顺序表，使A中大于0的元素存放在B中，小于0的元素存放在C中。（3）假设一个算术表达式中包含圆括号，方括号和花号三种类型的括号，编写一个判别表达式中括号是否正确配对的函数correct（exp，tag）；其中：exp为字符串类型量，表示被判别的表达式，tag为布尔型的变量。（4）编写向顺序分配的循环队列QU0,m-1中插入一个结点的函数enqueue和从该队列中取出一个节点的dequeue函数。（5）编写一个主函数,调试上述算法。4.1.3 需求分析（1）删除所有值为item的数据元素，要使时间复杂度为0(n)、空间复杂度为0(1)。（2）对顺序表A输入元素，根据元素的正负对其分组。（3）使用一个栈st进行判定，将（，,入栈，当遇到）， 时，检查当时栈顶元素是否是对应的（，,，若是则退栈，否则返回表示不配对。当整个算术表达式检查完毕时栈为空，表示括号正确的配对；否则不配对。（4）在循环队列中，队尾插入结点，并在该队列中取出一个结点（5）建立工程实现上述函数4.1.4 概要设计4.1.5 详细代码见附录一。4.1.6 使用说明建立工程，按线性表运用系统提示进行操作。4.1.7 测试结果与分析选择1，调试第一个函数。输入7个数，1，2，3，4，5，3，7。选择删除3，程序运行后输出1，2，7，4，5结果正确。且在程序中采用头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。保证了程序的效率。选择2，调试第2个函数。按照正负，拆分线性表。输入6个数，1，2，3，-1，-2，-3。运行后a中存放1，2，3；b中存放-1，-2，-3。结果正确。选择3，进行符号配对函数调试。输入字符表达式：a+（b-c）/d；经过运行，结果为：Match！，配对。在设计算法时，使用一个栈st进行判定，将（，,入栈，当遇到）， 时，检查当时栈顶元素是否是对应的（，,，若是则退栈，否则返回表示不配对。当整个算术表达式检查完毕时栈为空，表示括号正确的配对；否则不配对。 选择4，进行第4个函数调试。选择队列个数：5；输入队列元素：1，2，3，4，5选择y,进入操作，进行入队。输入要插入的数字：6。入队只能在队尾进行插入，插入后的结果为：1，2，3，4，5，6。再进行出队操作。出队只能在对首进行删除，删除1。删除后的队列为：2，3，4，5结果正确。4.1.8 参考文献1 严蔚敏等著， 数据结构（C语言版）， 清华大学出版社4.2链表的应用4.2.1 设计目的熟悉链表的运用，对单链表，循环链表，进行插入、删除操作。4.2.2 设计内容(1) 假设有两个按元素值递增次序排列的线性表A和B，均以单链表形式存储，里面的大部分元素对应相等，请删除一些元素（A中有而B中没有，或B中有而A中没有），使得两个有序表中保留下来的元素对应相等。比如，A中元素为（1,3,5,8,10,13,18），B中元素为（1,3,6,8,9,10,13,15），则删除元素后A、B里的元素为（1,3,8,10,13）。(2) 猴子选大王。n只猴子围成一圈，从1到m报数，报m的猴子出局。余下的猴子从第m+1只开始继续从1到m报数，报m的猴子出局。第n只猴子报数后，第1只猴子接着报数（因为围成了圈）。待整个圈只剩下一只猴子时，该猴子即为大王。n和m由用户输入，请输出当选大王的猴子的编号。(3) 设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有prev（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。 (4) 在主函数中设计一个简单的菜单，分别调试上述算法。4.2.3 概要设计4.2.4 需求分析（1）将链表A和链表B中互不相等的数删除。（2）用链表实现约瑟夫循环。（3）对双向非循环链表进行排序。4.2.5 详细代码详见附录二。4.2.6 使用说明运行工程后，出现链表的运用菜单。如下图所示：菜单共有四个选项，选择不同的选项会出现相应的提示进行下一步操作：选择1：第一小题；选择2：第二小题；选择3：第三小题。 选择0：退出；4.2.7 测试结果与分析选择1，调试第一个函数：输入A 链表：1，3，5，8，10，13，18；B链表：1，3，6，8，9，10，13，15。经过程序运行后输出A，B的内容为：1，3，8，10，13。本程序对A链表进行遍历操作，和B比较，删除A中有而B中没有的元素，得到最A中的元素。同样对B进行操作，和删除后的A比较，删除多余的元素，即可得最后B中的元素。选择2，调试第2个函数，输入猴子数目30，再输入报数数目3，经过运行，得出最后的王为16号。选择3，对函数3进行调式。输入5个数据：1，2，3，5，7。首先访问：2，根据排序规律，访问后的顺序为：2，1，3，5，7；再访问：5，排序为：2，5，1，7。这是因为：最近访问的结点排在频度相同的结点的最后。然后再次访问5，得到：5，2，1，3，7。可见程序运行正确。4.2.8 参考文献1 严蔚敏等著， 数据结构（C语言版）， 清华大学出版社4.3链表选作题4.3.1 设计目的评优标准 4.3.2 设计内容及要求内容：已知两个单链表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素值递增的单链表形式存储。4.3.3 需求分析建立两个单链表A,B，将其元素递增排列后，再求出交集C4.3.5 详细代码详见附录三。4.3.6 使用说明将A，B的元素分别输入进去，以0结束。4.3.7 测试结果与分析输入A：3，10，18，13，5，1，8，0。输入B：15，10，6，8，3，1，9，13，0。输出A和B的交集：1，3，8，10，13。设计算法时，交集指的是两个单链表的元素值相同的结点的集合，为了操作方便，先让单链表C带有一个头结点c，最后将其删除掉。4.3.8 参考文献1 严蔚敏等著， 数据结构（C语言版）， 清华大学出版社5 体会与感想（1）这次数据结构的课程设计，使我对线性表和链表的理解加深了很多，通过实验题目的具体运用，有了一个更加清楚的认识和理解。对书上列出的函数算法，也能够更加深刻的理解它的意义。（2）在做线性时，主要是用结构体对线形表接点表示；对链表排序时所要考虑到的指针指向，这些操作为什么要按照这个顺序。考虑是头指针。（3）这次课程设计，我体会到编程要分段，把问题细画，看到一个题目，要理清大致思路，线性表该如何操作，链表该如何操作。画出流程图，可以使思路更加清晰。特别是双向非循环指针，对它排序要执行很多步骤，每次指针要移动多次，运行出来都只知道排序出错。只有细化，通过流程图。（4）本次实验采取工程来调试各个函数，学会了建立工程。对以后编写应用系统有一定帮助。附录一：顺序表运代码：头文件：head. h#include <stdio.h>#include <stdlib.h>#define MAXSIZE 100#define MAX_STACK 100#include<string.h>struct List int dataMAXSIZE; int length;struct stStack char szStackMAX_STACK; int nTop;struct Queue intpMAXSIZE; int front,rear; ;void program1_1();void program1_2();void program1_3();void program1_4();Main()函数：#include<stdio.h>#include<stdlib.h>#include"head.h"int main()int choice;doprintf("n 欢迎进入顺序表应用系统 n");printf("n-主菜单-n");printf("(1) 删除线性表中所有值为item的数据元素.n");printf("(2) 将一个顺序表以0为界点分拆成两个顺序表.n");printf("(3) 一个判别表达式中括号是否正确配对.n");printf("(4) 向队列插入一个结点和从该队列中取出一个结点.n");printf("(0) 退出系统.n");printf("n请选择：");scanf("%d",&choice);if(choice<0 && choice>5) continue;switch(choice)case 1:program1_1();break;case 2:program1_2();break;case 3:program1_3();break;case 4:program1_4();break;case 0:exit(0);default:break;while(1);return 0;program1_1();函数#include <stdio.h>#include"head.h"void program1_1() int item,n,i=0; printf("请输入一n的值：n"); scanf("%d",&n); printf("请输入n个数：n"); int *p=new intn;/动态开创数组pn for(i=0;i<n;i+)scanf("%d",&pi); printf("请输入要删除的数：n"); scanf("%d",&item); for(i=0;i<n;i+) if(pi=item) pi=pn-1; n-; i-; else continue; printf("删除后的结果:为n"); for(i=0;i<n;i+) printf("%d ",pi);printf("n"); program1_2();函数#include <stdio.h>#include <stdlib.h>#include"head.h"void program1_2() struct List la,lb,lc; int length,m,i,j=0,k=0; printf("请输入一个m的值："); scanf("%d",&m); la.length=m; printf("请输入m个数(不为零)："); int *p=new intm; int *q=new intm; int *n=new intm; for(i=0;i<m;i+)/存储线性表la的值 scanf("%d",&pi); for(i=0;i<m;i+) la.datai=pi; for(i=0;i<la.length;i+)/判断线性表lb,lc中的值的大小 if(la.datai>0) qj=la.datai; j+;lb.length=j; else nk=la.datai; k+; lc.length=k; for(j=0;j<lb.length;j+)/对线性表lb,lc中data赋值 lb.dataj=qj; for(k=0;k<lc.length;k+) lc.datak=nk; printf("a中大于0的元素存放在b中,为："); for(j=0;j<lb.length;j+)/打印线性表lb,lc中的内容 printf("%d ",lb.dataj);printf("n"); printf("a中小于0的元素存放在C中,为："); for(k=0;k<lc.length;k+) printf("%d ",lc.datak);printf("n"); program1_3();函数#include <stdio.h>#include <string.h>#include "head.h"void InitStack(stStack& s) s.nTop = -1;char Push(stStack& s, char c) if (s.nTop = MAX_STACK - 1) return 0; s.nTop +; s.szStacks.nTop = c; return c;char Pop(stStack& s) if (s.nTop = -1) return 0; char c = s.szStacks.nTop; s.nTop-; return c;int correct(char* szText) stStack s; InitStack(s); int nLen = strlen(szText); for (int i = 0; i < nLen; i+) char c = szTexti; switch (c) case '(': case '': case '': Push(s, c); break; case ')': if (Pop(s) != '(') return 0; break; case '': if (Pop(s) != '') return 0; break; case '': if (Pop(s) != '') return 0; break; if(s.nTop=-1) return 1; else return 0;void program1_3() char szText100;printf("请输入一个含字符串的表达式：n");scanf("%s",&szText); if (correct(szText) printf("Match!n"); else printf("Not match!n"); program1_4();函数 #include<stdio.h>#include<stdlib.h>#include<string.h>#include"head.h"void program1_4()void initqueue(Queue &L);int dequeue(Queue &L);void enqueue(Queue &L,char a); void PrintQueue(Queue &L);int i;char a;Queue L;initqueue(L);printf("请输入队列的个数：");int n;scanf("%d",&n);printf("请依次输入队列元素：n"); for(i=0;i<n;i+)scanf("%d",&L.pi);L.front=0;L.rear=n-1;printf("队列元素：");PrintQueue(L);int insert;printf("开始操作，请按y继续：");scanf("%s",&a);while(a='y')printf("是否进行入队操作:(是输入“y”)n");scanf("%s",&a);if(a='y')printf("请输入你要插入的数字：n");scanf("%d",&insert);enqueue(L,insert);printf("插入后的结果为：n");PrintQueue(L);printf("是否进行出队操作:（“是”则输入“y”,其他字符否n:");scanf("%s",&a);if(a='y')printf("删除的数字为：%dn",dequeue(L);printf("删除之后的队列为：n");PrintQueue(L); printf("继续？"); scanf("%s",&a);void initqueue(Queue &L)/初始化队列L.front=L.rear=-1;void enqueue(Queue &L,char item)/插入结点函数if(L.rear=(L.rear+1)%100)=L.front)printf("Queue overflow!");exit (0);elseL.pL.rear=item;int dequeue(Queue &L)/删除结点函数if(L.front=-1&&L.rear=-1)printf("Queue is empty!");exit (0);elseint temp=L.pL.front;L.front=L.front+1;return temp;void PrintQueue(Queue &L) int i; for(i=L.front; i<L.rear-L.front+1;i+)printf("%dn",L.pi);附录二：链表的运用代码Head.文件：struct LNode/*单链表结构*/ int num; struct LNode *next;void print(LNode *p);void compare(LNode *&pa,LNode *&pb);void programe_1();struct node int number; /* 猴子的数目 */ int cipher; struct node *next; /* 指向下一个节点的指针 */;struct node *CreatList(int num) ;void programe_2();typedef struct list2char data;int freq;struct list2 *pre,*next;DoubleNode;void print(DoubleNode *L);DoubleNode* Locate(DoubleNode *L,char x);void programe_3();main文件：#include "head.h"#include "stdio.h"#include <stdlib.h>int main(int argc,char *argv)int choice;doprintf("n顺序表的应用系统n");printf("n-主菜单-n");printf("(1) 比较并删除单链表中的元素.n");printf("(2) 猴子选大王.n");printf("(3)元素访问频率排序 .n"); printf("(0) 退出系统.n");printf("n请选择：");scanf("%d",&choice);if(choice<0 && choice>4) continue;switch(choice)case 1:programe_1();break;case 2:programe_2();break;case 3:programe_3();break; default:break;while(1);return 0;program1_1();#include<stdio.h>#include<stdlib.h>#include "head.h"void programe_1()void print(LNode *p);