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

《数据结构(5顺序表类).ppt》由会员分享，可在线阅读，更多相关《数据结构(5顺序表类).ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、C/C+C/C+与数据结构与数据结构郭郭 鹏鹏城市与环境科学学院城市与环境科学学院15.顺序表类顺序表类C+预备知识发展由来输入输出内联函数、缺省函数函数重载、运算符重载引用型、布尔型C基本顺序表到C+顺序表类25.顺序表类顺序表类C+发展由来C丹尼斯里奇&肯汤普逊贝尔实验室（1973）B语言（汤普逊）C语言（里奇）C+Bjarne Stroustrup博士博士(比杨尼比杨尼斯卓司朱夫斯卓司朱夫)Cwithclass从Simula继承了类的概念，从Algol68继承了运算符重载、引用以及在任何地方声明变量的能力，从BCPL获得了/注释，从Ada得到了模板、名字空间从Ada、Clu和ML取来了异

2、常31983年两人获得了图灵奖年两人获得了图灵奖5.顺序表类顺序表类C+与C的不同C+是在扩充了C面向过程的基础上增加了面向对象的功能面向过程（C）不需要了解计算机内部逻辑，只是关注算法逻辑和过程描述，通过程序把解决问题的执行步骤告诉计算机机器语言-汇编语言-过程语言(以C为代表)面向对象(C+)一种认识世界的方法，也是一种程序设计思想客观世界由对象组成，每种对象有其内部状态和规律，不同对象联系和作用构成了不同的系统，进而构成客观世界抽象、封装、继承和多态45.顺序表类顺序表类人们能解决的问题的复杂性直接与抽象的类型和质量有关。类型：要抽象的东西汇编语言：对底层机器的小幅度抽象，命令式语言(f

3、ortran,C)是对汇编的抽象编写和维护费用高面向对象的方法为程序员提供了在问题空间中表示各种事物元素的工具。问题空间中的事物和它们在解空间中的表示称为对象。纯面向对象程序设计的基本特征万物皆对象程序就是一组对象，对象之间通过发送消息互相通知做什么每一个对象都有它自己的由其它对象构成的存储区每个对象都有一个类型一个特定类型的所有对象都能接受相同的信息55.顺序表类顺序表类输入输出流cin;cout/键盘输入，显示器输出（printf，scanf）cin.get();cout.put()/字符输入输出（getchar,putchar）cin.getline(para1,para2,para3)

4、/字符串输入(gets)输入（para2-1）个字符para3，输入的终止字符cout.write(para1,para2)/输出（puts）para1:输出字符来源；para2:输出字符个数#includevoidmain()charm20;cin.getline(m,5);/,C);coutmendl;6/“ABCFDG”/ABCF/AB5.顺序表类顺序表类内联函数使用函数的优点便于阅读、便于修改、可重用并隐藏细节缺点消耗栈内存,降低系统速度在c+中，为了解决一些频繁调用的小小函数大量消耗栈空间（栈内存）的问题，特别的引入了inline修饰符，表示为内联函数栈空间就是指放置程序的局部数据也

5、就是函数内数据的内存空间，在系统下，栈空间是有限的有限的，如果频繁大量的使用就会造成因栈空间不足所造成的程序出错的问题，函数的死循环递归调用的最终结果就是导致栈内存空间枯竭75.顺序表类顺序表类内联函数实例inlineintJudge(inti);/函数原形声明为inline即:内联函数voidmain()for(inti=1;i10;i+)couti“:”Judge(i)0?)1:0);8(i%20?)1:0)/直接替换直接替换5.顺序表类顺序表类内联函数内联函数和宏很类似，只是在需要用到的时候，内联函数像宏一样的展开，所以取消了函数的参数压栈，避免了频繁调用函数对栈内存重复开辟所带来的消耗

6、，减少了调用的开销。既然这么好？是不是都可以把函数都声明为Inline?95.顺序表类顺序表类内联函数的局限只适合函数体内代码简单的函数使用不能包含循环、条件、选择等复杂的结构控制语句，例如while/switch/for必须在声明函数的代码文件中进行函数定义真相-Truth即便你没有指定函数为内联函数，有的编译系统也会自动将很简单的函数作为内联函数处理；而对于复杂的函数，即便你指定他为内联函数，系统也不会理会的Inline只是请求请求！编译器负责实现！105.顺序表类顺序表类内联函数与宏定义的区别宏定义#define:简单的字符串替换，不考虑参数类型宏的参数替换是不经计算而直接处理的,而函数

