常德市住房和城市建设局网站,wordpress华为,东莞市建,开微信公众号流程目录 大纲 1.数据结构基础知识 1.1 什么是数据结构 1.2 数据 1.3 逻辑结构 1.4 存储结构 1.4.1 顺序存储 1.4.2 链式存储 1.4.3 索引存储结构 1.4.4 散列存储 1.5 操作 2.算法基础知识 2.1 什么是算法 2.2 算法的设计 2.3 算法的特性 2.4 评价算法的好坏 大纲 数据结构、算法(理… 目录 大纲 1.数据结构基础知识 1.1 什么是数据结构 1.2 数据 1.3 逻辑结构 1.4 存储结构 1.4.1 顺序存储 1.4.2 链式存储 1.4.3 索引存储结构 1.4.4 散列存储 1.5 操作 2.算法基础知识 2.1 什么是算法 2.2 算法的设计 2.3 算法的特性 2.4 评价算法的好坏 大纲 数据结构、算法(理解) 线性表顺序表(数组)、链表(单向链表、单向循环链表、双向链表、双向循环链表)、栈(顺序栈、链式栈)、队列(循环队列、链式队列) 树特性、二叉树(性质、创建、遍历) 排序方法、查询方法(原理、思路) 1.数据结构基础知识 1.1 什么是数据结构 数据结构就是数据的逻辑结构以及存储操作 (类似数据的运算) 数据结构就教会你一件事如何更有效的存储数据 1.2 数据 数据不再是单纯的数字而是类似于集合的概念。 数据元素是数据的基本单位由若干个数据项组成。 数据项数据的最小单位描述数据元素的有用的信息。 数据元素又叫节点 例如 计算机处理的对象(数据)已不再是单纯的数值 图书管理中的数据如下表所列: 数据图书 数据元素每一本书 数据项编号、书名、作者、出版社等 1.3 逻辑结构 数据元素并不是孤立存在的它们之间存在着某种关系(或联系、结构)。元素和元素之间的关系 线性关系 线性结构 一对一 线性表顺序表、链表、栈、队列 层次关系 树形结构 一对多 树二叉树 网状关系 图状结构 多对多 图 例题 田径比赛的时间安排问题 1.4 存储结构 数据的逻辑结构在计算机中的具体实现数据的运算 1.4.1 顺序存储 特点内存连续、随机存取、每个元素占用较少 实现数组 1.4.2 链式存储 通过指针存储 特点内存不连续通过指针实现 链表实现 结构体 #include stdio.hstruct node
{int data; //数据域存放节点中要保存的数据struct node *next; //指针域保存下一个节点的地址也就是说指向了下一个节点 (类型为自身结构体指针)
};int main()
{//定义三个节点struct node A {1, NULL}; //定义结构体变量的同时给每个成员赋值struct node B {2, NULL};struct node C {3, NULL};// struct node D; //先定义结构体变量再单独给其中成员赋值// D.data4;// D.nextNULL;//连接三个节点A.next B; //连接A和B节点通过让A中的指针域保存B的地址B.next C;printf(%d\n, A.data);printf(%d\n, A.next-data);printf(%d\n, A.next-next-data);
}1.4.3 索引存储结构 在存储数据的同时建立一个附加的索引表。 也就是索引存储结构 索引表 存数据的文件 可以提高查找速度特点检索速度快但是占用内存多删除数据文件要及时更改索引表。 1.4.4 散列存储 数据存储按照和关键码之间的关系进行存取。关系由自己决定比如关键码是key, 存储位置也就是关系是key1。获取关键数据通过元素的关键码方法的返回值来获取。 存的时候按关系存 取的时候按关系取 1.5 操作 增删改查 2.算法基础知识 2.1 什么是算法 算法就是解决问题的思想方法数据结构是算法的基础。 数据结构 算法 程序 2.2 算法的设计 算法的设计 取决于数据的逻辑结构 算法的实现依赖于数据的存储结构 2.3 算法的特性 有穷性 步骤是有限 确定性每一个步骤都有明确的含义无二义性 可行性在规定时间内可以完成 输入 输出 2.4 评价算法的好坏 正确性 易读性 健壮性容错处理 高效性执行效率通过重复执行语句的次数来判断也就是时间复杂度(时间处理函数)来判断。 时间复杂度 语句频度用时间规模函数表达 时间规模函数: T(n)O(f(n)) T(n) //时间规模的时间函数 O //时间数量级 n //问题规模例如a[100], n100 f(n) //算法可执行重复语句的次数 称O(f(n)) 为算法的渐进时间复杂度简称时间复杂度。 渐进时间复杂度用大写O来表示所以也被称为大O表示法。直白的讲时间复杂度就是把时间规模函数T(n)简化为一个数量级如nn^2n^3。 例1 求1234...n的和 算法1 int sum0;
for(int i1;in;i)
{sum i; //重复执行n次
}f(n) n T(n) O(n) 算法2 利用等差数列前n项和公式Snn*a1n(n-1)d/2 或 Snn(a1an)/2 (d是公差 int sum (1n)*n/2; //重复执行1次 f(n) 1 T(n) O(1) 例2 int i,j;
for(i0;in;i)
{for(j0;jn;j){printf(ok\n); //重复执行n*n次}
}T(n) O(n^2) 例3 int i,j;
for(i0;in;i)
{for(j0;ji;j){printf(ok\n); }
}1 2 ... n f(n) n*(1n)/2 n^2/2 n/2 //只保留最高项n^2/2, 除以最高项系数 得到n^2 T(n) O(n^2) 计算大O的方法 根据问题规模n写出表达式f(n)如果有常数项将其置为1 //当f(n)的表达式中只有常数项例如f(n) 8 O(1)只保留最高项其他项舍去。如果最高项系数不为1则除以最高项系数。 f(n) 3*n^4 2*n^3 6*n^7 10; O(n^7)
