毕业论文统数据结构实验课教学平台开发

1、摘 要数据结构是计算机及相关专业中一门重要的专业基础课程，也是其它理工专业的热门选修课。由于数据结构的算法涉及从简单的线性表到复杂的树、图，具有一定的难度和复杂性，使得学习该课程十分困难。其中算法思想的理解是学习数据结构这门课程的一个关键，所以如何将抽象的算法执行过程以浅显易懂的形式展现在学生面前，是决定这门课教学成败的一个重要因素。基于上述原因，本文设计了一个教学平台对算法执行过程演示，促进学生对算法的理解。对于实验平台的建立，本文从最基本的VC基础知识介绍，一步步的深入到平台的开发，进而到如何合理的将数据结构的线性表、栈、数组、树、图等嵌入到平台中，再到演示各个算法，都作了较为详尽的阐述。

2、为了使演示过程形象化，本文用VC进行可视化编程演示。该系统界面友好、操作简单，既方便学生学习，也方便教师教学。关键词：数据结构； 演示； 算法； VCThe Platform's Development For Course Data Structure TeachingABSTRACT：“Data Structure” is an important basic course of computer and other relevant majors.Its also a popular elective course for other science majors.The alg

3、orithm of data structure is difficult to study bacause it involves a range of data structures from as simple as linear list to as complex as trees and graphs, which is not easy to master. Among all, the understanding of the algorithm is a key of the course of Data Structure.How to illustrate the abs

4、tract algorithmic performing process to the students in a simple way becomes vital to the teaching of this course.Based on the reasons above, this paper design a teaching platform demonstrating the processing of the algorithm, which improve the students' understanding of the algorithm. For the e

5、stablishment of experimental platform, this paper,from introduction of the most basic knowledge of VC,step by step,and them further to platform bevelopment and how to reasonably embed the data structure of the linear table,stack,array,tree into platform,and demonstrated for each algorithm minutely.T

6、o make the demonstrating vivial, this paper uses VC visually programming the demonstrating. The system is friendly, easy to use. It serves to the study of the students as well as the teacher's teaching.Key words: Datastucture, Demonstrate, Algorithm, VC目 录第1章 绪论11.1 选题背景11.2 研究内容1第2章 VC环境22.1 什么

7、是面向对象22.2 WINDOWS编程基础知识32.2.1 定义窗口类的结构32.2.2 窗口类的注册与窗口创建42.2.3 窗口的显示与更新62.3 MFC的应用与对话框编程72.3.1 基于对话框的应用程序82.3.2 对话框类CDialog92.3.3 向对话框类中添加菜单10第3章 数据结构123.1 数据结构简介123.1.1 什么是数据结构123.1.2 算法和算法分析133.2 线性表143.2.1 内容简介143.2.2 实例分析153.3 栈和队列163.3.1 内容简介163.3.2 实例分析163.4 串173.4.1 内容简介173.4.2 实例分析173.5 数组和广

8、义表183.5.1 内容简介183.5.2 实例分析193.6 树和二叉树193.6.1 内容简介193.6.2 实例分析203.7 图203.7.1 内容简介203.7.2 实例分析213.8 动态存储管理223.8.1 内容简介223.8.2 实例分析223.9 查找233.9.1 内容简介233.9.2 实例分析233.10 内部排序243.10.1 内容简介243.10.2 实例分析243.11 外部排序253.11.1 内容简介253.11.2 实例分析253.12 文件263.12.1 内容简介263.12.2 实例分析26第4章 示例演示284. 1 系统平台284. 2 算法演

9、示28结 论32致 谢33参考文献3434 / 38文档可自由编辑打印第1章 绪论1.1 选题背景数据结构是计算机及相关专业中一门重要的专业基础课程，也是其它理工专业的热门选修课。它涉及数据在计算机中的表示、组织和处理，以及相应结构上的算法设计和初步的算法性能分析技术。其研究思想和研究方法在计算机科学中许多有尝试的研究领域得到广泛的应用，为学生今后从事理论研究、应用开发、技术管理工作提供了坚实的理论基础。但该课程具有相当的抽象性和动态性，容易造成教学低效和学时膨胀。如何使学生更好地掌握最常用的数据结构，理解数据结构内在的逻辑关系，数据与关系在计算机中存储表示以及在这些数据结构上的去处和实际的执