7、调用是将实参的值传递给形参宏在编译之前进行,即先用宏体替换宏名,然后再编译的,而函数是编译之后,在执行时,才调用的.因此,宏占用的是编译的时间,而函数占用的是执行时的时间C+中基本不会使用#define,而是用const取代#define只是简单替换const会进行类型检查115.顺序表类顺序表类默认函数指带有默认参数的函数默认参数：在函数声明时就带有一个默认值，当调用该函数时，如果不给出相应的实参，则编译器将默认值赋给这个参数主要用于默认构造函数12u带有默认值的形参必须从参数列表最右边开始带有默认值的形参必须从参数列表最右边开始 连续不断列出连续不断列出void func(int x=0,

8、int y,int z=0)void func(int x=0,int y,int z=0)【】u如果函数由声明和定义两部分，默认值只能出如果函数由声明和定义两部分，默认值只能出现在函数声明中现在函数声明中5.顺序表类顺序表类函数重载三个结构中的求长基本操作Int ListSize(const SeqList*l)/基本顺序表Int QSize(const Queue*q)/基本顺序队列Int StSize(const Stack*s)/基本顺序栈如果更多结构？WhatSize？13int Size()5.顺序表类顺序表类Size函数重载Int Size(const SeqList*l)/基本

9、顺序表Int Size(const Queue*q)/基本顺序队列Int Size(const Stack*s)/基本顺序栈函数表名和函数有一处不同，就表示函数不同因为函数参数表的不同，构成了函数重载注意：如果只有返回值不同，则不能重载如果两个函数的参数个数相同且类型可隐式转换，尽量不要重载，因为会容易出现二义性void display(char a);void display(double a);Display(10)/出现二义性145.顺序表类顺序表类函数重载#includevoid display(char);void display(int);/注意匹配提升void display(c

10、har,char);void main()display(65);display(A);display(A,B);15void display(char ch)coutchendl;void display(int n)coutnendl;void display(char ch1,char ch2)coutch1tch2endl;5.顺序表类顺序表类结构的比较是非法语句p209struct studentlong ID；double g;int find(const SeqList*L，Type item)For(int i=0;i size;i+)if(L-datai=item)/非法语句

11、return i;return(-1)如果想用“=”来比较，应该如何做呢？16error C2676:binary=:const struct student does not define this operator5.顺序表类顺序表类运算符重载运算符重载就是赋予已有的运算符多重含义。C+中通过重新定义运算符，使它能够用于特定类的对象执行特定的功能，这便增强了C+语言的扩充能力。把运算符看做是函数，函数名为operator,为运算符int operator=(student a,student b)return(a.ID=b.ID);重载后：优先级不变；结合律不变；操作数个数不变；语法结构不

12、变 175.顺序表类顺序表类运算符重载好处是什么?面向问题，而不是面向机器或具体数据结构。不允许重载的运算符“”，“*”，“:”,“?:”限制不可臆造新的运算符坚持4个“不能改变”不能改变运算符操作数的个数不能改变运算符原有的优先级不能改变运算符原有的结合性不能改变运算符原有的语法结构18原则：原则：(1)重载运算符含义必须清楚。重载运算符含义必须清楚。(2)重载运算符不能有二义性。重载运算符不能有二义性。应有一个参量是用户应有一个参量是用户自定义类型，不能全自定义类型，不能全部是语言固有的类型部是语言固有的类型5.顺序表类顺序表类运算符重载提供了C+的可扩展性，是C+最引人的属性之一在完成同

13、样的操作的情况下，如果运算符重载能够比用明确的函数调用使程序更清晰，则应该使用运算符重载不能过度或不合理地使用运算符重载，因为这样会使程序语义不清楚且难以阅读用于类的对象的运算符必须重载（赋值运算符=和地址运算符&除外）运算符重载最适合数学类，如复数类。195.顺序表类顺序表类函数调用值调用-费时费空间地址调用（但属于指针，是语言固有类型）引用型引用（reference）是一个空间的别名，即一个空间的另一个名称。（:-D好像绰号一样？）定义格式类型标识符&引用=被引用的变量Int x=5;Int&y=x;引用必须初始化；不能声明引用数组205.顺序表类顺序表类引用参数传统上C中是通过值和地址进

