当前位置：文档之家 › 数据结构实验指导书

数据结构实验指导书

  • 格式：doc
  • 大小：107.00 KB
  • 文档页数：16

数据结构与算法 课程简介：本课程总学时需要64学时,其中实验课10学时,共有5个实验,每个实验为2学时,从其中的7个实验选其中的5个。 本课程的先行课为《C++程序设计》

实验一 线性表及其应用 一、实验目的 1、掌握用上机调试线性表的基本方法； 2、掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。 二、实验环境 硬件：PC 微型计算机、256M以上内存，40G以上硬盘。 软件：Windows XP，VC或VS.Net 三、实验内容 线性表基本操作的实现 当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。

四、实验步骤 1、 本实验的程序清单如下。 下面只是根据实验指导书上的程序，各位同学要按照实际上机调试后的结果程序附上： typedef Null 0; typedef int datatype; #define maxsize 1024; typedef struct { datatype data[maxsize]; int last; }sequenlist; int insert(L, x, i) sequenlist *L; int i; { int j; if ((*L).last= =maxsize-1) { printf(“overflow”); return Null; } else if ((i<1)‖(i>(*L).last+1) { printf(“error”); return Null; } else { for(j=(*L).last; j>=i-1; j--) (*L).data[j+1]=(*L).data[j]; (*L).data[i-1]=x; (*L).last=(*L).last+1; } return(1); } int delete(L,i) sequenlist *L; int i; { int j; if ((i<1)‖(i>(*L).last+1)) {printf (“error”); return Null; } else { for(j=i, j<=(*L).last; j++) (*L).data[j-1]=(*L).data[j]; (*L).data - -; } return(1); } void creatlist( ) { sequenlist *L; int n, i, j; printf(“请输入n个数据\n”); scanf(“%d”,&n); for(i=0; i{ printf(“data[%d]=”, i); scanf (“%d”, (*L).data[i]); } (*L).last=n-1; printf(“\n”); } printout (L) sequenlist *L; { int i; for(i=0; i<(*L).last; i++) { printf(“data[%d]=”, i); printf(“%d”, (*L).data[i]); } } void main( ) { sequenlist *L; char cmd; int i, t; clscr( ); printf(“i, I„..插入\n”); printf(“d,D„..删除\n”); printf(“q,Q„„退出\n”); do { do { cmd =getchar( ); } while((cmd!=‘d’)‖(cmd!=‘D’) ‖(cmd!=‘q’) ‖ (cmd!=‘Q’) ‖(cmd!=‘i’) ‖(cmd!=‘I’)); switch (cmd) { case ‘i’,‘I’; scanf(&x); scanf(&i); insert(L, x, i); printout(L); break; case ‘d’,‘D’; scanf(&i); delete(L, i); printout(L); break; } } while ((cmd!=‘q’)&&( cmd!=‘Q’)); } 2、 本程序运行的结果如下： 根据各位同学的实际调试数据编写。 3、 结合以上程序如何进行分析和改进。并把分析和改进的内容附上。

五、实验小结 实验过程中的体会和收获。 六、实验思考题与练习 线性表的非顺序存储结构如何实现？链表是如何操作的？模仿线性表的顺序存储结构的实验编写线性表的非顺序存储结构的实验报告并进行相应的实验。 实验二 栈的基本操作 一、 实验目的 1．掌握栈的基本操作： 2．初始化栈、判栈为空、出栈、入栈等运算。 二、实验要求 1． 认真阅读和掌握本实验的算法。 2． 上机将本算法实现。 3． 保存和打印出程序的运行结果，并结合程序进行分析。 三、实验内容 利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为： 1、定义栈的顺序存取结构 2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3、定义一个函数用来实现上面问题： 十进制整数X和R作为形参 初始化栈 只要Ｘ不为０重复做下列动作 将Ｘ％Ｒ入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素

四、实验思考题与练习 1、如何实现队列的操作 2、利用栈实现数学表达式的转换 3、迷宫问题 选择一个以上题目进行实验，并编写实验报告 实验三、队列应用—迷宫问题 一、 实验内容 n*m迷宫是一个矩形区域，（1，1）为入口（n，m）为出口，0表示该方格可通过，1表示该方格有阻碍不能通过，每次只能从一个无障碍方格向其周围8各方向的邻接任一无障碍方格移动一步，问，当迷宫有解时如何寻找一条由入口到出口的路径并返回这个序列，或者不能连通时给出无解标志。迷宫如下表所示。

