资源描述：
《二级公共基础知识讲义》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、二级公共基础知识讲义算法和数据结构16-18程序设计2-4软件工程6-8数据库设计4-6第一部分：算法与数据结构算法.Ø算法的概念Ø算法的复杂度.一、算法的概念算法就是指解题方案的准确而完整地描述1）算法的基本特征可行性确定性有穷性拥有足够的情报（输入、输出）2）算法的基本要素算法:数据项,运算,控制结构,数据传输一是数据对象的运算和操作二是算法的控制结构u运算种类（算术运算+-*/，关系运算><=，逻辑运算andornot，数据传输）u控制结构由三种组成（顺序结构，分支结构，循环结构）3）常用的算
2、法列举法归纳法递推法递归法减半递推技术一、算法的复杂度（时间复杂度，空间复杂度）时间复杂度（执行算法所需要的计算工作量，也就是算法执行过程中所需要的基本运算次数，与命令的多少无关）空间复杂度（执行一个算法所需要的内存空间，与硬盘的存储空间无关）时间复杂度和空间复杂度没有联系数据结构【引言】主要研究问题：1.数据集合中各元素之间所固有的逻辑关系，既数据的逻辑结构；2.在对数据进行处理时，各个元素在计算机中的存储关系，既数据的存储结构；1、逻辑结构2、存储结构3、数据的运算：检索、排序、插入、删除、修改
3、等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队列树形结构图形结构数据结构的三个方面(物理结构)3.对各种数据结构进行的运算。一、什么是数据结构：数据结构是研究大量数据在计算机中存放和组织方法的计算机科学二、数据的逻辑结构和存储结构1.数据结构是说数据集合中各元素之间的前后件关系。如一年四季的顺序关系：a){春、夏、秋、冬}春是夏的前件，夏是春的后件春冬秋夏b)在家庭成员间的关系中，父亲是儿子和女儿的前件，儿子和女儿都是父亲的后件：父亲儿子女儿1.一个结构应包含以下两个方面的信息1)表示
4、数据元素的信息（通常用D表示）2)表示各个元素之间的前后件关系（通常用R表示）所以一个结构可以表示成B=(D,R)2.逻辑结构是反映数据元素之间逻辑关系的抽象描述，而不考虑数据在计算机中存储方式。逻辑结构分为：线性结构和非线性结构3.数据的物理结构：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构），数据元素在计算机存储空间中的位置可能与逻辑关系不同，在数据的存储结构中，不仅要存放个元素的信息，还需要存放各元素之间的前后件关系的信息。常用的存储结构有顺序：链式：一、线
5、性结构及其存储结构线性结构有三种（线性表，栈，队列）(三．1)线性表及其顺序存储结构a)线性结构的特点是：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。在一个线性结构里插入或删除任何一个结点后应该还是线性结构。b)非空线性表的结构特点是：l有且只有一个根结点a1，它没有前件；l有且只有一个终端结点an，它没有后件l除了根结点和终端结点外，其他所有结点有且只有一个前件，有且只有一个后件。l线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。l一般线性表,可以在端点插入删除,也
6、可在中间任何位置插入删除a)线性表的顺序存储结构，是说将线性表中的数据顺序存放在存储器中。b)线性表中第i个元素ai在计算机存储空间中的存储地址的算法a1a2……ai所有元素的存储位置取决于第一个数据元素的存储位置LOC(ai)=LOC(a1)+（i-1）*CC表示一个元素所占的存储空间常见的顺序表的常见处理操作：插入删除查找注：在顺序表里做插入、删除运算是需要移动大量的元素(三．2)线性表的链式存储结构(线形链表)a)线性表的链式存储结构称为线性链表。在链表中，存储空间的位置关系与逻辑关系不一致。
7、各数据结点的存储序号是不连续的。每个结点有两个部分组成：一部分用于存放数据元素值，称为数据域，另一部分用于存放指针（用来存放下个元素的起始地址），叫指针域；数据之间的逻辑，关系是由指针域来确定的。数据1数据1数据2a)对于线性链表，沿各结点的指针扫描到链表中的所有结点，在这种链表中，每各结点只有一个指针域，只能找到后件，不能找到前件。这样的链表称为单向链表。b)为了弥补这个缺点，在某些应用中，每个结点设置两个指针，一个左指针（llink）,一个右指针（rlink）这样的链表称为双向链表。数据1数据2
8、线性链表常见处理操作：插入、删除、查找1.线性表的链式存储结构称为线性链表，现行链表的基本运算有查找，插入，删除等1.链式存储结构里进行插入、删除元素的时候不需要移动大量元素。ba插入前插入后bax删除后(三．3)栈及其基本运算1.栈是限定在一端进行插入和删除的线性表，特点是“先进后出”，能够进行插入、删除的那一端称为栈顶（top）,另一端称为栈底(bottom)。1234不可能输出顺序____a)1,3,2,4b)3,4,2,1;c)4,3,1,2d)2,3,4,1
