二级教程公共基础

《二级教程公共基础》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第1章数据结构与算法1.1算法1.1.1算法的基本概念算法:是指解题方案的准确而完整的描述。1．算法的基本特征：可行性、确定性、有穷性、拥有足够的信息。2．算法的基本要素：对数据对象的运算和操作：算术运算逻辑运算关系运算数据传输算法的控制结构：顺序结构、选择结构、循环结构3．算法的基本方法：列举法归纳法递推法递归法减半递推技术1.1.2算法复杂度1.算法的时间复杂度：用算法在执行过程中所需基本运算的执行次数来度量算法的工作量算法的工作量=f(n)其中n是问题的规模算法的平均性态(AverageBehavior)A(n)=最坏情况复杂性(Worst-Ca

2、seComplexity)W(n)=2.算法的空间复杂度：一般是指执行这个算法所需要的内存空间1.2数据结构的基本概念：数据结构主要研究数据的逻辑结构、数据的存储结构、对各种数据结构的运算。1.2.1什么是数据结构1．数据的逻辑结构：一个数据结构应包含以下两方面的信息：表示数据元素的信息表示各数据元素之间的前后件的关系线性结构、树形结构、图形结构、集合2．数据的存储结构：顺序结构、链接结构、索引结构1.2.2数据结构的图形表示：数据结点(简称结点)用方框表示，有向线表示前后关系。1.2.3线性结构与非线性结构线性结构：二个条件：有且只有一个根结点；每一

3、个结点最多有一个前件，也最多有一个后件。非线性结构：结点之间的关系较复杂，前件和后件的个数多于一个。1.3线性表及其顺序存储结构1.3.1线性表的基本概念(LinearList)一组数据元素，例矩阵，每个元素的类型一致。数据元素可以是简单项，也可以由若干项数据组成。非空线性表有如下一些结构特征：有且只有一个根结点a1，它无前件；有且只有一个终端结点an，它无后件；除根结点和终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。表中结点的个数称为表的长度。当n=0时，称为空表。1.1.2线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点

4、：1．表中所有元素所占的存储空间是连续的。2．线性表中各数据元素在存储空间中是按逻辑依次存放的。在线性表的顺序存储结构下，主要的运算有以下几种：线性表的插入线性表的删除线性表的查找线性表的排序线性表的分解线性表的合并线性表的复制线性表的逆转1.3.3顺序表的插入运算：寻找插入位置，后移，插入。1.3.4顺序表的删除运算：寻找删除位置，前移。1.4栈与队列1.4.1栈及其基本运算1.什么是栈？栈(stack)是限定在一端进行插入与删除的线性表2.栈的顺序存储及其运算栈顶(top指针指向栈顶)，栈底(bottom指针指向栈底元素)入栈：指针进1，元素插入指

5、针所指向的单元。退栈：栈顶的元素赋给一个指定的变量，栈顶指针退1。读栈顶元素：栈顶的元素赋给一个指定的变量，栈顶指针不变。1.2.2队列及其基本运算1.什么是队列：队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。尾指针(rear)指向队尾元素，头指针(front)指向排头元素的前一个位置。2.循环队列及其运算在循环队列中，尾指针(rear)指向队尾元素，头指针(front)指向排头元素的前一个位置。循环队列的初始状态为空，即rear=front=m入队：队尾指针进一，当队尾指针rear=m+1时，则置rear=1退队：队头指针退一

6、，当队头指针front=m+1时，则置front=1在循环队列中，当front=rear时，不能确定是队列满还是队列空。在实际使用循环队列时，为了能区分队列满还是队列空，，通常还需增加一个s,s值的定义如下：S=由此得出：队列空的条件为s=0队列满的条件为s=0且front=rear(1)入队运算：先要判断一个队列是否为满，若不满，则进行入队操作。(2)退队运算：先要判断一个队列是否为空，若不空，则进行退队操作1.5线性链表1.1.1线性链表的基本概念顺序存储结构的缺点：插入、删除需移动数据元素存储空间分配不灵活多个线性表同时共享存储空间不好同时分配1

7、．线性链表：线性表的链式存储结构。存储结点的概念：数据元素的值，数据元素的之间前后件关系HEADV(i)NEXT(i)2.带链的栈：入栈和退栈3.带链的队列：入列和出列1.5.2线性链表的基本运算：在线性链表中包含指定元素的结点之前插入一个新元素在线性链表中删除包含指定元素的结点将两个线性链表按要求全成一个线性链表将一个线性链表按要求进行分解逆转线性链表复制线性链表线性链表的排序线性链表的查找1.5.3循环链表的基本运算：循环链表与线性链表相比具有以下两个特点：增加了表头结点，最后一个结点的指针域空表和非空表的表现形式1.6树与二叉树1.6.1树的基本

8、概念在树结构中，每一个结点只有一个前件，称为父结点。可以有多个后件，称为该结点的子结点。度：结