一个带边界哨的10×15迷宫 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

二、 实验要求 ① 提出思想 ② 给出算法 ③ 程序设计 ④ 给定一个迷宫表，列出运行结果 三、 实验目的 通过实验，同学掌握队列数据结构在算法中的深入应用方法，这是宽度优先的搜索过程中使用队列结构的典型应用 实验四 二叉树的操作 一、实验目的 1、进一步掌握指针变量、动态变量的含义； 2、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围； 3、掌握用指针类型描述、访问和处理二叉树的运算。

二、 实验要求 1． 认真阅读和掌握本实验的程序。 2． 上机运行本程序。 3． 保存和打印出程序的运行结果，并结合程序进行分析。 4． 按照你二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 三、实验内容 已知以二叉链表作存储结构，试编写按层次顺序遍历二叉树的算法。 算法思想：本算法要采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的。 程序实现： #define M 100 #define Null 0 typedef struct node { int data; stuuct node *lchild, *rchild; } bitree; bitree *que[M]; int front=0, rear=0; bitree *creat( ) { bitree *t; int x; scanf (“%d”, &x); if (x= =0) t=Null; else { t=malloc(sizeof(bitree)); t→data=x; t→lchild=creat( ); t→rchild=creat( ); } return t; } void inorder( t ) bitree *t; { if (t!=Null) { inorder (t→lchild);

合集下载

数据结构实验报告(C语言)(强力推荐)

数据结构实验报告(C语言)(强力推荐)

数据结构实验实验内容和目的：掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。

学习基本的查找和排序技术。

让我们在实际上机中具有编制相当规模的程序的能力。

养成一种良好的程序设计风格。

实验教材：数据结构题集（C语言版）清华大学出版社2007年实验项目：实验一、栈和循环队列㈠、实验内容：①栈掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。

本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所有栈里的元素四个功能。

②循环队列掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。

本程序具有初始化一个队列、入队、出队、显示队列的所有元素、队列长度五个功能。

㈡、实验代码①栈程序代码：#include <stdio.h>#include <malloc.h>#define Stack_Size 6#define ERROR 0#define OK 1typedef int SElemType;typedef struct SNode{SElemType data;struct SNode *next;}SNode,*LinkStack;int CreatTwo(LinkStack &head,int n){int i;SNode *p;head=(LinkStack)malloc(sizeof(SNode));head->next=NULL;printf("请输入数据(数字):\n");for(i=n;i>0;--i){p=(SNode *)malloc(sizeof(SNode));scanf("%d",&p->data);p->next=head->next;head->next=p;}return 1;}int menu_select(){int sn;for(;;){scanf("%d",&sn);if(sn<1||sn>6)printf("\n\t输入错误，请重新输入\n");elsebreak;}return sn;}int Push(LinkStack &top,SElemType e){SNode *q;q=(LinkStack)malloc(sizeof(SNode));if(!q){printf("溢出!\n");return(ERROR);}q->data=e;q->next=top->next;top->next=q;return(OK);}int Pop(LinkStack &top,SElemType &e){SNode *q;if(!top->next){printf("error!\n");return(ERROR);}e=top->next->data;q=top->next;top->next=q->next;free(q);return(OK);}void main(){ int e;LinkStack top;printf("1.初始化一个栈;\n2.PUSH;\n3.POP;\n4.显示所有栈里的元素;\n5.结束;\n");while(1){switch(menu_select()){case 1:if(CreatTwo(top,Stack_Size))printf("Success!\n");break; case 2:printf("Push:\n");scanf("%d",&e);if(Push(top,e))printf("Success!\n");break;case 3:if(Pop(top,e))printf("Success!\n");printf("%d\n",e);break;case 4:LinkStack p;printf("所有栈里的元素:\n");p=top;while(p->next){p=p->next;printf("%7d",p->data);}printf("\n");break;case 5:return;}}}运行结果：②循环队列程序代码：#include<stdlib.h>#include<stdio.h>#define OVERFLOW -1#define OK 1#define ERROR 0#define MAXSIZE 100typedef struct{int *elem;//队列存储空间int front;int rear;}SqQueue;//判断选择是否正确int menu_select(){int sn;for(;;){scanf("%d",&sn);if(sn<1||sn>6)printf("\n\t输入错误，请重新输入\n");elsebreak;}return sn;}//参数(传出)SqQueue &Q,循环队列(空)int InitQueue(SqQueue &Q){Q.elem=(int *)malloc(MAXSIZE*sizeof(int));if(!Q.elem)exit(OVERFLOW);Q.front=Q.rear=-1;for(int i=0;i<MAXSIZE;i++)Q.elem[i]=-1;return OK;}//返回Q的元素个数int QueueLength(SqQueue Q){return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;}//显示队列的元素void Display(SqQueue Q){for(int i=0;i<=QueueLength(Q);i++)if(Q.elem[i]!=-1)printf("%d ",Q.elem[i]);printf("\n");}//入队int EnQueue(SqQueue &Q,int e){Q.rear=(Q.rear+1)%MAXSIZE;if(Q.rear==Q.front)return ERROR;Q.elem[Q.rear]=e;return OK;}//出队int DeQueue(SqQueue &Q,int &e){if(Q.front==Q.rear)return ERROR;e=Q.elem[Q.front+1];Q.elem[Q.front+1]=-1;Q.front=(Q.front+1)%MAXSIZE;return OK;}void main(){SqQueue Q;InitQueue(Q);int elem,e;printf("请输入队列元素(以0结束):\n");scanf("%d",&elem);while(elem!=0){EnQueue(Q,elem);scanf("%d",&elem);}printf("队列为：\n");Display(Q);printf("1.初始化一个队列;\n2.入队;\n3.出队;\n4.显示队列的所有元素;\n5.队列长度:\n6.结束;\n");while(1){switch(menu_select()){case 1:printf("请输入队列元素(以0结束):\n");scanf("%d",&elem);while(elem!=0){EnQueue(Q,elem);scanf("%d",&elem);}printf("队列为：\n");Display(Q);fflush(stdin);break;case 2:scanf("%d",&elem);EnQueue(Q,elem);printf("队列为：\n");Display(Q);fflush(stdin);break;case 3:DeQueue(Q,elem);printf("队列为：\n");Display(Q);break;case 4:printf("\n队列的所有元素:\n");Display(Q);break;case 5:printf("%d\n",QueueLength(Q));break;case 6:return;}}}运行结果：实验二、数组㈠、实验内容：数组一般不做插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。

