首页 > 其他分享 >day03（数据结构）顺序表

day03（数据结构）顺序表

时间：2024-08-19 22:25:43浏览次数：12  
标签：顺序 last day03 seqlist int post 数据结构 data

线性表

线性表是最基本、最简单、也是最常用的一种数据结构，可以存储逻辑关系为线性的数据。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

包含：顺序表(数组)、链表(单向链表、单向循环链表、双向链表、双向循环链表)、栈(顺序栈、链式栈)、队列(循环队列、链式队列)逻辑结构：线性结构

存储结构：顺序存储(数组)或链式存储(通过指针)

特点：一对一，每个节点最多一个前驱和一个后继，首节点无前驱，尾节点无后继。

 顺序表

顺序表存储数据的具体实现方案是：将数据全部存储到一整块内存空间中，数据元素之间按照次序挨个存放。

举个简单的例子，将 {1,2,3,4,5} 这些数据使用顺序表存储，数据最终的存储状态如下图所示：

1.顺序表的特性

逻辑结构：线性结构

存储结构：顺序存储结构

特点：内存连续

操作：增删改查

2. 操作数组

例题：

int a[100]={1,2,3,4,5,6,7,8};

函数命名规则：

下划线法：create_empty_seqlist

小驼峰法：createEmptySeqList

大驼峰法：CreateEmptySeqList

数组的增删操作：
#include <stdio.h>

/*  
    功能：向数组的第几个位置插数据
    函数：void insetIntoA(int *p,int n, int post, int data);
    参数：
    int *p: 保存数组首地址
    int n: 有效数据元素的个数
    int post: 插入元素下标
    int data: 数据
*/
void insertIntoA(int *p, int n, int post, int data) //insert插入  //p=a, n=8,post=4, data=100
{
    int i;
    //1.从最后一个元素到插入位置的元素向后移动一个单位
    for (i = n - 1; i >= post; i--) //i=7 , 7>=4;    i=6, 6>=4; i=5, 5>=4;  i=4, 4>=4;  i=3 3>=4(不满足退出循环)
        p[i + 1] = p[i];            //p[8]=p[7];   p[7]=[6];   p[6]=p[5];  p[5]=p[4]

    //2.插入新元素data到指定位置
    p[post] = data; //p[4] = 100
}

/* （2）遍历数组中的有效元素
    功能：遍历数组中的有效元素
    函数：void showA(int *p,int n);
    参数：
    int *p:保存数组收地址
    int n:有效数据元素的个数
*/
void showA(int *p, int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", p[i]);
    printf("\n");
}

/* （3）删除数组元素
    功能：删除数组中指定元素 
    函数：void deleteIntoA(int *p,int n, int post);
    参数：
    int *p: 保存数组首地址
    int n: 有效数据元素的个数
    int post: 删除元素下标
*/
void deleteIntoA(int *p, int n, int post) //delet删除  //p=a, n=9, post=4
{
    int i;
    //从删除位置元素的后一个元素到最后一个元素向前移动一个单位
    for (i = post + 1; i < n; i++) //i = 5, i<9; i=6,6<9; i=7,i<9; i=8; i=9(出循环)
        p[i - 1] = p[i];           //p[4]=p[5]; p[5]=p[6];  p[6]=p[7]; p[7]=p[8];
}

int main()
{
    int a[100] = {1, 2, 3, 4, 5, 6, 7, 8};
    insertIntoA(a, 8, 4, 100);
    showA(a, 9);
    deleteIntoA(a, 9, 4);
    showA(a, 8);
}
通过添加全局变量last表示最后一个有效元素的下标：
#include <stdio.h>
int last = 7; //代表最后一个有效元素下标 last = 有效元素个数-1

/*  
    功能：向数组的第几个位置插数据
    函数：void insetIntoA(int *p,int post, int data);
    参数：
    int *p: 保存数组首地址
    int post: 插入元素下标
    int data: 数据
*/
void insertIntoA(int *p, int post, int data) //insert插入
{
    int i;
    //1.从最后一个元素到插入位置的元素向后移动一个单位
    for (i = last; i >= post; i--)
        p[i + 1] = p[i];

    //2.插入新元素data到指定位置
    p[post] = data; //p[4] = 100

    //3. 让last加一，因为插入一个元素，有效元素多了一个
    last++;
}

/* （2）遍历数组中的有效元素
    功能：遍历数组中的有效元素
    函数：void showA(int *p);
    参数：
    int *p:保存数组收地址
*/
void showA(int *p)
{
    for (int i = 0; i <= last; i++)
        printf("%d ", p[i]);
    printf("\n");
}

