数据结构知识点总结-

第一章概述一、概念：1．学科：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等。2．概念：由某一数据对象及该对象中所有数据成员之间的关系组成。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存储结构和对数据所施加的运算。3．这三个方面的关系为：1)数据的逻辑结构独立于计算机，是数据本身所固有的。2)存储结构也称为物理结构，是逻辑结构在计算机存储器中的映像，必须依赖于计算机。3)运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。4．数据（data）:信息的载体，指能够输入到计算机中，并被计算机识别和处理的符号的集合。例如：数字、字母、汉字、图形、图像、声音都称为数据。5．数据元素（dataelement）：数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位。6．逻辑结构：从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向对象的。7．物理结构：指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。8．逻辑结构与存储结构二者关系：物理结构是逻辑结构的存储映象。任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。9．从逻辑结构划分数据结构：线性结构和非线性结构（树、图）10．线性结构：1)元素之间为一对一的线性关系2)第一个元素无直接前驱3)最后一个元素无直接后继4)其余元素都有一个直接前驱和直接后继。k1k2k3k4k5k6k711．非线性结构1)元素之间为一对多或多对多的非线性关系2)每个元素有多个直接前驱或多个直接后继12．顺序存储：数据元素存储方法：所有元素存放在一片连续的存贮单元中。数据元素之间关系表示：逻辑上有相邻关系的元素存放到计算机内存仍然相邻，即存储位置体现了数据元素之间的关系。13．链式存贮数据元素存储方法：元素可以存放在不连续的存贮单元中。数据元素之间关系表示：逻辑上相邻的元素存放到计算机内存后不一定是相邻的，因此元素之间的关系通过地址确定。14．算法：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。特性：输入有0个或多个输入输出有一个或多个输出(处理结果)确定性每步定义都是确切、无歧义的有穷性算法应在执行有穷步后结束可行性每一条运算应可通过已经实现的基本运算执行有限次来实现算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死batcateatmat^…循环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。15．算法的分析与度量：1）算法的性能标准：正确性：正确执行的功能和性能要求。可使用性：算法能够很方便的使用。可读性：便于理解、测试和修改算法。效率：计算机资源的消耗，包括存储和运行时间。健壮性：检错、报错及纠错的功能。2）算法的事前估计：空间复杂度和时间复杂度3）算法的后期测试：在算法中的某些部位插装时间函数time()，测定算法完成某一功能所花费的时间。16．时间复杂度：一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记作T(n)=O(f(n))：表示算法中基本运算次数T(n)是问题规模n的某个函数f(n)。1）求下列算法段的语句频度for(i=1;i=n;i++)for(j=1;j=i;j++)x=x+1;时间频度T(n)=1+2+3+…+n=2)1(nnＴ(n)与n2数量级相同，因此它的时间复杂度为Ｏ(n2)。2）例分析下列算法段的时间频度及时间复杂度for（i=1;i=n;i++）for(j=1;j=i;j++)for(k=1;k=j;k++)x=i+j-k;第二章线性表1．线性表的定义：线性表（linearlist）是n（n≥0）个数据元素a1，a2，…an组成的有限序列。其中n称为数据元素的个数或线性表的长度，当n=0时称为空表，n0时称为非空表。通常将非空的线性表记为（a1，a2，…,an），其中的数据元素ai（1≤i≤n）是一个抽象的符号，其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定。2．线性表中数据元素的关系：元素之间为一对一的线性关系。有且仅有一个开始结点(表头结点)a1，它没有直接前驱，只有一个直接后继;有且仅有一个终端结点(表尾结点)an，它没有直接后继，只有一个直接前驱;其它结点都有一个直接前驱和直接后继；3．线性表的顺序存储结构,也称为顺序表。在内存中开辟一片连续存储空间，但该连续存储空间的大小要大于或等于顺序表的长度。然后让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。4．假设线性表中元素为（a1，a2，….,an）设第一个元素a1的内存地址为LOC(a1)，每个元素在计算机内占d个存储单元，则第i个元素ai的地址为LOC(ai)=LOC(a1)+(i-1)×d(其中1≤i≤n)。5．插入元素voidListInsert_sq(Sqlist&L,inti,inte){int*p,*q;if(i1||iL.length+1)return;q=&L.elem[i-1];//插入位置for(p=&L.elem[L.length-1];p=q;--p)*(p+1)=*p;*q=e;++L.length;return;}0123…i-1ii+1…n…maxsize-1a1a2a3…ai-1xai…an-1an0123…i-1ii+1…n…maxsize-1a1a2a3…ai-1aiai+1…an…序号内容序号内容插入前插入后0123…i-1ii+1…n-1…maxsize-1a1a2a3…ai-1ai+1ai+2…an…0123…i-1ii+1…n…maxsize-1a1a2a3…ai-1aiai+1…an…序号内容序号内容删除前删除后6．删除元素voidListDel_sq(Sqlist&L,inti,int&e){if(i1||iL.length)return;e=L.elem[i-1];for(intj=i;jL.length;j++)L.elem[j-1]=L.elem[j];--L.length;}7．线性表的链式存储结构，也称为链表。存储方式：存储单元可以不连续，元素的存放顺序及位置都可以以任意顺序进行，原来相邻的元素存放到计算机内存后不一定相邻。元素关系：为了从一个元素找下一个元素增加一个存储下一个元素地址的指针。特点：不能像顺序表一样随机访问，而只能按顺序访问。常用的链表有单链表、循环链表和双向链表、多重链表等。8．定义的链表时，若只含有一个指向直接后继的指针域，称这样的链表为单链表或线性链表。线性链表中的结点结构可描述为:中data域用来存放结点本身信息，类型由具体问题而定，设定为elemtype类型，表示某一种具体的已知类型。next域用来存放下一个元素地址。9．①②插入结点时的指针修改sabxp③10．单链表上的插入运算建立新的数据结点。找到插入位置前的结点。改变指针指向。11．单链表上的删除运算找到删除结点前一个结点（这就要求有两个指针）改变指针指向释放结点空间12．栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一pqa1xa2删除结点的指针修改种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。13．第1个进栈的元素在栈底最后一个进栈的元素在栈顶第1个出栈的元素为栈顶元素最后一个出栈的元素为栈底元素栈是一种后进先出(LastInFirstOut)的线性表，简称为LIFO表。根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。13．仅允许在一端进行插入，另一端进行删除的线性表，称为队列(queue)。允许插入的一端称为队尾(rear)，允许删除的一端称为队头（frort）。队列是一种先进先出（FirstInFirstOut）的特殊线性表，或称FIFO表。若队列中没有任何元素，则称为空队列，否则称为非空队列。14．表尾称作队尾，表头称为队头；a1为队头元素，an为队尾元素；在表尾插入元素操作，称为入队操作；在表头删除元素的操作，称为出队操作；元素按a1,a2,a3,...an顺序入队，第1个入队的元素为a1,最后一个入队的元素是an第1个出队的元素为a1,最后一个出队的元素是an队列具有先进先出的特点，所以又称为先进先出表（FIFO表）15．顺序队列常常会出现“假溢出”现象。虽然队列中还有一定的存储空间，但因为front指针与rear指针均向同一个方向移动，导致该队列不能再进行入队操作。为了避免“假溢出”，可以这样规定，一旦rear指针（或front指针）指向了存储空间的末尾位置，如果此时再进行入队（或出队）操作，则将相应的指针平移到数组的起始位置，即是将队列假想为一个循环的环状空间，我们称之为循环队列。出队时应先判----队是否空?队空条件：q.rear==q.front不空，则出队。进队时应先判----队是否满?队满条件：((q.rear+1)%maxsize)==q.front不满，则进队。16．字符串是一种特殊的线性表，表中的元素类型刚好都是字符型的。串(string)是由零个或多个字符组成的有限序列，记作s=“a1a2…an”，其中s为串的名字，用成对的双引号括起来的字符序列为串的值，但两边的双引号不算串值，不包含在串中。ai(1≤i≤n)可以是字母、数字或其它字符。n为串中字符的个数，称为串的长度。空串：不含任何字符的串称为空串，它的长度n=0，记为s=“”。空白串：含有一个空格的串，称为空白串，它的长度n=1，记为s=“”或s=“ø”。子串、主串：若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。除串本身以外的子串都称为真子串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，则s1为s2的子串，s2相对于s1为主串。17．一维数组：可以看成是一个线性表，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。18．二维数组中的每一个元素最多可有二个直接前驱和两个直接后继（边界除外），故是一种典型的非线性结构。行优先顺序(m个)：也称为低下标优先或左边下标优先于右边下标。(a00a01a02……a0n-1)(a10a11a12……a1n-1)……(ai0ai1ai2…aij-1aijaij+1…ain-1)……(am-10am-11am-112……am-1n-1)列优先顺序（n个）：也称为高下标优先或右边下标优先于左边下标。(a00a10a20……am-10)(a01a11a21……am-11)……(a0ja1ja2j…ai-1jaijai+1j…am-1j)……(a0n-1a1n-1a2n-1……am-1n-1)第三章树1．仅有一个没有前趋的结点称为根结点。除根结点外其它结点都有且仅有一个直接前驱，但可以有0个或多个直接后继，这样的逻辑结构称之为树。树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n0，则：有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱。除根结点以外的其它结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，每个集合T