14、行参数传递C+更多使用引用调用引用调用Intoperator=(Student&a,Student&b);形参是实参的引用，即为引用调用如果不改变参数值，则设为常量型引用Intoperator=(constStudent&a,constStudent&b)215.顺序表类顺序表类课件实例引用实质（const常量指针）常量型引用调用和值调用以结构为参量的值的调用函数，一般都改为常量型引用调用引用调用和函数返回值（可不构建临时变量）带有返回值的函数可以优化为引用调用引用与函数返回值类型对常量的引用必须是常量型引用函数返回值不能是自变量的引用225.顺序表类顺序表类引用与指针的区别引用就是别名（绰号

15、），主要功能在于传递函数的参数和返回值int m;int&n=m引用被创建时候必须初始化，指针可以随时进行初始化int*p;不能有NULL引用，但可以有NULL指针 int*p=NULL一旦引用被初始化，就不能改变引用的关系，指针则可以随时改变所指的对象23对对n的任何操作就是对的任何操作就是对m的操作，的操作，n既不是既不是m的拷贝的拷贝,也不是指向也不是指向m的指针，其实的指针，其实n就是就是m自己自己void Func(int *A)int B=9;A=&B;void Func(int&A)int B=9;A=B;Int C=10;Func(&C);Int C=10;Func(C);5.

16、顺序表类顺序表类C+中的三种函数调用值传递指针传递引用传递24void Func1(int A)A +=10;Int n=0;Func1(n);Cout n;void Func1(int *A)（*A）+=10;Int n=0;Func1(&n);Cout n;void Func1(int&A)A +=10;Int n=0;Func1(n);Cout C+顺序表类Excellent Language!=Excellent CodeExcellent Programmer=Excellent Code 代码组织构造函数基本操作函数声明功能函数定义C语言编译器没有区分以上函数，声明、定义、调用方式

17、相同C+则从概念和语法上把上述3类函数进行区分265.顺序表类顺序表类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 i

18、d)函数重载Size()/Empty()/Full()275.顺序表类顺序表类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 Er

19、ror(const SeqList*this,const char*c)/错误信息报告，哑元隐藏this指针，const修饰符移位，函数声明放入结构体内 -成员函数285.顺序表类顺序表类C基本顺序表的C+改造const int MaxSize=100;struct SeqListType DataMaxSize;int size;void SetList(void);/构造函数int Size(void)const;/常量型成员函数bool Empty(void)const;void InsertRear(const Type&item);const Type&GetData(int id)

20、const;void Erase(int id);void Error(const char*c);295.顺序表类顺序表类C基本顺序表的C+改造调用方式的改变Erase（&L,2）=L.Erase(2)/L为表结构变量Erase（L,2）=L-Erase(2)/L为表结构指针成员函数定义可定义在结构体内（等于内联函数）也可定义在结构体外结构体外定义成员函数需要域解析运算符域解析运算符“:”，用以区别一般实用功能函数构造函数名改为与结构名相同void SetList(void);=SeqList(void);/不可以有返回值305.顺序表类顺序表类C基本顺序表的C+改造访问权限设置私有 pri

21、vate:对外隐藏，成员函数可访问公有 public：对外对内都开放，任何函数可直接访问new和delete运算符new负责调用构造函数delete释放动态数组需要加下标运算符,delete315.顺序表类顺序表类C基本顺序表的C+改造Class-类类的默认项为私有，结构为公有结构与类的使用选择结构：不含成员函数类：数据成员被封装，需要利用公有成员函数访问对象：由类定义的变量方法：类的成员函数，成员函数（方法）只能通过对象调用，不对构造函数进行调用（实际上在定义类的变量即对象的时候已经调用了构造函数）325.顺序表类顺序表类C+顺序表类的声明与实现课件实例演示335.顺序表类顺序表类作业：Content：用C+重构基本顺序队列Due Date：2010-11-8要求提交重构方案和步骤（纸质提交）、代码34