一、查找和排序
1.排序
sort()函數
頭檔案:<algorithm>
sort(begin,end,com),com參數可以沒有,預設為升序
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
int a[5]={1,3,4,2,5};
sort(a,a+5);
for(int i=0;i<5;i++)
cout<<a[i]<<' ';
return 0;
}
注意:參數的begin和end為位址,如對數組data[6]的排序為
sort(data,data+6)//預設升序排序
sort(data,data+6,greater<int>())//降序排序
二級排序(如結構體)
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct link
{
int a,b;
};
bool cmp(link x,link y)
{
if(x.a==y.a)
return x.b>y.b;
return x.a>y.a;
}
int main()
{
link x[4];
for(int i=0;i<4;i++)
cin>>x[i].a>>x[i].b;
sort(x,x+4,cmp);
for(int i=0;i<4;i++)
cout<<x[i].a<<' '<<x[i].b<<endl;
return 0;
}
需要自己寫com函數,bool類型。com()函數工作原理是,如果傳回值是0則互換位置,傳回值是1位置不變。
或者使用functional裡面的函數。functional提供了一堆基于模闆的比較函數對象。
equal_to<Type>、not_equal_to<Type>、greater<Type>、greater_equal<Type>、less<Type>、less_equal<Type>
參考:C++中SORT函數使用方法
2.查找
線性查找、二分查找
binary_search()函數
頭檔案:<algorithm>
binary_search(begin,end,target),注意:begin和end為被查數組的位址,要求數組元素非遞減
二分查找代碼
bool BinarySearch(int n,int target)
{
int left = 0;
int right = n - 1;
while(left <= right)
{
int middle = (left + right) / 2;
if(data[middle] < target)
left = middle + 1;
else if(data[middle] > target)
right = middle - 1;
else
return true;
}
return false;
}
參考:C++ STL中的Binary search(二分查找)
二、字元串
C++資料類型字元串string
庫: <string>
初始化:
輸入:
string str;
cin >> str;
可以用字元串常量初始化
string str = "hello";
元素通路:可以采用已經重載好的運算符[index]通路或者str.at(index)
操作符:可以用 ==、>、<、>=、<=、和!=比較字元串,可以用+或者+=操作符連接配接兩個字元串,并且可以用[]擷取特定的字元
函數:
字元串操作 | |
---|---|
size() | 傳回字元串長度,有幾個字元(不包括\0) |
length() | 和size()功能基本相同 |
insert(int index,string s) | 從下表index開始,插入字元串s |
erase(int index,int length) | 從index開始,删除length個字元 |
erase(int index) | 删除index後面所有的東西(保留index上的,從1計數) |
clear() | 清空字元串 |
字元串查找 | |
find("string substring") | 找到傳回其下标(多個傳回第一次出現的位置),找不到傳回string::npos |
substr(int index1,int index2) | 傳回一個子串string,從下标index1到index2的字元串,從0計數,深拷貝 |
swap(string s) | s1.swap(s2),字元串的内容交換 |
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int main()
{
string str = "hello world hello world";
cout << str << endl;
int found = str.find("world");//尋找有的,多個的
printf("world found at %d\n",found);
found = str.find("123");//尋找沒有的
printf("123 found at %d",found);
return 0;
}
輸出:
hello world hello world
world found at 6
123 found at -1
三、資料結構——向量(vector)
vector是可以改變大小的線性序列容器。和數組一樣,向量使用連續的空間存儲元素,也可以使用下表通路元素,但是向量的大小可以動态變化。在vector内部實作中,使用動态的數組配置設定存儲元素,重新配置設定數組時需要将原來所有的元素重新配置設定,移動到新數組中。對于預先不知道數組開多大的情況,可以使用vector。
頭檔案:<vector>
定義:vector<typename> name
常用方法:
狀态 | |
empty() | 傳回是不是空的 |
size() | 傳回向量元素個數 |
添加或删除 | |
push_back() | 向尾部添加元素 |
pop_back() | 删除尾部元素 |
元素操作 | |
insert(index,num) | 指定位置index插入元素 |
inset(index,typesize,num) | 在index位置插入typesize個元素 |
元素通路 | |
begin() | 傳回第一個元素的位置 |
end() | 最後一個元素的位置 |
front() | 傳回a的第一個元素 |
back() | 傳回a的最後一個元素 |
可以使用疊代器通路
for(vector<int>::iterator it=c.begin();it<c.end();it++)
print("%d",*it)
三、資料結構——隊列
隊列(queue),隊列頭部删除,隊列尾删除
頭檔案:<queue>
定義:queue<typename> name
常用方法:
size() | 元素個數 |
empty() | 隊列是否空 |
push() | 隊尾入隊 |
pop() | 隊頭出隊 |
front() | 獲得隊頭元素 |
back() | 獲得隊尾元素 |
例題:
約瑟夫問題No.2
三、資料結構——棧
資料從一頭進,同一端出
頭檔案:<stack>
定義:stack<typename> name
方法:
size() | 傳回個數 |
empty() | 傳回是否空 |
push() | 添加新元素 |
pop() | 彈棧 |
top() | 隻能通過棧頂通路元素 |