/* （3）删除数组元素
    功能：删除数组中指定元素 
    函数：void deleteIntoA(int *p, int post);
    参数：
    int *p: 保存数组首地址
    int post: 删除元素下标
*/
void deleteIntoA(int *p, int post) //delet删除
{
    int i;
    //从删除位置元素的后一个元素到最后一个元素向前移动一个单位
    for (i = post + 1; i <= last; i++)
        p[i - 1] = p[i];

    //让last减一，因为删除了一个元素有效元素少了一个
    last--;
}

int main()
{
    int a[100] = {1, 2, 3, 4, 5, 6, 7, 8};
    insertIntoA(a, 4, 100);
    showA(a);
    deleteIntoA(a, 4);
    showA(a);
}

3. 顺序表编程实现

封装结构体:
#define N 10
typedef struct seqlist //封装顺序表结构体类型
{
    int data[N]; //用来存数据的数组
    int last;    //代表数组中最后一个有效元素的下标
} seqlist_t, *seqlist_p;
//seqlist_t A;  // 等同于struct seqlist A
//seqlist_p p;   //等同于 struct seqlist *p;

创建空顺序表：

#include <stdio.h>
#include <stdlib.h>
#define N 10
typedef struct seqlist //封装顺序表结构体类型
{
    int data[N]; //用来存数据的数组
    int last;    //代表数组中最后一个有效元素的下标
} seqlist_t, *seqlist_p;

// 创建一个空的顺序表
seqlist_p CreateEpSeqlist() //create创造 empty 空的 seqlist顺序表
{
    //动态申请一块顺序表结构体大小空间
    seqlist_p p = (seqlist_p)malloc(sizeof(seqlist_t));
    if (NULL == p)
    {
        perror("malloc lost"); //perror打印上一个函数报的错误信息
        return NULL;           //错误情况让函数返回空指针
    }
    //对结构体初始化
    p->last = -1;

    return p;
}

//判断顺序表是否为满，满返回1,未满返回0
int IsFullSeqlist(seqlist_p p) //full满
{
    return p->last + 1 == N;
}

//向顺序表的指定位置插入数据
int InsertIntoSeqlist(seqlist_p p, int post, int data)
{
    //容错判断：判满，对post做判断
    if (IsFullSeqlist(p) || post < 0 || post > p->last + 1)
    {
        printf("InsertIntoSeqlist err\n");
        return -1; //错误返回
    }
    //让最后一个元素到插入位置的元素向后移动一个单位
    for (int i = p->last; i >= post; i--)
        p->data[i + 1] = p->data[i];
    //插入数据
    p->data[post] = data;
    //让last加一
    p->last++;
    return 0;
}

//遍历顺序表sequence顺序list表
void ShowSeqlist(seqlist_p p)
{
    for (int i = 0; i <= p->last; i++)
        printf("%d ", p->data[i]);
    printf("\n");
}

//判断顺序表是否为空，为空返回1，不为空返回0
int IsEpSeqlist(seqlist_p p)
{
    return p->last == -1;
}

//删除顺序表中指定位置的数据，post为删除位置
int DeleteIntoSeqlist(seqlist_p p, int post)
{
    //容错判断：判空，对post判断
    if (IsEpSeqlist(p) || post < 0 || post > p->last)
    {
        printf("DeleteIntoSeqlist err\n");
        return -1;
    }

    //从删除位置元素的后一个元素到最后一个元素向前移动一个单位
    for (int i = post + 1; i <= p->last; i++)
        p->data[i - 1] = p->data[i];

    //让last减一，因为删除了一个元素有效元素少了一个
    p->last--;

    return 0;
}

// 修改指定位置上数据
int ChangePostSeqList(seqlist_p p, int post, int data)
{
    //容错判断：判空，对post判断
    if (IsEpSeqlist(p) || post < 0 || post > p->last)
    {
        printf("ChangePostSeqList err\n");
        return -1;
    }

    //修改指定位置数据
    p->data[post] = data;

    return 0;
}

// 查找指定数据出现的位置,返回下标，未找到返回-1
int SearchDataSeqList(seqlist_p p, int data)
{
    for (int i = 0; i <= p->last; i++)
    {
        if (p->data[i] == data)
            return i;
    }
    return -1;
}

// 清空顺序表（清空：访问不到，但是内存中还有。销毁：内存清空）
void ClearSeqList(seqlist_p p)
{
    p->last = -1;
}

int main(int argc, char const *argv[])
{
    seqlist_p p = CreateEpSeqlist();
    InsertIntoSeqlist(p, 0, 10);
    InsertIntoSeqlist(p, 1, 20);
    InsertIntoSeqlist(p, 2, 30);
    ShowSeqlist(p);

    DeleteIntoSeqlist(p, 1);
    ShowSeqlist(p);

    ChangePostSeqList(p, 0, 99);
    ShowSeqlist(p);

    printf("search 99:%d\n", SearchDataSeqList(p, 99));
    return 0;
}
分文件编程实现：
main.c
#include <stdio.h>
#include <stdlib.h>
#include "seqlist.h"

