数据结构1-1绪论

数据结构

（C语言版）

中国石油大学（北京）计算机科学与技术系李莉

1计算机科学与技术系地质楼（608）联系电话：89733006（O）

取课件邮箱：pubcup@联系方式2主教材：数据结构（C语言版）严蔚敏，清华出版社辅助教材：数据结构（C语言版）陈明，清华出版教材与参考书3课程安排64学时：

理论课：48学时实践课：16学时第2,3,5,7,9,11,13周周五3、4节上机地点：三教403

4why?what?how?课程地位5Why---计算机专业基础课之一6

求1名学生10次C语言程序设计的测验成绩总分与平均分。其中10次成绩分别为：80，85，77，56，68，83，90，92，80，98.Why---软件开发中的重要作用main(){intsum,aver;intt1,t2,t3,t4,t5,t6,t7,t8,t9,t10;t1=80;t2=85;t3=77;t4=56;t5=68;t6=83;t7=90;t8=92;t9=80;t10=98;sum=t1+t2+t3+t4+t5+t6+t7+t8+t9+t10;aver=sum/10;printf(“总分=%d\n”,sum);printf(“平均分=%d”,aver);}采用数组结构存储，提高程序的使用范围。7例如：酒店客房分配问题要求计算机能够辅助解决酒店客人入住时的房间合理分配的问题；要求每间客房分配给客人入住的机会均等。具体问题8经过抽象：计算机通过管理与酒店客房有关的数据来合理分配客房客房数据：1、房间号码2、房间的状态（已分配、未分配）将空客房数据放在一起，排成一队得到数学模型9在计算机中存储表示可以采用高级程序设计语言中的一维数组来存放客房信息；空客房之间的关系通过在物理存储器的相邻性来体现；10保证客房能够机会均等的分配的处理方法：将空客房排成一个队列，每次只能从队头分配客房，客人结账离店时将客房回收，排到空客房队列的末尾。402517411234出租402517411234若再有客人入住，则分配51711517411234此时若402房间的客人离店，则将402房间放在空房间队列的队尾。517411234402这是一种常见的数据结构，它要求只能在队头作出队操作，在队尾作进队操作，具体实现方法会在后期课程中介绍给大家。12what---利用计算机解决问题的方法：

具体问题数学模型编写算法解决问题在计算机中存储（物理结构）1、数据(事物)2、数据间的关系（事物间的联系）将算法转换成程序抽象数据结构逻辑结构1.事物2.事物间的联系13NiklausWirth：

Programs=

DataStructures

+Algorithm程序设计：为计算机处理问题编制的一组指令集数据结构：问题的数学模型算法：处理问题的策略Why---软件开发中的重要作用14how?15how？16读算法模仿写自己写，找差距算法分析how？循序渐进，切忌心浮气躁提高课外学习的时间和内容理解科学而不是背诵科学→读书正确对待考试作习题

华罗庚：“学数学不做习题等于入宝山而空返”

作实验

计算机学科是一门科学性与工程性并重的学科，表现为理论和实践紧密结合的特征。

17考核方法考试课，满分100分。考核分平时成绩和期末考试两部分。平时成绩占30%：日常考核：10分，包括出勤情况和课堂提问

注：三次考勤未到，取消考试资格作业考核：10分实验考核：10分期末考试成绩占70%，闭卷笔试。18基础篇：基本概念（绪论）结构篇：基本的数据结构①线性结构：

线性表、栈和队列、串、数组和广义表②非线性结构：树、图技术篇：基本的数据处理技术①查找技术②排序技术课程主要内容与安排19绪论第一章基本术语数据结构的概念数据的逻辑结构数据的存储结构算法20基本术语数据（data）信息的载体，它是描述客观事物的数、字符以及所有能输入到计算机中，能被计算机程序识别、加工处理的信息的集合。DATA(计算机能接受和处理的符号集合)客观事物（信息）21基本术语数据元素：数据的基本单位，是对一个客观实体的数据描述学号姓名语文…物理000王明86…95001王志平73…92……………100李昕65…89数据元素数据项22基本术语数据对象：具有相同性质的数据元素的集合。酒店系统的全部数据数据元素客房数据员工数据客人数据数据对象23基本术语数据类型（datatype）：具有相同性质的计算机数据的集合及定义在这个集合上的一组操作的总称。如：两类数据类型：原子类型（其值不可分解，如：int,float.....）结构类型（其值可以分解，如结构体）如C/C++中的int就是整型数据类型。它是所有整数的集合(在16位计算机中为－32768~32767的全体整数)和相关的整数运算(如＋、－、＊、／等)。24基本术语——抽象数据类型（AbstractDataType,ADT）ADT：指一个数学模型以及定义在该模型上的一组操作。抽象数据类型=数据元素集合＋抽象运算ADT抽象数据类型名{

数据对象：（数据对象的定义）数据关系：（数据关系的定义）基本操作：（基本操作的定义）}ADT抽象数据类型名25例如,抽象数据类型复数的定义：ADTComplex{

D={e1,e2|e1,e2均为实数}R1={<e1,e2>|e1：实数部分,e2：虚数部分}AssignComplex(&Z,v1,v2)：构造复数ZDestroyComplex(&Z):复数Z被销毁

GetReal(Z,&real):返回复数Z的实部值

GetImag(Z,&Imag):返回复数Z的虚部值

Add(z1,z2,&sum):返回两个复数z1,z2的和}ADTComplexe1＋e2i26抽象数据类型名数据对象基本操作数据关系基本术语数据结构：

