【数据结构】顺序表和链表基本实现（含全代码）

一、什么是线性表

概念：线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…。线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

关于为什么物理结构上并不一定是连续的，可以看我的另外一篇文章【c语言】动态内存管理

1. 什么是顺序表

概念： 首先，顺序表是线性表其中之一；其次，顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。
   

a.静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
b. 那我们在学习数据结构之前，肯定学习了C语言，C语言的题目大多是以IO的形式进行调试的，而我们学数据结构的题目大多是以接口的形式进行调试的。
2. 动态顺序表：使用动态开辟的数组存储。

接口的实现：

#pragma once
// SeqList.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 顺序表的动态存储
typedef int SLDataType;
typedef struct SeqList
{SLDataType* a;  // 指向动态开辟的数组[a是array的意思]-----关于这里动态开辟和数组的问题见下面解释int size ;    // 有效数据个数int capicity ;  // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化void SeqListInit(SeqList* ps);
// 检查空间，如果满了，进行增容
void SeqListCheckCapacity(SeqList* ps);
// 顺序表尾插
void SeqListPushBack(SeqList* ps, SLDateType x);
// 顺序表尾删
void SeqListPopBack(SeqList* ps);
// 顺序表头插
void SeqListPushFront(SeqList* ps, SLDateType x);
// 顺序表头删
void SeqListPopFront(SeqList* ps);
// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x, int begin);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);
// 顺序表销毁
void SeqListDestroy(SeqList* ps);
// 顺序表打印
void SeqListPrint(SeqList* ps);

#define _CRT_SECURE_NO_WARNINGS 1
//SeqList.c
#include "SeqList.h"
//动态顺序表
void SeqListInit(SeqList* ps)
{assert(ps);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}void SeqListCheckCapacity(SeqList* ps)
{assert(ps);if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDateType* tmp = (SLDateType*)realloc(ps->a, newCapacity*sizeof(SLDateType));if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}
}void SeqListPushBack(SeqList* ps, SLDateType x)
{	//assert(ps);//SLCheckCapacity(ps);//ps->a[ps->size] = x;//因为顺序表的数据存放要连续//ps->size++;SeqListInsert(ps, ps->size ,x);}
void SeqListPopBack(SeqList* ps)
{//assert(ps);//assert(ps->size > 0);//ps->a[ps->size - 1] = 0;//ps->size--;SeqListErase(ps, ps->size - 1);
}
void SeqListPushFront(SeqList* ps, SLDateType x)
{//assert(ps);//SLCheckCapacity(ps);从前往后挪动数据 -- 再在前面插入数据//int end = ps->size - 1;//while (end >= 0)//{//	ps->a[end + 1] = ps->a[end];//	end--;//}//ps->a[0] = x;//ps->size++;SeqListInsert(ps, 0, x);}
void SeqListPopFront(SeqList* ps)
{//assert(ps);//assert(ps->size > 0);//int begin = 1;//while (begin < ps->size )//{//	ps->a[begin - 1] = ps->a[begin];//	begin++;//}//ps->size--;SeqListErase(ps, 0);}
int SeqListFind(SeqList* ps, SLDateType x ,int begin){assert(ps);for (int i = begin; i < ps->size; i++){if (ps->a[i] == x){return 1;}}return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType 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 SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}
void SeqListDestroy(SeqList* ps)
{assert(ps);if (ps->a != NULL){free(ps->a);ps->a = NULL;ps->size = 0;ps->capacity = 0;}
}
void SeqListPrint(SeqList* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d" , ps->a[i]);}printf("\n");}

动态开辟空间和数组的问题解释

1. [ ]运算符是C语言几乎最高优先级的运算符。[ ]运算符需要两个操作数，一个指针类型，一个整数。
2. 标准的写法是这样的：a[int]。这样编译器会返回 *(a+int) 的值。 a[int] 就等于 *(a + int)。
3. 平时static开辟的空间是存在静态区；而在函数中定义使用的数组是存在栈区；而malloc动态开辟空间返回地址，解决了静态数组而需要实时更改数组大小以及一系列的问题。关于malloc动态内存管理可以看我之前写的文章
   【c语言】动态内存管理

LeetCode-exercise

1. 原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。

2. 什么是链表

概念：首先，链表是线性表之一；其次，链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

2.1链表的分类

1. 单向或者双向
   

2. 带头或者不带头
   
3. 循环或者非循环
   

2.2常用的链表结构及区别

1. 那么组合起来呢，2 ^ 3 = 8，所以总共有 8 种链表结构。但是常用的链表结构呢？主要有两种，无头单向非循环链表和带头双向循环链表
   
2. 区别：
   a.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
   b. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

2.3无头单向非循环链表的实现

//#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// slist.h// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x);
//节点的连接
SListNode* CreateSList(int n);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);// 单链表的销毁
void SListDestroy(SListNode** plist);

SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;//申请节点先保证 这个指针不是野指针  初始化return newnode;
}
//SListNode* plist = CreateSList(5);
SListNode* CreateSList(int n)//最后phead地址传给CreateSList
{SListNode* phead = NULL,*ptail = NULL;for (int i = 0; i < n; i++){SListNode* newnode = BuySListNode(i);if (phead == NULL){ptail = phead = newnode;}else{ptail->next = newnode;ptail = newnode;}}return phead;
}// 单链表打印
//SListPrint(plist);
void SListPrint(SListNode* plist)//此时的plist是 上面传回来的 phead
{SListNode * cur = plist;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;//下一个节点的地址}printf("NULL\n");//表示链表遍历结束，标识没有下一个节点
}
// 单链表尾插--------最后一个节点连接新节点
//SListPushBack(&plist , 100);
void SListPushBack(SListNode** pplist, SLTDateType x)//传递过来的是指针变量的地址
{//这里要改变的是实参，所以要用** plist；如果这里传的是plist，则无法通过改变形参来达到改变实参SListNode* newnode = BuySListNode(x);if (*pplist == NULL)//如果前面没有开辟 节点，链表为空{//这里就是解引用访问*plist     为访问指针pplist*pplist = newnode;}else{SListNode* tail = *pplist;while (tail->next)//直到最后tail->next节点结束位置，获取到tail的地址{tail = tail->next;}tail->next = newnode;//给tail后面 新开辟节点地址  实现尾插}
}// 单链表的头插 
void SListPushFront(SListNode** pplist, SLTDateType x)
{	//如果pplist为NULL  不用检查  不影响SListNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;//生成新的    头地址指针
}
// 单链表的尾删
//SListPopBack(&pplist);
void SListPopBack(SListNode** pplist)
{	//暴力的检查 assert(*pplist);//排除 链表为空时 还继续一直删除if ((*pplist)->next == NULL){free(*pplist);*pplist = NULL;//此时又实参与由形参的问题}else{SListNode* tail = *pplist;while (tail->next->next){tail = tail->next;}free(tail->next);//tail == NULL;  tail是个局部变量 tail->next = NULL;}
}// 单链表头删
void SListPopFront(SListNode** pplist)
{	//链表为空 不用删assert(*pplist);SListNode* next = (*pplist)->next;//*和->都是解引用 ，优先级确定不了所以要加括号free(*pplist);*pplist = next;
}
// 单链表查找
//SListNode* pos = SListFind(plist , 3);
//
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur = plist;while (cur){if (cur->data = x){return cur;}cur = cur->next;}return NULL;
}
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}
void SListEraseAfter(SListNode* pos)
{assert(pos);if (pos->next == NULL){return; }else{//free(pos->next);//pos->next = pos->next->next;//如果pos的next被释放则其值为随机值，但原本应该存放next的next的地址SListNode* nextNode = pos->next;pos->next = nextNode->next;free(nextNode);}
} // 单链表的销毁
void SListDestroy(SListNode** plist)
{SListNode* cur = *plist;while (cur){SListNode* next = cur->next;free(cur);cur = next;}*plist = NULL;
}

2.4带头双向循环链表的实现

//.h
// 2、带头+双向+循环链表增删查改实现
#pragma once#include <stdio.h>
#include <assert.h>
#include <stdlib.h>// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType _data;struct ListNode* _next;struct ListNode* _prev;
}ListNode;//创建一个节点
ListNode* BuyListNode(LTDataType x);// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

