[清航考研]暑期数据结构辅导-01

《[清航考研]暑期数据结构辅导-01》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、清航计算机辅导www.tsinghang.com清航计算机辅导www.tsinghang.com数据结构辅导第一章线性表线性表清航考研第一章线性表顺序表链表顺序表与链表的比较清华大学计算机系殷人昆多项式清航考研www.tsinghang.com清航考研www.tsinghang.com清航计算机辅导www.tsinghang.com清航计算机辅导www.tsinghang.com线性表(LinearList)a1a2a3a4a5a6�线性表的定义和特点�理解线性表的要点是�定义n（≥清航考研0）个数据元素的有限序列，记作a)表中元素具有逻辑上的顺序性，在序列中

2、清航考研（a1,a2,…,an）各元素排列有其先后次序。ai是表中数据元素，n是表长度。b)表中元素个数有限。�特点线性排列c)表中元素都是数据元素。就是说，每一表�除第一个元素外，其他每一个元素有一个元素都是不可再分的原子数据。且仅有一个直接前驱。d)表中元素的数据类型都相同。这意味着每�除最后一个元素外，其他每一个元素有一一表元素占有相同数量的存储空间。个且仅有一个直接后继。清航考研www.tsinghang.com清航考研www.tsinghang.com1清航计算机辅导www.tsinghang.com清航计算机辅导www.tsinghang.com顺

3、序表(SequentialList)顺序表的连续存储方式�顺序表的定义和特点LOC(i)=LOC(i-1)+l=a+i*l,�定义将线性表中的元素相继存放在一个连续LOC是元素存储位置，l是元素大小的存储空间中，即构成顺序表。清航考研清航考研0123456789�它是线性表的顺序存储表示，可利用一维数组a35274918605477834102描述存储结构。�其特点是：元素的逻辑顺序与物理顺序一致。llllllllll�访问方式：可顺序存取，可按下标直接存取。a+i*la,i=0012345LOC(i)=elem253457164809LOC(i-1)+l=a

4、+i*l,i>0清航考研www.tsinghang.com清航考研www.tsinghang.com清航计算机辅导www.tsinghang.com清航计算机辅导www.tsinghang.com顺序表的静态结构定义顺序表的动态结构定义#defineListSize100//最大允许长度#defineListSize100//最大允许长度typedefintElemType清航考研;//元素的数据类型typedefintElemType清航考研;//元素的数据类型typedefstruct{typedefstruct{ElemTypeelem[ListSize

5、];//存储数组ElemType*elem;//存储数组intlength;//当前表元素个数intlength;//当前表元素个数}SeqList;intmaxSize;//表的最大长度}SeqList;�顺序表静态定义，假定L是一个类型SeqList的顺序表，一般用L.elem[i]来访问它。�顺序表动态定义，它可以扩充，新的大小计入�表一旦装满，不能扩充。数据成员maxSize中。清航考研www.tsinghang.com清航考研www.tsinghang.com2清航计算机辅导www.tsinghang.com清航计算机辅导www.tsinghang.

6、com顺序表基本运算的实现�动态分配命令new是Pascal、C++、Java常用的�构造一个空的顺序表语句，它的作用与C的malloc命令等效，但比voidInitList(SeqList&L){malloc简洁，它不用计算分配字节数，不用做指L.elem=new清航考研ElemType[ListSize];针转换，一切工作清航考研new替你代劳了。if(L.elem==NULL){�注意指针的使用。指针所指示元素也有它的数据printf(“存储分配失败!”);类型。例如对于指针*p和*q：exit(1);char*p=newchar[maxSize];

7、}L.length=0;L.maxSize=ListSize;float*q=newfloat[maxSize];}�用p++让p指到下一字符位置，用q++让q指到下一浮点数位置，它们移过的字节数不同。�判断L.elem是否为空语句是后置条件。清航考研www.tsinghang.com清航考研www.tsinghang.com清航考研www.tsinghang.com清航考研www.tsinghang.com�引用型参数&的使用�按值查找：在顺序表中从头查找结点值等于给定值x的结点�例如，voidInitList(SeqList&L)�C++的引用型参数“&”

8、与Pascal的变量参数一intFin