实验四 栅格数据结构
第二章将地球“装入”计算机利用计算机分析地理世界，需要在计算机中建立一个地理世界的模型，而不能直接将地理世界的实体装入计算机，这个过程就是建模。如何建模呢？首先要对地理世界进行抽象，地理学中描述地理世界，不仅要描述组成地物的特征，还要描述这些地物的位置；然后，将描述的结果转换为计算机能够接受的形式，这个过程称为“编码”；最后，将编码结果在计算机中表示出来，这个过程称为“解码”，经过以上三个步骤就实现了将现实世界装入了计算机，生成了各种类型的空间数据。
本章内容包括两个实验，实验四—栅格数据结构和实验五—矢量数据结构，分别介绍两种将地球“装入”计算机的方法。
实验四栅格数据结构
一、实验目的
1.通过实验，加深对栅格数据结构的认识。
2.通过实验，了解栅格数据坐标系统。
3.通过实验，掌握栅格矩阵结构、游程编码结构、四叉树编码结构的栅格数据压缩的方法。
二、实验内容
1.掌握栅格矩阵结构数据文件头的定义。
2.以扫描地图为基础，运用混合像元属性值确定方法，确定栅格单元的属性值。
3.根据栅格数据文件格式要求，手工制作栅格矩阵结构的栅格数据文件。
4.根据栅格数据压缩编码的要求，对手工制作的栅格矩阵结构进行游程压缩编码和解码。
5.尝试实现栅格数据的四叉树压缩编码和解码。
三、实验要求
1.掌握对空间区域进行格网化的方法。
2.了解栅格数据文件头中各参数的含义。
3.掌握栅格数据单元格属性取值方法。
4.了解栅格数据的可视化表达方法。
5.掌握栅格数据的游程长度编码、四叉树编码的原理，了解四叉树编码在VB环境下的实现过程。
四、实验数据
1.
图1 栅格数据文件举例
五、实验步骤
1、拟解决的问题
地理环境中的实体或者现象有一部分是连续的，如温度、气压等地理现象，为了将这些内容输入计算机，必须将它们转换为计算机能接受的形式。地学中常用的方法就是将连续的研究对象格网化，将其规则地分成若干独立的单元，每个单元的位置用格网行列号表示，单元的特征用一个具体数值来表示，所有的单元按照行列号的顺序组织在一起，就实现了对连续分布的地物或者地理现象的有效地描述。这种格网化的方法得到的结果，就是地理信息系统常见的数据类型之一——栅格数据。GIS中的栅格数据目前主要类型有数字高程模型（DEM）、遥感影像数据、栅格地形图等，虽然以上几种栅格数据在形式、文件结构等方面存在着一定的差别，但原理基本上是一样的。本实验主要介绍如何实现栅格
数据的编码、解码和压缩。
2、原理
（一）、格网化方法
为了表示连续的地理目标，通常将地理目标所在的区域等分为若干行、列构成的网格，网格行列号表示位置，用一个值来表示每个网格的属性，将所有的单元格位置和属性记录下来，这样就得到了栅格数据，而对于一个单元格而言，可能会出现多种地物共存的现象，为了方便记录，最终只能取一种地物的属性作为这一单元的记录属性，因而需要以一定的方式决定哪种地物作为这个单元格的代表，栅格单元的取值方法有多种：当栅格单元中有多个地物时只能选择一个代表栅格单元，如何选择呢？常用的选择方案主要有：1）中心点法则：栅格单元的属性值以网格中心点对应的面域属性值来确定。
2）重要性法则：根据栅格内不同地物的重要性程度，选取特别重要的空间实体决定对应的栅格单元值。
3）面积占优法则：每个栅格单元的值以在该网格单元中占据最大面积的属性值
4）长度占优法则：每个栅格单元的值以网格中线（水平或垂直）的大部分长度所对应的面域的属性值来确定。
（二）、编码
确定了栅格单元中的属性值之后，则可建立栅格数据文件，这个过程称为栅格数据的编码。编码首先要确定栅格数据文件的构成，每个单元格中的属性值是栅格数据文件中最重要的部分，但是为了高效率的对栅格数据文件进行读取、管理，需要在文件头部加上一些参数对其进行必要的说明，因而一般栅格数据文件的组成包括文件头和数据主体两部分，其中文件头主要定义栅格数据的行、列数，栅格单元的大小，位置等内容，文件体是格网化描述以后的属性数值构成矩阵。
栅格数据文件的文件头和文件体组成，文件头是对格网化方法和文件体的描述。以DEM 数据文件头为例，其文件头定义如下：
表1 ArcVIEW的DEM数据文件头说明
文件格式举例含义
ncols 15 列数
nrows 10 行数
xllcorner 50 西南角格网单元横坐标X0
yllcorner 50 西南角格网单元纵坐标Y0
cellsize 100 格网间距
nodata_value -9999 无效数据区的属性值
图１是一个用记事本打开的栅格数据文件，其中第一行到第六行就是栅格数据文件的文件头，六个参数描述的意义分别是列数15、行数10、西南角栅格单元的X坐标50、西南栅格单元Y坐标50、栅格单元的边长100和无数据区的表示值-9999。从第七行开始，记录的则是栅格数据文件的具体内容，也就是将现实世界描述的结果，排列为10行、15列的二维矩阵。
（三）解码
运用不同的编码方法，可以得到各种不同格式的栅格文件，当需要应用这些数据时，必须通过一定的方式将这些数据通过计算机表达并显示出来，这个过程称为解码。
（四）压缩
（1）游程压缩
（2）四叉树压缩
（3）金字塔压缩
3、工具与使用方法
（一）Command Line工具
Command Line工具是ArcMap提供的命令行工具，通过点击Window—Command Line
可以打开CommandLine浮动工具栏。该工具栏分上下两个部分，上面用于输入各种命令和参数，下面用于显示运行信息。
在Command Line中输入命令的方法是通过键盘输入命令名称，后空一格，再必要的输入参数，如果有多个参数，参数之间用空格分开。如果不知道命令完整名称，可以先输入命令的前面几个字符，在出现的提示信息中进行选择。参数的输入也可以利用提示信息，如果用已经加载的数据作参数，这些已经加载的数据会出现在提示信息中，直接选择即可。
在Command Line的命令输入框中输入A然后用鼠标选择AsciiToRaster，即可。（二）ASCIIToRaster工具
ASCIIToRaster是将ASCII格式保存的栅格数据转换为ESRI的Grid格式的栅格数据的工具。具体步骤如下：
步骤一复制创建ASC格式的栅格数据文件。将图1中的数据复制到记事本中另存为ASC 格式的文件，比如文件命名为doc1.asc。
步骤二将ASC格式的栅格数据转换为ESRI格式的GRID数据。打开Command Line，输入AsciiToRaster，输入空格，再输入包含完整路径的文件，比如：“C：\doc1.asc”，再输入空格，接着输入转换结果保存路径，例如“D:\ddd”，空格，在弹出的选项中选择Integer。
步骤三转换运算。弹出转换对话框，运算结束后，自动添加到当前视图。
（三）ArcToolBox工具
4、自我练习
请运用栅格数据原理，对图5中的实验练习.jpg 数据进行编码，然后运用上面的程序将编码结果显示出来，与原图进行比较。然后提高编码精度，比较数据量的大小，然后进行压缩。
栅格矩阵结构 游程编码结构 四叉树编码结构 金字塔编码结构
5、问题与解答
本实验中的常见问题有：
1、 运用游程编码进行数据压缩，一定会取得压缩效果吗？
答：压缩的效果取决于原始栅格数据的内部结构，如果原始栅格数据的游程数较多，则使用流程编码会取得较好的效果。
2、 四叉树编码和游程编码哪一个效果更好？
答：取决于原始数据的内部结构，有时游程编码的效果会优于四叉树编码。 3、 如何评价栅格数据的压缩效果？ 答：可采用计算压缩比的方式，如采用压缩前后栅格数据量所占存储空间的比值作为参数来计算此编码的压缩效果，此值越大表示压缩效果越好。
6、拓展与探索
GIS中另一种常见的栅格编码为四叉树编码，它是最有效的栅格数据压缩编码方法之一。其基本思想是首先把一幅图像或一幅栅格地图等分成四部分，如果检查到某个子区的所有格网都含有相同的值（灰度或属性值），那么这个子区域就不再往下分割；否则，把这个区域再分割成四个子区域，这样递归地分割，直至每个子块都只含有相同的灰度或属性值为止。如果栅格数据不是2N×2N的方阵，则自动补栅格属性值为0的行或列，使得2N大于或者等于行、列数中的大者，取合乎要求的最小的自然数N。
分割完成之后则采用一定的机制对分割的结果进行记录，四叉树存储方法：包括常规四叉树存储：存储结点（子结点和父结点）指针、结点值；线性四叉树只存储最后叶结点信息，包括叶结点的地址、深度（该结点所处的层）和格网值。四叉树的叶结点的编码需要遵循一定的规则，隐含了位置信息，称为地址码，常用的编码是Morton码（MD十进制码）。如对以下数据采用记录Morton码、深度、属性值的方法进行记录，如假设有如下栅格数据：
1 1 1 1
2 2
3 3
1 1 1 1
2 2
3 3
1 1 1 1 4 4 5 5
1 1 1 1 4 4 5 5
6 6
7
8 13 13 14 14
6 6 9 10 13 13 14 14
11 11 12 12 15 16 19 19
11 11 12 12 17 18 19 19
进行四叉树编码之后得到如下文件，试进行程序开发实现此过程，结果如图5。
M码深度值
0 1 1
16 2 2
20 2 3
24 2 4
28 2 5
32 2 6
36 3 7
37 3 8
38 3 9
39 3 10
40 2 1
44 2 12
48 2 13
52 2 14
56 3 15
57 3 16
58 3 17
59 3 18
60 2 19
链接
1973年美国学者I ．NASSI 和B ．SHINEIDERMAN 提出了一种新的流程图形式。它把
全部算法写在一个矩形框中，矩形框中嵌套着其他的框，使算法的结构更加清晰，适合于描述结构化算法。这种流程图用两位学者名字的第一个字母命名，称为N-S 结构流程图。
以下为栅格数据的读写操作程序设计，读取过程如图2所示：
为了将编码后的栅格文件显示出来，首先用VB 构建一个用于显示栅格编码结果的程序。具体过程如下：
步骤一 打开VB ，在默认工程中新建一个窗体，在窗体中添加一个Picture 控件、两个
CommandButton 控件和一个Commdialog 控件。
步骤二 设置控件的属性，将Form1的Caption 属性设为“栅格数据编码”，将Picture1的
AutoRedraw 属性设置为True ，将Command1的Caption 设为“打开”，将Command2的Caption 设为“退出”，用户界面如图3所示。
图2 栅格数据编码、解码N-S 过程图
图5 栅格数据的四叉树编码
步骤三 定义全局变量
Dim fileName As String '定义文件头参数变量 Dim nCol As Integer Dim nRow As Integer Dim xll As Integer Dim yll As Integer
Dim cellSize As Integer Dim nodata As Integer
'临时字符串变量,放置读取的临时字符 Dim strTemp As String
'定义读到栅格单元属性值的变量 Dim tempData As Integer '临时颜色
Dim nRColor, nGColor, nBColor As Integer '游程值，流程长度
Dim nRVal, nYcfn As Integer
步骤四 双击“打开”，在代码窗口输入如下代码：
On Error GoTo err
CommonDialog1.CancelError = True
CommonDialog1.Filter = "用户自定义栅格数据文件格式(*.rjys)" + _ "|*.rjys|游程长度编码格式(*.ycf)|*.ycf|所有格式(*.*)|*.*" CommonDialog1.ShowOpen
fileName = CommonDialog1.FileTitle Open fileName For Input As #1 '读取第1行,获得列数 Input #1, strTemp
arrTemp = Split(strTemp, " ") nCol = CInt(arrTemp(1)) '读取第2行,获得行数 Input #1, strTemp
arrTemp = Split(strTemp, " ") nRow = CInt(arrTemp(1))
'读取第3行,获得西南角点栅格单元的X 坐标 Input #1, strTemp
arrTemp = Split(strTemp, " ")
xll = CInt(arrTemp(1))
'读取第4行,获得西南角点栅格单元的Y坐标
Input #1, strTemp
arrTemp = Split(strTemp, " ")
yll = CInt(arrTemp(1))
'读取第5行,获得栅格单元的大小
Input #1, strTemp
arrTemp = Split(strTemp, " ")
cellSize = CInt(arrTemp(1))
'读取第6行,获得无数据区域对应数值
Input #1, strTemp
arrTemp = Split(strTemp, " ")
nodata = CInt(arrTemp(1))
Picture1.Scale (-10, cellSize * nRow)-(cellSize * nCol, 10)
'直接编码文件的读取、绘制
If (Right(filename, 4) = "rjys") Then
For i = 0 To nRow - 1
For j = 0 To nCol - 1
Input #1, tempData
nRColor = (75 * tempData + 110) Mod 256
nGColor = (15 * tempData + 150) Mod 256
nBColor = (35 * tempData + 10) Mod 256
Picture1.Line (j * cellSize, (nRow - i) * cellSize)-((j + 1) * cellSize, _
(nRow - i - 1) * cellSize), RGB(nRColor, nGColor, nBColor), BF Next j
Next i
'游程编码文件的读取、绘制
ElseIf (Right(filename, 3) = "ycf") Then
i = 0
j = 0
Do
Input #1, nRVal, nYcfn
For t = 0 To nYcfn - 1
If (j = nCol) Then
i = i + 1
j = j Mod nCol
End If
nRColor = (75 * nRVal + 110) Mod 256
nGColor = (15 * nRVal + 150) Mod 256
nBColor = (35 * nRVal + 10) Mod 256
Picture1.Line (j * cellSize, (nRow - i) * cellSize)-((j + 1) * cellSize, _
(nRow - i - 1) * cellSize), RGB(nRColor, nGColor, nBColor), BF j = j + 1
Next t
Loop While Not EOF(1)
End If
Close #1
err:
Exit Sub
步骤五双击“退出”，输入end；
步骤六将工程重命名为“栅格数据编码”，并保存；
步骤七测试执行。
（四）压缩
栅格数据解码实验验证了数据量和栅格单元大小的关系，对于同一区域而言，栅格单元的面积越小，数据精度会越高，表达的效果会越好，但数据量也越大。
经过格网化处理之后，可视化表达的效果和原来地理对象相比发生了很大的变化，为了准确表达现实世界，需要将格网细化，但是格网细化会导致数据量增大，单元格的边长缩小为原来的1/2，数据将变为原来的4倍，数据精度与数据量之间存在矛盾，为了尽可能提高精度，同时使数据量控制在允许的范围之内，一种常见的解决方案是进行栅格数据的重编码以实现压缩的目的。栅格数据压缩方法很多，常见的有游程长度编码、链码、块码、四叉树编码等，其中游程长度是比较简单实用的一种。
游程长度编码是栅格数据压缩的重要编码方法，它的基本思路是：对于一幅栅格数据，常常有行(或列)方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。其编码方案是，只在各行(或列)数据的代码发生变化时依次记录该代码以及相同代码重复的个数，从而实现数据的压缩。
例如对图1所示的栅格数据，可沿行方向进行如下游程长度编码：
(0，25)，(50，3)，(0，9)，(1，1)，(0，3)，(1，1)，(0，10)，(1，1)，(0，3)，
(1，1)，(0，4)，(50，7)，(0，3)，(1，1)，(0，4)，(1，1)，(0，5)，(1，1)，
(0，3)，(1，1)，(0，4)，(1，1)，(0，5)，(1，1)，(0，3)，(1，1)，(0，4)，
(1，1)，(0，5)，(1，1)，(0，3)，(1，1)，(0，4)，(1，1)，(0，5)，(1，1)，
(0，2)，(50，3)，(0，17)。
游程长度编码对图1用了78个整数就可以表示，而如果用前述的直接编码却需要150个整数表示，可见游程长度编码压缩数据是十分有效又简便的。事实上，压缩比的大小是与数据内部的复杂程度成反比，在变化多的部分，游程数相对较多，变化少的部分游程数就少，因此数据越简单，压缩效率就越高，下面介绍一个游程长度编码的压缩程序，具体过程如下：在原来的栅格数据例程界面中，增加一个CommandButton控件，设置其Caption为“编码”。输入如下代码：
步骤一
On Error GoTo err
CommonDialog1.CancelError = True
GrdFile = CommonDialog1.FileTitle
CommonDialog1.Filter = "游程长度编码格式(*.ycf)|*.ycf"
CommonDialog1.ShowSave
Ycffile = CommonDialog1.FileTitle
Call YCF_Encode(GrdFile, Ycffile)
err:
Exit Sub
步骤二其中使用了一个函数YCF_Encode(GrdFile, Ycffile)，其代码为：Sub YCF_Encode(ByVal GrdFile As String, ByVal Ycffile As String)
Dim i As Integer, j As Integer, k As Integer
Dim row As Integer, column As Integer
Dim nCols As String
Dim nCol As Integer
Dim nRows As String
Dim nRow As Integer
Dim xlls As String
Dim xll As Integer
Dim ylls As String
Dim yll As Integer
Dim cellSizes As String
Dim cellSize As Integer
Dim nodatas As String
Dim nodata As Integer
'生成游程长度编码文件
Open GrdFile For Input As #1
Input #1, nCols, nRows, xlls, ylls, cellSizes, nodatas
arrTemp = Split(nCols, " ")
nCols = arrTemp(0)
nCol = CInt(arrTemp(1))
arrTemp = Split(nRows, " ")
nRows = arrTemp(0)
nRow = CInt(arrTemp(1))
arrTemp = Split(xlls, " ")
xlls = arrTemp(0)
xll = CInt(arrTemp(1))
arrTemp = Split(ylls, " ")
ylls = arrTemp(0)
yll = CInt(arrTemp(1))
arrTemp = Split(cellSizes, " ")
cellSizes = arrTemp(0)
cellSize = CInt(arrTemp(1))
arrTemp = Split(nodatas, " ")
nodatas = arrTemp(0)
nodata = CInt(arrTemp(1))
Open Ycffile For Output As #2
Print #2, nCols + Str(nCol)
Print #2, nRows + Str(nRow)
Print #2, xlls + Str(xll)
Print #2, ylls + Str(yll)
Print #2, cellSizes + Str(cellSize)
Print #2, nodatas + " " + Str(nodata)
Input #1, a
k = 0
For j = 2 To nCol * nRow
Input #1, b
If a <> b Then
k = k + 1
Print #2, a; p;
p = 1
a = b
Else
p = p + 1
End If
If (j = nCol * nRow) Then
Print #2, b, p + 1
End If
Next j
Close #1, #2
'显示文件冗余度及压缩比，并自动显示游程长度编码
MsgBox GrdFile + "文件的冗余度为" + Format(Str((1 - k / (nRow * nCol))), "0.000") + _ "。压缩比为" + Format(Str(nRow * nCol / (k + 1)), "0.000") + "。"
Shell "C:\WINDOWS\system32\notepad.exe " & CurDir & "\" & Ycffile, vbNormalFocus End Sub
步骤三编译，通过文件下拉菜单----“make 栅格数据编码.exe”，得到可执行文件，选择路径，保存，如果要在没有安装VB6.0的环境下运行，则应该将VB6.0所需的动态链接库文件，放到同一目录下；
步骤四首先打开需要压缩的文件，然后点击“编码”，选择编码以后保存的路径和文件名，保存即可。编码以后的文件自动用记事本打开，
步骤五比较压缩前后的文件大小。
1、栅格数据读取
步骤一将图1的内容复制到记事本，保存为栅格数据文件raster1.rjys；
步骤二双击“栅格数据编码.exe”，弹出使用图2所示界面，单击打开按钮，弹出打开文件对话框，选择raster1.rjys打开；
步骤三显示结果如图3所示，观察显示结果同数据的对应关系。
2、游程压缩编码数据的压缩与解码
步骤一利用上述程序，单击编码按钮，弹出保存文件对话框，起名为raster2.ycf，得到游程编码的结果；
步骤二利用记事本打开raster2.ycf，观察游程编码的结果；
步骤三单击打开按钮，读取rater2.ycf，观察显示结果与原数据是否一致。
在本实验中，实验数据由实验者自己制作，首先将图1所示的内容输入到记事本文件中，然后将其命名为raster1.rjys，其中“raster1”为文件名，“fjys”为文件的后缀名，表示这是在本实验中的一个自定义文件。需要特别注意：行、列数要与文件头中的行列数定义一致，中间不要出现空行，否则无法将会导致实验过程中出现不可预料的错误。
六、实验报告
将图5的图形栅格化，提取数据，保存为自定义栅格文件格式。修改上面的例程，用于显示自定义的栅格文件，并完成实验报告。
数据结构实验4
（一）题目 1. 按下述原则编写快排的非递归算法： (1) 一趟排序之后，若子序列已有序(无交换)，则不参加排序，否则先对长度较短的子序列进行排序，且将另一子序列的上、下界入栈保存； (2) 若待排记录数<=3，则不再进行分割，而是直接进行比较排序。 测试实例：{49 38 65 97 76 13 27 49 88 21 105} （二）算法思路 (1) 建立存储序列上下界的栈序列。 (2) 对栈顶作如下判断： A. 若栈顶中记录的头与尾相距小于3，对对应的子序列进行排序，然后出栈，进入(3)； B. 若栈顶中记录的头与尾相距大于等于3，则进行分块，判断分块是否有序， a.若两分块都有序，则出栈，进入(3)； b.若只有一分块有序，则改变栈顶内容为无序分块内容，进入(3)； c.若两分块都无序，则改变栈顶内容为较长的无序块，然后把较短的无序块 压进栈。进入(3) (3)重复(2)的操作，直至栈空，得到最终结果。 （三）程序结构 定义的结构体及声明 （四）源码
using namespace std; typedef struct _stack{ int left; //lowerbound int right; //upperbound struct _stack *next; }qstack; //to store the child sequence's left and right void sort(int *arr, int left, int right){ //sort child sequence less than 3 for(int i = left; i <= right; i++){ int k = i; for(int j = i+1; j <= right; j++){ if(arr[k] > arr[j]) k = j; } if(k != i){ int t; t = arr[k]; arr[k] = arr[i]; arr[i] = t; } } } bool sorted(int *arr, int left, int right){ for(int i = left; i < right; i++){ if(arr[i] > arr[i+1]) return false; } return true; } void qsort(int *arr, int left, int right){ qstack *head; head = new qstack; head->left = left; head->right = right; head->next = NULL; qstack *p; while(head != NULL){ if(head->right - head->left < 3){ //if less than 3, sort and pop sort(arr, head->left, head->right);
数据结构实验报告格式
《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时）
数据结构实验报告(四)
《数据结构》实验报告 班级： 学号： 姓名：
实验四二叉树的基本操作实验环境：Visual C++ 实验目的： 1、掌握二叉树的二叉链式存储结构； 2、掌握二叉树的建立，遍历等操作。 实验内容： 通过完全前序序列创建一棵二叉树，完成如下功能： 1)输出二叉树的前序遍历序列； 2)输出二叉树的中序遍历序列； 3)输出二叉树的后序遍历序列； 4)统计二叉树的结点总数； 5)统计二叉树中叶子结点的个数； 实验提示： //二叉树的二叉链式存储表示 typedef char TElemType; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
一、程序源代码 #include
} void Create_BiTree(BiTree *T){ char ch; ch = getchar(); //当输入的是"#"时，认为该子树为空 if(ch == '#') *T = NULL; //创建树结点 else{ *T = (BiTree)malloc(sizeof(struct TNode)); (*T)->data = ch; //生成树结点 //生成左子树 Create_BiTree(&(*T)->lchild); //生成右子树 Create_BiTree(&(*T)->rchild); } } void TraverseBiTree(BiTree T) { //先序遍历 if(T == NULL) return;
数据结构实验报告全集
数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include
nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"<
数据结构实验报告
数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 数据分析实验报告 文稿归稿存档编号：[KKUY-KKIO69-OTM243-OLUI129-G00I-FDQS58- 第一次试验报告 习题1.3 1建立数据集，定义变量并输入数据并保存。 2数据的描述，包括求均值、方差、中位数等统计量。 分析—描述统计—频率，选择如下： 输出： 统计量 全国居民 农村居民 城镇居民 N 有效 22 22 22 缺失 均值 1116.82 747.86 2336.41 中值 727.50 530.50 1499.50 方差 1031026.918 399673.838 4536136.444 百分位数 25 304.25 239.75 596.25 50 727.50 530.50 1499.50 75 1893.50 1197.00 4136.75 3画直方图，茎叶图，QQ 图。（全国居民） 分析—描述统计—探索，选择如下： 输出： 全国居民 Stem-and-Leaf Plot Frequency Stem & Leaf 5.00 0 . 56788 数据分析实验报告 【最新资料，WORD 文档，可编辑修改】 2.00 1 . 03 1.00 1 . 7 1.00 2 . 3 3.00 2 . 689 1.00 3 . 1 Stem width: 1000 Each leaf: 1 case(s) 分析—描述统计—QQ图，选择如下： 输出： 习题1.1 4数据正态性的检验：K—S检验，W检验数据： 取显着性水平为0.05 分析—描述统计—探索，选择如下：（1）K—S检验 结果：p=0.735 大于0.05 接受原假设，即数据来自正太总体。 （2 ）W 检验 结果：在Shapiro-Wilk 检验结果972.00 w ，p=0.174大于0.05 接受原假设，即数据来自正太总体。 习题1.5 5 多维正态数据的统计量 数据： 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 《数据分析》实验报告 班级：07信计0班学号：姓名：实验日期2010-3-11 实验地点：实验楼505 实验名称：样本数据的特征分析使用软件名称：MATLAB 实验目的1.熟练掌握利用Matlab软件计算均值、方差、协方差、相关系数、标准差与变异系数、偏度与峰度，中位数、分位数、三均值、四分位极差与极差； 2.熟练掌握jbtest与lillietest关于一元数据的正态性检验； 3.掌握统计作图方法； 4.掌握多元数据的数字特征与相关矩阵的处理方法； 实验内容安徽省1990-2004年万元工业GDP废气排放量、废水排放量、固体废物排放量以及用于污染治理的投入经费比重见表6.1.1，解决以下问题：表6.1.1废气、废水、固体废物排放量及污染治理的投入经费占GDP比重 年份 万元工业GDP 废气排放量 万元工业GDP 固体物排放量 万元工业GDP废 水排放量 环境污染治理投 资占GDP比重 （立方米）（千克）（吨）（%）1990 104254.40 519.48 441.65 0.18 1991 94415.00 476.97 398.19 0.26 1992 89317.41 119.45 332.14 0.23 1993 63012.42 67.93 203.91 0.20 1994 45435.04 7.86 128.20 0.17 1995 46383.42 12.45 113.39 0.22 1996 39874.19 13.24 87.12 0.15 1997 38412.85 37.97 76.98 0.21 1998 35270.79 45.36 59.68 0.11 1999 35200.76 34.93 60.82 0.15 2000 35848.97 1.82 57.35 0.19 2001 40348.43 1.17 53.06 0.11 2002 40392.96 0.16 50.96 0.12 2003 37237.13 0.05 43.94 0.15 2004 34176.27 0.06 36.90 0.13 1.计算各指标的均值、方差、标准差、变异系数以及相关系数矩阵； 2.计算各指标的偏度、峰度、三均值以及极差； 3.做出各指标数据直方图并检验该数据是否服从正态分布？若不服从正态分布，利用boxcox变换以后给出该数据的密度函数； 4.上网查找1990-2004江苏省万元工业GDP废气排放量，安徽省与江苏省是 否服从同样的分布？ 实验一约瑟夫问题 实验学时：3学时 实验类型：设计 实验要求：必修 一、实验目的 熟练掌握线性链表的基础知识； 能够使用C++或其他程序设计语言编程实现线性链表； 能够使用线性链表构造正确而且时间复杂度低的算法解决实际问题； 锻炼程序设计能力。 二、实验内容 M个教徒和N个非教徒在深海上遇险，必须将N个人投入海中，其余的人才能幸免于难，于是想了一个办法：所有人围成一圆圈，从第一个人开始依次报数，每数到第K个人就将他扔入大海，如此循环进行直到仅余M个人为止。设计一个算法，找出这样一个排序：使每次被扔进大海的都是非教徒。并用程序设计语言实现。 三、实验原理、方法和手段 使用循环单链表，将每个人作为一个结点，每个结点的指针域指向下一个人，采用循环链表的遍历对每隔N-1个结点的结点进行标记，直至标记出N个结点为止。该实验亦可用顺序表实现。 四、实验组织运行要求 本实验采用集中授课形式，每个同学独立完成上述实验要求。 五、实验条件 每人一台计算机独立完成实验，有如下条件： （1）硬件：联想高性能PC机； （2）软件：VC++ 6.0、VC++.Net。 六、实验步骤 （1）编写循环链表构造函数Node *Create( )，使链表中每个结点的数据域值为0，并让最后一个结点的指针域指向第一个结点； （2）编写约瑟夫问题函数 Node *Move(Node *H,int n); void Insert(Node *H,int pos,int data); （5）主函数中调用Create，Move和Insert，采用具体数据计算，输出结果。 七、实验程序 // stdafx.h : 标准系统包含文件的包含文件， // 或是经常使用但不常更改的 // 特定于项目的包含文件 // #pragma once #include"targetver.h" #include 《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作 附源程序清单： 1. #include { printf("栈上溢出!\n"); } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } } void Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { printf("栈下溢出\n"); } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} } int main() { SqStack L; SqStack *st=&L; ElemType c; int i; InitStack(st); printf("输入回车结束入栈"); while((c=getchar())!='\n') { if(c=='(') Push(st,c); if((i=StackEmpty(st))==-1) { if(c==')') Pop(st,c); } if(c==')' && (i=StackEmpty(st))==0) { printf("右括号多出,配对失败"); goto loop; 本科实验报告 课程名称：数据结构（C语言版） 实验项目：线性表、树、图、查找、内排序实验地点：明向校区实验楼208 专业班级：学号： 学生姓名： 指导教师：杨永强 2019 年 1 月10日 #include 数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于（ A ） A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ） A、正确的 B、错误的 C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ） A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是（ B ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ A ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ C ） A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ） A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ） 数据分析实验报告 【最新资料，WORD文档，可编辑修改】 第一次试验报告 习题1.3 1建立数据集，定义变量并输入数据并保存。 2数据的描述，包括求均值、方差、中位数等统计量。 分析—描述统计—频率，选择如下： 输出： 方差1031026.918399673.8384536136.444百分位数25304.25239.75596.25 50727.50530.501499.50 751893.501197.004136.75 3画直方图，茎叶图，QQ图。（全国居民） 分析—描述统计—探索，选择如下： 输出： 全国居民Stem-and-Leaf Plot Frequency Stem & Leaf 9.00 0 . 122223344 5.00 0 . 56788 2.00 1 . 03 1.00 1 . 7 1.00 2 . 3 3.00 2 . 689 1.00 3 . 1 Stem width: 1000 Each leaf: 1 case(s) 分析—描述统计—QQ图，选择如下： 输出： 习题1.1 4数据正态性的检验：K—S检验，W检验数据： 取显着性水平为0.05 分析—描述统计—探索，选择如下：（1）K—S检验 单样本Kolmogorov-Smirnov 检验 身高N60正态参数a,,b均值139.00 标准差7.064 最极端差别绝对值.089 正.045 负-.089 Kolmogorov-Smirnov Z.686 渐近显着性(双侧).735 a. 检验分布为正态分布。 b. 根据数据计算得到。 结果：p=0.735 大于0.05 接受原假设，即数据来自正太总体。（2）W检验 数据结构实验报告 实验名称：实验四——排序 学生：XX 班级： 班序号： 学号： 日期： 1．实验要求 实验目的： 通过选择实验容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 题目1： 使用简单数组实现下面各种排序算法，并进行比较。 排序算法如下： 1、插入排序； 2、希尔排序； 3、冒泡排序； 4、快速排序； 5、简单选择排序； 6、堆排序； 7、归并排序； 8、基数排序（选作）； 9、其他。 具体要求如下： 1、测试数据分成三类：正序、逆序、随机数据。 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关 键字交换记为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。 5、编写main（）函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构 存储结构：数组 2.2 关键算法分析 一、关键算法： 1、插入排序 a、取排序的第二个数据与前一个比较 b、若比前一个小，则赋值给哨兵 c、从后向前比较，将其插入在比其小的元素后 d、循环排序 2、希尔排序 a、将数组分成两份 b、将第一份数组的元素与哨兵比较 c、若其大与哨兵，其值赋给哨兵 d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组 e、循环进行数组拆分 3、对数据进行编码 a、取数组元素与下一个元素比较 b、若比下一个元素大，则与其交换 c、后移，重复 d、改变总元素值，并重复上述代码 4、快速排序 a、选取标准值 b、比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后 指针前移，重新比较 c、否则后面元素赋给前面元素 d、若后指针元素小于标准值，前指针后移，重新比较 e、否则前面元素赋给后面元素 5、简单选择排序 a、从数组中选择出最小元素 b、若不为当前元素，则交换 c、后移将当前元素设为下一个元素 6、堆排序 a、生成小顶堆 b、将堆的根节点移至数组的最后 c、去掉已做过根节点的元素继续生成小顶堆 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 浙江科技学院《数据结构》实验报告 年级班级 学号 姓名 任课老师 实验指导教师 实验地点 信息学院 实验一线性表操作（一元多项式的运算） 实验目的： 1、定义线性表的链式存储 2、实现对线性表的一些基本操作和具体函数定义 实验要求： 1、定义线性表的链式存储； 2、实现对线性表的一些基本操作和具体函数定义。 3、定义输出一元多项式的函数； 4、编写主程序调用上面的函数实现一元多项式的加减。 数据输入输出要求： 输入示例： 3 2 3 3 4 5 7 5 2 1 3 3 -3 4 4 6 5 7 （说明：第一个数据3表示该第一个一元多项式的项数为3，后面的2 3 表示第一项的系数为2 指数为3；按指数递增的次序输入） 输出示例： 一元多项式1： 2x(3)+3x(4)+5x(7) 一元多项式2： 2x(1)+3x(3)-3x(4)+4x(6)+5x(7) 加的结果：2x(1)+5x(3) +4x(6)+10x(7) 减的结果：-2x(1)-1x(3)＋6x(4)-4x(6) 程序代码： #include #include 贵州大学实验报告 学院：计信学院专业：通信工程班级：通信091 姓名何川学号0908060235 实验 组实验时间2011.12、 指导教 师 陈静成绩实验项目名称二叉树操作 实 验目的1、熟悉二叉树结点的结构和对二叉树的基本操作及具体实现。 2、利用递归方法编写对二叉树的各种遍历算法。 3、掌握递归方法在二叉树中的使用。 实验要求1、认真阅读和掌握本实验内容所给的全部程序。 2、在Visual C++6.0集成开发环境下编写和调试所有程序。 3、编写的所有算法须给出测试函数，并自行设计测试数据，对算法进行测试。 4、保存和打印出程序运行结果，并结合程序进行分析。 5、按照你对二叉树操作的需要，重新改写主文件并运行，打印出主文件清单 和运行结果。 实验原理Visual C++的编译环境下，独立完成实验要求的内容，独立完成编写、编以运行。 实 验 仪 器 安装了VC++6.0的PC机 实验步骤1、实现二叉树结点的定义和操作。该程序包括一个头文件，用来存储定义二 叉树结构类型以及对二叉树进行各种操作的函数声明；第二个为操作的实现文件，用来存储每一种操作的具体函数定义以及主函数。二叉树的操作包括二叉树初始化、创建二叉树，判断二叉树是否为空，求二叉树的深度和结点数，遍历二叉树等。 2、已知二叉树的前序遍历序列和中序遍历序列，编写可唯一确定该二叉树的 算法。 3、根据所给的n个带权叶子结点，编写算法构造哈夫曼树和哈夫曼编码。 实验内容（１）typedef char ElemType; struct BTreeNode{ ElemType data; BTreeNode *left; BTreeNode *right; }; void InitBTree(BTreeNode *&BT); void CreatBTree(BTreeNode *&BT,char *a); bool EmptyBTree(BTreeNode *BT); void TraverseBTree(BTreeNode *BT); int BTreeDepth(BTreeNode *BT); int BTreeCount(BTreeNode &BT); void PrintBTree(BTreeNode *BT); #include 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template数据分析实验报告
数据结构实验报告模板
数据分析实验报告
数据结构实验报告
数据结构实验4_99XXX
数据结构实验报告
数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)
数据分析实验报告
数据结构实验四题目一排序实验报告
数据结构实验报告及心得体会
数据结构实验报告
数据结构实验四
数据结构实验报告图实验