2009-7-30 软件基础教案（第一章 绪论）
计算机软件基础
The Foundations of
Computer Software
制 作：西安理工大学自动化学院讲 课：王 栋办公室,5-416
电 话,13186197626
E-mail,wangdong1210@xaut.edu.cn
2009-7-30 软件基础教案（第一章 绪论）
学时数,56小时授课,34小时实验,22小时教材,数据结构 —C语言描述高等教育出版社主编,耿国华
2009-7-30 软件基础教案（第一章 绪论）
第 1章 绪论
1.2 数据结构基本概念
1.4 算法设计目标和算法评价
1.3 C语言的数据类型
1.1 数据结构课程简介
2009-7-30 软件基础教案（第一章 绪论）
1.1 数据结构课程简介计算机处理中常见的问题学 号 姓 名 性别 籍 贯 出生年月
1 9 8 1 3 1 刘激扬 男 北 京 1 9 7 9,1 2
2 9 8 1 6 4 衣春生 男 青 岛 1 9 7 9,0 7
3 9 8 1 6 5 卢声凯 男 天 津 1 9 8 1,0 2
4 9 8 1 8 2 袁秋慧 女 广 州 1 9 8 0,1 0
5 9 8 2 0 3 林德康 男 上 海 1 9 8 0,0 5
6 9 8 2 2 4 洪 伟 男 太 原 1 9 8 1,0 1
7 9 8 2 36 熊南燕 女 苏 州 1 9 8 0,0 3
8 9 8 2 9 7 宫 力 男 北 京 1 9 8 1,0 1
9 9 8 3 1 0 蔡晓莉 女 昆 明 1 9 8 1,0 2
1 0 9 8 3 1 8 陈 健 男 杭 州 1 9 7 9,1 2
信息表的管理 文件系统的管理 交通规划管理
2009-7-30 软件基础教案（第一章 绪论）
表学 号 姓 名 性别 籍 贯 出生年月
1 9 8 1 3 1 刘激扬 男 北 京 1 9 7 9,1 2
2 9 8 1 6 4 衣春生 男 青 岛 1 9 7 9,0 7
3 9 8 1 6 5 卢声凯 男 天 津 1 9 8 1,0 2
4 9 8 1 8 2 袁秋慧 女 广 州 1 9 8 0,1 0
5 9 8 2 0 3 林德康 男 上 海 1 9 8 0,0 5
6 9 8 2 2 4 洪 伟 男 太 原 1 9 8 1,0 1
7 9 8 2 36 熊南燕 女 苏 州 1 9 8 0,0 3
8 9 8 2 9 7 宫 力 男 北 京 1 9 8 1,0 1
9 9 8 3 1 0 蔡晓莉 女 昆 明 1 9 8 1,0 2
1 0 9 8 3 1 8 陈 健 男 杭 州 1 9 7 9,1 2
学生信息登记表
2009-7-30 软件基础教案（第一章 绪论）
UNIX文件系统的系统结构图
/ (root)
bin lib user etc
math ds sw yin tao xie
Stack.cppQueue.cpp Tree.cpp
树
2009-7-30 软件基础教案（第一章 绪论）
交通图图乌鲁木齐兰州 西安呼和浩特北京郑州成都
1892
1145
668
676
695
511842
2009-7-30 软件基础教案（第一章 绪论）
由以上例子可见非数值 计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的 。
数据结构研究的是计算机所处理的数据元素间的结构关系及其操作实现的算法数据结构
2009-7-30 软件基础教案（第一章 绪论）
计算机是如何 组织数据？
如何 处理数据？
从而更好地利用数据？
初期,计算机主要工作是对各种各样数据进行 计算 。
目前,计算机是以对数据进行 非数值性处理 为主。
例：计算机进行电话查号工作需大量的检索（查询）工作。
如何组织数据直接关系到计算机的工作效率。
2009-7-30 软件基础教案（第一章 绪论）
1.研究数据结构的重要性数据结构直接影响着程序的 结构 和 算法,从而影响程序的运行 效率 。
数据结构研究计算机所处理的数据元素间的关系 及其 操作 实现的算法。
数据结构是培养学生 软件设计 能力的重点专业课之一 。
2.数据结构的课程安排
2009-7-30 软件基础教案（第一章 绪论）
第 1章 绪论 2学时第 2章 线性表 6学时第 3章 堆栈和队列 6学时第 4章 数组 2学时第 5章 树和二叉树 8学时第 6章 图 2学时第 7章 排序 4学时第 8章 查找 4学时
2009-7-30 软件基础教案（第一章 绪论）
1.2 数据结构基本概念
1.数据 (Data)：
2.数据元素：
3.数据项 (DataFilde)：
4.数据对象 (Data Object)：
5.数据结构 (Data Structure)：
有关术语
6.数据类型：
7.操作,
2009-7-30 软件基础教案（第一章 绪论）
1.数据,数据是信息的载体，是描述客观事物的数字、字符、以及所有能输入到计算机中，被能为计算机所接受的 符号集 。
数据 ={x|x是计算机操作的对象 }
数值性数据
非数值性数据例如,整数、实数 数据计算字符串 文本编辑图形、图象、声音 多媒体
2.数据元素：
是数据的基本单位，有时一个数据元素由若干个 数据项 组成（ 具有独立含义的最小标识单位 ）。
2009-7-30 软件基础教案（第一章 绪论）
3.数据项（域）,--数据不可分割的最小单位。
数据元素是有若干个数据域（项）组成。
数据处理的最小单位。
性质相同的数据元素的集合。
4.数据对象：
关系：见下图：
一个班学生集合为数据对象每一个数据元素均有六个数据域（项）
数据元素 1
数据元素 2
数据元素 33
………...
例如：学生管理登记卡特点：数据对象学号 姓名 性别 籍贯 民族 专业
98001 王立 男 河北 汉 计算机
98002 李立 男 山西 汉 自动化
98003 张颖 女 陕西 回 电信
… …,… … … …
980033 杨越 男 陕西 汉 通信数据元素 3
数据项
2009-7-30 软件基础教案（第一章 绪论）
5.数据结构：
计算机处理的数据元素的组织形式及其相互间的关系。
由数据元素的有限集合及所有数据元素之间的关系组成。记为：
Data_Structure = {D,R}
其中,D是数据元素的有限集,R是所有数据元素之间的关系的有限集合。
2009-7-30 软件基础教案（第一章 绪论）
例如：
下述数据结构来描述 2行 3列的矩阵：
它是一个含 6个数据元素 D={a1,a2,a3,a4,a5,a6} 的集合，且集合上存在 "行关系 "和 "列关系 "两个次序关系，其中行关系为
{<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}，列关系为
<a1,a4>,<a2,a5>,<a3,a6>}
654
321
aaa
aaa
2009-7-30 软件基础教案（第一章 绪论）
再例如：
Data_Structure = {D,R}
2009-7-30 软件基础教案（第一章 绪论）
逻辑结构线性结构,
非线性结构顺序存储链式存储所有元素呈线状关系的数据结构。
存储结构用一组地址连续的存储单元依次存储各个元素。
用一组不连续的存储单元存放数据元素。
逻辑结构 （逻辑数据结构）
存储结构 （物理数据结构）
从不同的抽象层次看：
2009-7-30 软件基础教案（第一章 绪论）
6.数据类型,
具有 相同性质 的计算机数据集合及在这个集合上的 一组操作 。
7.操作,数据结构上需要或能够进行的处理。
2009-7-30 软件基础教案（第一章 绪论）
数据结构逻辑结构存储结构操作实现算法线性数据结构非线性数据结构线性表栈队列树图顺序存储结构链式存储结构索引存储结构散列存储结构
2009-7-30 软件基础教案（第一章 绪论）
1.3 C语言的数据类型
1、基本数据类型
int short; long; unsigned
float float; double; long double
在 C语言中
数据类型：基本类型和构造类型
基本类型：整型、浮点型、字符型
构造类型：数组、结构、联合、指针,枚举型、
自定义
2.指针类型,
计算机的内存的数据存取：
内存区,地址 内存单元例,旅馆,房间号 房间
计算机访问内存的方式：
直接方式：按变量的地址存取变量。
间接方式：将变量的地址放在另一个变量中。
例,A抽屉的钥匙放在 B抽屉中。
对存放变量的地址进行操作；
函数间传递值
2009-7-30 软件基础教案（第一章 绪论）
指针：地址例,2000
i
表示,2000是变量 i的指针。
指针变量：
变量的指针：
指向变量的指针变量：
例,int *p_1;
char *p_2;,*”表示指针型变量基本型 *指针变量名定义：
2009-7-30 软件基础教案（第一章 绪论）
,&”:取地址运算。例,int *p_1;
int a;
p_1=&a;
“*”:指针运算符。例 （ *p_1） ++ 相当于 a++
引用：
2009-7-30 软件基础教案（第一章 绪论）
3,数组类型数组名就是数组的起始地址数组名作为函数参数时，为地址传递
int a[100];
a &a[0],a+1 &a[1]……
*a a[0],*(a+1) a[1]……
2009-7-30 软件基础教案（第一章 绪论）
4、字符串
字符串定义成字符数组
‘ \0’ 为字符串结束标志
char a[40]=,I am a student”
strlen(a) 为 14
不包括 ‘ \0’
2009-7-30 软件基础教案（第一章 绪论）
5,结构体类型结构体 由若干个 结构体成员组成。
定义结构体类型变量：
1.定义结构体 类型 ；
2.定义结构体类型 变量 。
struct student
{
char name[10];
int age;
float score;
};
struct student student1;
struct student stu2[100];
struct student *p;
2009-7-30 软件基础教案（第一章 绪论）
6,自定义类型
typedef char elemtype;
typedef struct student
{
char name[10];
int age;
float score;
} stu;
elemtype a;
stu student1;
2009-7-30 软件基础教案（第一章 绪论）
1.4 算法设计目标和算法效率度量
1.算法定义,一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列
2.算法特性：
输入性 有 0个或多个输入输出性 有一个或多个输出 (处理结果 )
确定性 每步定义都是确切、无歧义的有穷性 算法应在执行有穷步后结束；整个指令序列在有限的时间内完成。
可行性（有效性） 算法中的每一个步骤都应当能被有效的执行，并得到确定的结果。 例如：被零除的计算动作是不能被有效执行的。
算法的描述,c++,c,PASCAL,类 c等语言
2009-7-30 软件基础教案（第一章 绪论）
3,算法描述方法：
1）自然语言：
2）伪代码：
用自然语言描述，不准确，易产生多义。
英文或英文缩写。
3）流程图,（ 1）传统流程图
（ 2） N--S流程图
4）类 pascal语言,由 pascal语言指令（简化）描述。
5） C语言,用简化的 C语言指令描述。
2009-7-30 软件基础教案（第一章 绪论）
4,算法设计目标
（ 1）正确性,满足要求
（ 2）可读性,易于理解
（ 3）健壮性,可处理非法数据
（ 4）高效性,执行时间短
（ 5）低存储量,省空间
2009-7-30 软件基础教案（第一章 绪论）
5,评价算法的一般原则：
1） 正确性 。 这是首要条件，在有限的时间内得出结果。
2） 运行时间短,指占用 CPU时间。
3） 占用存储空间少 。
4） 最优性,在给定问题的所有算法中,执行的运算次数最少
5） 可读性,要求算法易于理解,便于分析
6） 可修改可扩展性,如果解决问题 P 的一个算法是 A,为了解答一个与 P类似的问题,希望对 A稍做改动就可正确运行,如算法 A满足这一点,则说 A的可修改性好 。
2009-7-30 软件基础教案（第一章 绪论）
6.算法效率的度量首先算法必须是正确的。此外还需考虑：
1,算法易于理解,易于编程（在计算机上实现），
易于调试。
2,要求算法高效,节省时间与空间。
时间和空间相互之间有一种制约关系，何者为重需视具体情况而定。
重点考虑因素,时间
2009-7-30 软件基础教案（第一章 绪论）
Main()
{
int a=1;
int b=0;
for(int i=0;i<10;i++)
{
b=b+a;
}
}
Main()
{
int b=0;
for(int i=0;i<10;i++)
{
int a=1;
b=b+a;
}
}
例 1:
2009-7-30 软件基础教案（第一章 绪论）
一个算法所耗费的 时间,应该是该算法中每条 语句的执行时间之和,而每条语句的执行时间又是该语句的 执行次数
（频度）与该语句执行 一次所需时间的乘积 。
我们假定，每条语句一次执行的时间都是 相同 的，为单位时间。这样我们对时间的分析就可以独立于软硬件系统。
一般，时间复杂度是问题规模的函数 － T( n )。
当问题的规模 n 趋于无穷大时,把时间复杂度 T( n )的数量级
（ 阶 ） 称为算法的渐进时间复杂度 （ 有时简称为 时间复杂度
） 。
2009-7-30 软件基础教案（第一章 绪论）
严格的数学定义为：若 T( n ) 和 f( n ) 是定义在正整数集合上的两个函数，当存在两个正的乘数 C和 n0时，使得对所有的
0nn?
)()( nfcnT
))(()( nfOnT?成立，则都有这时称 T( n )的时间复杂度为 f( n )数量级 。
1、假定每条语句的执行时间为单位时间。算法的时间复杂度是该算法中所有语句的执行频度之和。
2009-7-30 软件基础教案（第一章 绪论）
x=x+1;执行 n次 O(n）
x=x+1;只执行一次 O(1）? x=x+1;
For(i=1;i<=n;i++)
x=x+1;
For(i=1;i<=n;i++)
For(j=1;j<=n;j++)
x=x+1;
x=x+1;执行 n2次 O(n2）
例 2,计算时间复杂度
2009-7-30 软件基础教案（第一章 绪论）
＃ define n 自然数
matri(float A[n][n],float B[n][n],float C[n][n])
{
int i,j,k;
for(i=0;i<n;i++) //n+1
for(j=0;j<n;j++) //n(n+1)
{
C[i][j]=0; //n*n
for( k=0;k<n;k++) //n*n*(n+1)
C[i][j]=A[i][k]*B[k][j] //n*n*n
}
} 1232)( 23 nnnnT T(n)=O(n3)
例 3：求两个方阵的乘积 C＝ A*B
2009-7-30 软件基础教案（第一章 绪论）
2。一般情况下，对步进循环语句只考虑循环体语句的执行次数
，而 忽略 该语句中 步长加一、终值判别、循环转移 等成份。因此，当有若干个循环语句时，算法的时间复杂度是 由嵌套层数最多的循环语句中最内层语句的频度 所决定的。
例,x=0;y=0;
for (k=1;k<=n;k++)
x++;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) //n*n
y++; T(n)=O(n2)
2009-7-30 软件基础教案（第一章 绪论）
3,选择执行的成分,如 if 语句的执行时间，决定于 then 子句、
else 子句耗时较多的部分例,temp = i;
i = j;
j = temp;
4、如果算法的 执行时间是一个与问题规模 n无关的常数,则算法的时间复杂度为常数阶，记作 T(n)=O(1)。
T(n)=O(1)
2009-7-30 软件基础教案（第一章 绪论）
例：
i=n-1;
while ((i>=0)&&A[i]!=k))
i--;
return i;
5、很多算法的时间复杂度不仅与问题的规模有关，而且还与它所处理的数据集的状态有关。通常是根据数据集中可能出现的最坏情况估计出算法的 最坏时间复杂度 。
T(n)=O(n)
2009-7-30 软件基础教案（第一章 绪论）
常数阶对数阶线性阶线性对数阶平方阶立方阶
K次方阶指数阶
)1(O
常见的时间复杂度，按数量级递增排序：
)( lo g 2 nO
)(nO
)lo g( 2 nnO
)( 2nO
)( 3nO
)( knO
)2( nO
2009-7-30 软件基础教案（第一章 绪论）
概念,数据，数据元素，数据项，数据结构，
数据类型，操作数据结构研究内容算法目标和算法评价 （ 时间复杂度 ）
作业,P32 1-2,1-9,2,3,4,6
总结：
计算机软件基础
The Foundations of
Computer Software
制 作：西安理工大学自动化学院讲 课：王 栋办公室,5-416
电 话,13186197626
E-mail,wangdong1210@xaut.edu.cn
2009-7-30 软件基础教案（第一章 绪论）
学时数,56小时授课,34小时实验,22小时教材,数据结构 —C语言描述高等教育出版社主编,耿国华
2009-7-30 软件基础教案（第一章 绪论）
第 1章 绪论
1.2 数据结构基本概念
1.4 算法设计目标和算法评价
1.3 C语言的数据类型
1.1 数据结构课程简介
2009-7-30 软件基础教案（第一章 绪论）
1.1 数据结构课程简介计算机处理中常见的问题学 号 姓 名 性别 籍 贯 出生年月
1 9 8 1 3 1 刘激扬 男 北 京 1 9 7 9,1 2
2 9 8 1 6 4 衣春生 男 青 岛 1 9 7 9,0 7
3 9 8 1 6 5 卢声凯 男 天 津 1 9 8 1,0 2
4 9 8 1 8 2 袁秋慧 女 广 州 1 9 8 0,1 0
5 9 8 2 0 3 林德康 男 上 海 1 9 8 0,0 5
6 9 8 2 2 4 洪 伟 男 太 原 1 9 8 1,0 1
7 9 8 2 36 熊南燕 女 苏 州 1 9 8 0,0 3
8 9 8 2 9 7 宫 力 男 北 京 1 9 8 1,0 1
9 9 8 3 1 0 蔡晓莉 女 昆 明 1 9 8 1,0 2
1 0 9 8 3 1 8 陈 健 男 杭 州 1 9 7 9,1 2
信息表的管理 文件系统的管理 交通规划管理
2009-7-30 软件基础教案（第一章 绪论）
表学 号 姓 名 性别 籍 贯 出生年月
1 9 8 1 3 1 刘激扬 男 北 京 1 9 7 9,1 2
2 9 8 1 6 4 衣春生 男 青 岛 1 9 7 9,0 7
3 9 8 1 6 5 卢声凯 男 天 津 1 9 8 1,0 2
4 9 8 1 8 2 袁秋慧 女 广 州 1 9 8 0,1 0
5 9 8 2 0 3 林德康 男 上 海 1 9 8 0,0 5
6 9 8 2 2 4 洪 伟 男 太 原 1 9 8 1,0 1
7 9 8 2 36 熊南燕 女 苏 州 1 9 8 0,0 3
8 9 8 2 9 7 宫 力 男 北 京 1 9 8 1,0 1
9 9 8 3 1 0 蔡晓莉 女 昆 明 1 9 8 1,0 2
1 0 9 8 3 1 8 陈 健 男 杭 州 1 9 7 9,1 2
学生信息登记表
2009-7-30 软件基础教案（第一章 绪论）
UNIX文件系统的系统结构图
/ (root)
bin lib user etc
math ds sw yin tao xie
Stack.cppQueue.cpp Tree.cpp
树
2009-7-30 软件基础教案（第一章 绪论）
交通图图乌鲁木齐兰州 西安呼和浩特北京郑州成都
1892
1145
668
676
695
511842
2009-7-30 软件基础教案（第一章 绪论）
由以上例子可见非数值 计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的 。
数据结构研究的是计算机所处理的数据元素间的结构关系及其操作实现的算法数据结构
2009-7-30 软件基础教案（第一章 绪论）
计算机是如何 组织数据？
如何 处理数据？
从而更好地利用数据？
初期,计算机主要工作是对各种各样数据进行 计算 。
目前,计算机是以对数据进行 非数值性处理 为主。
例：计算机进行电话查号工作需大量的检索（查询）工作。
如何组织数据直接关系到计算机的工作效率。
2009-7-30 软件基础教案（第一章 绪论）
1.研究数据结构的重要性数据结构直接影响着程序的 结构 和 算法,从而影响程序的运行 效率 。
数据结构研究计算机所处理的数据元素间的关系 及其 操作 实现的算法。
数据结构是培养学生 软件设计 能力的重点专业课之一 。
2.数据结构的课程安排
2009-7-30 软件基础教案（第一章 绪论）
第 1章 绪论 2学时第 2章 线性表 6学时第 3章 堆栈和队列 6学时第 4章 数组 2学时第 5章 树和二叉树 8学时第 6章 图 2学时第 7章 排序 4学时第 8章 查找 4学时
2009-7-30 软件基础教案（第一章 绪论）
1.2 数据结构基本概念
1.数据 (Data)：
2.数据元素：
3.数据项 (DataFilde)：
4.数据对象 (Data Object)：
5.数据结构 (Data Structure)：
有关术语
6.数据类型：
7.操作,
2009-7-30 软件基础教案（第一章 绪论）
1.数据,数据是信息的载体，是描述客观事物的数字、字符、以及所有能输入到计算机中，被能为计算机所接受的 符号集 。
数据 ={x|x是计算机操作的对象 }
数值性数据
非数值性数据例如,整数、实数 数据计算字符串 文本编辑图形、图象、声音 多媒体
2.数据元素：
是数据的基本单位，有时一个数据元素由若干个 数据项 组成（ 具有独立含义的最小标识单位 ）。
2009-7-30 软件基础教案（第一章 绪论）
3.数据项（域）,--数据不可分割的最小单位。
数据元素是有若干个数据域（项）组成。
数据处理的最小单位。
性质相同的数据元素的集合。
4.数据对象：
关系：见下图：
一个班学生集合为数据对象每一个数据元素均有六个数据域（项）
数据元素 1
数据元素 2
数据元素 33
………...
例如：学生管理登记卡特点：数据对象学号 姓名 性别 籍贯 民族 专业
98001 王立 男 河北 汉 计算机
98002 李立 男 山西 汉 自动化
98003 张颖 女 陕西 回 电信
… …,… … … …
980033 杨越 男 陕西 汉 通信数据元素 3
数据项
2009-7-30 软件基础教案（第一章 绪论）
5.数据结构：
计算机处理的数据元素的组织形式及其相互间的关系。
由数据元素的有限集合及所有数据元素之间的关系组成。记为：
Data_Structure = {D,R}
其中,D是数据元素的有限集,R是所有数据元素之间的关系的有限集合。
2009-7-30 软件基础教案（第一章 绪论）
例如：
下述数据结构来描述 2行 3列的矩阵：
它是一个含 6个数据元素 D={a1,a2,a3,a4,a5,a6} 的集合，且集合上存在 "行关系 "和 "列关系 "两个次序关系，其中行关系为
{<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}，列关系为
<a1,a4>,<a2,a5>,<a3,a6>}
654
321
aaa
aaa
2009-7-30 软件基础教案（第一章 绪论）
再例如：
Data_Structure = {D,R}
2009-7-30 软件基础教案（第一章 绪论）
逻辑结构线性结构,
非线性结构顺序存储链式存储所有元素呈线状关系的数据结构。
存储结构用一组地址连续的存储单元依次存储各个元素。
用一组不连续的存储单元存放数据元素。
逻辑结构 （逻辑数据结构）
存储结构 （物理数据结构）
从不同的抽象层次看：
2009-7-30 软件基础教案（第一章 绪论）
6.数据类型,
具有 相同性质 的计算机数据集合及在这个集合上的 一组操作 。
7.操作,数据结构上需要或能够进行的处理。
2009-7-30 软件基础教案（第一章 绪论）
数据结构逻辑结构存储结构操作实现算法线性数据结构非线性数据结构线性表栈队列树图顺序存储结构链式存储结构索引存储结构散列存储结构
2009-7-30 软件基础教案（第一章 绪论）
1.3 C语言的数据类型
1、基本数据类型
int short; long; unsigned
float float; double; long double
在 C语言中
数据类型：基本类型和构造类型
基本类型：整型、浮点型、字符型
构造类型：数组、结构、联合、指针,枚举型、
自定义
2.指针类型,
计算机的内存的数据存取：
内存区,地址 内存单元例,旅馆,房间号 房间
计算机访问内存的方式：
直接方式：按变量的地址存取变量。
间接方式：将变量的地址放在另一个变量中。
例,A抽屉的钥匙放在 B抽屉中。
对存放变量的地址进行操作；
函数间传递值
2009-7-30 软件基础教案（第一章 绪论）
指针：地址例,2000
i
表示,2000是变量 i的指针。
指针变量：
变量的指针：
指向变量的指针变量：
例,int *p_1;
char *p_2;,*”表示指针型变量基本型 *指针变量名定义：
2009-7-30 软件基础教案（第一章 绪论）
,&”:取地址运算。例,int *p_1;
int a;
p_1=&a;
“*”:指针运算符。例 （ *p_1） ++ 相当于 a++
引用：
2009-7-30 软件基础教案（第一章 绪论）
3,数组类型数组名就是数组的起始地址数组名作为函数参数时，为地址传递
int a[100];
a &a[0],a+1 &a[1]……
*a a[0],*(a+1) a[1]……
2009-7-30 软件基础教案（第一章 绪论）
4、字符串
字符串定义成字符数组
‘ \0’ 为字符串结束标志
char a[40]=,I am a student”
strlen(a) 为 14
不包括 ‘ \0’
2009-7-30 软件基础教案（第一章 绪论）
5,结构体类型结构体 由若干个 结构体成员组成。
定义结构体类型变量：
1.定义结构体 类型 ；
2.定义结构体类型 变量 。
struct student
{
char name[10];
int age;
float score;
};
struct student student1;
struct student stu2[100];
struct student *p;
2009-7-30 软件基础教案（第一章 绪论）
6,自定义类型
typedef char elemtype;
typedef struct student
{
char name[10];
int age;
float score;
} stu;
elemtype a;
stu student1;
2009-7-30 软件基础教案（第一章 绪论）
1.4 算法设计目标和算法效率度量
1.算法定义,一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列
2.算法特性：
输入性 有 0个或多个输入输出性 有一个或多个输出 (处理结果 )
确定性 每步定义都是确切、无歧义的有穷性 算法应在执行有穷步后结束；整个指令序列在有限的时间内完成。
可行性（有效性） 算法中的每一个步骤都应当能被有效的执行，并得到确定的结果。 例如：被零除的计算动作是不能被有效执行的。
算法的描述,c++,c,PASCAL,类 c等语言
2009-7-30 软件基础教案（第一章 绪论）
3,算法描述方法：
1）自然语言：
2）伪代码：
用自然语言描述，不准确，易产生多义。
英文或英文缩写。
3）流程图,（ 1）传统流程图
（ 2） N--S流程图
4）类 pascal语言,由 pascal语言指令（简化）描述。
5） C语言,用简化的 C语言指令描述。
2009-7-30 软件基础教案（第一章 绪论）
4,算法设计目标
（ 1）正确性,满足要求
（ 2）可读性,易于理解
（ 3）健壮性,可处理非法数据
（ 4）高效性,执行时间短
（ 5）低存储量,省空间
2009-7-30 软件基础教案（第一章 绪论）
5,评价算法的一般原则：
1） 正确性 。 这是首要条件，在有限的时间内得出结果。
2） 运行时间短,指占用 CPU时间。
3） 占用存储空间少 。
4） 最优性,在给定问题的所有算法中,执行的运算次数最少
5） 可读性,要求算法易于理解,便于分析
6） 可修改可扩展性,如果解决问题 P 的一个算法是 A,为了解答一个与 P类似的问题,希望对 A稍做改动就可正确运行,如算法 A满足这一点,则说 A的可修改性好 。
2009-7-30 软件基础教案（第一章 绪论）
6.算法效率的度量首先算法必须是正确的。此外还需考虑：
1,算法易于理解,易于编程（在计算机上实现），
易于调试。
2,要求算法高效,节省时间与空间。
时间和空间相互之间有一种制约关系，何者为重需视具体情况而定。
重点考虑因素,时间
2009-7-30 软件基础教案（第一章 绪论）
Main()
{
int a=1;
int b=0;
for(int i=0;i<10;i++)
{
b=b+a;
}
}
Main()
{
int b=0;
for(int i=0;i<10;i++)
{
int a=1;
b=b+a;
}
}
例 1:
2009-7-30 软件基础教案（第一章 绪论）
一个算法所耗费的 时间,应该是该算法中每条 语句的执行时间之和,而每条语句的执行时间又是该语句的 执行次数
（频度）与该语句执行 一次所需时间的乘积 。
我们假定，每条语句一次执行的时间都是 相同 的，为单位时间。这样我们对时间的分析就可以独立于软硬件系统。
一般，时间复杂度是问题规模的函数 － T( n )。
当问题的规模 n 趋于无穷大时,把时间复杂度 T( n )的数量级
（ 阶 ） 称为算法的渐进时间复杂度 （ 有时简称为 时间复杂度
） 。
2009-7-30 软件基础教案（第一章 绪论）
严格的数学定义为：若 T( n ) 和 f( n ) 是定义在正整数集合上的两个函数，当存在两个正的乘数 C和 n0时，使得对所有的
0nn?
)()( nfcnT
))(()( nfOnT?成立，则都有这时称 T( n )的时间复杂度为 f( n )数量级 。
1、假定每条语句的执行时间为单位时间。算法的时间复杂度是该算法中所有语句的执行频度之和。
2009-7-30 软件基础教案（第一章 绪论）
x=x+1;执行 n次 O(n）
x=x+1;只执行一次 O(1）? x=x+1;
For(i=1;i<=n;i++)
x=x+1;
For(i=1;i<=n;i++)
For(j=1;j<=n;j++)
x=x+1;
x=x+1;执行 n2次 O(n2）
例 2,计算时间复杂度
2009-7-30 软件基础教案（第一章 绪论）
＃ define n 自然数
matri(float A[n][n],float B[n][n],float C[n][n])
{
int i,j,k;
for(i=0;i<n;i++) //n+1
for(j=0;j<n;j++) //n(n+1)
{
C[i][j]=0; //n*n
for( k=0;k<n;k++) //n*n*(n+1)
C[i][j]=A[i][k]*B[k][j] //n*n*n
}
} 1232)( 23 nnnnT T(n)=O(n3)
例 3：求两个方阵的乘积 C＝ A*B
2009-7-30 软件基础教案（第一章 绪论）
2。一般情况下，对步进循环语句只考虑循环体语句的执行次数
，而 忽略 该语句中 步长加一、终值判别、循环转移 等成份。因此，当有若干个循环语句时，算法的时间复杂度是 由嵌套层数最多的循环语句中最内层语句的频度 所决定的。
例,x=0;y=0;
for (k=1;k<=n;k++)
x++;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) //n*n
y++; T(n)=O(n2)
2009-7-30 软件基础教案（第一章 绪论）
3,选择执行的成分,如 if 语句的执行时间，决定于 then 子句、
else 子句耗时较多的部分例,temp = i;
i = j;
j = temp;
4、如果算法的 执行时间是一个与问题规模 n无关的常数,则算法的时间复杂度为常数阶，记作 T(n)=O(1)。
T(n)=O(1)
2009-7-30 软件基础教案（第一章 绪论）
例：
i=n-1;
while ((i>=0)&&A[i]!=k))
i--;
return i;
5、很多算法的时间复杂度不仅与问题的规模有关，而且还与它所处理的数据集的状态有关。通常是根据数据集中可能出现的最坏情况估计出算法的 最坏时间复杂度 。
T(n)=O(n)
2009-7-30 软件基础教案（第一章 绪论）
常数阶对数阶线性阶线性对数阶平方阶立方阶
K次方阶指数阶
)1(O
常见的时间复杂度，按数量级递增排序：
)( lo g 2 nO
)(nO
)lo g( 2 nnO
)( 2nO
)( 3nO
)( knO
)2( nO
2009-7-30 软件基础教案（第一章 绪论）
概念,数据，数据元素，数据项，数据结构，
数据类型，操作数据结构研究内容算法目标和算法评价 （ 时间复杂度 ）
作业,P32 1-2,1-9,2,3,4,6
总结：