10、行算法，培养学生解决实际问题的程序设计能力以适应学科迅速发展和知识更新的需要，是这一门课程的目的和宗旨。现今，各大学的数据结构课程的教材和内容都主要集中在“基本数据结构的阐述和分析、基本数据结构的应用、典型算法的适当渗透”这三个方面。其中，前两部分是重点，并占据了较多的篇幅，而这些内容的教与学离不开大量的实践。所以在数据结构与算法课程教学中经常会有大量的课程实验作为辅助。通过进一步的深入分析可以看出，上述基本知识的学习并不是最终目标，而是为到达最终目标打下的基础，学习数据结构的更深层次的目标是能够针对实际问题来选择扩展甚至设计全新的数据结构，然后设计相应的存储结构并加以实现，从而最终完成问题的

11、求解。1.2 研究内容 通过以上分析，可以看出，数据结构作为计算机相关专业的基础课，发挥着越来越重要的作用，但由于数据结构这门课程的学习过于抽象，因此，本文以实验平台的形式帮助学生学习。通过对相关背景的了解，本文志在研究以下问题：1) 深入分析了VC编程工具，本文所开发的数据结构实验平台使用VC进行编程；2) 使用VC实现数据结构的基本算法，包括线性表、栈、数组、树、图等。使得这门课的内容更加贴切的展现出来；3) 使用实例对系统进行测试。第2章 VC环境计算机语言指用于人与计算机之间通讯的语言。计算机语言是人与计算机之间传递信息的媒介。计算机程序设计语言的发展，经历了从机器语言、汇编语言到高级

12、语言的历程。不同的设计要求，选用的语言种类以及程序的架构模式各不相同。当前两种主流的程序架构模式C/S以及B/S，所使用的编程语言略有不同。C/S模式即是客户机和服务器结构，主要使用的编程语言有：VB、VF、VC等；B/S模式即是浏览器和服务器结构，主要使用的编程语言有：ASP、ASP.NET、PHP、JSP等。C/S模式历经多年的发展，技术成熟，安全性能高，与windows系统的契合度较高；B/S模式则是近年兴起的一种新兴模式，在网络发达的今天，越来越受重视，但由于发展时间稍短，安全问题比较突出。本文选择C/S模式，编程语言使用比VB、VF相对流行的VC语言。本章内容主要包括三个方面：一、学

13、习面向对象的概念；二、学习WINDOWS编程基础知识；三、MFC的应用与对话框编程。2.1 什么是面向对象面向对象是一种新的软件设计思想。这种思想力求使软件系统直接模拟现实世界，尽量将现实世界中的事物直接映射到软件的解空间，从而使用户能够轻松地、最大程度地使用软件系统解决现实问题。对象是面向对象思想的核心，正确地定义和理解它是掌握面向对象理论的前提。一般认为，对象存在两方面的含义，即在现实世界中的含义和在计算机世界中的含义。在现实世界中，我们身边实实在在的人和物都是对象，不可触摸的时间、事件也是对象，这种情况下，对象是现实世界中的一个实体。只要我们继续研究，就会发现，这些对象都具备三个共同特征

14、：有一个与其他事物区分开来的标识，具有可以描述自身的状态或属性；具有可以作用于自身和其他对象的操作。因此可以认为，对象是封闭了实体状态属性和可以施加于该实体的操作的描述体。在计算机世界中，对象是存储器中一块可标识的区域，它保存了关于实体的属性和操作的数据值。综合上述两方面的含义，可以给对象一个更加明确的定义：对象是问题域及其实现中的一些事物 的抽象，它反映系统为之保存信息和与之交互的能力，是一些属性及其专用服务的一个封装体。以对象的观点分析问题和解决问题，出现了面向对象分析（OOA）、面向对象设计（OOD）和面向对象编程（OOP）等概念。面向对象思想不但符合现实生活的实际善，也符合人们的思维习

15、惯。一个符合面向对象思想的系统，必须具备以下三方面的特性：封装性 对象是属性数据和对属性数据进行的操作的集合体，而封闭性把这些数据和操作屏蔽起来，使用户不必知道对象行为的实现细节，只需根据对象提供人的外部特性接口访问对象即可。C+类的定义体现了封闭性的基本特性。继承性 继承是一种表示对象类之间的相似性的机制，它使得某类对象可以具有另一类对象的特征和能力。C+语言的继承性表现在对类的单继承和多继承支持。多态性 不同的对象收到相同的消息时能产生不同的动作。C+语言支持两种多态性：静态性和动态多态性。静态多态性是通过重载实现的，到底执行函数的哪个版本在编译阶段确定；动态多态性是通过虚函数实现的，到底

