数据结构P46（2-1~2-4）

2-1编写算法查找顺序表中值最小的结点，并删除该结点

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct List
{int Max;//最大元素 int n;//实际元素个数 DataType *elem;//首地址 
};
typedef struct List*SeqList;//顺序表类型定义
SeqList SetNullList_Seq(int m)
{SeqList slist=(SeqList)malloc(sizeof(struct List));if(slist!=NULL){slist->elem=(DataType*)malloc(sizeof(DataType)*m);//申请顺序表空间，大小为m个DataType空间 if(slist->elem){slist->Max=m;//顺序表赋予的最大值 slist->n=0;//顺序表长度赋值为0 return(slist);}else free(slist);}printf("Alloc failure!\n");return NULL;}int IsNullList_seq(SeqList slist)
{return(slist->n==0);
} /*int InsertPre_seq(SeqList slist ,int p, DataType x)
{int q;if (slist->n>=slist->Max)//顺序表满了 {printf("overflow");return 0;}if(p<0||p>slist->n)//下标不存在 {printf("not exist!\n");return 0;}for(q=slist->n-1;q>=p;q--){slist->elem[q+1]=slist->elem[q];}slist->elem[p]=x;slist->n=slist->n+1;return 1;
}*/int DelIndex_seq(SeqList slist,int p)
{int i=0,q=0;for(i=0;i<slist->n;i++){if(slist->elem[i]==p){for(q=i;q<slist->n-1;q++){slist->elem[q]=slist->elem[q+1];}slist->n=slist->n-1;return 1;}}
}
void Print(SeqList slist)
{int i;for(i=0;i<slist->n;i++){printf("%d\n",slist->elem[i]);}
}int Insert_min(SeqList slist)
{int min=0,i=0;min=slist->elem[0];for(i=0;i<slist->n;i++){if(slist->elem[i]<min){min=slist->elem[i];}}return min;
}
int main()
{SeqList alist;int max,len,i,x,p;printf("\n please input the max value(<100) of max=");scanf("%d",&max);alist=SetNullList_Seq(max);printf("%d\n",IsNullList_seq(alist));if(alist!=NULL){printf("\n please input the length of list len =");scanf("%d",&len);for(i=0;i<len;i++){scanf("%d",&x);alist->elem[i]=x;alist->n=i+1;}}printf("The List is:\n"); Print(alist);p=Insert_min(alist);DelIndex_seq(alist,p);printf("After deleting the min the list is :\n");Print(alist);return 1;
}

在这里插入图片描述

2-2编写算法查找单链表中值最大的结点，并将该结点移至链表尾部


#include<stdio.h>
#include<stdlib.h>typedef int DataType; 
struct Node
{DataType      data; struct Node*  next;  
};
typedef struct Node  *PNode;    
typedef struct Node  *LinkList;   void MoveMaxToTail(head);LinkList SetNullList_Link() //设置头结点
{LinkList head = (LinkList)malloc(sizeof(struct Node));if (head != NULL) head->next = NULL;else printf("alloc failure");return head; 
}void CreateList_Tail(struct Node* head)//利用尾插法
{PNode p = NULL;PNode q = head;DataType data;scanf("%d", &data);while (data != -1){   p = (struct Node*)malloc(sizeof(struct Node));p->data = data;p->next = NULL;q->next = p;q = p;scanf("%d", &data);}
}
void  MoveMaxToTail(LinkList head)//移动到最后
{PNode pmax=NULL,p=NULL,pre=NULL,end=NULL;pmax=head->next;p=head->next->next;while(p){if(p->data>pmax->data){pmax=p;}p=p->next;}if(pmax->next==NULL){return 1;}else{p=head;while(p){if(p->next==pmax){pre=p;}if(p->next==NULL){end=p;}p=p->next;}pre->next=pmax->next;pmax->next=end->next;end->next=pmax;} return 0;
}
void print(LinkList head)   //打印
{PNode  p = head->next;while (p){printf("%d ", p->data);p = p->next;}
}
void DestoryList_Link(LinkList head)  //销毁链表
{PNode  pre = head; PNode p = pre->next;while (p){free(pre);pre = p;p = pre->next;}free(pre);
}int main()
{LinkList head = NULL;head = SetNullList_Link();CreateList_Tail(head);MoveMaxToTail(head);print(head);DestoryList_Link(head);return 0;
}

在这里插入图片描述

2-3编写算法实现顺序表的就地逆序置，即利用原表的存储空间将线性表（a1.a2,…,an）逆置为（an,an-1,…,a1），并分析设计的算法时间复杂度

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct List
{int Max;//最大元素 int n;//实际元素个数 DataType *elem;//首地址 
};
typedef struct List*SeqList;//顺序表类型定义
SeqList SetNullList_Seq(int m)
{SeqList slist=(SeqList)malloc(sizeof(struct List));if(slist!=NULL){slist->elem=(DataType*)malloc(sizeof(DataType)*m);//申请顺序表空间，大小为m个DataType空间 if(slist->elem){slist->Max=m;//顺序表赋予的最大值 slist->n=0;//顺序表长度赋值为0 return(slist);}else free(slist);}printf("Alloc failure!\n");return NULL;}int IsNullList_seq(SeqList slist)
{return(slist->n==0);
} void Print(SeqList slist)
{int i;for(i=0;i<slist->n;i++){printf("%d\n",slist->elem[i]);}
}void DispList(SeqList slist)
{int i,x;for(i=0;i<slist->n/2;i++)// 只需要遍历原表的一半就可以实现数据元素位置的交换{x=slist->elem[i];slist->elem[i]=slist->elem[slist->n-i-1];slist->elem[slist->n-i-1]=x;}
}int main()
{SeqList alist;int max,len,i,x,p;printf("\n please input the max value(<100) of max=");scanf("%d",&max);alist=SetNullList_Seq(max);printf("%d\n",IsNullList_seq(alist));if(alist!=NULL){printf("\n please input the length of list len =");scanf("%d",&len);for(i=0;i<len;i++){scanf("%d",&x);alist->elem[i]=x;alist->n=i+1;}}printf("The List is:\n"); Print(alist);DispList(alist);printf("The dispList is:\n"); Print(alist);return 1;
}

在这里插入图片描述
这段代码实现了一个顺序表，其中包括初始化、判断是否为空表、打印表元素、反转表元素等功能。算法时间复杂度如下：

  1. SetNullList_Seq：申请顺序表空间，时间复杂度为O(1)。
  2. IsNullList_seq：判断是否为空表，时间复杂度为O(1)。
  3. Print：遍历表元素并打印，时间复杂度为O(n)，其中n为表的长度。
  4. DispList：遍历表元素并交换位置，时间复杂度为O(n/2)，其中n为表的长度。

所以，整个代码的时间复杂度取决于最耗时的操作，即遍历表元素和交换位置。因此，整体的时间复杂度为O(n)。

2-4编写算法实现链表得到就地逆置，即利用原表的存储空间将线性表（a1,a2,…,an），逆置为（an,an-1,…,a1），并分析设计的算法时间复杂度

#include<stdio.h>
#include<stdlib.h>typedef int DataType; 
struct Node
{DataType      data; struct Node*  next;  
};
typedef struct Node  *PNode;    
typedef struct Node  *LinkList;   LinkList SetNullList_Link() //设置头结点
{LinkList head = (LinkList)malloc(sizeof(struct Node));if (head != NULL) head->next = NULL;else printf("alloc failure");return head; 
}void CreateList_Tail(struct Node* head)//利用尾插法
{PNode p = NULL;PNode q = head;DataType data;scanf("%d", &data);while (data != -1){   p = (struct Node*)malloc(sizeof(struct Node));p->data = data;p->next = NULL;q->next = p;q = p;scanf("%d", &data);}
}
void ListOppose(LinkList head)//逆置 
{LinkList p,t;p=head->next;while(p->next!=NULL){t=p->next;p->next=t->next;//此时跳过了t结点元素，也就是说t结点元素脱离了链表t->next=head->next; //将t结点元素放在头结点后面，即t结点元素成为第一个结点head->next=t; //头结点的指针指向t}
}
void print(LinkList head)   //打印
{PNode  p = head->next;while (p){printf("%d ", p->data);p = p->next;}
}
void DestoryList_Link(LinkList head)  //销毁链表
{PNode  pre = head; PNode p = pre->next;while (p){free(pre);pre = p;p = pre->next;}free(pre);
}int main()
{LinkList head = NULL;head = SetNullList_Link();CreateList_Tail(head);print(head);printf("\n");ListOppose(head);print(head);return 0;
}

在这里插入图片描述
这段代码实现了一个链表，并包括了创建链表、逆置（反转）链表、打印链表和销毁链表等功能。算法的时间复杂度如下：

  1. SetNullList_Link：创建头结点，时间复杂度为O(1)。
  2. CreateList_Tail：利用尾插法创建链表，时间复杂度为O(n)，其中n为输入的元素个数。
  3. ListOppose：逆置链表，时间复杂度为O(n)，其中n为链表的长度。
  4. print：遍历链表并打印，时间复杂度为O(n)，其中n为链表的长度。
  5. DestroyList_Link：销毁链表，时间复杂度为O(n)，其中n为链表的长度。

因此，整个代码的时间复杂度取决于具有最高时间复杂度的操作，即创建链表、逆置链表和销毁链表，这三者的时间复杂度均为O(n)。所以，整体的时间复杂度为O(n)。

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

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

相关文章

Linux系统之安装cook菜谱工具

Linux系统之安装cook菜谱工具

Linux系统之安装cook菜谱工具 一、cook菜谱工具介绍二、本地环境介绍2.1 本地环境规划2.2 本次实践介绍 三、检查本地环境3.1 检查本地操作系统版本3.2 检查系统内核版本3.3 检查系统是否安装pnpm 四、部署Node.js环境4.1 下载Node.js安装包4.2 解压Node.js安装包4.3 复制二进制…
阅读更多...
为什么网络安全明明缺口很大，却看起来招聘很少呢？

为什么网络安全明明缺口很大，却看起来招聘很少呢？

2023 年我国网络空间安全人才数量缺口超过了 140 万&#xff0c;就业人数却只有 10 多万&#xff0c;缺口高达了 93%。这里就有人会问了&#xff1a; 1、网络安全行业为什么这么缺人&#xff1f; 2、明明人才那么稀缺&#xff0c;为什么招聘时招安全的人员却没有那么多呢&…
阅读更多...
一文解释mapState的来龙去脉

一文解释mapState的来龙去脉

mapState Vuex 提供的辅助函数之一&#xff0c;将 store 中的状态映射到组件的计算属性中&#xff0c;使得在组件中可以轻松地访问 Vuex store 中的状态值 MapState(映射状态) 在我们的 Count.vue 组件中&#xff0c;可以使用 mapState 来更简洁地获取 count 的状态值 首先&…
阅读更多...
【c++_containers】10分钟带你学会list

【c++_containers】10分钟带你学会list

前言 链表作为一个像是用“链子”链接起来的容器&#xff0c;在数据的存储等方面极为便捷。虽然单链表单独在实际的应用中没用什么作用&#xff0c;但是当他可以结合其他结构&#xff0c;比如哈希桶之类的。不过今天学习的list其实是一个带头双向链表。 言归正传&#xff0c;让…
阅读更多...
【ARM】（1）架构简介

【ARM】（1）架构简介

前言 ARM既可以认为是一个公司的名字&#xff0c;也可以认为是对一类微处理器的通称&#xff0c;还可以认为是一种技术的名字。 ARM公司是专门从事基于RISC技术芯片设计开发的公司&#xff0c;作为知识产权&#xff08;IP&#xff09;供应商&#xff0c;本身不直接从事芯片生产…
阅读更多...
iphone怎么传大量照片到电脑，这四招你要学会

iphone怎么传大量照片到电脑，这四招你要学会

如果你喜欢用iPhone拍照、总会遇到要把大量照片从iPhone传输到电脑的情况&#xff0c;要是你对这方面不熟悉就很容易浪费时间。下面小编就介绍几种方法可以快速高效的传大量照片到电脑上去。 iPhone传输照片到电脑 方法一&#xff1a;使用iMazing传输 推荐度★★★★★ 有了i…
阅读更多...
不断优化的素数算法

不断优化的素数算法

前言&#xff1a;素数判断是算法中重要的一环&#xff0c;掌握优秀的素数判断方法是算法player的必修课。本文介绍的是由简到繁的素数算法&#xff0c;便于初学者从入门到精通。 素数&#xff08;质数&#xff09;&#xff1a;只能被 1 和它本身整除的数称作素数&#xff0c;如…
阅读更多...
overleaf在线编辑工具使用教程

overleaf在线编辑工具使用教程

文章目录 1 用 orcid注册overleaf获取模板2 使用模板 1 用 orcid注册overleaf获取模板 通常来说&#xff0c;在期刊投稿网站information for author中找template 。下载压缩包后上传到over leaf中。 加入找不到官方模板&#xff0c;用overleaf中的 2 使用模板 .bib文件&…
阅读更多...
需求变化频繁的情况下，如何实施自动化测试

需求变化频繁的情况下，如何实施自动化测试

一.通常来说&#xff0c;具备以下3个主要条件才能开展自动化测试工作: 1.需求变动不频繁 自动化测试脚本变化的频率决定了自动化测试的维护成本。如果需求变动过于频繁&#xff0c;那么测试人员就需要根据变动的需求来不断地更新自动化测试用例&#xff0c;从而适应新的功能。…
阅读更多...
【Blender实景合成】会跳舞的神里绫华

【Blender实景合成】会跳舞的神里绫华

效果预览 本文将介绍Blender用于实景合成的工作流程。 先看效果&#xff1a; 神里绫华爬上了我的办公桌 模型和动作资源准备 角色模型 本次主要使用的是原神游戏中&#xff0c;神里绫华的角色模型&#xff0c;该模型米哈游在模之屋网站上进行开源。 下载地址&#xff1a;ht…
阅读更多...
react项目从webpack迁移到vite的解决方案

react项目从webpack迁移到vite的解决方案

虽然webpack是前端工程编译工具的王者&#xff0c;但是最近vite牛逼吹的震天响&#xff0c;说什么开发/生产打包速度甩webpack 100条街。不管是不是事实&#xff0c;总得尝试一下吧。 于是说干就干&#xff0c;在网上找了很多资料&#xff0c;终于搞定了&#xff0c;以下就是r…
阅读更多...
spark on hive

spark on hive

需要提前搭建好hive&#xff0c;并对hive进行配置。 1、将hive的配置文件添加到spark的目录下 cp $HIVE_HOME/conf/hive-site.xml $SPARK_HOME/conf2、开启hive的hivemetastore服务 提前创建好启动日志存放路径 mkdir $HIVE_HOME/logStart nohup /usr/local/lib/apache-hi…
阅读更多...
【AI视野·今日CV 计算机视觉论文速览 第262期】Fri, 6 Oct 2023

【AI视野·今日CV 计算机视觉论文速览 第262期】Fri, 6 Oct 2023

AI视野今日CS.CV 计算机视觉论文速览 Fri, 6 Oct 2023 Totally 73 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computer Vision Papers Improved Baselines with Visual Instruction Tuning Authors Haotian Liu, Chunyuan Li, Yuheng Li, Yong Jae Lee大型多模…
阅读更多...
多普勒频率相关内容介绍

多普勒频率相关内容介绍

图1 多普勒效应 1、径向速度 径向速度是作用于雷达或远离雷达的速度的一部分。 图2 不同的速度 2、喷气发动机调制 JEM是涡轮机的压缩机叶片的旋转的多普勒频率。 3、多普勒困境 最大无模糊范围需要尽可能低的PRF&#xff1b; 最大无模糊速度需要尽可能高的PRF&#xff1b…
阅读更多...
Labview 实战 99乘法表

Labview 实战 99乘法表

基于新手小白&#xff0c;使用Labview实现99乘法表&#xff0c;敢于发表自己的一点方法&#xff0c;还请各位大侠放过&#xff01; 如下&#xff1a; 运行效果如下&#xff1a; 思路为&#xff1a;将要显示出来的数据&#xff0c;全部转换为字符串形式&#xff0c;再塞入到数组…
阅读更多...
Suricata + Wireshark离线流量日志分析

Suricata + Wireshark离线流量日志分析

Suricata 环境搭建&#xff1a;基于Ubuntu坏境下的Suricata坏境搭建_奈何&#xff20;_&#xff20;的博客-CSDN博客 suricata&#xff1a;监控日志 wireshark:监控流量 同时使用需要降噪&#xff0c;因为规则有许多重叠 题目及要求我打包上传了&#xff0c;有需要的同学自…
阅读更多...
Vmware 静态网络配置

Vmware 静态网络配置

概述 仅主机模式&#xff08;VMware1&#xff09;&#xff1a;使用host-only的方式是不能和外界通信的&#xff0c;只能够和本机的物理网卡通信 桥接&#xff08;VMnet0&#xff09;&#xff1a;使用桥接的方式使得自己的虚拟机和自己的真实机网卡在同一个网段 NAT&#xff0…
阅读更多...
Tensorflow2 GPU 安装方法

Tensorflow2 GPU 安装方法

一、Tensorflow2 GPU 安装方法 1. 首先安装Anaconda3环境2. 在Anaconda Prompt 中安装tensorflow23. 验证GPU是否可以使用4. 错误解决 1. 首先安装Anaconda3环境 https://www.anaconda.com/ 2. 在Anaconda Prompt 中安装tensorflow2 conda update conda conda create -n ten…
阅读更多...
【Linux学习】05-2Linux上部署项目

【Linux学习】05-2Linux上部署项目

Linux&#xff08;B站黑马&#xff09;学习笔记 01Linux初识与安装 02Linux基础命令 03Linux用户和权限 04Linux实用操作 05-1Linux上安装部署各类软件 05-2Linux上部署项目 文章目录 Linux&#xff08;B站黑马&#xff09;学习笔记前言05-2Linux上部署项目部署Springboot项目…
阅读更多...
【SpringBoot】多环境配置和启动

【SpringBoot】多环境配置和启动

环境分类&#xff0c;可以分为 本地环境、测试环境、生产环境等&#xff0c;通过对不同环境配置内容&#xff0c;来实现对不同环境做不同的事情。 SpringBoot 项目&#xff0c;通过 application-xxx.yml 添加不同的后缀来区分配置文件&#xff0c;启动时候通过后缀启动即可。 …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023