四大公共基础知识要点基本数据结构与算法1．算法：简单说是解决特定问题的方法。在计算机领域，可以理解为由基本运算和运算顺序共同构成的完整的解题步骤。算法评价：正确性、运行时间、存储空间、简单性。时间复杂度：指某算法中包含简单操作次数的多少，是算法运行时间的相对度量。空间复杂度：指某算法的运行过程中临时占用的存储空间的大小。2．数据结构：数据与数据之间的联系以及数据在存储器上的存储方式。逻辑结构：数据之间的联系，一般情况下代表数据结构。存储结构：数据的存储方式，比如顺序、链接、索引、散列。线性结构：表结构（顺序表、链接表），每个结点元素有且只有一个直接前驱元素（第一个元素除外），有且只有一个直接后继元素（最后一个元素除外），数据之间是1：1的关系。非线性结构：包括树型结构、图型结构。每个结点有且只有一个前驱结点（树根结点除外），但可以有任意多个后继结点，数据之间是1：N（N≥0）的关系，称树型结构；每个结点可以有任意多个前驱结点和任意多个后继结点，数据之间是M：N（M≥0，N≥0）的关系，称为图型结构。3．线性表：一个有限的元素系列a0,a1,…an，如果ai的前面是ai-1，ai的后面是ai+1，则构成线性表。线性表是一种线性结构。堆栈、队列属于线性表。线性表的顺序存储结构：在内存中开辟一块连续的存储空间，让第一个元素存储在第一个单元，第二个元素存储在第二个单元，以此类推。如数组是个线性表，采用顺序存储结构。线性表的插入算法：（1）检查线性表空间是否占满，若占满则进行“溢出”错误处理；（2）检查i值是否超出允许范围（1≤i≤n+1），若超出则进行“超出范围”错误处理；（3）将第i个元素及后面所有元素向后移动一个位置；（4）将新元素写到第i个位置；（5）使线性表的长度增1。线性表的删除算法：（1）检查i值是否超出允许范围（1≤i≤n），若超出则进行“超出范围”错误处理；（2）将第i个元素后面的所有元素向前移动一个位置；（3）使线性表的长度减1。4．栈：也叫堆栈，属于运算受限的线性表。只允许在表的一端进行插入（进栈）和删除（出栈）操作，这一端叫栈顶，另一端叫栈底。也称后进先出表（LIFO）。可看成一端开口的圆桶。栈的顺序存储结构：因为栈属于线性表，可采用线性表的顺序存储结构。进栈算法：（1）检查栈是否已满，若满，则进行“溢出”错误处理；（2）将栈顶指针上移1；（3）将新元素赋给栈顶单元。出栈算法：（1）检查栈是否为空，若空，则进行“下溢”错误处理；（2）将栈顶指针下移1。队列：也称队，属于运算受限的线性表。只允许在表的一端（队尾）进行插入（进队），而在表的另一端（队首）进行删除（出队）。也称先进先出表（FIFO）。可看成两端都开口的圆筒。在顺序存储结构中，队首指针指向队首元素，删除一个元素时，队首指针向后移动一个位置；队尾指针指向队尾元素，插入一个元素时，队尾指针也向后移动一个位置。循环队列：将队列的最后一个位置绕到第一位置，形成环状空间。一般情况下，队尾指针大于队首指针，但特殊的情况是，队尾到达队列的上限之后又从队列的低端开始，此时，队尾指针是小于队首指针的队列的顺序存储结构：跟栈一样，可采用线性表的顺序存储结构。队列的插入算法：（1）检查队是否已满，若满，则进行“溢出”错误处理；（2）队尾指针后移1；（3）将新元素赋给队尾单元；（4）判断原队列是否为空；为空则把队首指针置为1。队列的删除算法：（1）检查原队是否为空，若空，则进行“下溢”错误处理；（2）检查队首和队尾指针是否相等（只剩一个元素），是则令队首和队尾指针同时为0（置空队），否则队首指针增1。5．链接表：简称链表，是由n个（n≥0）结点所组成的有限元素系列，每个结点除了包含数据元素外，还包含指向其他结点的一到多个指针元素。单链表与多链表：一个链接表中，如果每个结点只包含一个指向其他结点的指针，该表为单链表，否则为多链表。线性单链表：一种线性表，数据元素之间是1：1的联系，每个结点只包含一个指向后继元素的指针。也简称单链表。单链表的插入算法：假设a结点（存放a数据元素），其后继元素为c（存放c数据元素），a结点中指向c结点的指针为q。现有b结点（存放b数据元素），指向b结点的指针为p。欲把b插入到a之间c，则：（1）将a结点中的指针值q赋给b结点的指针域，使b指向了c；（2）将指向b结点的指针值p赋给a结点的指针域，使a指向了b。单链表的删除算法：假设a结点（存放a数据元素）的后继元素为b（存放b数据元素），a指向b的指针为p。b结点的后继元素为c（存放c数据元素），b指向c的指针为q。欲将b结点删除，则将b指向c的指针q赋给a结点的指针域即可。6．树：即树型结构，属非线性数据结构；空树是不含