16、执行函数的哪个版本，需要在运行时找出发出消息的对象后才能确定。基于上述标准，可以把使用对象的计算机语言分为面向对象和基于对象两种。而开发本程序的C+语言就属于面向对象语言。2.2 WINDOWS编程基础知识WINDOWS界面包括了丰富的标准用户界面对象元素，如：窗口、图标、菜单、滚动条、对话框、控件和消息框等。为了设计出具有WINDOWS标准风格的应用程序，必须了解这些窗口的标准元素性质及其作用。2.2.1 定义窗口类的结构由于WINDOWS窗口具有标准的我，所以，在创建窗口之前，完全可以对窗口的共同我进行描述，然后，根据描述的属性，建立可视化的交互界面，即窗口。WIN32的窗口类就是窗口共性

17、的一个数据结构，它描述了窗口样式、窗口消息处理函数、程序句柄、程序句柄、图标、光标、背景刷、菜单以及描述本窗口类型的结构名称。 WNDCLASS结构描述下面的WNDCLASS结构为WINDOWS的窗口类定义。Typedef structUINT style;WNDPROC lpfnWndProc;Int cbClsExtra;Int cbWndExtra;HINSTANCE hInstance;HICON hIcon;HCURSOR Hcursor;HBRUSH hbrBackground;LPCTSTR lpszMenuName;LPCTSTR lpszClassName;WNDCLASS,

18、 * PWNDCLASS;上述各项含义：Style 指定窗口格局的整型数，如移动或改变窗口大小时，自动重画窗口。lpfnWndProc 负责控制窗口、处理窗口消息的窗口函数，本函数由系统调用。cbClsExtra 是为指定这个窗口类别结构额外分配的字节数，一般设为0.cbWndExtra 是为这个类别中所有窗口结构额外分配的字节数，一般设为0.hInstance 标志要创建的窗口所属应用程序的句柄。HIcon 指定窗口缩小成最小时的图形标志的句柄。hCursor 窗口中所使用的光标的句柄。hbrBackground 用来画窗口背景的刷的句柄。lpszMenuName 标志窗口中的菜单资源名字的

