无锡网站定制公司,无锡网站排名哪里有,做网站的公司那家好。,地推项目发布平台主页#xff1a;醋溜马桶圈-CSDN博客 专栏#xff1a;数据结构_醋溜马桶圈的博客-CSDN博客 gitee#xff1a;mnxcc (mnxcc) - Gitee.com 目录
1.线性表
1.1 顺序表
1.1.1 概念及结构
1.1.2 静态顺序表
1.1.3 动态顺序表
1.2 链表
1.2.1 链表的概念及结构
1.2.2 链表… 主页醋溜马桶圈-CSDN博客 专栏数据结构_醋溜马桶圈的博客-CSDN博客 giteemnxcc (mnxcc) - Gitee.com 目录
1.线性表
1.1 顺序表
1.1.1 概念及结构
1.1.2 静态顺序表
1.1.3 动态顺序表
1.2 链表
1.2.1 链表的概念及结构
1.2.2 链表的分类
1.2.2.1 单向或者双向
1.2.2.2 带头或者不带头
1.2.2.3 循环或者非循环
1.3 顺序表和链表的区别
2.顺序表的实现
2.1 创建顺序表
2.2 基本的增删查改接口
2.2.1 顺序表初始化
2.2.2 顺序表的销毁
2.2.3 检查顺序表的容量
2.2.4 打印顺序表
2.2.5 顺序表的尾插
2.2.6 顺序表的头插
2.2.7 顺序表的尾删
2.2.8 顺序表的头删
2.2.9 任意位置的插入
2.2.10 任意位置的删除
2.2.11 顺序表的查找
2.3实现代码
2.3.1 SeqList.h
2.3.2 SeqList.c
3.单链表的实现
3.1 认识单链表
3.2 创建单链表
3.3 单链表的操作
3.3.1 打印单链表
3.3.2 开辟新空间
3.3.3 尾插
3.3.4 头插
3.3.5 尾删
3.3.6 头删
3.3.7 查找
3.3.8 在pos前面插入
3.3.9 删除pos位置
3.3.10 销毁
3.3.11 在pos位置之后插入
3.3.12 删除pos位置之后的值
3.4 实现代码
3.4.1 SList.h
3.4.2 SList.c
4.带头双向循环链表的实现
4.1 认识带头双向循环链表
4.1.1 双向链表
4.1.2 循环链表
4.1.3 带头链表
4.1.4 带头双向循环链表
4.1.5 双向链表的优势和不足
4.1.6 顺序表的优势和不足
4.2 实现带头双向循环链表
4.2.1 创建带头双向循环链表
4.2.2 初始化
4.2.3 创建返回链表的头结点
4.2.4 打印链表
4.2.5 尾插
4.2.6 尾删
4.2.7 头插
4.2.8 头删
4.2.9 查找
4.2.10 在pos位置前插入
4.2.11 删除pos位置
4.2.12 销毁
4.3 实现代码
4.3.1 ListNode.h
4.3.2 ListNode.c
5.数组下标为什么从0开始
5.1 原因
5.2 拓展
6.环型链表
6.1 环型链表是什么
6.2 快慢指针判断环形链表
6.2.1 思考
6.2.2 推导思路
6.2.3 结论 1.线性表
线性表linear list是n个具有相同特性的数据元素的有限序列
线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串..
线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储 1.1 顺序表
1.1.1 概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构
一般情况下采用数组存储在数组上完成数据的增删查改
顺序表一般可以分为
1.1.2 静态顺序表
静态顺序表使用定长数组存储元素 1.1.3 动态顺序表
动态顺序表使用动态开辟的数组存储 1.2 链表
1.2.1 链表的概念及结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的
现实中 数据结构中 注意
从上图可以看出链式结构在逻辑上是连续的但在物理上不一定连续现实中的结点一般都是从堆上申请出来的 从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续
1.2.2 链表的分类
实际中链表的结构非常多样以下情况组合起来就有8种链表结构
1.2.2.1 单向或者双向 1.2.2.2 带头或者不带头 1.2.2.3 循环或者非循环 虽然有这么多的链表的结构但是我们实际中最常用还是两种结构
无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向 循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了。 1.3 顺序表和链表的区别 与程序员相关的CPU缓存知识 | 酷 壳 - CoolShell
2.顺序表的实现
2.1 创建顺序表
2.2 基本的增删查改接口
2.2.1 顺序表初始化
顺序表的初始化我们只需要讲指针置为空指针 然后将当前数据元素个数和最大数据元素个数置为0 到插入时我们便会动态开辟空间给指针a //顺序表的初始化
void SLInit(SL* ps)
{ps-a NULL;//置为空指针ps-size 0;//数据个数为0ps-capacity 0;//空间大小置为0
} 2.2.2 顺序表的销毁 //顺序表的销毁
void SLDestroy(SL* ps)
{if (ps-a ! NULL){free(ps-a);ps-a NULL;ps-size 0;ps-capacity 0;}
} 2.2.3 检查顺序表的容量 //检查顺序表的容量
void SLCheckCapacity(SL* ps)
{if (ps-size ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;SLDataType* tmp realloc(ps-a, sizeof(SLDataType) * newCapacity);if (tmp NULL){perror(realloc fail);return;}ps-a tmp;ps-capacity newCapacity;}
} 2.2.4 打印顺序表 //打印顺序表
void SLPrint(SL* ps)
{for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
} 2.2.5 顺序表的尾插 //顺序表的尾插
void SLPushBack(SL* ps, SLDataType x)
{SLCheckCapacity(ps);ps-a[ps-size] x;ps-size;
} 2.2.6 顺序表的头插 //顺序表的头插
void SLPushFront(SL* ps, SLDataType x)
{SLCheckCapacity(ps);int end ps-size - 1;while (end 0){ps-a[end 1] ps-a[end];}ps-a[0] x;ps-size;
} 2.2.7 顺序表的尾删 //顺序表的尾删
void SLPopBack(SL* ps)
{assert(ps-size 0);//ps-a[ps-size - 1] -1;ps-size--;
} 2.2.8 顺序表的头删 //顺序表的头删
void SLPopFront(SL* ps)
{//for (int i 0; i ps-size; i)//{// ps-a[i] ps-a[i 1];//}//ps-size--;assert(ps);assert(ps-size 0);int begin 1;while (begin ps-size){ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
} 2.2.9 任意位置的插入 //任意位置的插入
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);int end ps-size - 1;while (end pos){ps-a[end 1] ps-a[end];--end;}ps-a[pos] x;ps-size;
} 2.2.10 任意位置的删除 //任意位置的删除
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);int begin pos;while (begin ps-size){ps-a[begin] ps-a[begin1];begin;}ps-size--;
} 2.2.11 顺序表的查找 //顺序表的查找
//找到返回下标找不到返回-1
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-a[i] x){return i;}}return -1;
} 2.3实现代码
2.3.1 SeqList.h #pragma once
#include stdio.h
#include stdlib.h
#include assert.h
typedef int SLDataType;
//顺序表的动态存储
typedef struct SeqList
{SLDataType* a; //指向动态开辟的数组int size; //有效元素个数int capacity; //容量空间的大小
}SL;//顺序表的初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);//检查顺序表的容量
void SLCheckCapacity(SL* ps);
//打印顺序表
void SLPrint(SL* ps);//顺序表的尾插
void SLPushBack(SL* ps, SLDataType x);
//顺序表的头插
void SLPushFront(SL* ps, SLDataType x);
//顺序表的尾删
void SLPopBack(SL* ps);
//顺序表的头删
void SLPopFront(SL* ps);//任意位置的插入
void SLInsert(SL* ps, int pos, SLDataType x);
//任意位置的删除
void SLErase(SL* ps, int pos);//顺序表的查找
//找到返回下标找不到返回-1
int SLFind(SL* ps, SLDataType x);2.3.2 SeqList.c #define _CRT_SECURE_NO_WARNINGS 1
#include SeqList.h//顺序表的初始化
void SLInit(SL* ps)
{ps-a NULL;//置为空指针ps-size 0;//数据个数为0ps-capacity 0;//空间大小置为0
}
//顺序表的销毁
void SLDestroy(SL* ps)
{if (ps-a ! NULL){free(ps-a);ps-a NULL;ps-size 0;ps-capacity 0;}
}
//检查顺序表的容量
void SLCheckCapacity(SL* ps)
{if (ps-size ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;SLDataType* tmp realloc(ps-a, sizeof(SLDataType) * newCapacity);if (tmp NULL){perror(realloc fail);return;}ps-a tmp;ps-capacity newCapacity;}
}
//打印顺序表
void SLPrint(SL* ps)
{for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}
//顺序表的尾插
void SLPushBack(SL* ps, SLDataType x)
{SLCheckCapacity(ps);ps-a[ps-size] x;ps-size;
}
//顺序表的头插
void SLPushFront(SL* ps, SLDataType x)
{SLCheckCapacity(ps);int end ps-size - 1;while (end 0){ps-a[end 1] ps-a[end];--end;}ps-a[0] x;ps-size;
}
//顺序表的尾删
void SLPopBack(SL* ps)
{assert(ps-size 0);//ps-a[ps-size - 1] -1;ps-size--;
}
//顺序表的头删
void SLPopFront(SL* ps)
{//for (int i 0; i ps-size; i)//{// ps-a[i] ps-a[i 1];//}//ps-size--;assert(ps);assert(ps-size 0);int begin 1;while (begin ps-size){ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}
//任意位置的插入
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);int end ps-size - 1;while (end pos){ps-a[end 1] ps-a[end];--end;}ps-a[pos] x;ps-size;
}
//任意位置的删除
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);int begin pos;while (begin ps-size){ps-a[begin] ps-a[begin1];begin;}ps-size--;
}
//顺序表的查找
//找到返回下标找不到返回-1
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-a[i] x){return i;}}return -1;
} 3.单链表的实现
顺序表存在下面的问题 尾插效率还不错头插或中间插入删除需要挪动数据效率低满了以后只能扩容扩容是有一定的消耗的扩容一般存在一定的空间浪费 3.1 认识单链表
如果想要插入一个结点就不需要挪动数据了改指针的指向就可以了
同样我们删除结点直接将前一个结点的指针指向后一个结点就可以了
首先我们还是从工程的角度去考虑创建SList.h SList.c test.c三个文件
SList.h放置函数的声明
SList.c放置函数的定义
test.c进行测试
3.2 创建单链表
3.3 单链表的操作
3.3.1 打印单链表 //打印单链表
//尽量不要动phead
void SLTPrint(SLNode* phead)
{SLNode* cur phead;while (cur ! NULL){printf(%d-, cur-val);cur cur-next;}printf(NULL\n);
} 3.3.2 开辟新空间 //开辟新空间
SLNode* CreateNode(SLNDataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-next NULL;return newnode;
} 3.3.3 尾插 //尾插
void SLTPushBack(SLNode** pphead, SLNDataType x)
{SLNode* newnode CreateNode(x);if (*pphead NULL){*pphead newnode;}else{SLNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
} 3.3.4 头插 //头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{SLNode* newnode CreateNode(x);newnode-next *pphead;*pphead newnode;
} 3.3.5 尾删 //尾删
void SLTPopBack(SLNode** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLNode* prev NULL;SLNode* tail *pphead;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}
} 3.3.6 头删 //头删
void SLTPopFront(SLNode** pphead)
{assert(*pphead);SLNode* tmp *pphead;*pphead (*pphead)-next;free(tmp);
} 3.3.7 查找 //查找
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{SLNode* cur phead;while (cur){if (cur-val x){return cur;}else{cur cur-next;}}return NULL;
} 3.3.8 在pos前面插入 //在pos前面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);assert(pos);assert(*pphead);//assert((!pos !(*pphead)) || (pos (*pphead)));if (*pphead pos){SLTPushFront(pphead, x);}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLNode* newnode CreateNode(x);prev-next newnode;newnode-next pos;}
} 3.3.9 删除pos位置 //删除pos位置
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(pos);assert(*pphead);if (*pphead pos){SLTPopFront(pphead);}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
} 3.3.10 销毁 //销毁
void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur *pphead;while (cur-next ! NULL){SLNode* next cur-next;free(cur);cur next;}*pphead NULL;
} 3.3.11 在pos位置之后插入 // 单链表在pos位置之后插入x
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{SLNode* newnode CreateNode(x);newnode-next pos-next;pos-next newnode;
} 3.3.12 删除pos位置之后的值 // 单链表删除pos位置之后的值
void SLTEraseAfter(SLNode* pos)
{assert(pos-next ! NULL);pos-next pos-next-next;free(pos-next);pos-next NULL;
} 3.4 实现代码
3.4.1 SList.h #pragma once
#include stdio.h
#include stdlib.h
#include assert.h
//创建单链表
typedef int SLNDataType;
typedef struct SLNode
{SLNDataType val;struct SLNode* next;
}SLNode;//打印单链表
//尽量不要动phead
void SLTPrint(SLNode* phead);
//开辟新空间
SLNode* CreateNode(SLNDataType x);//尾插
void SLTPushBack(SLNode** pphead, SLNDataType x);
//头插
void SLTPushFront(SLNode** pphead, SLNDataType x);
//尾删
void SLTPopBack(SLNode** pphead);
//头删
void SLTPopFront(SLNode** pphead);//查找
SLNode* SLTFind(SLNode* phead, SLNDataType x);
//在pos前面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);
//删除pos位置
void SLTErase(SLNode** pphead, SLNode* pos); // 单链表在pos位置之后插入x
void SLTInsertAfter(SLNode* pos, SLNDataType x);
// 单链表删除pos位置之后的值
void SLTEraseAfter(SLNode* pos);//销毁
void SLTDestroy(SLNode** pphead);3.4.2 SList.c #define _CRT_SECURE_NO_WARNINGS 1
#includeSList.h
//打印单链表
//尽量不要动phead
void SLTPrint(SLNode* phead)
{SLNode* cur phead;while (cur ! NULL){printf(%d-, cur-val);cur cur-next;}printf(NULL\n);
}
//开辟新空间
SLNode* CreateNode(SLNDataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-next NULL;return newnode;
}
//尾插
void SLTPushBack(SLNode** pphead, SLNDataType x)
{SLNode* newnode CreateNode(x);if (*pphead NULL){*pphead newnode;}else{SLNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}
//头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{SLNode* newnode CreateNode(x);newnode-next *pphead;*pphead newnode;
}
//尾删
void SLTPopBack(SLNode** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLNode* prev NULL;SLNode* tail *pphead;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}
}
//头删
void SLTPopFront(SLNode** pphead)
{assert(*pphead);SLNode* tmp *pphead;*pphead (*pphead)-next;free(tmp);
}
//查找
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{SLNode* cur phead;while (cur){if (cur-val x){return cur;}else{cur cur-next;}}return NULL;
}
//在pos前面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);assert(pos);assert(*pphead);//assert((!pos !(*pphead)) || (pos (*pphead)));if (*pphead pos){SLTPushFront(pphead, x);}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLNode* newnode CreateNode(x);prev-next newnode;newnode-next pos;}
}
//删除pos位置
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(pos);assert(*pphead);if (*pphead pos){SLTPopFront(pphead);}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}
// 单链表在pos位置之后插入x
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{SLNode* newnode CreateNode(x);newnode-next pos-next;pos-next newnode;
}
// 单链表删除pos位置之后的值
void SLTEraseAfter(SLNode* pos)
{assert(pos-next ! NULL);pos-next pos-next-next;free(pos-next);pos-next NULL;
}
//销毁
void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur *pphead;while (cur-next ! NULL){SLNode* next cur-next;free(cur);cur next;}*pphead NULL;
}4.带头双向循环链表的实现
4.1 认识带头双向循环链表
4.1.1 双向链表
我们之前认学习的单链表是包含一个next指针指向下一个结点而双向链表既有next指针又有一个前指针指向前一个结点
4.1.2 循环链表
循环链表就是最后一个结点的next不指向NULL指向第一个结点
4.1.3 带头链表
带头链表就是带哨兵位的头结点head头结点不存数据
4.1.4 带头双向循环链表 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单
4.1.5 双向链表的优势和不足 双向链表的优势 任意位置插入删除都是O(1)按需申请释放合理利用空间不存在浪费 问题 下标的随机访问不方便O(N) 4.1.6 顺序表的优势和不足 顺序表的优势 支持下标的随机访问O(1) 问题 头插或中间插入的效率低O(N)空间不够需要扩容有一定的消耗且可能存在一定的空间浪费只适合尾插尾删 4.2 实现带头双向循环链表
同样我们创建三个文件来实现
4.2.1 创建带头双向循环链表
我们在结构体中定义val存数据prev指向前一个结点next指向下一个结点
4.2.2 初始化
让phead-next和phead-prev都指向phead给phead-val赋值为-1最后返回phead
4.2.3 创建返回链表的头结点
4.2.4 打印链表
4.2.5 尾插
4.2.6 尾删
4.2.7 头插
4.2.8 头删
头结点不能删
所以我们要assert(phead-next ! phead)
4.2.9 查找
4.2.10 在pos位置前插入
特殊情况 LTInsert(phead-next,x)就是头插LTInsert(phead,x)就是尾插
4.2.11 删除pos位置
特殊情况 LTErase(phead-next)就是头删LTErase(phead-prev)就是尾删
4.2.12 销毁
4.3 实现代码
4.3.1 ListNode.h #pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
typedef int LTDataType;
typedef struct ListNode
{LTDataType val;struct ListNode* prev;struct ListNode* next;
}LTNode;//初始化
LTNode* LTInit();
//创建返回链表的头结点.
LTNode* CreateLTNode(LTDataType x);
//打印
void LTPrint(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置前插入
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置
void LTErase(LTNode* pos);
//销毁
void LTDestroy(LTNode* phead); 4.3.2 ListNode.c #define _CRT_SECURE_NO_WARNINGS 1
#includeListNode.h
//初始化
LTNode* LTInit()
{LTNode* phead CreateLTNode(-1);phead-next phead;phead-prev phead;return phead;
}
//创建返回链表的头结点.
LTNode* CreateLTNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-next NULL;newnode-prev NULL;return newnode;
}
//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;printf(哨兵位);while (cur ! phead){printf(%d, cur-val);cur cur-next;}printf(哨兵位\n);
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail phead-prev;LTNode* newnode CreateLTNode(x);tail-next newnode;newnode-prev tail;phead-prev newnode;newnode-next phead;
}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTNode* tail phead-prev;LTNode* tailPrev tail-prev;free(tail);tailPrev-next phead;phead-prev tailPrev;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode CreateLTNode(x);LTNode* first phead-next;newnode-next first;first-prev newnode;phead-next newnode;newnode-prev phead;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTNode* first phead-next;LTNode* second first-next;phead-next second;second-prev phead;free(first);first NULL;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-val x){return cur;}cur cur-next;}return NULL;
}
//在pos位置前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode CreateLTNode(x);LTNode* posprev pos-prev;posprev-next newnode;newnode-prev posprev;newnode-next pos;pos-prev newnode;
}
//删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev pos-prev;LTNode* posnext pos-next;posprev-next posnext;posnext-prev posprev;free(pos);pos NULL;
}
//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);phead NULL;
} 5.数组下标为什么从0开始 我们在学习数组时会有这个疑问
数组元素的下标为什么从0开始而不从1开始呢
从1开始更符合我们的日常习惯比如生活中我们通常说第1个而不是第0个
5.1 原因
对于数组元素的访问在操作系统层其实就是对特定内存偏移量的数据的访问
换而言之即如果想要访问一个数组的某一个元素的值那么首先就要计算它的地址偏移量
其大概的公式为:
a[k]_adress base_address k*type_size ;
倘若数组下标是从1开始那么地址计算公式即会转变为:
a[k]_adress base_address (k-1)*type_size ; 这对于CPU来说多了一次减法操作 简单一句话: 就是为了方便 计算出每个元素的具体内存地址 因为数组变量 实际上在内存上储存的是这个数组变量中第一个元素的的首地址,而系统在取数组中某个元素的值时,必须要得到具体的那个元素的地址才能获取到对应的值
具体每个元素的内存地址 数组变量首地址 下标 x 每个元素占用的字节数
比如: int a[5]{10,11,12,13,14} 因为 int每个元素占用4个字节,所以 数组中每个相邻的元素内存地址都相差4,
那么每个元素的地址就等于前一个元素的地址 4
a[0] 的内存地址 a的地址 0 * 4 (第一个元素的地址计算结果 跟数组的首地址一样)a[1] 的内存地址 a的地址 1 * 4 (下标是1,内存地址就就是首地址 偏移 4字节)a[2] 的内存地址 a的地址 2 * 4 (下标是2,内存地址就首地址 偏移 8字节)..........a[5]的内存地址 a的地址 5 * 4 (下标是5 内存地址就是首地址 偏移 20字节)
如果从1开始 就要减去1,多一步运算,效率自然不让直接点高
所以数组的索引(下标)从0开始是为了方便计算每个元素的地址
如果从1开始的话运算起来没有从0开始方便
所以大部分编程语言数组索引都是从0开始
5.2 拓展
为什么计算机语言中的下标都是从0开始的 - 知乎 (zhihu.com)
6.环型链表
6.1 环型链表是什么 尾结点不指向NULL指向头就是循环链表 那么带环链表就意味着尾结点的next可以指向链表的任意一个结点甚至可以指向他自己 这里我们的算法思路唯一靠谱的还是快慢指针
slow一次走一步fast一次走两步当slow走到中间的时候fast一定入环了如果fast指向NULL则该链表无环 当slow再走一半也就入环了这个时候由于slow走的慢fast走的快所以fast和slow最终会相遇的 6.2 快慢指针判断环形链表
我们在前面文章中写过用快慢指针判断链表是否带环
leetcode环形链表-CSDN博客
我们用的是slow指针一次走一步fast指针一次走两步当slow入环后开始了追击每走一次距离缩短1最终就会相遇
6.2.1 思考
但是我们思考一个问题如果slow一次走一步fast一次走三步会不会相遇呢
思考这个问题我们可以做一个假设
假设环的长度是C假设slow进环时fast与slow之间的距离为N
6.2.2 推导思路
接着我们可以推一下
如果slow一次走一步fast一次走三步每次追击距离缩小2
所以我们可以得出初步的结论
如果N是偶数就直接追上了如果N是奇数C是奇数第一轮错过了第二轮就追上了如果N是奇数C是偶数就永远追不上
结论的第三条其实条件是不成立的我们画图推一下
所以这里我们就能得到一个结论
如果N是奇数C是偶数这个等式的条件是不成立的所以不可能出第三种情况
6.2.3 结论
所以我们可以得出最终的结论 如果N是偶数就直接追上了如果N是奇数C是奇数第一轮错过了第二轮就追上了不可能出现N是奇数C是偶数的情况 所以如果slow一次走一步fast一次走三步一定能追上
