如何在未排序数组中搜索、插入和删除

2025年3月17日 | 阅读 7 分钟

本文讨论了一个在未排序数组上执行搜索、插入和删除操作的代码。

搜索操作

对于未排序数组，搜索操作可以通过从第一个元素到最后一个元素的线性遍历来完成。

How to Search, Insert, and Delete in an Unsorted Array

搜索操作的编程实现

C 语言

#include <stdio.h>
int findElement(int array[], int n, int key)
{
	int i;
	for (i = 0; i < n; i++)
		if (array[i] == key)
			return i;
	
	return -1;
}
int main()
{
	int array[] = { 22, 24, 30, 16, 35 };
	int n = sizeof(array) / sizeof(array[0]);

	int key = 16;

	int position = findElement(array, n, key);

	if (position == -1)
		printf("Element not found");
	else
		printf("Element Found at Position: %d",
			position + 1);

	return 0;
}

输出

Element Found at Position: 4

C++ 程序

#include <bits/stdc++.h>
using namespace std;
int findElement(int array[], int n, int key)
{
	int i;
	for (i = 0; i < n; i++)
		if (array[i] == key)
			return i;
	
	return -1;
}

int main()
{
	int array[] = { 22, 24, 30, 16, 35 };
	int n = sizeof(array) / sizeof(array[0]);

	int key = 16;

	int position = findElement(array, n, key);

	if (position == -1)
		cout << "Element not found";
	else
		cout << "Element Found at Position: "
			<< position + 1;

	return 0;
}

输出

Element Found at Position: 4

Java

class Main {
	static int findElement(int array[], int n, int key)
	{
		for (int i = 0; i < n; i++)
			if (array[i] == key)
				return i;
		return -1;
	}
	public static void main(String args[])
	{
		int array[] = { 22, 24, 30, 16, 35 };
		int n = array.length;

		int key = 16;
	
		int position = findElement(array, n, key);

		if (position == -1)
			System.out.println("Element not found");
		else
			System.out.println("Element Found at Position: "
							+ (position + 1));
	}
}

输出

Element Found at Position: 4

时间复杂度为 O(N)。
辅助空间将为 O(1)。

插入操作

1. 插入到末尾

在未排序数组中，插入操作比在已排序数组中更快，因为我们不必担心插入元素的具体位置。

插入操作的编程实现

C 语言

#include <stdio.h>

int insertSorted(int array[], int n, int key, int capacity)
{
	if (n >= capacity)
		return n;

	array[n] = key;

	return (n + 1);
}

int main()
{
	int array[20] = { 22, 26, 30, 50, 60, 80 };
	int capacity = sizeof(array) / sizeof(array[0]);
	int n = 6;
	int i, key = 34;

	printf("\n Before Insertion: ");
	for (i = 0; i < n; i++)
		printf("%d ", array[i]);

	n = insertSorted(array, n, key, capacity);

	printf("\n After Insertion: ");
	for (i = 0; i < n; i++)
		printf("%d ", array[i]);

	return 0;
}

输出

Before Insertion: 22 26 30 50 60 80 
 After Insertion: 22 26 30 50 60 80 34

C++ 程序

#include <bits/stdc++.h>
using namespace std;
int insertSorted(int array[], int n, int key, int capacity)
{
	if (n >= capacity)
		return n;

	array[n] = key;

	return (n + 1);
}

int main()
{
	int array[20] = { 22, 26, 30, 50, 60, 80 };
	int capacity = sizeof(array) / sizeof(array[0]);
	int n = 6;
	int i, key = 34;

	cout << "\n Before Insertion: ";
	for (i = 0; i < n; i++)
		cout << array[i] << " ";

	n = insertSorted(array, n, key, capacity);

	cout << "\n After Insertion: ";
	for (i = 0; i < n; i++)
	cout << array[i] << " ";

	return 0;
}

输出

