数据结构导论知识点(34页).doc

《数据结构导论知识点(34页).doc》由会员分享，可在线阅读，更多相关《数据结构导论知识点(34页).doc（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数据结构导论知识点-第 34 页数据结构导论知识点第一章 概论数据结构：是相互之间存在一种或多种关系的数据元素的集合。和该集合中数据元素之间的关系组成。数据结构包括数据的逻辑结构、数据的存储结构和数据的基本运算。简单地说，数据结构是计算机组织数据和存储数据的方式。更进一步地说，数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的操作。合理的数据结构可降低程序设计的复杂性，提高程序执行的效率。1.1 引言计算机解决一个具体问题时，一般需要经过以下几个步骤：从具体的问题抽象出一个适当的数学模型；设计一个求解该数学模型的算法；用某种计算机

2、语言编写实现该算法的程序，调试和运行程序直至最终得到问题的解答。数据的逻辑结构：数据和数据的组织方式称为数据的逻辑结构。为了能用计算机加工处理，逻辑结构还必须转换为能被计算机存储的存储结构。1976年瑞士计算机科学家尼克劳斯维尔特提出公式：算法+数据结构=程序。该公式简洁的描述了数据结构和程序之间关系。1.2 基本概念和术语1.2.1 数据、数据元素和数据项数据：所有被计算机存储、处理的对象。数据元素：简称元素（又称为结点），数据的基本单位，在程序中作为一个整体而加以考虑和处理。数据元素是运算的基本单位，通常具有完整确定的实际意义。数据元素由数据项组成。数据项：在数据库中数据项又称为字段或域，

3、是数据的不可分割的最小标识单位，组成数据元素。关系：数据、数据元素和数据项实际上反映了数据组织的三个层次，数据可由若干个数据元素组成，而数据元素又可由若干个数据项组成。表格（逻辑结构），行=记录=数据元素，列=数据项。1.2.2 数据的逻辑结构数据的逻辑结构：是指数据元素之间的逻辑关系。逻辑关系：是指数据元素之间的关联方式或邻接关系。逻辑结构示意图中的小圆圈称为结点，一个结点代表一个数据元素（记录）。根据数据元素之间关系的不同特性，通常有集合、线性结构、树形结构和图结构四类基本逻辑结构，反映了四类基本的数据组织形式。四类基本逻辑结构：集合：集合中任何两个结点之间都没有邻接关系，组织形式松散。线

4、性结构：线性结构中结点按逻辑关系依次排列形成一条“链”，结点之间一个一个依次相邻接。树形结构：树形结构具有分支、层次特性，其形态有点像自然界中的树，上层的结点可以和下层多个结点相邻接，但下层结点只能和上层的一个结点相邻接。图结构：图结构最复杂，任何两个结点都可以邻接。数据的逻辑结构与存储无关，独立与计算机。1.2.3 数据的存储结构数据的逻辑结构在计算机中的实现称为数据的存储结构（或物理结构）。一个存储结构包括两个部分：存储数据元素。数据元素之间的关联方式。表示数据元素之间的关联方式主要有：顺序存储方式：是指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的相对位置来表示数据元素之间的

5、逻辑关系。（使用数组，内存地址连续）链式存储方式：是指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。索引存储方式。散列存储方式。一种逻辑结构可以采用一种或几种存储方式来表达数据元素之间的逻辑关系，相应的存储结构称为给定逻辑结构的存储实现或存储现象。1.2.4 运算运算是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。在每个逻辑结构上，都定义了一组基本运算，包括：建立、查找、读取、插入和删除等。线性表、栈和队列中的元素具有相同的逻辑结构（即线性结构），但有不同的运算集，是不同的数据结构。1.3 算法及描述运算的实现是

