网站开发fsdpjq,如何搭建asp网站,质量品质好的装修公司,网叶制作概要参考《大话数据结构》#xff0c;把常用的基本数据结构梳理一下。线性表定义线性表(List)#xff1a;零个或多个数据元素的有限序列。若将线性表记为 \((a_1, \cdots, a_{i-1}, a_i, a_{i1}, \cdots, a_n)\)#xff0c;则表中 \(a_{i-1}\) 领先于 \(a_i\)#xff0c;\(…概要参考《大话数据结构》把常用的基本数据结构梳理一下。线性表定义线性表(List)零个或多个数据元素的有限序列。若将线性表记为 \((a_1, \cdots, a_{i-1}, a_i, a_{i1}, \cdots, a_n)\)则表中 \(a_{i-1}\) 领先于 \(a_i\)\(a_i\) 领先于 \(a_{i1}\)称 \(a_{i-1}\) 是 \(a_i\) 的直接前驱元素\(a_{i1}\) 是 \(a_i\) 的直接后继元素。线性表的元素个数 \(n\) 定义为线性表的长度当 \(n0\) 时称为空表。线性表的顺序存储结构线性表的顺序存储结构就是在内存中找了块地儿通过占位的形式把一定的内存空间给占了然后把相同数据类型的数据元素依次存放在这块空地中。因此可以用一维数组来实现顺序存储结构即把第一个数据元素存到数组下标为 \(0\) 的位置中接着把线性表相邻的元素存储在数组中相邻的位置。来看看线性表的顺序存储结构的代码。# define MAXSIZE 20 //存储空间初始分配量typedef int ElemType; // ElemType 类型根据实际情况而定这里假设为 inttypedef struct{ElemType data[MAXSIZE]; // 数组存储数据元素最大值为 MAXSIZEint length; // 线性表当前长度}SqList;这里注意描述顺序存储结构需要三个属性存储空间的起始位置数组 data它的存储位置就是存储空间的存储位置线性表的最大存储容量数组长度 MAXSIZE(注意不等于线性表的长度)。线性表的当前长度length.线性表顺序存储结构的优缺点线性表的顺序存储结构在存、读数据时不管是哪个位置时间复杂度都是 \(O(1)\)而插入或删除时时间复杂度都是 \(O(n)\). 这就说明它比较适合元素个数不太变化而更多是存取数据的应用。优缺点总结如下优点无须为表示表中元素之间的逻辑关系而增加额外的存储空间可以快速地存取表中任一位置的元素缺点插入和删除操作需要移动大量元素当线性表长度变化较大时难以确定存储空间的容量造成存储空间的 “碎片”线性表的链式存储结构在链式结构中除了要存数据元素信息外还要存储它的直接后继元素的存储地址我们把存储数据元素信息的域称为数据域把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素 \(a_i\) 的存储映像称为结点。\(n\) 个结点链结成一个链表即为线性表 \((a_1, a_2, \cdots, a_n)\) 的链式存储结构*因为此链表的每个结点只包含一个指针域所以叫做单链表**。对于线性表来说总得有个头有个尾我们把链表中第一个结点的存储位置叫做头指针那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点其实就是上一个后继指针指向的位置。最后一个结点的指针为“空”(通常用 NULL 或 “^” 符号来表示)。有时为了更加方便地对链表进行操作会在单链表的第一个结点前附设一个结点称为头结点。头结点的数据域可以不存储任何信息也可以存储如线性表的长度等附加信息头结点的指针域存储指向第一个结点的指针如图注意头指针与头结点的异同点头指针头指针是指链表指向第一个结点的指针若链表有头结点则是指向头结点的指针头指针具有标识作用所以常用头指针冠以链表的名字无论链表是否为空头指针均不为空。头指针是链表的必要元素头结点头结点是为了操作的统一和方便而设立的放在第一元素的结点之前其数据域一般无意义(也可存放链表的长度)有了头结点对在第一元素结点前插入结点和删除第一结点其操作与其它结点的操作就统一了头结点不一定是链表必须要素来看看线性表的链式存储结构的代码。// 线性表的单链表存储结构typedef struct Node{ElemType data;struct Node *next;}Node;typedef struct Node *LinkList; // 定义 LinkList从这个结构定义中我们也就知道结点由存放数据元素的数据域存放后继结点地址的指针域组成。假设 \(p\) 是指向线性表第 \(i\) 个元素的指针则该结点 \(a_i\) 的数据域我们可以用 \(p-data\) 来表示\(p-data\) 的值是一个数据元素结点 \(a_i\) 的指针域可以用 \(p-next\) 来表示\(p-next\) 的值是一个指针指向第 \(i1\) 个元素即指向 \(a_{i1}\) 的指针。也就是说如果 \(p-data a_i\)那么 \(p-next-data a_{i1}\).单链表结构与顺序存储结构优缺点简单地对单链表结构和顺序结构做对比通过上面的对比我们可以得出一些经验性的结论若线性表需要频繁查找很少进行插入和删除操作时宜采用顺序存储结构。若需要频繁插入和删除时宜采用单链表结构。当线性表中的元素个数变化较大或者根本不知道有多大时最好用单链表结构这样可以不需要考虑存储空间的大小问题。如果事先知道线性表的大致长度比如一年 12 个月一周就是 7 天这种用顺序存储结构效率会好很多总之线性表的存储结构和单链表结构各有优缺点视实际情况而定。最后简单说一下静态链表。静态链表是用数组描述的链表我们让数组的元素都是由两个数域组成 data 和 cur. 也就是说数组的每个下标都对应一个 data 和下一个 cur. 数据域 data用来存放数据元素也就是通常我们要处理的数据而游标 cur 相当于单链表中的 next 指针存放该元素的后继在数组中的下标。所以它还有个别名游标实现法。它有单链表的插入和删除操作性能但是没有解决连续存储分配带来的表长难以确定的问题而且失去了顺序存储结构随机存取的特性。
