线性数据结构（线性表、链表、栈、队列、散列表）

《线性数据结构（线性表、链表、栈、队列、散列表）》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、线性数据结构（线性表、链表、栈、队列、散歹I」表）线性表基本概念线性结构是最常用、最简单的一种数据结构。线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中:存在一个唯一的被称为”第一个“的数据元素;存在一个唯_的被称为”最后一个”的数据元素；除第一个元素外”每个元素均有唯——个直接前驱;除最后一个元素外,每个元素均有唯——个直接后继。基本操作访问表的第k个节点，查看或改变它的字段内容在第k个节点之前或之后插入新节点删除第k个节点确定一个表中的节点个数基于节点的某个字段把表的节点排成递增顺序在表中查找某个字段中具有特定值

2、的一个节点把两个或多个线性表组合成一个表把一个线性表分成两个或更多的表复制一个线性表顺序存储顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。•LOC(ai+1)=LOC(ai)+Length•LOC(ai)=LOC(al)+(i-l)*Length链表排序点击标题链式存储链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表例:线性表L=(bat,cat,eat,fat,hat)其带头结点的单链表的逻辑状态和物理存储方式如图所示。基本数据结构依据上述内容，可以依据此来

3、建立链表。C版本[cpp]viewplaincopyprint?1.structListNode{2.intval;3・ListNode*next;4.ListNode(intx):val(x)next(NULL){}这里用到了结构体类型。其中，*next是指针域，用来向该结点的下一个结点；Data是一个整形变量，用来存放结点中的数据。当然，Data可以是彳曰可数据类型，包括结构体类型或类类型。C++版本[cpp]viewplaincopyprint?2・3・4・5・6・7・8-}1・publicclassListNode{intval;ListNoden

4、ext;ListNode(intx){val=x;next二null;}Java版本[java]viewplaincopyprint?1.classListNode{2.intval;3・ListNodenext;4.ListNode(intx){5.val=x;6.next=null;8.}需要注意事项1.链表结构2.写程序是都需要先判断链表为空的情况3.通过使用多个指针操纵链表一些题目•两链表求交点•链表求环•两个有序链表合并•链表求倒数第n个（中间）元素•求链表长度•链表逆序•链表节点的插入/删除链表变形循环链表循环链表是一种链式存储结构,它的最后一

5、个节点指向头结点，形成一个环。因此,从循环链表中的任何一个街角出发都能找到任何其他节点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。双向链表双向链表也叫做双链表,是链表的一种，它的每个数据节点中都有两个指针，分别指向直接后^和直接前驱。所以，从双向链表中的任意一个节点开始,都可以很方便地访问它的前驱节点和后继结点。一般,我们都构造双向循环链表。C语言线性表的双向链表存储结构[cpp]viewolaincopyprint?1・typedefstructDuLNode{2.ElemTypedata;3・structDuLNode

6、*prior*next;4.}DuLNode,*DuLinkList;带头节点的双向循环链表的基本操作一些练习题题目算法数据结构注意事Leetcode-LRUCache&SolutionN/A链表Leetcode-ReorderList&SolutionN/A链表快慢拒Leetcode-LinkedListCycle&SolutionN/A链表快慢拒Leetcode-LinkedListCycleII&SolutionN/A链表快慢指Leetcode-ReverseLinkedListII&SolutionN/A链表Leetcode-PartitionL

7、ist&SolutionN/A链表Leetcode-RemoveDuplicatesfromSortedList&SolutionN/A链表Leetcode-RemoveDuplicatesfromSortedListII&SolutionN/A链表Leetcode-MergeTwoSortedLists&SolutionN/A链表Leetcode-RotateList&SolutionN/A链表快慢拒Leetcode-ReverseNodesink-Group&SolutionN/A链表Leetcode-SwapNodesinPairs&Solution

8、N/A链表Leetcode-RemoveNthNodeFromEn