一起学数据结构之绪论基础概念五天前甚至对markdown语法都不是很熟悉现在却觉得没有这个语法的创作页面没有灵魂哈哈。其实这个东西一年前就有人推荐给博主了当时只是看一下觉得麻烦没怎么走几步回过头来才发现因为内心的不自信与它错过了一年。所以这个也是今天除了知识以外想和各位道友分享的一点点小心得——永远不要因为不自信觉得一件东西看起来难就放弃它。不要有任何心理负担就开始做回过头来时你一定会发现自己已经走出去很远也得到了很多意向不到的东西加油给正在学习的你一、内容要点一什么是数据结构1.用计算机解决问题需要几个步骤从实际问题抽象出数学模型设计解决此数学问题的算法编译、调试程序直至得到最终答案。2.问题的类型例1:图书管理系统、新生信息登记系统、酒店入住登记系统等此类文章管理的数学模型中计算机处理的对象间一般存在着一对一的线性关系所以叫线性数据结构例2:计算机与人机对弈问题、游戏中触发模型和步骤等此类游戏博弈的数学模型中计算机的处理对象间一般存在着一对多的数据关系它叫树形数据结构。因为对应关系可看作一个倒置的树此类关系结构是非线形的。例3:人际关系脉络关系、城市公交问题等此类多交叉路口交通灯的数学模型中计算机处理的对象间一般存在着多对多的数据关系它叫图状数据结构。通过图示表示出来是类似于“网”状所以又叫网状数据结构此类关系结构是非线性的。3.数据结构的定义数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系的操作等的学科。二基本概念和术语1.数据数据是对客观事物的符号总称了解符号学是计算机中所有能输入到计算机中并被计算机程序处理的符号关系的总称。数据元素数据元素是数据的基本单位在计算机中通常考虑做一个整体进行处理。数据项包含于数据元素。数据项数据项是数据最小的不可分割单位数据对象性质相同的数据元素的集合是数据的一个子集。数据结构相互之间存在一种或多种特定关系的数据元素的集合。数据结构包含三方面数据的逻辑结构、数据的存储结构和数据的运算。2.数据的逻辑结构定义数据的逻辑结构即数据元素之间的逻辑关系独立于计算机。线性结构一对一唯一直接前驱且唯一直接后继或不存在树形结构一对多唯一直接前驱或不存在且不唯一直接后继图形结构网状结构多对多不唯一直接前驱且不唯一直接后继辅助理解已理解的跳过我们可以从生活中的一些物与物之间的逻辑关系更好地理解上面的数据逻辑结构。线性结构比如火车车厢的关系、或者一群小孩子拉着手围成圈做游戏每一个个体都只有两只手去拉别人在离散数学图论中可以将它们看作每个节点最多有且只能有一个入度和一个出度树形结构比如我们中学历史课本上的附庸关系、工作中的严格上下级关系等每个人只有一个直系长官每个长官下面可以有多个下属每个节点能有一个入度和多个出度网状结构比如开party所有人随机和别人谈话节点的入初度不严格规定每个节点可以有多个入度和多个出度。3.数据的存储结构顺序存储方法该方法就是将逻辑上相邻的点存储在物理上也表示相邻节点间的相邻关系由存储上的相邻关系体现。一般用数组实现。链接存储方法该方法不要求逻辑上相邻的点存储在物理上也相邻节点间的相邻关系由附加的指针字段表示的得到的存储表示成为链式存储结构。一般借用指针实现。索引存储方法该方法通常是在存储节点信息的基础上还建立附加啊的索引表。索引表中的每一项称作索引项索引项的一般关键形式是关键字地址。关键字唯一标识节点地址做指向节点的指针。散列存储方法该方法的基本思想是根据关键字直接计算出节点的存储地址。4.数据的运算数据的运算是在数据的逻辑结构定义的操作算法如检索、插入、删除、更新和排序等。5.数据的类型原子类型其值不可再分的数据类型类比数据项记忆结构类型其值可再分的数据类型类比数据元素记忆抽象数据类型抽象数据组织和与之相关的操作。6.数据的操作插入在数据结构的指定位置上增添新的数据元素删除删除数据结构中某位置的数据元素更新改变某位置上数据元素的值在概念上等价于删除和原位插入操作查找在数据结构中查找某个满足特定要求的数据元素的位置或值排序在线性结构中重新安排数据元素之间的逻辑顺序关系使之按值由小到大或相反次序排列。更希望能在浏览的过程中读者自己也能回忆不停思考一个问题“我能用几种算法完成以上操作还有没有更优解“博主在写代码的时候只要ddl允许会一直不停地去完善自己的算法和代码怎样会更有序整洁些、怎样命名和注释别人看我的代码时会有一种赏心悦目的感觉、怎样优化下去耗时耗空间最小、怎样添加一些新奇有趣的小功能…心无旁骛地沉在里面不要去纠结一些浅薄浮躁的声音。三算法和算法分析1.算法算法算法是对某一问题求解步骤的描述它是有限序列每一条指令具有操作层面上的明确性。特点1有穷性2确定型3可行性4输入性0或多个输入5输出性0或多个输出。算法设计的要求1正确性2可读性3健壮性4效率与低存储量要求2.算法效率的度量时间复杂度一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记做 t(n)它是该算法求解问题规模n的函数。当问题无限大时t(n)的数量级称为渐近时间复杂度简称为时间复杂度记作 t(n)o(f(n)).空间复杂度算法的空间复杂度s(n)定义为该算法耗费存储空间它是问题规模为n的函数。渐进空间复杂度也常常称为空间复杂度记作s(n)o(f(n)).二、重难点重点数据的逻辑结构、数据的存储结构、数据的运算三方面的概念及关系难点分析算法的时间复杂度三、典例例1:设有数据结构line (D,R),其中D{01,02,03,04,05,06,07,08,09,10},R{r},r{05,01,01,03,03,08,08,02,02,07,07,04,04,06,06,09,09,10}解答线性原因定义一一对应关系选择此题的原因熟悉一下数据结构的表示方法学会用图形解决问题。其余此类体型属于赘述不予添加有兴趣的道友自己看教材找题目。例2:设n为整数指出下列各算法的时间复杂度。1:void prime(int n){ int i 2; while((n%i)!0 i*0.1sqrt(n)) i; if(i*1.0sqrt(n)) printf(%d是一个素数\n,n); else printf(%d不是一个素数\n,n); }2:void sum1(int n){ int p1,sum0,i; for(i1;in;i) { p*1; sump; } return sum; }3:void sum2(ihtn){ int i ,j,sum0; for(i1;in;i) { p1; for(j1;jn;j) P*j; sump; } return sum; }分析1算法的时间复杂度由嵌套最深层的语句执行次数决定。prime算法的嵌套最深语句是“i”它的执行次数由条件(n%i)!0 i0.1sqrt(n)决定所以看出执行次数小于sqrt(n),所以prime算法的时间复杂度是o(n1/2).2同上嵌套最深语句是“p1;sump;,执行n次所以算法的时间复杂度是o(n).3同理嵌套最深语句是”p*j,外层每循环一次内层语句执行n次外层一共循环n次所以sum2的算法时间复杂度为o(n2).决定时间复杂度的主要是循环要分析时间复杂度应从循环入手。 步入正轨以上明天见
