大二上软基软件技术基础_ds

1、第一章数据结构1.1 数据结构基础知识数据结构的基础知识线性结构（线性表、栈与队列、数组、串）非线性结构（树及二叉树、图）查找与排序数据结构Data Structure什么是数据结构？数据结构 讨论计算机系统中数据的组织形式及其相互关系 是相互之间存在一种或多种特定关系的数据元素的集合。 是对数据元素之间的逻辑关系、数据的存储方式以及对数据的操作的抽象描述。数据结构中的一些基本概念数据：客观事物采用计算机进行识别、存储和加工所进行的描述。（数值性数据、非数值性数据）单位？数据元素：是数据的基本单位，也是数据结构中讨论的基本单位。又称为节点、记录若干数据项组成 例：数据学号姓名英语数学物理1赵一

2、9085932钱二8892803孙三708077.数据元素数据项typedef struct student int id; char name20; float score3; elemtype;数据结构的三个层次某一数据对象的所有数据成员之间的关系。数据结构定义: 数据结构逻辑结构存储结构操作数据元素之间关系的描述1、二元组：B （ D， R ）D：元素集合R：元素间关系的集合关系：主要抽象为前驱与后继关系，表明结构中，一个元素的前一个元素是谁，它的后一个元素又是谁。（一）数据的逻辑结构2、图示法 图形要素：结点和有向线段结点：表示一个数据元素，一般以方形框代表 不管多么复杂的结点，都看作

3、是一个结点K i有向线段：表示元素之间的关系：箭尾指向的结点是前驱箭头指向的结点是后继K hK jKi的前驱Ki的后继逻辑结构有且仅有一个开始数据元素，有且仅有一个结束数据元素，其他数据元素最多只有一个直接前趋和直接后继。代表：线性表每个数据元素可能有多个直接前趋和直接后继。有且仅有一个称为“根”的元素无直接前趋，其他元素有且仅有一个直接前趋。树图每一个数据元素的直接前趋和直接后继个数没有限制。非线性结构线性结构（二）数据的存储结构存储结构（物理结构）顺序存储方法散列存储方法（地址转移法）链接存储方法索引存储方法主要用于线性数据结构，如线性表、数组数据元素分为数据项和指针项两部分，如链表稠密索

4、引（Dense Index)稀疏索引（Sparse Index）数据元素在存储器中的存放方式思考：为什么数据逻辑结构与物理结构不能完全统一？1、顺序存储方法连续顺序地存放数据元素，若数据的逻辑结构也是顺序（线性）的，则逻辑结构和物理结构就完全统一了。K1K2K3K40300030103020303030403050306030703080309K1K2K3K40300030103020303030403050306030703080309K1K2K3K4K5K6K1K2K3K4K5K6存储器的特点：由地址连续的单元构成单元间的线性关系不能反映非线性逻辑关系2、链接存储方法元素在内存中不一定连续

5、存放在元素中附加指针项，通过指针可以找到关系元素元素指针结点元素指针0300031003200330034003500370030203080390K1K2K3K4K5K6K1K2K3K4K5K6通过指针，可以方便地找到关系结点指向后继结点的指针指向前驱结点的指针3、索引存储方法为放在内存中的元素建立索引表0300030103020303030403050306030703080309K1K2K3K41234索引表元素可以离散存放通过查索引表找到需要的元素索引号联想：图书馆的查书卡4、散列存储方法结点中设一关键值，利用关键值和公式算出结点位置 （地址）例：以用户姓名为关键值DJS公式为字母的序

6、号相加04 + 10 + 19 = 33ZXM26 + 24 + 13 = 63联想：通过书的名字就能确定书的位置数据的逻辑结构与物理结构小结1、物理结构是元素在内存中的存储方式，与元素间固有的逻辑关系是相对独立的两个问题物理结构着眼于结点在内存中的定位2、简单的逻辑结构可能和物理结构一致例：线性逻辑关系与顺序存储方法3、利用物理结构在内存中找到一个结点，而为什么要找这个结点却由元素间的逻辑关系决定!一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。（三）数据的操作插入：遍历：删除：查找：排序：更新：在数据结构的各个元素中移动，逐一查看所有数据元素向数据结构中添加新元素

7、修改或替代数据结构中的数据元素在数据结构中去除指定的元素在数据结构中查找满足条件的元素把数据结构中的元素按要求重新排序例：一个树形关系结构用索引方式存储一个树形关系结构用链接方式存储？1234561234560300030103020303030403050306030703080309K1K2K3K4K5K6数据的逻辑结构与数据的存储结构举例：例：班级里的同学可能有各种各样的逻辑关系。比如班长、班委、组长、群众等。形成相应的逻辑结构。上课时，大家的座次形成存储结构座次（存储结构）可能与逻辑关系有关，也可能无关。为什么要这样抽象出两种关系？设想一个场景20考试时，大家的座次形成另一种存储结构数

8、据结构的命名 由于数据结构具有三个层次，故在对数据结构命名的时候可以将数据的逻辑结构、存储结构甚至操作结合起来给数据结构进行命名。线性表存储方式顺序表顺序存储方式链表链接存储方式操作栈插入和删除在同一端队列插入在一端 删除在另一端仅是一种线性结构常见的数据结构线性结构树结构图结构A1A2A3A4A4A3A2A1内存顺序表（数组）链表45hA3A216hA1内存01h16h45h56h56hA4数据类型数据类型（Data Type）：一组性质相同值的集合和定义在这个值的集合上的一组操作的总称。非结构的原子类型构造类型如 C 语言中的基本数据类型：int 、float 、 char 、*（指针型）

9、等等如在 C 语言中利用基本数据类型构造的结构类型算法基本概念定义：算法是为解决某一特定类型问题规定的运算规则的有穷集合。特性： 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本，可执行算法的性能标准： 正确性、可使用性、可读性、效率、健壮性 算法与程序相似：都是解决问题的方法和步骤，是指令的集合区别：有穷性描述方法联系：程序用某种程序设计语言来实现算法程序使用程序设计语言算法可以使用框图及其他语言类似：While(1) 的语句段，在程序中允许但在算法中不允许算法的写作规范int se

10、q_search( elemtype s ,keytype k, int n) int low, high, mid;sn.key = k;i = 0;while(s i .key != k) i+;if(i n) return i;else return -1;名称输入参数输出类型使用的变量说明初始化算法主体部分26时间复杂度度量运行时间 = 算法中每条语句执行时间之和。每条语句执行时间 = 该语句的执行次数（频度） * 语句执行一次所需时间。语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中

11、所有语句的频度之和。计算累加和程序程序步数计算工作表格算法中所有语句的频度之和是矩阵阶数n的函数 T(n) = 2n3 + 2n2 + 2n +1一般地，称 n 是问题的规模。则时间复杂度 T(n) 是问题规模 n 的函数。当n趋于无穷大时，把时间复杂度的数量级（阶）称为算法的渐进时间复杂度 T(n) = O(n3) -大O表示法时间复杂度的渐进表示法加法规则 针对并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m)各种函数的增长趋势 C log2n n nlog2n n2 n3 2n 3n n!乘法规则 针对嵌套程序段T (n, m) =

12、 T1 (n) * T2 (m) = O(f (n)*g (m)例：变量计数x = 0; y = 0;for ( int k = 0; k n; k + ) x +;for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1(n) = O(1)T2(n) = O(n)T3(n) = O(n2)T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)空间复杂度度量存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分（如数组元素、结构成分、对象的数据成员等）变量所占空间可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所