计算机软件基础绪论

计算机软件基础教学目的和任务：1、本课程的任务是在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。2、设置本课程的目的在于为后继的专业课打基础，能够使用计算机软件方法解决问题的能力，同时也为从事计算机软件的开发提供基础知识。本课程先修课为C语言。参考教材：学习教材：《计算机软件基础》，孟彩霞编，西安电子科技大学出版社参考教材：《数据结构(C语言版)》严蔚敏、吴伟民清华大学出版社

《计算机软件技术基础》,李淑芬等编著出版社：机械工作出版社，2009年8月第一版课程要求：教学内容重点分为1、掌握数据结构的基础知识。包括线性表、栈和队列、树、二叉树和图的部分概念。2、掌握查找及排序相关的概念、算法和应用。课程要求：（1）基本要求

掌握基本原理；熟悉主要算法特点；了解常用算法的设计思想与结构。注意：理论性强，比较枯燥。学好理论，才能在实际程序设计灵活应用。（2）学习方法a.知识：需要记忆、积累、联想、对比——抓重点b.技能：需要训练、经验、方法、技巧——抓特点c.思路：逻辑思维、形象思维（3）认真完成书后作业和补充习题。

学时安排授课36+上机18内容学时内容学时绪论3树和二叉树8线性表6图2堆栈和队列4排序4串查找4数组2文件递归算法复习3数学软件硬件数据结构的地位是介于数学、计算机硬件和计算机软件三者之间的一门核心课程第一章绪论1.1

数据结构的基本概念1.2数据结构研究的内容和方法1.4*C语言相关内容复习1.3算法和算法分析1.1

数据结构的基本概念为什么学习数据结构数值计算数学模型→选择计算机语言→编出程序→测试→最终解答。数值计算的关键是：如何得出数学模型（方程）？程序设计人员比较关注程序设计的技巧。非数值计算数据元素之间的相互关系一般无法用数学方程加以描述数据描述客观事物的数字、字符以及一切能够输入到计算机中，并且能够被计算机程序处理的符号的集合。

数据元素

表示一个事物的一组数据，是数据的基本单位，又称结点。在计算机程序中通常作为一个整体进行处理。一个数据元素由若干数据项构成。数据结构数据元素之间具有的关系，即数据的组织形式。数据对象具有相同性质的数据元素组成的集合。基本概念表结构学号姓名性别籍贯出生年月住址06048001赵玲女上海1987.10上海06048002杨扬男北京1987.3北京………………………………学籍登记表交通图乌鲁木齐兰州西安呼和浩特北京郑州成都18921145668676695511842图结构

非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。数据结构课程研究的是计算机所处理的数据元素间的结构关系及其操作实现的算法

1.

研究数据元素之间的客观联系。

2.

研究具有某种逻辑关系的数据在计算机存储器内的存储方式。

3.研究如何在数据的各种结构(逻辑的和物理的)

的基础上对数据实施一系列有效的基本操作。

逻辑结构存储结构1.2数据结构研究的内容算法数据结构：

计算机处理的数据元素的组织形式及其相互间的关系。由数据元素的有限集合及所有数据元素之间的关系组成。记为：

Data_Structure={D,R}

其中，D是数据元素的有限集，R是所有数据元素之间的关系的有限集合。

根据数据元素间关系的基本特性，有四种基本数据结构集合结构

数据元素间除“同属于一个集合”外，无其它关系线性结构

一个对一个，如线性表、栈、队列树形结构

一个对多个，如树图状结构

多个对多个，如图集合结构数据结构:

SET=（K,R）

K={01,02,03,04,05,06,07,08,09,10} R={}08010305020704060910集合结构示意图线性结构数据结构

LINEARITY=（K,R）

K={01,02,03,04,05,06,07,08,09,10}R={<05,01>,<01,03>,<03,08>,<08,02>,<02,07>,<07,04>,<04,06>,<06,09>,<09,10>}05010308020704060910线性结构示意图数据元素之间的联系：1:1树结构数据结构

