《数据结构》实验（三）
实验目的：
1、掌握栈的顺序存储结构的特点及算法描述。
2、掌握顺序栈的基本操作实现，熟悉应用方法。
3、掌握队列顺序存储结构的特点及算法描述
4、掌握顺序队列基本操作的实现，熟悉应用的方法。
实验课时：4课时
实验内容
1、在键盘上接收一串带括号的字符串，判断括号是否匹配，如果匹配，输出正确，如果不匹配，输出第一对不匹配的括号，并显示错误。例如：
{p{p})
输出
{ and }
{ and )
error
error
具体程序如下，请同学们仔细阅读，并在提示下，在有下划线的地方填上程序，#include "datastru.h"
#include "stdio.h"
void initstack(SEQSTACK *s)
/*顺序栈初始化*/
{ s->top = 0; }
DATATYPE1 sempty(SEQSTACK *s) /*判栈空*/
{ if(s->top== 0) return 1;
else return 0; }
int push(SEQSTACK *s, DATATYPE1 x)
/*元素x入栈*/
{ if(s->top == MAXSIZE - 1) {printf("栈满\n"); return 0;}
else {s->top++; (s->data)[s->top] = x; return 1;}
}
DATATYPE1 pop(SEQSTACK *s)
/*返回栈顶元素并删除栈顶元素*/
{DATATYPE1 x;
if(s->top == 0) { x = 0;}
else {x = (s->data)[s->top]; s->top--;}
return x;
}
DATATYPE1 gettop(SEQSTACK *s)
/*返回栈顶元素*/
{DATATYPE1 x;
if(s->top == 0) {printf("栈空\n"); x = 0;}
else x = (s->data)[s->top];
return x;
}
void check(SEQSTACK *s)
{
char ch,dh;
printf("\n请输入一串括号，回车键结束：");
ch = getchar();
while(ch != '\n')
{ if(ch=='('||ch=='['||ch=='{') //如果遇到左括号
{
push(s,ch); //把左括号入栈
}
if(ch==')'||ch==']'||ch=='}') //如果遇到右括号
{ //出栈，并把出栈的值赋给变量dh
if(sempty(s)) //如果栈为空
{
printf("缺失左括号！");
break; //跳出循环
}
dh=pop(s);
printf("%c和%c\n",dh,ch);
if(ch=='('&&dh!=")"||ch=='['&&dh!="]"||ch=='{'&&dh!="}") //如果dh和ch不匹配
{
printf("\n括号匹配错误\n");
break; //跳出循环
}
}
ch = getchar();
} /*继续处理*/
if(ch=='\n' && sempty(s)) //如果字符串结束并且栈为空
printf("\n括号配对正确\n");
if(sempty(s)==0) //如果栈不为空
printf("\n缺失右括号\n");
}
main()
{
SEQSTACK st, *s;
s = &st;
initstack(s);
check(s);
}
2、添加一个函数dTOb(),利用栈的原理实现十进制转换成二进制。#define DATATYPE1 int
#include "math.h"
#include "stdio.h"
#define MAXSIZE 100
typedef struct
{ DATATYPE1 data[MAXSIZE];
int top;
}SEQSTACK;
void initstack(SEQSTACK *s) /*初始化空栈*/
{ s->top = 0; }
int empty(SEQSTACK *s) /*判栈空*/
{ if(s->top == 0) return 1;
else return 0; }
int push(SEQSTACK *s, DATATYPE1 x) /*进栈*/
{ if(s->top == MAXSIZE - 1)
{ printf("Overflow\n");
return 0; }
else {s->top++;
s->data[s->top] = x;
return 1; }
}
DATATYPE1 pop(SEQSTACK *s) /*出栈*/
{ DATATYPE1 x;
if(empty(s)) { printf("Underflow\n");
x = NULL; }
else { x = (s->data)[s->top];
s->top--; }
return x;
}
int stacklen(SEQSTACK *s) /*计算栈中元素个数*/
{ return(s->top ); }
void output_stack(SEQSTACK *s) /*输出栈中元素*/
{int i;
printf("buttom:");
for(i=1;i<=s->top;i++)
printf("%d:",s->data[i]);
printf("top\n");
}
DATATYPE1 dTOb(DATATYPE1 x)
{int j,i,er=0;
if(x!=0)
{
for(i=1;x!=1;i++)
{
j=x%2;
x=x/2;
er+=j*pow(10,(i-1));
}
er+=1*pow(10,(i-1));
return er;
}}
main()
{ SEQSTACK s;
DATATYPE1 a;
int com,i,m,k;
initstack(&s); /*初始化空栈*/
do {printf("\n1:进栈2: 出栈3: 输出栈中元素4: 栈中元素个数5:十进制转二进制0:退出\n");
printf("enter a number(0-4):");
scanf("%d",&com);
switch(com) { case 1: p rintf(" enter a element:");
scanf("%d",&a);
push(&s,a);
output_stack(&s);
break;
case 2: a = pop(&s);
printf("pop :%d \n" ,a);
break;
case 3: output_stack(&s);
break;
case 4: printf("栈中有%d个元素\n",stacklen(&s));
break;
case 5: printf("请输入要转换的十进制数：");
scanf("%d",&k);
m=dTOb(k);
printf("二进制为：%d",m);}
} while(com!=0);
}
2、队列的相关操作
在循环队列中，队头指针和队尾指针在插入和删除中会发生移动而不确定，有时候Front在Rear之前，有时候Rear在Front之前，请同学们列出多种情况来输出队列。
// queueDisplay.java
// displays contents of queue
// to run this program: C>java DisplayApp
import java.io.*; // for I/O
////////////////////////////////////////////////////////////////
class Queue
{
private final int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
//--------------------------------------------------------------
public Queue(int s) //构造队列
{
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
//--------------------------------------------------------------
public void insert(long j) // 入队
{
if(rear == maxSize-1) // deal with wraparound
rear = -1;
queArray[++rear] = j; // increment rear and insert
nItems++; // one more item
}
//--------------------------------------------------------------
public long remove() // 出队
{
long temp = queArray[front++]; // get value and incr front
if(front == maxSize) // deal with wraparound
front = 0;
nItems--; // one less item
return temp;
}
//--------------------------------------------------------------
public long peekFront() //显示队头的第一个元素
{ return queArray[front]; }
//--------------------------------------------------------------
public boolean isEmpty() // 判断队列是否为空
{ return (nItems==0); }
//--------------------------------------------------------------
public boolean isFull() // 判断队列是否为满
{ return (nItems==maxSize); }
//--------------------------------------------------------------
public void display()
{
System.out.print("Array: ");
for(int j=0; j System.out.print( queArray[j] + " " ); System.out.println(""); System.out.print("Queue: "); if( isEmpty() == false ) // 输出队列元素 ｛if(___________) // 如果front指针在Rear指针之前for(_______________________) System.out.print( queArray[j] + " "); else { // 分开输出队列 for(________________________) System.out.print( queArray[j] + " "); for(________________________) System.out.print( queArray[j] + " "); } ｝ System.out.println("\n"); } // end display() //-------------------------------------------------------------- } // end class Queue //////////////////////////////////////////////////////////////// class DisplayApp { public static void main(String[] args) throws IOException { Queue theQueue = new Queue(5); // queue holds 5 items long value; while(true) { System.out.print("Enter first letter of "); System.out.print("show, insert, remove: "); int choice = getChar(); switch(choice) { case 's': theQueue.display(); break; case 'i': if( !theQueue.isFull() ) { System.out.print("Enter value to insert: "); value = getLong(); theQueue.insert(value); theQueue.display(); } else System.out.print("*** Queue is full ***\n"); break; case 'r': if( !theQueue.isEmpty() ) { value = theQueue.remove(); System.out.println("Removed " + value); theQueue.display(); } else System.out.print("*** Queue is empty ***\n"); break; default: System.out.print("Invalid entry\n"); } // end switch } // end while } // end main() // ------------------------------------------------------------- public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; } // ------------------------------------------------------------- public static char getChar() throws IOException { String s = getString(); if(s.length() == 0) // if immediate Enter return '#'; else return s.charAt(0); } //------------------------------------------------------------- public static long getLong() throws IOException { String s = getString(); return (long)Integer.parseInt(s); } // ------------------------------------------------------------- } // end class DisplayApp //////////////////////////////////////////////////////////////// #include<> #include<> #include<> #define MAXSIZE 100 typedef int DataType; typedef struct stack { DataType data[MAXSIZE]; int top; }sqstack; sqstack *InitStack(sqstack *S)出* 1.顺序栈的初始化*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* * *┃\n"); printf("\t┃* 2.元素的入栈* 3.元素的出栈*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* * *┃\n"); printf("\t┃* 4.取栈顶元素* 5.判空*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* *┃\n"); printf("\t┃* 6.将十进制数转换为其他进制数*┃\n"); printf("\t┃* *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); while ((m='0')&&(m='1')&&(m='2')&&(m='3')&&(m='4')&&(m='5')&&(m='6')&&(m='7')) { printf("\n请选择你需要操作的步骤(0至7):"); fflush(stdin); scanf("%c",&m); switch(m) { case '0': { exit(0); break; } 宁波工程学院电信学院计算机教研室 实验报告 课程名称：___ 数据结构 ___ __ 实验项目：链串的基本算法 指导教师： 实验位置：电子楼二楼机房姓名： 学号： 班级：计科102 日期： 2011/10/13 一、实验目的 1）熟悉串的定义和串的基本操作。 2）掌握链串的基本运算。 3）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C＋＋6.0的计算机。 三、实验内容 编写一个程序，实现链串的各种基本运算，并在此基础上设计一个主程序。具体如下： 编写栈的基本操作函数 链串类型定义如下所示： typedef struct snode{ char data; struct snode *next; }listring; （1）串赋值Assign(s,t) 将一个字符串常量赋给串s,即生成一个其值等于t的串s （2）串复制StrCopy(s,t) ?将串t赋给串s （3）计算串长度StrLength(s) ?返回串s中字符个数 （4）判断串相等StrEqual(s,t) ?若两个串s与t相等则返回1；否则返回0。 （5）串连接Concat(s,t) ?返回由两个串s和t连接在一起形成的新串。 （6）求子串SubStr(s,i,j) ?返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j 个字符组成的子串。 （7）插入InsStr (s,i,t) ?将串t插入到串s的第i(1≤i≤StrLength(s)+1)个字符中,即将t 的第一个字符作为s的第i个字符,并返回产生的新串（8）串删除DelStr (s,i,j) ?从串s中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j 的子串,并返回产生的新串。 （9）串替换RepStr (s,s1,s2) ?在串s中,将所有出现的子串s1均替换成s2。 （10）输出串DispStr(s) ?输出串s的所有元素值 （11）判断串是否为空IsEmpty(s) 编写主函数 调用上述函数实现下列操作： （1）建立串s=“abcdefghijklmn”，串s1=“xyz”，串t＝“hijk” （2）复制串t到t1，并输出t1的长度 （3）在串s的第9个字符位置插入串s1而产生串s2，并输出s2 （4）删除s第2个字符开始的5个字符而产生串s3，并输出s3 （5）将串s第2个字符开始的3个字符替换成串s1而产生串s4，并输出s4 （6）提取串s的第8个字符开始的4个字符而产生串s5，并输出s5 （7）将串s1和串t连接起来而产生串s6，并输出s6 （8）比较串s1和s5是否相等，输出结果 程序清单： #include 实验二堆栈和队列 实验目的： 1.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理： 堆栈顺序存储结构下的基本算法； 堆栈链式存储结构下的基本算法； 队列顺序存储结构下的基本算法；队列链式存储结构下的基本算法；实验内容： 3-18链式堆栈设计。要求 （1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化Stacklnitiate （S）, 非空否StackNotEmpty（S），入栈StackiPush（S,x）, 出栈StackPop （S,d）,取栈顶数据元素StackTop（S,d）; （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3, 4，5 入栈，然后出栈并在屏幕上显示出栈的数据元素； （3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 3-19对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当 前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写一个主函数进行测试。 实验结果： 3-18 typedef struct snode { DataType data; struct snode *n ext; } LSNode; /* 初始化操作：*/ 实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈和队列及其应用_ 一．实验目的及要求 （1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们； （2）本实验训练的要点是“栈”的观点及其典型用法； （3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； （2）应用栈的基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5）利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存： 代码部分： 栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl; cout << "你的选择是：" ; } 链式储存： 代码部分： 栈"< （封面） 学生实验报告 学院：国际经贸学院 课程名称：数据结构 专业班级： 09电子商务 姓名： 学号： 学生实验报告 （经管类专业用） 一、实验目的及要求： 1、目的 通过实验，实现顺序栈的各种基本运算。 2、内容及要求 编写一个程序，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成下列功能： （1）初始化栈S。 （2）判断栈S是否非空。 （3）依次进栈元素a，b，c，d，e。 （4）判断栈S是否非空。 （5）输出栈的长度。 （6）输出从栈顶到栈底的元素。 （7）输出出栈序列； （8）判断链栈S是否为空； （9）释放链栈 二、仪器用具： 三、实验方法与步骤: 一、查阅顺序栈等相关资料，熟悉顺序栈基本概念和流程 二、“开展”顺序栈实验流程 三、整理实验数据和文档，总结实验的过程，编写实验报告 四、实验结果与数据处理： 1、顺序栈的代码： #include 实验三的实验报告 学期： 2010 至_2011 第 2 学期 2011年 3月 27日课程名称: 数据结构专业:信息与计算科学 09 级5班实验编号： 03 实验项目：栈和队列实验指导教师 _冯山_姓名：朱群学号： 2009060548 实验成绩： 一实验目的： (1)熟练掌握栈和队列的抽象数据类型及其结构特点； (2)实现基本的栈和队列的基本操作算法程序。 二实验内容：(类C算法的程序实现，任选其一) (1) 设计与实现基本的堆栈和队列结构下的各种操作（如堆栈的PUSH、POP 等操作）(必做)； (2)以表达式计算为例，完成一个可以进行算术表达式计算功能的算法设计 与实现（选做）； (3)以迷宫问题为例，以堆栈结构完成迷宫问题的求解算法和程序（选做）。三实验准备： 1) 计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分 析与代码设计与分析准备。 四实验步骤： 1.录入程序代码并进行调试和算法分析； 2.编写实验报告。 五实验过程 一设计与实现基本的堆栈结构下的各种操作（如堆栈的PUSH、POP等操作）（1）问题描述 实现堆栈各种基本操作，如Pop,Push,GetTop等操作，即输入数据，通过Push入栈，再通过Pop操作输出出栈的元素,即入栈a,b,c,d,出栈d,c,b,a （2）算法实现及基本思想 堆栈是后进先出的线性表，由Push输入元素，Pop输出元素，堆栈的Push 操作思想,即插入元素e为新的的栈顶元素，先判断栈满与否，追加存储空间，然后将e值赋给栈顶指针Top。输入数据时用for循环 堆栈的Pop操作思想，先判断栈是否为空，若栈不空，则删除栈的栈顶元素，用e返回其值， （3）数据结构 栈的顺序存储结构 Typedef struct { 《数据结构与算法》实验报告 实验03：栈 一、实验目的 1．掌握链式栈和顺序栈的特点； 2．掌握链式栈和顺序栈基本结构的定义及其基本运算； 3．掌握链式栈和顺序栈的创建和初始化、进栈、出栈、读取栈顶元素和显示栈中所有元素等基本操作。 二、实验内容 假设一个班有N个学生（N<20），每个学生有学号、姓名、性别、分数共4个成员。各个学生之间的逻辑关系是线性的，请采用链式栈和顺序栈作为存储结构编写程序。 程序所要实现的功能如下： ①输入一个学生并进栈； ②出栈一个学生并输出； ③读取栈顶元素并输出； ④输出栈中所有学生的相关信息。 顺序栈程序的主菜单如图3-1所示，链式栈的功能界面与其类似。 三、实验要求 1、学号为双号的同学：采用链式栈作为存储结构，补全程序LinkedStack-NoHead.cpp之中的代码；学号为单号的同学：采用顺序栈作为存储结构，补全SeqStack-Dynamic.cpp中的代码。 2、程序的界面及详细功能分别参见演示程序LinkedStackDemo.exe和SeqStackDemo.exe。 3、实验报告电子稿和打印稿及其它提交方面的要求同实验01。 四、运行结果（截图） 图3-1 显示栈中所有元素 图3-2进栈一个元素 图3-3出栈一个元素五、实验程序（源代码） #include"stdio.h" #include"stdlib.h" #include"string.h" // 学生结构体 typedef struct { char no[10]; char name[20]; char gender; float score; } STU; // 链式栈结点的结构体 typedef struct LNode { STU data; // 当前结点中存储的学生数据 struct LNode *next; // 下一个结点的地址 } StackNode; // 链式栈的结构体 typedef struct { StackNode *top; // 栈顶指针（相当于无头结点单链表的头指针）} LinkedStack; // 功能菜单 void menu() { printf("\n\t***************链式栈*****************\n"); printf("\t* 1 进栈一个学生 *\n"); printf("\t* 2 出栈一个学生 *\n"); printf("\t* 3 读取栈顶元素并输出 *\n"); printf("\t* 4 输出所有学生信息 *\n"); printf("\t* 0 保存数据并退出程序 *\n"); printf("\t******************************************\n"); printf("\t请选择菜单项："); } /*检测当前目录下是否存在文件stu.dat，如果存在，则从其中读取数据构造链式栈； 否则，新建该数据文件。*/ void init(LinkedStack &LS) { FILE *fp; char flag='r'; STU stmp; StackNode *p, *rear; // 先设置链式栈的top指针为空，表示链式栈为空 LS.top = NULL; // 打开文件 if((fp=fopen("stu.dat","rb"))==NULL) { 数据结构实验 实验项目名称：堆栈的基本操作 实验地点班级： 姓名：学号： 指导教师：成绩： 一、实验目的： 掌握堆栈的基本操作，考查数据的组织方式和函数的基本应用。 二、实验要求： 堆栈的入栈、出栈。 三、实验内容： 1、程序代码：（小五分两栏） ①顺序栈： #include "stdio.h" #include "stdlib.h" #define max 100 typedef struct wr { int data[max]; int top; }stack; void push(stack *s,int x) { if(s->top==max-1) { exit(0); } s->top++; s->data[s->top]=x; } int pop(stack *s) { int x; if(s->top==-1) { exit(0); } x=s->data[s->top]; s->top--; return x; } int main() { int e,i,x; stack s; s.top=-1; scanf("%d",&x); for(i=0;i { scanf("%d",&e); push(&s,e); } for(i=0;i 南京信息工程大学实验（实习）报告 实验（实习）名称栈和队列日期2017.11.8 得分指导老师崔萌萌 系计算机系专业软件工程年级2016 班次(1) 姓名学号 一、实验目的 1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归 3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作 二、实验内容 1、用栈解决以下问题： （1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。 2、用递归写出以下程序： （1）求n！。 （2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。 3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。 三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换： 代码如下： #include printf("转换为%d进制： ",radix); while(n) { s.push(n%radix); n /= radix; } while(!s.empty()) { //非空 printf("%d",s.top()); s.pop(); } printf("\n"); return 0; } 运行结果如下： 2.2 求表达式的值 代码如下： #include 实验报告 学院（系）名称：计算机科学与工程学院 姓名赵振宇学号20175302 专业 计算机科学与技术 班级 2017级4班实验项目 实验三：图的遍历与应用 课程名称 数据结构与算法 课程代码 0661913 实验时间 2019年5月27日 第3、4节 实验地点 7-219 考核标准实验过程25分 程序运行20分 回答问题15分 实验报告30分 特色功能5分 考勤违纪情况5分 成绩 成绩栏 其它批改意见: 教师签字： 考核内容 评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。 □功能完善,□功能不全□有小错□无法运行 ○正确○基本正确○有提示○无法回答 ○完整○较完整 ○一般 ○内容极少○无报告 ○有 ○无 ○有 ○无一、实验目的 1、实验目的：通过实验使学生理解图的主要存储结构，掌握图的构造算法、图的深度优先和广度优先遍历算法，能运用图解决具体应用问题。 二、实验题目与要求 要求：第1题为必做题，2，3，4至少选一 1.输入指定的边数和顶点数建立图，并输出深度优先遍历和广度优先遍历的结果。 1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：1…图的建立2…深度优先遍历图3…广度优先遍历图0…结束 2）实验要求：在程序中定义下述函数，并实现要求的函数功能：CreateGraph():按从键盘的数据建立图 DFSGrahp()：深度优先遍历图 BFSGrahp()：广度优先遍历图 3）实验提示: 图的存储可采用邻接表或邻接矩阵； 图存储数据类型定义（邻接表存储） #define MAX_VERTEX_NUM8//顶点最大个数 typedef struct ArcNode {int adjvex; struct ArcNode*nextarc; int weight;//边的权 }ArcNode;//表结点 #define VertexType int//顶点元素类型 typedef struct VNode {int degree,indegree;//顶点的度，入度 VertexType data; ArcNode*firstarc; }Vnode/*头结点*/,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum;//顶点的实际数，边的实际数}ALGraph; 4）注意问题: 注意理解各算法实现时所采用的存储结构。 注意区别正、逆邻接。 2.教学计划编制问题 一、实验目的 1．进一步掌握指针变量的含义。 2．掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。 3．掌握用指针类型描述、访问和处理二叉树的运算。 二、实验要求 1．认真阅读和掌握本实验的参考程序。 2．按照对二叉树的操作需要，在创建好二叉树后再通过遍历算法验证创建结果。3．保存程序的运行结果，并结合程序进行分析。 三、实验内容 以下参考程序是按完全二叉树思想将输入的字符串生成二叉树，并通过遍历来验证二叉树创建正确与否，但不能创建非完全二叉树，请认真研究该程序，然后模仿教材例6.4初始化方式创建二叉树:所有的空指针均用#表示，如教材图 6-13对应的二叉树，建立时的初始序列为：AB#D##CE##F##。然后通过遍历算法验证二叉树是否正确（先递归验证后非递归验证）。 参考程序略 程序代码如下： #include "stdio.h" #include "stdlib.h" typedef char Datatype; #define MAXSIZE 100 typedef struct bnode { Datatype data; struct bnode *lchild,*rchild; }BNode,*BTree; typedef struct{ BTree data[MAXSIZE]; int front,rear; }seqqueue,*Pseqqueue; typedef struct{ BNode *node; int flag; }Data; typedef struct node { Data Data[MAXSIZE]; int top; }SeqStack,*PSeqStack; PSeqStack Init(void) 数据结构实验3 《数据结构与算法》实验报告 实验序号：3 实验项目名称：链式表的操作学号1507112104 姓名陈忠表专业、班15商智实验地点指导教师林开标实验时间16.11.09 一、实验目的及要求 1. 通过实验理解单链表的逻辑结构； 2. 通过实验掌握单链表的基本操作和具体的函数实现。 二、实验设备（环境）及要求 微型计算机； windows 操作系统； Microsoft Visual Studio 6.0集成开发环境。 三、实验内容与步骤 链式表表示和实现线性表的如下： #include"stdio.h" #include"stdlib.h" typedef struct node //定义结点 { int data; //结点的数据域为整型 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自 定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 ListNode *LocateNode(LinkList head, int key); //函数，按值查找结点 void DeleteList(LinkList head,int key); //函数，删除指定值的结点 void printlist(LinkList head); //函数，打印链表中的所有值 void DeleteAll(LinkList head); //函数，删除所有结点，释放内存 //==========主函数============== void main() { int num; char ch; LinkList head; head=CreatListR1(); //用尾插入 法建立单链表，返回头指针 printlist(head); //遍历链表 输出其值 printf(" Delete node (y/n):"); //输入 实验难度： A □ B □ C □序号学号姓名成绩 指导教师（签名） 学期：2017秋季学期 任课教师: 实验题目: 组员及组长: 承担工作： 联系电话: 电子邮件: 完成提交时间：年月日 一、【实验构思（Conceive）】(10%) （本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析） 魔王语言的解释规则： 大写字母表示魔王语言的词汇，小写字母表示人的词汇语言,魔王语言中可以包含括号，魔王语言的产生式规则在程序中给定，当接收用户输入的合法的魔王语言时，通过调用魔王语言翻译函数来实现翻译。 在 A 的基础上，（根据产生式）自定义规则，将一段魔王的话翻译为有意义的人类语言（中文）：输入wasjg,则魔王语言解释为“我爱数据结构”。 运用了离散数学的一些基本知识及程序设计知识。 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等） //---------------抽象数据类型的定义------------------// #define STACK_INIT_SIZE 50 #define STACKINCREMENT 10 #define OVERLOW -2 #define ERROR -1 typedef struct { char *base; //顺序栈的栈底指针 int top; //顺序栈的栈顶 int size; //栈元素空间的大小 }SqStack; //结构体类型顺序栈 typedef struct { char *base; int front; int rear; }SqQueue; //结构体类型队列 //---------------各个模块功能的描述------------------// void Init_SqStack(SqStack &s) //初始化顺序桟 void Push_SqStack(SqStack &s, char c) //压入数据 int Pop_SqStack(SqStack &s, char &e) //出桟 char GetTop_SqStack(SqStack s)//或得栈顶 《数据结构》课程实验报告 实验名称栈和队列实验序号实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。 (4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。 二、实验项目摘要 编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化栈s； （2）判断栈s是否非空； （3）依次进栈元素a,b,c,d,e； （4）判断栈s是否非空； （5）输出栈长度； （6）输出从栈顶到栈底元素； （7）输出出栈序列； （8）判断栈s是否非空； （9）释放栈。 编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能： （1）初始化队列q； （2）判断队列q是否非空； （3）依次进队列a,b,c； （4）出队一个元素，输出该元素； （5）输出队列q的元素个数； （6）依次进队列元素d,e,f； （7）输出队列q的元素个数； （8）输出出队序列； （9）释放队列。 三、实验预习内容 栈的顺序存储结构及其基本运算实现（初始化栈，销毁栈，求栈的长度，判断栈是否为空，进栈，取栈顶元素，显示栈中元素） 队列的顺序存储结构及其基本运算实现（初始化队列，销毁队列，判断队列是否为空，入队列，出队列） 三、实验结果与分析 3-1 #define maxsize 100 #include 南京工程学院实验报告 1.熟悉上机环境，进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素（学号）。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用 程序1的主要代码(附简要注释) #include p->rchild=NULL; p->data=n; } else if(n>p->data) p->rchild=initBST(n,p->rchild); else p->lchild=initBST(n,p->lchild); return p; } void inorder(BSTNODE *BT){ if(BT!=NULL){ inorder(BT->lchild); printf("%d",BT->data); inorder(BT->rchild); } } BSTNODE *search_btree(BSTNODE *root,int key) { if(!root) {printf("Emptu btree\n"); return root;} while(root->data!=key) { if(key 三题目：哈夫曼编/译码器 班级：姓名：学号：完成日期：15.11.14 一、题目要求 描述：写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0. 输入：输入表示字符集大小为n（n <= 100）的正整数，以及n个字符和n个权值（正整数，值越大表示该字符出现的概率越大）； 输入串长小于或等于100的目标报文。 输出：经过编码后的二进制码，占一行； 以及对应解码后的报文，占一行； 最后输出一个回车符。 输入样例： 5 a b c d e 12 40 15 8 25 bbbaddeccbbb 输出样例： 00011111110111010110110000 bbbaddeccbbb 提示：利用编码前缀性质。 二、概要设计 1.设计需要的数据结构：树型结构 2.需要的抽象数据类型： ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3,…,Dm(m>0)，对于任意j≠k(≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi?Di有 重庆文理学院软件工程学院实验报告册 专业：_____软件工程__ _ 班级：_____软件工程2班__ _ 学号：_____2 ___ 姓名：_____周贵宇___________ 课程名称：___ 数据结构 _ 指导教师：_____胡章平__________ 2013年 06 月 25 日 { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/ }SeqList; #include "common.h" #include "seqlist.h" void px(SeqList *A,int j); void main() { SeqList *l; int p,q,r; int i; l=(SeqList*)malloc(sizeof(SeqList)); printf("请输入线性表的长度:"); scanf("%d",&r); l->last = r-1; printf("请输入线性表的各元素值:\n"); for(i=0; i<=l->last; i++) { scanf("%d",&l->elem[i]); } px(l,i); printf("请输入要插入的值:\n"); scanf("%d",&l->elem[i]); i++； px(l,i); l->last++; for(i=0; i<=l->last; i++) { printf("%d ",l->elem[i]); } printf("\n"); } void px(SeqList *A,int j) { int i,temp,k; for(i=0;i 中央广播电视大学实验报告（学科：数据结构） 姓名班级学号实验日期 成绩评定教师签名批改日期 实验名称：实验三二叉树 3.1 二叉树的顺序存储结构和链式存储结构 【问题描述】 设一棵完全二叉树用顺序存储方法存储于数组tree中，编写程序： （1）根据数组tree，建立与该二叉树对应的链式存储结构。 （2）对该二叉树采用中序遍历法显示遍历结果。 【基本要求】 （1）在主函数中，通过键盘输入建立设定的完全二叉树的顺序存储结构。 （2）设计子函数，其功能为将顺序结构的二叉树转化为链式结构。 （3）设计子函数，其功能为对给定二叉树进行中序遍历，显示遍历结果。 （4）通过实例判断算法和相应程序的正确性。 【实验步骤】 （1）运行PC中的Microsoft Visual C++ 6.0程序， （2）点击“文件”→“新建”→对话窗口中“文件”→“c++ Source File”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”，（3）输入程序代码， 程序代码如下: #include 验证性实验3：栈子系统 班级学号 20 姓名施程程 1．实验目的 （1）掌握栈的特点及其描述方法。 （2）用链式存储结构实现一个栈。 （3）掌握建栈的各种基本操作。 （4）掌握栈的几个典型应用的算法。 2．实验内容 （1）设计一个字符型的链栈。 （2）编写进栈、出栈、显示栈中全部元素的程序。 （3）编写一个把十进制整数转换成二进制数的应用程序。 （4）编写一个把中缀表达式转换成后缀表达式（逆波兰式）的应用程序。（5）设计一个选择式菜单，以菜单方式选择上述操作。 栈子系统 ********************************************** * 1---------进栈 * * 2---------出栈 * * 3---------显示 * * 4---------数制转换 * * 5---------逆波兰式 * * 0---------返回 * ********************************************** 请选择菜单号（0--5）： 3．实验程序（附zhan.cpp） #include 数据结构实验三(顺序栈的基本操作)
数据结构实验报告3--链串
数据结构-堆栈和队列实验报告
数据结构_实验三_栈和队列及其应用
数据结构-实验报告顺序栈
数据结构 实验报告三
数据结构实验03-栈
数据结构实验-栈
数据结构栈和队列实验报告.doc
数据结构实验三
数据结构实验3二叉树
数据结构实验3
(精选)云南大学软件学院数据结构实验3
数据结构栈和队列实验报告
《数据结构》实验3实验报告
数据结构实验三实验报告
数据结构实验答案
(中央电大)数据结构实验报告3
数据结构实验3：栈子系统
相关主题
文本预览