首页 > 其他分享 >【数据结构】（2）顺序表和链表

【数据结构】（2）顺序表和链表

时间：2022-11-26 19:01:16浏览次数：55  
标签：ps 顺序 int void sl 链表 SListNode SL 数据结构

（1）线性表

数据结构实际两种结构

1.物理结构（内存中如何储存）

2.逻辑结构（是我们想像出来的）


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

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的（在内存里储存不一定连续），线性表在物理上存储时，通常以数组和链式结构的形式存储。

线性表：

数组（物理和逻辑上都是连续的）【可能会存在浪费】

链表；（物理上不一定是线性的，）按需申请内存】


（2）顺序表

1.概念及结构

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

顺序表一般可以分为：

  1. 静态顺序表：使用定长数组存储。
  2. 动态顺序表：使用动态开辟的数组存储。

案例

先定义一个头文件

struct SeqList
{
  int a[10];
  int size;
};

void SeqListPushBack(struct SeqList* pa, int x);
void SeqListPushBack(struct SeqList* pa, int x);
void SeqListPushBack(struct SeqList* pa, int x);

我们发现，在之后如果想要改变数组a的类型，就需要所有都改变，不方便。

所以我们使用typedef

并且用宏去定义只能是变量

typedef int SLDataType;
#define N 10;

struct SeqList
{
  SLDataType a[N];//定长数组
  int size;//有效数据个数
};

void SeqListPushBack(struct SeqList* ps, SLDataType x);
void SeqListPopBack(struct SeqList* ps );
void SeqListPushFront(struct SeqList* ps, SLDataType x);
void SeqListPopFront(struct SeqList* ps);

这个数据表我们称为静态顺序表设计（固定大小）

那我们怎么开辟动态的呢，方法如下

typedef int SLDataType;

struct SeqList
{
  SLDataType *a;//执行开辟的数组
  int size;//有效数据
  int capacity;//容量空间的大小
};

void SeqListPushBack(struct SeqList* ps, SLDataType x);//尾插尾删
void SeqListPopBack(struct SeqList* ps );
                    
void SeqListPushFront(struct SeqList* ps, SLDataType x);//头插头删
void SeqListPopFront(struct SeqList* ps);
                    
void SeqListInsert(struct Seqlist*ps,int pos,SLDataType x);//任意位置的插入删除
void SeqListErase(struct Seqlist*ps,int pos);

优化一下

typedef int SLDataType;

typedef struct SeqList
{
  SLDataType *a;//执行开辟的数组
  int size;//有效数据
  int capacity;//容量空间的大小
}SL，SeqList;

void SeqListPushBack(SL* ps, SLDataType x);//尾插尾删
void SeqListPopBack(SL* ps );
                    
void SeqListPushFront(SL* ps, SLDataType x);//头插头删
void SeqListPopFront(SL* ps);
                    
void SeqListInsert(SL*ps,int pos,SLDataType x);//任意位置的插入删除
void SeqListErase(SL*ps,int pos);

2.接口实现：

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

这里我们放上完整的码，大家可以研究一下

test.c

#include "Seqlist.h"

void TestSeqList1()
{
  SL sl;
  SeqListInit(&sl);
  SeqListPushBack(&sl, 1);
  SeqListPushBack(&sl, 2);
  SeqListPushBack(&sl, 3);
  SeqListPushBack(&sl, 4);
  SeqListPushBack(&sl, 5);
  SeqListPrint(&sl);

  SeqListPopBack(&sl);
  SeqListPopBack(&sl);
  SeqListPopBack(&sl);
  SeqListPopBack(&sl);
  SeqListPopBack(&sl);
  //SeqListPopBack(&sl);
  //SeqListPopBack(&sl);
  SeqListPrint(&sl);

  SeqListPushBack(&sl, 10);
  SeqListPushBack(&sl, 20);
  SeqListPrint(&sl);

  SeqListDestory(&sl);
}

void TestSeqList2()
{
  SL sl;
  SeqListInit(&sl);
  SeqListPushBack(&sl, 1);
  SeqListPushBack(&sl, 2);
  SeqListPushBack(&sl, 3);
  SeqListPushBack(&sl, 4);
  SeqListPushBack(&sl, 5);
  SeqListPrint(&sl);

  SeqListPushFront(&sl, 10);
  SeqListPushFront(&sl, 20);
  SeqListPushFront(&sl, 30);
  SeqListPushFront(&sl, 40);
  SeqListPrint(&sl);

  SeqListPopFront(&sl);
  SeqListPopFront(&sl);
  SeqListPrint(&sl);

  SeqListDestory(&sl);
}

