数据结构与算法论文

《数据结构与算法论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、•i果程学习总结班级学号姓名考核成绩一、学习内容总结(按章节进行)第一章：数据结构和算法本章主要是对数据、数据类型、数据结构、算法及算法分析等基本概念的常握，而如何合理地组织数据、高效地处理数据正是扩大计算机领域、提高软件效率的关键，所以对这些概念的理解就显得十分重要。数据是指描述客观事物的数值、字符、相关符号等所有能够输入到计算机中并能被计算机程序处理的符号的总称，其基本单位是数据元素，而数据类型是一个同类值的集合和定义在这个值集上的一组操作的总称。在高级程序语言屮定义一种数据类型时，编译程序编译系

2、统就能获得如下信息：(1)、一组性质相同的值的集合；(2)、一个预订的存储体系；(3)、定义在这个值集合上的一组集合。数据结构是指数据元素之间的关系，它包括数据的逻辑结构、存储结构、一组运算集合；数据的逻辑结构(即数据结构)分为线性结构和非线性结构，数据的存储方法有：顺序存储方法、连接存储方法、索引存储方法和散列存储方法。接下来便是关于算法的有关概念，算法是为解决一个特定问题而釆取的确定的有限步骤集合，它具有有穷性、确定性、可行性、输入和输出。关于算法的性能分析，分为时间性能分析和空间性能分析，在这里

3、要记得常见的时间复杂度的比较：O(l)

4、找、二分查找及分块查找等查找方法。其中以分块查找的效率最优，但必须在有序表屮完成查找运算。接下来是关于排序的算法，通常排序的方法有直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序，它们的算法时I'可复杂度如下：排序方法平均时间复杂度最坏时间复杂度辅助存储空间克接插入排序O(n2)0(n2)0(1)希尔排序0(n3/2)0(n3/2)0(1)冒泡排序0(n2)0(n2)0(1)快速排序0(nlog2n)0(n2)0(nlog2n)直接选择排序0(n2)0(n2)0(1)归并排序0(nl

5、og2n)0(nlog2n)0(n)由上表可以看111:1、就时间性能而言，快速排序和归并排序较好，但快速排序在最坏的情况下的时间性能不如归并排序。2、归并排序的时间性能虽然很好，但它所需要的辅助存储空间最多，空间性能较差。3、从方法的稳定性來看，时间性能较好的内部排序方法如快速排序、希尔排序等都是不稳定的。第三章：链表及其应用链表是一种简单、常用的数据结构，与顺序表相比，具有插入、删除结点不需要移动元素，不必事先估计存储空间大小等优点，操作较为灵活。它有六种基本运算：（1）、置空表（2）、求表长（3

6、）、按序号取元素（4）、按值查找（5）、插入（6）、删除。单链表即链表的每个结点只有一个指针域，用来存储其直接后继的存储位置。但是这样就使得对结点前面的元素的操作很困难，所以就在每个结点增加一个指向其前驱结点的指针域，从而构成双向链表。同时由于每个结点的地址既存放在其前驱结点的后继指针中，乂存放在其后继结点的前驱指针域屮，所以双向链表的插入操作分为前插和后插。第四章：堆栈及其应用首先要明白栈是一种受限制的线性结构，遵守“先进后出”的规则，其插入与删除操作都在栈顶进行。其次根据顺序存储和链接存储，栈分为

7、顺序栈和链栈。其中顺序栈栈是用地址连续的存储空间依次存储栈中数据元素，并记录当前栈顶数据元素的位置；基本算法包括置空栈、判栈空、判栈满、取栈顶元素、入栈和出栈。而链栈则使用链式存储堆栈的数据元素，并记录当前栈顶数据元素的位置；每个结点包括data数据域：用來存放数据元素的值，next指针域：用來存放其直接后继结点的存储地址，其基本运算和顺序栈相同。最后是关于堆栈的应用：（1）、数值转换问题；由于在将十进制数N转换为d进制数时，最先得到的余数是d进制数的最低位，在显示结果时需要最后输出；而最后求得的余数

8、是d进制数的最高位，需要最先输出。这与栈的“先入后出”性质相吻合，所以可用栈来存放逐次求得的余数，然后输出。（2）、括号匹配问题；当读収一个表达式时，一旦读到括号就进栈，而读到下一个括号时就与栈屮括号比较，若相匹配，则出栈，否则继续读取表达式。到最后，如果栈为空栈，则说明括号兀配，否则括号不匹配。第五章：队列及其应用首先和栈一样，要知道队列是一种受限制的线性结构，遵守“先进先出”的规则，其插入在队尾、删除在对头。其次根据顺序存储和链式存储，队列也分为顺序