济南有哪些网站是做家具团购的,市场营销策划课程,企业 网站 推广,数控技术是学什么前言
由于之前存在过对两者的区别考虑#xff0c;所以把他们放在一起来说#xff0c;更加容易区别和理解
对于有关线性表的概念这里就不展示了#xff0c;这里主要是介绍线性表里面的这两个结构的知识点
一.顺序表
1.顺序表介绍 顺序表的存储结构和逻辑结构都是相邻的所以把他们放在一起来说更加容易区别和理解
对于有关线性表的概念这里就不展示了这里主要是介绍线性表里面的这两个结构的知识点
一.顺序表
1.顺序表介绍 顺序表的存储结构和逻辑结构都是相邻的 这里如果我们把a1的地址设置成100假设每个元素占4个存储空间那么a2就是104a3就是108依次往下 所以只要确定起始位置后面的位置都能找到这也就代表了可以随机存取这句话请记住和后面链表的区别有关。 顺序表的底层结构就是数组其实你把它当作数组来看也不是不行同时顺序表采用的是顺序存储结构对与数组的操作一般有增删查改和之前的通讯录差不多大家可以参考一下之前的通讯录 动态顺序表的实现其实也有静态版本但是静态版本有缺陷
typedef int SLDataType;
#define N 7
typedef struct SeqList
{SLDataType a[N];//数组长度int size;//当前有效数据个数
}SL;
可以很明显的看出N是固定的所以大小不能随便改变但是如果用动态的方法去用malloc开辟一片空间那么这个空间用realloc去增容那这块空间就是可以随时变化的
typedef int SLDataType;
typedef struct SeqList
{SLDataType *a;int size;//有效数据int capacity;//容量如果不够就用realloc去增容
}SL;
动态分配的空间是在堆上开辟的静态分配是在栈上开辟的两者的开辟空间不一样所以动态开辟需要自己主动去释放空间而且需要一个指针去指向这个空间因为你需要知道它的地址才能对它进行一个操作而静态的因为是数组数组名就代表了它的地址 2. 顺序表的实现 1.初始化表 2.插入元素 3.删除元素 4.查找元素 5.修改元素 初始化
void SLInit(SL *psl) {psl-a (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//先开辟这么多大小if (psl NULL) {perror(malloc fail);return;}psl-sz 0;psl-capacity 4;//分别把结构体里的元素初始化
}
静态版本的初始化就是遍历整个顺序表的元数把他们全设置为0。
这里的空间要记得用free释放不然会有内存泄露 容量不够的时候就增容这个函数一般反正插入数据的函数里面
void SLCheckBack(SL* psl) {if (psl-sz psl-capacity) {SLDatatype *tmp (SLDatatype*)realloc(psl-a, sizeof(SLDatatype) * psl-capacity*2);//如果容量不够了那么就增容if (tmp NULL) {perror(realloc fail);//扩容失败把错误信息打印出来return;}psl-a tmp;psl-capacity * 2;}
} 插入元素 插入元素有头插和尾插还有中间插入其实很简单就把它当作数组来做就行了因为用malloc开辟的空间是连续的那么放进去的元素也是连续的还有一点就是这里要判断是否要扩容。还有就是头插和中间插入的时候要移动数据 时间复杂度O(N) void SLPushBack(SL* psl, SLDatatype x) {SLCheckBack(psl);//判断psl-a[psl-sz] x;
} //尾插
void SLPushFron(SL* psl, SLDatatype x) {SLCheckBack(psl);for (int i psl-sz - 1; i 0; i--) {//这里需要移动数据把他们都往后移一位psl-a[i1]psl-a[i];}psl-a[0] x;psl-sz;}//头插void SLInsert(SL* psl, int pos, SLDatatype x){//中间插入assert(pos 0 pos psl-sz);这里插入的位置不能出错不然会越界所以用assert断言SLCheckBack(psl);for (int i psl-sz - 1; i psl-sz - pos; i--) {psl-a[i 1] psl-a[i];}psl -a[pos-1] x;psl-sz;
}删除元素
删除元素和插入有些类似删除头和中间的需要把数据往前面移动删除最后的则不需要 时间复杂度位 O(N) void SLPopBack(SL* psl) {assert(psl-sz 0);psl-sz--;
}//尾删
void SLPopFron(SL* psl) {assert(psl-sz 0);for (int i 1; i psl-sz - 1; i) {psl-a[i - 1] psl-a[i];}psl-sz--;
}//头删void SLErase(SL* psl, int pos) {//中间删除assert(pos 0 pos psl-sz);for (int i pos 1; i psl-sz - 1; i) {psl-a[i - 1] psl-a[i];}psl-sz--;
}查找元素
遍历整个表中的元素直到找到要找的元素为止找到返回坐标没有找到返回-1除了实现方法查找也分为按位查找和按值查找按位查找就是已经知道了数组下表去寻找按值查找就是看是否有这个值然后返回这个下标 按位查找的时间复杂度是 O(1), 按值查找的时间复杂度是 O(N) ;这两者还是要区分开的 int SLFind(SL* psl, SLDatatype pos)
{for (int i 0; i psl-sz; i){if (psl-data pos)return i;}return -1;
} 修改元素
这里的修改很简单因为前面已经有了查找元素的函数这里直接套过来就行了 void SLModify(SL* psl, int pos, SLDatatype x)
{int kSLFind(psl, pos);psl-data[k] x;//直接修改就行
}
二.链表
1.链表介绍
链表的存储结构不要求连续所以不具备顺序表的一些缺陷但是链表也有自己的缺陷就是不能随机存取它是一种链式存储结构之所以这样说是因为它如果要存取一个元素需要进行遍历到需要的位置再进行操作。
链表分为单链表双链表循环链表循环双链表其中由有带头和不带头的这样看起来链表其实有点复杂其实链表咱们再偷点懒把它们分为单链表和循环双链表这样就简单很多了因为循环双链表已经包括了前面两个。链表是由很多个结点组成具体多少看你需求每个结点都由一个数据域和指针组成指针的作用就是把每个结点连起来 很多人会这么理解就是不用指针这里就会有一个结构体嵌套的问题如果嵌套了那么这个结构体的大小就无法计算 所以这里要用指针去链接假设每个结点的大小是一个字节如图所示 这就是基本的单链表结构这里是不带头的从图中可以看出其实链表其实并没有箭头只不过是为了更好的显示他们的next指针保存了下一个结点的地址所以可以通过指针去寻找他们记住指针是用来存放地址的变量把这里理解了就不会有什么问题。 如果是带头的也称之为哨兵位也就是没有前面的头指针有一个不存放数据的头结点 有了哨兵位可以减少在链表头插的时候判断是不是空的情况这样使头插尾删的操作变简单了
下面我们进行单链表的实现让你去体会这句话
2.单链表的实现 1.单链表的创建与销毁 2.单链表的增加元素 3.单链表的删除元素 4.单链表的修改元素 5.单链表的查找元素 下面给出单链表所以实现函数以便有一个清晰的认识这里说明一下为什么要双指针因为我们在头插和头删的时候我们需要去改变头指针的指向改变指针的指向我们需要指针的指针细品
#pragma once
#includeiostream
#includecstdlib
#includeassert.h
using namespace std;
typedef int SLTDataType;
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;
//创建一个结点
SLTNode* BuyLTNode(SLTDataType* x);
//打印
void SLTPrint(SLTNode* phead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode* phead);
//头删
void SLTPopFront(SLTNode** pphed);
//查找
SLTNode* SLTFind(SListNode* phead, SLTDataType x);
//在pos之前插入
void SLInsert(SLTNode** pphead, SLTDataType x);
//在pos之后插入
void SLInsetAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之前删除
void SLErase(SLTNode* phead);
1.单链表的创建销毁
创建就是创建一个结点销毁是把创建的所有结点都销毁
SLTNode* BuyLTNode(SLTDataType x) {//创建一个结点SLTNode* newnode (SLTNode*) malloc(sizeof(SLTNode));if (newnode NULL) {perror(malloc);return NULL;}newnode-data x;//创建出来初始化newnode-next NULL;//如果不初始化会导致野指针的问题出现return newnode;
}//销毁
void SLDesTory(SLTNode** pphead)
{SLTNode* next *pphead;while (next){SLTNode* tail next-next;free(next);next tail;}*pphead NULL;}2.单链表的插入元素头插指定位置插 但是这里的如果有两个指针 一个指向当前位置一个指向下一个位置那么就可以不管顺序因为你都可以找得到
void SLTPushFornt(SLTNode** pphead, SListDatatype x) {assert(pphead);SLTNode*newnode BuyNode(x);//创建一个结点newnode-next *pphead;*pphead newnode;
}//头插SLTNode* SLTFind(SListNode* phead,SLTDataType x) {SLTNode* tail phead;while (tail) {if (tail-data x) {return tail;}tail tail-next;}return NULL;
}//查找函数与下面的插入联系起来void SLTInset(SLTNode** pphead,SListDatatype m,SListDatatype x) {assert(pphead);SLTNode*posSLTFind(*pphead, m);//需要寻找你要插入的位置所以有一个Find函数assert(pos);if (*ppheadpos) {SLTPushFornt(pphead, x);}//这里分清没有结点的情况和有结点的情况如果不判断那么会导致有野指针情况else {SLTNode* tail *pphead;while (tail-next ! pos) {tail tail-next;}SLTNode* newnode BuyNode(x);tail-next newnode;newnode-next pos;}
}指定位置插 3.单链表删除元素头删尾删 和插入元素有点像这里删除就是如果链表为空那么就不能再删了所以我们用assert断言去操作插入是如果链表为空要特殊判断一下细品这里的尾删也有不同
void SLTPopFornt(SLTNode** pphead) {assert(pphead);assert(*pphead);//为空不能删SLTNode* tail *pphead;*pphead tail-next;//指向下一个可以自己画图理解free(tail);
}//头删void SLTPopBack(SLTNode** pphead) {assert(pphead);assert(*pphead);if ((*pphead)-next NULL) {free(*pphead);*pphead NULL;}else {SLTNode* tail *pphead;while (tail-next-next) {//这里就是那个特殊的地方你需要找到删除位置的前一个位置然后对要删除的位置进行操作如果不这样直接删除的话会导致前一个指针为野指针因为你找不到前一个也就不能把它的next设置为空tail tail-next;}free(tail-next);tail-next NULL;}
}//尾删 查找和修改比较容易都是一起的这里就不介绍了下面介绍一下双向循环链表 循环双向链表的优势比单链表的优势大很多但是我们一般做题都用单链表所以两者都要掌握
这里就不给双向链表的实现了因为比较简单唯一要注意的就是删除那里可以自己去尝试操作一下
三.总结
顺序表
优点
对于访问数据很方便还有尾删尾插很方便
缺点
但是对于删除数据和增加数据不包括尾插尾删所用的消耗比较大
单链表
优点
插入和删除数据都比较快不需要挪动数据
缺点随机访问需要遍历时间复杂度为O(N),顺序表有一个二分查找时间复杂度为O(logN)
还有就是我们内存在读取数据的时候是读取cpu规定的字节大小的比如一次读32字节那么由于单链表的空间不连续所以会读到很多垃圾信息所以这里花的时间也有损耗
四.oj题
1.移除链表元素 这里的话我们的思路就是链表里面的删除操作可以用尾删的方法也可以逆向思维把他们头插到新的链表里面这里我们使用尾删的方法 也就是遍历遇到就删除 struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode*prevNULL,*tailhead;//这里使用tail去遍历反正找不到头指针。这里的prev是找到删除的前面一个结点防止出现野指针的情况具体的在上面有探讨过while(tail){if(tail-valval)//如果等于那么我们直接删除{if(prev){//这里还需要主要的就是如果第一个就是要删除的值那么这里prev就是空
//如果不判断直接进行那么prev-next就会变成野指针prev-nexttail-next;free(tail);tailprev-next;}else{//如果是空那么直接删headhead-next;free(tail);tailhead;}}else//不是目标值进行迭代{prevtail;tailtail-next;}}return head;
} 有了上一个题目感觉题目都是单链表的操作其实不难难的在于细节这就需要边画图边操作 趁热打铁再来一个
2.反转链表 其实思路差不多也可以采用头插的方法也就是把最后一个元素依次头插那么这样就复杂了而且时间上开销也大所以我们这里的思路是将指针全部逆置就行了 struct ListNode* reverseList(struct ListNode* head) {if(headNULL)//如果为空直接返回return NULL;struct ListNode*n1NULL;//这里需要三个指针去指向不同的位置struct ListNode*n2head;struct ListNode*n3n2-next;//可以画图表示while(n2)//当n2为空的时候就结束循环了这里一直迭代然后改变n2结点处的指针指向{n2-nextn1;n1n2;n2n3;if(n3)n3n3-next;}return n1;
} 如果第一题是我们的链表基础题那么第二题有点偏理解和思维了那我们继续
3. 返回倒数第 k 个节点 乍一看好像没什么思路这里其实用一个快慢指针,快指针先走k步然后再一起走最后当快指针等于空的时候结束这时候慢指针就指向了倒数第k个结点的位置不理解的可以画图 int kthToLast(struct ListNode* head, int k){struct ListNode*fast,*slow;fastslowhead;while(k--){if(fastNULL)这里需要注意如果k比原链表长度还大那么就不存在倒数第几个直接返回就行了return NULL;fastfast-next;}while(fast){//快指针为空的时候退出循环slowslow-next;fastfast-next;}return slow-val;//返回慢指针指向的位置即可
} 做完以后你对于链表的认识就有了比较好的理解了但是还不够下面给出几个题目练习
合并两个有序链表
链表分割
相交链表 以上就是顺序表和单链表的相关知识整理可能单链表不是很全但是把单链表理解后面的链表也不在话下如果认真看完你会对链表有一个好的理解和认识希望本篇文章可以给你们带来帮助
