赞
踩
抽象数据类型(abstract data type,ADT)是一些操作的集合。
对诸如表、集合、图和它们的操作一起可以看作是抽象的数据类型,就像整数,实数和布尔量是数据类型一样。整数,实数和布尔量有与他们相关的操作,而抽象数据类型也有与它们自己相关的操作。
Print List和Make Empty是常用的操作,分别用来输出和清空。
Find 用来返回关键字首先出现的位置(用数组来解释就是查找对应数组的下标)。
Insert 和 Delete一般是从表的某个位置插入和删除某个关键字。(对应在数组中的解释就是在数组中插入和删除某个元素)。
对于表这样的线性结构,Print List、Make Empty、Find等操作所需要的时间同样也是线性的,通常情况只需要用一个循环遍历就能实现操作,但对于Insert 或Delete等操作,对于时间的花费则是及其昂贵的,例如在位置x插入一元素,首先需要将整个数组后移一个位置以空出空间来,然后再在这个空出来的空间进行插入操作,它对时间的要求就变得大起来,并且表的大小还必须事先已知,所以简单数组一般不用来实现表这种结构。为此,我们引出了链表。
为了避免插入和删除的时间开销,我们需允许表可以不连续存储,否则表的部分或全部需要整体移动。
图1-1 线性表的存储方式
对于一个线性存储的方式,我们的Insert或Delete等其他操作对其内存的访问会十分麻烦。
图1-2 一个链表
而对于一个链表,是由一系列不必在内存中相连的结构组成,每一个结构均含有表元素和指向包含该元素下一个表结构的指针(我们称之为Next指针),它们也叫数据域和指针域。最后一个表结构的Next指针指向NULL,ANSI C规定NULL为零。(图1-2中箭头表示的就是Next指针)
为了执行Print List或Find等操作,我们只要将一个指针传递到该表的第一个元素,然后用一些Next指针穿越该表即可。这个指针就是头指针,头指针指向的表结构叫做头节点,头节点一般不存储数据,其他的表结构叫做节点,最后一个节点的Next指针指向NULL。
有了链表之后,我们的Insert操作可以通过修改一个指针来实现。
图1-3 删除链表中的元素
如图1-3,我们只用将指向要删除的节点的指针重新指向该节点的下一个节点,就能实现删除,简单来说就“孤立”要删除的节点。
而要向链表中插入一个新的节点,我们要先用一次malloc函数从系统中申请一块新的内存空间,并在此后进行俩次指针调整(先将新节点的Next指针指向要插入位置的下一个节点,再将要插入位置的上一个节点的Next指针指向新节点,如图1-4。
图 1-4 向链表中插入一个新的元素
对于插入或删除数据越频繁的操作,单链表的效率就越明显。
有时候以倒序扫描链表很方便。标准化实现方法此时无能为力,然而解决方式却很简单,只要在数据结构上附加一个域,使它包含指向前一个节点的指针即可。如图1-5。
图 1-5 双向链表
让链表的最后一个节点指向头节点而不是NULL的链表就是循环链表,它可以有头节点也可以没有,并且还可以是双向链表(第一个节点的前驱元指针指向最后的单元)。
图 1-6 双向循环链表
本文部分思路来自《数据结构与算法分析——C语言描述》,文中引用的图片均来自百度搜索,如有侵权请及时联系我
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。