数据结构第一章ppt课件.ppt

《数据结构第一章ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构第一章ppt课件.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第一章ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望课程简介数据结构重要吗？YesWhy?专业基础课程序设计的重要理论基础算法数据结构程序设计操作系统软件工程网络应用举例文本编辑器的撤销序列IE历史记录Stack(栈)访问共享资源（打印机）等待队列Queue(队列)地图导航？无线接入冲突？合理的数据结构要求熟悉C语言编程按时完成作业与上机实验认真听课并做好必要的上课笔记积极思考与讨论自主学习考核办法笔试平时考核考勤作业上机考核实验设计C 要点循

2、环程序设计forwhiledo while数组函数指针结构体基本知识常量#define TRUE 1typedef声明新的类型代替已有的类型typedef float REAL;&引用参数地址TRUE MAX（REAL&a,REAL&b)基本知识malloc分配内存void*malloc(size)p1=(int*)malloc(sizeof(int)free释放内存void free(void*p)free(p1);循环程序设计for语句的一般格式for(变量赋初值；循环继续条件；循环变量增值)循环体语句组；循环程序设计while语句while(循环继续条件)循环体语句组；循环程序设计do-

3、while语句 do 循环体语句组;while(循环继续条件);循环程序设计例百钱买百鸡有人用100个钱买了100只鸡，一只母鸡4个钱，一只公鸡3个钱，小鸡两只1个钱，问公鸡、母鸡、小鸡各几只？数组数组的定义数组元素的引用数组的元素的初始化应用举例数组数组的定义数据类型 数组名常量表达式int a10;下标从0开始数组名代表整个数组的首地址数组一维数组元素的引用数组名下标表达式一维数组的元素的初始化数据类型 数组名常量表达式初值表数组二维数组的定义数据类型 数组名行常量表达式列常量表达式int a34数组字符数组输入字符串gets()函数输出字符串puts()函数字符串比较strcmp()函数

4、拷贝字符串strcpy()函数连接字符串strcat()函数字符串长度strlen()函数数组例fibonacci数列 int i;int f20=1，1;for(i=2；i20;i+)fi=fi-2+fi-1;for(i=0;i=0)long power(int n)long f;if(n1)f=power(n-1)*n;else f=1;return(f);函数数组作为函数参数数组名作为函数的形参和实参使用实现地址传送float average（float array10）averaverage（score）；/调用 float average（float array，int n）aver

5、average（score，10）；/调用指针指针的基本概念及应用数组的指针返回指针值的函数字符串指针指针指针的基本概念及应用指针与指针变量指针与指针变量指针即地址；变量的地址称为该变量的指针。指针变量存储其它变量地址的变量。指针变量的定义指针变量的定义数据类型 *指针变量；例如：int*p;float*f;char*c;指针运算符指针运算符&取操作数的内存地址*指针运算，访问指针变量所指向的变量的值int i,*p;p=&i;指针内存动态分配函数malloc（size）分配size字节空间free（指针）释放空间例如 char*p;p=malloc(20);strcpy(p,”Hello”)

6、;puts(p);free(p);指针指针与数组数组的指针：数组在内存中的起始地址数组元素的指针：数组元素在内存中的起始地址数组指针的定义与赋值int*p;p=a;/*p为1000*/a1000100210041006123654指针通过指针引用数组元素p+i和a+i都是数组元素a i的地址。*(p+i)和*(a+i)就是数组元素a i。指向数组的指针变量，也可将其看作是数组名，因而可按下标法来使用。例如，p i等价于*(p+i)。注注意意：p+1指向数组的下一个元素，而不是简单地 使 指 针 变 量 p的 值+1。其 实 际 变 化 为p+1*size(size为一个元素占用的字节数）。例如

7、：*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);/*使用指针变量来输入数组元素的值*/printf(“array10:”);for(i=0;i 一般地说，如果指针变量pointer已指向结构变量var，则以下三种形式等价：（1）var.成员（2）pointer-成员（3）(*pointer).成员上机作业定义一个结构体变量,其成员项包括工作证号、姓

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

9、据元素集合 数据结构的形式定义为：Data_Structures=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集基本概念研究数据结构，是指研究数据的逻辑结构和物理结构 数据的逻辑结构：数据元素之间的逻辑关系数据的物理结构：数据元素在计算机存储器中是如何存储的 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面数据结构的三个方面：基本概念抽象数据

10、类型Abstract Data Type 简称 ADT指一个数学模型以及定义在此数学模型上的指一个数学模型以及定义在此数学模型上的一组操作一组操作ADT=(D，S，P)其中：D 是数据对象，S 是 D 上的关系集，P 是 D 的基本操作集算法算法算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列操作序列。重要特性特性：有穷性有穷性 对于任意一组合法的输入值，在执行有穷步有穷步骤骤之后一定能结束。确定性确定性 对于每种情况每种情况下所应执行的操作，在算法中都有确切确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。算法可行性可行性 算法中的所有操作都

11、必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。有输入有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。但有些算法的字面上可以没有输入，实际上已被嵌入算法之中。有输出有输出 它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。算法算法的描述采用类C语言类型约定为 ElemType上机时再自行具体定义基本操作的算法都用以下形式的函数描述算法算法评价正确性运行时间占用的存储空间简单性算法时间复杂性一个算法所需的运算时间通常与所解决问题的规模大小及采用的“策略”有关。用n 表示问题规模的量，把算法运行所需的时间T表示为n的函数，记为T(n

12、)。不同的T(n)算法，当n增长时，运算时间增长的快慢很不相同。算法时间复杂性渐进时间复杂性：当n逐渐增大时T(n)的极限情况，一般简称为时间复杂性时间复杂性常用数量级的形式来表示，记作T(n)=O(f(n)。如T(n)=O(n2)。一种增长趋势的量度算法例计算下面求累加和程序段的时间复杂性 （1）sum=0；（一次）（2）for(i=1;i=n;i+)（n次）（3）for(j=1;j=n;j+)（n2次）（4）sum+；（n2次）解：T(n)=2n2+n+1=O(n2)算法分析下列算法的时间复杂性 sum=0;for(i=1;i=n;i+)sum=sum+i;O(n)i=1;while(i=n)i=i*10；O(lgn)本章小结本章小结基本概念算法C语言基础