数据结构(5顺序表类).ppt

C/C+与数据结构,郭 鹏 城市与环境科学学院,1,5. 顺序表类,C+预备知识 发展由来 输入输出 内联函数、缺省函数 函数重载、运算符重载 引用型、布尔型 C基本顺序表到C+顺序表类,2,5. 顺序表类,C+发展由来 C 丹尼斯里奇&肯汤普逊 贝尔实验室（1973） B语言（汤普逊） C语言（里奇） C+ Bjarne Stroustrup博士(比杨尼斯卓司朱夫) C with class 从Simula继承了类的概念， 从Algol68继承了运算符重载、引用以及在任何地方 声明变量的能力， 从BCPL获得了/注释， 从Ada得到了模板、名字空间 从Ada、Clu和ML取来了异常,3,1983年两人获得了图灵奖,5. 顺序表类,C+与C的不同 C+是在扩充了C面向过程的基础上增加了面向对象的功能 面向过程（C） 不需要了解计算机内部逻辑，只是关注算法逻辑和过程描述，通过程序把解决问题的执行步骤告诉计算机 机器语言-汇编语言-过程语言(以C为代表) 面向对象(C+) 一种认识世界的方法，也是一种程序设计思想 客观世界由对象组成，每种对象有其内部状态和规律，不同对象联系和作用构成了不同的系统，进而构成客观世界 抽象、封装、继承和多态,4,5. 顺序表类,人们能解决的问题的复杂性直接与抽象的类型和质量有关。 类型：要抽象的东西 汇编语言：对底层机器的小幅度抽象，命令式语言(fortran,C)是对汇编的抽象编写和维护费用高 面向对象的方法为程序员提供了在问题空间中表示各种事物元素的工具。问题空间中的事物和它们在解空间中的表示称为对象。 纯面向对象程序设计的基本特征 万物皆对象 程序就是一组对象，对象之间通过发送消息互相通知做什么 每一个对象都有它自己的由其它对象构成的存储区 每个对象都有一个类型 一个特定类型的所有对象都能接受相同的信息,5,5. 顺序表类,输入输出流 cin; cout /键盘输入，显示器输出（printf，scanf） cin.get();cout.put()/字符输入输出（getchar,putchar） cin.getline(para1,para2,para3)/字符串输入(gets) 输入（para2-1）个字符 para3，输入的终止字符 cout.write(para1,para2)/输出（puts） para1:输出字符来源； para2: 输出字符个数 #include void main () char m20; cin.getline(m,5);/, C); coutmendl; ,6,/“ABCFDG”,/ABCF,/AB,5. 顺序表类,内联函数 使用函数的优点 便于阅读、便于修改、可重用并隐藏细节 缺点 消耗栈内存,降低系统速度 在c+中，为了解决一些频繁调用的小函数大量消耗栈空间（栈内存）的问题，特别的引入了inline修饰符，表示为内联函数 栈空间就是指放置程序的局部数据也就是函数内数据的内存空间，在系统下，栈空间是有限的，如果频繁大量的使用就会造成因栈空间不足所造成的程序出错的问题，函数的死循环递归调用的最终结果就是导致栈内存空间枯竭,7,5. 顺序表类,内联函数实例 inline int Judge(int i); /函数原形声明为inline即:内联函数 void main() for(int i=1;i0?)1:0); ,8,(i %20?)1:0) /直接替换,5. 顺序表类,内联函数 内联函数和宏很类似，只是在需要用到的时候，内联函数像宏一样的展开，所以取消了函数的参数压栈，避免了频繁调用函数对栈内存重复开辟所带来的消耗，减少了调用的开销。 既然这么好？是不是都可以把函数都声明为Inline?,9,5. 顺序表类,内联函数的局限 只适合函数体内代码简单的函数使用 不能包含循环、条件、选择等复杂的结构控制语句，例如while/switch/for 必须在声明函数的代码文件中进行函数定义 真相-Truth 即便你没有指定函数为内联函数，有的编译系统也会自动将很简单的函数作为内联函数处理；而对于复杂的函数，即便你指定他为内联函数，系统也不会理会的 Inline只是请求！编译器负责实现！,10,5. 顺序表类,内联函数与宏定义的区别 宏定义#define:简单的字符串替换，不考虑参数类型 宏的参数替换是不经计算而直接处理的,而函数调用是将实参的值传递给形参 宏在编译之前进行,即先用宏体替换宏名,然后再编译的,而函数是编译之后,在执行时,才调用的.因此,宏占用的是编译的时间,而函数占用的是执行时的时间 C+中基本不会使用#define,而是用const取代 #define只是简单替换 const会进行类型检查,11,5. 顺序表类,默认函数 指带有默认参数的函数 默认参数：在函数声明时就带有一个默认值，当调用该函数时，如果不给出相应的实参，则编译器将默认值赋给这个参数 主要用于默认构造函数,12,带有默认值的形参必须从参数列表最右边开始 连续不断列出 void func(int x=0,int y,int z=0) 【】 如果函数由声明和定义两部分，默认值只能出现在函数声明中,5. 顺序表类,函数重载 三个结构中的求长基本操作 Int ListSize(const SeqList * l)/基本顺序表 Int QSize(const Queue * q)/基本顺序队列 Int StSize(const Stack * s)/基本顺序栈 如果更多结构？WhatSize？,13,int Size(),5. 顺序表类,Size函数重载 Int Size(const SeqList * l)/基本顺序表 Int Size(const Queue * q)/基本顺序队列 Int Size(const Stack * s)/基本顺序栈 函数表名和函数有一处不同，就表示函数不同 因为函数参数表的不同，构成了函数重载 注意： 如果只有返回值不同，则不能重载 如果两个函数的参数个数相同且类型可隐式转换，尽量不要重载，因为会容易出现二义性 void display(char a); void display(double a); Display(10)/出现二义性,14,5. 顺序表类,函数重载 #include void display(char); void display(int);/注意匹配提升 void display(char,char); void main() display(65); display(A); display(A,B); ,15,void display(char ch) coutchendl; void display(int n) coutnendl; void display(char ch1, char ch2) coutch1tch2endl; ,5. 顺序表类,结构的比较是非法语句p209 struct studentlong ID；double g; int find(const SeqList *L，Type item) For(int i=0;i size; i+) if(L-datai=item) /非法语句 return i; return (-1) 如果想用“=”来比较，应该如何做呢？,16,error C2676: binary = : const struct student does not define this operator,5. 顺序表类,运算符重载 运算符重载就是赋予已有的运算符多重含义。C+中通过重新定义运算符，使它能够用于特定类的对象执行特定的功能，这便增强了C+语言的扩充能力。 把运算符看做是函数，函数名为operator,为运算符 int operator=(student a,student b) return(a.ID=b.ID); 重载后：优先级不变；结合律不变；操作数个数不变；语法结构不变,17,5. 顺序表类,运算符重载 好处是什么?面向问题，而不是面向机器或具体数据结构。 不允许重载的运算符 “ ”，“ * ”， “ : ” , “?:” 限制 不可臆造新的运算符 坚持4个“不能改变” 不能改变运算符操作数的个数 不能改变运算符原有的优先级 不能改变运算符原有的结合性 不能改变运算符原有的语法结构,18,原则： (1) 重载运算符含义必须清楚。 (2) 重载运算符不能有二义性。,应有一个参量是用户自定义类型，不能全部是语言固有的类型,5. 顺序表类,运算符重载 提供了C+的可扩展性，是C+最引人的属性之一 在完成同样的操作的情况下，如果运算符重载能够比用明确的函数调用使程序更清晰，则应该使用运算符重载 不能过度或不合理地使用运算符重载，因为这样会使程序语义不清楚且难以阅读 用于类的对象的运算符必须重载（赋值运算符=和地址运算符&除外） 运算符重载最适合数学类，如复数类。,19,5.顺序表类,函数调用 值调用-费时费空间 地址调用（但属于指针，是语言固有类型） 引用型 引用（reference）是一个空间的别名，即一个空间的另一个名称。（ :-D 好像绰号一样？） 定义格式 类型标识符 引用必须初始化；不能声明引用数组,20,5. 顺序表类,引用参数 传统上C中是通过值和地址进行参数传递 C+更多使用引用调用 引用调用 Int operator=(Student 形参是实参的引用，即为引用调用 如果不改变参数值，则设为常量型引用 Int operator=(const Student &a, const Student &b),21,5. 顺序表类,课件实例 引用实质（const常量指针） 常量型引用调用和值调用 以结构为参量的值的调用函数，一般都改为常量型引用调用 引用调用和函数返回值（可不构建临时变量） 带有返回值的函数可以优化为引用调用 引用与函数返回值类型 对常量的引用必须是常量型引用 函数返回值不能是自变量的引用,22,5. 顺序表类,引用与指针的区别 引用就是别名（绰号），主要功能在于传递函数的参数和返回值 int m; int 不能有NULL引用，但可以有NULL指针 int *p = NULL 一旦引用被初始化，就不能改变引用的关系，指针则可以随时改变所指的对象,23,对n的任何操作就是对m的操作，n既不是m的拷贝,也不是指向m的指针，其实n就是m自己,void Func ( int *A ) int B = 9; A = ,void Func ( int ,Int C = 10; Func(,Int C = 10; Func(C);,5. 顺序表类,C+中的三种函数调用 值传递 指针传递 引用传递,24,void Func1 ( int A ) A += 10; ,Int n = 0; Func1(n); Cout n;,void Func1 ( int *A ) （*A） += 10; ,Int n = 0; Func1(,void Func1 ( int ,Int n = 0; Func1(n); Cout n;,“引用传递” 的性质象“指针传递”，而书写象“值传递”,实质：引用可以做的事情指针都可以去做。 目的：“用适当的工具做恰如其分的工作” 指针可以毫无约束地操做内存中的任何东西，因此虽然功能强大，但比较危险。 建议：如果只需要借用别名，则用引用，而不用指针。,5. 顺序表类,布尔型（bool） 只占一个字节,仅取两个值true/false，对应的整型值为1和0 避免其他数据类型与布尔型的比较运算 如果函数仅取真假值，则返回值类型应为布尔型 bool Empty(const SeqList * l) bool operator =(const Student &, const Student &),25,5. 顺序表类,C顺序表-C+顺序表类 Excellent Language != Excellent Code Excellent Programmer = Excellent Code 代码组织 构造函数 基本操作函数声明 功能函数定义 C语言编译器没有区分以上函数，声明、定义、调用方式相同 C+则从概念和语法上把上述3类函数进行区分,26,5. 顺序表类,C基本顺序表的C+改造 bool类型定义-返回值为真/假的函数值定义为bool类型 宏常量改为const常量 #define MaxSize 100 const int MaxSize = 100 形参值调用 常量型引用调用 InsertRear(SeqList * L, Type item) InsertRear(SeqList * L, const Type& item) 形式数据类型函数 常量型引用 Type GetData(const SeqList *L, int id) Const Type& GetData(const SeqList *L, int id) 函数重载 Size()/Empty()/Full(),27,5. 顺序表类,C基本顺序表的C+改造 成员函数声明(结构的指针改为this指针) void SetList(SeqList * this) /初始化 int Size(const SeqList * this)/求长 bool Empty(const SeqList *) /判断空 const Type& GetData(const SeqList *this, int id)/取值 void InsertRear(SeqList * this, const Type& item)/尾插 void Delete(SeqList * this, int id) /删除 void Error(const SeqList * this, const char *c) /错误信息报告，哑元 隐藏this指针，const修饰符移位，函数声明放入结构体内 - 成员函数,28,5. 顺