数据结构课程说明教材：«数据结构»(C语言版)严蔚敏等编著,清华大学出版社参考书：《数据结构》算法实现及解析高一凡编著西安电子科技大学出版社«数据结构»(用面向对象方法与C++描述)殷人昆等编著,清华大学出版社«数据结构与程序设计»(C++语言描述)，高等教育出版社课时：64考试方式：考试成绩计算：平时*30%+考试*60%什么是数据结构基本概念和术语抽象数据类型算法分析性能分析与度量一、什么是数据结构“学生”表格“课程”表格“选课单”包含如下信息学号课程编号成绩时间学生选课系统中实体构成的网状关系UNIX文件系统结构图2、实现计算机程序通常需经过哪些步骤？数学模型二、基本概念和术语2、数据元素（DataElement）数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(DataItem)组成。数据项是具有独立含义的最小标识单位。数据元素又称为元素、结点、记录3、数据对象(dataobject)具有相同性质的数据元素的集合。整数数据对象N={0,1,2,…}字母字符数据对象C={‘A’,‘B’,‘C’,…‘F’}4、数据结构（DataStructure）形式定义：某一数据对象的所有数据成员之间的关系。记为：Data_Structure={D,S}其中，D是某一数据对象，S是该对象中所有数据成员之间的关系的有限集合。四个基本结构集合线性结构树形结构网状结构5、数据的逻辑结构6、数据的逻辑结构分类bin堆结构7、数据的存储结构三、抽象数据类型（ADT：AbstractDataType）2、抽象数据类型抽象数据类型3、抽象数据类型的描述其中,数据对象、数据关系用伪码描述；基本操作定义格式为基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。4、抽象数据类型的表示和实现ADTNaturalNumberisobjects:一个整数的有序子集合,它开始于0,结束于机器能表示的最大整数(MaxInt)。Function:对于所有的x,yNaturalNumber;False,TrueBoolean,+、-、<、==、=等都是可用的服务。Zero():NaturalNumber返回自然数0IsZero(x):if(x==0)返回TrueBooleanelse返回FalseAdd(x,y):if(x+y<=MaxInt)返回x+yNaturalNumberelse返回MaxIntSubtract(x,y):if(x<y)返回0NaturalNumberelse返回x-yEqual(x,y):if(x==y)返回TrueBooleanelse返回FalseSuccessor(x):if(x==MaxInt)返回xNaturalNumberelse返回x+1endNaturalNumber四、算法分析3、算法设计要求4、应用举例voidselectSort(inta[],intn){//对n个整数a[0],a[1],…,a[n-1]按递增顺序排序for(inti=0;i<n-1;i++)for(intj=i+1;j<n;j++)if(a[j]<a[j]){//从a[i]查到a[n-1],找最小整数,在a[k]inttemp=a[i];a[i]=a[j];a[j]=temp;}}5、算法的性能标准算法的效率主要体现在应用该算法编制的程序在计算机上的执行时间。度量一个程序的执行时间通常有两种方法：后期测试和事前估算。（1）、后期测试在算法中的某些部位插装时间函数time(),测定算法完成某一功能所花费时间doublestart,stop;time(&start);intk=seqsearch(a,n,x);time(&stop);doublerunTime=stop-start;printf(”%d%d\n",n,runTime);intseqsearch(inta[],intn,intx){//在a[0],…,a[n-1]中搜索xinti=0;while(i<n&&a[i]!=x)i++;if(i==n)return-1;returni;}缺点：必须编制两个程序来测试两种算法，花费较多的时间和精力；