数据结构知识点全面总结—精华版

第1章绪论内容提要：◆数据结构研究的内容。针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。数据结构涵盖的内容：◆基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。数据——所有能被计算机识别、存储和处理的符号的集合。数据元素——是数据的基本单位，具有完整确定的实际意义。数据对象——具有相同性质的数据元素的集合，是数据的一个子集。数据结构——是相互之间存在一种或多种特定关系的数据元素的集合，表示为：Data_Structure=（D,R）数据类型——是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作，它由基本的数据类型构成。◆算法的定义及五个特征。算法——是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。算法的基本特性：输入、输出、有穷性、确定性、可行性◆算法设计要求。①正确性、②可读性、③健壮性、④效率与低存储量需求◆算法分析。时间复杂度、空间复杂度、稳定性学习重点：◆数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。◆用计算语句频度来估算算法的时间复杂度。第二章线性表内容提要：◆线性表的逻辑结构定义，对线性表定义的操作。线性表的定义：用数据元素的有限序列表示◆线性表的存储结构：顺序存储结构和链式存储结构。顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。链式存储结构:其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。通过指针来实现！◆线性表的操作在两种存储结构中的实现。数据结构的基本运算：修改、插入、删除、查找、排序1)修改——通过数组的下标便可访问某个特定元素并修改之。核心语句:V[i]=x;顺序表修改操作的时间效率是O(1)2)插入——在线性表的第i个位置前插入一个元素实现步骤：①将第n至第i位的元素向后移动一个位置；②将要插入的元素写到第i个位置；③表长加1。注意：事先应判断:插入位置i是否合法?表是否已满?应当符合条件：1≤i≤n+1或i=[1,n+1]核心语句：for(j=n;j=i;j--)a[j+1]=a[j];a[i]=x;n++;插入时的平均移动次数为：n(n+1)/2÷（n+1）＝n/2≈O(n)3)删除——删除线性表的第i个位置上的元素实现步骤：①将第i+1至第n位的元素向前移动一个位置；②表长减1。注意：事先需要判断，删除位置i是否合法?应当符合条件：1≤i≤n或i=[1,n]核心语句：for(j=i+1;j=n;j++)a[j-1]=a[j];n--;顺序表删除一元素的时间效率为:T（n)=(n-1)/2≈O(n)顺序表插入、删除算法的平均空间复杂度为O(1)单链表：（1）用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z）,请写出C语言程序。#includestdio.h#includestdlib.htypedefstructnode{chardata;structnode*next;}node;node*p,*q,*head;//一般需要3个指针变量intn;//数据元素的个数intm=sizeof(node);/*结构类型定义好之后，每个node类型的长度就固定了，m求一次即可*/voidbuild()//字母链表的生成。要一个个慢慢链入{inti;head=(node*)malloc(m);//m=sizeof(node)前面已求出p=head;for(i=1;i26;i++)//因尾结点要特殊处理，故i≠26{p-data=i+‘a’-1;//第一个结点值为字符ap-next=(node*)malloc(m);//为后继结点“挖坑”！p=p-next；}//让指针变量P指向后一个结点p-data=i+‘a’-1;//最后一个元素要单独处理p-next=NULL;//单链表尾结点的指针域要置空！}}voiddisplay()//字母链表的输出{p=head;while(p)//当指针不空时循环（仅限于无头结点的情况）{printf(%c,p-data);p=p-next;//让指针不断“顺藤摸瓜”}}（2）单链表的修改(或读取）思路：要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，然后才能：pdata=new_value读取第i个数据元素的核心语句是：Linklist*find(Linklist*head,inti){intj=1;Linklist*p;P=head-next;While((p!=NULL)&&(ji)){p=p-next;j++;}returnp;}3.单链表的插入链表插入的核心语句：Step1：s-next=p-next;Step2：p-next=s；6.单链表的删除删除动作的核心语句（要借助辅助指针变量q）：q=p-next;//首先保存b的指针，靠它才能找到c；p-next=q-next;//将a、c两结点相连，淘汰b结点；free(q)；//彻底释放b结点空间7.双向链表的插入操作：设p已指向第i元素，请在第i元素前插入元素x：①ai-1的后继从ai(指针是p)变为x（指针是s):s-next=p;p-prior-next=s;②ai的前驱从ai-1(指针是p-prior)变为x(指针是s);s-prior=p-prior;p-prior=s;8.双向链表的删除操作：设p指向第i个元素，删除第i个元素后继方向：ai-1的后继由ai(指针p)变为ai+1(指针p-next);p-prior-next=p-next;前驱方向：ai+1的前驱由ai(指针p)变为ai-1(指针p-prior);p-next-prior=p-prior;◆数组的逻辑结构定义及存储数组：由一组名字相同、下标不同的变量构成N维数组的特点：n个下标，每个元素受到n个关系约束一个n维数组可以看成是由若干个n－1维数组组成的线性表。存储：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。在二维数组中，我们既可以规定按行存储，也可以规定按列存储。设一般的二维数组是A[c1..d1,c2..d2]，则行优先存储时的地址公式为：二维数组列优先存储的通式为：◆稀疏矩阵（含特殊矩阵）的存储及运算。稀疏矩阵：矩阵中非零元素的个数较少（一般小于5%）学习重点：◆线性表的逻辑结构，指线性表的数据元素间存在着线性关系。在顺序存储结构中，元素存储的先后位置反映出这种线性关系，而在链式存储结构中，是靠指针来反映这种关系的。◆顺序存储结构用一维数组表示，给定下标，可以存取相应元素，属于随机存取的存储结构。◆链表操作中应注意不要使链意外“断开”。因此，若在某结点前插入一个元素，或删除某元素，必须知道该元素的前驱结点的指针。◆掌握通过画出结点图来进行链表（单链表、循环链表等）的生成、插入、删除、遍历等操作。◆数组（主要是二维）在以行序/列序为主的存储中的地址计算方法。◆稀疏矩阵的三元组表存储结构。◆稀疏矩阵的十字链表存储方法。补充重点：1.每个存储结点都包含两部分：数据域和指针域(链域)2.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。3.在链表中设置头结点有什么好处？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。4.如何表示空表？（1）无头结点时，当头指针的值为空时表示空表；（2）有头结点时，当头结点的指针域为空时表示空表。5.链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。6.sizeof(x)——计算变量x的长度（字节数）；malloc(m)—开辟m字节长度的地址空间，并返回这段空间的首地址；free(p)——释放指针p所指变量的存储空间，即彻底删除一个变量。7.链表的运算效率分析：（1）查找因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)。（2）插入和删除因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O(1)。但是，如果要在单链表中进行前插或删除操作，因为要从头查找前驱结点，所耗时间复杂度将是O(n)。例：在n个结点的单链表中要删除已知结点*P，需找到它的前驱结点的地址，其时间复杂度为O（n）8.顺序存储和链式存储的区别和优缺点？顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。◆顺序表适宜于做查找这样的静态操作；◆链表宜于做插入、删除这样的动态操作。◆若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；◆若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。9.判断：“数组的处理比其它复杂的结构要简单”，对吗？答：对的。因为——①数组中各元素具有统一的类型；②数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。10.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。11.写出右图所示稀疏矩阵的压缩存储形式。解：介绍3种存储形式。法1：用线性表表示：（(1,2,12)，(1,3,9)，(3,1,-3)，(3,5,14)，(4,3,24)，(5,2,18)，(6,1,15)，(6,4,-7)）法2：用十字链表表示用途：方便稀疏矩阵的加减运算方法：每个非0元素占用5个域法3：用三元组矩阵表示：稀疏矩阵压缩存储的缺点：将失去随机存取功能代码：1.用数组V来存放26个英文字母组成的线性表（a，b，c，…，z），写出在顺序结构上生成和显示该表的C语言程序。charV[30];voidbuild()//字母线性表的生成，即建表操作{inti;V[0]='a';for(i=1;i=n-1;i++)V[i]=V[i-1]+1;}voiddisplay()//字母线性表的显示，即读表操作{inti;for(i=0;i=n-1;i++)printf(%c,v[i]);printf(\n);}voidmain(void)//主函数，字母线性表的生成和输出{n=26;//n是表长，是数据元素的个数，而不是V的实际下标build();display();}第三章栈和队列内容提要：◆从数据结构角度来讲，栈和队列也是线性表，其操作是线性表操作的子集，属操作受限的线性表。但从数据类型的角度看，它们是和线性表大不相同的重要抽象数据类型。◆栈的定义及操作。栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶端。插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。对于向上生成的堆栈:入栈口诀：堆栈指针top“先压后加”:S[top++]=an+1出栈口诀：堆栈指针top“先减后弹”:e=S[--top]◆栈的顺序和链式存储结构，及在这两种结构下实现栈的操作。顺序栈入栈函数PUSH（）statusPush(ElemTypee){if(topM){上溢}elses[top++]=e;}顺序栈出栈函数POP()statusPop(){if(top=L){下溢}else{e=s[--top];return(e);}}◆队列的定义及操作，队列的删除在一端（队尾），而插入则在队列的另一端（队头）。因此在两