19、字符串。lpszClassName 标志该窗口类别的名称的字符串。2.2.2 窗口类的注册与窗口创建（1）窗口类的注册定义一个WNDCLASS结构变量，指定每个域的聚会后，便已经完成了一个窗口类的指定。但是，在创建窗口前，还有一件重要事情要做，就是使用RegisterClass函数注册该窗口类。注册的目的是为了系统，由该窗口类创建的窗口与其指定的窗口函数发生关联。注册窗口类的代码如下：If(!RegisterClass(&wndclass)MessageBox(NULL,TEXT(“This program requires Windows NT!”),szAppName,MB_ICO

20、NERROR);Return 0;RegisterClass函数接收的是一个WNDCLASS结构的指针。如果注册成功，RegisterClass返回TRUE,否则返回FALSE。只有注册成功后，才能创建窗口。（2）窗口的创建如果窗口类注册成功，下一步，便可以使用该窗口创建窗口了。使用CreateWindow函数创建窗口，如果创建成功，则返回一个系统分配的窗口句柄，否则，返回0.CreateWindow函数的参数包括：窗口类别名窗口标题窗口规格窗口位置父窗口句柄菜单句柄应用程序事例句柄32位附加数据创建窗口的代码如下：Hwnd=CreateWindow(“MyWndClass”, /window

21、 class name “The Hello Program”, /window caption “WS_OVERLAPPEDWINDOW /window style CW_USEDERAULT, /initial x positionCW_USEDEFAULT, /initial y positionCW_USEDEFAULT, /initial x sizeCW_USEDEFAULT, /initial y sizeNULL, /parent window handleNULL, /window menu handlehInstance, /program instance hadleNU

22、LL);/creation parameters第1个参数“MyWndClass”,指定的是注册成功的窗口类名。第2个参数”The Hello Program”，指定的是窗口的标题。第3 个参数WS_OVERLAPPEDWINDOW指定窗口的类型为可重叠式窗口。第4到第7个参数分别指定窗口的位置和大小，单位 为像素。第8个参数NULL表示要创建的窗口为顶层窗口，没有你窗口，因为这是可重叠 式窗口；当然，如果是子窗口攻其无备弹出式窗口，那么很可能 有父窗口，这时该参数应该为父窗口的句柄。第9个参数用来指定菜单资源。第10个参数为hInsance,指定拥有此窗口的应用程序实例句柄。最后一个参数是窗

23、口函数使用的额外数据。2.2.3 窗口的显示与更新当CreateWindow返回的hwnd不为零时，说明窗口已经创建成功，系统已经为该窗口分配内在，并把内存的索引返回。但是，这时，窗口并没有显示出来，需要使用ShowWindow函数来显示窗口，并用UpdateWindow函数更新窗口的客户区。这两个函数的代码如下：ShowWindow(hwnd,SW_SHOW);UpdateWindow(hwnd);ShowWindow函数告诉系统显示新的窗口，第1个参数是要的窗口的句柄，第2个参数表示窗口以什么样式显示，如是成图标，或者最大化等，这里为SW_SHOW表示正常显示。一般在显示窗口后，需要马上调

24、用UpdateWindow函数。UpdateWindow函数会给刚显示的窗口发出WM_PAINT消息，以通知窗口函数更新窗口。2.3 MFC的应用与对话框编程本实验平台是基于MFC技术，用对话框进行编程。对话框在窗口应用中扮演了非常重要的角色。几乎在每一个MFC窗口中都可以见到对话框的身影。从对话框的工作方式上分，对话框可以分为模态对话框和非模态对话框两种类型。用户平常使用的对话框大部分都是模态对话框，模态对话框在关闭之前，不允许用户切换到程序的其他窗口。这是因为当弹出模态对话框时，这个对话框就获得了程序的控制权，并且模态对话框拥有自己的消息循环，因此应用程序的其他窗口所产生的消息都不会送到消

25、息主窗口的消息循环中。区别于模态对话框，非模态对话框弹出后，用户不需要关闭它就可以在非模态对话框之间进行切换。声明一个模态对话框对象的方法如下：BOOL CHjApp:InitInstance()AfxEnableControlContainer();CDMain dlg;Dlg.DoModal();Return TRUE;从上面可以看出，声明一个模态对话框要以在某成员函数的内部，只需要调用DoModal()成员函数即可。如果要创建一个非模态的对话框，就会麻烦一些，需要调用Create()函数装入对话框资源：Dlg=new CDMain;Dlg->Create(IDD_MAINDLG);

26、Dlg->ShowWindow(SW_SHOW);在对话框使用完毕后需要用delete()删除对话框对象。2.3.1 基于对话框的应用程序创建基于对话框的应用程序，可以用MFC AppWizard应用程序向导来创建。打开Visual C+6.0,执行“File”/”New”菜单命令，打开“New”对话框。选择”Projects”选项卡，在列表框中选择”MFC AppWizardexe”列表项，再在右侧添加项目名称，如图2-1，单击“OK”按钮进入MFC AppWizard-step1对话框。2-1 MFC AppWizard-step1对话框如图2-2，选择本实验平台所用的Dialog

27、based类型，点击next,直到MFC AppWizard-step4.图2-2 MFC AppWizard-step1如图2-3,注意，系统自动为我们生成了两个类（如下图所示），分别为CWmApp和CWmDlg。单击”Finish”,完成创建。图2-3 MFC AppWizard-step 对话框类CDialog为了程序方便地实现对话框的功能，MFC提供了一系列对话框类，并实现了对话框消息响应和处理机制。CDialog类是对话框中最重要的类，用户在程序中创建的对话框通常都是从此类派生的，CDialog类还是其他所有对话框类的基类。CDialog是从CWnd派生而来的，所以它继

28、承了CWnd类的成员函数，具有CWnd的基本功能，可以编写代码移动 、显示或隐藏对话框。表2-1为常用的成员函数。表2-1 CDialog类中常用的成员函数成员函数功能CDialog()通过调用派生类构造函数，根据对话框模板定义一个对话框DoModel()激活模态对话框，显示对话框窗口Create()根据对话框模板创建非模态对话框OnOK()单击OK按钮调用该函数，接收用户输入后退出OnCancel()单击Cancel按钮或Esc按钮键时调用该函数，不接收用户输入直接退出OnInitDialog()WM_INITDIALOG的消息响应函数，在显示对话框系统会调用该函数进行初始化工作EndDia

29、log()用于关闭模态框窗口ShowWindow()显示或隐藏对话框窗口DestroyWindow()关闭或摧毁非模态对话框UpdateData()通过调用DoDataExchange()设置或获取对话框控件的数据DoDataExchange()被UpdateData()调用以实现对话框数据交换，不能直接调用GetWindowText()获取对话框窗口的标题SetWindowText()修改对话框窗口的标题GetDlgItemText()获取对话框中控件的文本内容SetDlgItemText()修改对话框中控件的文本内容GetDlgItem()获取控件或子窗口的指针MoveWindow()用于

30、移动对话框窗口EnableWindow()使窗口处于无效或有效状态2.3.3 向对话框类中添加菜单利用AppWiazird建立一个基于对话框的应用程序wm；在wm中利用菜单生成器创建一个菜单栏IDR_MENU,如图2-4、2-5图2-4 插入菜单图2-5 插入菜单资源在对话框资源中单击鼠标右键，在弹出的快捷菜单上选择”properties”菜单项，打开”Dialog Properties”对话框；在”Dialog Properties”对话框中的Menu组合框中选择“IDR_MENU”，如图2-6图2-6 插入菜单函数模块再在”Dialog”中拖入两个edit和一个button,即完成了主要的

31、框架。第3章 数据结构自1946年第一台计算机问世以来，计算机产业的飞速发展已远远走出人们对它的预料，在某些生产线上，甚至几秒钟就能生产出一台微型计算机，产量猛增，价格低廉，这就使得它的应用范围迅速扩展。如今，计算机已深入到人类社会的各个领域。计算机的应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。与此相应，计算机加式处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据，这就给程序设计带来一些新的问题。为了编写出一个“好”的程序，必须分析待处理的对象的我以及各处理的对象的我以及各处理对象之间存在的关系。这就是“数据结构”这门学科形成和发展的背景

32、。3.1 数据结构简介一般来说，用计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型算法，最后编出程序，进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学煌语言加以描述。例如，求解梁架结构中应力的数学模型为纯属议程组；预报人口听常数模型为微分方程。然而，更多的非数值计算问题无法用数学方程加以描述。3.1.1 什么是数据结构 “数据结构”作为一门独立的课程在国处是从1968年才开始设立的。在这之前，它的某些内容曾在其他课程，如表处理语言中有所阐述。196

33、8年在美国一些大学的计算机系的教学中，虽然把“数据结构”规定为一门课程，但对课程的范围仍没有作明确规定。当时数据结构几乎和图论，特别是和表、树的理论为同义语。随后，数据结构这个概念被扩充到包括网络、集合代数论、格、关系等方面，因此，不仅考虑数据本身的数学性质，而且还必须考虑数据的存储结构，这就进一步扩大了数据结构的内容。近年来，随着数据库系统的不断发展，在“数据结构”课程中又增加了文件管理（特别是大型文件的组织等）的内容。1968年美国唐欧克努特教授开创了“数据结构”的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从20世纪60年

34、代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主阿内容，人们就越来越重视“数据结构”，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。从20世纪70年代中期到80年代初，各种版本的数据结构著作就相继出现。目前在我国，“数据结构”也已经不仅仅是计算机专业的教学中的核心课程之一，而且是其他非计算机专业的主要等候课程之一。“数据结构”在计算机科学中是一门综合性的专业基础课。“数据结构”的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据

35、元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。因此，可以认为“数据结构”是介于数学、计算机硬件和计算机软件三者之间的一门核心课程（如图所示）。在计算机退票中，“数据结构”不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。值得注意的是，“数据结构”的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来讨论数据结构，已成为一种新的趋势，越来越被人们所重视。3.1.2 算法和算法分析1

36、 算法算法是对特定问题求解步骤的一种描述，它是有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列5个重要特性：有穷性 一个算法必须总是（对任何合法的输入值在执行有穷步之后结束，且每一步都可在有穷时间表内完成。确定性 算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得出相同的输出。可行性 一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。输入 一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。输出 一个算法有一个或多个的输出，这些输出是同输入法有着某

37、些特定关系的量。2 算法的设计要求通常设计一个“好”的算法应考虑达到以下目标。正确性 算法应当满足具体问题的需求。可读性 算法主要是为了人的阅读与交流，其次才是机器执行，可读性好有助于人对算法的理解；晦涩对懂的程序易于隐藏较多错误，难以调试和修改。健壮性 当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫明其妙的输出结果。效率与低存储量需求 通俗地说，效率指的是算法执行的时间。3 算法效率的度量算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。事后统计的方法 因为很多计算机内部都有计时功能，有的甚至可精确到毫秒级，不

38、同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。事前分析估算的方法 一个用高级程序评议编写的程序在计算机上运行时所消耗的时间取决于下列因素：依据的算法选用何种策略；问题规模；书写程序的语言，对于同一个算法，实现语言的级别越高，执行效率就越低；编译程序所产生的机器代码的质量；机器执行指令的速度。3.2 线性表3.2.1 内容简介本节主要内容包括4个方面，分别为：线性表的类型定义，线性表的顺序表示和实现，线性表的链式表示和实现，以及一元多项式的表示及相加。其中线性表的链式表示和实现又包括：线性链表、循环链表和双向链表。3.2.2 实例分析例1 算法2.2void MergeList(Lis

39、t La, List Lb, List &Lc) / 算法2.2 / 已知线性表La和Lb中的元素按值非递减排列。 / 归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。 int La_len, Lb_len; ElemType ai, bj; int i=1, j=1, k=0; InitList(Lc); La_len = ListLength(La); Lb_len = ListLength(Lb); while (i <= La_len) && (j <= Lb_len) / La和Lb均非空 GetElem(La, i, ai); Ge

40、tElem(Lb, j, bj); if (ai <= bj) ListInsert(Lc, +k, ai); +i; else ListInsert(Lc, +k, bj); +j; while (i <= La_len) GetElem(La, i+, ai); ListInsert(Lc, +k, ai); while (j <= Lb_len) GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / MergeList3.3 栈和队列3.3.1 内容简介本节主要内容包括5个方面,分别为：栈，栈的应用举例，栈与递归的实现，队列，以及

41、实现离散事件模拟。其中栈分为：抽象数据类型栈的定义，栈的表示和实现；栈的应用举例分为：数制转换，括号匹配的检验，行编辑程序，迷宫求解，表达式求值；队列分为：抽象数据类型队列的定义，链队列队列的链式表示和实现，循环队列队列的顺序表示。3.3.2 实例分析例2 算法3.2void LineEdit() / 算法3.2 /利用字符栈S，从终端接收一行并传送至调用过程的数据区。 char ch,*temp; SqStack S; InitStack(S); /构造空栈S printf("请输入一行(#:退格；:清行):n"); ch = getchar(); /从终端接收第一个字符

42、 while (ch != EOF) /EOF为全文结束符 while (ch != EOF && ch != 'n') switch (ch) case '#': Pop(S, ch); break; / 仅当栈非空时退栈 case '': ClearStack(S); break; / 重置S为空栈 default : Push(S, ch); break; / 有效字符进栈,未考虑栈满情形 ch = getchar(); / 从终端接收下一个字符 temp=S.base; while(temp!=S.top) printf(

43、"%c",*temp); +temp; / 将从栈底到栈顶的栈内字符传送至调用过程的数据区； ClearStack(S); / 重置S为空栈 printf("n"); if (ch != EOF) printf("请输入一行(#:退格；:清行):n"); ch = getchar(); DestroyStack(S);3.4串3.4.1 内容简介本章主要内容包括4个方面，分别为：串类型的定义，串的表示和实现，串的模式匹配算法，串操作应用举例。其中串的表示和实现分为：定长顺序存储表示，堆分配存储表示，串的块链存储表示；串的模式匹配算法分

44、为：求子串位置的定位函数index(S,T,pos)，模式匹配的一种改进算法；串操作应用举例分为：文本编辑，建立词索引表。3.4.2 实例分析例3 算法4.8void get_nextval(SString T, int *next) / 算法4.8 / 求模式串T的next函数修正值并存入数组nextval。 int i = 1; int j = 0; next1 = 0; while (i<T0) if (j=0 | Ti=Tj) +i; +j; if (Ti!=Tj) nexti = j; else nexti = nextj; else j = nextj; / get_next

45、valint Index_KMP(SString S, SString T, int pos) / 算法4.6 / 利用模式串T的next函数求T在主串S中第pos个字符之后的位置 / 的KMP算法。其中，T非空，1posStrLength(S)。 int next255; int i = pos; int j = 1; get_nextval(T, next); while (i<=S0 && j<=T0) if (j=0 | Si=Tj) +i; +j; / 继续比较后继字符 else j = nextj; / 模式串向右移动 if (j>T0) retu

46、rn i-T0; / 匹配成功 else return 0; / Index_KMP3.5数组和广义表3.5.1 内容简介本节内容主要包括7个方面，分别人：数组的定义，数组的顺序表示和实现，矩阵的压缩存储， 广义表的定义，广义表的存储结构，M元多项式的表示，以及广义表的递归算法。其中矩阵的压缩存储分为：特殊矩阵，稀疏矩阵；广义表的递归算法分为：求广义表的深度，复制广义表，建立广义表的存储结构。3.5.2 实例分析例4 算法5.2Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) / 算法5.2 / 采用三元组顺序表存储表示，求稀疏矩