TREE=（K,R）K={01,02,03,04,05,06,07,08,09,10}R={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>,<04,10>}01020304070809050610树结构示意图数据之间的联系：1：NGraph=(D,R)D={1,2,3,4,5,6,7,8,9}R={<1,2>,<1,3>,<2,4>,<2,5>,<2,6>,<2,8>,<3,2>,<3,4>,<4,5>,<5,7>,<6,7>,<6,9>,<7,9>,<8,9>}图结构数据之间的联系：M：N存储结构（StorageStructure):数据在计算机中的表示(或称映象）称为数据的存储结构，又称为物理结构。四种基本的存储方法：（1）顺序存储方法（顺序存储结构）（2）链接存储方法（链式存储结构）（3）索引存储方法（4）散列存储方法同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。

数据的逻辑结构

数据的存储结构数据的运算

线性结构

非线性结构

顺序存储

链式存储线性表堆栈队列树形结构图形结构数据结构的三个方面：

散列存储索引存储串及数组查找、排序、插入、删除、修改等1.3算法和算法分析1.算法的定义(1).

算法是用来解决某个特定问题的指令的集合。(2).

算法是由人们组织起来准备加以实施的一系列有限的基本步骤。2.算法的描述文字形式程序设计语言形式（如C语言等）伪码形式3.算法的性质

一个完整的算法应该满足下面五个基本标准：输入性

有0个或多个输入输出性有一个或多个输出(处理结果)确定性每步定义都是确切、无歧义的有穷性算法应在执行有穷步后结束；整个指令序列在有限的时间内完成。可行性（有效性）算法中的每一个步骤都应当能被有效的执行，并得到确定的结果。例如：被零除的计算动作是不能被有效执行的。4.算法设计目标正确性可读性健壮性高时间效率高空间效率当时间效率目标和空间效率目标发生矛盾时，应先考虑时间效率目标5.算法分析时间复杂度T（n）空间复杂度S（n）其它（如可读性、可移植性等）前提条件：算法必须正确

2.源程序编译的强弱以及所产生的机器代码质量的优劣。3.机器执行一条指令的时间长短。4.程序中语句的执行次数。1.问题的规模。

一个程序在计算机中运行时间的多少与诸多因素有关，其中主要有：4.时间复杂度称为时间频度，记为T（n）

定义：若有一辅助函数f(n)，当n趋于无穷大时，T(n)/f(n)为一不等于零的实常数，则f(n)为T(n)的同数量级函数，记为

T(n)=O(f(n))

称O(f(n))为时间复杂度。

例：3n+2=O(n)/*3n+24nforn2*/10n2+4n+2=O(n2)/*10n2+4n+211n2forn5*/6*2n+n2=O(2n) /*6*2n+n27*2nforn4*/常用的计算规则：1.加法规则

T(n)=T1(n)+T2(n)=O(f1(n))+O(f2(n))

=O(max(f1(n),f2(n)))

2.乘法规则

T(n)=T1(n)×T2(n)=O(f1(n))×O(f2(n))=O(f1(n)×f2(n))

时间复杂度T(n)按数量级递增顺序为：

注

空间复杂度S(n)按数量级递增顺序也与上表类同。复杂度高复杂度低时间复杂度的计算：例1：{++x;s=0;}2O(1)for(i=1;i<=n;++i){++x;s+=x;}2nO(n)for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}n*2nO(n2)例2：例3：频度时间复杂度程序例4：频度时间复杂度程序x=n;//n>1while(x>=(y+1)*(y+1))y++;n1/2-1O(n1/2)例5：x=91;y=100;while(y>0)if(x>100){x=x-10;y--;}elsex++;常数O(1)例6：频度时间复杂度程序O(n3)inti,j,k,x=0;for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+2;按增长率由小至大的顺序排列下列各函数：

