软基软件技术基础_ds

1、软件技术基础霍永青Phone：61831246Office：科B24221、课程内容数据结构：计算机软件基础，描述计算机内数据 的逻辑关系，是计算机操控对象的抽 象模型。操作系统：计算机核心软件的集合，是计算机系 统的逻辑抽象。数据库 ：计算机数据处理的延伸发展。帮助用 户有效地组织大量数据。软件工程：软件开发的一般步骤和方法。网络基础：网络基础、协议及编程接口。32、课程安排课堂讲授40学时，半期考试2学时，复习、作业讲评2学时，上机实验20学时。 数据结构-22学时 操作系统-18学时 数据库-自学 软件工程-自学 网络基础-自学4第一章数据结构1.1 数据结构基础知识数据结构的基础知识线

2、性结构（线性表、栈队列、数组、串）非线性结构（树及二叉树、图）查找与排序数据结构Data Structure5数据结构中的一些基本概念数据：客观事物采用计算机进行识别、存储和加工所进行的描述。（数值性数据、非数值性数据）单位？数据元素：是数据的基本单位，也是数据结构中讨论的基本单位。又称为结点、记录数据对象（Data Object）：性质相同的数据元素的集合，数据的子集。数据项组成 7例：学号姓名英语数学物理1赵一9085932钱二8892803孙三708077.数据数据元素（节点）数据项数据对象车型生产商颜色载重价格DF141二汽兰5吨13万88什么是数据结构？数据结构 讨论计算机系统中数据

3、的组织形式及其相互关系 是相互之间存在一种或多种特定关系的数据元素的集合。 是对数据元素之间的逻辑关系、数据的存储方式以及对数据的操作的抽象描述。数据结构的三个层次某一数据对象的所有数据成员之间的关系。数据结构定义: 数据结构逻辑结构存储结构操作9数据元素之间关系的描述1、二元组：B （ D， R ）D：元素集合R：元素间关系的集合关系：主要抽象为前驱与后继关系，表明结构中，一个元素的前一个元素是谁，它的后一个元素又是谁。（一）数据的逻辑结构102、图示法 图形要素：结点和有向线段结点：表示一个数据元素，一般以方形框代表 不管多么复杂的结点，都看作是一个结点K i有向线段：表示元素之间的关系：

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

5、Sparse Index）数据元素在存储器中的存放方式思考：为什么数据逻辑结构与物理结构不能完全统一？131、顺序存储方法连续顺序地存放数据元素，若数据的逻辑结构也是顺序（线性）的，则逻辑结构和物理结构就完全统一了。K1K2K3K40300030103020303030403050306030703080309K1K2K3K4140300030103020303030403050306030703080309K1K2K3K4K5K6K1K2K3K4K5K6存储器的特点：由地址连续的单元构成单元间的线性关系不能反映非线性逻辑关系152、链接存储方法元素在内存中不一定连续存放在元素中附加指针项，通

6、过指针可以找到关系元素元素指针结点元素指针160300031003200330030403500370030203080390K1K2K3K4K5K6K1K2K3K4K5K6通过指针，可以方便地找到关系结点指向后继结点的指针指向前驱结点的指针173、索引存储方法为放在内存中的元素建立索引表0300030103020303030403050306030703080309K1K2K3K41234索引表元素可以离散存放通过查索引表找到需要的元素索引号184、散列存储方法结点中设一关键值，利用关键值和公式算出结点位置 （地址）例：以用户姓名为关键值DJS公式为字母的序号相加04 + 10 + 19 =

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

8、在数据结构中查找满足条件的元素把数据结构中的元素按要求重新排序21数据结构的命名 由于数据结构具有三个层次，故在对数据结构命名的时候可以将数据的逻辑结构、存储结构甚至操作结合起来给数据结构进行命名。线性表存储方式顺序表顺序存储方式链表链接存储方式操作栈插入和删除在同一端队列插入在一端 删除在另一端仅是一种线性结构22常见的数据结构线性结构树结构图结构A1A2A3A4A4A3A2A1内存45hA3A216hA1内存01h16h45h顺序表（数组）链表56h56hA423数据类型数据类型（Data Type）：一组性质相同值的集合和定义在这个值的集合上的一组操作的总称。非结构的原子类型构造类型如

9、C 语言中的基本数据类型：int 、float 、 char 、*（指针型）等等如在 C 语言中利用基本数据类型构造的结构类型24 算法与程序相似：都是解决问题的方法和步骤区别：联系：程序用某种程序设计语言来实现算法程序使用程序设计语言算法可以使用框图及其他语言算法的实现必须借助于程序设计语言中提供的数据类型及其运算。数据结构的选择对数据处理的效率起着至关重要的作用。程序算法数据结构描述方法26算法基本概念定义：算法是为解决某一特定类型问题规定的运算规则的有穷集合。特性： 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步

10、后结束 有效性 每一条运算应足够基本，可执行算法的性能标准： 正确性、可使用性、可读性、效率、健壮性2527算法效率的 衡量方法和准则通常有两种衡量算法效率的方法: 事后统计法事前分析估算法缺点：1必须执行程序 2其它因素掩盖算法本质28和算法执行时间相关的因素：1算法选用的策略2问题的规模3编写程序的语言4编译程序产生的机器代码的质量5计算机执行指令的速度29 一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。30 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T (n) = O(f(n)称T

11、 (n) 为算法的(渐近)时间复杂度。31如何估算 算法的时间复杂度？时间复杂度度量运行时间 = 算法中每条语句执行时间之和。每条语句执行时间 = 该语句的执行次数（频度） * 语句执行一次所需时间。语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。28时间复杂度计算示例1. for (i=0; in; i+)2. for (j=0; jn; j+)3. bij=0;4. for (k=0; kn; k+)5. bij=bij+aik*akj;6. 我们以执行次数最多的语句（

12、第5句）进行计算： 语句频度为：F(n)=n3 时间复杂度：T(n)=O(F(n)=O(n3)2934 4）思考下列程序段的时间复杂度 1、x=x+1; 2、for (j=0; jn; j+) x=x+1; 3、for (j=0; jn; j+) for (k=0; kn; k+) x=x+1; 4、for (j=2; j=n; j+) for (k=2; kreal;45结构类型的定义typedef struct my_typeint x;int y;my_type;利用结构类型声明变量my_type my_struct ;46结构的使用my_type my_struct ; 结构变量K =

13、 my_struct . x;访问结构中的变量对结构变量取成员 使用 . 符号对使用指向结构的指针取成员 使用 - 符号my_type * my_pointer ; 结构指针变量my_pointer = &my_struct;K = my_pointer-x;47结构体指针的概念存放结构体首地址一个结构体变量的指针就是该变量所占据的内存段的起始地址。结构体指针可以作为函数参数，传递结构体的首地址结构体指针48部分运算符赋值变量1 = 变量2逻辑判断相等 ： = 或条件：| 与条件：&逻辑运算或运算：|与运算：&非运算：！j = j+1; j += 1; j+;等价加1：+减1：- -49C语言

14、语句赋值语句条件语句分支语句注意多条语句时大括号的使用多条语句时不需使用大括号switch (分支变量） case 分支值1：语句；break;if （条件） 语句；条件为真else 语句；条件为假50C语言语句while循环for循环do while循环while（条件 ） 语句；for（初始化语句；条件；步进语句） 语句；do 语句；while （条件）51for( j = 0; j 10; j+) . 等价j = 0;while( j 10)j + ;j 0;do j +; while(j 10)j = 0;while( jy?x:y); int max(int *x,int *y) return(*x*y?*x:*y); 函数调用：c=max(a,b); c=max(&