《数据结构》实验报告

《数据结构》实验报告

《数据结构》实验报告实验一一、实验目的及要求理解线性表的顺序存储结构；熟练掌握顺序表结构及其有关算法的设计；理解线性表的链式存储结构；熟练掌握动态链表结构及其有关算法的设计；根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法；深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时巩固对这两种结构的构造方法的理解。

二、实验环境硬件：计算机软件：Microsoft Visual C++三、实验内容1.以顺序表作存储结构，实现线性表的插入、删除；2.以单链表作存储结构，实现有序表的合并；3.利用栈（以顺序栈作存储结构）实现进制转换，并用队列（以链队列作存储结构）计算并打印杨辉三角。

四、源程序清单五、实验结果六、总结实验二一、实验目的及要求掌握二叉树的动态存储结构--二叉链表，掌握二叉树的三种遍历方法，会运用三种遍历的方法求解有关问题。

二、实验环境硬件：计算机软件：Microsoft Visual C++三、实验内容1.以二叉链表作存储结构，建立一棵二叉树；2.输出其先序、中序、后序遍历序列；3.求出它的深度；4.统计其叶子结点数四、源程序清单五、实验结果六、总结实验三一、实验目的及要求掌握图的存储结构及其建立算法，熟练掌握图的两种遍历算法及其应用。

二、实验环境硬件：计算机软件：Microsoft Visual C++三、实验内容1.以邻接矩阵法作存储结构，建立一个无向图；2.输出该图的深度优先搜索序列；3.输出该图的广度优先搜索序列；4. 设计算法求出该图的连通分量个数及边的数目。

四、源程序清单五、实验结果六、总结实验四一、实验目的及要求掌握顺序表的查找方法，尤其是折半查找方法。

掌握二叉排序树的查找算法。

二、实验环境硬件：计算机软件：Microsoft Visual C++三、实验内容1.建立一个顺序表，用顺序查找的方法对其实施查找；2.建立一个有序表，用折半查找的方法对其实施查找；3.建立一个二叉排序树，根据给定值对其实施查找；4.对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。

《数据结构》课程教学大纲(卓越班)