2100,(3/2)n,(2/3)n,nn,n0.5,n!,2n,lgn,nlgn,n3/2

思路：先将题中的函数分成如下几类：常数阶：2100对数阶：lgnK次方阶：n0.5、n3/2

指数阶(按指数由小到大排)：nlgn、(3/2)n、2n、n!、nn(2/3)n<2100<lgn<n0.5<n3/2<nlgn<(3/2)n<2n<n!<nn

1、数据结构是指计算机处理的

的组织形式以及它们相互之间的

。①A.数据元素B.计算方法

C.逻辑存储D.数据映像②A.结构B.关系

C.运算D.算法课堂练习3、衡量算法好坏的两个主要指标有算法的

和

。时间复杂度空间复杂度2、数据结构研究数据的

、

和操作实现算法。

A.结构关系、组织形式

B.逻辑结构、物理结构

C.数据元素、数据对象

D.数据复杂性、程序复杂性4、下面程序段的时间复杂度是

。

i=s=0;while(s<n){i++;s+=i;}O(n)5、算法的时间复杂度仅与问题的规模有关。（）×*还与输入的元素取值有关6、下面程序段A[i][j]=0执行次数为

,

时间复杂度为

。

for(i=1;i<=n;i++)for(j=1;j<=i;j++)A[i][j]=0;n(n+1)/2O(n2)

理解：数据，数据元素，数据项，数据结构。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。

掌握：算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，对一般算法要能分析出时间复杂度。小结END复习：C语言的数据类型1、基本数据类型intshort;long;unsignedfloatfloat;double;longdouble2、指针类型10003i_pointeri地址（i的指针）指针变量1000*i_pointeri100015i=3;3inti;

指针变量的定义

inti;int*i_pointer;i_pointer=&i;i=3;*i_pointer=3;5main(){intx=5;printf(“\n%d”,x);Function1(x);printf(“\n%d”,x)}voidFunction1(intx){x++;printf(“\n%d”,x);}main(){intx=5;printf(“\n%d”,x);Function1(&x);printf(“\n%d”,x)}voidFunction1(int*px){(*px)++;printf(“\n%d”,*px);}值传送地址传送x5x6x51000px1000*px63.数组类型数组名就是数组的起始地址数组作为函数参数时，为地址传递inta[100];a&a[0],a+1&a[1]……*aa[0],*(a+1)a[1]……4、字符串

字符串定义成字符数组

‘\0’为字符串结束标志chara[40]=“Iamastudent”;strlen(a)为14不包括‘\0’5.结构体类型结构体由若干个结构体成员组成。定义结构体类型变量：1.定义结构体类型；2.定义结构体类型变量。structstudent{charname[10];intage;floatscore;};structstudentstudent1;structstudentstu2[100];structstudent*p;6.

自定义类型typedefcharelemtype;typedefstructstudent{charname[10];intage;floatscore;}stu;elemtypea;stustudent1;

数据项具有独立含义的最小标识单位,是数据的最小单位数据元素数据项学号姓名性别籍贯出生年月住址06048001赵玲女上海1987.10上海06048002杨扬男北京1987.3北京………………………………

逻辑结构a1a2a3a30…d1d2d3d4

…d30a2a1a3a4a30存储结构1.顺序存储结构线性结构（线性表）刘晓光马广生王民…张玉华男男…女男汉回壮…汉161721…25……………

姓名性别民族年龄其他

例2.链式存储结构…d1d2d3d4

a1a2a3a30∧list…a2a1a4a3d4d1d5d3百钱买百鸡问题:100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？

for(i=0;i<=100;i++)for(j=0;j<=100;j++) for(k=0;k<=100;k++) {if(k%3==0&&(i+j+k)==100&&(5*i+3*j+k/3)==100) printf(“%d,%d,%d\n”,i,j,k);}求解：设母