6、指该运算的算法。算法是计算机科学的一个基本概念，也是程序设计的一个基本概念。一个算法规定了求解给定问题所需的处理步骤及其执行顺序，使给定问题在有限的时间内被求解。算法可以用某种语言描述。1.4 算法分析评价算法好坏的因素包括：正确性：能正确的实现预定的功能，满足具体问题的需要。易读性：易于阅读、理解和交流，便于调试、修改和扩充。健壮性：即使输入非法数据，算法也能适当的做出反应或进行处理，不会产生预料不到的运行结果。时空性：一个算法的时空性是指该算法的时间性能（或时间效率）和空间性能（或时间效率），前者是算法包含的计算量，后者是算法需要的存储量。1.4.1 时间复杂度估算算法的计算量，可将基本操

7、作次数作为该算法的时间度量。（执行次数最多的语句的执行次数。）假如问题的输入规模为n，一般情况下，一个算法的计算量是问题规模n的函数，一个算法的时间复杂度是算法输入规模的函数。常见算法时间复杂度的阶数有常数O(1)（最优的时间复杂度，与输入规模n无关）、对数阶O(log2n)、线性阶O(n)、多项式阶(平方阶)O(nC)、和指数阶O(Cn)，C为大于1的正整数。通常认为，时间复杂度具有指数阶的算法是实际不可计算的，而阶数低于平方阶的算法是高效的。O(1)O(log2n)O(n)O(nC)O(Cn)。最坏时间复杂度：对相同输入数据量的不同输入数据，算法时间用量的最大值。平均时间复杂度：对所有相同

8、输入数据量的各种不同输入数据，算法事件用量的平均值。1.4.2 空间复杂度一个算法的空间复杂度定义为该算法所耗费的存储空间。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在执行期间所需要的存储空间量包括：程序代码所占用的空间。输入数据所占用的空间。辅助变量所占用的空间。在估算法算法空间复杂度时，一般只需要分析辅助变量所占用的空间。第二章 线性表2.1 线性表的基本概念线性表（Linear List）是一种线性结构，是由n（n0）个数据元素组成的有穷数列，数据元素又称为结点。结点个数n称为表长。a1称为起始结点，an称为终端结点，ai称为ai+1的直接前驱，ai+1称为a

9、i的直接后继。线性表的基本特征：线性表中结点具有一对一的关系，如果结点数不为零，则除起始结点没有直接前驱，除终端结点没有直接后继，其他每个结点有且仅有一个直接前驱，一个直接后继。线性表的基本运算及功能描述：初始化Initiate(L)：建立一个空表L=()，L不含数据元素。求表长Length(L)：返回线性表L的长度。读表元素Get(L,i)：返回线性表第i个数据元素，当i不满足1iLength(L)时，返回一特殊值。定位Locate(L,x)：查找线性表中数据元素值等于x的结点序号，若有多个数据元素值与x相等，运算结果为这些结点中序号的最小值，若找不到该结点，则运算结果为0。插入Insert

10、(L,x,i)：在线性表L的第i个数据元素之前插入一个值为x的新数据元素，参数i的取值范围是1in+1。插入后线性表L表长度加1。删除Delete(L,i)：删除线性表L的第i个数据元素ai，i的有效取值范围是1in。删除后线性表L表长度减1。2.2 线性表的顺序存储顺序表是最简单的一个存储方式。2.2.1 线性表顺序存储的类型定义线性表顺序存储的方法是：将表中的结点依次存放在计算机内存中一组连续的存储单元中，数据元素在线性表中的邻接关系决定它们在存储空间中的存储位置，即逻辑结构中相邻的结点其存储位置也相邻。用顺序存储实现的线性表称为顺序表。一般使用数组来表示顺序表。假定线性表的数据结构的类型

11、是DataType，顺序表的结构定义，学生档案信息表的顺序存储实现：const int Maxsize=7;/预先定义一个足够大的常量，作为数组的最大长度typedef struct /定义一个结构体类型int num; /学号char name8; /姓名char sex2; /性别int age; /年龄int score; /入学成绩DataType; /定义结点类型typedef structDataType dataMaxsize;/存放数据的数组int length; /顺序表的实际长度SeqList; /顺序表类型名为SeqListSeqList student; /定义stud

