顺序表和链表的比较|E路上一路上

顺序表和链表的比较     顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢?这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑: ┌───┬───────────────┬───────────────┐ │      │         顺序表          │         链表            │ ├─┬─┼───────────────┼──────────…

双向链表(Double Linked List)|E路上一路上

双向链表(Double Linked List)|E路上一路上

双链表 1、双向链表(Double Linked List) 双(向)链表中有两条方向不同的链,即每个结点中除next域存放后继结点地址外,还增加一个指向其直接前趋的指针域prior。 注意: ①双链表由头指针head惟一确定的。 ②带头结点的双链表的某些运算变得方便。 ③将头结点和尾结点链接起来,为双(向)循环链表。 2、双向链表的结点结构和形式描述 ①结点结构(见上图a)       ②形式描…

循环链表(Circular Linked List)|E路上一路上

循环链表(Circular Linked List)|E路上一路上

循环链表(Circular Linked List)      循环链表是一种首尾相接的链表。 1、循环链表 (1)单循环链表——在单链表中,将终端结点的指针域NULL改为指向表头结点或开始结点即可。 (2)多重链的循环链表——将表中结点链在多个环上。   2、带头结点的单循环链表 注意:  判断空链表的条件是head==head->next; 3、仅设尾指针的单循环链表 用尾指针rear表…

单链表的运算|E路上一路上

单链表的运算 1、建立单链表 假设线性表中结点的数据类型是字符,我们逐个输入这些字符型的结点,并以换行符’\n’为输入条件结束标志符。动态地建立单链表的常用方法有如下两种: (1) 头插法建表 ① 算法思路 从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。 具体方法【参见动画演示】 注意:…

单链表|E路上一路上

单链表 1、链接存储方法 链接方式存储的线性表简称为链表(Linked List)。 链表的具体存储表示为: ① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的) ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link)) 注意…

顺序表|E路上一路上

顺序表 1. 顺序表的定义 (1) 顺序存储方法 即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。 (2) 顺序表(Sequential List) 用顺序存储方法存储的线性表简称为顺序表(Sequential List)。 2. 结点ai 的存储地址 不失一般性,设线性表中所有结点的类型相同,则每个结点所占用存储空间大小亦相同。假设表中每个结点占用c个存储单元,其中第一个单元…

线性表的逻辑定义|E路上

线性结构是最简单且最常用的数据结构。线性表是一种典型的线性结构。 线性表的逻辑定义 线性表(Linear List)是由n(n≥0)个数据元素(结点)a1,a2,…,an组成的有限序列。 ① 数据元素的个数n定义为表的长度(n=0时称为空表)。 ② 将非空的线性表(n>0)记作:(a1,a2,…,an) ③ 数据元素ai(1≤i≤n)只是个抽象符号,其具体含义在不同情况下可以不同。 【例1】英文字…

队列的应用|一路上

队列的应用–舞伴问题 1、问题叙述 假设在周末舞会上,男士们和女士们进入舞厅时,各自排成一队。跳舞开始时,依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同,则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。 2、问题分析 先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性,可用队列作为算法的数据结构。 在算法中,假设男士和女士…

栈的应用|一路上

栈和队列的应用非常之广,只要问题满足后进先出和先进先出原则,均可使用栈和队列作为其数据结构。 栈的应用 1、 数制转换 将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题,很容易通过”除B取余法”来解决。 【例】将十进制数13转化为二进制数。 解答:按除2取余法,得到的余数依次是1、0、1、1,则十进制数转化为二进制数为1101。 分析:由于最先得到的余数是转…