数据结构课件数据结构复习.ppt

数据结构梁春燕华电信息管理教研室******@:数据、数据元素、数据结构、数据类型抽象数据结构类型ADT的表示与实现算法和算法分析:特性、评价方法(时间/空间复杂度)数据结构是什么?其研究的主要内容?类型?算法的评价?数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构(DataStructure):是相互之间存在一种或多种特定关系的数据元素的集合。数据的逻辑结构数据的存储结构数据的运算:检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队列树形结构图形结构数据结构的三个方面:复****串讲第二章线性表线性表的逻辑结构:一对一线性表的顺序存储结构(顺序表):存储方式、特点、基本操作线性表的链式存储结构:存储方式、特点、基本操作单链表(静态链表)循环链表双向链表线性表的应用举例一元多项式的表示及相加(单链表)约瑟夫问题(循环链表)顺序存储和链式存储的优缺点?顺序存储结构优点逻辑相邻,物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配,利用不充分表容量难以扩充链式存储结构优点动态结构,整个存储空间为多个链表共用,节省空间不需预先分配空间,易扩充插入、删除操作方便缺点指针占用额外存储空间不能随机存取,查找速度慢测试程序填空:(JD*p){p->prior->next=p->next;p->next->prior=p->prior;free(p);}bcaPp->prior->next=p->next;p->next->prior=p->prior;复****串讲第三章栈和队列栈的逻辑结构、顺序存储结构、链式存储结构及其基本操作顺序栈:栈空、栈满链式栈:栈空队列的逻辑结构、顺序存储结构、链式存储结构及其基本操作循环队列:队空、队满链式队列:队空栈和队列的应用数制转换、表达式计算、汉诺塔问题(栈)舞伴问题(队列)栈和队列的异同?相同点栈和队列都是特殊的线性表,是操作受限的线性表,称限定性DS不同点栈限定仅在表尾(栈顶)进行插入或删除操作的线性表特点:先进后出(FILO)或后进先出(LIFO)进栈、退栈操作队列限定只能在表的一端(队尾)进行插入,在表的另一端(队头)进行删除的线性表特点:先进先出(FIFO)进队、(CirQueue*Q){DataTypetemp;if(queueEmpty(Q))Error(“队空\n”);temp=Q->data[Q->front];Q->count--;Q->front=(Q->front+1)%QueueSize;returntemp;}J4J5J6012345rearfront复****串讲第四章串串及其运算数据元素约束为字符集的线性表基本操作:以串的整体作为操作对象,“子串”的操作串的长度、串复制、联接、串比较、求子串串的存储结构顺序存储:定长顺序存储、堆分配存储链式存储:块链存储串的模式匹配算法简单匹配KMP算法串的存储方式的比较?定长顺序存储顺序存储、串的长度固定串的插入、联结:串的截断串的插入、删除:移动元素串的查找、定位:方便堆分配存储顺序存储、串的长度可变串的插入、删除:移动元素串的联结、查找、定位:方便串的块链存储链式存储、串的长度可变占用空间大、操作复杂复****串讲第五章数组和广义表数组的定义和特点特殊的线性表,即线性表中数据元素本身也是一个线性表数组的顺序存储:行序、列序数组的压缩存储:对称矩阵、三角矩阵、对角矩阵、稀疏矩阵数组的链式存储:带行指针向量的单链表、十字链表广义表的概念和表示稀疏矩阵的存储方式?稀疏矩阵(m行n列,t个非零元素,t<<m*n)顺序存储方法:m*n压缩存储方法顺序存储结构三元组表:3(t+1)带辅助行向量的二元组表:2(t+1)+m+1伪地址表示法:2(t+1)链式存储结构带行指针向量的单链表表示:3t+m十字链表:5t+m+n复****串讲第六章树和二叉树二叉树二叉树的特点和性质二叉树的存储结构:顺序、链式(二叉、三叉、线索)二叉树的遍历:先序、中序、后序、层次二叉树的线索化树树的存储结构:双亲、孩子、孩子兄弟表示方法树与二叉树转换森林与二叉树转换树和森林的遍历(与对应二叉树的遍历的关系)Huffman树Huffman树的建立:Huffman算法Huffman树的应用:Huffman编码树和二叉树的遍历算法的应用