数据结构第一章.ppt

1、数据结构,主讲：帅小应 shuai_,课程简介,数据结构重要吗？ Yes Why? 专业基础课 程序设计的重要理论基础 算法 数据结构,程序设计,操作系统,软件工程,网络,应用举例,文本编辑器的撤销序列 IE历史记录 Stack (栈) 访问共享资源（打印机） 等待队列 Queue (队列) 地图导航？ 无线接入冲突？,合理的数据结构,要求,熟悉C语言编程 按时完成作业与上机实验 认真听课并做好必要的上课笔记 积极思考与讨论 自主学习,考核办法,笔试 平时考核 考勤 作业 上机考核 实验 设计,C 要点,循环程序设计 for while do while 数组 函数 指针 结构体,基本知识,常

2、量 #define TRUE 1 typedef 声明新的类型代替已有的类型 typedef float REAL; ,循环程序设计,for语句的一般格式 for(变量赋初值；循环继续条件；循环变量增值) 循环体语句组； ,循环程序设计,while语句 while(循环继续条件) 循环体语句组； ,循环程序设计,do-while语句 do 循环体语句组; while(循环继续条件);,循环程序设计,例 百钱买百鸡 有人用100个钱买了100只鸡，一只母鸡4个钱，一只公鸡3个钱，小鸡两只1个钱，问公鸡、母鸡、小鸡各几只？,数组,数组的定义 数组元素的引用 数组的元素的初始化 应用举例,数组,数组

3、的定义 数据类型 数组名常量表达式 int a10; 下标从0开始 数组名代表整个数组的首地址,数组,一维数组元素的引用 数组名下标表达式 一维数组的元素的初始化 数据类型 数组名常量表达式初值表,数组,二维数组的定义 数据类型 数组名行常量表达式列常量表达式 int a34,数组,字符数组 输入字符串gets()函数 输出字符串puts()函数 字符串比较strcmp()函数 拷贝字符串strcpy()函数 连接字符串strcat()函数 字符串长度strlen()函数,数组,例 fibonacci数列 int i; int f20=1，1; for(i=2；i20;i+) fi=fi-2+

4、fi-1; for(i=0;i20;i+) if(i%5=0) printf(n); printf(%12d，fi); ,作业,将十进制数转换为K进制数 简要写出解题步骤 写出关键程序,函数,函数的定义与调用 数组作为函数参数 递归调用,函数,函数的定义 函数类型 函数名( 数据类型 参数，数据类型 参数2 ) 声明语句部分； 可执行语句部分； ,函数,函数的调用 函数调用的一般形式为： 函数名(实际参数表) max(a, b) 形式参数和实际参数 值传递,函数,递归调用 一个函数在它的函数体内，直接或间接地调用它自身 例如求N！(n=0) long power(int n) long f;

5、if(n1) f=power(n-1)*n; else f=1; return (f); ,函数,数组作为函数参数 数组名作为函数的形参和实参使用 实现地址传送 float average（float array10） averaverage（score）； /调用 float average（float array，int n） averaverage（score，10）； /调用,指针,指针的基本概念及应用 数组的指针 返回指针值的函数 字符串指针,指针,指针的基本概念及应用 指针与指针变量 指针即地址；变量的地址称为该变量的指针。 指针变量存储其它变量地址的变量。 指针变量的定义 数据类

6、型 *指针变量； 例如：int *p;float *f; char *c; 指针运算符 ,指针,内存动态分配函数 malloc（size）分配size字节空间 free（指针） 释放空间 例如 char *p; p=malloc(20); strcpy(p,”Hello”); puts(p); free(p);,指针,指针与数组 数组的指针：数组在内存中的起始地址 数组元素的指针：数组元素在内存中的起始地址 数组指针的定义与赋值 int *p; p=a ;/* p为1000 */,指针,通过指针引用数组元素 p+i和a+i都是数组元素a i的地址。 *(p+i)和*(a+i)就是数组元素a i

