教育响应式网站建设,网站顺序,哪个网站做初中英语试题赚钱,适合夜晚的直播专栏#xff1a;数据结构 个人主页#xff1a;HaiFan. 专栏简介#xff1a;从零开始#xff0c;数据结构#xff01;#xff01; 单链表前言顺序表的缺陷链表的概念以及结构链表接口实现打印链表中的元素SLTPrintphead-next!NULL和phead!NULL的区别开辟空间SLTNewNod… 专栏数据结构 个人主页HaiFan. 专栏简介从零开始数据结构 单链表前言顺序表的缺陷链表的概念以及结构链表接口实现打印链表中的元素SLTPrintphead-next!NULL和phead!NULL的区别开辟空间SLTNewNode尾插SLTPushBack和尾删SLTPopBack头插SLTPushFront和头删SLTPopFront查找SLTFind在查找元素的后面插入SLTInsertAfter在查找元素的后面删除SLTEraseAfter销毁开辟的空间SLTDestory各个接口测试源代码链表和顺序表的区别前言 顺序表的缺陷
顺序表每一次扩容都是连续的空间支持通过下标去访问数据。
但是顺序表的头插头删中间删元素需要把后面的数据覆盖前面的元素也就是挪动元素这就导致效率非常的低
并且顺序表在扩容之后可能会有一部分空间没有用这就导致了空间浪费。
链表的概念以及结构
链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
链表的结点一般是在堆上申请出来的从堆上申请的空间是按照一定策略来分配的两次申请的空间可能连续也可能不连续。
链表是每用一块空间便开辟一块空间因此不会造成空间浪费。 这个图什么意思呢
把开辟的空间当作2个合在一起的小方块一个小方块用来存元素的值一个方块用来存放下一个空间的地址。 当这个1就是最后一个元素的时候这个下一块空间的地址就是NULL因为1后面没有元素了不能让这个地址乱指向其他的空间。
链表接口实现 这里在结构体中要用结构体指针指针就是地址这个地址就是用来存放下一个空间的地址的。
typedef int SLTDataType;typedef struct SLTNode
{SLTDataType val;struct SLTNode* next;
}SLT;void SLTPrint(SLT* phead);//打印单链表中的数据SLT* SLTNewNode(SLTDataType x);//每要插入数据就需要开一一块空间void SLTPushBack(SLT** pphead, SLTDataType x);//尾插
void SLTPopBack(SLT** pphead);//尾删void SLTPushFront(SLT** pphead, SLTDataType x);//头插
void SLTPopFront(SLT** pphead);//头删SLT* SLTFind(SLT** pphead, SLTDataType x);//查找
//单链表在pos位置之后插入x
void SLTInsertAfter(SLT* pos, SLTDataType x);//插入
//单链表在pos位置之后删除元素
void SLTEraseAfter(SLT* pos);//删除void SLTDestory(SLT** pphead);//销毁空间打印链表中的元素SLTPrint
打印链表中的元素是最容易实现的一个接口。
void SLTPrint(SLT* phead)
{while (phead ! NULL){cout phead-val -;phead phead-next;}cout NULL endl;
}这里用一级指针因为打印链表不会更改链表中的一些东西。
每打印出一个元素都让phead指向下一块空间直到走到为NULL的时候为止 phead-next!NULL和phead!NULL的区别 假如现在phead是在3这块空间那么phead-next就是指向下一块空间因为下一块空间是NULL所以当你写出phead-next ! NULL的时候就会在3这里停止后面的打印。 phead !NULL是当phead走到NULL的时候才会执行。
开辟空间SLTNewNode
链表是每用一块空间就开辟一块空间。这样不会造成空间浪费。
SLT* SLTNewNode(SLTDataType x)
{SLT* newnode (SLT*)malloc(sizeof(SLT));newnode-next NULL;newnode-val x;return newnode;
}开辟了空间之后不要忘记把newnode-next置为NULL不然就成为野指针了。最后把这块空间返回即可。
尾插SLTPushBack和尾删SLTPopBack
尾插的时候先调用一下开辟空间的函数再把开辟的空间返回用一个结构体指针变量接收。
当链表为空的时候newnode就可以当作链表中的第一块空间。当链表不为空的时候就需要先找到链表的尾部然后把newnode链接在链表中即可
void SLTPushBack(SLT** pphead, SLTDataType x)
{SLT* newnode SLTNewNode(x);if (*pphead NULL){*pphead newnode;}else{SLT* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}要用一个临时变量走向链表最后一个元素的位置如果不用临时变量直接用头元素走到最后一个位置那么在打印元素的时候也是从最后一个元素的位置开始打印的前面的元素不会打印因为我们是用指针接收的头元素的位置通过指针直接去访问内容指针走到最后就会导致原本应该指向头元素的指针就指向了最后的元素。
所以在这里用 tail-next ! NULL 尾删分两种情况当链表中只有一个元素的时候和链表中有n个元素的时候。
第一种情况好说直接把第一个元素的空间给free掉在置为空即可。
第二种情况就是先找到尾但是在找到尾部之后不能直接把尾部free掉而是要先知道倒数第二个元素的位置。
void SLTPopBack(SLT** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLT* tail *pphead;while (tail-next-next ! NULL){ tail tail-next;}free(tail-next);tail-next NULL;}
}/*SLTNode* prev NULL;SLTNode* tail phead;while (tail-next){prev tail;tail tail-next;}free(tail);prev-next NULL;*/这两种方法都可以。
头插SLTPushFront和头删SLTPopFront
头插特别容易先开辟一块空间然后把这块空间指向头元素空间。在把头元素空间指向新开辟的空间即可。 void SLTPushFront(SLT** pphead, SLTDataType x)
{SLT* newnode SLTNewNode(x);newnode-next *pphead;*pphead newnode;
} 头删之前要先判断链表中有没有元素没有元素直接断言。
有一个元素直接free。
多个元素先用一个临时变量记录一下头元素指向的下一个元素的地址然后把头元素给free掉再让头元素临时变量。
void SLTPopFront(SLT** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLT* head (*pphead)-next;free(*pphead);*pphead NULL;*pphead head;}
}查找SLTFind
查找元素的时候把该空间的地址给返回即可遍历一遍链表即可实现。
SLT* SLTFind(SLT** pphead, SLTDataType x)
{SLT* tail *pphead;while (tail ! NULL){if (tail-val x){return tail;}tail tail-next;}return NULL;//没有找到
}在查找元素的后面插入SLTInsertAfter
先通过SLTFind找到要插入的位置然后通过断言来判断这个位置是否合法。 比如要把3插入到1和2之间把3-next 1-next再把1-next 3就能完成插入。
void SLTInsertAfter(SLT* pos, SLTDataType x)
{assert(pos);SLT* newnode SLTNewNode(x);newnode-next pos-next;pos-next newnode;}
在查找元素的后面删除SLTEraseAfter
还是先断言判断位置是否合法。 电脑上的画图实在是用不来原谅我------。。。
void SLTEraseAfter(SLT* pos)
{assert(pos);if (pos-next NULL){return;}SLT* newnode pos-next;pos-next newnode-next;free(newnode);newnode NULL;
}销毁开辟的空间SLTDestory
因为空间不一定是连续的所以需要遍历链表一个一个的释放
void SLTDestory(SLT** pphead)
{SLT* cur *pphead;while (cur){SLT* hh cur-next;free(cur);cur hh;}
}各个接口测试
void TestSLTNode()
{SLT* plist NULL;cout 尾插尾删 endl;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 4);SLTPopBack(plist);SLTPopBack(plist);SLTPopBack(plist);SLTPopBack(plist);SLTPrint(plist);
}void TestSLTNode1()
{SLT* plist NULL;cout 头插头删 endl;SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPopFront(plist);SLTPopFront(plist);SLTPopFront(plist);SLTPrint(plist);
}void TestSLTNode2()
{SLT* plist NULL;cout 查找删除插入 endl;SLTPushFront(plist, -1);SLTPushBack(plist, 1);SLTPushFront(plist, -2);SLTPushBack(plist, 2);SLTPushFront(plist, -3);SLTPushBack(plist, 3);SLTPushFront(plist, -4);SLTPushBack(plist, 4);SLT* ret SLTFind(plist, 3);if (ret){cout ret endl;}SLTPrint(plist);SLTInsertAfter(ret, 100);SLTInsertAfter(ret, 100);SLTInsertAfter(ret, 100);SLTPrint(plist);SLTEraseAfter(ret);SLTEraseAfter(ret);SLTPrint(plist);SLTDestory(plist);
}int main()
{TestSLTNode();TestSLTNode1();TestSLTNode2();return 0;
}源代码
.h文件
#pragma once#include iostream
#include stdlib.h
#include assert.husing namespace std;typedef int SLTDataType;typedef struct SLTNode
{SLTDataType val;struct SLTNode* next;
}SLT;void SLTPrint(SLT* phead);//打印单链表中的数据SLT* SLTNewNode(SLTDataType x);//每要插入数据就需要开一一块空间void SLTPushBack(SLT** pphead, SLTDataType x);//尾插
void SLTPopBack(SLT** pphead);//尾删void SLTPushFront(SLT** pphead, SLTDataType x);//头插
void SLTPopFront(SLT** pphead);//头删SLT* SLTFind(SLT** pphead, SLTDataType x);//查找
//单链表在pos位置之后插入x
void SLTInsertAfter(SLT* pos, SLTDataType x);//插入
//单链表在pos位置之后删除元素
void SLTEraseAfter(SLT* pos);//删除void SLTDestory(SLT** pphead);//销毁空间.cpp文件
#define _CRT_SECURE_NO_WARNINGS 1#include SList.hvoid SLTPrint(SLT* phead)
{while (phead){cout phead-val -;phead phead-next;}cout NULL endl;
}SLT* SLTNewNode(SLTDataType x)
{SLT* newnode (SLT*)malloc(sizeof(SLT));newnode-next NULL;newnode-val x;return newnode;
}void SLTPushBack(SLT** pphead, SLTDataType x)
{SLT* newnode SLTNewNode(x);if (*pphead NULL){*pphead newnode;}else{SLT* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}void SLTPopBack(SLT** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLT* tail *pphead;while (tail-next-next ! NULL){ tail tail-next;}free(tail-next);tail-next NULL;}
}void SLTPushFront(SLT** pphead, SLTDataType x)
{SLT* newnode SLTNewNode(x);newnode-next *pphead;*pphead newnode;
}void SLTPopFront(SLT** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLT* head (*pphead)-next;free(*pphead);*pphead NULL;*pphead head;}
}SLT* SLTFind(SLT** pphead, SLTDataType x)
{SLT* tail *pphead;while (tail ! NULL){if (tail-val x){return tail;}tail tail-next;}return NULL;//没有找到
}void SLTInsertAfter(SLT* pos, SLTDataType x)
{assert(pos);SLT* newnode SLTNewNode(x);newnode-next pos-next;pos-next newnode;}void SLTEraseAfter(SLT* pos)
{assert(pos);if (pos-next NULL){return;}SLT* newnode pos-next;pos-next newnode-next;free(newnode);newnode NULL;
}void SLTDestory(SLT** pphead)
{SLT* cur *pphead;while (cur){SLT* hh cur-next;free(cur);cur hh;}
}test.cpp文件
#define _CRT_SECURE_NO_WARNINGS 1#include SList.hvoid TestSLTNode()
{SLT* plist NULL;cout 尾插尾删 endl;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 4);SLTPopBack(plist);SLTPopBack(plist);SLTPopBack(plist);SLTPopBack(plist);SLTPrint(plist);
}void TestSLTNode1()
{SLT* plist NULL;cout 头插头删 endl;SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPopFront(plist);SLTPopFront(plist);SLTPopFront(plist);SLTPrint(plist);
}void TestSLTNode2()
{SLT* plist NULL;cout 查找删除插入 endl;SLTPushFront(plist, -1);SLTPushBack(plist, 1);SLTPushFront(plist, -2);SLTPushBack(plist, 2);SLTPushFront(plist, -3);SLTPushBack(plist, 3);SLTPushFront(plist, -4);SLTPushBack(plist, 4);SLT* ret SLTFind(plist, 3);if (ret){cout ret endl;}SLTPrint(plist);SLTInsertAfter(ret, 100);SLTInsertAfter(ret, 100);SLTInsertAfter(ret, 100);SLTPrint(plist);SLTEraseAfter(ret);SLTEraseAfter(ret);SLTPrint(plist);SLTDestory(plist);
}int main()
{TestSLTNode();TestSLTNode1();TestSLTNode2();return 0;
}链表和顺序表的区别
不同点顺序表链表存储空间上物理上一定连续逻辑上连续但物理上不一定 连续随机访问支持O(1)不支持O(N)任意位置插入或者删除 元素可能需要搬移元素效率低 O(N)只需修改指针指向插入动态顺序表空间不够时需要 扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率高低