《数据结构》课程教学大纲(卓越班)

课程编号：（）《数据结构》课程教学大纲（Date Structure）总学时：（64）学分：（3）一、课程简介：1、课程性质：专业基础课2、开课学期：第三学期3、适用专业：电子信息工程卓越班4、课程修读条件：学生在学习本课程之前应当先学《C语言程序设计》，若具有离散数学和概率论的知识则能更好理解本课程中的某些内容。

5、课程教学目的：本课程是关于数据结构知识的一门课程，为我院电子信息工程本科专业卓越班方向专业基础课。

通过本课程的学习，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术，培养学生的数据抽象能力，引导学生数据类型的使用，为今后学习程序设计、嵌入式系统、设备驱动开发等作一些铺垫。

二、教学基本要求或建议：全程以多媒体教学为主，理论联系实际应用，通过实验来理解理论知识。

三、内容纲目及标准：（一）理论部分学时数（48）第一章绪论[教学目的] 掌握数据、数据结构和算法的基本概念；了解算法的描述；掌握算法的时间和空间分析。

[教学重点与难点]算法分析第一节引言第二节基本概念和术语第三节算法描述第四节算法分析第二章线性表[教学目的] 掌握线性表的逻辑结构；了解线性表的基本操作和顺序存储结构；掌握插入、删除和定位等操作在顺序表上的实现，掌握线性表的链式存储结构。

[教学重点与难点] 基本操作在顺序表上的实现，单、双链表第一节线性表及其逻辑结构第二节线性表的顺序存储结构第三节线性表的链式存储结构第四节线性表的应用第五节有序表第三章栈和队列[教学目的] 了解栈和队列的概念；掌握栈和队列的存储结构。

[教学重点与难点]栈和队列的存储结构第一节栈第二节队列第四章串[教学目的] 掌握串的基本操作；了解串的存储结构。

[教学重点与难点]串的模式匹配第一节串的基本概念第二节串的存储结构第三节串的模式匹配第五章递归[教学目的] 掌握递归的概念和实现原理；了解递归算法的设计。

大学数据结构教案模板(3篇)

大学数据结构教案模板(3篇)

第1篇课程名称：数据结构授课教师：[教师姓名]授课班级：[班级名称]授课时间：[具体日期]课时安排：[课时数]教学目标：1. 理解数据结构的基本概念和特点，掌握常见数据结构（如线性表、栈、队列、树、图等）的定义、存储结构和操作算法。

2. 能够运用所学知识设计、分析和实现各种数据结构，解决实际问题。

3. 培养学生的逻辑思维能力、抽象思维能力和编程能力。

教学重难点：1. 数据结构的基本概念和特点2. 常见数据结构的存储结构和操作算法3. 数据结构的应用和实现教学准备：1. 教师准备PPT、教材、实验指导书等教学资源2. 学生预习教材，了解数据结构的基本概念和特点教学过程：一、导入1. 引入数据结构的概念，阐述数据结构在计算机科学中的重要性。

2. 简要介绍本课程的教学目标、教学重难点和教学进度。

二、讲授新课1. 线性表a. 定义和特点b. 存储结构（顺序存储、链式存储）c. 操作算法（插入、删除、查找等）2. 栈a. 定义和特点b. 存储结构（顺序存储、链式存储）c. 操作算法（入栈、出栈、判断栈空等）3. 队列a. 定义和特点b. 存储结构（顺序存储、链式存储）c. 操作算法（入队、出队、判断队列空等）4. 树a. 定义和特点b. 常见树结构（二叉树、二叉搜索树、堆等）c. 操作算法（遍历、查找、插入、删除等）5. 图a. 定义和特点b. 存储结构（邻接矩阵、邻接表）c. 操作算法（图的遍历、最短路径、最小生成树等）三、课堂练习1. 学生根据所学知识，完成课后习题。

2. 教师选取典型题目进行讲解，帮助学生巩固所学知识。

四、实验指导1. 引导学生了解实验目的和实验内容。

2. 学生分组进行实验，教师巡回指导。

3. 学生完成实验报告，教师批改并给予反馈。

五、课堂小结1. 总结本节课所学内容，强调重点和难点。

2. 提出思考题，引导学生课后继续学习。

六、课后作业1. 完成课后习题，巩固所学知识。

2. 预习下一节课内容，为下一节课的学习做好准备。