基本数据结构剖析

《基本数据结构剖析》由会员分享，可在线阅读，更多相关《基本数据结构剖析（26页珍藏版）》请在金锄头文库上搜索。

1、基本数据结构,线性表（Linear list）是最简单且最常用的一种数据结构。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。 线性表的逻辑结构和存储结构，以及线性表的基本运算,线性表,通信录课程设计实例,软件功能要求： 1.通信录具有新增联系人信息 2.通信录能够删除联系人信息 3.通信录能够查询到相应的联系人信息 4.能够修改联系人信息 软件核心数据结构联系人信息 学号、姓名、年龄、性别、电话、地址邮箱、QQ号、身份证号、备注等,2 . 线性表的基本运算(6种) 数据结构的运算

2、是定义在逻辑结构层次上的，而运算的具体实现则是建立在存储结构上的。 (1) 初始化线性表Initlist(L) 将线性表L置为空表。 (2) 求线性表的长度Getlen(L) 求解并返回线性表所含元素的个数n。若线性表为空，则返回整数0。 (3) 按序号取元素Getelem(L,i) 读取线性表L第i个数据元素，要求满足1iGetlen(L)。,(4) 按值查找Locate(L,x) 在线性表L中查找值为的数据元素，若查找成功则返回第一个值为x的元素的序号或地址; 否则，在L中未找到值为的数据元素，返回一特殊值（例如0），表示查找失败。 (5) 插入元素Inselem (L,i,x) 在线性表

3、L的第 i 个位置上插入一个值为 x 的新元素，这样使原序号为 i , i+1, ., n 的数据元素的序号变为 i+1,i+2, ., n+1，要求1iGetlen(L)+1，插入后原表长增1。 (6) 删除元素Delelem(L,i) 在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,., n 的元素变为序号i, i+1,.,n-1，要求1iGetlen(L)，删除后表长减。,2.2 线性表的顺序结构及运算实现,线性表有两种基本的存储结构：顺序存储结构和链式存储结构。,1.线性表的顺序存储结构,顺序表具有以下两个基本特点： (1) 线性表的所有元素所占的存储空间是连续的

4、。 (2) 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间（字节数）相同。因此，要在此结构中查找某一个元素是很方便的，即只要知道顺序表首地址和每个数据元素在内存所占字节的大小，就可求出第i个数据元素的地址。,在具体实现时，一般用高级语言中的数组来对应连续的存储空间。设最多可存储MaxLen个元素，在C语言中可用数组dataMaxLen来存储数据元素，为保存线性表的长度需定义一个整型变量length。线性表的第l，2，n个元素分别存放在此数组下标为0，1，length-1数组元素中，如下图所示,这样，一个线性表的

5、顺序存储结构需要两个分量。为体现数组data和length之间的内在联系，通常将它们定义在一个结构类型中。此处的元素类型用ElemType来表示。 综上所述，在C语言中，可用下述类型定义来描述顺序表： #define MaxLen 100 /线性表的容量 typedef int ElemType /在实际应用中，将ElemType定义成实际类型 typedef struct ElemType dataMaxLen; /定义存储表中元素的数组 int length; /线性表的实际长度 sqList; sqList L; /定义表结构的变量,2.3 线性表的链式存储和运算实现,线性表的顺序表示的

6、特点是用物理位置上的邻接关系来表示结点间的逻辑关系，故可以随机存取表中的任一结点；但在插入和删除操作时需移动大量的结点。 为避免大量结点的移动，介绍线性表的另一种存储方式: 链式存储结构，简称链表(Linked List)。 线性表的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储线性表的数据元素。对线性表中的每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，称这种存储单元为结点。 链式存储方式可用于表示线性结构，也可用于表示非线性结构。,2.3.1链表的存储结构,链式存储结构是利用任意的存储单

7、元来存放线性表中的元素，存储数据的单元在内存中可以连续，也可以零散分布。 由于线性表中各元素间存在着线性关系，每一个元素有一个直接前驱和一个直接后继。为了表示元素间的这种线性关系，在这种结构中不仅要存储线性表中的元素，还要存储表示元素之间逻辑关系的信息。所以用链式存储结构表示线性表中的一个元素时至少需要两部分信息，除了存储每一个数据元素值以外，还需存储其后继或前驱元素所在内存的地址。两部分信息一起构成链表中的一个结点。结点的结构如下所示。,C语言采用结构数据类型描述结点如下： typedef struct LNode ElemType data; /结点值 struct LNode *next

8、; /存储下一个结点的地址 LNode,*LinkList; LNode *head;,在此结构中，用数据域data存储线性表中数据元素 。指针域next，它给出下一个结点的存储地址。结点的指针域将所有结点按线性表的逻辑次序链接成一个整体，形成一个链表。由于链表中第一个结点没有直接前驱，所以必须设置一个头指针head存储第一个结点的地址。最后一个结点没有直接后继，其指针域应为空指针，C语言用NULL或0来表示，在图中表示为“”。 假设有一个线性表为（A,B,C,D,E），存储空间具有10个存储结点，该线性表在存储空间中的存储情况如图2-7(a)所示。,图 2-7 链表结构示意图,由于链表是一种