int main(int argc, char const *argv[])
{
    seqlist_p p = CreateEpSeqlist();
    InsertIntoSeqlist(p, 0, 10);
    InsertIntoSeqlist(p, 1, 20);
    InsertIntoSeqlist(p, 2, 30);
    ShowSeqlist(p);

    DeleteIntoSeqlist(p, 1);
    ShowSeqlist(p);

    ChangePostSeqList(p, 0, 99);
    ShowSeqlist(p);

    printf("search 99:%d\n", SearchDataSeqList(p, 99));
    return 0;
}

seqlist.c
#include <stdio.h>
#include <stdlib.h>
#include "seqlist.h"

// 创建一个空的顺序表
seqlist_p CreateEpSeqlist() //create创造 empty 空的 seqlist顺序表
{
    //动态申请一块顺序表结构体大小空间
    seqlist_p p = (seqlist_p)malloc(sizeof(seqlist_t));
    if (NULL == p)
    {
        perror("malloc lost"); //perror打印上一个函数报的错误信息
        return NULL;           //错误情况让函数返回空指针
    }
    //对结构体初始化
    p->last = -1;

    return p;
}

//判断顺序表是否为满，满返回1,未满返回0
int IsFullSeqlist(seqlist_p p) //full满
{
    return p->last + 1 == N;
}

//向顺序表的指定位置插入数据
int InsertIntoSeqlist(seqlist_p p, int post, int data)
{
    //容错判断：判满，对post做判断
    if (IsFullSeqlist(p) || post < 0 || post > p->last + 1)
    {
        printf("InsertIntoSeqlist err\n");
        return -1; //错误返回
    }
    //让最后一个元素到插入位置的元素向后移动一个单位
    for (int i = p->last; i >= post; i--)
        p->data[i + 1] = p->data[i];
    //插入数据
    p->data[post] = data;
    //让last加一
    p->last++;
    return 0;
}

//遍历顺序表sequence顺序list表
void ShowSeqlist(seqlist_p p)
{
    for (int i = 0; i <= p->last; i++)
        printf("%d ", p->data[i]);
    printf("\n");
}

//判断顺序表是否为空，为空返回1，不为空返回0
int IsEpSeqlist(seqlist_p p)
{
    return p->last == -1;
}

//删除顺序表中指定位置的数据，post为删除位置
int DeleteIntoSeqlist(seqlist_p p, int post)
{
    //容错判断：判空，对post判断
    if (IsEpSeqlist(p) || post < 0 || post > p->last)
    {
        printf("DeleteIntoSeqlist err\n");
        return -1;
    }

    //从删除位置元素的后一个元素到最后一个元素向前移动一个单位
    for (int i = post + 1; i <= p->last; i++)
        p->data[i - 1] = p->data[i];

    //让last减一，因为删除了一个元素有效元素少了一个
    p->last--;

    return 0;
}

// 修改指定位置上数据
int ChangePostSeqList(seqlist_p p, int post, int data)
{
    //容错判断：判空，对post判断
    if (IsEpSeqlist(p) || post < 0 || post > p->last)
    {
        printf("ChangePostSeqList err\n");
        return -1;
    }

    //修改指定位置数据
    p->data[post] = data;

    return 0;
}

// 查找指定数据出现的位置,返回下标，未找到返回-1
int SearchDataSeqList(seqlist_p p, int data)
{
    for (int i = 0; i <= p->last; i++)
    {
        if (p->data[i] == data)
            return i;
    }
    return -1;
}

// 清空顺序表（清空：访问不到，但是内存中还有。销毁：内存清空）
void ClearSeqList(seqlist_p p)
{
    p->last = -1;
}

seqlist.h
#ifndef __SEQLIST_H__
#define __SEQLIST_H__
#define N 10
typedef struct seqlist //封装顺序表结构体类型
{
    int data[N]; //用来存数据的数组
    int last;    //代表数组中最后一个有效元素的下标
} seqlist_t, *seqlist_p;

// 创建一个空的顺序表
seqlist_p CreateEpSeqlist(); //create创造 empty 空的 seqlist顺序表

//判断顺序表是否为满，满返回1,未满返回0
int IsFullSeqlist(seqlist_p p); //full满

//向顺序表的指定位置插入数据
int InsertIntoSeqlist(seqlist_p p, int post, int data);

//遍历顺序表sequence顺序list表
void ShowSeqlist(seqlist_p p);

//判断顺序表是否为空，为空返回1，不为空返回0
int IsEpSeqlist(seqlist_p p);

//删除顺序表中指定位置的数据，post为删除位置
int DeleteIntoSeqlist(seqlist_p p, int post);

// 修改指定位置上数据
int ChangePostSeqList(seqlist_p p, int post, int data);

