当前位置：首页 > news >正文

【数据结构】顺序表和链表

news 来源：原创 2025/6/8 21:23:48

线性表

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

顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为:

1. 静态顺序表:使用定长数组存储元素
2.动态顺序表

Seqlist.h

Seqlist.c

#include"Seqlist.h"void SLInit(SL* ps){ps->a = (SLDataType*)malloc(sizeof(SLDataType)* INIT_CAPACITY);if (ps->a == NULL) {perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}
void SLDestroy(SL* ps) {assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}
void SLPrint(SL* ps) {assert(ps);int i = 0;for (i = 0;i < ps->size;i++) {printf("%d ", ps->a[i]);}printf("\n");
}
void SLCheckCapacity(SL* ps) {assert(ps);if (ps->size == ps->capacity) {SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL) {perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}
void SLPushBack(SL* ps, SLDataType x) {//assert(ps);//扩容//SLCheckCapacity(ps);//ps->a[ps->size++] = x;SLInsert(ps, ps->size, x);}
void SLPopBack(SL* ps) {assert(ps);//暴力检查assert(ps->size > 0);//温柔地检查//if (ps->size == 0)//	return;ps->size--;
}
void SLPushFront(SL* ps, SLDataType 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++;*/SLInsert(ps, 0, x);
}
void SLPopFront(SL* ps) {assert(ps);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 + 1;while (begin < ps->size) {ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}
int SLFind(SL* ps, SLDataType x){assert(ps);int i = 0;for (i = 0;i < ps->size;i++) {if (ps->a[i] == x) return i;}return -1;
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#include"Seqlist.h"void TestSeqList1(){SL s;SLInit(&s);SLPushBack(&s,1);SLPushBack(&s,2);SLPushBack(&s,3);SLPushBack(&s,4);SLPushBack(&s,5);SLPushBack(&s,6);SLPushBack(&s,7);SLPopBack(&s);SLPopBack(&s);SLPrint(&s);SLDestroy(&s);
}
void TestSeqList2() {SL s;SLInit(&s);SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPushFront(&s, 4);SLPushFront(&s, 5);SLPrint(&s);//头插/头删N个数据，时间复杂度：O（N^2）//尾插/尾删N个数据，时间复杂度：O（N）SLPopFront(&s);SLPrint(&s);SLInsert(&s,4,40);SLPrint(&s);SLInsert(&s,0,40);SLPrint(&s);SLErase(&s, 3);SLPrint(&s);
}
int main() {TestSeqList2();return 0;
}

例1：
在这里插入图片描述

例2：

例3：

顺序表缺点：
1.中间头部插入删除数据，需要挪动数据，效率低下
2.空间不够，扩容。扩容有一定的消耗，其次还可能会有一定空间浪费

链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
在这里插入图片描述
注意:
1.从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

SList.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;typedef struct SListNode {SLTDataType 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* SListFind(SLTNode* phead, SLTDataType x);
//pos前插入
void SListInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x);
//pos位置删除
void SLTErase(SLTNode** pphead,SLTNode* pos);//pos后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//pos后删除
void SLTEraseAfter(SLTNode* pos);//销毁
//void SLTDestroy(SLTNode* phead);
void SLTDestroy(SLTNode** pphead);

SList.c

#include"SList.h"void SLTPrint(SLTNode* phead) {SLTNode* cur = phead;while (cur!=NULL) {printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}
SLTNode* BuySLTNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = BuySLTNode(x);//为空if (*pphead == NULL) {*pphead = newnode;}else {//不为空//找尾SLTNode* tail = *pphead;while (tail->next != NULL) {tail = tail->next;}tail->next = newnode;}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead) {//温柔地检查//if (*pphead == NULL) //	return;//暴力检查assert(pphead);assert(*pphead);//1.只有一个节点//2.有多个节点if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;}else {//找尾/*SLTNode* prev = NULL;SLTNode* tail = *pphead;while (tail->next != NULL) {prev = tail;tail = tail->next;}prev->next = NULL;free(tail);tail = NULL;*/SLTNode* tail = *pphead;while (tail->next->next != NULL) {tail = tail->next;}free(tail->next);tail->next = NULL;}
}
void SLTPopFront(SLTNode** pphead) {//温柔地检查//if (*pphead == NULL) //	return;//暴力检查assert(pphead);assert(*pphead);SLTNode* first = *pphead;*pphead = first->next;free(first);first = NULL;
}
SLTNode* SListFind(SLTNode* phead, SLTDataType x) {SLTNode* cur = phead;while (cur) {if (cur->data == x) {return cur;}cur = cur->next;}return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pos);assert(pphead);if (pos == *pphead) {SLTPushFront(pphead, x);}else {//找到pos前一个位置SLTNode* prev = *pphead;while (prev->next!= pos) {prev = prev->next;}SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(pos);//assert(*pphead);if (*pphead == pos) {SLTPopFront(pphead);}else {SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);}
}//一个单链表，给了pos，但不给头指针，是否能在pos之前插入x
//能，在pos后面插入x，再将pos和x的值交换位置
//删除同理，但不能删尾
void SListInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}
void SLTEraseAfter(SLTNode* pos) {assert(pos);assert(pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}//void SLTDestroy(SLTNode* phead) {
//	SLTNode* cur = phead;
//	while (cur) {
//		SLTNode* tmp = cur->next;
//		free(cur);
//		cur = tmp;
//	}
//}
void SLTDestroy(SLTNode** pphead) {assert(pphead);SLTNode* cur = *pphead;while (cur) {SLTNode* tmp = cur->next;free(cur);cur = tmp;}*pphead = NULL;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"void TestSList1() {SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPopBack(&plist);SLTPopFront(&plist);SLTPopBack(&plist);SLTPrint(plist);
}
void TestSList2() {SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);SLTNode* ret = SListFind(plist, 2);SListInsert(&plist, ret, 20);SLTPrint(plist);SLTNode* res = SListFind(plist, 4);SLTErase(&plist, res);res = NULL;SLTPrint(plist);/*SLTDestroy(plist);plist = NULL;*/SLTDestroy(&plist);SLTPrint(plist);
}
int main() {TestSList2();return 0;
}

例1：
在这里插入图片描述

方法1：

在这里插入图片描述

方法2：
不是val的值，尾插到新链表
在这里插入图片描述

例2：
在这里插入图片描述
方法：快慢指针
快指针一次走两步，慢指针一次走一步，快指针走到尾时，慢指针恰好在中间

例3：

方法1：
fast先走k-1步，然后slow和fast一起走，直到fast走到尾
方法2：
fast先走k步，然后slow和fast一起走，直到fast走到空
在这里插入图片描述

线性表

顺序表

链表

相关文章：