自学内容网 自学内容网
自学内容网 > 正文

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

🕗 发布于 2025-01-21 18:36 数据结构  链表  

线性表

线性表是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);

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;
}

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);
}
int main() {
TestSList2();
return 0;
}

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

方法1：

在这里插入图片描述

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

例2：
在这里插入图片描述
方法：快慢指针
快指针一次走两步，慢指针一次走一步，快指针走到尾时，慢指针恰好在中间
在这里插入图片描述
例3：
在这里插入图片描述
方法1：
fast先走k-1步，然后slow和fast一起走，直到fast走到尾
方法2：
fast先走k步，然后slow和fast一起走，直到fast走到空
在这里插入图片描述


原文地址：https://blog.csdn.net/2402_87467998/article/details/145205250

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

  • jvm学习总结

    在硬盘上查找并通过io读写字节码文件，使用类时才加载，例如调用来的main方法，new对象等等，在加载阶段会在内存中生成一个代表这个类的java.lang.Class对象，作为方法区这个类的各种数据的

    阅读更多2025-01-22
  • 【gopher的java学习笔记】Java中Mapper与Entity的关系详解

    在Java后端开发中，特别是在使用MyBatis等持久层框架时，Mapper与Entity的关系是架构设计中不可忽视的一部分。本文将从Java Web应用程序的角度出发，详细探讨Mapper与Enti

    阅读更多2025-01-22
  • 【gopher的java学习笔记】Java中Service与Mapper的关系详解

    在后端开发中，Java作为一种广泛使用的编程语言，其架构设计和层次划分对于系统的可维护性、可扩展性和性能有着至关重要的影响。特别是在使用MyBatis等持久层框架时，Service层与Mapper层的

    阅读更多2025-01-22
  • 基于单片机的直流电机控制系统（论文+源码）

    1系统方案设计本设计基于单片机的直流电机控制系统的总体架构设计如图2.1所示，其采用STM32F103单片机作为控制器，结合ESP8266WiFi通信模块、L9110电机驱动电路、OLED液晶、按键等

    阅读更多2025-01-22
  • 探索 Vue.js 的高级插槽特性：动态插槽与作用域插槽优化

    <thead><tr></th></tr></thead><tbody></td></tr></t

    阅读更多2025-01-22
  • HarmonyOS NEXT：华为分享-碰一碰开发分享

    碰一碰”是HarmonyOS NEXT系统中的一项创新功能，它允许用户通过简单的设备接触，实现多种内容的快速分享。这一功能打破了传统文件传输和分享的局限性，无需复杂的网络设置或社交关系，只需将两个设备

    阅读更多2025-01-22
  • 第17章 安全培训筑牢梦想根基

    在确认同事情况有所好转后，我们才回到考场，继续完成考试。王瑞瑞紧握着笔记本，点了点头，她的马尾辫随着动作轻轻摆动，但眼神却异常坚定：“是的，这让我们更加明白，我们的每一个小错误，都可能导致无法挽回的后

    阅读更多2025-01-22
  • C# 中的Stopwatch和timer

    Stopwatch：用于测量时间间隔，适合性能分析和精确计时。Timer：用于在指定的时间间隔后执行代码，适合定时任务。根据你的具体需求，可以选择使用Stopwatch来测量时间间隔，或使用Timer

    阅读更多2025-01-22
  • 学Python的人…

    它主要负责包管理比较臃肿，我也是后面学深度学习才开始用这个的不是必需，初学者可安可不安。提前思考好学习路线：思维导图中的基础部分所有的都要学，但高阶部分选定一个方向学就好。，它的交互性的确更强，但我觉

    阅读更多2025-01-22
  • Comment(爆破+git泄漏+二次注入)

    即用户名为admin%27%0Aor%0A%271%27%3E%270%27%0Aor%0Aname%0Alike%0A%27admin。使用bugscanteam的githack工具，下载泄漏的源码

    阅读更多2025-01-22
自学内容网
Copyright © 2015-2025