数据结构学习笔记

《数据结构学习笔记》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2012/10/25此番学习的数据结构视频，共64课时。按计划，每天4课时，计划15天完成。故在11月10号，必须完成。课时11.程序=算法+数据结构2.数据结构：研究数据的逻辑结构和物理结构及其关系。Data-Structure=(D,R)3.数据>数据元素>数据项4.逻辑结构：集合，线性表，树，图物理结构：顺序，链式，索引，散列课时21.数据类型：是一个值的集合以及在这些值上定义的一组操作的集合（交，并，异或等）的总称。（数组、指针、类、整形、实型、枚举等）2.抽象数据类型（ADT）：3.算法：有限指令的集合。五个性质：有穷性、确定性、可行性、输入（零个或多个）

2、、输出（至少一个）4.算法的设计要求：正确性、可读性、健壮性、时间效率和空间占有率5.算法与程序的区别：I.表现形式是否相同II.是否具有有穷性6.算法分析课时31.时间复杂度：用O（f（n））表示。2.面向对象程序设计的特点：抽象、封装和数据隐藏、继承和重用、多态性课时41.C++语言基本语句：I.赋值语句II.选择语句（if条件语句，switch开关语句）III.循环语句(for,while,do---which语句)2.函数结束:正常结束语句——return表达式；Break语句——退出循环异常结束函数——exit（异常代码）2012/10/26课时51.C+

3、+函数定义形式：返回类型函数名（形式参数）{语句}---函数名，由下划线、字母和数字组成，并且数字不能做开头。调用：声明函数原型类型说明符被调函数名（含类型说明的形参表）；函数调用函数名（时参列表）；2.参数传递的方式I.值传递：实参的值传递给形参，函数修改的是形参的值，实参值没有改变。II.地址传递：函数通过传递实参地址给形参引用。课时61.常值调用---可保护参数2.类和对象类的定义：用高级语言实现的一个ADT描述。类的定义：通过类说明定义的变量。3.类的声明一般形式：classclassname{private：私有数据成员私有函数成员public：公有数据成

4、员公有函数成员protected：保护数据成员保护函数成员}；4.类实现：：范围界定符5.对象的声明形式：类名对象名6.访问对象的公有成员对象名.公有成员函数名（参数表）---对象只能访问公有成员<>在标准路径（目录）下寻找“”在当前路径（目录）下寻找课时71.输入输出的C++实现：Iostream.h包含istream，ostream，cin（代表键盘），cout（代表显示器），cerr，clog操作符：.>>提取符（代表从键盘输入字符到计算机）<<插入符（代表从计算机打印出字符到屏幕）2.多态性：在程序中同一符号或名字在不同情况下具有不同解释的现象。intiad

5、d（inta，intb）intfadd（floata，floatb）I.函数重载：两个以上的函数，使得语意非常相似的函数取相同的函数名，但是形参的个数或者类型不同。intadd（intx，inty）{returnx+y}；intadd（floatx，floaty）；{returnx+y}；===================a=add（2，3）；b=add(2.5,3.5)；系统根据参数类型自动决定调用哪个函数II.操作符重载：使适用于基本数据类型的运算符，经过重载后，适用于用户自定义数据类型。重载为类的成员函数形式：函数类型operator运算符（形参）{函数体

6、；}1.动态存储分配I.分配空间形式：new类型名T（处置列表）；int*point；point=newint（2）；II.释放空间形式：delete指针名deletepoint；课时81.模块函数定义形式：template函数定义模块类定义形式：tamplate{---返回类型函数名（参数）}；2.线性表I.顺序表特点：存取空间连续，逻辑结构与物理结构相同，顺序存储，随机存取。最佳实现：一维数组地址：Loc（a[i]）=Loc(a[0])+i*cII.链表特点课时91.线性表的总结：插入、删除麻烦，移动需要大约一半的元素；插入一个元

7、素平均需要移动n/2的元素删除一个元素平均需要移动（n-1）/2的元素；课时101.链式表特点：逻辑顺序与物理顺序可以相同，也可以不同。优点：插入删除方便、空间共享性好。2.单链表定义：每个节点只含有一个链接域的链表。3．不带头结点的单链表2012/10/27课时111.带头节点的单链表（一般都带头结点）空表：L->next==NULL表尾：P->next==NULL2.插入3.删除课时121.循环链表课时131.双向循环链表2.栈：删插只能在一端进行的线性表。课时141.栈的顺序实现2.栈的链式实现2012/10/28课时151.队列：一端插入，另一端删除的线