1、 数据结构讨论的范畴数据结构讨论的范畴:非数值计算程序设计问题非数值计算程序设计问题数据结构数据结构是一门讨论是一门讨论“描述现描述现实世界实体的数学模型实世界实体的数学模型(非数值计非数值计算算)及其上的操作在计算机中如何及其上的操作在计算机中如何表示和实现表示和实现”的学科。的学科。数据结构课数据结构课程程介绍和研究数据在计算机中的存介绍和研究数据在计算机中的存储和处理的方法。储和处理的方法。1.1 常用术语常用术语人们利用文字符号人们利用文字符号,数字符号数字符号以及其他规定的符号对现实世以及其他规定的符号对现实世界的事物及其活动所做的抽象界的事物及其活动所做的抽象描述描述.是能够被计算
2、机输入，存储，是能够被计算机输入，存储，处理和输出的信息。处理和输出的信息。简称简称,它是一个数据整体中它是一个数据整体中相对独立的单位相对独立的单位.即即:数据（集合）中的一个数据（集合）中的一个“个个体体”是数据结构中讨论的基本单位是数据结构中讨论的基本单位简称简称,它是数据处理领域组它是数据处理领域组织数据的基本单位。织数据的基本单位。是指数据及其相互之间的是指数据及其相互之间的联系联系或者说，数据结构是相互或者说，数据结构是相互之间存在着某种之间存在着某种的数的数据元素的集合。据元素的集合。数据之间的相互联系，被称为数据之间的相互联系，被称为数据的数据的，一种数据结构在一种数据结构在存
3、储器中的存储方式称为数据的存储器中的存储方式称为数据的（。用用一组一组地址连续的存储单元地址连续的存储单元依次存储数据元素依次存储数据元素 x 以附加信息以附加信息(指针指针)表示后继表示后继关系需要用一个和关系需要用一个和 x x 在一起的在一起的附加信息附加信息指示指示 y y 的存储位置。的存储位置。例例 画出二元组画出二元组 (K，R)的图形表示的图形表示 其中其中K=01,02,03,04,05,06,07,08,09,10R=,01040602050703080910是对数据的取值范围、每一是对数据的取值范围、每一数据的结构以及允许施加操作的数据的结构以及允许施加操作的一种描述。可
4、分为简单类型和结一种描述。可分为简单类型和结构类型两种构类型两种.一一维维数组数组 an:元素元素 ai的存储位置为：的存储位置为：Address(ai)=a+i*L（0in-1）二维数组二维数组 bmn:行元素行元素 bi的的存储位置存储位置为：为：Address(bi)=b+i*n*L (0im-1)元素元素 bij的存储位置为：的存储位置为：Address(bij)=b+i*n*L+j*L (0im-1,0jn-1)其中其中L表示数组中元素类型的大小表示数组中元素类型的大小抽象数据类型抽象数据类型(Abstract Data Type 简称简称 ADT)由一组由一组和在该组数和在该组数据
5、结构上的一组据结构上的一组所组成。所组成。也可以被定义为由一组数据和也可以被定义为由一组数据和在该数据上的一组操作所组成。在该数据上的一组操作所组成。本课程中，为了便于叙述和本课程中，为了便于叙述和分析数据结构与算法，在实现分析数据结构与算法，在实现所定义的抽象数据类型时，把所定义的抽象数据类型时，把数据部分用数据部分用 结构类型来结构类型来描述，把操作部分中的每个操描述，把操作部分中的每个操作用外部函数（即普通函数）作用外部函数（即普通函数）来描述。来描述。注：注：ADT RECtangle is Data:float length,width；Operations:void InitRec
6、tangle(Rectangle&r,float len,float wid);float Circumference(Rectangle&r);float Area(Rectangle&r);end RECtangle对于矩形定义一种抽象数据类型，其数据部分对于矩形定义一种抽象数据类型，其数据部分包括矩形的长度和宽度，操作部分包括初始化矩形包括矩形的长度和宽度，操作部分包括初始化矩形的尺寸，求矩形的周长和求矩形的面积。的尺寸，求矩形的周长和求矩形的面积。struct Rectangle float length,width;void Initrectangle(Rectangle&r,flo
7、at len,float wid)r.length=len;r.width=wid;/初始化矩形数据函数初始化矩形数据函数float Circumference (Rectangle&r)returm 2*(r.length+r.Width);/求矩形周长函数求矩形周长函数float Area (Rectangle&r)return r.length*r.width;/求矩形面积函数求矩形面积函数1.#include v标准输入设备（键盘）流对象标准输入设备（键盘）流对象 cin;v标准输出设备（屏幕）流对象标准输出设备（屏幕）流对象 cout;v标准错误输出设备（屏幕）流对象标准错误输出设备
8、（屏幕）流对象 cerr;v用于输入的提取操作符用于输入的提取操作符;v用于输出的插入操作符用于输出的插入操作符;对于用户定义类型的数据对于用户定义类型的数据（记录记录），只有，只有通过对通过对和和(istream&istr,struct_type&x)istr x.成员成员1 x.成员成员2 x.成员成员n;return istr;ostream&operater (ostream&istr,struct_type&x)ostr x.成员成员1“”x.成员成员2“”x.成员成员n endl;return ostr;cin x1cout x12.#include void exit(int)；
9、int rand(void)；void srand(unsigned)；3.#include 输入文件流类输入文件流类 ifstream；输出文件流类输出文件流类 ofstream；输入输出文件流类输入输出文件流类 fstream。例如：例如：ifstream input 1(“a1.dat”,ios:in ios:nocreate)；4.#include int strlen(const char*s);/求串长度求串长度 char*strcpy(char*dest,const char*src);/串拷贝串拷贝 char*strcat(char*dest,const char*src);/
10、串连接串连接 int strcmp(const char*s1,const char*s2);/串比较串比较 char*strchr(const char*s,int c);/串定位串定位 char*strchr(const char*s,int c);/串右定位串右定位 char*strstr(const char*s1,const char*s2);/查找子串查找子串ofstream input 2(“a2.dat”,ios:out)；ofstream input 3(“a3.dat”,ios:app)；fstream input 4(“a4.dat”,ios:in ios:out)；例：
11、不同返回类型的三个重载函数例：不同返回类型的三个重载函数引用参数与值参数：引用参数与值参数：值参数：值参数：具有自己的存储空间具有自己的存储空间，内容的改，内容的改变不会影响到对应的实在参数。变不会影响到对应的实在参数。引用参数：引用参数：和实在变量参数具有同一存储和实在变量参数具有同一存储位置位置，对引用参数的读写操作实际上就是对，对引用参数的读写操作实际上就是对相应实参变量的读写操作，对引用参数的改相应实参变量的读写操作，对引用参数的改变将反映给对应的实参变量。变将反映给对应的实参变量。例：例：void swap1(int a,int b)int t;t=a;a=b;b=t;void sw
12、ap2(int&a,int&b)int t;t=a;a=b;b=t;设设x,y是两个整数变量，那么调用函数是两个整数变量，那么调用函数swap1(x,y)将不改变将不改变x,y的值，而调用函数的值，而调用函数swap2(x,y)将交换将交换x,y的数值。的数值。1.23 运算符重载运算符重载 对于自定义的结构类型，需要对关对于自定义的结构类型，需要对关系运算符进行重载，使得记录同记录系运算符进行重载，使得记录同记录之间、记录同其中一个域类型的数据之间、记录同其中一个域类型的数据之间也能够进行比较。之间也能够进行比较。如下例所示：如下例所示：struct pupil char pnum 8;in
13、t grade;boolbool operator=(operator=(pupil&r1,pupil&pupil&r1,pupil&r2r2)ifif(strcmpstrcmp(r1.(r1.pnumpnum,r2.,r2.pnumpnum)=)=0)=0)return return true;true;elseelse return return false;false;boolbool operator=(pupil&r,char operator=(pupil&r,char*key key)ifif(strcmpstrcmp(r.(r.pnumpnum,r2.key)=0),r2.ke
14、y)=0)return return true;true;elseelse return return false;false;boolbool operator operator(pupil&(pupil&r1,r1,pupil&r2pupil&r2)return r1.return r1.grade r2grade r2.grade;.grade;boolbool operator(pupil&operator(pupil&r,r,intint key key)return r.grade return r.grade key key;f(n)=O(g(n)例：例：int Sum(int
15、b,int n)int s=0;for(int i=0;in;i+)s+=bi;算法算法2:(:(矩阵相加）矩阵相加）void MatrixAdd(int aMSMS,int bMSMS,int cMSMS,int n)int i,j;for(int i=0;in;i+)for(j=0;jn;j+)cij=aij+bij;Void SelectSort(int b,int n)int i,j,k,x;for(int i=0;in-1;i+)k=i;for(j=i+1;j n;j+)if(bi bk)k=j;x=bi;bi=bk;bk=x;如：如：某程序的时间复杂度为：某程序的时间复杂度为：10
16、log2n+nlog2n+100则数量级表示为则数量级表示为 O(nlog2n)O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!)时间复杂度的各种不同数量时间复杂度的各种不同数量级对应的值存在如下关系：级对应的值存在如下关系：int SequenceSearch(int a ,int n,int key)for(int i=0;in;i+)if (ai=key)return i;return -1;算法的最好、最差和平均时间算法的最好、最差和平均时间复杂度的复杂度的计算。计算。例：例：最好时间复杂度为最好时间复杂度为O(1)最坏时间复杂度为最坏时间复杂度为O(1)平均时间复杂度为平均时间复杂度为O(n)是对一个算法在运行过程中临是对一个算法在运行过程中临时占用存储空间大小的量度。时占用存储空间大小的量度。即：即：算法在运行过程中为局部算法在运行过程中为局部变量分配的存储空间的大小变量分配的存储空间的大小，包括，包括为参数表中形参变量分配的存储空为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量间和为在函数体中定义的局部变量分配的存储空间两个部分。分配的存储空间两个部分。