void TestSeqList3()
{
  SL s;
  int pos = SeqListFind(&s, 5);
  if (pos != -1)
  {
    SeqListErase(&s, pos);
  }
}

// 写一个类似通讯录的菜单
void menu()
{
  printf("************************************\n");
  printf("请选择你的操作:>\n");
  printf("1、头插  2、头删\n");
  printf("3、尾插  4、尾删\n");
  // ...
  printf("************************************\n");
}

int main()
{
  TestSeqList1();
  TestSeqList2();
  TestSeqList3();
  return 0;
}

Seqlist.c

#define _CRT_SECURE_NO_WARNINGS 
#include "Seqlist.h"
/*==================================================*/
void SeqListPrint(SL* ps)//打印
{
  for (int i = 0; i < ps->size; ++i)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}
/*==================================================*/
void SeqListInit(SL* ps)//初始化
{
  ps->a = NULL;
  ps->size = ps->capacity = 0;
}
/*==================================================*/
void SeqListDestory(SL* ps)//释放
{
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->size = 0;
}
/*==================================================*/
void SeqListCheckCapacity(SL* ps)//扩容
{
  // 如果没有空间或者空间不足，那么我们就扩容
  if (ps->size == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//每次乘2，适合
    SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }

    ps->a = tmp;
    ps->capacity = newcapacity;
  }
}
/*==================================================*/
void SeqListPushBack(SL* ps, SLDataType x)//尾插
{
  SeqListCheckCapacity(ps);

  ps->a[ps->size] = x;
  ps->size++;
}
/*==================================================*/
void SeqListPopBack(SL* ps)//尾删
{
  // 温柔处理方式
  //if (ps->size > 0)
  //{
  //  //ps->a[ps->size - 1] = 0;
  //  ps->size--;
  //}

  // 暴力处理方式
  assert(ps->size > 0);
  ps->size--;
}
/*==================================================*/
void SeqListPushFront(SL* ps, SLDataType x)//头插
{
  SeqListCheckCapacity(ps);

  // 挪动数据
  int end = ps->size - 1;
  while (end >= 0)
  {
    ps->a[end + 1] = ps->a[end];
    --end;
  }
  ps->a[0] = x;
  ps->size++;
}
/*==================================================*/
void SeqListPopFront(SL* ps)//头删
{
  assert(ps->size > 0);

  // 挪动数据
  int begin = 1;
  while (begin < ps->size)
  {
    ps->a[begin - 1] = ps->a[begin];
    ++begin;
  }
  ps->size--;
}
/*==================================================*/
void SeqListInsert(SL* ps, int pos, SLDataType x)//任意位置增加
{
  assert(ps);
  assert(pos <= ps->size && pos >= 0);
  SeqListCheckCapacity(ps);

  int end = ps->size - 1;
  while (end >= pos)
  {
    ps->a[end + 1] = ps->a[end];
    --end;
  }
  ps->a[pos] = x;
  ps->size++;
}
/*==================================================*/
void SeqListErase(SL* ps, int pos)//任意位置删除
{
  assert(ps);
  assert(pos < ps->size&& pos >= 0);

  int start = pos;
  while (start < ps->size - 1)
  {
    ps->a[start] = ps->a[start + 1];
    ++start;
  }
  ps->size--;
}
/*==================================================*/
int SeqListFind(SL* ps, SLDataType x)//找位置
{
  assert(ps);
  int i = 0;
  while (i < ps->size)
  {
    if (ps->a[i] == x);
    {
      return i;
    }
    ++i;
  }
  return -1;
}
/*==================================================*/

Seqlist.h

#pragma once
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//#define N 10000
//typedef int SLDataType;
//
//// 静态顺序表
//typedef struct SeqList
//{
//  SLDataType a[N];
//  int size; // 表示数组中存储了多少个数据
//}SL;
//
//// 接口函数 -- 命名风格是跟着STL走的，方便后续学习STL
//void SeqListInit(SL* ps); 
//
//// 静态特点：如果满了就不让插入  缺点：给多少的合适呢？这个很难确定
//// N给小了不够用，N给大了浪费
//void SeqListPushBack(SL* ps, SLDataType x);
//void SeqListPopBack(SL* ps);
//void SeqListPushFront(SL* ps, SLDataType x);
//void SeqListPopFront(SL* ps);
//// ...

typedef int SLDataType;

