数据结构程序

目录 目 录 TOC \o "1-3" \h \z \u 第一章 数据结构实验标准 1 1.1数据结构实验简述 1 1．1．1实验教学目的与任务 1 1．1．2课程实验的基本要求 1 1．1．3课程设计的基本要求和特点 1 1．1．4主要仪器设备 2 1.2课程设计实验报告 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 3 第二章 数据结构课程实验 4 2.1实验一 C语言难点和抽象数据类型 4 2.2实验二 线性 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 的顺利存储 9 2.3实验三 线性表的链式存储 16 2.4实验四 栈及栈的应用实验 19 2.5实验五 队列及队列应用实验 22 2.6实验六 串操作 25 2.7实验七 稀疏矩阵操作实验 27 2.8实验八 树及树的应用实验 28 2.9实验九 哈夫曼编/译码器 32 2.10实验十 图及图的操作实验 34 2.11实验十一 图的应用实验 36 2.12实验十二 查找算法实现实验 37 2.13实验十三 哈希表设计 38 2.14实验十四 排序算法实验 39 2.15实验十五 内部排序算法比较 40 2.16实验十六 文件 42 第三章 课程设计实验 43 3.1综合实验一 运动会分数统计 43 3.2综合实验二 约瑟夫环 44 3.3综合实验三 集合的并、交和差运算 45 3.4综合实验四 一元稀疏多项式计算器 46 3.5综合实验五 停车场管理 47 3.6综合实验六 离散事件模拟 48 3.7综合实验七 魔王语言解释 50 3.8综合实验八 马踏棋盘 51 3.9综合实验九 迷宫问题 52 3.10综合实验十 航空客运订票系统 53 3.11综合实验十一 文学研究助手 54 3.12综合实验十二 校园导游咨询 55 3.13综合实验十三 最小生成树问题 56 3.14综合实验十四 教学 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 编制问题 57 3.15综合实验十五 全国交通咨询模拟 58 3.16综合实验十六 图 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 管理 59 3.17综合实验十七 多关键字排序 61 参考文献 62 附录 63 附录1：课程实验报告示例 63 附录2：课程设计报告封面 74 第一章 数据结构实验标准 1.1数据结构实验简述 1．1．1实验教学目的与任务 《数据结构》是计算机相关专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法。它是学习操作系统、编译原理、数据库原理等计算机专业核心课程的基础，掌握好这门课程的内容，是学习计算机其他相关课程的必备条件,通过数据结构课程实验使学生更进一步了解数据结构的算法设计思想及实现方法, 并对在不同存储结构上实现不同的运算方法和技巧有所体会，从而达到锻炼学生理论与实践相结合的能力。 用计算机解决实际问题时，就要涉及数据的表示及数据的处理，而这正是数据结构课程的主要研究对象。通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的基础，同时也提供了必要的技能训练，逐步培养良好的标准的编程风格和编程习惯。 数据结构课程设计是对学生的一种全面综合训练，是与课堂听课、自学和联系相辅相成的必不可少的教学环节。它更着眼于原理与应用的结合点，使读者学会如何将所学知识用于解决实际问题，培养软件工作所需要的动手能力。 《数据结构》是一门实践性很强的专业基础课。主要任务： 1、本实验课程以验证基本理论为主，通过实验，使学生们建立起验证常用数据结构算法的方法步骤，着重培养学生的逻辑思维能力和动手能力，帮助学生加深对常用数据结构的理解，培养良好的实验习惯。 2、培养学生设计数据结构的能力和根据数据结构设计算法的能力，使学生掌握非数值问题的数据结构和算法的设计方法。 3、通过实验，进一步培养学生利用C语言进行编程和调试程序的能力，使学生能够利用C语言编写较复杂的程序。 4、课程设计要求学生运用数据结构中所学的概念和算法等基础知识，应用一种算法，完成一个系统的分析、设计与实现。 1．1．2课程实验的基本要求 1、熟练掌握C语言的编辑、编译、调试程序。 2、会书写类C语言的算法，并将算法转变为程序实现。 3、正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。 4、掌握算法的时间分析和空间分析的技术； 5、针对问题的特点选择合适的数据结构，设计实用高效的算法，提高算法 设计的能力和动手实验的技能。 6、本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚、正确易读，符合软件过程的规范，从而培养学生的数据抽象能力； 7、通过若干数据结构应用实例，引导学生学习抽象数据类型的使用，为今后学习面向对象的程序做一些铺垫。 1．1．3课程设计的基本要求和特点 从培养一个软件工作者所应具备的科学工作的方法和作风的角度出发，通过本次课程实践，需要学生针对一个具体的问题和要求，掌握并完成如下步骤： 1、 问题分析和任务定义 在进行设计之前，应该充分地分析和理解问题，明确题目要求做什么，限制条件是什么。对问题的描述应该避开算法和所涉及的数据类型，应对所需完成的任务作出明确的规定。 2、 数据类型和系统设计 分为逻辑设计和详细设计两个步骤实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各函数的伪码算法。作为逻辑设计的结果，应写出每个抽象数据类型的定义，各主要模块的算法，并画出模块之间的调用关系图；详细设计的结果是对数据结构的基本操作的规格说明作出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出函数形式的算法框架。 3、 编码实现和静态检查 要求程序的每行一般不要超过60个字符，每个函数体一般不超过40行，最长不超过60行，否则应分割成较小的函数；要控制if语句的深度。 上机之前静态检查是必不可少的。可以用一组测试数据手工执行程序，也可以通过阅读或给别人讲解自己的程序而深入全面地了解程序逻辑。 1．1．4主要仪器设备 PC机，VC++或BC++或TC软件环境。 1.2课程设计实验报告规范 实习报告需封面（见附录2），在开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容： 1. 需求分析 1） 说明小组成员的明确分工。 2） 运行环境（软、硬件环境）的描述 3）以无岐义的陈述程序设计的任务，强调的是程序要做什么？明确规定： （1）输入的形式和输入值的范围； （2）输出的形式； （3）程序所能达到的功能； （4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 2. 概要设计 说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调）关系。 3. 详细设计 实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法（伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序）；画出函数的调用关系图。 4. 调试分析 内容包括： （1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讲座和分析； （2）算法的时空分析（包括基本操作和其他算法的时间复杂度和窨复杂度的分析）和改进设想； （3）经验和体会等。 5. 用户使用说明 说明如何使用你编写的程序，详细列出每一步的操作步骤。 6. 测试结果 列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好如需求分析中所列。 7. 附录 带注释的源程序。如果提交源程序软盘，可以只列出程序文件名的清单。 在以下各实习单元中都提供了实习报告实例。值得注意的是，实习报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写（当然也可以应该最后用实验报告纸誊清或打印）。 第二章 数据结构课程实验 2.1实验一 C语言难点和抽象数据类型 班级： 姓名： 学号： 专业： 一、 实验目的： （1） 掌握指针、结构体的应用 （2） 熟悉抽象数据类型的表示和实现方法 （3） 利用time函数实现算法评价的事后统计方法 二、 实验内容： 1、 学会定义指针变量和使用指针变量 输入三个整数，按由大到小的顺序输出。 #include Swap(int *p1,int *p2) { int p; ___________; ___________; ___________; } main() {int n1,n2,n3; int *p1,*p2,*p3; printf(“请输入三个整数：n1,n2,n3\n”); scanf(“%d,%d,%d”,_________); p1=&n1; p2=&n2; p3=&n3; if (n1 #include #define MAX 20 /*定义字符串的最大长度*/ #define n 10 /*定义字符串的个数*/ void sort(char *pstr[], int n1) /*冒泡法排序*/ {int i,j; char *p; for (i=0;i0) { __________________; __________________; __________________; } } } 试分析sort的时间复杂度：O（）； void main() { int i; char * pstr[n],str[n][MAX]; for (i=0;i max(int x,int y) { if (x>y) return x; else return y; } void main() { int (*p)();/*p是一个指向函数的指针变量，此函数带回整型的返回值*/ int a,b,c; p=max; /*将函数max的入口地址赋给指针变量P*/ scanf("%d,%d",&a,&b); c=(*p)(a,b); /*通过函数指针来调用函数max*/ printf("a=%d,b=%d,max=%d",a,b,c); } 设计一个函数qzz,在调用该函数时可以实现不同的功能，如输入两个整数a和b，第一调用qzz获得两个数中的最大值，第二次调用qzz获得两个数中的最小值，第三次调用qzz获得两个数的乘积。 #include void main() {int max(),min(),mul(),qzz();/*声明*/ int a,b; printf("input a,b:"); scanf("%d,%d",&a,&b); printf("max=%d\n",qzz(a,b,max)); printf("min=%d\n",____________); printf("mul=%d\n",____________); } int max(int x,int y) { return x>=y?x:y; } int min(int x,int y) { ________________; } int mul(int x,int y) { return x*y; } int qzz(int x,int y, int (*f)()) /*指向函数的指针变量作为函数的参数的用法*/ { __________________________; } 粘贴测试数据及运行结果： 4.[问题描述]：设计一个可进行复数运算的演示程序。 [基本要求]： ---复数存储结构的定义 typedef struct{ float realpart; float imagpart; }complex; ---基本操作说明 void Assign(complex &z,float realval,float imagval) //操作结果：构造一个复数，并为实部和虚部赋值。 float GetReal(complex z) //初始条件：Z已存在 //操作结果：获得Z的实部。 float Getimag(complex z) //初始条件：Z已存在 //操作结果：获得Z的虚部。 void add(complex z1,complex z2,complex &sum) //操作结果：由sum返回Z1+Z2的结果。 void substract(complex z1,complex z2,complex &sub) //操作结果：由sub返回Z1-Z2的结果。 void mult（complex z1,complex z2,complex &mul） //操作结果：由mul返回z1*z2的结果。 void conjugate(complex z1,complex &con) //操作结果：由con返回z1的共轭复数。 [用C语言（也可以用C++）加以实现] #include typedef struct{ float realpart; float imagpart; }complex; ----实现未完成的函数 void Assign(complex *z,float realval,float imagval) { } float GetReal(complex z) { return z.realpart; } float Getimag(complex z) { return z.imagpart; } void add(complex z1,complex z2,complex *sum) { } void substract(complex z1,complex z2,complex *sub) { } void mult（complex z1,complex z2,complex *mul） { } void conjugate(complex z1,complex *con) { } -----自定义main() void main() { } [测试数据] （1）Z1=0，Z2=0； （2）Z1=4.1，Z2=3.1+3.5i； （3）Z1=3+1.5i，Z2=8-1.5i； （4）Z1=-4+3.4i，Z2=-6-8.1i； （5）Z1=-5.4+1.2i，Z2=5.4+3.2i； [粘贴测试结果] Z1+z2： Z1-z2： z1*z2： Z1的共轭复数： 5. 算法事后统计分析方法，利用time()进行。 实例：统计5,000,000，00次空的for循环的时间，单位是秒。 （时间和日期函数需要头部,这个头部定义了与时间有关的三种类型Clock_t,time_t,tm。） #include #include int main(void) { time_t start,end; volatile long unsigned t;//volatile 可变的 start=time(NULL); for(t=0;t<500000000;t++); end=time(NULL); printf("loop used %f seconds.\n",difftime(end,start)); return 0; } 三、 心得体会：（含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程的心得） 2.2实验二 线性表的顺利存储 班级： 姓名： 学号： 专业： 1、​ 实验目的： （1）​ 掌握顺序表的基本操作的实现方法。 （2）​ 应用顺序表的基本算法实现集合A=AUB、A=AU（B-A）算法。 2、​ 实验内容： 1、线性表顺序存储结构的基本操作算法实现 [实现提示] （同时可参见教材p22-p25页算法） 库函数载和常量定义： #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; （1）线性表顺序存储结构的定义： #define INIT_SIZE 100 /*初始分配空间的大小*/ #define LISTINCREMENT 10 /*分配增量*/ typedef int ElemType; typedef struct{ ElemType *elem; int length; int listsize; }SqList; /*ElemType elem[INIT_SIZE],注两者区别。存储空间的起始地址。*/ /*线性表中数据元素个数，即表长*/ /*线性表所申请的存储空间的大小*/ （2）初始化线性表算法 SqList CreateList_Sq(SqList L) /*创建一个空的线性表*/ { L.elem=(ElemType *)malloc(INIT_SIZE*sizeof(ElemType)); if (!L.elem) exit(ERROR); L.length=0; /*表长为0*/ L.listsize=INIT_SIZE; /*申请的空间为初始大小*/ return L； } 或者： status InitList_Sq(SqList *L) /*创建一个空的线性表*/ { L->elem=(ElemType *)malloc(INIT_SIZE*sizeof(ElemType)); if (!L->elem) exit(ERROR); L->length=0; /*表长为0*/ L->listsize=INIT_SIZE; /*申请的空间为初始大小*/ Return OK; } （3）在线性表的第i个位置前插入元素e算法 SqList InsertList_Sq(SqList L, int i,ElemType e) /*在线性表的第i个位置前插入元素e*/ { if (i<1||i>L.length+1) {printf("i值不合法!\n");exit(ERROR);} if (L.length>=L.listsize) /*当前空间已满，增加分配空间*/ { newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTCREMENT)*sizeof(ElemType)); if (!newbase) exit(ERROR); L.elem=newbase; L.listsize+=LISTCREMENT; } for (j=L.length;j>=i;j--) L.elem[j]=L.elem[j-1]; L.elem[i-1]=e; L.length++; return L; } 或者： Status InsertList_Sq(SqList *L, int i, ElemType e) /*在线性表的第i个位置前插入元素e*/ { ElemType * newbase; if (i<1||i>L.length+1) {printf("i值不合法!\n");exit(ERROR);} if (L->length>=L->listsize) /*当前空间已满，增加分配空间*/ { newbase=(ElemType *)realloc(L->elem,(L->listsize+LISTCREMENT)*sizeof(ElemType)); if (!newbase) exit(ERROR); L->elem=newbase; L->listsize= L->listsize+LISTCREMENT; } for (j=L->length;j>=i;j--) L->elem[j]=L->elem[j-1]; L->elem[i-1]=e; L->length++; return OK; /* q=&(L.elem[i-1]); //q为插入位置（用地址来表示） for(p=&(L.elem[L->length-1]);p>=q;--p) *(p+1)=*p; *q=e; L->length++; */ } （4）删除线性表中第i个元素算法 SqList DeleteList_Sq(SqList L, int i, ElemType *e) /* 删除线性表中的第i个元素，并获得所删元素的值*/ { if ((i<1)||(i>L.length)) {printf("i值不合法!\n");exit(ERROR);} *e=L.elem[i-1]; for(j=i;j<=L.length;j++) L.elem[j-1]=L.elem[j]; L.length--; return L; } 或者： Status DeleteList_Sq(SqList *L, int i, ElemType *e) /* 删除线性表中的第i个元素，并获得所删元素的值*/ { if ((i<1)||(i>L.length)) {printf("i值不合法!\n");exit(ERROR);} *e=L->elem[i-1]; for(j=i;j<=L->length;j++) L->elem[j-1]=L->elem[j]; L->length--; return OK; } （5）遍历线性表元素算法 void Print_Sq(SqList L) /*遍历顺序线性表*/ { int i; printf("The list:\n"); for(i=0;i #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef char ElemType; （1）线性表顺序存储结构的定义： typedef struct Lnode { ElemType data; //数据域 struct Lnode *next; //指针域 }Lnode, *LinkList; （2）初始化带头结点链式线性表算法 status LinkListini_L(LinkList &L) /*初始化一个带头结点的单链表*/ {} （3）在带头结点线性表的第i个位置前插入元素e算法 status ListInsert_L(LinkList &L,int i,ElemType e){} //在带头结点的单链表L中第i个位置之前插入元素e。p26 （4）在带头结点线性表删除第i个元素算法 status ListDelete_L(LinkList L,int i,ElemType &e) /*在带头结点的单链表L中删除第i个结点，并返回该结点的值。*/ {} （5）遍历线性表元素算法 status Print_L(LinkList L) /*遍历带头结点的链表*/ {} （6）逆位序输入n个元素的值，建立带表头结点的单链表算法 status creatList_L(LinkList &L,int n) /*逆位序输入n个元素的值，建立带表头结点的单链表*/ （7）返回线性链表L中第1个与e满足函数compare()判定关系的元素的位置。 LinkList LocateElem(LinkList L,ElemType e, int (*compare)(ElemType,ElemType)){}; （8）求链式线性表的长度算法。 int ListLength_L(LinkList L){} （9）判链式线性表表空算法 int EmptyL(LinkList L){} (10)上机实现以上基本操作，写出main()程序： 实例： void main() {} 粘贴测试数据及运行结果： 2、用以上基本算法，实现：La,Lb为非递减的有序线性表，将其归并为Lc，该线性表仍有序（未考虑相同时删除一重复值）的算法。 status MergeList_L(LinkList La,LinkList Lb,LinkList &Lc) //按值排序的单链表LA,LB，归并为LC后也按值排序 { } main() { } 粘贴测试数据及运行结果： 3、按一元多项式ADT的定义，实现相关操作算法： ADT Polynomial{ Data object:D={ai|ai∈TermSet,i=1,2,…,m,m≥0 TermSet中的每个元素包含一个表示系数的实数和表示指数的整数} 数据关系：R1={|ai-1,ai∈D,且ai-1中的指数值 #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define SINIT_SIZE 100 //存储空间初始分配量 #define conver 8 #define STACKINCREMENT 10 //存储空间分配增量 typedef int Status; typedef char SElemType; （1）栈顺序存储结构的定义： typedef struct{ SElemType *base; //在栈构造之前和销毁时，base=NULL. SElemType *top; //栈顶指针 int stacksize; //当前已分配的存储空间，以元素为单位。 }SqStack; （2）初始化栈算法 Status InitStack(SqStack *S) { //构造一个空栈S} （3）获得栈顶元素算法 Status GetTop(SqStack S,SElemType *e) {//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR} （4）进栈算法 Status Push(SqStack *S,SElemType e){ //插入元素e为新的栈顶元素} （5）出栈算法 Status Pop(SqStack *S,SElemType *e){ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR} （6）遍历栈算法 Status print(SqStack S) {//遍历栈} （7）销毁栈算法 Status DestroyStack(SqStack *S) {//销毁栈S，S不再存在} （8）清空栈算法 Status ClearStack(SqStack *S){} （9）判栈空算法 Status StackEempty(SqStack S) {//判空} (10)求栈长 int StackLength(SqStack S) {} (11)上机实现以上基本操作，写出main()程序： 实例： void main() {} 粘贴测试数据及运行结果： 2、用以上基本算法，实现：void conversion() {//对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数；} void main() { } 粘贴测试数据及运行结果： 3、回文是指正读反读均相同的字符序列，如“acdca”、“dceecd”均是回文，但“book”不是回文。利用1中的基本算法，试写一个算法判定给定的字符向量是否为回文。（提示，将一半字符向量入栈） Status HuiWen(char *s) { } void main() { } 粘贴测试数据及运行结果： 选做题： 1、按栈顺序存储的基本操作，实现栈的链式操作算法。 2、参考p52-p54页，实现表达式求值EvaluateExpression()算法。 三、心得体会：（含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程的心得） 2.5实验五 队列及队列应用实验 班级： 姓名： 学号： 专业： 2、​ 实验目的： （1）掌握递归的基本思想。 （2）掌握链式队列及循环队列的基本操作算法。 （3）应用队列先进先出的特点，解决一些实际问题。 二、 实验内容： 1、 p(a-b，b)+1 当a>=b p(a,b)= 其中a,b为正整数。 0 当adata=ch; T->lchild=NULL; T->rchild=NULL;//99 q[w++]=T; scanf("%c",&ch); while(ch!='@') { n=n%2; if (ch!='#') { p=(BiTree)malloc(sizeof(BiTNode)); p->data=ch; p->lchild=NULL; p->rchild=NULL; //99 q[w++]=p; n++; if (n==1) {k=q[f];k->lchild=p;} else if(n==2) {k=q[f++];k->rchild=p;} }else {p=NULL; n++; if (n==1) {k=q[f];k->lchild=p;} else if(n==2) {k=q[f++];k->rchild=p;} } scanf("%c",&ch); }//while }//1 return T; }//LevelOrder 测试算法结果如下： 空树 仅有一个结点树 一般的普通的二叉树 给出数据输入的序列。 试分析，上列算法的基本算法思想，试问//99这句没有，数据的输入序列应如何？ 3、​ 实验心得（含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程的心得） ——二叉树非递归及递归操作算法（之二） 班级： 姓名： 学号： 专业： 一、 实验目的： 1、掌握二叉树创建的非递归算法 2、掌握二叉树遍历的非递归算法 3、掌握二叉树的其它操作算法 二、 实验内容： 1、二叉树数据结构表示及基本操作算法实现 [实现提示] （同时可参见教材p126-p131页算法） 库函数和常量定义： （1）二叉树存储结构定义： 自定义如下：（可自已定义） （2）二叉树递归遍历算法 4）​ 先序非递归遍历 算法如下： 5）​ 中序非递归遍历 算法如下： 6）​ 后序非递归遍历 算法如下： 测试结果粘贴如下： （3）二叉树创建非递归算法 按前序遍历实现二叉树创建的非递归算法 算法如下： 测试结果粘贴如下： （4）求二叉树的深度递归算法 算法如下： 测试结果粘贴如下： （5）求二叉树的结点数递归算法 算法如下： 测试结果粘贴如下： （6）求二叉树的叶子数递归算法 算法如下： 测试结果粘贴如下： (7)求两颗二叉树的相似 递归算法提示： 1）若T1和T2均为空，则返回值为1； 2）若T1和T2的深度均为1（即只有一个结点