“数据结构与算法”课程学习总结报告.doc

《“数据结构与算法”课程学习总结报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构课程总结孙博110401104511计本3班如何合理的组织数据、高效的处理数据是扩大计算机应用领域、提高软件效率的关键。而在软件开发过程中人们会要求软件工程师们使程序有更高的运行效率。因此要成为一名合格的软件编程员，必须具备数据结构领域和算法设计领域的专门知识。本学期我们在李红老师的带领下学习了《数据结构结构与算法》一书。这本书安排十分合理，在第一章对全书进行导引和学习的基础知识、预备知识。在2—6章中使逻辑结构为“线性”的数据结构及其应用知识内容。在7、8章中使逻辑结构中的为“树形”的数据结构及应哟就能够只是内容。在第九章中使逻辑结构为“集合

2、性”的数据元素在三列存储下的数据结构及其应用知识内容。在第十章使逻辑结构为“图形”的数据数据结构及其应用知识内容。下面将对各章的内容惊醒总结：第一章：首先介绍了数据的相关知识，讲述了数据的概、构成等，数据的最小组成单位。然后讲述了数据类型与数据结构。数据类型包括概念及定义，数据类型包括简单数据类型和复杂数据。简单数据类型有：整数，实属，字符，指针，枚举量等。而复杂数据类型包括：数组，结构图，共用体。而数据结构主要使讨论元素之间的关系，数据结构包括三方面内容，及逻辑结构，存储结构以及一组运算集合。数据的逻辑结构有四种基本结构：集合性结构，线性结构，树形结

3、构，图形结构。数据的存储结构是指数据严肃在存储器中的存储方式包括顺序存储，链表存储，索引存储，散列存储。然后介绍以前学习的C语言（及本教材的使用的算法描述工具）知识锦兴路回顾包括指针、结构比阿亮、函数、递归、动态存储分配、文件操作等内容。第二章：顺序表及其应用主要介绍的是线性逻辑结构的呼声几乎在顺序存储方法下的数据结构顺序标的概念、数据类型、数据结构、基本运算及相关应用问题。应用一：查找—介绍了两种方法：简单顺序查找（从书序标的一端来时扫描，将待查找元素与数据节点中的个元素比较。若相等，则查找成功，否则失败）和二分查找（将表中间的记录的关键字与给定的值

4、比较，若相等，则成功。否则，将顺序表风味左右两个字表，然后在子表中进一步查找。）应用二：排序问题—介绍了交换排序，选择排序，插入排序，归并排序。1、插入排序包括直接插入排序(将顺序表分为左右两个子表，左子表为有序表，右子表为无序表，将右子表中的元素插入左子表中)和希尔排序法（将整个待排序的元素序列分割成若干子序列，对每个子序列分别进行直接插入排序，当整个带排序元素序列“基本有序时”，在进行直接插入排序）2、交换排序a)冒泡排序：两辆比较待排序元素的关键字，发现相反时即进行交换，知道没有逆序的元素为止。b)快速排序算法：在待排序的元素中选定一个“中间数”

5、，将其他数据元素与该数比较，将比其小的数据放道左子表中，比起大的放入右子表中。3、选择排序a)直接选择排序：将数据进行多谈排序，每趟选出其中的最大数或最小数放在最终位置上，每趟中已排好的数不再参加下一轮的排序。b)堆排序：输出堆顶元素à将剩余元素按关键字大小重诚信排列成一个堆à重复上述2个步骤2、归并排序将两个或两个以上的有序表合并成一个新的有序表。应用三：字符处理问题介绍了串和顺序串的定义及相关概念，还有顺序串的基本算法。第三章：介绍链表。链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要

6、移动元素，给算法的效率带来较大的提高，且在存储空间上有动态申请的优点。这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。弄清其个运算的算法思想及其时间复杂度和空间性能。最后介绍了链表之中存储结构在实际中的相关应用。a)单循环链表是一种首尾相接的单链表，终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指针或尾指针。采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O(n)，不用遍历

7、整个链表。b)双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior，形成两条不同方向的链。由头指针head惟一确定。双链表也可以头尾相构成双循环链表。双链表上的插入和删除时间复杂度均为O(1)。顺序表和链表的比较a）基本空间的考虑存储密度是指节点数据本身所占的存储量除以结点构所占的存储总量所得的值。值越大存储空间利用率越高。顺序表是静态分配的，存储密度为1,链表是动态分配的，存储密度小于1。b)顺序表适用于静态查找，要进行删除和插入操作时，需移动大量结点。链表适用于做动态的插入和删除。第四章：堆栈是运算受限制的线性结构

8、。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的