摘 要

链式存储结构是数据结构中重要的学习内容，对于各种数据结构的来说，链式存储是它们链式表示和实现的前提。链式结构中基本内容如结构体、指针可拓展出多种算法，也可以根据特定的算法来选择链表与其相适应，提取数据逻辑结构后设计算法解决应用问题，设计链表算法库能有效提高该类数据结构在程序上的运行效率和存储效率。C 中面向对象的方法将数据和数据操作封装成一个整体，针对同类型数据关系抽象出共同特征，用类模板解决不同类型数据的代码通用问题。本课题以研究链表算法库为切入点，基于C 语言建立单链表、双链表算法库，添加链表可操作内容，运用链表的操作函数和原理以解决链表的游标实现和一元稀疏多项式计算器问题。

其次，本文还涉及链表的可视化演示，运用Qt框架来实现链表可视化功能，设计一系列几何对象来展示链表操作过程中指针的动态变化，用windeployqt.exe和Enigma Virtual Box整合压缩发布LinkListVisualizer.exe文件，使其可在普通windows机型下运行，便于初学者对于链表这种基础数据结构的理解。

关键词：C ；链表算法库；Qt框架；一元稀疏多项式计算器

Abstract

Linked Storage Structure is an important learning content in data structure. For various data structures, linked storage is the precondition of their chain representation and implementation. The basic knowledge in linked structure, such as structure and pointer, can extend many kinds of algorithms, and linked list can be selected by other specific algorithms. After extracting the logical structure of data, the algorithm is designed to solve the computer application problem. Designing a general algorithm library for the algorithm problem can effectively improve the operation efficiency and storage efficiency of this kind of data structure used in the program. The object-oriented method in C encapsulates data and data operations as a whole, abstracts common features for the same type of data relations, and uses class templates to solve the problem of code generalization for different types of data. This paper takes the research of linked list algorithm library as the breakthrough point, establishes single-linked list and double-linked list algorithm library based on C language to enrich the operation content of linked list, and uses the operation function or principle of linked list to solve the cursor implementation of linked list and the problem of one-dimensional sparse polynomial calculator.

Secondly, the visualization demonstration of linked list is also involved in this paper. Qt framework is used to realize the visualization function of linked list. And a series of geometric objects are designed to show the dynamic changes of pointers during the operation of linked list, then the system integration is compressed and released into LinkListVisualizer.exe file by windeployqt.exe and Enigma Virtual Box so that it can run under other ordinary windows model, which is convenient for beginners to understand the basic data structure of linked list.

Key Words：C ；Link List Algorithms Library；Qt Framework；one-dimensional sparse polynomial calculator

目录

第1章 绪论 1

1.1 研究背景及意义 1

1.2 国内外的研究现状 2

1.2.1 链表算法库 2

1.2.2 数据结构可视化 2

1.3 研究内容和技术方案分析 4

1.4 论文结构安排 5

第2章 算法库设计 6

2.1 链表结构综述 6

2.2 单链表算法库 6

2.2.1 单链表结构综述 6

2.2.2 算法实现 8

2.3 双链表算法库 15

2.3.1 双链表结构综述 15

2.3.2 算法实现 16

2.4 本章小结 19

第3章 算法库应用 20

3.1 一元稀疏多项式计算器 20

3.1.1 设计内容 20

3.1.2 计算器实现 23

3.2 游标实现 26

3.2.1 设计内容 26

3.2.2 具体函数操作实现 29

第4章 可视化演示系统 31

4.1 系统设计 31

4.1.1 功能分析 31

4.1.2 设计思想 32

4.1.3 开发平台 32

4.2 系统实现 33

4.2.1 单链表操作 34

4.2.2 双链表操作 36

4.2.3 稳定性 37

4.2.4 容错能力 38

第5章 总结和展望 40

5.1 总结 40

5.2 展望 40

参考文献 42

绪论

研究背景及意义

数据结构与算法是一切与计算机编程相关专业必备的核心课程，也是计算机软件和应用工作者必备的专业基础。数据结构是相互之间存在一种或多种特定关系的数据元素的组合^[1]，数据的逻辑结构与算法的设计相关，存储结构与算法的实现相关。许多应用软件都要用数据结构和算法编写程序来求解应用问题。

