当前位置：文档之家 › 《数据结构》课程设计试验报告

《数据结构》课程设计试验报告

  • 格式：doc
  • 大小：196.00 KB
  • 文档页数：11

《数据结构》课程设计 实验报告

题 目 约瑟夫问题和八皇后问题求解 学 院 数学与信息工程学院 专 业 计算机科学与技术 班 级 计科081 学 号 200853225142 学生姓名 陈哲 同组成员 魏艳舞 杨青 施晓洁 吴亚君 徐珍艳 张素姿 指导教师 刘小晶 编写日期 2009年6月28日 1

一、问题描述 1、约瑟夫问题描述 编号为1，2… n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。

2、八皇后问题描述 在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。

3、界面设计模块问题描述 设计一个菜单式界面，让用户可以选择要解决的问题，同时可以退出程序。界面要求简洁明了，大方得体，便于用户的使用，同时，对于用户的错误选择可以进行有效的处理。

二、问题分析 本人负责的是为用户设计菜单界面，使用户可以根据菜单进行选择其中的某个问题进行处理。对于一个菜单界面，首先要求界面简单明了，使得用户可以轻松通过界面知道如何获取自己想要的操作。其次，我们不能保证用户每次的选择都是有效的，即用户的选择是在我们提供的服务范围之内，所以要设计容错操作，即当用户的选择超出我们提供的范围时，提示用户重新选择。最后，要保证用户选择相应的操作后，程序能正确的按照用户的选择运行下去，完成用户的要求。

三、数据结构描述 Int choice; 记录用户的选择，然后选择相应的操作。

typedef struct LNode{ int num; int code; struct LNode *next; }node,*linklist; 单链表解决约瑟夫问题时储存结点信息

char a[9][9]; 八皇后问题中记录棋盘信息

四、算法设计 2

1、程序层次模块图 程序总层次模块图 2、算法设计 void jiemian() { printf(" the problem of people our of circlr\n"); printf(" ****************************************************\n"); printf(" * 1.solve by lianbiao; *\n"); printf(" * 2.solve by shunxubiao; *\n"); printf(" * 3.help; *\n"); printf(" * 4.ruturn to menu; *\n");

约瑟夫问题 八皇后问题 用链表解决 用顺序表解决 查看帮助 回到主菜单 主菜单 结束 建立顺序表并出列 建立单向循环链表 在单向链表中出列

棋盘初始化 判断能否安放皇后 递归安放

8皇

后 3

printf(" ****************************************************\n"); } void help() { printf(" the problem of people our of circlr\n"); printf("*******************************************************************************\n"); printf("* you can choise 1,2,3 or 4 to get the function you want.if you choise 1, *\n"); printf("* you will solve the problem by lianbiao.in this way,when a people out of *\n"); printf("* the circle,the node which contain his message will be deleted.if you *\n"); printf("* choise 2,you will solve the problem by shunxubiao.in this way,when a *\n"); printf("* people out of the circle,his code will change into 0,but his message *\n"); printf("* will be remained.if you choise 4,end the game. *\n"); printf("*******************************************************************************\n"); }

void welcome() { printf(" welcome to our system\n"); printf(" ****************************************************\n"); printf(" * 1.Joseph Central issues *\n"); printf(" * 2.Queen 8 *\n"); printf(" * 3.exit *\n"); printf(" ****************************************************\n");

} int main() { int choice; welcome(); printf(" please make your choice:"); scanf("%d",&choice); while(choice!=3) { switch(choice) { case 1:system("cls");Joseph();getch();break; case 2:system("cls");Queen();getch();getch();break; default:printf(" please chooose the right choice!");getch();getch();break; } system("cls"); 4

welcome(); printf(" please make your choice:"); scanf("%d",&choice); } }

五、详细程序清单 #include #include typedef struct LNode{ int num; int code; struct LNode *next; }node,*linklist; //数据结构声明

char a[9][9]; int total;

linklist creatstart(linklist L,int number) //建立单向循环链表 { int m,i; linklist s,p; s=L; for(i=1;i<=number;i++) { p=(linklist)malloc(sizeof(node)); if(!p) exit(0); p->num=i; printf("please input the code of number %d:",i); scanf("%d",&p->code); p->next=NULL; s->next=p; s=p; } s->next=L->next; return s; }

void chulie(linklist L,int number) //链表中的出列 { int turn,i,j; linklist p,s; printf("please input the start code:"); 5

scanf("%d",&turn); p=L; printf("the turn out of the circle is:"); for(i=1;i<=number-1;i++) { for(j=1;j<=turn-1;j++) p=p->next; printf("%d ",p->next->num); turn=p->next->code; s=p->next; p->next=s->next; free(s); } printf("%d ",p->next->num); printf("\n"); }