数据之间的相互关系及在这些数据上定义的数据运算方法的集合。数据之间关系：逻辑关系：也称为数据的逻辑结构存储结构：也就是物理结构数据的运算：对数据进行的操作27数据的逻辑结构1.集合：数据具有符合某一条件的相同的性质，且无其它关系。2.线性结构：数据元素之间存在一对一的关系。线性表、栈、队列、字符串、数组、广义表283.树型结构：数据之间存在一对多的关系。数据的逻辑结构4.网状结构：数据之间存在多对多的关系。非线性结构：树、图29数据的存储结构存储结构（物理结构）：数据的逻辑结构在计算机内的表示或实现，包括数据元素的表示和关系的表示。30通常有两种存储结构：1.

顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。…batcateat…起始地址例：（bat,cat,eat）31通常有两种存储结构：1.顺序存储结构：用一组连续的存储单元依次存储数据元素。例：（bat,cat,eat）0200020803000325…………bat0200cat0325eat∧322.链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。数据元素之间的逻辑关系由元素的存储位置来表示。存放学生表的结构体数组Stud定义为：

struct{ intno;/*存储学号*/ charname[8];/*存储姓名*/ charsex[2];/*存储性别*/ charclass[4];/*存储班号*/}Stud[7]={{1,“张斌”,“男”,“9901”},…,{5,"王萍","女","9901"}};33结构体数组Stud各元素在内存中顺序存放,即第i(1≤i≤6)个学生对应的元素Stud[i]存放在第i+1个学生对应的元素Stud[i+1]之前,Stud[i+1]正好在Stud[i]之后。9901女王萍5…9901男张斌1Stud[0]Stud[6]Stud数组起始地址34

存放学生表的链表的结点类型StudType定义为：

typedefstructstudnode{ intno; /*存储学号*/ charname[8]; /*存储姓名*/ charsex[2]; /*存储性别*/ charclass[4]; /*存储班号*/ structstudnode*next;/*存储指向下一个学生的指针*/}StudType；35链表首结点地址head1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901∧

学生表构成的链表如右图所示。其中的head为第一个数据元素的指针。学生表构成的链表36顺序存储方法定义：逻辑上相邻的结点存储在物理位置上也相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来表示特点：结点中只有自身信息域，没有连接信息域,存储密度大，存储空间利用率高通过计算直接确定数据结构的中的第i个结点的存储地址Li，Li=L0+（i-1）*m,其中L0为第一个结点的存储位置，m为每个结点所占用的存储单元个数。插入和删除都会引起大量的结点移动37链式存储方法定义：链式存储方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的关系由附加的指针来表示，指针指向结点的邻接结点

结点特点：存储结构的存储密度小，存储空间利用率低。逻辑上相邻的结点，物理上不必邻接删除和插入操作灵活方便，不必移动结点，只要改变结点中的指针值数据域：存储结点本身的值指针域：后继结点的存储单元地址38索引存储方法建立一个附加的索引表，利用索引表中索引想的值确定时间存储单位地址。

散列存储方法根据结点的关键字值，通过散列函数H（key）直接计算出结点的存储地址。39数据的运算查找插入删除修改排序40数据结构的基本概念（小结）数据的操作：插入、删除、修改、检索、排序等数据的逻辑结构

数据的存储结构

顺序存储链式存储集合线性结构树结构图结构数据表示41数据结构的研究对象计算机求解问题:

问题→抽象出问题的模型→求模型的解问题——数值问题、非数值问题

数值问题→数学方程非数值问题→数据结构42学籍管理问题——表结构学号姓名性别出生日期政治面貌0001王军男1983/09/02团员0002李明男1982/12/25党员0003汤晓影女1984/03/26团员……………数据结构的研究对象43例:人机对弈问题——树结构数据结构的研究对象如何实现对弈?各格局之间是什么关系？…………..……..………...……44例:教学计划编排问题——图结构C4,C5,C6数据库原理C7C2,

C4计算机原理C6C3,C4数据结构C5C1,C2程序设计C4C1离散数学C3无计算机导论C2无高等数学C1先修课课程名称编号数据结构的研究对象C1C2C3C4C6C5C7如何表示课程之间的先修关系？45

多叉路口交通灯的管理——图结构数据结构的研究对象设计几种颜色的交通灯既能使车辆不碰撞，又能达到最大车流量？46数据结构是研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科。数据结构的研究对象47

数据结构形式定义：数据结构在形式上可以定义为一个二元组：

Data_Stru