计算机处理应用问题，其实是将抽象数据的逻辑关系用物理存储表示出来，这与程序设计语言密切相关。算法的实现需要程序设计语言支持才能解决计算机应用问题，介于C语言简单易用的特点，国内大多数据结构教材内容多采用C语言教程，但是C语言模板化编程的特点严重限制了基于C语言应用的代码复用粒度^[2]。相较之下， C 这种面向对象的编程修正了许多C语言的语法缺陷，它增加类和模板、将数据和数据操作封装成一个整体、通过对象调用函数等优点可以实现数据结构的通用性。以C 标准类库STL（Standard Template Library，标准模板库)为例，STL中包含了list的容器，通过采用模板类和模板函数的方式组成双向链表库，为程序设计提供了高效的代码重用。

本题中用C 程序设计语言搭建链表算法库就是为了提高链表这种动态存储结构的通用性，使其适用于不同的系统，增强代码的复用性以减轻代码任务。本课题以研究链表算法库为切入点，基于C 语言建立单链表、双链表算法库，除结构的生成与销毁、查找、插入、删除、遍历等数据结构基本操作外以模板类和模板函数方式添加新的函数。讨论一个数据结构的同时，必须讨论在该类数据上执行的运算才有意义，该论文还将围绕着设计好的链表算法库以解决链表的游标实现和一元稀疏多项式计算器问题。

再者，通过上文可以得出，掌握扎实的数据结构是计算机有关从业人员必备的专业技能。尤其是在数据结构的学习中，对于程序设计初学者（理工科学生）而言，常规的课程学习对于展示数据结构和算法的抽象性和动态很难表示，学生无法实际看到从老师在课堂上的口头教授方式讲述的算法，而必须通过想象在脑海中呈现一套静态代码来理解数据结构的动态表示，对于算法中的细节过程难以补充，并且教材中算法范例中往往包含固有的参数，不能动态修改参数内容，容易陷入单一死板的教学，不利于学生自主深入探索。链表是所有数据结构教材中最基本的内容，对于链表的教学，仅仅描述链表的逻辑结构对于初学者来说有很大的障碍，而存储结构能直观地展现数据在计算机内的存储方式，如果能够得到直观的类链表结构可视化手段辅助，用图示的方式对算法动态执行过程进行直观可视化描述，将链表中各数据元素之间的关系以及一个结点存储下一阶段位置访问的方式动态演示出来，能够有效引导学生自主学习，主动去深入了解链表结构，进而更好运用数据结构来提高程序调试效率。

要想把链表各操作可视化演示出来，需要采取合理的可视化布局动态演示数据结构的变化过程，在链表的操作中添加一组可视属性，运用直观的符号画面表示抽象的数据及数据间的关系，设计一系列生动的几何对象，然后将每一个多维属性的数据项映射至一个对应的图标，数据项的每一维分别对应于图标的某个属性^[3]，最后对这些图标进行可视化布局。最终的可视化系统有利于程序员对程序执行过程作直观的理解，在此，本课题将以链表基本操作的可视化为目的，完成一个具备基本的链表算法库可视化的图形演示。

国内外的研究现状

链表算法库

链式存储结构是学习各种不同数据结构的链式表示和实现的前提，在对链表算法库的内容扩充上，祁建宏等人^[4]提出单链表中双插入排序算法研究，以一次插入两个元素为单位，以先确定较小位置插入位置的方式缩小查找范围；王思乐^[2]等人为基于C语言的建表代码复用问题，提出结合static 关键字和函数指针达到类似于C 对象概念的结构复用；张静[5]等人用将双链表的两个指针域保存两个地址换成一个指针域保存直接前驱结点地址和直接后继节点的地址异或值的方法，使得在不改变链表存储密度的情况下，只需要O (1)时间复杂度可以搜索到结点前后结点的地址；谭林、廖光忠[6]通过将按照一定规则插入元素的链表合并，反复执行插入合并操作的方式形成一种基于有序双链表的高效排序算法；白宇、郭显娥[7]用递归算法重新链接单链表的方法，基于分治策略提出一种平均时间复杂度为Ｏ（）的快速排序算法等等。不断有人在研究链表算法，扩充算法库内容，优化链式存储算法的同时为今后的计算机发展提供强大的支持。

