导图社区 线性表 linear list
把待插入的元素依次放到备用链表中,只需要把插入位置的前一个元素的游标改为插入元素的下标,然后把插入元素的游标改为前一个元素原来的游标即可。
这是一篇关于番茄工作法花树图,间歇工作的总体效率高于连续工作,休息和工作交替进行。希望对你的工作效率有所帮助!
关于TK类电机设计审核思维导图,MacTK类电机的设计审核是一个全面评估电机性能、可靠性、成本等各方面要求的过程。
这是一篇关于设计心理学思维导图,包含日用品中的设计问题、日常操作心理学、设计中的挑战等。
社区模板帮助中心,点此进入>>
论语孔子简单思维导图
《老人与海》思维导图
《傅雷家书》思维导图
《阿房宫赋》思维导图
《西游记》思维导图
《水浒传》思维导图
《童年》读书笔记
《茶馆》思维导图
《朝花夕拾》篇目思维导图
《昆虫记》思维导图
线性表 linear list
顺序存储
优点
分配连续的内存区域,无需为数据间的关系增加额外的存储空间
查找数据非常方便,只需返回链表的下表即可
时间复杂度为O(1)
缺点
增加/删除数据需要移动后面所有的数据
移动过程中容易产生存储空间碎片
难以确定存储空间的容量
因为插入和删除会移动后面n个元素,所以时间复杂度为O(n)
链式存储
数据元素的内存不连续
单链表
一个节点包含数据域和指针域,指针指向下一个节点的地址
头指针
指向链表第一个元素的指针
是链表的必要要素,无论链表是否为空,头指针偶读存在
如果存在头结点,就指向头结点
如果头结点不存在,就指向第一个元素结点
空链表
头结点
在链表第一个元素之前,这样如果在第一个元素之前插入数据,就和在中间插入一样了
不是链表的必要要素
头结点的数据域通常不存数据,而是存储关于这个链表的一些元数据
p指向第i个元素
数据
p -> data
指针域
p -> next
插入
1. s -> next = p -> next; 2. p - > next = s;
如果头结点存在,在链表的第一个元素前面执行插入操作于在中间插入一样
若在链表尾端插入
时间复杂度O(n)
时间主要用在了查找上,因为不像顺序存储那样能直接通过下表返回特定值,所以如果要找一个值,只有从头开始 如果找到了特定值,再执行插入,时间复杂度为O(1)
删除
p -> next = q -> next;
时间主要用在了查找上,因为不像顺序存储那样能直接通过下表返回特定值,所以如果要找一个值,只有从头开始 如果找到了特定值,再执行删除,时间复杂度为O(1)
空间可以无限分配
总结
因为顺序存储查找的时间复杂度为O(1),所以如果需要频繁地查找,就使用顺序存储
虽然顺序存储和链表在插入和删除上的时间复杂度一样,但链表的优势在于,一旦找到了需要插入的位置,就只需要O(1)的时间去改变指针的指向,无论需要连续插入多少个连续数据都一样。而顺序操作如果想在某个位置插入多个数据,就需要每次都移动后面的数据,每次都需要O(n)的时间。所以如果插入和删除操作频繁,就应该用链表
如果事先知道数据的多少,应该用顺序存储。否则用链表
线性表指的是元素之间具有线性关系(即前驱后继)的一个表
循环链表
和单链表唯一的区别在于尾结点指向头结点
双向链表
和单链表很像,只不过在每一个结点多了一个指针域指向其前驱结点
双向循环链表
1. s -> next = p -> next; 2. p -> next ->prior = s; 3.p ->next = s; 4. s -> prior = p;
1. p -> prior -> next = p -> next; 2. p -> next -> prior = p -> prior;
静态链表
用数组代替指针来模拟单链表
链表中每一个元素都有数据域和一个int型的域,用来存放下一个元素在数组中的位置
头结点和最后一个结点不存放数据
头结点的指针域存放备用链表第一个结点的下标
尾结点的指针域存放第一个插入元素的下标
把待插入的元素依次放到备用链表中,只需要把插入位置的前一个元素的游标改为插入元素的下标,然后把插入元素的游标改为前一个元素原来的游标即可
和插入类似,只需要改待删除位置上一个元素的游标,让他的游标设为待删除元素的游标即可
每释放一个结点,就得把它的位置空出来然后接入到备用链表的首段
插入和删除时不需要移动元素
失去了顺序存储的优点
依然得提前分配很多空间,会有浪费