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

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

🕗 发布于 2024-07-23 01:36 数据结构  链表  

顺序表和链表

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 1

SLPopBack(&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和ptail
SLTNode* 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->NULL

SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist); //4->3->2->1->NULL

SLTPopBack(&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->NULL
SLTInsertAfter(plist, 11);
SLTPrint(plist);1->11->2->3->4->NULL

SLTErase(&plist, plist);// 1->2->3->NULL
SLTEraseAfter(plist);

SLTPrint(plist);
SListDestroy(&plist);
SLTPrint(plist);
}
int main()
{
SListTest01();
return 0;
}

在这里插入图片描述


原文地址：https://blog.csdn.net/Yusei_0523/article/details/140505351

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

相关文章

  • VirtualBox 网络设置

    VirtualBox 提供了多种网络设置方式，每种方式都有其特定的应用场景和优缺点。在选择网络设置方式时，需要根据实际需求进行综合考虑。如果需要虚拟机像独立的物理计算机一样与外部网络中的其他设备进行通

    阅读更多2024-09-19
  • 什么是 SSL 代理？

    SSL 的作用是保证您的数据在您的设备和互联网之间传输时的安全。当您访问安全网站时，您的连接会使用 SSL 加密，因此您共享的任何数据都是加密的，不会被窥探。SSL 代理不仅会加密您的通信数据，还会修

    阅读更多2024-09-19
  • 【分立元件】案例：新人加了个TVS管为什么可能导致系统不能正常工作

    TVS是一种限压型的过压保护器，它将过高的电压钳制至一个安全范围，藉以保护后面的电路，有着比其它保护元件更快的反应时间，这使TVS可用在防护lighting、switching、ESD等快速破坏性瞬态

    阅读更多2024-09-19
  • python 绘制 y=x^3 图像

    Matplotlib 是Python中一个绘图库，支持跨平台运行，可以生成出版级别的图形，能够输出的图形包含折线图，散点图，曲线图，直方图，饼状图，条形图以及坐标图，其强大的绘画能力能够使得用户对数据

    阅读更多2024-09-19
  • 记忆化搜索

    记忆化搜索 OJ题

    阅读更多2024-09-19
  • 朴素贝叶斯 (Naive Bayes)

    朴素贝叶斯算法尽管假设特征独立，但在许多实际应用中表现良好。其简洁、有效的特性在文本分类、垃圾邮件过滤和推荐系统等多个领域中得到广泛应用。

    阅读更多2024-09-19
  • 【强化学习系列】Gym库使用——创建自己的强化学习环境2：拆解官方标准模型源码/规范自定义类+打包自定义环境

    本文记录在创建自定义gym环境中的报错与规范化问题，帮助后续矢量化环境创建

    阅读更多2024-09-19
  • supermap iclient3d for cesium中entity使用

    目标将西南石油大学部分区域围起来，然后引个标签显示名称，最后弄个飞机绕学校飞（这个时间有点晚了，明天弄)飞机的位置也要在写在外面，会和标签重合，所以重新创建一个对象,然后就是加载一个飞机，文档里面说了

    阅读更多2024-09-19
  • vim的 配置文件

    个人的配置文件是隐藏的，不进行配置的话一般是没有这个文件的，需要自己创建。，共有两个，一个是公共的、所有用户的。vim 的配置文件名是。，一个是私有的、个人的。私有的配置文件位于**

    阅读更多2024-09-19
  • 阿里1688一面总结

    发布-订阅模式，即当实验发生变更时，就发出一个变更事件，然后，每台机器感知到这个变更事件后，清空本地缓存，触发reload操作。为了避免大量请求打到DB，可以对查询请求进行加锁，保证相同的实验只有一个

    阅读更多2024-09-19
自学内容网
Copyright © 2015-2024