|
目录
第一章、绪论
第二章、线性表
第三章、栈和队列
第四章、树和二叉树
第五章、图
第六章、查找
第七章、排序
第一章、绪论
1：算法的四个目标和五个重要特征
????????四个目标：正确性，可读性，健壮性，效率与低存储量需求
????????五个特征：有穷性，确定性，可行性，输入，输出。
2：时间复杂度：
? ? ? ? 它是分析最坏情况以估算算法执行时间的一个上界。
第二章、线性表
1：线性表的顺序表的表示和实现
? ? ? ? 概念：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。
? ? ? ? 顺序表的特点是：为表中相邻的元素ai和ai+1赋以相邻的存储位置LOC(ai)和LOC(ai+1)。
? ? ? ? 换句话说，以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。
? ? ? ? 逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，它的存储位置可以用一个简单、直观的公式来表示。
? ? ? ? 只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。通常用??数组??来描述数据结构中的顺序存储结构。
? ? ? ? 当在顺序存储结构的线性表中某个位置插入和删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入和删除元素的位置。在顺序存储结构的线性表中插入和删除一个数据元素，平均移动一半元素，若表长为 n，则算法 插入 和 删除 的时间复杂度为O(n)。
????????顺序表的存储结构的弱点：在作插入和删除操作时，需要移动大量元素。
2：线性表的链式表示和实现
? ? ? ? 线性表的链式存储结构的特点：用一组任意的存储单元村塾线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。
? ? ? ? 对于数据元素ai来说，除了存储其本身的信息外，还需要存储一个指示其后继的信息（直接后继的存储位置），这两部分信息组成数据元素的结点，包括两个域，数据域和指针域，n个结点链结成一个链表，又因为每个结点中只包含一个指针域，故又称线性链表或链表。
????????单链表是表示非随机存取的存储结构。
第三章、栈和队列
1：栈
? ? ? ? 概念：栈是限定仅在表尾进行 插入 和 删除 操作的线性表。?
? ? ? ? 对栈来说，表尾有特殊含义——栈顶，表头——栈尾。不含元素的是空栈。它的原则是后进先出。
????????顺序栈：栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素自在顺序栈中的位置。top=0表示空栈。
base可称为栈低指针?，在顺序栈中，它始终指向栈底的位置，若base为NULL，则表示栈结构不存在。
top可称为栈顶指针，其初始值指向栈底，即top=base，可作为栈空的标记，每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，top减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。
2：队列
队列：先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一端叫对尾，允许删除的一段则称为对头。
3：队列的链式表示和实现
? ? ? ? 一个链队列显然需要两个分别指示对头和队尾的指针才能唯一确定。
? ? ? ? 空的链队列的判决条件为头指针和尾指针均为指向头结点。
? ? ? ? 删除队列头元素时仅需修改头结点中的指针，但当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对尾指针重新赋值（指向头结点）。
4：队列的顺序表示和实现
? ? ? ? 在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear 分别指示队列头元素及队列尾元素的位置。
? ? ? ? 在队列初始化建空队列时，令front=rear=0；插入新的队列尾元素时，尾指针加1，删除队列头元素时，头指针加1。
? ? ? ? 在非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。
第四章、树和二叉树
? ? ? ? 赫夫曼树及其应用：
? ? ? ? ? ? ? ? 赫夫曼树又称最优树（没有度为1 的结点），是一类带权路径最短的树 带权路径长度：WPL= 带权 * 度
? ? ? ? ? ? ? ? 赫夫曼编码
第五章、图
????????
第六章、查找
第七章、排序
?
|