数据结构复习资料

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

1、复习【第一章】1.数据结构：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算。2.概念：1)数据(data)：是描述客观事物的并能被计算机处理的信息的总称。2)数据元素(dataelement)：是数据的基本单位,在计算机中作为一个整体处理。3)数据项（DataItem）：具有独立意义的最小数据单位，是对数据属性的描述。4)数据对象集(dataobject)：是具有相同性质的数据的集合,是数据的一个子集。5)数据的逻辑结构：数据元素间的逻辑上的联系（关系）.6)数据的存储（物理）结构：是逻辑结构在计算机存储器里的实现

2、。3.数据类型是一组值的集合和定义在这个值集之上的一组操作的总称。4.抽象数据类型（AbstractDataType，简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。5.算法：(algorithm)是对特定问题求解步骤的一种描述,是指令的有限序列。6.算法重要特性:(1)输入(2)有穷性(3)确定性(4)可行性(5)输出7.算法的评价标准：（1）正确性（2）可读性（3）健壮性（4）效率和低存储量需求8.算法分析：1.空间2.时间9.渐近时间复杂度：1)计算出每条语句的执行次数（频度）f(n)，n是问题的规模2)计算出T(n)的数

3、量级   令T(n)=O（f(n)）的数量级，忽略常量、低次幂和最高次幂的系数。10【第二章】1.线性表（LinearList）：是由n(n>=0)个性质相同的具有线性关系的数据元素组成的有限序列.记为L=(a1,a2,a3,…,an)。a)线性表的逻辑结构：前后件关系2.线性表的顺序存储结构：用内存中一批地址连续的存储单元（数组）存储a)在a[n]中，ai的地址=LOC(ai)＝LOC(a0)＋L*(i－1)，L是每个元素的字节数。3.顺序表类声明：templateclasssq_LList//顺序表类{intmm;//存储空间容量in

4、tnn;//顺序表长度（元素个数）T*v;//顺序表存储空间首地址,或Ta[100];public://成员函数sq_LList(){mm=0;nn=0;}sq_LList(int);//建立空顺序表，申请存储空间voidprt_sq_LList();//顺序输出顺序表中的元素与顺序表长度intflag_sq_LList();//检测顺序表的状态voidins_sq_LList(int,T);//在表的指定元素前插入新元素voiddel_sq_LList(int);//在表中删除指定位置的元素};a)//在表的指定位置i处，插入新元素template

5、assT>voidsq_LList::ins_sq_LList(inti,Tb){intk;if(nn==mm)//存储空间已满，上溢{cout<<"上溢"<nn)//在最后一个元素之后插入i=nn;if(i<0)i=0;//在第一个元素之前插入for(k=nn;k>i;k--)//从最后一个元素直到第i个元素均后移一个位置v[k]=v[k-1];v[i]=b;//插入新元素nn=nn+1;//顺序表长度加1return;}b)//在顺序表中删除指定位置i的元素templatevoidsq_LLi

6、st::del_sq_LList(inti,intk){intp;if(nn==0)//顺序表为空，下溢错误{cout<<"underflow!"<

7、

8、(i>=nn)

9、

10、((i+k-1)>=nn))//顺序表中没有这个元素{cout<<"没有这个元素!"<

11、平均要移动表中大约一半的数据元素。b)若表长为n，前两个算法的时间复杂度为O(n)。2.线性表的顺序存储结构特点：效率较低，容量有限，适于直接(随机)存取操作3.线性表的链表存储结构：用内存空间中一组任意的存储单元（可以是地址连续的,也可以是不连续的）来存储线性表的数据元素。4.单链表：5.循环单链表：6.双向循环链表：7.结点的存储结构定义为:structnode{Tdata;//数据域node*next;　　//指针域10}1.单链表类声明：classLinkList{node*head；intn；//结点个数public://成员函数}；2.单

12、链表的查找（在单链表中查找第i个结点，若存在，则返回它的地址，否则