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

初阶数据结构的实现1 顺序表和链表

news 2025/7/16 23:46:43

顺序表和链表

  • 1.线性表
    • 1.1顺序表
      • 1.1.1静态顺序表（不去实现）
      • 1.1.2动态顺序表
        • 1.1.2.1 定义程序目标
        • 1.1.2.2 设计程序
        • 1.1.2.3编写代码
        • 1.1.2.3测试和调试代码
      • 1.1.2 顺序表的问题与思考
    • 1.2链表
      • 1.2.1链表的概念及结构
        • 1.2.1.1 定义程序目标
        • 1.2.1.2 设计程序
        • 1.2.1.3编写代码
        • 1.1.2.3测试和调试代码

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

相同特性
逻辑结构：人为想象出来的数据的组织形式
物理结构：数据在想象出来的数据的组织形式。

1.1顺序表

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

1.1.1静态顺序表（不去实现）

#define N 5
typedef int SLdatatype;
typedef struct SeqList {SLdatatype array [N];int size;
};

1.1.2动态顺序表

typedef int SLdatatype;
typedef struct SeqList {SLdatatype *arr;int capacity;//容量int size;//有效数据个数
}SL
1.1.2.1 定义程序目标
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef struct SeqList {SLDatatype *arr;int capacity;//容量int size;//有效数据个数
}SL;//初始化
void SLInitialize(SL*s);//销毁
void SLDestroy(SL*s );//打印顺序表
void SLPrint(SL* ps);//插入数据
//尾插
void SLPushBack(SL*s, SLDatatype x);//头插
void SLPushFront(SL*s, SLDatatype x);//尾删
void SLPopBack(SL* s);//头删
void SLPopFront(SL* s);//在指定位置插入数据
void SLInsert(SL* s, SLDatatype x, int pos);//在指定位置删除数据
void SLErase(SL* s,int pos);//查找数据
int SLFind(SL* s, SLDatatype x);
1.1.2.2 设计程序

面向程序员自身的，能实现包括顺序表的结构定义、初始化、插入、删除、查找、遍历、排序等操作