// 查找指定数据出现的位置,返回下标，未找到返回-1
int SearchDataSeqList(seqlist_p p, int data);

// 清空顺序表（清空：访问不到，但是内存中还有。销毁：内存清空）
void ClearSeqList(seqlist_p p);

#endif
makefile

CC=gcc
GFLAGS=-c -g -Wall
OBJS=seqlist.o main.o

seqlist:$(OBJS)
	$(CC) $^ -o $@
%.o:%.c
	$(CC) $(GFLAGS) $< -o $@
.PHONY:clean
clean:
	$(RM) seqlist *.o

顺序表特点：
  1. 顺序表内存空间连续
  2. 顺序表长度固定
  3. 插入和删除操作效率低，修改和查找效率高。

标签：顺序,last,day03,seqlist,int,post,数据结构,data
From： https://blog.csdn.net/QR70892/article/details/141336248

相关文章

  • lg根号数据结构
    根号数据结构序列分块通过将序列分成小段，整块标记，不足整块的暴力，以平衡修改查询的复杂度。如果两个操作的调用次数有较大差异，可以使用分块维护更多/更少信息来平衡两边的时间复杂度。请注意并非选择“更快”的数据结构就更好，比如树状数组看似更平衡，但是修改和询问的次数不平衡......
  • day03JS-函数
    1.什么是函数函数具有某种特定功能的代码块。函数其实本质也是一种数据，属于对象数据类型。2.为什么要有函数解决代码的冗余问题，形成代码复用。可以把整个代码项目，通过函数模块化。封装代码，让函数内部的代码对外部不可见。3.函数的组成函数的声明：function函数名（参数1，......
  • 数据结构与算法——滑动窗口
    目录引言核心思想使用场景解题步骤经典例题1、无重复字符的最长子串（LeetCode3）2、找到字符串中所有字母异位词（LeetCode438）引言定义：滑动窗口是指通过左右两个指针（或索引）来标记窗口的左右边界，随着指针的移动，窗口内的元素不断变化，从而实现对数组或字符串中连续子序列的......
  • 算法与数据结构——空间复杂度
    空间复杂度空间复杂度（spacecomplexity）用于衡量算法占用内存空间随着数据量变大时的增长趋势。这个概念与时间复杂度非常类似，只需将“运行时间”替换为“占用内存空间”。 算法相关空间算法在运行过程中使用的内存空间主要包括以下几种。输入空间：用于存储算法的输入数据。......
  • 【数据结构】详细介绍栈和队列，解析栈和队列每一处细节
    目录一.栈1. 栈的概念2. 栈的实现2.1栈的结构2.2初始化栈2.3入栈2.4出栈2.5获取栈顶元素2.6获取栈中有效个数2.7判断栈是否为空2.8销毁栈 二.队列1.队列的概念2.队列的实现 2.1队列的结构2.2队列初始化 2.3销毁队列 2.4入队列(队尾) ......
  • 算法与数据结构——时间复杂度
    时间复杂度运行时间可以直观且准确地反映算法的效率。要准确预估一段代码的运行时间，应该进行如下操作。确定运行平台，包括硬件配置、编程语言、系统环境等，这些因素都会影响代码的运行效率。评估各种计算操作的运行时间，例如加法操作需要1ns，乘法操作需要10ns，打印操作需要5ns等。......
  • 算法与数据结构——复杂度分析
    复杂度分析算法效率评估在算法设计中，我们追求以下两个层面的目标。找到问题解法：算法需要再规定的输入范围内可靠地求得问题的正确解寻求最优解法：同一个问题可能存在多种解法，我们希望找到尽可能高效的算法。也就是说，在能够解决问题的前提下，算法效率已经成为衡量算法优劣的主......
  • 数据结构（二）- 线性表
    数据结构（二）-线性表数据结构三要素——逻辑结构、数据的运算、存储结构；存储结构不同运算实现的方式不同；1.线性表的定义定义：线性表是具有相同数据类型的n(n>0)个数据元素的有限序列，其中n为表长，当n=0线性表是一个空表。一般表示为L=(a1,a2,…,ai,ai+1,…,an)......
  • 基础数据结构回顾记录
    数组初始化两种方式声明和初始化数组——使用new关键字和使用大括号。refer:https://www.freecodecamp.org/chinese/news/java-array-declaration-how-to-initialize-an-array-in-java-with-example-code/先声明，后赋值//数组声明dateType[]nameOfArray=newdataType......
  • 【数据结构与算法】如何构建最小堆
    最小堆的定义最小堆，作为一种独特且重要的数据结构，它是一种特殊的二叉树。在这种二叉树中，有一个关键的规则：每一个父节点所存储的值，都必然小于或者等于其对应的子节点的值。这一规则确保了根节点总是承载着整个堆中的最小数值。例如，下面这样一个简单的结构就是最小堆：1......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99