47、阵M的转置矩阵T int col, t, p, q; int num20, cpot20; T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col<=M.nu; +col) numcol = 0; for (t=1; t<=M.tu; +t) / 求 M 中每一列所含非零元的个数 +numM.datat.j; cpot1 = 1; / 求 M 中每一列的第一个非零元在 b.data 中的序号 for (col=2; col<=M.nu; +col) cpotcol = cpotcol-1+numcol-

48、1; for (p=1; p<=M.tu; +p) col = M.datap.j; q = cpotcol; T.dataq.i =M.datap.j; T.dataq.j =M.datap.i; T.dataq.e =M.datap.e; +cpotcol; / for / if return OK; / FastTransposeSMatrix3.6树和二叉树3.6.1 内容简介本节主要内容包括8个方面，分别为：树的定义和基本术语,二叉树，遍历二叉树和线索二叉树，树和森林，树与等价问题，赫夫曼树及其应用，回溯法与树的遍历，树的计数。其中二叉树分为：二叉树的定义，二叉树的性质，二叉树

49、的存储结构；遍历二叉树和线索二叉树分为：遍历二叉树，线索二叉树；树和森林分为：树的存储结构，森林与二叉树的转换，树和森林的遍历；赫夫曼树及其应用分为：最优二叉树（赫夫曼树），赫夫曼编码。3.6.2 实例分析例5 算法6.1Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) / 算法6.1 / 采用二叉链表存储结构，Visit是对数据元素操作的应用函数， / 先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。 / 最简单的Visit函数是： / Status PrintElement( ElemType e )