12、ent为一个顺序表2.2.2 线性表的基本运算在顺序表上的实现（插入、删除、定位的最优、最坏、平均时间复杂度都是O(n)）1.插入顺序表的插入运算InsertSeqlist(SeqList L, DataType x, int i)是指在顺序表的第i（1in+1）个元素之前，插入一个新元素x。使长度为n的线性表变为n+1的线性表。插入算法的具体步骤：首先将结点aian依次向后移动一个元素的位置，空出第i个数据元素的位置，然后将x置入该该空位，表长加1。插入算法描述：void InserSeqlist(SeqList L, DataType x, int i) /将元素x插入到顺序表L的第i个数

13、据元素之前if (L.length=Maxsize) exit(“表已满”);if (iL.length+1) exit(“位置错”); /检查插入位置是否合法for(j=L.length;j=i;j-) /初始i=L.length L.dataj=L.dataj-1; /依次后移L.datai-1=x; /元素x置入到下标为i-1的位置L.length+; /表长度加1顺序表中结点的物理顺序和线性表中结点的逻辑顺序保持一致。顺序表插入算法的元素比较和移动的次数是（n-i+1）次，平均移动次数是n/2，时间复杂度为O(n)。2.删除删除运算DeleteSeqlist(SeqList L, in

14、t i)是指将线性表的第i（1in）个数据元素删去，使长度为n的线性表变为n-1的线性表。当i=n时，直接将表长度减1即可。删除算法的基本步骤是：结点aian依次向左移动一个元素位置，覆盖掉被删结点ai。表长度减1，不考虑溢出，只判断参数i是否合法。删除算法描述：void DeleteSeqlist(SeqList L, int i) /删除顺序表L中的第i个数据结点if (iL.length+1) exit(“非法位置”);/检查插入位置是否合法for(j=i;jL.length+1)(L.datai!=x);/在顺序表中查找值为x的结点 i+;if(jnext=NULL;return he

15、ad;在算法中,变量head是链表的头指针，指向新创建的结点，即头结点。一个空单链表仅有一个头指针，它的指针域为NULL。求表长在单链表存储结构中，线性表的表长等于单链表中数据元素的结点个数，即除了头结点以外的结点的个数。单链表的求表长描述：通过结点的指针域来从头至尾访问每一个结点。int LengthLinklist(LinkList head) /求单链表表head的长度Node *p=head; /p是工作指针，初始时p指向头结点int cnt = 0; /计数器置初值while(p-next!=NULL)p=p-next; /指针移动到下一个结点cnt+;return cnt; /返回

16、表长读表元素给定一个序列号i，查找线性表的第i个元素。单链表的读表元素描述：从头指针出发，一直往后移动，直到第i个结点。Node *GetLinklist(LinkList head, int i)/在单链表head中查找第i个元素结点。找到返回指向该结点的指针，否则返回NULLNode *p; /p是工作指针p=head-next; /初始时，p指向首结点int c=1;while(cnext; c+;if(i=c) return p; /找到第i个结点else return NULL; /in，i值不合法，查找失败注意：p!=NULL在这里作为判断是否以遍历整个链表的条件，不可遗漏。定位定

17、位运算又称为安值查找。线性表的定位运算，是对给定表元素的值，找出这个元素的值。在单链表实现中，则是给定一个结点的值，找出这个结点是单链表的第几个结点。单链表的定位运算描述：从头至尾访问链表，直至找到需要的结点，返回其序列号；若未找到，返回0。int LocateLinklist(LinkList head,DataType x) /求单链表表head中第一个值等于x的结点的序号，若不存在这种结点，返回结果0Node *p=head; /p是工作指针p=p-next; /初始时p指向头结点int i = 0; /i代表结点的序号，这里置初值为0while(p!=NULLp-data!=x) /访

18、问链表i+;p=p-next;if(p!=NULL) return i+1;else return 0;插入单链表的插入运算是将值为x的元素插入到链表head的第i个结点之前。单链表的插入运算描述：先找到链表的第i-1个结点q，生成一个值为x的新结点p，p的指针域指向q的直接后继结点，q的指针域指向p。void InserLinklist(LinkList head,DataType x,int i) /在单链表head的第i个数据元素结点之前插入一个值为x的新结点Node *p,*q;if (i=1) q=head;else q=GetLinklist(head,i-1); /找第i-1个数

19、据元素结点if (q=NULL) /第i-1的结点不存在exit(“找不到插入的位置”); elsep=malloc(sizeof(Node);p-data=x; /生成新结点p-next=q-next; /新结点链域指向*q的后继结点q-next=p; /修改*q的链域单链表的插入运算操作p-next=q-next和q-next=p语句执行顺序不能颠倒。删除单链表的删除运算是给定一个值i，将链表中第i个结点从链表中移除，并修改相关结点的指针域，以维持剩余结点的链接关系。单链表的删除运算描述：将ai结点移除后，需要修改该结点的直接前驱结点ai-1的指针域，使其指向移除结点ai的直接后继结点ai

20、+1。void DeleteLinklist(LinkList head,int i) /在单链表head中删除第i个数据结点Node *q;if (i=1) q=head;else q=GetLinklist(head,i-1); /先找待删除结点的直接前驱if (q!=NULLq-next!=NULL) /若直接前驱存在且待删除结点存在p=q-next; /p指向待删除结点q-next=p-next; /移出待删除结点free(p); /释放以移出结点p的空间else exit(“找不到要删除的结点”); /结点不存在free(p)是必不可少的，当一个结点从链表中移出后，若不释放它的空间，

21、它将变成一个无用的结点，并一直占用着系统内存空间，其他程序将无法使用这块空间。2.4 其他运算在单链表上的实现2.4.1 建表根据线性表元素的邻接关系，建立该线性表的单链表。建立含头结点的单链表：首先建立带头节点的空表。其次建立一个新结点，然后将新结点链接到头结点之后，这个结点为尾结点（首结点）。最后重复建立新结点和将新结点链接到表尾这两个步骤，直到线性表中所有元素链接到单链表中。1.建立单链表方法一：通过已实现的初始化和插入算法来实现，依次增大插入位置i，使新的结点链入到链表中。每次插入都从表头开始查找，比较浪费时间。算法InserLinklist主要部分是找到第i个位置，然后将新结点插入，

22、计算量约等于i。线性表有n个元素，插入位从1到n，方法一算法的计算量约为n(n+1)/2，时间复杂度为O(n2)。LinkList CreatLinkList1()/通过调用初始化和插入算法实现建表算法。假定0是输入结束标志LinkList head;int x,i;head=InitiateLinkList(); /建立空表i=1; /置插入位置初值scanf(“%d”,x); /读入第一个数据元素，x为整型while(x!=0) /输入的不是结束标志时继续插入InserLinklist(head,x,i); /将输入插入到head表尾i+; /修改插入位置scanf(“%d”,x); /读

23、下一个元素return head;2.建立单链表方法二：每次把新结点链接到链尾，用一个指针指向尾结点，为下一个新结点指明了插入位置。时间与元素个数成正比，时间复杂度为O(n)。用方法二建立的链表，数据顺序与输入顺序相同。LinkList CreatLinkList2()/q是一个LinkList类型的变量，用来指示链入的位置LinkList head;Node *q,*t;int x;head=malloc(sizeof(Node); /生成头结点q=head; /尾指针置初值scanf(“%d”,x); /读入第一个数据元素，x为整型while(x!=0) /输入的不是结束标志时继续链入t=

24、malloc(sizeof(Node);t-data=x; /生成一个新结点q-next=t; /新结点链入q=t; /修改尾指针q，指向新结点scanf(“%d”,x); /读下一个元素q-next=NULL; return head;3.建立单链表方法三：将新增加的结点插入到头结点之后，第一个数据结点之前，称为前插操作。时间复杂度为O(n)。用方法三建立的链表，数据顺序与输入顺序相反。LinkList CreatLinkList3()LinkList head;Node *p;int x;head = malloc(sizeof(Node); /生成头结点head-next = NULL;

25、scanf(“%d”,x);while(x) /x=0时结束输入p = malloc(sizeof(Node);p-data = x;p-next = head-next; /前插：插入到链表的第一个结点处head-next = p;scanf(“%d”,x);return head;2.4.2 删除重复节点设计算法删除重复结点，只保留结点序号最小的那个结点。用链表作为存储结构，算法描述：void PurgeLinkList(LinkList head) /删除表head中多余的重复结点 Node *p,*q,*r; q = head-next; /q指示当前检查结点的位置，置其初值指向首结点

26、 while(q!=NULL) /当前检查结点*q不是尾结点时，寻找并删除他的重复结点 p = q; /工作指针p指向*q while(p-next!=NULL) /当*p的后继结点存在时，将其数据域与*q数据域比较 if(p-next-data=q-data) /若*(p-next)是*q的重复结点 r=p-next; /r指向待删结点 p-next=r-next; /移出结点*(p-next),p-next指向原来*(p-next)的后继结点 free(r); else p=p-next; /否则，让p指向下一个结点 q=q-next; /更新检查结点为了便于删除操作，P指针始终指向“当前

27、比较结点”的前驱结点。2.5 其他链表2.5.1 循环链表在单链表中，如果让最后一个结点的指针域指向第一个结点可以构成循环链表。在循环链表中，从任一结点出发能够扫描整个链表。常见的循环链表：带头结点的非空循环链表；带头结点的空循环链表；设立尾指针的非空循环链表；设立尾指针的空循环链表。（头指针head；尾指针rear，首结点表示为：rear-next-next）2.5.2 双向循环链表双向循环链表与单链表类似，用类C语言描述如下：struct dbnode Datatype data; struct dbnode *prior,*next;typedef struct dbnode *dbpo

28、inter;typedef dbpointer DLinkList;在单链表的每个结点中在设置一个指向其直接前驱结点的指针域prior，这样每个结点有两个指针，结点结构：|prior|data|next|。头结点的prior指向最后一个结点，最后一个结点的next指向头结点，由这种结点构成的链表称为双向循环链表。单链表找直接后继结点的时间复杂度是O(1)，双向循环链表是一种对称结构，找前驱结点和后继结点的时间复杂度均为O(1)。双向循环链表适合应用在需要经常查找结点的前驱和后继的场合。双向循环链表的对称性可以用下列等式表示：p=p-prior-next=p-next-prior结点p的前驱结点

29、的next和后继结点的prior都指向结点p。1.删除在双向循环链表中删除结点时，设p指向待删结点，删除*p可以通过下述语句完成：p-prior-next=p-next; /p前驱结点的后链指向p的后继结点p-next-prior=p-prior; /p后继结点的前链指向p的前驱结点free(p); /释放*p的空间其中、这两个语句的执行顺序可以颠倒。2.插入在双向循环链表中，在p所指结点的后面插入一个新结点*t，需要修改四个指针：t-prior=p;t-next=p-next;p-next-prior=t;p-next=t;2.6 顺序实现与链接实现的比较顺序表优点：随机存储数据元素；缺点：

30、需要预先分配存储空间。链表优点：插入、删除方便，不需要预先分配空间；缺点：需要分配存储指针空间。第三章 栈、队列和数组3.1 栈3.1.1 栈的基本概念栈是运算受限的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的一端称为栈顶，另一端称为栈底。不含任何数据元素的栈称为空栈。处于栈顶位置的数据元素称为栈顶元素。栈的修改原则是后进先出(Last In First Out)，栈又称为后进先出线性表，简称后进先出表。栈的插入和删除运算分别称为进栈和出栈。栈的基本运算：初始化InitStack(S)：构造一个空栈S；判栈空EmptyStack(S)：若栈S为空栈，则结果为1

31、，否则结果为0；进栈Push(S,x)：将元素x插入栈S中，使x成为栈S的栈顶元素；出栈Pop(S)：删除栈顶元素。取栈顶GetTop(S)：返回栈顶元素。3.1.2 栈的顺序实现栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个元素，并用始端作为栈底。栈的顺序实现称为顺序栈。通常用一个一维数组和一个记录栈顶元素位置的变量来实现栈的顺序存储。在出栈前判断栈是否为空，如果空栈作出栈运算，会产生“下溢”。在进栈前判断是否栈满，如果栈满作进栈运算，会产生“上溢”。顺序栈用类C语言定义如下：const int maxsize=6; /顺序栈的容量typedef struct seqstack D

32、ataType datamaxsize; /存储栈中数据元素的数组 int top; /标志栈顶位置的变量 SeqStk;上述定义存放到Seqstack.h中。下面列出栈的基本运算在顺序栈上的实现算法：初始化int InitStack(SeqStk *stk) stk-top=0; return 1;判栈空EmptyStack(S)int EmptyStack(SeqStk *stk) /若栈为空，则返回值1，否则返回值0 if(stk-top=0); return 1; else return 0;进栈int Push(SeqStk *stk, DataType x) /若栈未满，元素x进栈

33、stk中，否则提示出错信息 if (stk-top=maxsize-1); /判断栈是否满 error (“栈已满”); return 0; else stk-top+; /栈未满，top值加1 stk-datastk-top=x; /元素x进栈 return 1;出栈int Pop(SeqStk *stk) if (EmptyStack(stk); /判断是否下溢（栈空） error (“下溢”); return 0; else /未下溢，栈顶元素出栈 stk-top-; /top值减1 return 1;取栈顶元素DataType GetTop(SeqStk *stk)/取栈顶数据元素，栈

34、顶数据元素通过参数返回 if (EmptyStack(stk) return NULLData; /栈空，返回NULLData else return stk-datastk-top; /返回栈顶数据元素在某些应用中，为了节省空间，让两个数据元素类型一致的栈共享一维数组空间datamax，成为双栈，两个栈的栈底分别设在数组两端，让两个栈彼此迎面增长，两个栈的栈顶变量分别为top1、top2，仅当两个栈的栈顶位置在中间相遇时(top1+1=top2)才发生“上溢”。双栈的数据结构定义为：const int max=40; /栈容量typedef struct Dbstack DataType d

35、atamax; int top1,top2; DbStk;双栈中判断上溢语句为top1+1=top2，判栈空时，两个栈不同，当top1=0时栈1为空栈，top2=max-1时栈2为空栈。3.1.3 栈的链接实现栈的链接实现称为链栈，链栈可以用带头结点的单链表实现。LS指向链表的头结点，首结点是栈顶元素，LS-next指向栈顶结点，尾结点为栈底结点。各结点通过链域的链接组成栈，由于每个结点空间都是动态分配产生，链栈不用预先考虑容量的大小。链栈用类C语言定义如下：typedef struct node DataType data; struct node *next; LkStk;将上述定义存放到Lkstack.h中。栈的基本运算在链栈上的实现算法如下：初始化void InitStack(LkStk *LS) LS=(LkStk *)malloc(sizeof(LkStk); LS-next=NULL; /建立一个空栈判栈空int EmptyStack(LkStk *LS) /若栈为空，则返回值1，否则返回值0 if(LS-next=NULL); return 1; else return 0;进栈（在进栈操作算法中采用前插操作，新增结点始终插入到头结点之后）void Push(LkStk *LS, DataType x) LkStk *temp; te