9、动态管理的存储结构，每个结点需动态产生。 1初始化链表initlist(L)的实现 建立一个空的带头结点的单链表。所谓空链表就是指表长为0的表。在这种情况下，链表中没有元素结点。但应有一个头结点，其指针域为空。,void initlist(LinkList *L) *L=(LNode *)malloc(sizeof(LNode); (*L)-next=NULL; ,在函数调用时，指针L指向的内容发生了变化，为使得调用函数中头指针变量head获得头结点地址，需传递头指针变量的地址给initlist()函数，而函数中定义二级指针变量L接受该地址值，从而返回改变后的值。,请大家完成如下操作,(1)

10、初始化线性表Initlist(L) (2) 求线性表的长度Getlen(L) (3) 按序号取元素Getelem(L,i) (4) 按值查找Locate(L,x) (5) 插入元素Inselem (L,i,x) (6) 删除元素Delelem(L,i),2.3.3 循环链表 在单链表中，最后一个结点的指针域为空（NULL）。访问单链表中任何数据只能从链表头开始顺序访问，而不能进行任何位置的随机查询访问。如要查询的结点在链表的尾部也需遍历整个链表。所以单链表的应用受到一定的限制。 循环链表(Circular Linked List)是另一种形式的链式存储结构。它将单链表中最后一个结点的指针指向链

11、表的头结点，使整个链表头尾相接形成一个环形。这样，从链表中任一结点出发，顺着指针链都可找到表中其它结点。循环链表的最大特点是不增加存储量，只是简单地改变一下最后一个结点的指针指向，就可以使操作更加方便灵活。图2-13是循环链表的存储结构示意图。,图 2-13 循环链表结构示意图,带头结点的单循环链表的操作算法和带头结点的单链表的操作算法很相似，差别仅在于算法中的循环条件不同。在循环单链表上实现上述基本运算的改动如下： 初始化链表initlist(L) 创建的头结点指针域next不为空，而是指向自身，L-next=L 其它自己完成,2.3.4 双向链表,双向链表结点的定义如下： typedef

12、struct DNode ElemType data; struct DNode *prior; struct DNode *next; Dnode,*DuLinkList; 结点的结构如图2-15所示。,单链表只有一个指向后继的指针来表示结点间的逻辑关系。故从任一结点开始找其后继结点很方便，但要找前驱结点则比较困难。双向链式是用两个指针表示结点间的逻辑关系。即增加了一个指向其直接前驱的指针域，这样形成的链表有两条不同方向的链，前驱和后继，因此称为双链表。在双链表中，根据已知结点查找其直接前驱结点可以和查找其直接后继结点一样方便。这里也仅讨论带头结点的双链表。仍假设数据元素的类型为ElemTy

13、pe。,图2-15 双向链表结点结构图,图2-16 带头结点的双向链表,在图2-16中，如果某指针变量p指向了一个结点，则通过该结点的指针p可以直接访问它的后继结点，即由指针p-next所指向的结点；也可以直接访问它的前驱结点，由指针p-prior指出。这样在需要查找前驱的操作中，就不必再从头开始遍历整个链表。这种结构极大地简化了某些操作。,在双向链表中也可采用与单链表类似的方法，用头指针标识链表的开头，也可以带头结点。在双向链表中，每个结点都有一个指向直接前驱结点和一个指向直接后继结点的指针。链表中第一个结点的前驱指针和最后一个结点的后继指针可以为空，不做任何指向，这是简单的双向链表。,结点

14、的插入过程如图2-17所双向链表示：,注意：在图2-17中，关键语句指针操作序列既不是唯一也不是任意的。操作必须在操作之前完成，否则*p的前驱结点就丢掉了。,图2-17 双链表插入结点示意图,图2-18 双链表的删除结点示意图在双向链表中找到删除位置的前一个结点，由p指向它，q指向要删除的结点。删除操作如下：将*p的next域改为指向待删结点*q的后继结点；若*q不是指向最后的结点，则将*q之后结点的prior域指向*p。 注意：在双向链表中进行插入和删除时，对指针的修改需要同时修改结点的前驱指针和后继指针的指向。,【解】算法思路：扫描双向链表DL，查找链表DL的第i个位置并在第i个位置之后插

15、入元素x。 status ListInsert_DuL(DuLinkList DL,int i, ElemType x) Dnode *s; if(!p=get_linklist(DL,i) /p指向第i个元素结点， return ERROR; /p=NULL表示第i个元素不存在 if(!(s=(DulinkList)malloc(sizeof(Dnode) return OVERFLOW; s-data=x; /为新元素建结点 s-next=p-next; /插入 s-prior=p; p-next-prior=s; p-next=s return OK; ,2.3.5循环双链表 与循环单链

16、表一样，也可以使用循环双链表。循环单链表和循环双链表可通过尾结点找到头结点，也常作为编辑器的数据结构，尤其是循环双链表。 图2-19是带头结点且有n个结点的循环双链表。,图2-19 带头结点且有n个结点的循环双链表,在循环双向链表中，对于一些只涉及一个方向指针且存储结构不变的操作（如查找、求表长等），其算法实现与单链表相同。在进行插入或删除等结构变化的操作时，与双链表相同，必须同时修改两个方向上的指针，操作过程比单链表复杂。 【例2-8】编写从循环双向链表中删除第i(i1)个结点的算法。 【解】算法思想：扫描循环双向链表，查找第i个结点。若找到，修改其前趋结点的next域和后继结点的prior域，删除第i个（1i表长）结点，返回OK；否则返回ERROR。当删除的结点是链表中的第一个结点时，除上述操作外，还需要修改头指针。