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

顺序表和链表

  • 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://xiahunao.cn/news/3249815.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

Ai先行者工具与其他品牌大比拼！

Ai先行者工具与其他品牌大比拼！

AI先行者工具凭借其独特的技术优势和创新能力&#xff0c;成为了行业的焦点。那么&#xff0c;它究竟有哪些过人之处呢&#xff1f; AI先行者工具在算法优化上做了大量的工作。通过深度学习和自然语言处理技术&#xff0c;它能够更准确地理解和回应用户的需求&#xff0c;提供…
阅读更多...
Haproy服务

Haproy服务

目录 一.haproxy介绍 1.主要特点和功能 2.haproxy 调度算法 3.haproxy 与nginx 和lvs的区别 二.安装 haproxy 服务 1. yum安装 2.第三方rpm 安装 3.编译安装haproxy 三.配置文件详解 1.官方地址配置文件官方帮助文档 2.HAProxy 的配置文件haproxy.cfg由两大部分组成&…
阅读更多...
linux中list的基本用法

linux中list的基本用法

内核链表 1 list_head 结构 为了使用链表机制&#xff0c;驱动程序需要包含<linux/types.h>头文件&#xff0c;该文件定义了如下结构体实现双向链&#xff1a; struct list_head {struct list_head *next, *prev; };2 链表的初始化 2.1 链表宏定义和初始化 可使用以…
阅读更多...
如何在Mac下修改VSCode侧边栏字体大小

如何在Mac下修改VSCode侧边栏字体大小

在日常使用VSCode&#xff08;Visual Studio Code&#xff09;进行开发时&#xff0c;我们有时需要对IDE&#xff08;集成开发环境&#xff09;的界面进行一些个性化的调整&#xff0c;以提升我们的开发体验。 比如&#xff0c;有些用户可能会觉得VSCode的侧边栏字体大小不符…
阅读更多...
JavaDS —— 二叉树

JavaDS —— 二叉树

树的基本概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看 起来像一棵倒挂的树&#xff0c;也就是说它是根朝上&#xff0c;而叶朝下的。 树形结构中&#xff0c;子树之间不能有…
阅读更多...
健康问题查询找搜索引擎还是大模型

健康问题查询找搜索引擎还是大模型

随着自然语言处理&#xff08;NLP&#xff09;的最新进展&#xff0c;大型语言模型&#xff08;LLMs&#xff09;已经成为众多信息获取任务中的主要参与者。然而&#xff0c;传统网络搜索引擎&#xff08;SEs&#xff09;在回答用户提交的查询中的作用远未被取代。例如&#xf…
阅读更多...
idea怎么配置gradle多个版本

idea怎么配置gradle多个版本

1.背景 gradle版本很多,而且很多时候版本是不兼容的,我们希望拉取下来的代码就包含已经配置好的版本,而不是去配置本机的gradle版本..... 意思就是要实现项目A可以用6.X版本 项目B可以使用7.X版本 项目C可以用9.X版本..... 2.配置方式 步骤一:项目根路径下保留一个文件夹…
阅读更多...
阿里云ACP云计算高级攻城狮通用知识

阿里云ACP云计算高级攻城狮通用知识

&#x1f525;概述 阿里云云计算高级工程师ACP认证是面向使用阿里云云计算产品的架构、开发、运维类人员的专业技术认证&#xff0c;主要考核考生利用阿里云云计算技术服务体系设计稳定、安全、高性能、易扩展、低成本的企业云计算架构的能力。 前提&#xff1a;在写适用人群…
阅读更多...
【ROS2】高级:从包文件读取 (C++)

【ROS2】高级:从包文件读取 (C++)

目标&#xff1a;在不使用 CLI 的情况下从包中读取数据。 教程级别&#xff1a;高级 时间&#xff1a;10 分钟 目录 背景 先决条件 任务 1 创建一个包裹2 编写 C 读取器3 构建并运行 摘要 背景 rosbag2 不仅提供 ros2 bag 命令行工具。它还提供了一个 C API&#xff0c;用于从您…
阅读更多...
基于JAVA+SpringBoot+uniapp的心理小程序(小程序版本)

基于JAVA+SpringBoot+uniapp的心理小程序(小程序版本)

✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、SpringCloud、Layui、Echarts图表、Nodejs、爬…
阅读更多...
5G mmWave PAAM 开发平台

5G mmWave PAAM 开发平台

Avnet-Fujikura-AMD 5G 毫米波相控阵天线模块开发平台 Avnet 和 Fujikura 为毫米波频段创建了一个领先的 5G FR2 相控阵天线开发平台。该平台使开发人员能够使用 AMD Xilinx 的 Zynq UltraScale™ RFSoC Gen3 和 Fujikura 的 FutureAcess™ 相控阵天线模块 (PAAM) 快速创建和制…
阅读更多...
上海理工大学24计算机考研考情分析！初复试分值比55：45，复试逆袭人数不算多！

