C++实现有序表 |21xrx.com

C++实现有序表

2023-07-03 02:12:36 深夜i 30 0

C++ 有序表实现

有序表是一种基于二分查找算法的数据结构，它可以快速地查找和插入数据。在C++中，我们可以使用STL中的set或者map来实现有序表。

set是一种基于红黑树实现的有序表，其元素按照从小到大的顺序排列。我们可以通过以下代码来定义一个set，其中的compare函数指定了元素的排序方式：

#include<set>
using namespace std;
bool compare(int a, int b)
  return a < b;
set<int, bool(*)(int,int)> myset(compare);

上面的代码定义了一个包含整型元素的set，并指定了元素的排序方式为从小到大。其中第二个参数为一个函数指针，用于指定元素的比较规则。

我们可以通过以下代码向set中插入元素：

myset.insert(3);
myset.insert(5);
myset.insert(2);

上面的代码向set中插入了三个元素，分别为3、5、2。由于元素的排序方式为从小到大，因此插入的顺序不会影响元素的最终排列。

我们可以通过以下代码从set中查找元素：

set<int>::iterator it;
it = myset.find(3);
if(it != myset.end())
  cout << "3 is in the set." << endl;
else
  cout << "3 is not in the set." << endl;

上面的代码从set中查找值为3的元素，如果找到了则输出“3 is in the set.”，否则输出“3 is not in the set.”。可以看出，在set中使用二分查找算法查找元素非常容易。

map是一种基于红黑树实现的有序表，其中的元素由键值对组成。我们可以通过以下代码来定义一个map：

#include<map>
using namespace std;
bool compare(string a, string b)
  return a < b;
map<string,int, bool(*)(string,string)> mymap(compare);

上面的代码定义了一个包含string类型键和int类型值的map，并指定了键的排序方式为从小到大。其中第三个参数为一个函数指针，用于指定键的比较规则。

我们可以通过以下代码向map中插入元素：

mymap["apple"] = 10;
mymap["banana"] = 20;
mymap["orange"] = 30;

上面的代码向map中插入了三个键值对，分别为“apple”和10、“banana”和20、“orange”和30。由于键的排序方式为从小到大，因此插入的顺序不会影响键的最终排列。

我们可以通过以下代码从map中查找元素：

map<string,int>::iterator it;
it = mymap.find("apple");
if(it != mymap.end())
  cout << "apple: " << it->second << endl;
else
  cout << "apple is not in the map." << endl;

上面的代码从map中查找键为“apple”的元素，如果找到了则输出“apple: 10”，否则输出“apple is not in the map.”。可以看出，在map中使用二分查找算法查找元素非常容易。

总之，使用set或map可以非常方便地实现有序表，而二分查找算法也可以快速地对元素进行查找。在实际编程中，我们可以根据具体需求选择适合的方法来实现有序表，以提高程序的效率和可读性。

上一篇: idea打包java可执行jar包

下一篇: C++颜色代码表

评论区

相似文章