7、。 指向数组的指针变量，也可将其看作是数组名，因而可按下标法来使用。例如，p i等价于*(p+i)。 注意：p+1指向数组的下一个元素，而不是简单地使指针变量p的值+1。其实际变化为p+1*size(size为一个元素占用的字节数）。 例如：*p为第0个即a0的值 *(p+2)为第2个即a2的值,指针,例 使用指向数组的指针变量来引用数组元素 main() int array10, *pointer=array, i; printf(“Input 10 numbers: ”); for(i=0; i10; i+) scanf(“%d”, pointer+i);/*使用指针变量来输入数组元素的值

8、*/ printf(“array10: ”); for(i=0; i10; i+) printf(“%d ”, *(pointer+i);/*使用指向数组的指针变量输出数组*/ printf(“n”); 程序运行情况： Input 10 numbers: 0 1 2 3 4 5 6 7 8 9 array10: 0 1 2 3 4 5 6 7 8 9,指针,返回指针值的函数 返回指针值的函数（简称指针函数）的定义格式如下： 函数类型 *函数名(形参表),指针,字符串指针 字符串在内存中的起始地址称为字符串的指针，可以定义一个字符指针变量指向一个字符串。 在语言中，既可以用字符数组表示字符串，也

9、可用字符指针变量来表示；引用时，既可以逐个字符引用，也可以整体引用。 main() char *string=”I love C.”; for(; *string!=0; string+) printf(“%c”, *string); printf(“n”); ,指针,字符指针变量与字符数组之比较 存储内容不同 字符指针变量中存储的是字符地址，而字符数组中存储的是字符。 赋值方式不同 对字符指针变量，可用赋值语句赋值 字符数组，可在定义时初始化，不能整体赋值 指针变量的值是可以改变的 数组名代表数组的起始地址，是一个常量，而常量是不能被改变的,结构体,结构体类型与结构体变量的定义 结构体变量的

10、引用与初始化 结构体指针 结构体数组,结构体,结构类型定义 struct 结构类型名 /* struct是结构类型关键字*/ 数据类型 成员名1; 数据类型 成员名2; 数据类型 成员名; ;,结构体,结构体变量定义 先定义结构体类型、再定义结构体变量 struct date birthday; 在定义结构类型的同时，定义结构变量 一般格式为：struct 结构类型名 结构变量表； 例如： struct std_info student;,结构体,结构体变量的引用 引用结构体变量中的一个成员 结构体变量.成员名 结构体变量的整体引用 可以将一个结构体变量作为一个整体赋给另一个同类型的结构体变量

11、。 结构体变量的输入与输出 不允许把一个结构体变量作为一个整体进行输入与输出，须指明结构体变量对应的各成员项。,结构体,结构数组 结构数组的每一个元素，都是结构类型数据。 与结构变量的定义相似，结构数组的定义也分直接定义和间接定义两种方法，只需说明为数组即可。,结构体,结构体指针 结构变量在内存中的起始地址称为结构变量的指针。 定义格式：struct 结构体类型名 *结构体指针名； 例如：struct date birthday,*p; p=,结构体,指向运算符- 一般地说，如果指针变量pointer已指向结构变量var，则以下三种形式等价： （1）var.成员 （2）pointer-成员 （

12、3）(*pointer).成员,上机作业,定义一个结构体变量,其成员项包括工作证号、姓名、工资，编程计算N名职工的总工资和平均工资。,数据结构基本概念和术语,程序设计=算法+数据结构 程序设计的实质即为计算机处理问题编制一组“指令”，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略，而数据结构即为问题的数学模型。 数据结构是一门讨论描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现的学科。,基本概念,数据 是所有能被输入到计算机中，且能被计算机处理的符号(数字、图像等)的集合 数据元素 是数据中的个体，在计算机中通常作为一个整体进行考虑和处理，是数据结构中

13、讨论的基本单位。,基本概念,数据结构(Data structure) 具有特定关系的数据元素集合 数据结构的形式定义为： Data_Structures = ( D,S ) 其中： D是数据元素的有限集， S是D上关系的有限集,基本概念,研究数据结构，是指研究数据的逻辑结构和物理结构 数据的逻辑结构：数据元素之间的逻辑关系 数据的物理结构：数据元素在计算机存储器中是如何存储的,基本概念,抽象数据类型 Abstract Data Type 简称 ADT 指一个数学模型以及定义在此数学模型上的一组操作 ADT = ( D，S，P )其中：D 是数据对象，S 是 D 上的关系集，P 是 D 的基本操

14、作集,算法,算法 算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。重要特性： 有穷性 对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。 确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。,算法,可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。 有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。但有些算法的字面上可以没有输入，实际上已被嵌入算法之中。 有输出 它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算

15、法的功能。,算法,算法的描述 采用类C语言 类型约定为 ElemType 上机时再自行具体定义 基本操作的算法都用以下形式的函数描述,算法,算法评价 正确性 运行时间 占用的存储空间 简单性,算法,时间复杂性 一个算法所需的运算时间通常与所解决问题的规模大小及采用的“策略”有关。 用n 表示问题规模的量 ，把算法运行所需的时间T表示为n的函数，记为T(n)。 不同的T(n)算法，当n增长时，运算时间增长的快慢很不相同。,算法,时间复杂性 渐进时间复杂性：当n逐渐增大时T(n)的极限情况，一般简称为时间复杂性 时间复杂性常用数量级的形式来表示，记作T(n)=O(f(n)。如T(n)=O(n2)。 一种增长趋势的量度,