void lianbiao() //用单向循环链表解决约瑟夫问题 { int number; linklist L; L=(linklist)malloc(sizeof(node)); if(!L) exit(0); printf("please input the number of people:"); scanf("%d",&number); L=creatstart(L,number); chulie(L,number); }

void jiemian() //约瑟夫问题的界面 { printf(" the problem of people our of circlr\n"); printf(" ****************************************************\n"); printf(" * 1.solve by lianbiao; *\n"); printf(" * 2.solve by shunxubiao; *\n"); printf(" * 3.help; *\n"); printf(" * 4.ruturn to menu; *\n"); printf(" ****************************************************\n");

} void shunxubiao() //用顺序表解决约瑟夫问题 { int a[500]={0},i,code,number,shu; printf("please input the number of people:");

合集下载

数据结构课程实验报告(回文篇)

数据结构课程实验报告(回文篇)

数据结构课程实验报告要求实验题目：回文判断算法班级通信143姓名刘海波学号2014101114日期2015.6.17一、需求分析1．程序的功能；利用栈和队列的操作来实现对字符序列是否是一个回文序列的判断。

设计和验证入栈、出栈及入队、出队的算法。

2．输入输出的要求；从键盘读入一组字符序列，按输入顺序入队列到链式队列A中。

并将创建好的A队列中元素依次遍历，打印在屏幕上。

将字符序列从A队列出队列，压入到一个顺序栈中。

再将字符序列从顺序栈中出栈，入队到另一个链式队列B中。

将创建好的B队列中元素依次遍历，打印在屏幕上。

将A，B队列中的元素出队逐一比较，判断是否一致。

若一致则是回文，并将判定结果打印到屏幕上。

3.测试数据：输入一组字符串进行判断。

二、概要设计1．本程序所用的抽象数据类型的定义；typedef struct{char item[STACKSIZE];int top;}SqStack;typedef struct QNode{char data;struct QNode *next;}LQNode, *PQNode;typedef struct{PQNode front,rear;} LinkQueue;2．主程序的流程及各程序模块之间的层次关系。

从键盘上读取一个字符，同时存储在顺序栈与链队列之中，直到字符序列的最后一个字符为*停止插入。

在程序中设置了一个标志位flag，将输入的序列分别做入栈、出栈、入队、出队操作，若出栈与出队的数据完全一致，则将flag标志为1，否则为零。

Flag 为1，则表示该序列是回文序列，否则，为非回文序列。

三、详细设计1．采用c语言定义相关的数据类型；typedef struct{char item[STACKSIZE];int top;}SqStack;typedef struct QNode{char data;struct QNode *next;}LQNode, *PQNode;typedef struct{PQNode front,rear;} LinkQueue;2．写出各模块的伪码算法；int InitStack(SqStack *S)int StackEmpty(SqStack S)int Push(SqStack *s, char data)int Pop(SqStack *s, char *data)int InitQueue(LinkQueue *q)int QueueEmpty(LinkQueue q)int EnQueue(LinkQueue *q, char item)int DeQueue(LinkQueue *q, char *item)int PutOutQueue(LinkQueue q)四、调试分析1．调试中遇到的问题及对问题的解决方法；对于语句中的一般回文单词能正常输出，句末跟标点符号连在一起的回文单词也能通过程序把字符串末尾的标点给去掉并正常输出，而字符串中的连接符可以作为回文单词的组成部分一起输出。

《数据结构》实验报告模板(附实例)--实验一线性表的基本操作实现

《数据结构》实验报告模板(附实例)--实验一线性表的基本操作实现

《数据结构》实验报告模板(附实例)---实验一线性表的基本操作实现实验一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现，其中以熟悉各种链表的操作为重点。

2、巩固高级语言程序设计方法与技术，会用线性链表解决简单的实际问题。

二、实验内容√ 1、单链表的表示与操作实现 ( * )2、约瑟夫环问题3、Dr.Kong的艺术品三、实验要求1、按照数据结构实验任务书，提前做好实验预习与准备工作。

2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。

3、严格按照数据结构实验报告模板和规范，及时完成实验报告。

