查找元素x,若x存在,则与其后继交换,否则将x插入,使顺序表有序

2024-05-01 09:32

本文主要是介绍查找元素x,若x存在,则与其后继交换,否则将x插入,使顺序表有序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

#include<stdio.h>
#define LIST_INIT_SIZE 6
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct{ElemType *elem;int length;int listsize;
}SqList;void InitSqList(SqList *L);//初始化顺序表
void CreateSqList(SqList *L, ElemType *arr, int n);//给予顺序表初始数据
void ShowSqList(SqList *L);//输出顺序表数据//二分法查找x,找到则返回元素索引,找不到则返回不大于x的最大元素索引的相反数
int SearchByElem(SqList *L, ElemType x);
//第i个数据之前插入x
void InsertByIndex(SqList *L, int i, ElemType x);
//交换数据值
void swap(ElemType *x, ElemType *y);
//查找元素x,若x存在,则与其后继交换,否则将x插入,使顺序表有序
void SearchSwapInsert(SqList *L, ElemType x);int main()
{SqList L;ElemType arr[6] = { 1, 2, 3, 5, 7, 6 };InitSqList(&L);CreateSqList(&L, arr, 6);printf("初始数据列表:");ShowSqList(&L);printf("\n");printf("执行查找交换插入算法,数据为:%d\n",7);SearchSwapInsert(&L, 7);ShowSqList(&L);printf("执行查找交换插入算法,数据为:%d\n", 4);SearchSwapInsert(&L, 4);ShowSqList(&L);getchar();return 0;
}void InitSqList(SqList *L)
{L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));L->length = 0;L->listsize = LIST_INIT_SIZE;
}void CreateSqList(SqList *L, ElemType *arr, int n)
{int i;if (n <= LIST_INIT_SIZE){for (i = 0; i < n; i++){L->elem[i] = arr[i];}L->length = n;}else{printf("插入失败,数据个数应不大于 %d", LIST_INIT_SIZE);}
}void ShowSqList(SqList *L)
{int i;for (int i = 0; i < L->length; i++){printf(" %d ", L->elem[i]);}printf("\n");
}//二分法查找x,找到则返回元素索引,找不到则返回不大于x的最大元素索引
int SearchByElem(SqList *L, ElemType x)
{int high = L->length - 1;int low = 0;int mid;while (low <= high){mid = (high + low) / 2;if (L->elem[mid] == x){return mid;}else if (x < L->elem[mid]){high = mid - 1;}else{low = mid + 1;}}//high为小于x元素集合中的最大值的索引return -high;
}//第i个数据之前插入x
void InsertByIndex(SqList *L, int i, ElemType x)
{if (i<1||i>L->length+1){printf("位置不合法,插入失败!");return;}if (L->length >= L->listsize){ElemType *enew = (ElemType *)realloc(L->elem, (LISTINCREMENT + L->listsize) * sizeof(ElemType));L->elem = enew;L->listsize += LISTINCREMENT;}ElemType *p = &(L->elem[i - 1]);//待插入的位置ElemType *q = &(L->elem[L->length - 1]);//q指向最后一个元素for (; p <= q; q--){*(q + 1) = *q;}*p = x;L->length++;
}void swap(ElemType *x, ElemType *y)
{ElemType t = *y;*y = *x;*x = t;
}void SearchSwapInsert(SqList *L, ElemType x)
{int k;if ((k = SearchByElem(L, x)) >= 0){swap(&(L->elem[k]), &(L->elem[k + 1]));}else{InsertByIndex(L, -k + 2, x);}
}

这篇关于查找元素x,若x存在,则与其后继交换,否则将x插入,使顺序表有序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/951327

相关文章

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Jmeter如何向数据库批量插入数据

《Jmeter如何向数据库批量插入数据》:本文主要介绍Jmeter如何向数据库批量插入数据方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Jmeter向数据库批量插入数据Jmeter向mysql数据库中插入数据的入门操作接下来做一下各个元件的配置总结Jmete

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定