数据结构上机实验任务书一和二

目 录实验1 顺序表的应用2实验2 链表的应用5实验3 栈的应用6实验4 队列的应用7实验5 树的应用9实验6 图的应用10实验7 图的应用11实验8 查找与排序120 实验要求一、实验步骤 问题分析充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。 数据结构设计针对要求解决的问题，考虑各种可能的数据结构，并且力求从中找出最佳方案(必须连同算法一起考虑)，确定主要的数据结构及全局变量。对引入的每种数据结构和全局变量要详细说明其功能、初值和操作特点。 算法设计算法设计分概要设计和详细设计，概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题.详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，采用类C语言描述。 测试用例设计准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。 上机调试对程序进行编译，纠正程序中可能出现的语法错误，测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。二、实验报告每次实验结束后，均应撰写实验报告。实验报告应包括如下内容： 1、问题描述：简述题目要解决的问题是什么。2、设计：概要设计采用抽象数据类型描述，详细设计包括存储结构的定义、主要操作算法设计等。用类C语言或用框图描述。3、调试报告：调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、运行结果。可以贴相应的运行结果截图。5、算法分析与改进：算法的时间复杂度和空间复杂度分析；算法改进的设想。6、经验和体会所有实验做完后，上交上机实验源程序和相应的运行结果截图。源程序要加注释。如果题目规定了测试数据，则截图结果要包含这些测试数据和运行输出，当然还可以含有其它测试数据和运行输出（有时需要多组数据）。三、实验学时16学时实验1 线性表的顺序存储结构实验目的1 熟悉C语言的上机环境，掌握使用VC环境上机调试线性表的基本方法；2 掌握线性表的顺序存储结构及其线性表的基本操作：插入、删除、查找等。3 掌握线性表合并等运算在顺序存储结构上的实现。实验要求1 认真阅读和掌握本实验的程序。2 上机运行程序，观察程序的运行结果。3 按照你对线性表的操作需要，重新改写主程序并运行。实验内容（基础题必做，应用题可选）1. 基础题：线性表基本操作的实现这个程序中演示了顺序表的创建、插入、删除和查找，（1）请修改并记录运行结果；（2）按照你自己对线性表测试的需要，增加新的操作，重新改写主程序并记录运行结果。#include #include /顺序表的定义#define ListSize 100typedef int ElemType;typedef structElemType *elem; /*存放表元素的空间基地址*/ int length;/*当前的表长度*/ int listsize; /*能容纳的最大元素个数*/SeqList;void CreateList(SeqList &L,int n);void PrintList(SeqList L,int n);int LocateList(SeqList L,int x);void InsertList(SeqList &L,int x,int i);void DeleteList(SeqList &L,int i);void main() SeqList L;int i,x;int n=10;/*THE LENGTH OF LIST*/L.length=0;clrscr();CreateList(L,n);/*CREATE THE LIST*/PrintList(L,n);/*PRINT THE LIST*/printf(INPUT THE SEARCH ELEMENT);scanf(%d,&x);i=LocateList(L,x);printf(the search position is %dn,i);/*顺序表查找*/printf(input the position of insert:n);scanf(%d,&i);printf(input the value of insertn);scanf(%d,&x);InsertList(L,x,i);/*顺序表插入*/PrintList(L,n);/*打印顺序表*/printf(input the position of deleten);scanf(%d,&i);DeleteList(L,i);/*顺序表删除*/PrintList(L,n);getch();/*打印顺序表*/*顺序表的建立：*/void CreateList(SeqList &L,int n)L. elem =(ElemType *)malloc(ListSize *sizeof(ElemType);if(!L.elem) exit(0);L.listsize= ListSize;int i;printf(please input n numbersn);for(i=1;i=n;i+)scanf(%d,&L. elem i);L.length=n;/*顺序表的打印：*/void PrintList(SeqList L,int n)int i;printf(the sqlist isn);for(i=1;i=n;i+)printf(%d ,L.elem i);/*顺序表的查找：*/int LocateList(SeqList L,int x)int i;for(i=1;ilength;j=i;j-)L- elem j+1=L- elem j;L- elem i=x;L.length+;/*顺序表的删除：*/void DeleteList(SeqList &L,int i) int j;for(j=i;j=(L.length)-1;j+)L. elem j=L. elem j+1;2.应用题（1）学生成绩管理本题目是对学生成绩管理的简单模拟，用菜单选择方式完成下列功能：输入学生数据；输出学生数据；学生数据查询；添加学生数据；修改学生数据；删除学生数据。本题目的数据是一组学生的成绩信息，每条学生的成绩信息由学号、姓名和成绩组成。（2）考试报名管理本项目是对考试报名管理的简单模拟，用菜单选择方式完成下列功能：输入考生信息；输出考生信息；查询考生信息；添加考生信息；修改考生信息；删除考生信息。本题目的数据是一组考生信息，每条考生信息由准考证号、姓名、性别、年龄、报考类别等信息组成。实验2 链表的应用实验目的1 定义单链表的结点类型。2 熟悉对单链表的一些基本操作和具体的函数定义。3 通过单链表的定义掌握线性表的链式存储结构的特点。4 熟悉单链表的应用场合。实验要求1 独立完成；2 准备好测试数据，程序调试正确，有执行结果。实验内容（基础题必做，应用题任选）1、基础题：按照教材中抽象数据类型线性表的定义，演示单链表的基本操作，按照自己的意图编写基本操作函数和主函数进行测试。示例：这个程序演示了单链表的创建和插入操作。程序如下：#include #includetypedef int ElemType;typedef struct node ElemType data; struct node *next; NODE;typedef NODE *LinkList;/*/LinkList Create()NODE *p,*head;int x;head=(NODE *)malloc(sizeof(NODE);head-next=NULL;printf(Input data,-1 to End!n);scanf(%d,&x);while(x!=-1) p=(NODE *)malloc(sizeof(NODE); p-data=x; p-next=head-next; head-next=p; scanf(%d,&x);return(head);/*/void Output(LinkList head) NODE *p; p=head; printf(Begin to dump the LinkList.n); while(p-next!=NULL) printf(-%d,p-next-data); p=p-next; printf(nThe LinkList ended!n);/*/int Listlen(LinkList head) int i=0; NODE *p=head; while(p-next!=NULL) i+; p=p-next; return(i);/*/void Ins(LinkList head,int i,int e)NODE *p=head,*q;int j=0;while(p-next&jnext;if(!p-next&ji-1) printf(Wrong positionn );else q=(NODE *)malloc(sizeof(NODE); q-data=e; q-next=p-next; p-next=q;/*/main() LinkList head; int length; int i,element; clrscr(); head=Create(); Output(head); length=Listlen(head); printf(the length of the link is %dn,length); printf(Input the insert position and element:n); scanf(%d%d,&i,&element); Ins(head,i,element); Output(head); getch();2、应用题：（1）约瑟夫生者死者游戏： 30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人开始，依次报数，数到第9人，便把他投入大海中，然后从他的下一个人数起，数到第9人，再将他投入大海，如此循环，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。本游戏的数学建模如下：假设n个旅客排成一个环形，依次顺序编号1，2，n。从某个指定的第1号开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。这个过程一直进行到剩下k个旅客为止。本游