数据结构之顺序表和链表
线性表
线性表是数据结构中最基本且常用的一种形式，用于存储具有线性关系的数据元素。其特点是数据元素之间存在一对一的顺序关系。线性表（linear list）是n个具有相同特性的数据元素的有限序列。常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
线性表支持以下常见操作：
-
初始化：创建一个空表。
-
插入：在指定位置插入元素。
-
删除：删除指定位置的元素。
-
查找：按值或位置查找元素。
-
更新：修改指定位置的元素值。
-
遍历：访问表中的每个元素。
-
求长度：返回表中元素的个数。
-
判断空表：检查表是否为空。
两种主要存储方式：
顺序表（顺序储存）
-
定义：用一组连续的内存单元依次存储数据元素。
-
特点：
-
随机访问：通过下标直接访问元素，时间复杂度为O(1)。
-
插入和删除效率低：需要移动大量元素，时间复杂度为O(n)。
-
存储密度高：仅存储数据元素，无需额外空间。
-
-
实现：通常使用数组。
-
类型：静态顺序表：使用定长数组存储元素。动态顺序表：使用动态开辟的数组存储。
//静态顺序表
struct SeqList
{
int arr[100];//定长数组
int size;//顺序表当前有效的数据个数
};
//动态顺序表
typedef struct SeqList
{
SLDataType* arr;
int size;//有效的数据个数
int capacity;//空间大小
}SL;
动态顺序表的实现 SeqList.h
#include <stdio.h>
#include <stdlib.h>
#include<assert.h>
//typedef int SLDataType;//方便后续类型的替换
typedef struct SeqList
{
SLDataType* arr;
int size;//有效的数据个数
int capacity;//空间大小
}SL;
//顺序表初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
void SLPrint(SL s);
//头部插入/尾部插入
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);
//查找
int SLFind(SL* ps, SLDataType x);SeqList.c
#include"SeqList.h"
void SLInit(SL* ps)
{
ps->arr= NULL;
ps->size = ps->capacity = 0;
}
void SLDestroy(SL* ps)
{
if (ps->arr)
{
free(ps->arr);
}
ps -> arr = NULL;
ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)
{
//插入数据之前先看空间够不够
if (ps->capacity == ps->size)
{
//申请空间
//增容
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);//直接退出程序，不再继续执行
//return;
}
//空间申请成功
ps->arr = tmp;
ps->capacity = newcapacity;
}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
温柔的方式
//if (ps == NULL)
//{
// return;
//}
assert(ps);//等价于assert(ps!=NULL)
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
//等价于
//ps->arr[ps->size]=x;
//++ps->size;
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
//先让顺序表中已有的数据往后移动
for (int i = ps->size; i>0; i--)
{
ps->arr[i] = ps->arr[i - 1];//arr[1]=arr[0]
}
ps->arr[0] = x;
ps->size++;
}
//void SLPrint(SL s)
//{
// for (int i = 0; i < s.size; i++)
// {
// printf("%d ", s.arr[i]);
// }
// printf("\n");
//}
//尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
//顺序表不为空
//ps->arr[ps->size - 1] = -1;
--ps->size;
}
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
//顺序表不为空
//数据整体往前挪
for (int i = 0; i < ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];
//arr[size-2]=arr[size-1];
}
ps->size--;
}
//在指定位置之前插入数据
//pos表示下标
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
//插入数据:空间够不够
SLCheckCapacity(ps);
//让pos及之后的数据往后移动一位
for (int i =ps->size; i > pos ; i--)
{
ps->arr[i] = ps->arr[i - 1];
//arr[pos+1]=arr[pos]
}
ps->arr[pos] = x;
ps->size++;
}
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i<ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];
//arr[size-2]=arr[size-1]
}
ps->size--;
}
//查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
//找到了
return i;
}
}
//没有找到 无效下标
return -1;
}链表
-
定义：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
-
特点：
-
插入和删除效率高：只需修改指针，时间复杂度为O(1)。
-
随机访问效率低：需要从头遍历，时间复杂度为O(n)。
-
存储密度低：需要额外空间存储指针。
-
-
类型：
-
单链表：每个节点只包含指向下一个节点的指针。
-
双向链表：每个节点包含指向前后节点的指针。
-
循环链表：尾节点指向头节点，形成环。
-
单向或者双向：
带头或者不带头：
循环或者非循环：
单链表
无头单向不循环单链表的实现 SList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//定义节点的结构
//数据+指向下一个节点的指针
typedef int SLTDataType;
typedef struct SListNode
{
int data;
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);SList.c
#include "SList.h"
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)//pcur!=NULL
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//*pphead就是指向第一个结点的指针
//空链表和非空链表
SLTNode* newnode = SLTBuyNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//要先找到尾节点，再将尾节点和新节点连接起来
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
//ptail指向的就是尾节点
ptail->next = newnode;
}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//空链表和非空链表
SLTNode* newnode = SLTBuyNode(x);
// newnode *pphead
newnode->next = *pphead;
*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
//链表不能为空
assert(pphead && *pphead);
//链表只有一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//链表有多个节点
else
{
//找尾
SLTNode* prev = *pphead;
SLTNode* ptail = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}
void SLTPopFront(SLTNode** pphead)
{
//链表不能为空
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//pcur==NULL
return NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
//链表不为空 pos就说明链表不可能为空
assert(pphead && *pphead);
assert(pos);
SLTNode* prev = *pphead;
//若pos==*pphead;说明是头插
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
while (prev->next != pos)
{
prev = prev->next;
//pos的前一个节点
}
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos;
prev->next = newnode;
}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
assert(pos);
//pos是头节点
if (pos == *pphead)
{
//头删
SLTPopFront(pphead);
}
//不是
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos&&pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
void SListDesTroy(SLTNode** pphead)
{
//销毁一个一个节点
assert(pphead&&*pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}双链表
带头双向循环链表的实现 List.h
#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;
}LTNode;
//声明双向链表中提供的方法
//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDesTroy(LTNode* phead);
void LTprint(LTNode* phead);
//插入数据之前，链表必须初始化到只有一个头结点的情况
//哨兵位节点不能被删除，节点的地址也不能发生改变
//一级指针即可 （不改变哨兵位的位置）
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void PopBack(LTNode* phead);
//头删
void PopFront(LTNode* phead);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点处的数据
void LTErase(LTNode* pos);
LTNode* LTfind(LTNode* phead, LTDataType x);List.c
#include "List.h"
void LTprint(LTNode* phead)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
//申请节点
LTNode* LTBuyNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}
node->data = x;
node->next = node->prev = node;
//不能置为NULL 需要满足双向链表的循环条件
return node;
}
//void LTInit(LTNode** pphead)
//{
// //给双向链表创建一个哨兵位
// *pphead = LTBuyNode(-1);
//}
LTNode* LTInit()
{
LTNode* phead = LTBuyNode(-1);
return phead;
}
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
//这两行不能交换位置
}
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
//尾删
void PopBack(LTNode* phead)
{
//链表必须有效且链表不能为空（只有一个哨兵位）
assert(phead&&phead->next!=phead);
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
//删除
free(del);
del = NULL;
}
//头删
void PopFront(LTNode* phead)
{
assert(phead && phead->next != NULL);
LTNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
LTNode* LTfind(LTNode* phead, LTDataType x)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}
//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->prev = pos;
newnode->next = pos->next;
pos->next->prev = newnode;
pos->next=newnode;
}
void LTErase(LTNode* pos)
{
assert(pos);
pos->next->prev= pos->prev;
pos->prev->next= pos->next;
free(pos);
pos = NULL;
}
//销毁
void LTDesTroy(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//此时pcur指向phead,而phead还没有被销毁
free(phead);
phead = NULL;
}对比
链表例题
1.面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
int kthToLast(struct ListNode* head, int k)
{
struct ListNode* fast,*slow;
fast = slow = head;
//fast先走k步
while(k--)
{
fast=fast->next;
}
//然后再一起走
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow->val;
}
2. 206. 反转链表 - 力扣（LeetCode）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
//思路1：创建新的链表将原链表的节点拿过来头插
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur= head ;
struct ListNode* newhead = NULL;
while(cur)
{
struct ListNode* next=cur->next;
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}3.876. 链表的中间结点 - 力扣（LeetCode）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast,* slow;
fast = head, slow = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}4.链表的回文结构_牛客题霸_牛客网
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
//找到中间节点 然后逆置中间节点的后面节点 然后再进行比较
class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast&&fast->next)//不能交换位置
{
slow = slow->next;
fast = slow->next->next;
}
//此时slow指向的刚好是中间节点
return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur=head;
struct ListNode* newhead=NULL;
while(cur)
{
struct ListNode*next=cur->next;
//头插
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}
bool chkPalindrome(ListNode* A)
{
struct ListNode* mid=middleNode(A);
struct ListNode* rmid=reverseList(mid);
while(rmid&&A)
{
if(rmid->val!=A->val)
{
return false;
}
rmid=rmid->next;
A=A->next;
}
return true;
}
};5.203. 移除链表元素 - 力扣（LeetCode）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode Listnode;
//思路:创建新的链表 将值！=val的 数字 尾插到新的链表当中 然后返回新的链表的头
struct ListNode* removeElements(struct ListNode* head, int val)
{
Listnode* newhead,*newtail;
newhead = newtail = NULL;
Listnode* pcur = head;
while(pcur)
{
if(pcur->val!=val)
{
if(newhead==NULL)
{
newhead=newtail=pcur;
}
else
{
newtail->next=pcur;
newtail=newtail->next;
}
}
pcur=pcur->next;
}
if(newtail)
newtail->next=NULL;
return newhead;
}6.21. 合并两个有序链表 - 力扣（LeetCode）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
//创建新链表 遍历原链表 将节点值小的拿到新链表中进行 尾插
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if(list1==NULL && list2==NULL)
return NULL;
if(list1==NULL)
return list2;
if(list2==NULL)
return list1;
struct ListNode* l1=list1;
struct ListNode* l2=list2;
struct ListNode* newhead, *newtail;
newhead=newtail= (struct ListNode*)malloc(sizeof(struct ListNode));
while(l1 && l2)
{
if(l1->val < l2->val)
{
newtail->next=l1;
newtail=newtail->next;
l1=l1->next;
}
else
{
newtail->next=l2;
newtail=newtail->next;
l2=l2->next;
}
}
if(l1)
{
newtail->next=l1;
}
if(l2)
{
newtail->next=l2;
}
struct ListNode* ret=newhead->next;
free(newhead);
newhead=NULL;
return ret;
}7.160. 相交链表 - 力扣（LeetCode）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
//相交：判断尾指针 用尾地址判断 不要用值判断
//思路：A链表的节点依次和B链表所有节点比较，A某个节点和B某个节点相等，这个节点就是交点 4
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
ListNode* curA=headA;
ListNode* curB=headB;
int lenA=0;
int lenB=0;
while(curA->next)
{
curA=curA->next;
++lenA;
}
while(curB->next)
{
curB=curB->next;
++lenB;
}
if(curA!=curB)
{
return NULL;
}
int gap=abs(lenA-lenB);
//假设
ListNode* longlist=headA;
ListNode* shortlist=headB;
if(lenA<lenB)
{
longlist=headB;
shortlist=headA;
}
while(gap--)
{
longlist=longlist->next;
}
while(longlist!=shortlist)
{
longlist=longlist->next;
shortlist=shortlist->next;
}
return longlist;
}8.链表分割_牛客题霸_牛客网
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x)
{
struct ListNode *greathead, *greattail;
struct ListNode *smallhead, *smalltail;
struct ListNode *pcur = pHead;
greathead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode));
smallhead = smalltail = (struct ListNode*)malloc(sizeof(struct ListNode));
while(pcur)
{
if(pcur->val < x)
{
smalltail->next = pcur;
smalltail = pcur;
}
else
{
greattail->next = pcur;
greattail = pcur;
}
pcur = pcur -> next;
}
smalltail -> next = greathead->next;
greattail -> next = nullptr;
return smallhead -> next;
}
};