数据结构可视化

数据结构可视化一直都是数据结构学习中必要的辅助内容。数据结构算法可视化教学研究工作成果可以大致分为两类：一类是简单的动画演示，单纯在于演示数据结构动态变化过程，带有固定参数；一类是采用动态交互技术，各种操作内容可选，在运行的过程中可以根据个人需求修改参数内容，注重用户与系统之间的动态交互^[4]。第一类大多出现在学校数据结构教学中，有些教师通过PowerPoint幻灯片或者Flash动画简单呈现数据结构特征，动态变化依靠图例播放展示，在可视化教学软件中，应用最广的严蔚敏教授编著的《数据结构》中专门配备描述教材中各种数据结构算法的演示光盘，国外更有匈牙利 Sapientia 大学以舞蹈展示排序算法，都属于单向输出算法结构特征。第二类动态交互技术更能展示数据结构细节变化，数据结构可视化网站Visualgo是由新加坡国立大学Steven Halim博士带领团队在2011年发布的一款可视化学习算法的工具，它显性地将代码执行过程与数据结构动态变化匹配，每一次链表结构变化对照相应的代码段，有助于学生对于代码理解，给予学生足够的学习资源。（图1.1所示）。

数据结构学习网站Data Structure Visualizations由旧金山大学David Galles副教授团队完成，给出了该网站的可视化例子html javascript代码，提供一个可视化的交互模式介绍数据结构和算法（图1.2所示）。

浙江广播电视大学科研组完成的省级立项课题《数据结构（本科）网络教学课件》中，利用java语言网络编程实现网络版可视化教学软件[8]，动画演示来展示数据结构；清华大学研制的单片机版式的可视化数据结构教学软件，界面控制按钮可以实现自动执行、单步执行等功能，还能模拟程序运行时数据变量在计算机内存中的当前值，在数据逻辑结构动态变化中全面模拟呈现各种数据结构，重在适应学生各种学习需求。

研究内容和技术方案分析

本文主要是建立单链表算法库、双链表算法库，基于两个算法库中模板函数实现链表的游标实现、完成一元稀疏多项式计算器，并且运用数据结构可视化软件将链表算法结构动态变化演示出来。

1. 用C 程序设计语言建立链表算法库，以类模板、模板函数增强链表这种链式存储结构的复用性，为其他链式存储结构的应用问题提供模板。
2. 除链表基本操作函数：链表创建、销毁、插入、查找、删除、遍历外添加排序、合并、深赋值、深拷贝等操作，尽可能全面地添加链表函数，并对函数实现进行必要的优化。链表算法库中的操作内容为游标实现、一元稀疏多项式的提供实现思路和现成函数，以实现两个系统为目的来完善链表算法库。
3. 完成链表的游标实现（静态链表）创建、插入、查找、删除、遍历等基本操作，一元稀疏多项式加法、减法、乘法、求导等运算。
4. 对链表算法库内容做可视化演示，界面布局分别有函数操作模块、暂停播放模块、使用说明、图形展示模块、代码模块。实现一款界面美观、操作人性化的交互式可视化演示软件，旨在辅助更好的教学。

论文结构安排

本文共分为五章，每章的内容描述如下：

第一章：绪论。绪论主要介绍了该课题的研究背景以及目的，分析国内外研究现状，确定课题完成内容，并且对论文结构安排做大致的总结。

第二章：建立链表算法库。包含单链表算法库和双链表算法库类模板和模板函数的研究，完善链表函数，为第二章、第三章中一元稀疏多项式计算器和游标实现打下基础。

第三章：设计一元稀疏多项式计算器的实现。对一元稀疏多项式结构与链表结构关系进行分析，设计计算器实现内容。

第四章：链表的游标实现。分析游标算法和链表算法的异同，联系它们之间共通点后参考链表实现原理，高效完成静态链表各个操作。

第五章：总结与展望。本章节主要围绕着这次课题的完成情况做一个总结，并且对目前完成内容提出未来展望。

算法库设计

链表结构综述

