怎么看公司网站是哪里做的,自己做购物网站推广,主机屋做网站视频,erp软件公司有哪些文章目录 6.线性表(下)(4).栈与队列的定义和ADT#1.ADT#2.栈的基本实现#3.队列的形式#4.队列的几种实现 (5).栈与队列的应用#1.栈的应用i.后缀表达式求值ii.中缀表达式转后缀表达式 #2.队列的应用 (6).线性表的其他存储方式#1.索引存储#2.哈希存储i.什么是哈希存储ii.碰撞了怎么… 文章目录 6.线性表(下)(4).栈与队列的定义和ADT#1.ADT#2.栈的基本实现#3.队列的形式#4.队列的几种实现 (5).栈与队列的应用#1.栈的应用i.后缀表达式求值ii.中缀表达式转后缀表达式 #2.队列的应用 (6).线性表的其他存储方式#1.索引存储#2.哈希存储i.什么是哈希存储ii.碰撞了怎么办iii.这个散列函数怎么设计呢 (7).查找#1.线性查找#2.二分查找 小结 6.线性表(下)
(4).栈与队列的定义和ADT
#1.ADT 上面说的链表和数组都是几乎没有限制的线性表结构接下来我们就提一提两种受限制的线性表结构——栈和队列它们的ADT是这样的 ADT Stack { 数据对象: D a i ∣ a i ∈ E l e m S e t , i 0 , 1 , 2 , . . . , n − 1 , n ≥ 0 D {a_i|a_i \in ElemSet, i0,1,2,...,n-1, n\ge0} Dai∣ai∈ElemSet,i0,1,2,...,n−1,n≥0 数据关系: R { a i − 1 , a i ∣ a i ∈ D , i 1 , 2 , . . . , n − 1 , n ≥ 0 } R \{a_{i-1},a_i|a_i \in D, i1,2,...,n-1, n \ge 0\} R{ai−1,ai∣ai∈D,i1,2,...,n−1,n≥0}, a n − 1 a_{n-1} an−1为栈顶 a 0 a_0 a0为栈底 基本操作: 初始化、进栈、出栈、取栈顶元素等 } ADT Queue { 数据对象: D { a i ∣ a i ∈ E l e m S e t , i 0 , 1 , . . . , n − 1 , n ≥ 0 } D \{a_i|a_i\in ElemSet, i 0, 1, ..., n-1, n\ge 0\} D{ai∣ai∈ElemSet,i0,1,...,n−1,n≥0} 数据关系: R { a i − 1 , a i ∣ a i − 1 , a i ∈ D , i 1 , 2 , . . . , n − 1 } R \{a_{i-1}, a_i|a_{i-1},a_i\in D, i 1,2,..., n-1\} R{ai−1,ai∣ai−1,ai∈D,i1,2,...,n−1}约定其中 a 1 a_1 a1端为队列头 a n a_n an端为队列尾 基本操作初始化、入队、出队、获得头元素、清空等 } #2.栈的基本实现 栈是一种后进先出(Last In First Out, LIFO) 的数据结构听起来你想实现一个基本的栈相当简单啊比如这就是个例子
#include cstringstruct stack
{int* _data;int _capacity;int _top;stack(): _data(nullptr), _capacity(0), _top(0) {}stack(const int _cap): _data(new int[_cap] {0}), _capacity(_cap), _top(0) {}stack(const stack s): _data(new int[_capacity] {0}), _capacity(s._capacity), _top(s._top){memcpy(_data, s._data, _top * sizeof(int));}~stack(){delete[] _data;_data nullptr;}bool empty() const{return (_top 0);}void push(const int val){if (_top _capacity) {_data[_top] val;}else {std::cout Stack Full! std::endl;}}int pop(){if (!empty()) {int rt{ _data[--_top] };return rt;}else {std::cout Stack Empty! std::endl;return -1;}}int top() const{if (!empty()) {return _data[_top];}else {std::cout Stack Empty! std::endl;return -1;}}int size() const{return _top 1;}
};相当简单用一个很简单的数组就可以完成模拟了因为它的入和出操作都是在末尾因此不需要涉及到数据的频繁移动。
#3.队列的形式 但是队列可就不一样了队列是一种先进先出(First In First Out, FIFO) 的数据结构如果我们简单用一个数组来模拟那我们从数组的最后入队再从数组的头出队这样一次操作之后我们可能需要把后面所有的数字都往前移动一位这样的性能是很低的 因此基于数组的队列我们一般采取环形队列的思路来实现然后你会发现这个数据结构对于链式存储的线性表来说好像实现起来非常容易—因为我们不管是在头还是尾插入都不需要对后面的数据进行移动操作所以链式存储结构不仅可以实现队列还可以实现双端队列也就是在头和尾都可以进行入队、出队的队列。 还有一种则是优先队列它的出队顺序不是依照入队顺序来的它的顺序是依照我们预先对于数据的顺序进行出队例如我们按照整数大小作为优先顺序那么输入7, 10, 4, 8, 3, 2, 3, 9, 2, 6入队之后再依次出队的结果就是2, 2, 3, 3, 4, 6, 7, 8, 9, 10哇哦输出的顺序就变成有序了这就是一种排序了再偷偷告诉你这个排序算法的时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn) 那么这么好的队列我们要怎么实现呢我们只要用堆就可以实现了 所以我等会儿可以给你提供一段代码但我不会细讲具体的内容要等到后面的树篇才能讲到了。
#4.队列的几种实现 首先是顺序存储实现的循环队列
struct queue
{int* _data;int _capacity;int _size;int _head;queue(): _data(nullptr), _capacity(0), _size(0), _head(0) {}queue(const int capa): _data(new int[capa] {0}), _capacity(capa), _size(0), _head(0) {}queue(const queue q): _data(new int[q._capacity]), _capacity(q._capacity), _size(q._size), _head(q._head){memcpy(_data, q._data, _size * sizeof(int));}~queue(){delete[] _data;_data nullptr;}bool empty() const{return (_size 0);}void enqueue(const int val){if (_size _capacity) {_data[(_head _size) % _capacity] val;_size;}else {std::cout Queue Full! std::endl;}}int dequeue(){if (!empty()) {_size--;int rt{ _data[_head] };_head (_head 1) % _capacity;return rt;}else {std::cout Queue Empty! std::endl;return -1;}}int first() const{if (!empty()) {return _data[_head];}else {std::cout Queue Empty! std::endl;return -1;}}
};还算简单只是在计算访问和插入的下标时要注意使用取余来保证我们的数据是循环地存在整个数组当中的这样的做法可以有效避免多次数据的移动从而增加队列的效率不过这种队列还是有存储空间限制的有点讨厌用链式存储实现的队列一般来说就不会有这个问题。 然后是链式存储实现的队列/双端队列
struct deque
{list _data;int _size;deque(): _data(), _size(0) {}deque(const deque dq): _data(dq._data), _size(dq._size) {}~deque() default;bool empty() const{return (_size 0);}void push_front(const int val){_data.push_front(val);_size;}void push_back(const int val){_data.push_back(val);_size;}int pop_front(){if (!empty()) {int rt{ _data.front() };_data.pop_front();_size--;return rt;}else {std::cout Deque Empty! std::endl;return -1;}}int pop_back(){if (!empty()) {int rt{ _data.back() };_data.pop_back();_size--;return rt;}else {std::cout Deque Empty! std::endl;return -1;}}int back() const{if (!empty()) {return _data.back();}else {std::cout Deque Empty! std::endl;return -1;}}int front() const{if (!empty()) {return _data.front();}else {std::cout Deque Empty! std::endl;return -1;}}
};如果你的链表功能已经实现的很完全了那么这个双端队列的实现就要多简单有多简单了只要插插头、插插尾就可以了双端队列就是在头和尾都可以进行入队和出队的队列你想只实现一个正常的队列其实也是一样的把front的系列函数都去掉就好了。 最后是优先队列
templatetypename T
class heap
{// Small root heap
public:vectorT data;size_t size;heap(){size 0;}heap(vectorT nums){// 99 5 36 7 22 17 46 12 2 19 25 28 1 92this-data nums;this-size nums.size() - 1;for (size_t i size / 2; i 1; i--) {siftdown(i);}}void siftup(size_t i){bool check false;if (i 1) return;else {while (i ! 1 !check) {if (this-data[i] this-data[i / 2]) {T temp this-data[i / 2];this-data[i / 2] this-data[i];this-data[i] temp;i / 2;}else check true;}}return;}void siftdown(size_t i){bool check false;size_t t 0;while (i * 2 this-size !check) {if (this-data[i] this-data[i * 2]) {t i * 2;}else t i;if (i * 2 1 this-size) {if (this-data[t] this-data[i * 2 1]) {t i * 2 1;}}if (t ! i) {T temp this-data[t];this-data[t] this-data[i];this-data[i] temp;i t;}else {check true;}}return;}T deletemin(){T temp this-data[1];this-size--;this-data[1] this-data[this-size];siftdown(1);return temp;}void addElement(T num){this-data.push_back(num);this-size;siftup(this-size);}void heap_sort(){heapT h_temp{ *this };while (h_temp.size 1) {cout h_temp.deletemin() ;}cout endl;}bool empty(){if (this-size 0) return true;else return false;}templatetypename Ufriend ostream operator(ostream output, heapU h){size_t n 1;for (size_t i 1; i h.size; i) {output h.data[i] ;if (i n * 2 - 1) {output endl;n * 2;}}output endl;return output;}~heap(){this-data.~vector();this-size 0;}
};优先队列依靠的堆是一种完全二叉树在序号前一个节点未被填充的情况下后一个节点是不能被填充的因此用数组存这棵树不会有空间的浪费并且相较于采取二叉树一般的两个子节点的存法这种实现方法更加简单不过具体的等到我们的树篇再详细介绍吧。
(5).栈与队列的应用 说完了实现接下来就看看栈和队列有什么用吧。栈和队列实际上是对我们生活中的某些有固定存取顺序的问题的一个模拟数据类型例如栈就像堆在一起的盘子我们把盘子从下面一个个往上堆最先取出的只能是最上面的那个不然盘子塔就塌了这不好还有是队列这个更好说我们平时排队的时候就是这么做的人从最后进来然后从最前面出去中间需要进行排队等待。
#1.栈的应用 计算机内存的栈区实际上也是将内存依照栈的方式排布的对于我们来说有了栈的结构想要完成函数的相互调用就很容易了我们把一个函数所需要的参数、调用的基本指令占用的栈区的所有部分称为栈帧那么调用某个函数的过程就可以简单描述为传入参数、建立栈帧、调用指令处理数据、消去栈帧、回传数据这也支持了我们现在的编程语言的一般思路函数里调用另一个函数会暂停当前函数先继续完成被调用函数直到调用链到头再开始回溯。 这也保证了我们C中的Stack Unwinding流程可以顺利进行Stack Unwinding是C的遇到异常时会进行的自动释放资源的一套流程这保障了RAII机制的稳定运行。
i.后缀表达式求值 好了好了扯远了有一些比较经典的问题可以用栈来解决在这里我们举一个后缀表达式求值的例子它的基本情况是这样的 我们常见的数学表达式是形如 ( 1 3 ) × 5 ÷ 6 41 × ( 2 451 ) (13)\times 5\div 641\times (2451) (13)×5÷641×(2451)这样的但是括号的出现以及运算符优先级带来了很多不确定性因此我们在计算机中习惯性地会采用前缀表达式或后缀表达式来表示数学表达式这里我们介绍一下后缀表达式的基本形式 n u m 1 n u m 2 o p num1 \ num2 \ op num1 num2 op如 3 4 3 \ 4 \ 3 4 12 41 / 12 \ 41 \ / 12 41 /这样的前面两个作为操作数后面的符号是要进行的运算符使用前缀或后缀表达式的好处就在于它们不需要括号可以表达优先级这样一来问题的处理会变得很简单 接下来你要尝试接收一个长度不超过100个字符的字符串其中存在若干个0~9之间的操作数以及若干操作符其中不会出现除以0或操作数对应失败等非法操作你要做的是求出这个后缀表达式的值整数计算。 乍一看你好像并不知道怎么操作这个东西但是你可以先试试算一下这个式子告诉我结果是多少 3 3 4 5 × × 6 − 9 4 ÷ 3\ 3\ 4\ 5\ \times\ \ \times\ 6\ -\ 9\ 4\div 3 3 4 5 × × 6 − 9 4÷算出来了吗结果是65计算过程是什么样的呢我们一步步看看
1.接收3、3、4、5直到遇到 × \times ×然后把4和5做一个乘法得到20再塞回去就是3、3、202.遇到 把3和20做一个加法得到23塞回去3、233.遇到 × \times ×把3和23做一个乘法得到69塞回去694.接下来继续接收6又遇到了-把69和6做一个减法得到63塞回去635.接下来接收9、4又遇到了 ÷ \div ÷把9和4做一个整除得到2塞回去63、26.最后接收到了 把63和2做一个加法得到65表达式结束结果就是65 所以我们的计算流程主要就是这么两步接收输入如果是数字就存一下如果是符号就取数字做计算、把计算结果存回去而且我们会发现取数字和存数字的顺序是后进先出的也就是说我们可以使用一个栈来存下这些数字所以我们就可以得到以下的代码
int calculate(const string RPN)
{stackint s;for (int i 0; i RPN.size(); i) {if (isdigit(RPN[i])) {s.push(RPN[i] - 0);}else {int num1{ 0 }, num2{ 0 };num2 s.top();s.pop();num1 s.top();s.pop();switch (RPN[i]) {case :s.push(num1 num2);break;case -:s.push(num1 - num2);break;case *:s.push(num1 * num2);break;case /:s.push(num1 / num2);break;}}}return s.top();
}输入的表达式中每个操作符和运算数之间没有多余的空格效果如下 很好效果和我们想的一样不过一般的表达式可能会更复杂包括包含超过1位的数字包含负号等这里给出一个更加完善的后缀表达式求解的函数
int calculate(const string RPN)
{stackint s;int temp{ 0 };bool num{ false };for (int i 0; i RPN.size(); i) {if (isdigit(RPN[i])) {temp * 10;temp RPN[i] - 0;num true;}else if (!isdigit(RPN[i])) {if (RPN[i] ) {if (num) {num false;s.push(temp);temp 0;}continue;}if (RPN[i] ~) {int num s.top();s.pop();s.push(-num);}else {int num1{ 0 }, num2{ 0 };num2 s.top();s.pop();num1 s.top();s.pop();if (RPN[i] ) s.push(num1 num2);else if (RPN[i] -) s.push(num1 - num2);else if (RPN[i] *) s.push(num1 * num2);else if (RPN[i] /) s.push(num1 / num2);}}}return s.top();
}这里用~表示负号主要是因为负号的出现可能导致后缀表达式出现二义性例如: − 3 − ( − 4 − 5 ) − ( − 5 ) ⇒ 3 − 4 − 5 − − 5 − − -3-(-4-5)-(-5) \Rightarrow 3-4-5--5-- −3−(−4−5)−(−5)⇒3−4−5−−5−−然后看看我们的解析流程这里声明一下如果从栈中只能获得一个数字那么把负号认为是单目的负号而不是减号
1.接收3遇到 − - −栈里只有一个数字操作把-3放回栈中2.接收4遇到 − - −栈里有-3, 4那么计算得到-7放回栈3.接收5遇到 − - −栈里有-7, 5那么计算得到-12放回栈4.遇到 − - −栈里只有一个数字操作把12放回栈中5.接收5遇到 − - −栈里有12, 5那么计算得到7放回栈6.遇到 − - −栈里只有一个数字操作把-7放回栈中读取结束结果为-7 你再看看这个结果对吗 − 3 − ( − 4 − 5 ) − ( − 5 ) -3-(-4-5)-(-5) −3−(−4−5)−(−5)的结果应该是11而不是-7因此单一的负号并不具备在后缀表达式中同时表达取负和减法两种功能的能力所以在这里我们用~来表示负号你可以自己尝试一下。
ii.中缀表达式转后缀表达式 还是回到前面的问题现在我们的问题不再是把这个表达式的值求出来了而是说我们平时用的都是中缀表达式让我把中缀表达式转后缀表达式还有点麻烦呢能不能让计算机直接给我算出来呢 你可以按Windows R然后输入calc敲一下回车就可以算出来了 哈你当然不能在解决实际问题的时候让别人这么做所以我们得想想我们自己是怎么把中缀表达式计算成后缀表达式的比如 3 × 4 3\times 4 3×4那么结果很简单就是 3 4 × 3\ 4\ \times 3 4 ×如果是 3 4 × 5 34\times5 34×5那么首先这里优先级最高的是 × \times ×所以碰到3直接输出然后碰到 也暂存起来碰到4又直接输出然后碰到了 × \times ×这次的优先级比上次的 更高继续下去又碰到了5直接输出然后遍历完了再逐渐出栈最后就得到了 3 4 5 × 3\ 4 \ 5 \times\ 3 4 5× 这就对了 所以我们好像知道方法了在遍历的过程中只要碰到数字就输出、碰到符号就去比较栈如果栈空或者栈顶符号优先级比现在符号优先级低就入栈如果比现在符号优先级高就把栈顶输出然后再入栈所以代码就写出来了
void ToRPN(const string origin)
{stackchar ch;bool isInner{ false };for (const auto i : origin) {if (isdigit(i)) {cout i;}else {if (ch.empty()) ch.push(i);else {if (i ! )) {if (i () {ch.push(i);isInner true;}else if (!ch.empty() cmp(i, ch.top()) 0 || (!isdigit(i) isInner ch.top() ()) {ch.push(i);}else {while (!ch.empty() ch.top() ! ( cmp(i, ch.top()) 0) {if (ch.top() ! () cout ch.top();ch.pop();}ch.push(i);}}else {while (!ch.empty() ch.top() ! () {cout ch.top();ch.pop();}if (!ch.empty()) ch.pop();isInner false;}}}}while (!ch.empty()) {cout ch.top();ch.pop();}
}int transform(char c)
{switch (c) {case :case -:return 1;case *:case /:return 2;case ^:return 3;case (:return 4;case ):return 5;default:return -1;}
}// c1 c2 return 0, c1 c2 return 0, else return 0
int cmp(char c1, char c2)
{int a{ transform(c1) }, b{ transform(c2) };return a - b;
}这么做其实写代码不难关键在于符号之间的优先级应该怎么界定在这里我们用了一个转换再比较的方式得到结果±优先级相同且最低然后是*/然后是^之后是括号这样就做出来了看看结果 就是这样不过现在这个函数还不能接收多位数字和负号这里指的是i中提到的负号的二义性问题的输入因此我们“稍微”改造一下就好了
string ToRPN(const string origin)
{string ans;stackchar ch;bool isInner{ false };bool lastNum{ false };bool isNegative{ true };for (const auto i : origin) {if (isdigit(i)) {ans.push_back(i);lastNum true;}else {if (lastNum) {lastNum false;isNegative false;ans.push_back( );}if (ch.empty()) {if (i - !isInner ans.empty()) ch.push(~);else {ch.push(i);if (i () isInner true, isNegative true;}}else {if (i ! )) {if (i () {ch.push(i);isNegative true;isInner true;}else if (!ch.empty() (cmp(i, ch.top()) 0 || (!isdigit(i) isInner ch.top() ())) {if (ch.top() ( isNegative i -) ch.push(~);else ch.push(i);}else {while (!ch.empty() ch.top() ! ( cmp(i, ch.top()) 0) {if (ch.top() ! () {ans.push_back(ch.top());ans.push_back( );}ch.pop();}ch.push(i);}}else {while (!ch.empty() ch.top() ! () {ans.push_back(ch.top());ans.push_back( );ch.pop();}if (!ch.empty()) ch.pop();isInner false;}}}}if (lastNum) ans.push_back( );while (!ch.empty()) {ans.push_back(ch.top());ans.push_back( );ch.pop();}return ans;
}int transform(char c)
{switch (c) {case :case -:return 1;case *:case /:return 2;case ~:return 3;case ^:return 4;case (:return 5;case ):return 6;default:return -1;}
}// c1 c2 return 0, c1 c2 return 0, else return 0
int cmp(char c1, char c2)
{int a{ transform(c1) }, b{ transform(c2) };return a - b;
}稍微嘛、、稍微修改这个代码会稍微复杂一点你可以自己试着写一遍然后再来对对答案其实不会很困难而且做出来之后会很有意思 现在你已经可以把中缀表达式转后缀表达式又可以求出后缀表达式的值了把它们结合一下就可以实现中缀表达式求值了下面是一个例子
#include iostream
#include cctype
#include stack
#include string
using namespace std;
const char c[]{ , -, *, /, (, ), ~ };string ToRPN(const string origin);
int transform(char c);
int cmp(char c1, char c2);
int calculate(const string RPN);int main()
{string temp;cin temp;// cout ToRPN(temp);cout calculate(ToRPN(temp));return 0;
}string ToRPN(const string origin)
{string ans;stackchar ch;bool isInner{ false };bool lastNum{ false };bool isNegative{ true };for (const auto i : origin) {if (isdigit(i)) {ans.push_back(i);lastNum true;}else {if (lastNum) {lastNum false;isNegative false;ans.push_back( );}if (ch.empty()) {if (i - !isInner ans.empty()) ch.push(~);else {ch.push(i);if (i () isInner true, isNegative true;}}else {if (i ! )) {if (i () {ch.push(i);isNegative true;isInner true;}else if (!ch.empty() (cmp(i, ch.top()) 0 || (!isdigit(i) isInner ch.top() ())) {if (ch.top() ( isNegative i -) ch.push(~);else ch.push(i);}else {while (!ch.empty() ch.top() ! ( cmp(i, ch.top()) 0) {if (ch.top() ! () {ans.push_back(ch.top());ans.push_back( );}ch.pop();}ch.push(i);}}else {while (!ch.empty() ch.top() ! () {ans.push_back(ch.top());ans.push_back( );ch.pop();}if (!ch.empty()) ch.pop();isInner false;}}}}if (lastNum) ans.push_back( );while (!ch.empty()) {ans.push_back(ch.top());ans.push_back( );ch.pop();}return ans;
}int transform(char c)
{switch (c) {case :case -:return 1;case *:case /:return 2;case ~:return 3;case ^:return 4;case (:return 5;case ):return 6;default:return -1;}
}// c1 c2 return 0, c1 c2 return 0, else return 0
int cmp(char c1, char c2)
{int a{ transform(c1) }, b{ transform(c2) };return a - b;
}int calculate(const string RPN)
{cout RPN endl;stackint s;int temp{ 0 };bool num{ false };for (int i 0; i RPN.size(); i) {if (isdigit(RPN[i])) {temp * 10;temp RPN[i] - 0;num true;}else if (!isdigit(RPN[i])) {if (RPN[i] ) {if (num) {num false;s.push(temp);temp 0;}continue;}if (RPN[i] ~) {int num s.top();s.pop();s.push(-num);}else {int num1{ 0 }, num2{ 0 };num2 s.top();s.pop();num1 s.top();s.pop();if (RPN[i] ) s.push(num1 num2);else if (RPN[i] -) s.push(num1 - num2);else if (RPN[i] *) s.push(num1 * num2);else if (RPN[i] /) s.push(num1 / num2);}}}return s.top();
}这里的后缀表达式计算中没有考虑幂运算的操作你可以试着完善一下。
#2.队列的应用 队列的应用主要还是在广度优先搜索(BFS) 中这个等到图篇我们再细说。
(6).线性表的其他存储方式 这里主要提一提索引存储和哈希存储。
#1.索引存储 索引存储类似于分桶的思路我们采取相对小数量的桶给它们编号0~10然后对于索引对10取余的结果将结点存到对应的桶当中去这个就不细说了我们主要说一说哈希存储。
#2.哈希存储
i.什么是哈希存储 哈希(Hash)存储是根据存储内容的特性经过散列函数H(x)计算得到一个在已分配存储空间上的位置它的思路像是上面说的分桶存储的极限情况这时候每个桶只存一个数据这样做其实并不一定能充分利用空间因为如果你的散列函数不能比较均匀地把数据映射到整个表中即出现了很多哈希碰撞的情况那么就会浪费非常多已经预先分配好的空间比如我们的哈希函数如果简单如下 H ( x ) x % 10 H(x)x\%10 H(x)x%10 然后给你一堆11、21、31、41…这样以1结尾的数据你就麻烦大了所有的数据全都存到下标为1的分组下面去了这样不仅浪费了别的空间而且还得在同一个下标下不停地存这样到最后查找数据就直接退化了完全不能发挥哈希表的优势。 因此哈希表并不是解决空间利用效率低的办法而是加快查找速度的方法只要你的散列函数不太复杂时间复杂度为 O ( 1 ) O(1) O(1)那么在一个表里查找某个值的最优时间复杂度往往就是 O ( 1 ) O(1) O(1)如果有一个完美的散列函数那么查找的平均和最坏时间复杂度也基本都是 O ( 1 ) O(1) O(1)当然我们做不到完美哈不过哈希的效率的确是比较高的。
ii.碰撞了怎么办 那么如果碰到哈希碰撞的问题怎么办 鉴于我们不能找到完美散列函数所以我们需要一个解决碰撞的方法一般来说是两种开放寻址法和链地址法。 首先是开放寻址法主要采取线性寻址。这个方法还蛮简单的如果你经过散列函数得到的下标已经被占用了那就往后找一直找到下一个能存的位置再存这个方法可能会导致哈希方法的退化因为当前元素随手往后找一个很有可能直接挤占了下一个元素的空间导致后面的每一个元素都要往后找 然后是链地址法这个要好一点就是在碰撞之后往当前地址的链后面加一个新的结点类似于分桶查找但是这么一来就可以有效避免挤占别人空间的问题效率真的会比线性寻址的方法更加高一点。
iii.这个散列函数怎么设计呢 鉴于你用的是C我们可以直接
std::hashint hash;
std::cout hash(214);C对于内置的类型包括STL都提供了std::hashT你可以直接调用但是对于一些没有内置哈希函数的语言比如C语言我们可能得自己想个办法设计在这里提供一种对于字符串的处理思路将字符串作为一个大于26的素数进制的整数将这个字符串还原为对应素数进制的十进制整数再对哈希表大小取余你可以这么操作
int hash(const string str)
{size_t size{ str.size() };int base{ 31 }, code{ str[0] };for (int i 1; i size; i) {code * base;code % 100010;code str[i];}return code % 100010;
}为了避免越界我们的结果要进行取余操作。
(7).查找 你知道我要说什么.jpg没错这一节我们就讲两种查找方式线性查找和二分查找。
#1.线性查找 这个就很自然了比如我们有一个未知顺序的线性表我们可以
// int to_find
int ans{ -1 };
for (int i 0; i v.size(); i) {if (v[i] to_find) {ans i;break;}
}它的时间复杂度是 O ( n ) O(n) O(n)。
#2.二分查找 二分查找的思路是每一次查找的过程中把范围缩小一半不过就缩小一半范围这个要求也挺困难的这需要被查找的线性表有序并且支持随机访问因为我们的查找过程是需要经常发生跳转的所以一般的链表采用二分查找并不能优化效率这个之后我们再来说。 来看看代码吧这个代码其实反而简单了
int binary_search(const vectorint v, int val)
{int low{ 0 }, high{ v.size() - 1 }, mid{ 0 };while (low high) {mid (low high) / 2;if (v[mid] val) return mid;else if (v[mid] val) {high mid - 1;}else low mid 1;}return -1;
}最后来看看时间复杂度我们设二分查找对于n个数据的操作次数为 T ( n ) T(n) T(n)那么应该有以下递推式 T ( n ) T ( n 2 ) 1 T ( n 4 ) 2 . . . T ( n 2 k ) k , ( n 2 k ) T ( 1 ) log 2 n log 2 n 1 ⇒ O ( T ( n ) ) O ( log n ) T(n) T(\frac{n}{2})1T(\frac{n}{4})2...\\T(\frac{n}{2^k})k, (n 2^k) T(1) \log_2 n\log_2 n1\\\Rightarrow O(T(n)) O(\log n) T(n)T(2n)1T(4n)2...T(2kn)k,(n2k)T(1)log2nlog2n1⇒O(T(n))O(logn) 因此我们证明了二分查找的时间复杂度是 O ( log n ) O(\log n) O(logn)所以它的效率真的很高不过代码当中我们看到我们总是要做v[mid]的操作这对于链表来说是不能在 O ( 1 ) O(1) O(1)的时间复杂度内实现的因此我们的递推式就会变成这样 T ( n ) T ( n 2 ) n 2 1 T ( n 4 ) n 2 n 4 2 . . . T ( n 2 k ) ∑ i 1 k n 2 i k , ( n 2 k ) T ( 1 ) n − n 2 k k n log 2 n − 1 ⇒ O ( T ( n ) ) O ( n ) T(n)T(\frac{n}{2})\frac{n}{2}1T(\frac{n}{4})\frac{n}{2}\frac{n}{4}2...\\ T(\frac{n}{2^k}) \sum_{i1}^k\frac{n}{2^i}k, (n2^k) T(1)n-\frac{n}{2^k}kn\log_2 n-1\\ \Rightarrow O(T(n)) O(n) T(n)T(2n)2n1T(4n)2n4n2...T(2kn)i1∑k2ink,(n2k)T(1)n−2knknlog2n−1⇒O(T(n))O(n) 最后发现就因为随机访问的时间复杂度是 O ( n ) O(n) O(n)所以对于链表的二分查找就从 O ( log n ) O(\log n) O(logn)退化成了 O ( n ) O(n) O(n)了。 最后提一下我们还是需要知道如何计算时间复杂度的对于前面的线性问题还比较好解决对于这种递推式的一般来说还可以采取主定理的方式来解决它的基本内容如下 假定有递推关系式 T ( n ) a T ( n b ) f ( n ) T(n)aT(\frac{n}{b})f(n) T(n)aT(bn)f(n)其中 n n n为问题规模 a a a为递推的子问题数量 n b \frac{n}{b} bn为每个子问题的规模假设每个子问题的规模基本一样 f ( n ) f(n) f(n)为递推以外进行的计算工作。 a ≥ 1 , b 1 a\ge1,b1 a≥1,b1为常数 f ( n ) f(n) f(n)为函数 T ( n ) T(n) T(n)为非负整数则有 (1).若 f ( n ) O ( n log b a − ε ) , ε 0 f(n)O(n^{\log_b a-\varepsilon}),\varepsilon0 f(n)O(nlogba−ε),ε0那么 T ( n ) Θ ( n log b a ) T(n)\Theta(n^{\log_b a}) T(n)Θ(nlogba) Θ \Theta Θ是同阶量的表示法 (2).若 f ( n ) Θ ( n log b a ) f(n)\Theta(n^{\log_b a}) f(n)Θ(nlogba)那么 T ( n ) Θ ( n log b a log n ) T(n)\Theta(n^{\log_b a} \log n) T(n)Θ(nlogbalogn) (3).若 f ( n ) Ω ( n log b a ε ) , ε 0 f(n)\Omega(n^{\log_b a\varepsilon}), \varepsilon0 f(n)Ω(nlogbaε),ε0且对于某个常数 c 1 c1 c1和所有充分大的 n n n有 a f ( n b ) ≤ c f ( n ) af(\frac{n}{b})\le cf(n) af(bn)≤cf(n)那么 T ( n ) Θ ( f ( n ) ) T(n)\Theta(f(n)) T(n)Θ(f(n)) Ω \Omega Ω是高阶量的表示法1 例如对于快速排序有以下递推式 T ( n ) 2 T ( n 2 ) n , a 2 , b 2 , f ( n ) n T(n)2T(\frac{n}{2})n,a2,b2,f(n)n T(n)2T(2n)n,a2,b2,f(n)n 根据主定理则有 T ( n ) Θ ( n log n ) T(n)\Theta(n\log n) T(n)Θ(nlogn) 还挺简单对吧
小结 线性表的这一篇就到这里结束了这算是数据结构的一个起点下一章我们将介绍字符串的一些基本内容。 https://baike.baidu.com/item/主定理/3463232 ↩︎