// 动态顺序表
typedef struct SeqList
{
  SLDataType* a;
  int size;      // 表示数组中存储了多少个数据
  int capacity;  // 数组实际能存数据的空间容量是多大 
}SL;


// 接口函数 -- 命名风格是跟着STL走的，方便后续学习STL
void SeqListPrint(SL* ps);
void SeqListInit(SL* ps);
void SeqListDestory(SL* ps);

void SeqListCheckCapacity(SL* ps);
void SeqListPushBack(SL* ps, SLDataType x);
void SeqListPopBack(SL* ps);
void SeqListPushFront(SL* ps, SLDataType x);
void SeqListPopFront(SL* ps);
// ...

// 找到了返回x位置下标，没有找打返回-1
int SeqListFind(SL* ps, SLDataType x);
// 指定pos下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
// 删除pos位置的数据
void SeqListErase(SL* ps, int pos);

3.优缺点

1.可动态增长的数组

2.数据在数组中储存时必须是连续的

缺点：

1.中间或头部的插入删除很慢，需要挪动数据，时间复杂度是O（N）

2.空间不够时，扩容会有一定消耗和浪费

优点：

1.随机访问

2.缓存利用率比较高


（3）链表

1.链表的概念及结构

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

现实中：

【数据结构】（2）顺序表和链表_数据

数据结构中：

【数据结构】（2）顺序表和链表_数组_02

这样的链式结构易于增减

2.种类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向、双向

2. 带头、不带头

3. 循环、非循环

其中常用的是

【数据结构】（2）顺序表和链表_顺序表_03

3.例子

这里我们以单向链表为例，直接来一个码，大家拷贝后研究

特别注意源程序命名

SList.c

