计算机考研基础讲义-数据结构基础

计算机考研小组(100)2019年计算机考研基础班讲义docin/sundae_meng第一章绪论什么是数据结构直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间关系和运算的一门学科。数据结构是指数据之间的关系按某种关系组织起来的一批数据。以一定的存储方式把它们存储到计算机的存储器中，并在这些数据上定义一个运算集合，这就是数据结构。学习数据结构的重要性1.“数据结构”在计算机科学中是一门综合性的专业基础课,在考研中占很大的分值。2.数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。3.数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。§1.2数据结构的概念一、基本概念数据：能输入计算机且被能计算机处理的一切对象。数据元素：对现实世界中某独立个体的数据描述。数据项：具有独立意义的最小数据单位。数据类型：每个数据项必须属于某确定的数据类型。基础§1.3数据的逻辑结构一、基本概念数据对象：具有相同特征的数据元素的集合。关系：在数据对象中各数据元素之间存在着某种关系（或联系）。这种关系反映了该数据对象中数据元素所固有的一种结构。在数据处理领域，通常把数据之间这种固有的关系简单的用前驱和后继关系描述。§1.3数据的逻辑结构二、数据的逻辑结构设D表示数据元素的集合，R表示D上的关系的集合，则一个数据结构B可表示为：B=（D，R）由此可见数据结构由两部分构成（1）表示各元素的信息D（2）表示数据之间关系的信息R一般用二元组表示D中各数据元素之间的前驱、后继关系。假设a,b是D中的两个元素，则二元组a,b表示a是b的前驱，b是a的后继。§1.3数据的逻辑结构三、数据结构的分类线性结构：除了一个根结点外，其他各结点有唯一的前驱；除了一个终端结点外，其他各结点有唯一的后继。树状结构：除了一个根结点外，各结点有唯一的前驱；所有的结点都可以有多个后继。网状结构：各结点可以有多个前驱或多个后继。§1.4数据的存储结构数据结构在计算机中的表示称为数据的存储结构。数据结构包括结点的值及结点之间的关系，其存储结构除了必须存储结点的值外，还得能以直接或隐含的方式体现出结点之间的关系。四种基本的存储方式：1、顺序方式顺序结构最适合于线性结构，它把逻辑上相邻的结点存放到物理上相邻的存储单元中，顺序存储结构只存储结点的值，不存储结点的关系，结点的关系通过存储单元相邻关系隐含表示出来。§1.4数据的存储结构2、链接方式链接存储方式不仅存储结点的值，而且还存储结点之间的关系。它利用结点附加的指针字段，存储其后继结点的地址。3、索引方式在线性结构中，各结点可以依前驱、后继关系排成一个序列（a1,a2,a3,……an)。每个结点ai在序列中都对应一个序号i序号i也称为结点ai的索引号。索引存储就是通过建立一个附加的索引表，然后利用索引表中的索引项的值来确定结点的实际存储单元的地址。§1.4数据的存储结构4、散列方式利用该结点的值确定该结点的存储单元地址。§1.5数据运算和算法1、数据运算按一定的逻辑结构把数据组织起来，采用适当的存储方式把数据结构存储到计算机中，最终的目的是为了有效地处理数据，提高数据的运算效率。1）插入：往数据结构中添加新的结点称为插入。2）删除：把指定的结点从数据结构中删除。3）更新：改变指定结点的值或者改变某些结点的关系称为更新。4）查找：在数据结构中查找某些满足条件的结点。5）排序：对线性表的各结点，按指定数据项的值从小到大或从大到小的重新排列。排序运算实际上是破坏线性表的旧关系，重新建立线性表的新关系。§1.5数据运算和算法2、算法算法是对特定问题求解步骤的一种描述。算法应具有的几个特征：1）有穷性：算法应在计算机存储资源容许的条件下，在一定时间内执行完毕。2）确定性：算法的每一步骤应定义明确，没有二义。3）可行性：算法是可以被计算机执行的。当输入正确的数据后，应得到正确的结果。§1.5数据运算和算法3、算法的评价对算法评价的几个指标空间复杂度空间复杂度是指执行算法所需要的辅助空间大小。时间复杂度时间复杂度是指执行完算法所需的运算次数。第二章线性表线性表是一种最简单、最常用的数据结构。线性表的主要存储结构有两种：顺序存储结构和链接存储结构。§2.1线性表的定义及基本运算一、线性表的定义线性表是由n(n≥0)个性质相同的数据元素a1,a2,a3,…an组成的有限序列，记为(a1,a2,a3,…an)。二、线性表的基本运算（1）置线性表为空表；（2）求线性表的长度；（3）读取线性表中的第i个元素；（4）修改线性表中的第i个元素；（5）查找线性表中具有某个特征值的数据元素；§2.1线性表的定义及基本运算二、线性表的基本运算（6）在线性表的第i个数据元素之前或之后插入一个新的数据元素；（7）删除线性表中第i个数据元素或满足给定条件的第一个数据元素；（8）对线性表中的所有元素按照给定的关键字大小进行排序。§2.2线性表的顺序存储结构及运算一、线性表的顺序存储结构线性表的顺序存储结构是将线性表中的结点按其逻辑顺序依次存放在内存中一组连续的存储单元中，即把线性表中相邻的结点存放在地址相邻的内存单元中。线性表在c语言中用一维数组表示。c语言的描述TypedefintET;#definemaxlen1000ETs[maxlen];§2.2线性表的顺序存储结构及运算一、线性表的顺序存储结构线性表C语言描述的说明：在C语言中，数组的下标是从0开始的，数据结构中的结点的序号是从一开始的。因此在线性表中的第一个元素是指S[0]。两个相邻结点ai和ai+1的存储位置记为LOC（ai）和LOC（ai+1），则结点满足以下关系LOC（ai+1）=LOC（ai）+1§2.2线性表的顺序存储结构及运算二、线性表的运算1、插入运算的算法描述：intinsertqlist(inti,ETx,ETs[],int*np){intj,n;n=*np;if((i1)||(in+1))return(0);else{for(j=n;j=i;j--)s[j]=s[j-1];s[j]=x;*np=++n;return(1);}}§2.2线性表的顺序存储结构及运算二、线性表的运算2、删除运算的算法描述：intdelqlist(inti,ETs[],int*np){intj,n;n=*np;if((i1)||(in))return(0);else{for(j=i;jn;j++)s[j-1]=s[j];*np=--n;return(1);}}§2.2线性表的顺序存储结构及运算二、线性表的运算3、查找运算的算法描述：intfincl(ETx,ETs[],intn){intj;for(i=0;in;i++)if(x==s[i])break;if(i==n)return(0);return(i+1)}§2.3线性表的链接存储结构及运算一、线性链表用链接方式存储的线性表称线性链表，简称链表。线性表的链接存储结构是用一组地址任意的存储单元来存放表中的数据元素，这组存储单元可以是连续的，也可以是不连续的。数据指针数据域指针域单链表结点结构§2.3线性表的链接存储结构及运算一、线性链表结点的数据定义形式：typedefstructnode{ETdata;structnode*link;}NODE;结点的内存分配：（NODE*)malloc(sizeof(NODE))§2.3线性表的链接存储结构及运算二、单链表及其运算线性链表的每一个结点只含有一个指针域，这样的线性链表称为单链表。单链表的运算：建表、查找、插入、删除以及判断是否为空表。1、建立单链表首先生成表头结点，形成一个空链表，然后在表中逐一增加新的结点。（1）使用malloc函数，开辟新的存储单元q；（2）读入新结点数据，新结点的指针域为空（3）把新结点链接到链表上去。建立单链表的算法描述：NODE*create(intn){NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));p-data=0;p-link=NULL;head=p;for(i=1;i=n;i++){q=(NODE*)malloc(sizeof(NODE));scanf(%d,&q-data);q-link=NULL;p-link=q;p=p-link;}return(head);}§2.3线性表的链接存储结构及运算2、查找链表中的X查找链表中是否存在结点X，算法的基本思想为：从表头指针指向的第一个结点开始，依次把表中结点的数据域和给定值X进行比较，直到某个结点的数据域的值等于给定值X（既查找成功），则返回该结点的地址；如果查找到表尾仍未找到（既查找失败），则返回NULL。查找单链表中结点X的算法描述：NODE*found(NODE*head,ETx){NODE*p;p=head-link;while((p!=NULL)&&(p-data!=x))p=p-link;return(p);}§2.3线性表的链接存储结构及运算3、在单链表中插入新结点X在链表中的某一结点p之后插入一个数据为X的新结点。过程如下：（1）生成一个新结点q，将X赋给q-data;（2）修改有关结点的指针域：将原p结点的后继作为q结点的后继，q结点作为p结点的后继。在单链表中插入新结点X的算法描述：voidinsert(NODE*head,NODE*p,ETx){NODE*q;q=(NODE*)malloc(sizeof(NODE));q-data=x;if(head-link==NULL){head-link=q;q-link=NULL;}else{q-link=p-link;p-link=q;}}§2.3线性表的链接存储结构及运算4、删除单链表中的结点X删除单链表中的结点X，并由系统收回其占用的存储空间。过程如下：（1）设定两指针p和q，p指针指向被删除结点；q为跟踪结点，指向被删除结点的前驱结点;（2）p从表头指针head指向的第一个结点开始向后依次进行搜索。当p-data等于X时，被删除结点找到。（3）修改p的前驱结点q的指针域：使被删除结点的后继结点成为其前驱结点的后继结点，既q-link=p-link，p结点被删除，然后再释放存储空间。在单链表中删除结点X的算法描述：voiddelete(NODE*head,ETx){NODE*p,*q;p=head;q=p;p=p-link;while((p!=NULL)&&(p-data!=x)){q=p;p=p-link;}if(p==NULL)printf(Notfound!\n);else{q-link=p-link;free(p);}}§2.3线性表的链接存储结构及运算三、循环链表链表中的最后一个结点的指针指向链表中第一个结点，使链表形成一个环行，此链表称循环链表。循环链表是线性链表的一种变形。其优点是从链表中任何一个结点出发都可以访问到表中的所有结点。在循环链表中为了使空表和非空表处理一致，可以附加一个表头结点。§2.3线性表的链接存储结构及运算三、循环链表非空表（a)headhead空表（b)(1)在头指针为head的循环链表查找值为x的前驱结点。NODE*looknode(head,x)ETx;NODE*head;{NODE*p;p=head;while((p-link!=head)&&(((p-link)-data)!=x))p=-link;return(p);}(2)在头指针为head的循环链表在值为x的结点之前插入一个值为b的新结点。NODEinsnode(head,x,b)ETx,b;NODE*head;{NODE*p,*q;p=(NODE*)malloc(sizeof(NOD