课件年专升本数据结构

《课件年专升本数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章引论一、算法涉及题目：05年二(1,3)二、复杂度=占用资源的多少，时间、空间O(...)，表示数量级O(1)

2、def统一类型名称(无论物理结构为何)，统一函数的名称、参数和返回类型统一是为了编写程序方便（......）数据类型例子：C里头int就是一个类型intx;变量是内存中的若干字节，一套房子变量有名字，张三家有地址，305类型有名字、是模板（两室一厅）。函数定义例子：C里头voidf(inti,floaty);函数有名字，参数（局部变量）、返回类型参数是碗，参数的值=水intx,y;x=y;赋值语句左边是单元，右边是单元的内容类型定义：typedef例子：typedefstructx*YYY;typedefstructx{inta;int

3、b;charc;}ListItem;voidmain(){ListItemy;y.a=6;//y家a房间住6YYYp;p=&y;//y家地址保存在p中p->a=7;}四、数据结构=逻辑结构，物理结构数据逻辑结构：顶层成分数据+成分数据之间关系（线性、层次-树、图）数据元素（成分数据）：一个同学档案数据项：姓名、生日、学号....数据物理结构：-底层存储结构=顺序（数组）、非顺序（链表）操作的算法具体实现不同（比如在数组插入，在链表中插入算法不同）但是可以用高级语言C统一类型名称----ADT(抽象数据类型)（逻辑结构写成数据类型，无论用

4、什么物理结构）统一操作的函数定义(函数名和参数)---ADTvoidInsert(intk,ListItemx,...)应用程序逻辑结构ADT-界面/接口物理结构五、指针1、地址是非负整数，地址长度与内存大小有关。n个字节，地址二进制最短长度logn位2、指针变量是保存地址的变量，变量是内存中的若干字节，一套房子变量有名字，张三家有地址，305变量有类型：具体占几个字节。变量的运算3、指针变量占字节数=地址长度，sizeof4、指针变量必须有名字、类型int*p;intx;p=&x;//p存放x的首字节地址。*表示指针变量，该变量名字为

5、p，int表示p是指向int类型变量，p中存放一个int变量首字节的地址,p代表x占有的所有空间（由p类型决定），。p=&x;表示p内保存x首字节的地址，注意x不止一个字节，p虽然是指向x首字节，并不意味p只管x的首字节，而是管理x的所有字节。因为p是指向int的指针。p++相当于p加上sizeof(int)，即int变量占用的字节数sizeof(p)是p占用的字节数5、double*q;q++相当于q加上sizeof(double)sizeof(q)是q占用的字节数，6.不管是什么类型的指针变量，所占字节数应该相同，但是不同指针变量不

6、能任意互相赋值，因为无法确定究竟管理多少字节。如果要互相赋值，必须进行强制类型转换。p=q;//错p=(int*)q;//对这样p与q内容相同，但是p管理两个字节，q管理4个字节。空类型指针void，表示不知道应该管理几个字节。6、typedefstructx*YYY;//*表示指针变量类型，类型名是YYY,x表示YYY是指向x模板的类型typedefstructx{inta;intb;charc;}ListItem;voidmain(){ListItemy;//y是记录变量，//y是a,b,c变量的总名字，y.a=6;//一旦有了y，

7、则a,b,c不能//单独被访问，y.b=7;//必须在y.之后被访问y.c='a';//一旦分了房子，不能单独说//厨房漏水，要说张三家厨房漏水YYYp;//p是另外一个变量，而且//是另外一个类型p=&y;//p与y不是一个变量，也不//是一个类型，p中存放y首字节地址。//p管理y的所有字节p->a=7;//可以通过p来访问y的a,b,cp->b=6;//因为p是指向y类型的指//针，p->b会自动跳过a所//占的字节（不止一个字节），//取得b所占的字节（不止一个），//这就是指针类型的必要性。p->c='b';}p++相当于p加

8、上sizeof(y)，即y变量占用的字节数第二章线性表一、顺序表线性表ADT：Listtypedefstructx{inta;intb;charc;}ListItem;typedefstructalist*