50、/ 输出元素e的值 / printf( e ); / 实用时，加上格式串 / return OK; / / 调用实例：PreOrderTraverse(T, PrintElement); if (T) if (Visit(T->data) if (PreOrderTraverse(T->lchild, Visit) if (PreOrderTraverse(T->rchild, Visit) return OK; return ERROR; else return OK; / PreOrderTraverse3.7图3.7.1 内容简介本节主要内容包括6个方面，分别为：图的定

51、义和术语，图的存储结构，图的遍历，图的连通性问题，有向无环图及其应用，最短路径。其中图的存储结构分为：数组表示法，邻接表，十字链表，邻接多重表；图的遍历分为：深度优先搜索，广度优先搜索；图的连通性问题分为：无向图的连通分量和生成树，有向图的强连通分量，最小生成树，关节点和重连通分量；有向无环图及其应用分为：拓扑排序，关键路径；最短路径分为：从某个源点到其余各顶点的最短路径，每一对顶点之间的最短路径。3.7.2 实例分析例6 算法7.1Status CreateUDN(MGraph &G) / 算法 7.2 / 采用数组（邻接矩阵）表示法，构造无向网G。 int i,j,k,w; Ver

52、texType v1,v2; printf("G.vexnum :" ); scanf("%d",&G.vexnum); printf("G.arcnum :"); scanf("%d",&G.arcnum); getchar(); /* 加上此句getchar()! */ / scanf("%d,%d,%d",&G.vexnum, &G.arcnum, &IncInfo); for (i=0; i<G.vexnum; i+ ) printf("G.vexs%d : ",i); scanf("%c",&G.vexsi); getchar(); / 构造顶点向量 for (i=0; i<G.vexnum; +i ) / 初始化邻接矩阵 for (j=0; j<G.vexnum; +j ) G.arcsij.adj = INFINITY; /adj,info G.= NULL; for (k=0; k<G.arcnum; +k ) / 构造邻接矩阵 printf("v1 (char) : "