Before Insertion: 22 26 30 50 60 80 
 After Insertion: 22 26 30 50 60 80 34

Java

class Main {
	static int insertSorted(int array[], int n, int key,
							int capacity)
	{
		if (n >= capacity)
			return n;

		array[n] = key;

		return (n + 1);
	}

	public static void main(String[] args)
	{
		int[] array = new int[20];
		array[0] = 22;
		array[1] = 26;
		array[2] = 30;
		array[3] = 50;
		array[4] = 60;
		array[5] = 80;
		int capacity = 20;
		int n = 6;
		int i, key = 34;

		System.out.print("Before Insertion: ");
		for (i = 0; i < n; i++)
			System.out.print(array[i] + " ");

		n = insertSorted(array, n, key, capacity);

		System.out.print("\n After Insertion: ");
		for (i = 0; i < n; i++)
			System.out.print(array[i] + " ");
	}
}

输出

Before Insertion: 22 26 30 50 60 80 
 After Insertion: 22 26 30 50 60 80 34

时间复杂度为 O(1)。
辅助空间将为 O(1)。

2. 插入到任意位置

通过将目标位置右侧的元素向右移动，可以在数组中的任意位置执行插入操作。

插入操作的编程实现

C 语言

#include <stdio.h>

void insertElement(int array[], int n, int x, int pos)
{
	for (int i = n - 1; i >= pos; i--)
		array[i + 1] = array[i];

	array[pos] = x;
}
int main()
{
	int array[15] = { 1, 3, 5, 7, 4 };
	int n = 5;

	printf("Before insertion : ");
	for (int i = 0; i < n; i++)
		printf("%d ", array[i]);

	printf("\n");

	int x = 9, pos = 3;

	insertElement(array, n, x, pos);
	n++;

	printf("After insertion : ");
	for (int i = 0; i < n; i++)
		printf("%d ", array[i]);

	return 0;
}

输出

Before insertion : 1 3 5 7 4 
After insertion : 1 3 5 9 7 4

C++ 程序

#include <bits/stdc++.h>
using namespace std;

void insertElement(int array[], int n, int x, int pos)
{
	for (int i = n - 1; i >= pos; i--)
		array[i + 1] = array[i];

	array[pos] = x;
}

int main()
{
	int array[15] = { 1, 3, 5, 7, 4 };
	int n = 5;

	cout << "Before insertion : ";
	for (int i = 0; i < n; i++)
		cout << array[i] << " ";

	cout << endl;

	int x = 9, pos = 3;

	insertElement(array, n, x, pos);
	n++;

	cout << "After insertion : ";
	for (int i = 0; i < n; i++)
		cout << array[i] << " ";

	return 0;
}

输出

Before insertion : 1 3 5 7 4 
After insertion : 1 3 5 9 7 4

Java

import java.io.*;

class JTP {
	static void insertElement(int array[], int n, int x,
							int pos)
	{
		for (int i = n - 1; i >= pos; i--)
			array[i + 1] = array[i];
		array[pos] = x;
	}
	public static void main(String[] args)
	{
		int array[] = new int[15];
		array[0] = 1;
		array[1] = 3;
		array[2] = 5;
		array[3] = 7;
		array[4] = 4;
		int n = 5;
		int x =9, pos = 3;

		System.out.print("Before Insertion: ");
		for (int i = 0; i < n; i++)
			System.out.print(array[i] + " ");

		insertElement(array, n, x, pos);
		n += 1;

		System.out.print("\n\nAfter Insertion: ");
		for (int i = 0; i < n; i++)
			System.out.print(array[i] + " ");
	}
}

输出

Before insertion : 1 3 5 7 4 
After insertion : 1 3 5 9 7 4

时间复杂度为 O(N)。
辅助空间将为 O(1)。

删除操作

通过线性搜索找到要删除的元素，然后执行删除操作，并重新定位元素。

删除操作的编程实现

