数据结构讨论的范畴.ppt

《数据结构讨论的范畴.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章绪论一、数据结构讨论的范畴二、基本概念三、算法和算法的度量一、数据结构讨论的范畴非数值计算程序设计问题数据的逻辑结构数据的存储结构二、基本概念1.数据与数据结构2.抽象数据类型1.数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位数据结构：带结构的数据元素的集合或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。是研究数据的逻辑结构和物理结构以及它们之间的相互关系

2、，并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算以后所得的新结构仍然是原来的结构类型数据结构：概括地说：数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构数据的存储结构——逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？关系的映象方法：顺序映象用一组地址连续的存储单元依次存储数据元素xy链式映象以附加信息(指针)表示后继关系需要用一个和x在一起的附加信息指示y的存储位置yx2.抽象数据

3、类型(AbstractDataType简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。三、算法和算法的衡量1.算法2.算法设计的原则3.算法效率的衡量方法和准则4.算法的存储空间需求算法是对解决某类问题的方法的一种描述。一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同。T(n)=O(f(n))渐近时间复杂度第二章线性表线性表的概念---基本操作算法实现---顺序存储---链式存储顺序映象方法是：逻辑关系相邻,物理位置相邻.用

4、一组地址连续的存储单元依次存放线性表中的数据元素a1a2…ai-1ai…an基地址constintMaxSize=50;structList{ElemTypelist[MaxSize];intsize;//当前线性表长度};线性表顺序存储结构一、有关空表的操作1.初始化操作2.清空操作3.判空操作*当前线性表长度*二、有关查找的操作2.查找具有给定值的元素1.遍历线性表操作3.更新表中具有给定值的元素从表头元素起依次访问每一个元素，并且每个元素只被访问一次a1a2…ai-1ai…an基地址L.list[0]最后一个L.list[L.si

5、ze-1]三、有关插入的操作3.插在i位置操作2.表头插入一个元素1.末尾添加一个元素后移a1a2…ai-1ai…ana1a2…ai-1…aiean表的长度增1i位置for(intj=L.size;j<=i;j--){L.list[j]=L.list[j-1];}最后的位置L.size四、有关删除的操作2.删除i位置元素操作1.删除表头元素操作前移ai-1插入、删除、建立等操作在单链表中的实现：有序对改变为和eaiai-1s=newLNode;s->data=e;//生成新结点s->next

6、=p->next;p->next=s;//插入eai-1aiai-1spai-1aiai+1ai-1q=p->next;p->next=q->next;e=q->data;deleteq;pq逆位序输入建立带头结点的单链表一、建立一个“空表”；二、输入数据元素an；三、输入数据元素an-1，建立结点并前插；四、依次类推，直至输入a1为止。L->next=p;p->next=L->next;最后一个结点的指针域的指针又指回第一个结点循环链表a1a2…an判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。ai-1

7、aies->right=p->right;p->right=s;s->right->left=s;s->left=p;psai-1ai插入双向链表ai-1删除aiai+1p->right=p->right->right;p->right->left=p;pai-1第三章稀疏矩阵和广义表压缩存储方法:一、三元组顺序表二、带行指针向量的链接存储三、十字链表稀疏矩阵的概念原矩阵转置后矩阵一、三元组顺序表用“三元组”表示实现矩阵转置需要把具有相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表，每个三元组结点的类型可定义为：二、带行指针向

8、量的链接存储rowcolvalnext121415-522-731363428三元组行指针向量22-73136342815-51214vector/////三、十字链表cvrv30050-1002