数据结构 清华大学出版社 第1章 绪论-1.ppt

1、自我介绍,何春香 北京理工大学珠海学院 Tel:数据结构,课程名称：数据结构 预修课程: C语言, 高等数学,离散数学 教 材：数据结构(C语言版)清华大学出版社,Data Structures /*存储学号*/ char name8; /*存储姓名*/ char sex2; /*存储性别*/ char class4; /*存储班号*/ Stud7=1,“张斌”,“男”,“9901”, 5,王萍,女,9901;,结构体数组,存放学生表的链表的结点类型 StudType定义为： typedef struct studnode int no; /*存储学号*/ char

2、name8; /*存储姓名*/ char sex2; /*存储性别*/ char class4; /*存储班号*/ struct studnode *next; /*存储指向 下一个学生的指针*/ StudType；,链表,head,1,张斌,男,9901,8,刘丽,女,9902,34,李英,女,9901,20,陈华,男,9902,12,王奇,男,9901,26,董强,男,9902,5,王萍,女,9901,学生表构成的链表,学生表构成的链表如右图所示。其中的head为第一个数据元素的指针。,对于“学生表”这种数据结构,可以进行一系列的运算,例如: 增加一个学生记录、删除一个学生记录、查找性别为

3、“女”的学生记录,查找班号为“9902”的学生记录等等。 从前面介绍的两种存储结构看到,同样的运算,在不同的存储结构中,其实现过程是不同的。,对于Stud数组,可以从Stud0开始比较,Stud0.no不等于20,再与Stud1.no比较,直到Stud3.no等于20,返回S。,例如,查找学号为20的学生的姓名：,对于head为首结点指针的链表,从head所指结点开始比较,head-no不等于20,从它的next得到下一个结点的地址,再与下一个结点的no域比较,直到某结点的no域等于20,返回其name域。,链表,结构体数组,对比,3、数据的运算：检索、排序、插入、删除、修改

4、等。,数据结构可描述为 Data_Structure =（D，S）,数据结构的三要素：逻辑结构，存储结构，运算。,抽象的数据类型,数据类型（Data Type）： 值的集合以及定义在这个集合上的一组操作。 例如: C语言中的整数类型 C语言中分：原子类型和结构类型,原子类型：值不可分解,结构类型：值可以分解，成分可以是非结构或结构的,基本类型（整型、实型、字符型、枚举类型） 指针类型 空类型,数组 结构 联合,抽象的数据类型,抽象数据类型(ADT) 数学模型以及定义在该模型上的一组操作。 与其在计算机中的表示和实现无关。 ADT可用三元组表示：（D,S,P） D 数据对象; S D上的关系;

5、P 对D的基本操作集,数学抽象特性 类型更加广泛，可自由定义,即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。,注: 抽象数据类型数据类型实质是一个概念.,抽象数据类型的定义格式：,ADT抽象数据类型名 数据对象D：数据对象的定义 数据关系S：数据关系的定义 基本操作P：基本操作的定义ADT抽象的数据类型名 基本操作的定义格式为：基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述,1.3抽象数据类型的表示与实现,类C语言（作了扩充和修改）的表示,自学1.3节-“课件1.3-”,类语言的语法规则,1、预定义常量和类型： 2、数据结构的描述，数据元素类型的定义 3、基本操作的算法可以使用的函数表示 4、算法描述中可以使用的赋值语句形式 5、算法描述中可以使用的选择结构语句形式 6、算法描述中可以使用的循环结构语句形式 7、描述算法中可以使用的结