技术标签: 线性表 常见算法与数据结构实现 数据结构
今天是单链表的实现,主要实现函数如下:
/*
Project: single linkeed list (数据结构 单链表)
Date: 2018/09/14
Author: Frank Yu
InitList(LinkList &L) 参数:单链表L 功能:初始化 时间复杂度 O(1)
ListLength(LinkList L) 参数:单链表L 功能:获得单链表长度 时间复杂度O(n)
ListInsert(LinkList &L,int i,ElemType e) 参数:单链表L,位置i,元素e 功能:位置i后插 时间复杂度O(n)[加入了查找]
若已知指针p指向的后插 O(1)
ListDelete(LinkList &L,int i) 参数:单链表L,位置i 功能:删除位置i元素 时间复杂度O(n)[加入了查找]
若已知p指针指向的删除 最好是O(1),因为可以与后继结点交换数据域,然后删除后继结点。
最坏是O(n),即从头查找p之前的结点,然后删除p所指结点
LocateElem(LinkList L,ElemType e) 参数:单链表L,元素e 功能:查找第一个等于e的元素,返回指针 时间复杂度O(n)
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define Status int
#define ElemType int
//单链表结点数据结构
typedef struct LNode
{
ElemType data;//数据域
struct LNode *next;//指针域
}LNode,*LinkList;
//**************************基本操作函数***************************//
//初始化函数
Status InitList(LinkList &L)
{
L = new LNode;//生成头结点 这样删除等操作就不必分第一个结点和其他了
L->next = NULL;
return 1;
}
//获取单链表长度 头结点无数据,不算
int ListLength(LinkList L)
{
LinkList p=L;int sum=0;
while(p)
{
sum++;
p=p->next;
}
return sum-1;//去除头结点
}
//插入函数--后插法 插入到第i(1<=i<=length+1)个位置 即i-1之后 不必区分i的位置
bool ListInsert(LinkList &L,int i,ElemType e)
{
LNode* s;LinkList p=L;int j=0;
while(p&&(j<i-1))//j指到i-1位置或者p已经到最后时跳出
{
p=p->next;
++j;
}
if(!p||j>i-1)//i<1或者i>ListLength(L)+1时,插入位置无效 不调用ListLength,提高效率
{
printf("插入位置无效!!!\n");
return false;
}
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
//删除函数 删除位置i的结点 即删除i-1之后的结点
bool ListDelete(LinkList &L,int i)
{
LNode* s;LinkList p=L;int j=0;
LinkList q;
while(p&&(j<i-1))//j指到i-1位置
{
p=p->next;
++j;
}
if (p==nullptr||!(p->next) || j>i - 1)//i<1或者i>ListLength(L)时,删除位置无效
{
printf("删除位置无效!!!\n");
return false;
}
q=p->next;
p->next=q->next;
free(q);//释放空间
return true;
}
//查找函数 按值查找 查找第一个等于e的结点 成功返回该结点指针,否则返回NULL
LNode *LocateElem(LinkList L,ElemType e)
{
LNode *p=L;
while(p&&(p->data!=e))
{
p=p->next;
}
return p;
}
//**************************功能实现函数**************************//
//遍历输出函数
void PrintList(LinkList L)
{
LinkList p=L->next;//跳过头结点
if(ListLength(L))
{
printf("当前单链表所有元素:");
while(p)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
else
{
printf("当前单链表已空!\n");
}
}
//插入功能函数 调用ListInsert后插
void Insert(LinkList &L)
{
int place;ElemType e;bool flag;
printf("请输入要插入的位置(从1开始)及元素:\n");
scanf("%d%d",&place,&e);
flag=ListInsert(L,place,e);
if(flag)
{
printf("插入成功!!!\n");
PrintList(L);
}
}
//删除功能函数 调用ListDelete删除
void Delete(LinkList L)
{
int place;bool flag;
printf("请输入要删除的位置(从1开始):\n");
scanf("%d",&place);
flag=ListDelete(L,place);
if(flag)
{
printf("删除成功!!!\n");
PrintList(L);
}
}
//查找功能函数 调用LocateElem查找
void Search(LinkList L)
{
ElemType e;LNode *q;
printf("请输入要查找的值:\n");
scanf("%d",&e);
q=LocateElem(L,e);
if(q)
{
printf("找到该元素!\n");
}
else
printf("未找到该元素!\n");
}
//菜单
void menu()
{
printf("********1.后插 2.删除*********\n");
printf("********3.查找 4.输出*********\n");
printf("********5.退出 *********\n");
}
//主函数
int main()
{
LinkList L;int choice;
InitList(L);
while(1)
{
menu();
printf("请输入菜单序号:\n");
scanf("%d",&choice);
if(choice==5) break;
switch(choice)
{
case 1:Insert(L);break;
case 2:Delete(L);break;
case 3:Search(L);break;
case 4:PrintList(L);break;
default:printf("输入错误!!!\n");
}
}
return 0;
}
--------------------------20210216更新--------------------------
感谢评论区的@瓦系大便超人,详细的指出了bug的触发方式、位置及解决办法,是一位很棒的读者,祝牛年大吉,编程无bug!!!
--------------------------20210216更新--------------------------
更多数据结构实现:数据结构严蔚敏版的实现
有问题请下方评论,转载请注明出处,并附有原文链接,谢谢!如有侵权,请及时联系。
文章浏览阅读7.5k次,点赞2次,收藏21次。如何设置VB.NET 窗体的全局热键(快捷键),_vb.net 中窗体快捷键如何设置为alt+p
文章浏览阅读9.8k次。本文测试安装的是32位的ubuntu-14.10-desktop-i386.iso 系统。准备: Ubuntu系统ISO文件。官网或者学校的镜像源可下。 UltraISO 软件。 Google 搜一下,可用试用版就行。主要用于从ISO文件里提取文件。 EasyBCD 软件。 Google 一下。Step 1. 计算机右键,管理,_win7无u盘安装ubuntu18.04
文章浏览阅读6.6k次,点赞18次,收藏80次。文章目录介绍PHP命令执行函数代码执行函数命令拼接符命令执行的一些绕过技巧绕过str_replace()函数空格被过滤的绕过用编码来绕过URL编码绕过Base64编码绕过Hex编码绕过Oct编码绕过:偶读拼接绕过(黑名单绕过)花括号{command,}的别样用法无回显的命令执行方法一:反弹shell方法二:msf反向回连利用RCE反弹Shellnetcat 一句话反弹Shellbash反弹shel..._rec 远程
文章浏览阅读211次。Ivan likes to learn different things about numbers, but he is especially interested in really big numbers. Ivan thinks that a positive integer number x is really big if the difference between x and th..._codeforces 817c
文章浏览阅读3.6k次。因为毕业设计的缘故,必须学习mininet(一种基于Linux内核,由python语言编写的虚拟SDN网络平台),来实现多种路由规则分配算法的仿真。然而,在学习过程中,我算是遇到了各种各样的障碍,甚是苦恼。好在mininet官方做的tutorial足够丰富,google也很给力,所以许多问题都可以查到该如何解决。今天,作死的Windows10系统在我上厕所的过程_找不到/etc/network/interfaces' mininet
文章浏览阅读3.4k次。在生产环境中使用Hive,强烈建议使用HiveServer2来提供服务,好处很多:1. 在应用端不用部署Hadoop和Hive客户端;2. 相比hive-cli方式,HiveServer2不用直接将HDFS和Metastore暴漏给用户;3. 有安全认证机制,并且支持自定义权限校验;4. 有HA机制,解决应用端的并发和负载均衡问题;5. JDBC方式,可以使用任何语言,方便与应_hiveserver2连接zookeeper用zookeeper账户
文章浏览阅读675次。会议将围绕“能源、电力与电气工程”的最新研究领域而展开,为研究人员、工程师、专家学者以及行业专业人士提供一个交流与探讨最新研究成果的平台,并为与会者们交流新的思想和应用经验建立业务或研究关系。本次会议将于2023年11月22至24日在澳大利亚墨尔本召开,在会议期间您将有机会聆听到行业前沿的学术报告,见证该领域的成果与进步。5. 至少有一位论文作者应注册参会,并且至少有一位作者必须在会议上发表论文。5.文章录用:若您的文章被录用,我们将以邮件形式通知您,您将收到以下文件:录用通知、审稿意见表、中文注册表。_coeepe 2023
文章浏览阅读477次,点赞7次,收藏6次。1.什么是全自动采集文章php?全自动采集文章php是一款优秀的基于PHP的软件,它能智能提取并储存互联网文章至数据库中,极大地减轻了用户获取大量信息的负担,更有效率地利用了您宝贵的时光与精力。2.如何使用全自动采集文章php?运用PHP全自动采集文章只需三步。首先
文章浏览阅读1.3k次。rose.png你应该注意到了,在项目结构上我们有静态资源两个目录:src/assets和static/。他们之间有什么区别?通过webpack处理的资源首先我们需要了解webpack如何处理静态资源。在*.vue组件中,所有的html模板和css都会被vue-html-loader和css-loader压缩并且查找资源路径。例如,(../logo.png)和background:url(../l..._vue2 webpack项目 static
文章浏览阅读2.5k次。Glide实现加载网络图片Glide,一个被google所推荐的图片加载库作者是Bump Technologies这个库被广泛运用在google的开源项目中,包括2014年的google I/O大会上发布的官方app加载图片的步骤图片的地址把图片转换为可被加载的对象通过图片加载控件展示图片使用流程.with() 创建图片加载实例.load() 指定加载的图片资源.into() 指定图片的加载控件Generated API继承库可以为Generated API扩展自定义_glide加载网络图片
文章浏览阅读300次,点赞5次,收藏7次。1.背景介绍机器学习是一种通过从数据中学习泛化规则的方法,以解决复杂问题的计算机科学领域。在过去的几年里,机器学习已经取得了显著的进展,成为许多领域的核心技术,如图像识别、自然语言处理、推荐系统等。然而,随着数据规模和复杂性的增加,传统的机器学习算法在处理这些挑战时面临着困难。因此,研究人员在寻求更有效的算法和方法来解决这些问题时,发展了次梯度取值(Second-order Taylor ex...
文章浏览阅读812次。以全国各城市空气质量年度数据为例。分别应用系统聚类算法和K均值聚类法对数据进行分析。_r形聚类法代码