#define _CRT_SECURE_NO_WARNINGS 1#include "DList.h"ListNode* BuyListNode(LTDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){perror("malloc fail");exit(-1);}node->_data = x;node->_next = NULL;node->_prev = NULL;return node;}
// 创建返回链表的头结点.
ListNode* ListCreate()
{ListNode* phead = BuyListNode(-1);phead->_next = phead;phead->_prev = phead;return phead;
}
// 双向链表销毁
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->_next;while (cur != pHead){ListNode* ne_nextxt = cur->_next;free(cur);cur = ne_nextxt;}free(pHead);//phead = NULL;}
// 双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->_next;printf("guard<=>\n");while (cur != pHead) {printf("%d<=>", cur->_data);cur = cur->_next;}printf("\n");}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode = BuyListNode(x);ListNode* tail = pHead->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = pHead;pHead->_prev = newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);assert(pHead->_next != pHead);  // 空ListNode* tail = pHead->_prev;ListNode* tailPrev = tail->_prev;tailPrev->_next = pHead;pHead->_prev = tailPrev;free(tail);
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);/*LTNode* newnode = BuyListNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;*/ListNode* newnode = BuyListNode(x);ListNode* first = pHead->_next;// phead newnode first // 顺序无关pHead->_next = newnode;newnode->_prev = pHead;newnode->_next = first;first->_prev = newnode;
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead->_next != pHead); // 空/*LTNode* first = phead->next;LTNode* second = first->next;free(first);phead->next = second;second->prev = phead;*/ListErase(pHead->_next);
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur = pHead->_next;while (cur != pHead){if (cur->_data == x){return cur;}cur = cur->_next;}return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* _prev = pos->_prev;ListNode* newnode = BuyListNode(x);// prev newnode pos_prev->_next = newnode;newnode->_prev = _prev;newnode->_next = pos;pos->_prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* _prev = pos->_prev;ListNode* _next = pos->_next;free(pos);_prev->_next = _next;_next->_prev = _prev;
}

