线性表(linear list)是n个具有相同特性的数据元素的有限序列
线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串..
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储:
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构
一般情况下采用数组存储,在数组上完成数据的增删查改
顺序表一般可以分为:
静态顺序表:使用定长数组存储元素
1.1.3 动态顺序表
动态顺序表:使用动态开辟的数组存储
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的
现实中
数据结构中
注意:
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:
无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向 循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。
与程序员相关的CPU缓存知识 | 酷 壳 - CoolShell
顺序表的初始化我们只需要讲指针置为空指针 然后将当前数据元素个数和最大数据元素个数置为0 到插入时我们便会动态开辟空间给指针a
//顺序表的初始化
void SLInit(SL* ps)
{
ps->a = NULL;//置为空指针
ps->size = 0;//数据个数为0
ps->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];
}
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[begin+1];
++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;
}
#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);
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
//顺序表的初始化
void SLInit(SL* ps)
{
ps->a = NULL;//置为空指针
ps->size = 0;//数据个数为0
ps->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[begin+1];
++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;
}
顺序表存在下面的问题:
如果想要插入一个结点,就不需要挪动数据了,改指针的指向就可以了
同样我们删除结点,直接将前一个结点的指针指向后一个结点就可以了
首先我们还是从工程的角度去考虑,创建SList.h SList.c test.c三个文件
SList.h放置函数的声明
SList.c放置函数的定义
test.c进行测试
//打印单链表
//尽量不要动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;
}
}
//销毁
void SLTDestroy(SLNode** pphead)
{
assert(pphead);
SLNode* cur = *pphead;
while (cur->next != NULL)
{
SLNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = 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;
}
#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);
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.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;
}
我们之前认学习的单链表,是包含一个next指针指向下一个结点,而双向链表既有next指针,又有一个前指针指向前一个结点
循环链表就是最后一个结点的next不指向NULL,指向第一个结点
带头链表就是带哨兵位的头结点head,头结点不存数据
双向链表的优势:
问题:
顺序表的优势:
问题:
同样我们创建三个文件来实现:
我们在结构体中定义val存数据,prev指向前一个结点,next指向下一个结点
让phead->next和phead->prev都指向phead,给phead->val赋值为-1,最后返回phead
头结点不能删!!!
所以我们要assert(phead->next != phead)
特殊情况:
特殊情况:
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.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);
#define _CRT_SECURE_NO_WARNINGS 1
#include"ListNode.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;
}
我们在学习数组时会有这个疑问:
数组元素的下标为什么从0开始而不从1开始呢?
从1开始更符合我们的日常习惯,比如生活中我们通常说第1个,而不是第0个
对于数组元素的访问在操作系统层其实就是对特定内存偏移量的数据的访问
换而言之即如果想要访问一个数组的某一个元素的值那么首先就要计算它的地址偏移量
其大概的公式为:
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
如果从1开始 就要减去1,多一步运算,效率自然不让直接点高
所以数组的索引(下标)从0开始是为了方便计算每个元素的地址
如果从1开始的话,运算起来没有从0开始方便
所以,大部分编程语言数组索引都是从0开始
为什么计算机语言中的下标都是从0开始的? - 知乎 (zhihu.com)
尾结点不指向NULL,指向头就是循环链表
那么带环链表就意味着尾结点的next可以指向链表的任意一个结点,甚至可以指向他自己
这里我们的算法思路唯一靠谱的还是快慢指针
slow一次走一步,fast一次走两步,当slow走到中间的时候,fast一定入环了,如果fast指向NULL,则该链表无环
当slow再走一半也就入环了,这个时候,由于slow走的慢,fast走的快,所以fast和slow最终会相遇的
我们在前面文章中写过用快慢指针判断链表是否带环:
我们用的是slow指针一次走一步,fast指针一次走两步,当slow入环后开始了追击,每走一次距离缩短1,最终就会相遇
但是我们思考一个问题:如果slow一次走一步,fast一次走三步,会不会相遇呢?
思考这个问题我们可以做一个假设:
假设环的长度是C,假设slow进环时,fast与slow之间的距离为N
接着我们可以推一下:
如果slow一次走一步,fast一次走三步,每次追击距离缩小2
所以我们可以得出初步的结论:
结论的第三条其实条件是不成立的,我们画图推一下:
所以这里我们就能得到一个结论
如果N是奇数,C是偶数,这个等式的条件是不成立的,所以不可能出第三种情况
所以我们可以得出最终的结论:
所以如果slow一次走一步,fast一次走三步,一定能追上