《数据结构知识点总结》计算机考研复试应届生求职刷题必备.docx
- 文档编号:13950388
- 上传时间:2023-06-19
- 格式:DOCX
- 页数:122
- 大小:12.76MB
《数据结构知识点总结》计算机考研复试应届生求职刷题必备.docx
《《数据结构知识点总结》计算机考研复试应届生求职刷题必备.docx》由会员分享,可在线阅读,更多相关《《数据结构知识点总结》计算机考研复试应届生求职刷题必备.docx(122页珍藏版)》请在冰点文库上搜索。
《数据结构知识点总结》计算机考研复试应届生求职刷题必备
数据结构知识点总结
要求:
(1)对数据结构这么课学了哪些知识有个清楚的认知;
(2)掌握目录结构,能复述出来每个知识点下都有哪些内容。
1绪论
1.1相关术语
绪论中会介绍数据结构的一些基本概念,要对数据模型有基本的了解。
数据(Data)是信息的载体,它能够被计算机识别、存储和加工处理。
它是计算机程序加工的原料,应用程序处理各种各样的数据。
数据元素(DataElement)是数据的基本单位。
在不同的条件下,数据元素又可称为元素、结点、顶点、记录等。
数据对象(DataObject)或数据元素类(DataElementClass)是具有相同性质的数据元素的集合。
在某个具体问题中,数据元素都具有相同的性质(元素值不一定相等),属于同一数据对象(数据元素类),数据元素是数据元素类的一个实例。
例如,在交通咨询系统的交通网中,所有的顶点是一个数据元素类,顶点A和顶点B各自代表一个城市,是该数据元素类中的两个实例,其数据元素的值分别为A和B。
数据结构研究的三个方面:
(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;
(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;
(3)对各种数据结构进行的运算。
数据的逻辑结构和存储结构是密不可分的两个方面,一个算法设计取决于所选定的逻辑结构,而算法实现依赖于所采用的存储结构。
数据的逻辑结构
数据的逻辑结构是指数据元素之间的逻辑关系,即从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。
数据的逻辑结构分线性结构和非线性结构。
数据的存储结构
存储结构是指数据结构在计算机中的表示,又称为映像,也叫物理结构。
它包括元素的表示和关系的表示。
数据的存储结构依赖于计算机,数据的存储结构主要有:
顺序存储、链式存储、索引存储、散列存储。
数据的运算
施加在数据上的运算包括运算的定义与实现。
运算的定义是针对逻辑结构的,指出运算的功能;运算的实现针对存储结构的,指出运算的具体操作步骤。
1.2算法及评价
算法是对特定问题求解步骤的描述,它是指令的有限序列,其中每条指令表示一个或多个操作。
算法要求能够对一定规范的输入,在有限时间内获得所要求的输出,因此一个算法也经常被封装为一个函数,用来实现特定的功能。
算法优劣的衡量标准:
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法具有五个特性:
有穷性、确切性、输入、输出、可行性。
一个算法有0个或多个输入。
一个算法有一个或多个输出,没有输出的算法是毫无意义的。
算法的衡量:
算法原地工作指算法所需的辅助空间未常量,即O
(1)。
例1:
下面程序的时间复杂度是?
x=2;
while(x x=2*x; } 答案: O(log2N) 每执行一次x以二倍往上增长,注意x 含有二分的思想在里面,二分即倍数增长或倍数下降后重新赋值。 因此复杂度为logn。 只要含有二分的思想就有logN。 例2: 请给出下面程序的时间复杂度? intfact(intn){ if(n<=1)return1; returnn*fact(n-1); } 求阶乘的递归函数,一共执行了n次的量级,故时间复杂度为O(N)。 例3: 下列程序的时间复杂度为? count=0; for(k=1;k<=n;k*=2){ for(j=1;j<=n;j++){ coun++; } } 分析下count++的执行次数在什么量级上,答案为: O(N*logN)。 例4: 下列程序的时间复杂度为? 答案: 这个不是二分的思想,幂次增长。 2线性表 2.1定义 线性表是具有相同数据类型的N(N>=0)个元素的有限序列,其中N为表长,当N=0时线性表是一张空表。 线性表的逻辑特征: 每个非空的线性表都有一个表头元素和表尾元素,中间的每个元素有且仅有一个直接前驱,有且仅有一个直接后继。 线性表是一种逻辑结构,表示元素之间一对一相邻的关系。 顺序表(数组)和链表是指存储结构,两者属于不同的层面。 2.2线性表的基本操作 基本操作的实现取决于采用哪种存储结构,存储结构不同,算法实现也不同,比如底层采用数据实现和链表实现,对应的代码不一样,但在上层实现算法逻辑时不关心底层具体实现,上述方法名可以直接作为伪代码使用。 2.3线性表的顺序表示 2.3.1顺序表定义 #defineMaxSize50//定义线性表的最大长度 typedefintElemType; typedefstruct{ ElemTypedata[MaxSize];//顺序表的元素 intlength;//顺序表的当前长度 }SqList;//别名 线性表的顺序存储又称为顺序表。 它是用一组地址连续的存储单元,依次存储线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。 顺序表可以是静态分配的数组,也可以是动态分配的数组。 如果采用动态分配,就是在使用时按照实际大小申请空间。 #defineInitSize100 typedefstruct{ ElemType*data;//指示动态分配数组的指针 intMaxSize,length;//数组的最大容量和当前个数 }SeqList;//动态分配数组顺序表的类型定义 C语言初始化: L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize); C++初始化: L.data=newElemType[InitSize]; 注意: 动态分配并不是链式存储,同样还是属于顺序存储结构,其物理结构没有变化,依然是随机存取方式,只是分配的空间大小可以在运行时决定。 顺序表的特点 顺序表最主要的特点是: 随机访问,即通过首地址和元素序号可以在O (1)时间内找到指定的元素。 顺序表的存储密度高,每个结点只存储数据元素,相对于链表来说没有指针域。 顺序表逻辑上相邻的元素物理上也相邻,所以插入和删除操作需要移动元素。 2.3.2顺序表基本操作 有效性校验、边界检查: 如下面代码的“判断i的范围是否有效”。 在函数体前面,主代码运行之前,对数据的有效性进行检查,比如是否为空、是否越界等。 体现代码的健壮性,完整性,在考试时如果能多这一步并加上注释,是加分项。 (1)顺序表的插入代码实现 //本算法实现将元素e插入到顺序表L中第i个位置 boolListInsert(SqList&L,inti,ElemTypee){ if(i<1||i>L.length+1){//判断i的范围是否有效 returnfalse; } if(L.length>=MaxSize){//当前存储空间已满,不能插入 returnfalse; }//有效性检查 for(intj=L.length;j>=i: j--){//将第i个元素及之后的元素后移 L.data[j]=L.data[j-1]; } L.data[i-1]=e;//在位置i处放入e L.length++;//线性表的长度加1 returntrue; } 插入算法的平均时间复杂度为O(N)。 最好情况: 在表尾插入(即i=n+1),元素移动语句将不执行,时间复杂度为O (1)。 最坏情况: 在表头插入(即i=1),元素移动语句将执行n次,时间复杂度为O(n)。 (2)删除操作代码 //本算法实现删除顺序表L中第i个位置的元素 boolListDelete(SqList&L,inti,int&e){ if(i<1||i>L.length){//判断i的范围是否有效 returnfalse; } e=L.data[i-1];//将被删除的元素赋值给e for(intj=i;j L.data[j-1]=L.data[j] } L.length--;//线性表的长度减1 returntrue; } 最好情况: 删除表尾元素(即i=n),无须移动元素,时间复杂度为O (1)。 最坏情况: 删除表头元素(即i=1),需要移动一个元素外的所有元素,时间复杂度为O(n)。 同理删除操作的平均时间复杂度也是O(N) (3)按值查找,返回位序。 //本算法实现查找顺序表中值为e的元素,如果查找成功,返回元素位序,否则返回0 intLocateElem(SqListL,ElemTypee){ inti; for(i=0;i if(L.data[i]==e){ returni+1;//下标为i的元素值等于e,返回其位序i+1 } return0;//退出循环,说明查找失败 } 最好情况: 查找的元素就在表头,仅需比较一次,时间复杂度为O (1)。 最坏情况: 查找的元素在表尾(或不存在)时,需要比较n次,时间复杂度为O(n)。 因此,线性表按值查找算法的平均时间复杂度为O(n)。 (4)按下标查找、随机访问。 给定下标之后(或给定取第几个元素)可以直接通过下标访问l.data[i],l.data[i-1];因此随机访问的时间复杂度为O (1)。 2.4线性表的链式表示 顺序表的插入产出操作需要移动大量元素,而链式存储时不要求逻辑上相邻的元素物理上也相邻,插入删除操作时不需要移动元素,而只需要修改指针即可。 虽然提高了插入删除的效率,但也失去了随机存取的优点。 2.4.1单链表定义 typedefstructLNode{//定义单链表结点类型 ElemTypedata;//数据域 structLNode*next;//指针域 }LNode,*LinkList;//类型定义 利用单链表可以解决顺序表需要大量的连续存储空间的缺点,但是单链表附加指针域,也存在浪费存储空间的缺点。 由于单链表的元素是离散地分布在存储空间中的,所以单链表是非随机存取的存储结构,即不能直接找到表中某个特定的结点。 查找某个特定的结点时,需要从头开始遍历,依次查找。 通过“头指针”来标识一个单链表,不同的教材有两种标识方式,一种不带头结点的单链表,一种带头结点的单链表。 不带头结点的单链表,第一个结点为NULL时代表空表,带头结点的单链表,L->next=NULL时表示一个空表。 带头结点的单链表头结点的指针域指向线性表的第一个元素结点,如下图: 头结点和头指针的区分: 不管带不带头结点,头指针始终指向链表的一个结点,而头结点是带头结点链表中的第一个结点,结点内通常不存储信息。 引入头结点后,可以带来两个优点: (1)由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作和在表的其他位置上的操作一致,无须进行特殊处理。 (2)无论链表是否为空,其头指针是指向头结点的非空指针(空表中头结点的指针域为空),因此空表和非空表的处理也就统一了。 (3)头结点的数据域不设任何信息,也可以记录表长等相关信息。 2.4.2单链表的基本操作 (1)头插法建立单链表 该方法从一个空表开始,生成新结点,并将读取到的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头,即头结点之后。 采用头插法建立单链表,读入数据的顺序与生成的链表中元素的顺序是相反的。 //从表尾到表头逆向建立单链表L,每次均在头结点之后插入元素 LinkListCreateList1(LinkList&L){ LNode*s; intx; L=(LinkList)malloc(sizeof(LNode));//创建头结点 L->next=NULL;//初始为空链表 scanf("%d",&x);//输入结点的值 while(x! =9999){//输入9999表示结束 s=(LNode*)malloc(sizeof(LNode));//创建新结点 s->data=x; s->next=L->next;//将新结点插入表中,L为头指针 L->next=s; scanf("%d",&x); } returnL; } (2)尾插法 头插法生成的链表中结点的次序和输入数据的顺序不一致。 若希望两者次序一致,可采用尾插法。 该方法是将新结点插入到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。 尾插法逻辑上更好理解。 //从表头到表尾正向建立单链表L,每次均在表尾插入元素 LinkListCreateList2(LinkList&L){ intx;//设置元素类型为整型 L=(LinkList)malloc(sizeof(LNode)); LNode*s,*r=L;//r为表尾指针 scanf("%d",&x);//输入结点的值 while(x! =9999){//输入9999表示结束 s=(LNode*)malloc(sizeof(LNode)); s->data=x; r-next=s; r=s;//r指向新的表尾结点 scanf("%d",&x); } r->next=NULL;//尾结点指针置空 returnL; } (3)按值查找结点 //本算法直接查找单链表L(带头结点)中数据域值等于e的结点指针,否则返回NULL LNode*LocateElem(LinkListL,ElemTypee){ LNode*p=L->next; while(p! =NULL&&P->data! =e){//从第1个结点开始查找data域为e的结点 p=p->next; } returnp;//找到返回该结点指针,否则返回NULL } (4)链表插入 实现插入结点的代码片段如下: 第一步: p=GetElem(L,i-1)//查找插入位置的前驱结点 第二步: s->next=p->next;//上图中的操作步骤1 第三步: p->next=s;//上图中的操作步骤2 扩展: 对某结点进行前插操作。 前插操作是指在某结点的前面插入一个新结点,后插操作的定义刚好与之相反,在单链表插入算法中,通常都是采用后插算法的。 通常的做法是,插入到后面,然后交换结点的值。 这种思想在删除时也常用,删除下一个交换节点值。 //将*s结点插入到*p之前的主要代码片段 s->next=p->next;//修改指针域,不能颠倒 p->next=s; temp=p->data;//交换数据域部分 p->data=s->data; s->data=temp; 小总结: 先把申请的空间插入进去,然后交换一下数据域部分。 (5)删除操作 假设结点*p为找到的被删除结点的前驱结点,为了实现这一操作后的逻辑关系的变换,仅需要修改*p的指针域,即将*p的指针域next指向*q的下一个结点。 //实现删除结点的代码片段如下: p=GetElem(L,i-1);//查找删除位置的前驱结点 q=p->next;//令q指向被删除结点 p->next=q->next;//将*q结点从链中“断开” free(q);//释放结点的存储空间。 扩展: 删除结点*p 要实现删除某一给定结点*p,通常的做法是先从链表的头结点开始顺序找到其前驱结点,然后再执行删除操作即可,算法的时间复杂度为O(n)。 其实,删除结点*p的操作可以用删除*p的后继结点操作来实现,实质就是将其后继结点的值赋予其自身,然后删除后继结点,也能使得时间复杂度为O (1)。 q=p->next;//令q指向*p的后继结点 p->data=p->next->data;//用后继结点中的数据覆盖要删除结点的数据 p->next=q->next;//将*q结点从链中“断开” free(q);//释放后继结点的存储空间 2.4.3双向链表定义 单链表结点中只有一个指向其后继的指针,这使得单链表只能从头结点依次顺序地向后遍历。 若要访问某个结点的前驱结点(插入、删除操作时),只能从头开始遍历,访问后继结点的时间复杂度为O (1),访问前驱结点的时间复杂度为O(n)。 为了克服单链表的删除缺点,引入了双向链表,双向链表结点中有两个指针prior和next,分别指向其前驱结点和后继结点。 双链表中结点类型的描述如下: typedefstructDNode{//定义双链表结点类型 ElemTypedata;//数据域 structDNode*prior,*next;//前驱和后继指针 }DNode,*DLinkList; 双链表仅仅是在单链表结点中增加了一个指向其前驱的prior指针,因此,在双链表中执行按值查找和按位查找的操作和单链表相同。 但双链表在插入和删除操作的实现上,和单链表有着较大的不同。 这是因为“链”变化时也需要对prior指针做出修改,其关键在于保证在修改的过程中不断链。 此外,双链表可以很方面地找到其前驱结点,因此不管前插入、后插入、前删除、后阐述,算法的时间复杂度均为为O (1)。 (1)插入操作 第一步: s->next=p->next;//将结点*s插入到结点*p之后 第二步: p->next->prior=s; 第三步: s->prior=p; 第四步: p->next=s; 上面的代码的语句顺序不是唯一的,但也不是任意的,第一步和第二步必须在第四步之前,否则*p的后继结点的指针就丢掉了,导致插入失败。 (2)删除操作 删除双链表中结点*p的后继结点*q,其指针的变化过程如下图: 删除操作的代码片段如下: p->next=q->next;//上图中的第一步 q->next->prior=p;//上图中的第二步 free(q);//释放结点空间 2.4.4循环单链表 循环单链表和单链表的区别在于,表中最后一个结点指针不是NULL,而改为指向头结点,从而整个链表形成了一个环,如下图所示: 在循环单链表中,表尾结点*r的next域指向L,故表中没有指针域为NULL的结点,因此,循环单链表的判空条件不是头结点的指针是否为空,而是它是否等于头指针。 在单链表中只能从表头结点开始往后顺序遍历整个链表,而循环单链表可以从表中的任一结点开始遍历整个链表。 有时对单链表常做的操作是在表头和表尾进行的,此时可以对循环单链表不设头指针而仅设尾指针,从而使得操作效率更高。 其原因是若设的是头指针,对表尾进行操作需要O(n)的时间复杂度,而如果设的是尾指针r,r->next即为头指针,对于表头与表尾进行操作都只需要O (1)的时间复杂度。 2.4.5循环双向链表 由循环单链表的定义不难推出循环双链表,不同的是在循环双链表中,头结点的prior指针还要指向表尾结点,如下图所示: 在循环双链表L中,某结点*p为尾结点时,p->next==L;当循环双链表为空表时,其头结点的prior和next域都等于L。 2.4.6静态链表 静态链表是借助数组来描述线性表的链式存储结构,结点也有数据域data和指针域next,与前面所讲的链表中的指针不同的是,这里的指针是结点的相对地址(数组下标),又称为游标。 和顺序表一样,静态链表也要预先分配一块连续的内存空间。 静态链表和单链表的对应关系如下图: 静态链表结构类型的描述如下: #defineMaxSize50//静态链表的最大长度 typedefstruct{//静态链表结构类型的定义 ElemTypedata;//存储数据元素 intnext;//下一个元素的数组下标 }SLinkList[MaxSize]; 静态链表以next==-1作为其结束的标志。 静态链表的插入、删除操作与动态链表相同, 只需要修改指针,而不需要移动元素。 总体来说,静态链表没有单链表使用起来方便,但是在一些不支持指针的高级语言(如Basic)中,这又是一种非常巧妙的设计方法。 顺序表和静态链表的物理结构(即存储结构)是相同的,在计算机内存中以数组的形式实现,是用一组地址连续的存储单元依次存储数据元素的线性结构,但两者的数据结构(逻辑结构)是不同的。 静态链表不是顺序结构,这里的结构指的是逻辑结构,在逻辑结构层面,静态链表是链式结构。 在物理层面,都采用顺序形式保存数据,因此物理结构、存储结构与线性表的顺序存储相同。 2.5顺序表和链表的比较(数组与链表) (1)存取方式 顺序表可以顺序存取,也可以随机存取,链表只能从表头顺序存取元素。 (2)逻辑结构和物理结构 采用顺序存储时,逻辑上相邻的元素,其对应的物理存储位置也相邻。 而采用链式存储时,逻辑上相邻的元素,其物理存储位置则不一定相邻,其对应的逻辑关系是通过指针链接来表示的,静态链表也是链式存储方式。 注意区别存取方式和存储方式,存取方式指的插入删除。 (3)查找、插入和删除操作 对于按值查找,当顺序表在无序的情况下,两者的时间复杂度均为O(n);而当顺序表有序时,可采用折半查找,此时时间复杂度为O(lgN)。 对于按序号查找,顺序表支持随机访问,时间复杂度为O (1),而链表不支持随机访问,只能遍历链表,其平均时间复杂度为O(n)。 顺序表的插入、删除操作,平均需要移动半个表长的元素。 链表的插入、删除操作,只需要修改相关结点的指针域即可。 由于链表每个结点带有指针域,因而在存储空间上比顺序存储要付出较大的代价,存储密度不如顺序存储。 (4)空间分配 顺序存储在静态存储分配情形下,一旦存储空间装满就不能扩充,如果再加入新元素将出现内存溢出,需
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构知识点总结 数据结构 知识点 总结 计算机 考研 复试 应届生 求职 必备