C 语言

#include <stdio.h>

int findElement(int array[], int n, int key);

int deleteElement(int array[], int n, int key)
{
	int pos = findElement(array, n, key);

	if (pos == -1) {
		printf("Element not found");
		return n;
	}

	int i;
	for (i = pos; i < n - 1; i++)
		array[i] = array[i + 1];

	return n - 1;
}
int findElement(int array[], int n, int key)
{
	int i;
	for (i = 0; i < n; i++)
		if (array[i] == key)
			return i;

	return -1;
}

int main()
{
	int i;
	int array[] = { 20, 60, 40, 50, 30 };

	int n = sizeof(array) / sizeof(array[0]);
	int key = 40;

	printf("Array before deletion\n");
	for (i = 0; i < n; i++)
		printf("%d ", array[i]);
	
	n = deleteElement(array, n, key);

	printf("\nArray after deletion\n");
	for (i = 0; i < n; i++)
		printf("%d ", array[i]);

	return 0;
}

输出

Array before deletion
20 60 40 50 30 
Array after deletion
20 60 50 30

C++ 程序

#include <iostream>
using namespace std;

int findElement(int array[], int n, int key);

int deleteElement(int array[], int n, int key)
{
	int pos = findElement(array, n, key);

	if (pos == -1) {
		cout << "Element not found";
		return n;
	}

	int i;
	for (i = pos; i < n - 1; i++)
		array[i] = array[i + 1];

	return n - 1;
}

int findElement(int array[], int n, int key)
{
	int i;
	for (i = 0; i < n; i++)
		if (array[i] == key)
			return i;

	return -1;
}
int main()
{
	int i;
	int array[] = { 20, 60, 40, 50, 30 };

	int n = sizeof(array) / sizeof(array[0]);
	int key = 40;

	cout << "Array before deletion\n";
	for (i = 0; i < n; i++)
		cout << array[i] << " ";
	
	n = deleteElement(array, n, key);

	cout << "\n\nArray after deletion\n";
	for (i = 0; i < n; i++)
		cout << array[i] << " ";

	return 0;
}

输出

Array before deletion
20 60 40 50 30 
Array after deletion
20 60 50 30

Java

class Main {
	static int findElement(int array[], int n, int key)
	{
		int i;
		for (i = 0; i < n; i++)
			if (array[i] == key)
				return i;

		return -1;
	}
	static int deleteElement(int array[], int n, int key)
	{
		int pos = findElement(array, n, key);

		if (pos == -1) {
			System.out.println("Element not found");
			return n;
		}
		int i;
		for (i = pos; i < n - 1; i++)
			array[i] = array[i + 1];

		return n - 1;
	}
	public static void main(String args[])
	{
		int i;
		int array[] = { 20, 60, 40, 50, 30 };

		int n = array.length;
		int key = 40;

		System.out.println("Array before deletion");
		for (i = 0; i < n; i++)
			System.out.print(array[i] + " ");
		
		n = deleteElement(array, n, key);

		System.out.println("\n\nArray after deletion");
		for (i = 0; i < n; i++)
			System.out.print(array[i] + " ");
	}
}

输出

Array before deletion
20 60 40 50 30 
Array after deletion
20 60 50 30

时间复杂度为 O(N)。
辅助空间将为 O(1)。

下一个主题计算二叉树的非叶子节点

如何在未排序数组中搜索、插入和删除

搜索操作

插入操作

1. 插入到末尾

2. 插入到任意位置

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

如何在未排序数组中搜索、插入和删除

搜索操作

插入操作

1. 插入到末尾

2. 插入到任意位置

相关帖子

数据结构中的栈操作

循环排序

k 路归并排序

二叉树的高度

检测有向图中的循环

B 树可视化

从二叉搜索树中删除所有叶子节点

JavaT 村的水收集距离最小化

Recaman 序列

打印字符串中的所有不同字符

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器