数据结构第一天

数据结构基础知识

1.1 什么数据结构

数据结构就是数据逻辑结构以及存储操作 (类似数据的运算)

数据结构教会你一件事如何有效存储数据

1.2 数据

数据不再是单纯而是类似于集合概念

数据元素数据基本单位若干数据项组成

数据项数据最小单位描述数据元素有用信息

数据元素又叫节点

例如:

计算机处理的对象(数据)已不再是单纯的数值:

图书管理中的数据,如下表所列:

数据:图书

数据元素:每一本书

数据项:编号书名作者出版社

1.3 逻辑结构

数据元素并不是孤立存在的,它们之间存在着某种关系(或联系、结构)。元素和元素之间的关系:

  • 线性关系

线性结构 ==> 一对一 ==> 线性表顺序表链表队列

  • 层次关系

树形结构 ==> ==> 二叉树

  • 网状关系

图状结构 ==> ==>

例题:

田径比赛的时间安排问题

1.4 存储结构

数据的逻辑结构在计算机中的具体实现(数据的运算)

1.4.1 顺序存储

特点内存连续随机存取每个元素占用较少

实现数组

1.4.2 链式存储

通过指针存储

特点内存不连续通过指针实现

链表实现

结构体:

#include <stdio.h>struct node
{int data;          //数据域:存放节点中要保存的数据struct node *next; //指针域:保存下一个节点的地址,也就是说指向了下一个节点 (类型为自身结构体指针)
};int main()
{//定义三个节点struct node A = {1, NULL}; //定义结构体变量的同时给每个成员赋值struct node B = {2, NULL};struct node C = {3, NULL};// struct node D;   //先定义结构体变量,再单独给其中成员赋值// D.data=4;// D.next=NULL;//连接三个节点
    A.next = &B; //连接A和B节点,通过让A中的指针域保存B的地址
    B.next = &C;printf("%d\n", A.data);printf("%d\n", A.next->data);printf("%d\n", A.next->next->data);
}

1.4.3 索引存储结构

存储数据同时建立一个附加索引表

也就是索引存储结构 = 索引表 + 存数据文件

可以提高查找速度,特点检索速度快,但是占用内存多,删除数据文件要及时更改索引表。

1.4.4 散列存储

数据存储按照和关键码之间的关系进行存取。关系由自己决定,比如关键码是key, 存储位置也就是关系是key+1。获取关键数据,通过元素的关键码方法的返回值来获取。

存的时候按关系存

取的时候按关系取

1.5 操作

增删改查

  1. 算法基础知识

2.1 什么算法

算法就是解决问题思想方法数据结构算法基础

数据结构 + 算法 = 程序

2.2 算法设计

算法设计 取决于数据逻辑结构

算法实现:依赖于数据存储结构

2.3 算法特性

有穷性 步骤有限

确定性每一个步骤都有明确含义无二义性

可行性规定时间内可以完成

输入

输出

2.4 评价好坏

正确性

易读性

健壮性容错处理

高效性执行效率通过重复执行语句次数判断也就是时间复杂度(时间处理函数)判断

时间复杂度:

语句频度:用时间规模函数表达

时间规模函数: T(n)=O(f(n))

T(n) //时间规模的时间函数

O //时间数量级

n //问题规模,例如:a[100], n=100

f(n) //算法可执行重复语句的次数

称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

渐进时间复杂度用大写O来表示,所以也被称为大O表示法。直白的讲,时间复杂度就是把时间规模函数T(n)简化为一个数量级,如n,n^2,n^3。

例1:

求1+2+3+4+...+n的和

算法1:

int sum=0;
for(int i=1;i<=n;i++)
{
    sum += i; //重复执行n次
}

f(n) = n

==>T(n) = O(n)

算法2

利用等差数列前n项和公式:Sn=n*a1+n(n-1)d/2 或 Sn=n(a1+an)/2 (d是公差)

int sum = (1+n)*n/2;   //重复执行1次

f(n) = 1

==> T(n) = O(1)

2

