数据结构域算法设计-第六单元基本数据结构教案

《数据结构域算法设计-第六单元基本数据结构教案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六单元　基本数据结构数据结构就是数据之间的结构或关系。主要研究数据之间的关系的。有一个必须要知道的等式：程序设计=算法+数据结构。合理的组织数据，才能让算法更高效的运行起来。数据结构是为算法服务的，所有的题目，必须要先知道算法，再根据算法，选择相应的数据结构。也就是说：算法主要对数据进行各种操作，而操作之前，数据之间的关系必须建立起来。线性表是最基本的数据结构，每一个元素只有一个前驱和一个后继，表中的元素与元素之间类似于一条线，叫线性表。线性表有两种结构，一种是顺序结构，就是我们用的数组，一种是链式结构。6.1　

2、线性表（顺序结构）线性表是最基本的数据结构，可以用普通的一维数组存储。你可以让线性表可以完成以下操作（代码实现很简单，这里不再赘述）：1.返回元素个数。也就是数组中有多少个元素。2.判断线性表是否为空。3.得到位置为p的元素。4.查找某个元素。5.插入、删除某个元素：务必谨慎使用，因为它们涉及大量元素的移动。操作4和5的时间复杂度都是O(n)的。6.2　线性表（链式结构）链表（Linkedlist）是一种常见的数据结构，是动态数据结构的最基本形式。链式结构这里引用的是指针写法，指针作为编程语言必学的部分，是必须要学

3、习的，建议有兴趣的人自行百度。我们这里给出指针写法的链式结构线性表的基本写法，仅作了解，竞赛中我们用静态链表的写法，这样的写法在比赛中，更容易调试，更容易避免低级失误。具体图例和详细讲解会在静态链表里阐述。(1)单链表!（作为了解，不需要代码实现。）1.定义：下面有一个空链表，表头叫head，并且表内没有任何元素。structnode{intvalue;node*next;}arr[MAX];inttop=-1;node*head=NULL;2.内存分配：在竞赛中不要用new，也不要用malloc、calloc——

4、像下面一样做吧。#defineNEW(p)p=&arr[++top];p->value=0;p->next=NULLnode*p;NEW(head);//初始化表头NEW(p);//新建结点3.插入：把q插入到p的后面。时间复杂度O(1)。if(p!=NULL&&q!=NULL)//先判定是否为空指针。如果不是，继续。{q->next=p->next;p->next=q;}1.删除：把p的下一元素删除。时间复杂度O(1)。if(p!=NULL&&p->next!=NULL)//先判定是否为空指针。如果不是，继续。{

5、node*q=p->next;p->next=q->next;//delete(q);//如果使用动态内存分配，最好将它的空间释放。}2.查找或遍历：时间复杂度O(n)。node*p=first;while(p!=NULL){//处理value//cout<value<<'t';p=p->next;}(2)静态链表（必须掌握，图的邻接表）链表在信息学竞赛中的应用相当广泛，这是因为使用链表可以克服数组需要预先知道数据大小的缺点，充分利用计算机内存空间，实现灵活的内存动态管理。用数组模拟链表，可以简化链表的操

6、作，从而使链表更好的为我们服务。指针的作用就是存储地址。如果我们找到了替代品，就可以放弃指针了。而我们的替代品就是用数组的下标来代替存储地址。单向链表是链表中最简单的一种，一个单向链表的结点包含两个域：一个信息域和一个指针域。第一个部分保存或者显示关于结点的信息，第二个部分存储下一个结点的地址。另外，一个特殊的头指针指向链表的第一个元素，并且在最后一个结点保存一个特殊的结束标记。这种最为普通的，每个结点只有一个指针的链表叫单向链表，或者单链表，通常用在每次都只会按顺序遍历这个链表的时候（例如图的邻接表等）。我们使用

7、链表主要是要发挥链表动态分配内存空间的优势，但是在信息学竞赛中，我们基本上不需要过多考虑动态空间分配，所以，使用数组模拟链表就可以很好的实现链表数据结构。数组模拟链表，是一种半静态链表，是链表的线性存储。一个链表可以用一对数组或一个记录数组表示（上面的定义是以记录数组为例的）。链表中的每个结点，也就是数组中的每个元素，都是一个记录，它像链表一样也有两个数据域：信息域和指针域，分别保存该元素信息value和下一个结点在数组中的位置next（整型）。另外，我们需要一个特殊的头指针指向第一个元素，即记录第一个元素在数组中

8、的位置（整型）；类似地，可以将最后一个结点的next记为-1作为结束标记。这样插入，删除，遍历等，都可以归结到数组操作了，这就比链式存储容易多了，却不会丧失链表快速插入删除的优势。1.我们先看一下它的定义，形式如图所示：structnode{intvalue;intnext;//表示下一元素在arr中的下标}arr[MAX];inttop;//top来记录链