四、实验步骤（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（成员函数）的伪码算法、函数实现、程序编码、调试与分析、总结、附流程图与主要代码）㈠、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、单链表的结点类型定义/* 定义DataType为int类型 */typedef int DataType;/* 单链表的结点类型 */typedef struct LNode{ DataType data;struct LNode *next;}LNode,*LinkedList;2、初始化单链表LinkedList LinkedListInit( ){ // 每个模块或函数应加注释，说明函数功能、入口及出口参数 }3、清空单链表void LinkedListClear(LinkedList L){// 每个模块或函数应加注释，说明函数功能、入口及出口参数}4、检查单链表是否为空int LinkedListEmpty(LinkedList L){ …. }5、遍历单链表void LinkedListTraverse(LinkedList L){….}6、求单链表的长度int LinkedListLength(LinkedList L){ …. }7、从单链表表中查找元素LinkedList LinkedListGet(LinkedList L,int i){ //L是带头结点的链表的头指针，返回第 i 个元素 }8、从单链表表中查找与给定元素值相同的元素在链表中的位置LinkedList LinkedListLocate(LinkedList L, DataType x){ …… }9、向单链表中插入元素void LinkedListInsert(LinkedList L,int i,DataType x) { // L 为带头结点的单链表的头指针，本算法// 在链表中第i 个结点之前插入新的元素 x}10、从单链表中删除元素void LinkedListDel(LinkedList L,DataType x){ // 删除以 L 为头指针的单链表中第 i 个结点 }11、用尾插法建立单链表LinkedList LinkedListCreat( ){ …… }㈡、函数调用及主函数设计（可用函数的调用关系图说明）㈢程序调试及运行结果分析㈣实验总结五、主要算法流程图及程序清单1、主要算法流程图：2、程序清单（程序过长，可附主要部分）说明：以后每次实验报告均按此格式书写。

数据结构实验报告

数据结构实验报告

数据结构实验报告一、实验目的数据结构是计算机科学中重要的基础课程，通过本次实验，旨在深入理解和掌握常见数据结构的基本概念、操作方法以及在实际问题中的应用。

具体目的包括：1、熟练掌握线性表（如顺序表、链表）的基本操作，如插入、删除、查找等。

2、理解栈和队列的特性，并能够实现其基本操作。

3、掌握树（二叉树、二叉搜索树）的遍历算法和基本操作。

4、学会使用图的数据结构，并实现图的遍历和相关算法。

二、实验环境本次实验使用的编程环境为具体编程环境名称，编程语言为具体编程语言名称。

三、实验内容及步骤（一）线性表的实现与操作1、顺序表的实现定义顺序表的数据结构，包括数组和表的长度等。

实现顺序表的初始化、插入、删除和查找操作。

2、链表的实现定义链表的节点结构，包含数据域和指针域。

实现链表的创建、插入、删除和查找操作。

（二）栈和队列的实现1、栈的实现使用数组或链表实现栈的数据结构。

实现栈的入栈、出栈和栈顶元素获取操作。

2、队列的实现采用循环队列的方式实现队列的数据结构。

完成队列的入队、出队和队头队尾元素获取操作。

（三）树的实现与遍历1、二叉树的创建以递归或迭代的方式创建二叉树。

2、二叉树的遍历实现前序遍历、中序遍历和后序遍历算法。

3、二叉搜索树的操作实现二叉搜索树的插入、删除和查找操作。

（四）图的实现与遍历1、图的表示使用邻接矩阵或邻接表来表示图的数据结构。

2、图的遍历实现深度优先遍历和广度优先遍历算法。

四、实验结果与分析（一）线性表1、顺序表插入操作在表尾进行时效率较高，在表头或中间位置插入时需要移动大量元素，时间复杂度较高。

删除操作同理，在表尾删除效率高，在表头或中间删除需要移动元素。

2、链表插入和删除操作只需修改指针，时间复杂度较低，但查找操作需要遍历链表，效率相对较低。

（二）栈和队列1、栈栈的特点是先进后出，适用于函数调用、表达式求值等场景。

入栈和出栈操作的时间复杂度均为 O(1)。

2、队列队列的特点是先进先出，常用于排队、任务调度等场景。

数据结构课程设计实验报告

数据结构课程设计实验报告

《数据结构》课程设计任务书学期：12-13-1 班级：软件111一、设计目的《数据结构》是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。

本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。

二、设计要求1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。

同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

2、学生必须仔细研读《数据结构》课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。

3、本次课程设计按照教学要求需要在三周时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。

4、编程语言任选。

三、设计选题说明：课程设计题目主要分为两大类：，主要是验证性题，少数是简单的综合性题，侧重考查学生对数据结构课程中重要数据结构和算法的理解与掌握程度，相对较简单；本类题目选题要求：要求个人所选题目必须独立完成；原则上不得参考别人的程序，若个人能力有限必须参考，参考成分不得超过30%，其中参考部分自己必须能消化吸收，否则视为无效；为培养学生分析问题、解决问题的实际动手能力和团队协作能力，鼓励有能力的学生尽可能选作难度较高的题目，故仅选作一星题目的学生，无论完成多少题目，原则上最高分不超出70分；仅选作一星和二星题目的学生，无论完成多少题目，原则上最高分不超出85分注意：上述题目，可以相互讨论，但严禁搭便车，杜绝拷贝或分享别人的劳动果实，坚决杜绝让别人代做。

一经发现、核实，无论是拷贝者或是被拷贝者的成绩均视为不及格，情节严重者将交由学工办通报批评并受到相应的纪律处分。