2.5循序表和链表的区别

LeetCode-exercise

1.删除链表中等于给定值 val 的所有结点

3. 快慢指针

LeetCode-exercise

1. 给你一个链表的头节点 head ，判断链表中是否有环。

方法一：暴力解法：判断引用地址是否重复

1. 这道题最简单的做法就是在遍历链表的同时记录下每一个节点，在遍历过程中不停的判断当前节点是不是之前已经记录过的节点。
2. 如果遍历时发现有和记录下来的节点重复的，则证明是环形链表； 如果整个链表能够遍历完也没有重复节点，则证明不是环形链表。

方法二：快慢指针解法：简单原理就是用两个指针，一个快，一个慢。 慢指针走一步，快指针走两步。

1. 如果存在环，那么快指针始终可以追上慢指针，即两个指针一定会出现指向同一个节点的状态，就好像赛跑中被套圈。
2. 因为是判断链表是否有环，所以我们考虑使用追及相遇来解决。我们使用快慢指针fast和slow，初始化它们都为头结点，然后让slow一次走一步，fast一次走两步。
3. 为什么肯定能追击上呢？
   如果存在环，当slow进环时，fast肯定在环里，此时两者相差N的距离，这个时候它们开始追及。因为fast的步长是slow的两倍，所以它们之间的距离每走一次是减小1的，它们之间的距离逐渐逼近，这样slow和fast一定可以相遇。当它们距离减小到0时，即它们相遇，这个时候就可以确定链表肯定有环。
   

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode* slow = head, *fast = head;while(fast && fast->next)//如果不带环fast会为NULL；fast不为NULL，那么slow肯定不为NULL，fast->next不为NULL{slow = slow->next;fast = fast->next->next;if(slow == fast)return true;}return false;
}