1.1.2.3编写代码
void SLInitialize(SL* ps)
{ps->arr = NULL;ps->capacity = ps->size = 0;
}void SLDestroy(SL* ps)
{if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->capacity = ps->size = 0;
}void SLCheckCapacity(SL* ps)
{//判断空间是否充足if (ps->size == ps->capacity){//增容//若capacity为0，给个默认值，否则×2倍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);}ps->arr = tmp;ps->capacity = NewCapacity;}
}void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}void SLPushBack(SL*ps, SLDatatype x)
{assert(ps);SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}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];}ps->arr[0] = x;ps->size++;
}void SLPopBack(SL* ps)
{assert(ps && ps->size);ps->size--;
}
void SLPopFront(SL* ps)
{assert(ps && ps->size);for (int i = 0; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}void SLInsert(SL* ps, SLDatatype x, int pos)
{assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);for (int i = ps->size; i >pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[ps->size] = x;ps->size++;}void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size&& ps->size);for (int i=pos; i < ps->size-1; i++){ps->arr[i] = ps->arr[i+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;
}
1.1.2.3测试和调试代码
#include"Seqlist.h"
void SLtest01()
{SL s;SLInitialize(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPushBack(&s, 6);/*SLPushBack(NULL , 6);*/SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPushFront(&s, 4);SLPrint(&s); //4 3 2 1SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLInsert(&s, 11, 0);SLPrint(&s);SLInsert(&s, 22, s.size);SLPrint(&s);SLInsert(&s, 33, 1);SLPrint(&s);SLDestroy(&s);
}int main()
{SLtest01();return 0;
}

在这里插入图片描述

1.1.2 顺序表的问题与思考

  1. 中间/头部的插入删除，时间复杂度为O(N)
  2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
  3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们
    再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
    思考：如何解决以上问题呢？下面给出了链表的结构来看看。

1.2链表

1.2.1链表的概念及结构

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

1.2.1.1 定义程序目标

实现

define _CRT_SECURE_NO_WARNINGS 1
#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*);
//申请新结点
SLTNode* SLTBuyNode(SLTDataType);
//尾插
void SLTPushBack(SLTNode**, SLTDataType);
//头插
void SLTPushFront(SLTNode** , SLTDataType );//删除//尾删
void SLTPopBack(SLTNode**);
//头删
void SLTPopFront(SLTNode**);//查找
SLTNode* SLTFind(SLTNode*, SLTDataType);//在指定位置之前插⼊数据
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);
1.2.1.2 设计程序

面向程序员自身的，能实现包括链表的结构定义、初始化、插入、删除、查找、遍历、排序等操作

1.2.1.3编写代码
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc fail");exit(1);}node->data = x;node->next = NULL;return node;
}void SLTPushBack(SLTNode**pphead, SLTDataType x)
{//申请新结点SLTNode*NewNode = SLTBuyNode(x);if (*pphead == NULL){*pphead = NewNode;}//尾结点->新结点//找尾结点else{SLTNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = NewNode;}
}void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//申请新结点SLTNode* NewNode = SLTBuyNode(x);//进行头插NewNode->next = *pphead;*pphead = NewNode;
}void SLTPopBack(SLTNode** pphead)
{//链表为空不可以删除assert(pphead && *pphead);//处理链表只有一个结点的情况if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找prev和ptailSLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}void SLTPopFront(SLTNode** pphead)
{//链表为空不可以删除assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = NULL;*pphead = next;
}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}else{pcur = pcur->next;}}return NULL;
}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (*pphead == pos)SLTPushBack(pphead, x);else{SLTNode* prev = *pphead;SLTNode* NewNode = SLTBuyNode(x);while (prev->next != pos){prev = prev->next;}prev->next = NewNode;NewNode->next = pos;}
}void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* NewNode = SLTBuyNode(x);NewNode->next = pos->next;pos->next = NewNode;
}void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead&&*pphead);assert(pos);if (*pphead = pos)SLTPopBack(pphead);else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}void SListDestroy(SLTNode** pphead)
{SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}
1.1.2.3测试和调试代码
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"void SListTest01()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);//1->2->3->4->NULLSLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist); //4->3->2->1->NULLSLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTNode* find = SLTFind(plist, 4);if (find == NULL){printf("未找到！\n");}else{printf("找到了！\n");}SLTInsert(&plist, plist, 11);//4->3->2->11->1->NULLSLTInsertAfter(plist, 11);SLTPrint(plist);1->11->2->3->4->NULLSLTErase(&plist, plist);// 1->2->3->NULLSLTEraseAfter(plist);SLTPrint(plist);SListDestroy(&plist);SLTPrint(plist);
}
int main()
{SListTest01();return 0;
}

在这里插入图片描述

http://www.lryc.cn/news/402459.html

相关文章：

  • 破解反爬虫策略 /_guard/auto.js（一） 原理
  • 40.简易频率计（基于等精度测量法）（3）
  • 关于Centos停更yum无法使用的解决方案
  • 插画感言：成都亚恒丰创教育科技有限公司
  • 【算法】数组中的第K个最大元素
  • Perl 语言的特点
  • NLP教程：1 词袋模型和TFIDF模型
  • 【开源 Mac 工具推荐之 2】洛雪音乐（lx-music-desktop）：免费良心的音乐平台
  • AMEYA360：思瑞浦推出汽车级理想二极管ORing控制器TPS65R01Q
  • 简约的悬浮动态特效404单页源HTML码
  • Golang 创建 Excel 文件
  • 探索GitHub上的两个革命性开源项目
  • SpringBoot框架学习笔记（三）：Lombok 和 Spring Initailizr
  • 【ASP.NET网站传值问题】“object”不包含“GetEnumerator”的公共定义，因此 foreach 语句不能作用于“object”类型的变量等
  • Stateflow中的状态转换表
  • 结合Redis解决接口幂等性问题
  • 2024算力基础设施安全架构设计与思考（免费下载）
  • ExoPlayer架构详解与源码分析（15）——Renderer
  • 网络安全-等级保护制度介绍
  • 【介绍下大数据组件之Storm】
  • React Hook 总结（React 萌新升级打怪中...）
  • Typora 1.5.8 版本安装下载教程 (轻量级 Markdown 编辑器)，图文步骤详解，免费领取
  • mac docker no space left on device
  • 单片机主控的基本电路
  • 【19】读感 - 架构整洁之道(一)
  • 多层全连接神经网络（三）---分类问题
  • 签名优化：请求数据类型不是`application/json`,将只对随机数进行签名计算，例如文件上传接口。
  • PostgreSQL的Json数据类型如何使用
  • SpringData JPA Mongodb 查询部分字段
  • NC65 设置下拉列表框值