数据结构总复习

文章目录

  • 线性表
    • 动态分配的顺序存储结构
    • 链式存储
  • 栈与队列
      • 顺序栈
      • 链栈
    • 队列

线性表

动态分配的顺序存储结构

通过分析代码,我们发现,要注意什么:

  • 要分清你的下标
  • Insert 函数是可以用来没有元素的时候,增加元素的
  • Init(或者Create )函数一般只用来分配空间等的初始化
//动态分配空间的顺序存储结构的线性表
#include<stdio.h>
#include<stdlib.h>#define Linitesize 100
#define Laddsize 10
#define OK 1
#define error 0typedef int Status;
typedef int Elemtype;
typedef struct{Elemtype * elem;int length;int listsize;
}SqList;
void Show(SqList L)
{int i;for(i=0;i<L.length ;i++)printf("%d ",L.elem[i]);printf("\n");return ;
}
Status Create(SqList &L)
{L.elem = (Elemtype *)malloc(Linitesize*sizeof(Elemtype));if(!(L.elem ))return error;L.length = 0;L.listsize = Linitesize;return OK;
} 
//在第i个元素之前插入 ,从1开始计数,就是下标为i
Status Insert(SqList &L,int i,Elemtype e)
{int j;if(i<1||i>L.length+1 )return error;if(L.length>=L.listsize){L.elem =(Elemtype *)realloc(L.elem ,(L.listsize + Laddsize)*sizeof(Elemtype));if(!(L.elem ))return error;L.listsize = L.listsize + Laddsize;}for(j=L.length-1 ;j>=i-1;j--)L.elem[j+1] = L.elem[j];L.elem[i-1] = e;L.length ++;return OK;} 
//i为你想要删除的第几个元素 
Status Delete(SqList &L,int i,Elemtype &e)
{int j;if(i<1||i>L.length )return error;e = L.elem[i-1];for(j=i-1;j<L.length-1;j++)L.elem[j] = L.elem[j+1];L.length --;return OK;
}int main()
{int i,j;Elemtype e;SqList L;Create(L);for(i=1;i<=5;i++)Insert(L,i,i*i);	printf("输出具体数据:\n");Show(L);printf("请输入你想要删除第几个元素:\n");scanf("%d",&j);Delete(L,j,e);printf("删除的数据是:%d \n",e);Show(L);return 0;
}

考点

  • 两个有序递增的顺序表的合并

关键点,可以学到什么,就是分别用pa,pb,pc,来记录首地址,一句话,就是用辅助变量来方便操作

void Merge(Sqlist la,Sqlist lb,Sqlist &lc)
//目标,将原本有序递增的la,pb顺序表整合到lc ,lc认为有序递增的
{pa = la.elem;pb = la.elem;lc.listsize = lc.length = la.length + lb.length;pc =lc.elem = (ElemType *)malloc(lc.listsize*(sizeof(ElemType)));if(!lc.elem)exit OVERFLOW;pa_last = pa + la.length-1;pb_last = pb + lb.length-1;while(pa<=pa_last&&pb<=pb_last){if(*pa<*pb) *pc++ = *pa++;else *pc++ = *pb++;}while(pa<=pa_last) *pc++ = *pa++;while(pb<=pb_last) *pc++ = *pb++;}

顺序表优点与缺点

  • 优点:可以随便进行数据的插入与删除
  • 优点:占据较少的空间
  • 缺点:需要连续的一串地址
  • 缺点:在插入与删除时,要移动大量的元素

链式存储

在这里插入图片描述