int i,j;
for(i=0;i<n;i++)
{for(j=0;j<n;j++){printf("ok\n");        //重复执行n*n次}
}

T(n) = O(n^2)

3

int i,j;
for(i=0;i<n;i++)
{for(j=0;j<=i;j++){printf("ok\n");  }
}

1 + 2 + ... n

f(n) = n*(1+n)/2 = n^2/2 + n/2 //保留最高项n^2/2, 除以最高项系数 得到n^2

T(n) = O(n^2)

计算大O的方法

  1. 根据问题规模n写出表达式f(n)
  2. 如果有常数项,将其置为1 //f(n)表达式只有常数项例如f(n) = 8 ==> O(1)
  3. 只保留最高项,其他项舍去。
  4. 如果最高项系数不为1,则除以最高项系数。

     f(n) = 3*n^4 + 2*n^3 + 6*n^7 +10;

     ==> O(n^7)

  1. 线性表

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

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

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

特点一对一每个节点最多一个前驱后继首节点前驱节点后继

3.1 顺序表

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

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

3.1.1 顺序特性

逻辑结构线性结构

存储结构顺序存储结构

特点内存连续

操作增删改查

3.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.1.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)
{
}int main(int argc, char const *argv[])
{
    seqlist_p p = CreateEpSeqlist();return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/402403.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用 Python 进行 PDF 文件加密

使用 Python 解密加密的 PDF 文件-CSDN博客定义一个名为的函数&#xff0c;该函数接受三个参数&#xff1a;输入的加密 PDF 文件路径input_pdf、输出的解密 PDF 文件路径output_pdf和密码password。https://blog.csdn.net/qq_45519030/article/details/141256661 在数字化时代…

优先级队列的实现

什么是优先级队列 优先级队列是一种特殊的数据结构&#xff0c;它类似于队列或栈&#xff0c;但是每个元素都关联有一个优先级或权重。在优先级队列中&#xff0c;元素的出队顺序不是简单地按照它们进入队列的先后顺序&#xff08;先进先出&#xff0c;FIFO&#xff09;&#…

虚幻5|角色武器装备的数据库学习(不只是用来装备武器,甚至是角色切换也很可能用到)

虚幻5|在连招基础上&#xff0c;给角色添加武器并添加刀光|在攻击的时候添加武器并返回背后&#xff08;第一部分&#xff0c;下一部分讲刀光&#xff09;_unreal 如何给角色添加攻击-CSDN博客 目的&#xff1a;捡起各种不同的武器&#xff0c;捡起的武器跟装备的武器相匹配 …

练习:python条件语句、循环语句和函数的综合运用

需求描述&#xff1a; 期望输出效果&#xff1a; 练习成果&#xff1a; #简单的银行业务流程 many 50000 def main_menu():print("----------主菜单----------"f"\n{name}您好&#xff0c;欢迎来到ATM&#xff0c;请选择操作&#xff1a;""\n查询余…

挑战同档位最强护眼性能,书客L2 Pro革新护眼台灯全新体验!

2024年8月17日&#xff0c;SUKER书客在今日宣布&#xff1a;书客护眼台灯L2 PRO正式发售。书客作为专业护眼台灯实力老牌&#xff0c;主打“医学养护眼”的特性&#xff0c;是唯一做到降低96%近视风险的同时&#xff0c;缓解88%用眼疲劳&#xff0c;光源99.8%高度还原自然光&am…

Ubuntu离线安装docker

查看操作系统版本&#xff1a; rootzyh-VMware-Virtual-Platform:~/install# lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 24.04 LTS Release: 24.04 Codename: noble rootzyh-VMware-Virtual-Platform:~/install#…

删除镜像报子镜像依赖错误

1、删除镜像报子镜像依赖错误 出现这个错误的原因是因为有其他镜像依赖需要删除的镜像。 2解决方法 2.1首先查看无法删除的镜像被哪些镜像所依赖 docker image inspect --format{{.RepoTags}} {{.Id}} {{.Parent}} $(docker image ls -q --filter since${image_id}) # ${ima…

在阿里云上部署 Docker并通过 Docker 安装 Dify

目录 一、在服务器上安装docker和docker compose 1.1 首先关闭防火墙 1.2 安装docker依赖包 1.3 设置阿里云镜像源并安装docker-ce社区版 1.4 开启docker服务并设置开机自启动 1.5 查看docker版本信息 1.6 设置镜像加速 1.7 将docker compose环境复制到系统的bin目录下…

Jmeter接口测试断言详解

&#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 一、响应断言 对服务器的响应接口进行断言校验&#xff0c;来判断接口测试得到的接口返回值是否正确。 二、添加断言 1、apply to&#xff1a; 通常发出一个请…

可视化编程-七巧低代码入门02

1.1.什么是可视化编程 非可视化编程是一种直接在集成开发环境中&#xff08;IDE&#xff09;编写代码的编程方式&#xff0c;这种编程方式要求开发人员具备深入的编程知识&#xff0c;开发效率相对较低&#xff0c;代码维护难度较大&#xff0c;容易出现错误&#xff0c;也需要…

nginx核心配置示例

目录 1、nginx location的详细使用 &#xff08;1&#xff09;精确匹配 &#xff08;2&#xff09;区分大小写 &#xff08;3&#xff09;不区分大小写 &#xff08;4&#xff09;匹配文件名后缀 2、nginx下的用户认证 3、nginx自定义错误页面 4、自定义错误日志 5、n…

WordPress建站之头像及字体错误修正

目录 一、谷歌字体 二、头像网址 三、后续使用中的“坑” 网站建设好以后,会发现有些卡顿,网速好的环境感觉不明写,但是差的环境就难以忍受了。这是打开网页的控制台(Console)会发现有报错信息: 这些报错信息反应了2个问题: 谷歌字体网站无法访问头像网站无法访问下面…

基于Springboot 和Vue 的高校宿舍管理系统源码

网络上很多宿舍管理系统都不完整&#xff0c;大多数缺少数据库文件&#xff0c;所在使用极其不方便&#xff0c;由于本人程序员&#xff0c;根据代码&#xff0c;自己花时间不全了数据库文件&#xff0c;并且可以完美运行&#xff01;&#xff01;&#xff01;&#xff01;&…

基于VS2022+Qt5+C++的串口助手开发

目录 一、前言 二、环境准备 三、创建QT串口项目 ​编辑 四、串口项目实现 1.ui界面设计 2.添加QT串口模块 3.功能实现 ①串口扫描 ②波特率、停止位等设置 ③接收数据 ④发送数据 五、最终效果 六、总结 一、前言 如果有人之前看过我文章的话应该知道&#xf…

Hbase架构和读写流程

目录 1.概述 2.简介 3.Hbase架构 4.数据模型 5.Hbase写流程 6.Hbase读数据 1.概述 本篇文章将简单的讲述Hbase的架构和读写流程&#xff0c;多为理论部分&#xff0c;不涉及API代码 2.简介 从官方介绍可以知道,Hbase是一种分布式、可扩展、支持海量数据存储的 NoSQ…

Element-UI动态生成的表单元素验证示例

模拟数据 tableData: [{name: "系统1",score: 0,children:[{name: "一号子系统",score: 0,}]},{name: "系统2",score: 0,children:[{name: "3号子系统",score: 0,}]},{name: "系统3",score: 0,children:[{name: "5号子…

python-docx在word文件表格中指定行下插入新一行并填充值

from docx import Document from copy import deepcopydef insert_row_after_specific_value(doc, table_index, column_header, target_value, new_row_data):# 加载文档# doc doc_path# 检查表格索引是否有效if table_index > len(doc.tables):print("文档中没有足够…

matlab 音频音量处理(音量大小按照dB调节)

1 音量(声压级)以分贝(dB)表示的计算公式为: 2 % 已知的 x 值 x = 0:-1:-127; % 在这里填入 x 的具体值% 计算 y %y = 10

江理工文档管理系统的设计与实现

TOC springboot148江理工文档管理系统的设计与实现 绪论** 1.1 研究背景 在这个推荐个性化的时代&#xff0c;采用新技术开发一个文档系统来分享和展示内容是一个永恒不变的需求。本次设计的文档管理系统有管理员和用户两个角色。管理员功能有论坛管理&#xff0c;公告管理…

Spark-环境启动

一、概览 从start-all.sh开始捋&#xff0c;一直捋到Master、Worker的启动并建立通信 二、宏观描述 Master端 1、start-all.sh调用start-master.sh启动Master 2、执行org.apache.spark.deploy.master.Master中main方法 3、通过工厂模式创建RpcEnv子类NettyRpcEnv a、创建…