数据结构整理完整版.docxVIP

第二章 线性表顺序表和链表的优缺点顺序表定义：用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。即：在顺序表中逻辑结构上相邻的数据元素，其物理位置也是相邻的。?优点?逻辑相邻，物理相邻?可随机存取任一元素?存储空间使用紧凑?缺点?插入、删除操作需要移动大量的元素（平均约需移动一半结点，当n很大时，算法的效率较低）?预先分配空间需按最大空间分配，利用不充分?表容量难以扩充链式存储结构定义：由分别表示a1,a2,…,ai-1,ai,…,an的N 个结点依次相链构成的链表，称为线性表的链式存储表示优势：(1)能有效利用存储空间；动态存储分配的结构，不需预先为线性表分配足够大的空间，而是向系统“随用随取”，在删除元素时可同时释放空间。(2)用“指针”指示数据元素之间的后继关系，便于进行“插入”、“删除”等操作；插入或删除时只需要修改指针，而不需要元素移动。劣势：(1)不能随机存取数据元素；(2)丢失了一些顺序表的长处，如线性表的“表长”和数据元素在线性表中的“位序”，在单链表中都看不见了。如，不便于在表尾插入元素，需遍历整个表才能找到插入的位置。单链表中删除一个节点和插入一个节点的语句操作，p29插入元素操作算法基本思想：首先找到相应结点，然后修改相应指针。假定在a，b之间插入结点X，s指向X, p指向a，指针修改语句为：s-next=p-next; p-next =s;删除元素操作算法基本思想:首先找到第 i-1 个结点，然后修改相应指针。删除b结点，其中，P指向a，指针修改语句为： p-next=p-next-next；单链表的就地逆置 习题集2.22算法的基本思想：以单链表作存储结构进行就地逆置的正确做法应该是：将原链表的头结点和第一个元素结点断开（令其指针域为空），先构成一个新的空表，然后将原链表中各结点，从第一个结点起，依次插入这个新表的头部（即令每个插入的结点成为新的第一个元素结点）。算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。 void reverse (Linklist H){LNode *p;p=H-next; /*p指向第一个数据结点*/H-next=NULL; /*将原链表置为空表H*/ while (p){q=p;p=p-next;q-next=H-next; /*将当前结点插到头结点的后面*/H-next=q;}}第三章 栈和队列栈和队列的特性特点栈必须按“后进先出”（LIFO）的规则进行操作，仅限在表尾进行插入和删除的操作。队列（FIFO）必须按“先进先出”的规则进行操作，队尾插入，队头删除。循环队列为空和满的判定方法，p63队空条件：front == rear;队满条件：(rear + 1) % maxSize == front 第四章 串一、模式匹配的改进算法求Next数组Next[j]的定义求解next[j]示例式串abaabcacNext[j五章 数组与广义表一、对称矩阵和上（下）三角矩阵的压缩存储对称矩阵的压缩存储若一个n阶方阵A中的元素满足ai,j=aj,i (1≤i,j≤n),则称其为n阶对称矩阵。（1）只存储对称矩阵中上三角或下三角中的元素（2）将n2个元素压缩存储到n(n+1)/2个元素的空间中，以一个一维数组作为A的存储空间。下三角矩阵的压缩存储 B[n(n+1)/2+1] 上三角矩阵的压缩存储 B[n(n+1)/2+1] 二、理解广义表的取表头和表尾的操作广义表的表头(Head)和表尾(Tail)：当广义表LS=(a1,a2,…,ai,…,an)非空时，称第一个元素a1为广义表的表头，其余元素组成的表(a2, a3, …,an)称为广义表的表尾。表头可能是原子，也可能是广义表，但表尾一定是广义表。取表头 GetHead(LS) = a1。取表尾 GetTail(LS) = (a2,a3,…,an)。取表头表尾示例①B=(e) GetHead(B) = e; GetTail(B) = ( ).②A=(a, ((b, c), d, e))GetTail(A)=(((b, c), d, e))GetHead( GetTail(A))= ((b, c), d, e)GetHead( GetHead( GetTail(A))) = (b, c).③A=( ); B = ( ( ) )A空表，长度0，深度1，无表头和表尾；B长度1，深度2，表头( )，表尾( )。第六章 树和二叉树二叉树先序、中序和后序的关系p1541.二叉树遍历的概念 二叉树的遍历是指按照一定次序访问树中所有结点,并且每个结点仅被访问一次的过程。它是最基本的运算,是二叉树中