//动态分配空间的顺序存储结构的线性表
#include<stdio.h>
#include<stdlib.h>#define Linitesize 100
#define Laddsize 10
#define OK 1
#define error 0typedef int Status;
typedef int Elemtype;typedef struct LNode{struct LNode * next;Elemtype data;
}LNode,*LinkList;
int Length(LinkList L)
{int sum=0;while(L->next !=NULL){sum++;L=L->next ;}return sum;
}
//尾插法 
Status Create(LinkList &L,Elemtype e)
{LinkList p = L;//开始p 指向头结点 while(p->next !=NULL )//找到最后一个结点 p=p->next ;LinkList temp = (LNode *)malloc(sizeof(Elemtype));if(!temp) return error;temp->data = e;//由于p 指向最后一个结点,那么p->next 进行赋值,实际上会改变原来的数据temp->next = p->next ;p->next = temp;return OK;}
Status Show(LinkList L)
{LinkList p = L->next  ;while(p !=NULL){printf("%d ",p->data );p = p->next ;}printf("\n");return OK;
}
//在第i 个元素之前插入 ,确保不超过范围 
Status Insert(LinkList &L,int i,Elemtype e)
{if(i<1||i>Length(L)+1)return error;LinkList p = L;//指向头结点//找到第i-1个结点int j ;for(j=1;j<i;j++)p = p->next ; LinkList temp = (LNode * )malloc(sizeof(LNode));if(!temp) return error;temp->data = e;temp->next = p->next ;p->next = temp;return OK;
}
Status Delete(LinkList &L,int i,Elemtype &e)
{//删除第i 个元素,并返回其值if(i<1||i>Length(L))return error;//找到第i-1个结点int j;LinkList temp = L;for(j=1;j<i;j++)temp = temp->next ;e = temp->next->data;temp->next = temp->next->next;return OK;
}
int main()
{Elemtype e;LinkList L = (LNode *)malloc(sizeof(LNode));L->next = NULL;for(int i = 1;i<= 5;i++)Create(L,i);Show(L);Insert(L,2,10);Show(L);Delete(L,3,e);Show(L);printf("%d \n",e);return 0;}

应用

  • 有序非递减链表的整合
  • 有序非递减链表求交集
  • 有序

优点以及缺点

  • 优点:插入与删除不用移动大量的元素
  • 优点:不需要连续的地址
  • 优点:采用动态链表不用固定最大长度
  • 缺点:占用较大的内存
  • 缺点:不可以随机访问某个元素

栈与队列

定义:只能在表尾进行插入与删除的线性表(先进后出)

  • 表尾是栈顶,表头是栈底

在这里插入图片描述

顺序栈

  • 顺序栈的精髓就是通过S.top == S.base 来判断栈是否为空
  • 用S.top-S.base >=stacksize 来判断栈是否满
#include<stdio.h>
#include<stdlib.h>#define initsize 100
#define addsize 50
#define OK 1
#define error 0typedef int Status;
typedef int Elemtype;typedef struct{Elemtype *base,*top;int stacksize;
}SqStack;
Status Init(SqStack &S)
{S.base =(Elemtype *)malloc(initsize*sizeof(Elemtype ));if(!S.base )return error;S.top = S.base ;//说明此时栈为空S.stacksize = initsize;return OK;}
Status Push(SqStack &S,Elemtype e)
{if(S.top -S.base >=S.stacksize )//栈满{S.base =(Elemtype *)realloc(S.base ,(initsize + addsize)*sizeof(Elemtype));if(!S.base)return error;}*(S.top ) = e;S.top ++;return OK;
}
Status Pop(SqStack &S,Elemtype &e)
{if(S.base == S.top )return error;//栈为空S.top --;e = *(S.top );return OK;}
int main()
{int n,i;Elemtype e;SqStack S;Init(S);printf("请输入你想要入栈的元素的个数:\n");scanf("%d",&n);for(i=1;i<=n;i++){printf("请输入你要入栈的元素:");scanf("%d",&e);Push(S,e);}printf("出栈 \n");for(i=1;i<=n;i++){Pop(S,e);printf("%d ",e);}return 0;
}

链栈

在这里插入图片描述

  • 相比之下,链栈的操作更为简单,
  • 在初始化的时候给传递过来的头指针分配一个头结点
  • 当S->next ==NULL 的时候,就说明栈为空
  • 进行插入操作的时候,先分配空间LinkStack temp ,来存储数据,temp->next =S->next; S->next=S
  • 删除操作的时候,temp = S-> next,e = temp ->data;S->next = temp ->next;
  • 不过应该注意的是,链栈是在队头进行操作,区别于顺序栈的队尾,不过,可以这么记忆,你在哪边进行插入的就在哪边进行删除就可以

#include<stdio.h>
#include<stdlib.h>#define OK 1
#define Error 0typedef int Status;
typedef int Elemtype;typedef struct Node {Elemtype data;struct Node * next;
}Node,*ListStack;Status InitStack(ListStack &S)
{S =(ListStack )malloc(sizeof(Node));if(!S)  return Error;S->next = NULL ;return OK;}
Status Pop(ListStack &S,Elemtype &e)
{if(S->next ==NULL)//栈为空return Error;ListStack p = S->next ;e = p->data  ;S->next = p->next ;free(p);return OK; 
}Status Push(ListStack &S,Elemtype e)
{ListStack p =(ListStack )malloc(sizeof(Node));if(!p)	return Error;p->data = e;p->next = S->next ;S->next = p;return OK;
}int main()
{ListStack S;Elemtype e;int i; InitStack(S);printf("请输入想要进栈的6个数据:\n");for(i=1;i<=6;i++){scanf("%d",&e);Push(S,e);}printf("依次出栈:\n");for(i=1;i<=6;i++){Pop(S,e);printf("%d ",e);}return 0;}

队列

在这里插入图片描述

  • 链队列:判断为空的条件:Q.rear==Q.front 指向头结点
  • 这也要求了,在删除操作的时候,要判断删除之后是否为空,要是为空就让两个指针相等
#include<stdio.h>
#include<stdlib.h>#define OK 1
#define Error 0typedef int Status ;
typedef int Elemtype;typedef struct QNode{Elemtype data ;struct QNode * next;}QNode,*QueuePtr;
typedef struct{QueuePtr front;QueuePtr rear;
}LinkQueue;Status InitQueue(LinkQueue &Q)
{QNode * p=(QNode *)malloc(sizeof(QNode));//头结点 if(!p)	return Error;p->next =NULL;  Q.front =Q.rear =p;return OK;
}
Status Push(LinkQueue &Q,Elemtype e)
{QNode * p=(QNode *)malloc(sizeof(QNode));if(!p)	 return Error;p->data =e;p->next = Q.rear ->next;Q.rear ->next = p;Q.rear = p ;return OK;
}
Status Pop(LinkQueue &Q,Elemtype &e)
{if(Q.front ==Q.rear )//队列为空return Error;QNode * p ;p = Q.front ->next;e = p->data;Q.front ->next = p->next ;if(Q.rear == p)Q.rear = Q.front ; free(p);return OK;
}
int main()
{LinkQueue Q;Elemtype e;printf("创建带有头结点的链队列\n");InitQueue(Q);printf("请输入5个你想要依次入队列的数字\n");for(int i=1;i<=5;i++){scanf("%d",&e);Push(Q,e);}printf("依次出队列\n");for(int i=1;i<=5;i++){Pop(Q,e);printf("%d ",e);}return 0;}

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

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

相关文章

Servlet概念视频笔记

学习地址:121-尚硅谷-Servlet-什么是Servlet_哔哩哔哩_bilibili 目录 1.Servlet技术 a.什么是Servlet b.手动实现Servlet程序 c.url地址如何定位到Servlet程序去访问 d.Servlet的生命周期 e.GET 和 POST 请求的分发处理 f.通过继承 HttpServlet 实现 Servlet程序 g.使用…

微服务架构:解析分布式系统的演进

目录 微服务是什么&#xff1f; 微服务的优势 微服务的挑战 应对微服务挑战的方法 结论 在当今快速发展的软件开发领域&#xff0c;微服务架构成为一种备受瞩目的设计理念&#xff0c;被广泛应用于构建灵活、可扩展的分布式系统。本文将深入探讨什么是微服务&#xff0c;为…

论文阅读:“Appearance Capture and Modeling of Human Teeth”

文章目录 AbstractIntroductionMethod OverviewTeeth Appearance ModelEnamelDentinGingiva and oral cavity Data AcquisitionImage captureGeometry capture ResultsReferences Abstract 如果要为电影&#xff0c;游戏或其他类型的项目创建在虚拟环境中显示的人类角色&#…

模糊C均值(Fuzzy C-means,FCM)聚类的可运行的python程序代码,复制即可用!!切记需要安装库 scikit-fuzzy

文章目录 前言一、安装库 scikit-fuzzy二、具体程序代码&#xff08;复制可运行&#xff09;三、结果展示总结 前言 模糊C均值&#xff08;Fuzzy C-means&#xff0c;FCM&#xff09;聚类是一种软聚类方法&#xff0c;它允许数据点属于多个聚类&#xff0c;每个数据点对所有聚…

Matlab 点云线性指数计算(加权)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 思路其实很简单,即对每个邻近点集中的点,根据其到点集中心的距离进行加权处理(权重函数),之后再基于加权之后的点获取其协方差矩阵,最后再求取其相关的特征值,以此来获取该点的线性指数。相关公式如下所示:…

IntelliJ IDEA安装使用教程

IntelliJ IDEA是一个流行的Java 集成开发环境&#xff08;IDE&#xff09;&#xff0c;由JetBrains公司开发。它是一款全功能的IDE&#xff0c;支持多种编程语言&#xff0c;如Java、Kotlin、Groovy、Scala、Python、JavaScript、HTML、CSS等等。IntelliJ IDEA 提供了高效的代码…

docker-compose脚本编写及常用命令

安装 linux DOCKER_CONFIG/usr/local/lib/docker/cli-plugins sudo mkdir -p $DOCKER_CONFIG/cli-plugins sudo curl -SL https://521github.com/docker/compose/releases/download/v2.6.1/docker-compose-linux-x86_64 -o $DOCKER_CONFIG/cli-plugins/docker-compose sudo c…

AntDB“超融合+流式实时数仓”——颠覆50年未变的数据库内核

流式处理引擎&#xff0c;颠覆50年未变的数据库内核 流式处理的概念 2001年9月11日&#xff0c;美国世贸大楼被袭击&#xff0c;美国国防部第一次将“主动预警”纳入国防的宏观战略规划。而IBM作为当时全球最大的IT公司&#xff0c;承担了大量基础支撑软件研发的任务。其中200…

2021年11月10日 Go生态洞察:Twelve Years of Go

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…

计算机网络:快速了解网络框架

文章目录 前言一、什么是Internet&#xff1f;1.从具体构成角度什么是协议&#xff1f; 2.从服务角度3小结 二、网络边缘1.采用网络设施面向连接服务&#xff08;TCP&#xff09;2.采用基础设施的无连接服务&#xff08;UDP&#xff09; 三、网络的核心1.电路交换2.分组交换3.分…

软件工程 - 第8章 面向对象建模 - 2 静态建模

静态建模&#xff08;类和对象建模&#xff09; 类和对象模型的基本模型元素有类、对象以及它们之间的关系。系统中的类和对象模型描述了系统的静态结构&#xff0c;在UML中用类图和对象图来表示。 类图由系统中使用的类以及它们之间的关系组成。类之间的关系有关联、依赖、泛…

Google Chrome 下载 (离线版)

1 访问网址 Google Chrome 网络浏览器 2 点击 下载Chrome 3 直接运行 ChromeStandaloneSetup64.exe 其他&#xff1a; ####################### 谷歌浏览器 (Google Chrome) 最新版离线安装包下载 https://www.iplaysoft.com/tools/chrome/#google_vignette Google Chrome …

【译】Spring 6 入参数据校验: 综合指南

原文地址&#xff1a;Spring 6 Programmatic Validator: A Comprehensive Guide 一、前言 在 Spring 6.1 中&#xff0c;有一个非常值得注意的重要改进——编程式验证器实现。Spring 长期以来一直通过注解支持声明式验证&#xff0c;而 Spring 6.1 则通过提供专用的编程式验证…

kafka学习笔记(一)--脑裂

我知道你想裂&#xff0c;但你先别裂 目录 脑裂Kafka脑裂实验Kafka如何防止脑裂--Leader Epochepoch的局限性ISR列表ISR列表的伸缩机制 脑裂 用集群部署的大多数的分布式系统无可避免会面临脑裂问题。简单来说&#xff0c;脑裂就是在同一时刻出现了两个“Leader&#xff08;或…

Vue+Element-ui实例_在form中动态校验tag标签

1.开发需求 在日常开发中&#xff0c;我们会遇到form表单的动态添加和校验&#xff0c;当我们需要在动态添加的内容中再次动态使用输入框的时候&#xff0c;就会变得很繁琐&#xff0c;我在网上找了很多案例&#xff0c;没有符合自己需求的内容&#xff0c;只好闲暇时间自己搞…

css加载会造成阻塞吗??

前言 前几天面试问到了这个问题&#xff0c;当时这个答得不敢确定哈哈&#xff0c;虽然一面还是过了 现在再分析下这个&#xff0c;总结下&#xff0c;等下次遇到就能自信得回答&#xff0c;666 准备工作 为了完成本次测试&#xff0c;先来科普一下&#xff0c;如何利用chr…

【开源】基于Vue和SpringBoot的农家乐订餐系统

项目编号&#xff1a; S 043 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S043&#xff0c;文末获取源码。} 项目编号&#xff1a;S043&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 用户2.2 管理员 三、系统展示四、核…

Peter算法小课堂—差分与前缀和

差分 Codeforces802 D2C C代码详解 差分_哔哩哔哩_bilibili 一维差分 差分与前缀和可以说成减法和加法的关系、除法和乘法的关系、积分和微分的关系&#xff08;听不懂吧&#xff09; 给定数组A&#xff0c;S为A的前缀和数组&#xff0c;则A为S的差分数组 差分数组构造 现…

openbabel 安装 生成指纹方法

今日踩坑小结&#xff1a; openbabel 安装&#xff1a; 可以装&#xff0c;但是得在 Linux 环境下&#xff0c;win 环境装会报错&#xff08;安装不会报错&#xff0c;但是生成指纹的时候会&#xff09; 指纹&#xff1a; 在下面这个链接里&#xff0c;官方给出了命令行调用 o…

这几款 idea 插件让效率起飞!

作者&#xff1a;苍何&#xff0c;前大厂高级 Java 工程师&#xff0c;阿里云专家博主&#xff0c;CSDN 2023 年 实力新星&#xff0c;土木转码&#xff0c;现任部门技术 leader&#xff0c;专注于互联网技术分享&#xff0c;职场经验分享。 &#x1f525;热门文章推荐&#xf…