线性表是数据结构的基础内容，可以用顺序存储或链式存储结构存储数据，链表属于线性表以链式存储结构存储数据的数据结构。所谓链式存储结构，其主要的特点就体现在“链”字上。什么是链？就是将线性表中所有数据元素用类似一个链串起来，对于数据元素a_i来说，通过“链”可以访问与a_i有关系的其他数据元素，a_i结点除了存储自身的数据元素值之外，还要存储其他元素的地址（单链表只用存储直接后继地址，双链表要存储前驱地址和后继地址），存储链中结点的位置可以是连续的或不连续的，甚至零散分布在内存中任意位置的^[9]，这种逻辑关系表现在链表结点的指针域上。n个结点a_i(1≤i≤n)用指针链接成“链”，即为线性表：

链表结构的特点就是数据元素与数据元素之间的逻辑关系反映在结点与结点之间的链接关系上，根据指针域数量不同，链表可以分为两种：单链表和双链表。单链表的结点只有一个指针域，用来存储后继结点的地址，指针指向下一个结点，尾结点的指针指向NULL；双链表的结点有两个指针域，分别存储前驱结点和后继结点的地址，可以根据已知数据结点查找上一个和下一个结点，头结点的前驱指针指向尾结点，尾结点的后继指针指向头结点。本章主要内容就是建立单链表算法库和双链表算法库。

单链表算法库

单链表结构综述

链表中每一个结点只包含一个指针域的链表就是单链表^[10]。在单链表中，为了实现前一个元素可以直接通过访问后一个结点，需要将数据元素和它的后继元素所在地址封装成一个结点，指针域存放直接后继结点在计算机内的存储地址，数据域保存数据元素值，如图2.1所示：

为了操作方便，链表的第一个数据结点前会定义一个头结点，头结点不用保存数据元素，对于链表这种链式存储结构，每一次查找数据都要通过头结点head指针从第一个结点开始遍历访问链表其他结点，同时，由于最后一个数据元素没有直接后继，所有单链表最后一个元素指针域指向“空”（如图2.2（a）所示），当链表为空表时，头指针等于尾指针指向“空”（ 如图2.2（b）所示）。

结点结构体用C 语言描述如下所示：

template lt;typename ElemTypegt; struct Node 以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。 相关图片展示： 您需要先支付 80元 才能查看全部内容！立即支付 ﰊ PREVIOUS NEXT ﰋ 您可能感兴趣的文章 校园二手交易平台的设计与实现开题报告 基于安卓的车位智能分享及查询平台分析与设计开题报告 基于vba的画法几何试卷自动生成系统设计开题报告 企业员工信息管理平台的设计与实现开题报告 课程多媒体资源学习与管理平台设计与实现开题报告 基于安卓Android的考勤系统的设计与实现开题报告 基于不良信息字词过滤系统的网络论坛的设计与实现开题报告 高通量数据分析系统的设计与实现文献综述 基于Android的点餐系统设计与实现开题报告 基于node.js的网络书友平台的设计与实现文献综述 最新文档 华北地区夏季降水多年、少年近地层水汽场及风场分布特征开题报告 天山地区典型流域降雪分布研究文献综述 2016年台风狮子山路径突变原因的初步分析开题报告 北京和寿县地区边界层急流观测与模型的对比文献综述 具有双Kelvin波结构MJO活动的再分析开题报告 基于单片机的温控风扇设计文献综述 1961-2015年江苏省气候资源的时空分布规律开题报告 智能搬运机器人文献综述 基于类型的电影推荐系统文献综述 Bi6S2O15的合成及其降解有机污染的研究开题报告 不确定时滞奇异摄动系统的鲁棒控制器设计文献综述 小型双模SIW滤波器的研究与设计开题报告 我国绿色出行政策执行研究——以南京市为例文献综述 试论李碧华小说中的爱情悲剧开题报告 基于FPGA的电子相册设计文献综述 企业微信 推荐栏目 本站简介 人才招聘 版权声明 免责声明 毕业论文网 教育 科研 学术文档分享平台 专注服务十二年 可信/实名双认证 老牌网站值得信赖 Copyright © 2010-2022 毕业论文网 站点地图  企业微信 