怎么用ps做网站首页背景图片,兰州市住房和城乡建设局官网,安监网站安全建设信息,推广链接点击器网页本章重点 链表的分类 带头双向循环链表接口实现 顺序表和链表的区别 缓存利用率参考存储体系结构 以及 局部原理性。 一、链表的分类 实际中链表的结构非常多样#xff0c;以下情况组合起来就有8种链表结构#xff1a;
1. 单向或者双向 2. 带头或者不带头
3. 循环或者非…本章重点 链表的分类 带头双向循环链表接口实现 顺序表和链表的区别 缓存利用率参考存储体系结构 以及 局部原理性。 一、链表的分类 实际中链表的结构非常多样以下情况组合起来就有8种链表结构
1. 单向或者双向 2. 带头或者不带头
3. 循环或者非循环 虽然有这么多的链表的结构但是我们实际中最常用还是两种结构 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带 来很多优势实现反而简单了后面我们代码实现了就知道了。 二、带头双向循环链表接口实现 1.申请结点struct ListNode* BuyLTNode(LTDataType x)
动态申请结点函数返回的是一个指针类型用malloc开辟一个LTNode大小的空间并用node指向这个空间再判断是否为空如为空就perror显示错误信息。反之则把要存的数据x存到newnode指向的空间里面把指针置为空。
// 申请结点
struct ListNode* BuyLTNode(LTDataType x)
{struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode));if (node NULL){perror(malloc fail);exit(-1);}node-data x;node-prev node;node-next node;return node;
}2.初始化struct ListNode* LTInit()
// 初始化
void LTInit(struct ListNode* phead)
{phead BuyLTNode(-1);phead-prev phead;phead-next phead;
}我们首先看看这个初始化有什么问题嘛 phead为空指针说明我们的初始化没有效果这是因为phead是函数里面的形参出了作用域就销毁plsit仍然是空指针形参的改变不能影响实参但是我们可以通过返回phead的地址解决问题。
单链表开始是没有节点的可以定义一个指向空指针的结点指针但是此链表不同需要在初始化函数中创建个头结点它不用存储有效数据。因为链表是循环的在最开始需要让头结点的next和pre指向头结点自己。
因为其他函数也不需要用二级指针因为头结点指针是不会变的变的是next和pre改变的是结构体只需要用结构体针即可也就是一级指针为了保持一致此函数也不用二级指针把返回类型设置为结构体指针类型。
// 初始化 - 改变实参plsit
struct ListNode* LTInit()
{struct ListNode* phead BuyLTNode(-1);phead-prev phead;phead-next phead;return phead;
}
3.尾插void LTPushBack(struct ListNode* phead, LTDataType x)
尾插首先要找到尾结点再将要尾插的结点与尾结点和带头结点链接由于是带头结点所以此处不需要关注头结点为空的问题。
// 尾插
void LTPushBack(struct ListNode* phead, LTDataType x)
{assert(phead);struct ListNode* tail phead-prev;struct ListNode* newnode BuyLTNode(x);newnode-prev tail;tail-next newnode;newnode-next phead;phead-prev newnode;} 4.尾删void LTPopBack(struct ListNode* phead)
尾删只需要找到尾结点的前驱结点再把带头结点和前驱结点链接释放尾结点就完成了尾删。
不过这里需要处理一下只有带头结点的删除此时真正的链表为空此时就不能删除了。
// 尾删
void LTPopBack(struct ListNode* phead)
{assert(phead);assert(phead-next ! phead);//链表为空struct ListNode* tail phead-prev;struct ListNode* tailPrev tail-prev;free(tail);tailPrev-next phead;phead-next tailPrev;} 5.头插void LTPushFront(struct ListNode* phead, LTDataType x)
头插需要注意顺序如果先让phead和newnode链接那么就找不到phead结点的后续结点这样就无法让newnode和phead结点的后续结点链接。
// 头插
void LTPushFront(struct ListNode* phead, LTDataType x)
{assert(phead);struct ListNode* newnode BuyLTNode(x);//顺序不可颠倒newnode-next phead-next;phead-next-prev newnode;phead-next newnode;newnode-prev phead;
} 6.头删void LTPopFront(struct ListNode* phead)
// 头删
void LTPopFront(struct ListNode* phead)
{assert(phead);assert(phead-next ! phead);//链表为空struct ListNode* first phead-next;struct ListNode* second first-next;free(first);phead-next second;second-prev phead;
} 7.链表长度int LTSize(struct ListNode* phead) 求链表长度先把头结点下一个结点存到cur中再用while循环遍历终止条件是cur等于头结点用size记录长度并更新cur最后返回size32位机器下是无符号整型size_t。 此类型可以提高代码的可移植性有效性可读性。此链表长度可能是字符型或者数组整型他可以提供一种可移植方法来声明与系统中可寻址的内存区域一致的长度而且被设计的足够大能表示内存中任意对象的大小 注意这里求链表长度不需要求带头结点我们有时也经常看到由于带头结点的数据没有使用就有的书上会把该数据存储上链表的长度sizephead-data然后插入数据phead-data,删除phead---但是这有个限制这种写法只适合int类型如果我们写出char类型的数据存储几个数据char就保存不了char类型的phead-data一直最后就会溢出所以不建议这种写法。
// 链表长度
int LTSize(struct ListNode* phead)
{assert(phead);int size 0;struct ListNode* cur phead-next;while (cur ! phead){size;cur cur-next;}return size;
}
8.在pos的前面进行插入void LTInsert(struct ListNode* pos, LTDataType x)
断言pos不能为空插入数据先申请一结点放到定义的newnode指针变量中为了不用考虑插入顺序先把pos前面的存到posPrev中然后就可以随意链接 posPrev指向新节点新节点前驱指针指向posPrev新节点指向pospos前驱指针指向新节点。
// 在pos的前面进行插入
void LTInsert(struct ListNode* pos, LTDataType x)
{assert(pos);struct ListNode* posPrev pos-prev;struct ListNode* newnode BuyLTNode(x);posPrev-next newnode;newnode-prev posPrev;newnode-next pos;pos-prev newnode;
}
9.删除pos位置的结点void LTErase(struct ListNode* pos)
删除把pos位置之前的结点直接指向pos的下一个结点把pos下一个结点的前驱指针指向pos之前的结点。
// 删除pos位置的结点
void LTErase(struct ListNode* pos)
{assert(pos);struct ListNode* posPrev pos-prev;struct ListNode* posNext pos-next;free(pos);posPrev-next posNext;posNext-prev posPrev;
} 10.双向链表查找struct ListNode* ListFind(struct ListNode* phead, LTDataType x)
查找把头结点下一个结点存到cur然后用while循环遍历终止条件是cur等于头结点指针如果cur等于x直接返回cur指针再更新cur最后遍历完返回NULL表示没有该数据。
// 双向链表查找
struct ListNode* ListFind(struct ListNode* phead, LTDataType x)
{assert(phead);struct ListNode* cur phead-next;while (cur ! phead){if (cur-data x)return cur;cur cur-next;}return NULL;
}
11.销毁void LTDestroy(struct ListNode* phead)
释放链表从头开始释放把头结点下一个结点存到cur中再用用while循环终止条件是cur不等于头指针在里面把cur下一个指针存到next中释放掉cur再把next更新为cur。最后头结点也是申请的也得释放。
这里需要注意由于形参的改变不会影响实参我们在函数内部将phead置空是无意义的我们需要在函数外面调用LTDestroy函数后需要手动将phead置空。
// 销毁
void LTDestroy(struct ListNode* phead)
{assert(phead);struct ListNode* cur phead-next;while (cur ! phead){struct ListNode* next cur-next;free(cur);cur next;}free(phead);
}
12.打印void LTPrint(struct ListNode* phead)
打印链表先断言phead它不能为空再把头结点下个地址存到cur中用while循环去遍历终止条件是等于头指针停止因为他是循环的并更新cur。
// 打印
void LTPrint(struct ListNode* phead)
{assert(phead);printf(phead);struct ListNode* cur phead-next;while (cur ! phead){printf(%d, cur-data);cur cur-next;}
}
三、顺序表和链表的区别 不同点顺序表链表存储空间上物理上一定连续逻辑上连续但物理上不一定 连续随机访问支持O(1)不支持O(N)任意位置插入或者删除 元素可能需要搬移元素效率低 O(N)只需修改指针指向插入动态顺序表空间不够时需要 扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率高低
四、缓存利用率参考存储体系结构 以及 局部原理性。
1.存储体系结构 寄存器Registers寄存器是CPU内部的最快速存储用于存储最常用的数据和指令。它们在执行指令时起着重要作用速度非常快。 高速缓存Cache高速缓存是位于中央处理器CPU和主存储器之间的一层快速存储用于临时存放经常访问的数据和指令。它可以分为多个层次如L1、L2和L3缓存随着级别的升高容量逐渐增大但速度逐渐降低。 主存储器Main Memory也称为RAMRandom Access Memory主存储器是计算机中用于存放运行中程序和数据的地方。它是CPU能够直接访问的存储设备速度比较快但容量通常相对有限。 辅助存储器Secondary Storage这包括各种长期存储设备如硬盘驱动器、固态硬盘、光盘、磁带等。这些设备的容量通常很大但速度较慢用于持久性存储和备份。 虚拟内存Virtual Memory虚拟内存是一种在主存和辅助存储之间创建的抽象层允许程序使用比主存更大的地址空间。操作系统可以根据需要将数据从主存移到辅助存储以优化内存使用。 2.局部性原理 存储体系结构的局部性原理是指在计算机程序执行过程中访问内存的模式往往呈现出一定的规律性即数据和指令的访问并不是完全随机的而是倾向于集中在某些特定的内存区域或者特定的数据块上。这个原理分为两种类型时间局部性和空间局部性。 时间局部性Temporal Locality时间局部性指的是一个被访问过的内存位置在未来的一段时间内很可能会再次被访问。这意味着程序在不久的将来可能会多次使用相同的数据或指令。时间局部性的实现依赖于高速缓存因为缓存可以暂时存储最近使用过的数据从而在未来的访问中加速存取。 空间局部性Spatial Locality空间局部性指的是在访问某个内存位置时附近的内存位置也很可能会被访问。这种情况在程序中存在连续存储、数组访问等情况下特别明显。空间局部性的实现同样依赖于高速缓存因为缓存可以在一个较小的区域内存储多个相邻的数据块。 局部性原理对计算机性能具有重要意义。通过充分利用局部性计算机系统可以更有效地使用高速缓存减少主存访问次数从而提高数据访问的速度和效率。这对于减少存储层次之间的数据传输时间以及提高程序的整体性能至关重要。 举例来说如果一个循环中多次使用相同的数组元素由于时间局部性这些数组元素会被缓存在高速缓存中从而避免了多次访问主存。同样如果一个算法中需要顺序访问数组的各个元素由于空间局部性缓存中可能会存储这些相邻的数据块从而加速了后续的访问。 3.为什么顺序表的效率比链表效率高 顺序表顺序表是一种将元素顺序存储在一块连续的内存区域中的数据结构。由于顺序表的元素在内存中是相邻存储的因此它充分利用了空间局部性。当访问一个元素时由于它的相邻元素也在内存中这些相邻元素很可能也会被加载到高速缓存中从而减少了主存访问的次数。此外由于顺序表的元素是连续存储的通过数组索引可以直接计算出元素的地址避免了链表节点的跳转操作。 链表链表是一种通过节点和指针连接元素的数据结构它的元素在内存中不一定是连续存储的。在链表中每个节点都包含了数据以及指向下一个节点的指针。这种非连续的存储方式可能导致空间局部性较差因为在访问一个节点时并不保证它的相邻节点会被加载到高速缓存中。这会导致更频繁的主存访问从而降低了效率。 综上所述顺序表相比链表具有更好的空间局部性。它的元素连续存储使得访问一个元素时附近的元素也可能在缓存中从而减少了主存访问的需求提高了数据访问的速度和效率。而链表的节点之间不一定相邻存储导致空间局部性不如顺序表因此链表在访问数据时可能需要更多的主存访问操作从而效率相对较低。 需要注意的是对于插入、删除等操作链表在某些情况下可能更加灵活因为它们不需要移动大量的数据而顺序表在插入、删除操作时可能需要进行元素的移动可能会带来一些开销。所以在选择使用顺序表还是链表时需要根据具体的应用场景和操作需求综合考虑。 本章结束啦
