[理学]数据结构PPT第一章.ppt

数据结构 文玉锋 E_mail:wenyf@nwnu.edu.cn 相关知识 指针 数组 结构 动态内存分配 动态内存分配的概念 Ｃ语言中不允许动态数组类型。例如： int n; scanf(%d,n); int a[n]; 用变量表示长度，想对数组的大小作动态说明， 这是错误的。但是在实际的编程中，往往会发生这种情况， 即所需的内存空间取决于实际输入的数据，而无法预先确定。对于这种问题， 用数组的办法很难解决。为了解决上述问题，Ｃ语言提供了一些内存管理函数，这些内存管理函数可以按需要动态地分配内存空间， 也可把不再使用的空间回收待用，为有效地利用内存资源提供了手段。 C++中动态内存分配的操作 申请内存：malloc()函数 调用形式： (类型说明符*) malloc (size) 功能：在内存的动态存储区中分配一块长度为“size” 字节的连续区域。函数的返回值为该区域的首地址。 “类型说明符”表示把该区域用于何种数据类型。(类型说明符*)表示把返回值强制转换为该类型指针。“size”是一个无符号数。 例如： pc=(char *) malloc (100); 表示分配100个字节的内存空间，并强制转换为字符数组类型， 函数的返回值为指向该字符数组的指针， 把该指针赋予指针变量pc。 释放内存：free()函数 调用形式： free(void*ptr); 功能：释放ptr所指向的一块内存空间，ptr 是一个任意类型的指针变量，它指向被释放区域的首地址。被释放区应是由malloc函数所分配的区域： For example: Typedef struct stu { int num; char *name; char sex; float score;} stu; main() { stu *ps; ps=(struct stu*)malloc(sizeof(struct stu));ps-num=102;ps-name=Zhang ping;ps-sex=M;ps-score=62.5;printf(Number=%d\nName=%s\n,ps-num,ps-name);printf(Sex=%c\nScore=%f\n,ps-sex,ps-score);free(ps);} 什么是数据结构 抽象数据类型 算法及分析 “学生”表格 “课程”表格 “选课单”包含如下信息 学号 课程编号 成绩 时间  学生选课系统中实体构成的网状关系 文件系统的系统结构图 1.1 数据结构的基本概念 数据结构定义: 1.2 数据结构中的基本概念 例： 1.3 数据结构的三个层次 1.3.1 数据的逻辑结构 数据的逻辑结构相关解释： 数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关； 数据的逻辑结构可以看作是从具体问题抽象出来的数据模型； 数据的逻辑结构与数据元素本身的形式、内容无关； 数据的逻辑结构与数据元素的相对位置无关。 1.3.2 数据的存储结构 数据的存储结构是逻辑结构用计算机语言的实现； 数据的存储结构依赖于计算机语言。 1.3.3 数据的操作 1.3.4 数据结构的命名 1.3.5 常见的数据结构 1.3.6 数据类型和抽象数据类型 构造数据类型由基本数据类型或抽象造数据类型组成。 基本数据类型可以看作是计算机中已实现的数据结构。 数据类型就是数据结构，不过它是从编程者的角度来使用的。 数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。 例：自然数的抽象数据类型定义 ADT NaturalNumber is objects: 一个整数的有序子集合,它开始于0, 结束于机器能表示的最大整数(MaxInt)。 Function: 对于所有的 x, y ? NaturalNumber; False, True ? Boolean, +、-、、==、=等都是可用的服务。 1.4 算法定义 定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列 特性： 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本 性能分析与度量 算法的性能标准 算法的后期测试 算法的事前估计 时间复杂度度量 运行时间 = 算法中每条语句执行时间之和。 每条语句执行时间 = 该语句的执行次数（频度）* 语句执行一次所需时间。 语句执行