上海理工大学24计算机考研考情分析！初复试分值比55：45，复试逆袭人数不算多！

上海理工大学&#xff08;University of Shanghai for Science and Technology&#xff09;&#xff0c;位于上海市&#xff0c;是一所以工学为主&#xff0c;工学、理学、经济学、管理学、文学、法学、艺术学等多学科协调发展的应用研究型大学&#xff1b;是上海市属重点建设大…
阅读更多...
Amisco供应汽车线圈与Husco是一家私营公司高性能液压和机电部件在汽车和非公路应用的组件设计和制造方面拥有超过 75 年的经验10于年的合作

Amisco供应汽车线圈与Husco是一家私营公司高性能液压和机电部件在汽车和非公路应用的组件设计和制造方面拥有超过 75 年的经验10于年的合作

Amisco和Husco在汽车线圈和高性能液压和机电部件的设计和制造方面合作已经超过10年。 Amisco是一家供应汽车线圈的公司&#xff0c;而Husco则专注于高性能液压和机电部件的设计和制造。 这两家公司在汽车和非公路应用领域拥有超过75年的经验。通过合作&#xff0c;Amisco和Husc…
阅读更多...
【开源 Mac 工具推荐之 2】洛雪音乐（lx-music-desktop）：免费良心的音乐平台

【开源 Mac 工具推荐之 2】洛雪音乐（lx-music-desktop）：免费良心的音乐平台

旧版文章&#xff1a;【macOS免费软件推荐】第6期&#xff1a;洛雪音乐 Note&#xff1a;本文在旧版文章的基础上&#xff0c;新更新展示了一些洛雪音乐的新功能&#xff0c;并且描述更为详细。 简介 洛雪音乐&#xff08;GitHub 名&#xff1a;lx-music-desktop &#xff09;…
阅读更多...
将iPad 作为Windows电脑副屏的几种方法（二）

将iPad 作为Windows电脑副屏的几种方法（二）

将iPad 作为Windows电脑副屏的几种方法&#xff08;二&#xff09; 1. 前言2. EV 扩展屏2.1 概述2.2 下载、安装、连接教程2.3 遇到的问题和解决方法2.3.1 平板连接不上电脑 3. Twomon SE3.1 概述3.2 下载安装教程 4. 多屏中心&#xff08;GlideX&#xff09;4.1 概述4.2 下载安…
阅读更多...
LeetCode 算法：单词搜索 c++

LeetCode 算法：单词搜索 c++

原题链接&#x1f517;&#xff1a;单词搜索 难度&#xff1a;中等⭐️⭐️ 题目 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 单词必须按照字母顺序&#xff0c;通…
阅读更多...
解决npm install（‘proxy‘ config is set properly. See: ‘npm help config‘）失败问题

解决npm install（‘proxy‘ config is set properly. See: ‘npm help config‘）失败问题

摘要 重装电脑系统后&#xff0c;使用npm install初始化项目依赖失败了&#xff0c;错误提示&#xff1a;‘proxy’ config is set properly…&#xff0c;具体的错误提示如下图所示&#xff1a; 解决方案 经过报错信息查询解决办法&#xff0c;最终找到了两个比较好的方案&a…
阅读更多...
vscode+wsl2+anaconda环境的配置与使用

vscode+wsl2+anaconda环境的配置与使用

目录 下载anaconda Anaconda使用参考 vscodeubuntuanaconda 先用vscode连接本地ubuntu。 如果没有安装wsl2与ubuntu&#xff0c;可点击下面的链接。 问题&#xff1a;wsl install 无法解析服务器 成功记录&#xff1a; 在vscode终端用ubuntu安装anaconda。 创建pytho…
阅读更多...
学习008-02-01 Define the Data Model and Set the Initial Data（定义数据模型并设置初始数据）

学习008-02-01 Define the Data Model and Set the Initial Data（定义数据模型并设置初始数据）

Define the Data Model and Set the Initial Data&#xff08;定义数据模型并设置初始数据&#xff09; This section explains how to design a business model (database) for an application built with Cross-Platform .NET App UI (XAF) and Entity Framework Core. 本节…
阅读更多...
Python简化命令行界面库之fire使用详解

Python简化命令行界面库之fire使用详解

概要 在开发命令行工具时，开发者通常需要编写大量代码来解析命令行参数，这既耗时又容易出错。Python Fire 是 Google 开源的一个库，旨在简化命令行界面的开发。它可以将任何 Python 对象自动生成一个命令行界面，从而大大减少了开发时间和代码复杂度。本文将详细介绍 Pytho…
阅读更多...
最新文章

Copyright @ 2022~2023