文档介绍：…………………………装………………………………订………………………………线………………………………
课程学习总结
班级
学号
姓名
考核成绩
学习内容总结(按章节进行)
第一章:数据结构和算法
本章主要是对数据、数据类型、数据结构、算法及算法分析等基本概念的掌握,而如何合理地组织数据、高效地处理数据正是扩大计算机领域、提高软件效率的关键,所以对这些概念的理解就显得十分重要。
数据是指描述客观事物的数值、字符、相关符号等所有能够输入到计算机中并能被计算机程序处理的符号的总称,其基本单位是数据元素,而数据类型是一个同类值的集合和定义在这个值集上的一组操作的总称。在高级程序语言中定义一种数据类型时,编译程序编译系统就能获得如下信息:(1)、一组性质相同的值的集合;(2)、一个预订的存储体系;(3)、定义在这个值集合上的一组集合。数据结构是指数据元素之间的关系,它包括数据的逻辑结构、存储结构、一组运算集合;数据的逻辑结构(即数据结构)分为线性结构和非线性结构,数据的存储方法有:顺序存储方法、连接存储方法、索引存储方法和散列存储方法。接下来便是关于算法的有关概念,算法是为解决一个特定问题而采取的确定的有限步骤集合,它具有有穷性、确定性、可行性、输入和输出。关于算法的性能分析,分为时间性能分析和空间性能分析,在这里要记得常见的时间复杂度的比较:O(1)< O(logn)< O(n)< O(nlogn)< (n)< O(n)< O(n)< O(2)。
第二章:顺序表及其应用
顺序表作为一种简单而又常用的数据结构,应用范围较为广泛,本章主要是对顺序表、顺序表的结构、数据类型、基本算法及相关应用的介绍。
首先顺序表是一种简单而常用的数据结构,其应用范围较为广泛,它的基本运算包括初始化表、求表长、查找表中元素及删除元素等。在这其中,进行插入和删除操作时需要大量移动元素,算法的时间复杂度为O(n)。其次是关于查找运算,主要有简单顺序查找、二分查找及分块查找等查找方法。其中以分块查找的效率最优,但必须在有序表中完成查找运算。接下来是关于排序的算法,通常排序的方法有直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序,它们的算法时间复杂度如下:
排序方法
平均时间复杂度
最坏时间复杂度
辅助存储空间
直接插入排序
O(n)
O(n)
O(1)
希尔排序
O(n)
O(n)
O(1)
冒泡排序
O(n)
O(n2)
O(1)
快速排序
O(nlogn)
O(n)
O(nlogn)
直接选择排序
O(n)
O(n)
O(1)
归并排序
O(nlogn)
O(nlogn)
O(n)
由上表可以看出:
1、就时间性能而言,快速排序和归并排序较好,但快速排序在最坏的情况下的时间性能不如归并排序。
2、归并排序的时间性能虽然很好,但它所需要的辅助存储空间最多,空间性能较差。
3、从方法的稳定性来看,时间性能较好的内部排序方法如快速排序、希尔排序等都是不稳定的。
:链表及其应用
链表是一种简单、常用的数据结构,与顺序表相比,具有插入、删除结点不需要移动元素,不必事先估计存储空间大小等优点,操作较为灵活。它有六种基本运算:(1)、置空表(2)、求表长(3)、按序号取元素(4)、按值