#define _CRT_SECURE_NO_WARNINGS 
#include"SList.h"
/*=================================================*/
SListNode* BuySListNode(SListDataType x)
{
  SListNode* newNode = (SListNode*)malloc(sizeof//建立新结点
  (SListNode));
  if (newNode == NULL)
  {
    printf("申请结点失败\n");
    exit(-1);
  }
  newNode->data = x;
  newNode->next = NULL;
  return newNode;
}
/*=================================================*/
void SListPrint(SListNode* phead)//遍历打印列表
{
  SListNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next; 
  }
    printf("NULL\n");
}
/*=================================================*/
void SListPushBack(SListNode** pphead, SListDataType x)//尾插
{
  assert(pphead);
  SListNode* newNode = BuySListNode(x);
  if (*pphead == NULL)
  {
    *pphead = newNode;
  }
  else
  {
    SListNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newNode;//将新的结点连在后面
  }
}
/*=================================================*/
void SListPopBack(SListNode** pphead)
{
  //1.空
  //2.一个
  //3.一个结点以上
  if (*pphead == NULL)
  {
    return;
  }
  else if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    //小心野指针
    SListNode* tail = *pphead;
    SListNode* prev = NULL;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    prev->next = NULL;
  }
}
/*=================================================*/
void SListPushFront(SListNode** pphead, SListDataType x)
{
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
/*=================================================*/
void SListPopFront(SListNode** pphead)
{
  if (*pphead == NULL)
  {
    return;
  }
  else 
  {
    SListNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
  }
}
/*=================================================*/
SListNode* SListFind(SListNode* phead, SListDataType x)
{
  SListNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
/*=================================================*/
void SListInsertAfter(SListNode* pos, SListDataType x)//与find连用
{
  assert(pos);
  SListNode* newnode = BuySListNode(x);
  //一定注意以下顺序
  newnode->next = pos->next;
  pos->next = newnode;
}
/*=================================================*/
void SListEraseAfter(SListNode* pos)
{
  assert(pos->next);
  if (pos->next)
  {
    SListNode* next = pos->next;
    SListNode* nextnext = next->next;
    pos->next = nextnext;
    free(next);
  }
}
/*=================================================*/
void SListDestory(SListNode** pphead)
{
  assert(pphead);
  SListNode* cur = *pphead;
  while (cur)//释放所有
  {
    SListNode* next = cur->next;
    free(cur);
    cur = next;
  }
}
/*=================================================*/

SList.h

#pragma once
#include<Stdio.h>
#include<malloc.h>
#include<assert.h>

typedef int SListDataType;
//结点
typedef struct SListNode
{
  SListDataType data;
  struct SListNode* next;
}SListNode;

SListNode* BuySListNode(SListDataType x);

void SListPushBack(SListNode** pphead,SListDataType x);
void SListPopBack(SListNode** pphead);

void SListPushFront(SListNode** pphead, SListDataType x);
void SListPopFront(SListNode** pphead);

void SListPrint(SListNode* phead);
void SListSize(SListNode* phead);

SListNode*SListFind(SListNode*plist, SListDataType x);//单链表查找
void SListInsertAfter(SListNode* pos, SListDataType x);//随意插入
void SListEraseAfter(SListNode* pos);//删除

void SListDestory(SListNode** pphead);

test.h

#define _CRT_SECURE_NO_WARNINGS 
#include"SList.h"

int main()
{
  SListNode* pList = NULL;
  SListPushBack(&pList, 1);
  SListPushBack(&pList, 2);
  SListPushBack(&pList, 3);
  SListPushBack(&pList, 4);
  SListPrint(pList);

  SListPopBack(&pList);
  SListPopBack(&pList);
  SListPopBack(&pList);
  SListPopBack(&pList);
  SListPopBack(&pList);
  SListPrint(pList);

  SListPushFront(&pList,1);
  SListPushFront(&pList,2);
  SListPushFront(&pList,3);
  SListPushFront(&pList,4);
  SListPushFront(&pList,5);
  SListPrint(pList);

  SListPopFront(&pList);
  SListPopFront(&pList);
  SListPopFront(&pList);
  SListPopFront(&pList);
  SListPopFront(&pList);
  SListPrint(pList);

  return 0;
}

（4）顺序表和链表的区别和联系

​顺序表：一白遮百丑

白：空间连续、支持随机访问

丑：中间或前面部分的插入删除时间复杂度O(N) 2.增容的代价比较大。

​链表：一(黑)毁所有

黑：以节点为单位存储，不支持随机访问

所有：任意位置插入删除时间复杂度为O(1) 2.没有增容问题，插入一个开辟一个空间。



















标签：ps,顺序,int,void,sl,链表,SListNode,SL,数据结构
From： https://blog.51cto.com/u_15796276/5889129

相关文章

  • go专家编程--数据结构chan
    chan结构typehchanstruct{ qcount uint//队列中剩余元素大小 dataqsiz uint//队列大小 buf unsafe.Pointer//环......
  • 数据结构实验（五）二叉树
    6-1二叉树的遍历就是简单的遍历voidInorderTraversal(BinTreeBT){if(BT==NULL)return;if(BT->Left!=NULL)InorderTraversal(BT->Left);......
  • .NET|--Winform|--DotnetBar库的Button显示顺序设置
    前言winform真的要注意细节啊.细节拉满才能把握得住的一个框架.需求实现一个动态添加按钮,但是要根据按钮来排序.解决方案usingDevComponents.DotNetBar;namespa......
  • jmeter并发测试如何保证多线程多请求按照顺序执行【杭州多测师】【杭州多测师_王sir】
    1、没有处理线程执行顺序时，多个线程里的请求是一起执行的，不分先后。（未勾选独立线程运行结果）2、在测试计划里勾选独立运行每个线程组。（测试计划处勾选独立运行每个线程组）3、......
  • leetcode 24. 两两交换链表中的节点 js实现
    给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。示例1：输入：head=[1,2,3,4]输出：[2,......
  • 算法6：LeetCode_合并两个有序链表
    题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 输入：l1=[1,2,4],l2=[1,3,4]   输出：[1,1,2,3,4,4]......
  • 寻找链表相交结点问题
    寻找链表相交结点问题作者：Grey原文地址：博客园：寻找链表相交结点问题CSDN：寻找链表相交结点问题题目描述给定两个可能有环也可能无环的单链表，头节点head1和head2。请实......
  • sort自然排序顺序
    1、问题：fs读取文件夹文件的时候，有时顺序是乱的   而实际想要的顺序是这样的2、思路：主要通过js的数组中的sort方法来处理利用replace正则区分数字与非数字来遍历......
  • [数据结构] 树哈希（待补）
    树哈希参考：​​树哈希（TreeHash）​​​哔哩哔哩koko​​无权树哈希函数设计设hs[x]表示以x为根的子树的哈希值其中y是x的儿子，是以y为根的子树的大小，prime[i]是第i个质数其实......
  • 【数据结构】树的遍历
    【数据结构】树的遍历​​题目链接​​思路如果树节点都不一样，那么我们可用通过树的中序遍历和后序遍历确定一棵树。我们通过哈希表来存左儿子和右儿子`l[root]=r[root]=构......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99