会计公司网站样式,加速器国外,建站工具官网,o2o网站平台怎么做数据结构是计算机存储、组织数据的方式。常见的数据结构分类方式如下图#xff1a; 常用的线性结构有#xff1a;线性表#xff0c;栈#xff0c;队列#xff0c;循环队列#xff0c;数组。线性表中包括顺序表、链表等#xff0c;其中#xff0c;栈和队列只是属于逻辑上… 数据结构是计算机存储、组织数据的方式。常见的数据结构分类方式如下图 常用的线性结构有线性表栈队列循环队列数组。线性表中包括顺序表、链表等其中栈和队列只是属于逻辑上的概念实际中不存在仅仅是一种思想一种理念线性表则是在内存中数据的一种组织、存储的方式。 顺序表 顺序表将元素一个接一个的存入一组连续的存储单元中在内存物理上是连续的。如下图 顺序表存储密度较大节省空间但需要事先确定容量在时间性能方面读运算较快时间复杂度为O(1)查找运算为O(n/2)和链表同样插入运算和删除运算如果要操作中间一个元素比如3那么就需要把3后面的元素全部进行移动因此时间复杂度相对链表要大一些插入时间复杂度最好为O(0)或最坏为O(n)删除时间复杂度为O([n-1]/2) 链表 链表拥有很多结点每个结点前半部分是数据域后半部分是指针域指针域指针指向下一个结点链表可分为单链表、循环链表和双链表。 单链表 从上图可以看出单链表的上一个结点指针指向下一个结点最后一个结点的指针域为null。 结点的删除 删除一个结点如删除上图中q结点只需将p结点中的指针域指向a3然后将a2释放掉free即可。 结点的插入 插入一个结点如插入上图中s结点首先将s的指针域指向a2也就是把s的next赋值为p的next然后将p结点的指针域指向x即可p的next指向x。 循环链表 循环链表与单链表唯一不同之处是循环链表的最后一个结点指针不为空而是指向头结点。结点的插入和删除和单链表非常相似就不再示范了。 双链表 双链表拥有一前一后两个指针域从两个不同的方向把链表连接起来如此一来从两个不同的方向形成了两条链因此成为双链表。因此双链表的灵活度要大于单链表。 结点的删除 双链表的操作比单链表要稍显复杂按照单链表思路来做其实也不难如上图要删除p节点首先需要将a1的后驱指向a3然后将a3的前驱指向a1最后将p节点释放掉即可。 结点的插入 如上图插入q结点首先要按照方向将步骤拆分首先将q节点的前驱指向p结点后驱紧接着将x后驱指向a2然后按照顺序完成图中所示的3、4步即可。经llhhyy1989 voteforvip wanghuan203 三位童鞋的指正发现此处有误正确插入方法可查看评论为保留错误原文不做改动不懂具体插入过程可移步百度知道 从空间性能来看链表的存储密度要差一些但在容量分配上更灵活一些。从时间性能来看查找运算与顺序存储相同插入运算和删除运算的时间复杂度为O(1)要更优于顺序存储但读运算则弱一些为O([n1]/2)最好为1最坏为n。 栈 上面提到栈属于一个逻辑概念栈的实现可以用顺序也可以用链式。它遵循先进后出原则如下图 Java中测试代码如下 [java] view plaincopy package com.snail.test; import java.util.Stack; public class TestStack { public static void main(String[] args) { StackString stack new StackString(); stack.push(NO1); stack.push(NO2); stack.push(NO3); System.out.println(初始数量 stack.size()); while(!stack.isEmpty()){ System.out.println(stack.pop()); } System.out.println(取完后的数量 stack.size()); } } 输出结果顺序为初始数量3NO3NO2NO1取完后的数量0。 队列 队列遵循先进先出的原则如下图 Java中测试代码如下 [java] view plaincopy package com.snail.test; /** * * author Zang XT */ import java.util.Queue; import java.util.LinkedList; public class TestQueue { public static void main(String[] args) { QueueString queue new LinkedListString(); queue.offer(NO1); queue.offer(NO2); queue.offer(NO3); System.out.println(初始数量 queue.size()); String str; while((strqueue.poll())!null){ System.out.println(str); } System.out.println(取出后数量 queue.size()); } } 运行结果顺序为初始数量3NO1NO2NO3取出后数量0。 队列还有一种形式为循环队列如下图 循环队列有两个指针头指针head和尾指针tail尾指针一般指向的不是队尾元素实际地址而是指向实际地址的下一个空地址因此循环队列一般牺牲最后一个空间用来计算该队列是否满了判断方式是tail1 head既该队列已满。 为了尽可能的说清楚插了大量图片希望理解。以后有时间将继续分析树、图等数据结构。
