时间戳

首页 > 技术文章 > 数据结构、算法、及线性表总结

数据结构、算法、及线性表总结

cjt0722 2020-03-28 18:20 原文

目录

一、思维导图

二、重要概念的笔记

栈和队列

1. C++标准库之stack
定义stack对象的代码：stack<int>intStack;
基本操作函数：

  • empty() 堆栈为空则返回真
  • pop() 移除栈顶元素
  • push() 在栈顶增加元素
  • size() 返回栈中元素数目
  • top() 返回栈顶元素

2. C++标准库之queue
定义queuek对象的代码：queue<int>IntQueue;
queue的操作函数和stack的有些类似，但还有很多是不同的：

  • front()：返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
  • back()：返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
  • push(a)：把a接在队列的最后一位，即进队。
  • pop()：删除 queue 中的第一个元素，即出队。
  • size()：返回 queue 中元素的个数。
  • empty()：如果 queue 中没有元素的话，返回 true。
  • emplace()：用传给 emplace() 的参数调用 T 的构造函数，在 queue 的尾部生成对象，感觉和push差不多，没怎么用过。
  • swap(queue &other_q)：将当前 queue 中的元素和参数 queue 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。

3. 需要注意的是，stack和queue不能直接访问某个元素，访问元素的唯一方法是遍历一遍容器，并移除访问过的每一个内容。

例题——jmu-ds-栈与队列-stack、queue与string小综合

#include<iostream>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
int main() {
	stack<char>charStack;//定义了一个字符栈
	queue<char>charQueue;//定义了一个字符队列
	char* s = new char[100]; char x;
	cin >> s ;
	cin >> x;
	int len = strlen(s);
	for (int i = 0; i < len; i++) {
		charStack.push(s[i]);//进栈
	}
	cout << charStack.size() << " " << charStack.top() << endl;
	while (!charStack.empty()) {
		cout << charStack.top();
		if (charStack.top() != x) {
			charQueue.push(charStack.top());//取栈顶元素，并存入队列
		}
		charStack.pop();//出栈
	}
	cout << endl;
	cout << charQueue.size() << " " << charQueue.front() << " " << charQueue.back() << endl;
	while (!charQueue.empty()) {
		cout << charQueue.front();//输出队首元素
		charQueue.pop();//出队
	}
	return 0;
}

串

1. string出来的串是与char初始化来的串是不同的，string出来的串不能使用strlen、strcmp等在库中的函数，但是有size()和length()等成员函数，还可以直接用'>'，'<'直接比较大小，串添加字符时可以直接用'+=',方便了许多。

2.string的重要的成员函数：

  • 构造：string s:生成空字符串
  • 长度：s.size()和s.length()：返回string对象的字符个数，效果一样。
  • 比较：C++字符串支持常见比较操作符（>,>=,<,<=,==,!=），也支持和常字符串（c-string）进行比较，如str>"1245ss"。此外，string还有一个成员函数int compare(size_type __pos1, size_type __n1, const basic_string& __str, size_type __pos2, size_type __n2)，多参数处理，支持用索引值和长度定位子串来进行比较,pos1位置开始长度为n1的子字符串和str从pos2位置开始长度为n2的子字符串按字典序比较大小。 返回值意义如下：0：相等 1：大于 -1：小于。举几个例子，string A="ABCD",string B="abcd",A.compare(B)就相当于串A和串B比较，A.compare(2, 2, B)就相当于"CD" 和 "abcd"比较。
  • 插入：push_back() 和 insert()：push_back()是直接在尾部插入，insert()可以在指定位置插入，举例：
string s1 = "to be the question"；
string s2 = "or not to be";
s1.insetr(6,s2,3,4);

结果是s1变成"to be not the question"。

  • 拼接：s.append("123456")或者 s += str.c_str();
  • 查找：s.find(str,5)：从串s的第5位开始找串str，返回找到的位置索引，找不到就返回-1。
  • 遍历：下标法
  • 删除：s.erase(0,5):删除字符串s从第0位开始的5个字符。
  • 字符替换： s.replace(2,3,str):把串s从第2位开始的三个字符，替换成字符串str。
  • 截取字符串：s2 = s1.substr(3,5)把字符串s1从第三位开始的五个字符赋给字符串b。
  • 字符串分割：strtok函数，例子：

3. 参考材料：
(转）C++ string 字符串详解(这个讲的比较详细）。
c++ string 类基本用法样例

三、疑难问题及解决方案

1. KMP算法（未改进版）怎么理解：对于模式串t，先求出对应的next数组的值，求法：next[1]=0,next[2]=1,然后设第i（i>=3）个元素前有k个字符和模式串t开头的字符相同，next[i]=k+1，以此类推求出next数组。然后在主串S和模式串t进行匹配时，若s[i]!=t[j]，主串s无需回溯，只需让j=next[j]即可，如果j退到值为0，则将模式串t向右滑动一个位置，令s[i+1]和t[1]重新开始匹配。

2. 中缀转后缀的表达式转换

#include<iostream>
#include<algorithm>
#define MAXN 100000
using namespace std;
typedef struct LNode {
	int coefficient;
	int index;
	struct LNode* next;
}LNode, *LinkList;
LNode list[MAXN];
void CreateListR(LinkList& L, int n);
void DispList(LinkList L);
void Destroy(LinkList& L);
void DeleteEqual(LinkList& L);
void Multiply(LinkList L1, LinkList L2, LinkList& L3, int m, int n);
void add(LinkList L1, LinkList L2, LinkList& L3, int m, int n);
bool compare(LNode a, LNode b) {
	return a.index > b.index;
}
int main() {
	LinkList L1, L2;
	int m, n;
	cin >> m;
	CreateListR(L1, m);
	cin >> n;
	CreateListR(L2, n);
	LinkList L3,L4;
	Multiply(L1, L2, L3, m, n);
	add(L1, L2, L4, m, n);
	DispList(L3);
	if (m == 0 || n == 0) {
		printf("0 0");
	}
	cout << endl;
	DispList(L4);
	Destroy(L3);
	Destroy(L4);
}
void Multiply(LinkList L1, LinkList L2, LinkList& L3,int m,int n) {
	L3 = new LNode;
	LinkList r = L3, s, p1 = L1->next, p2 = L2->next;
	for (int i = 0, k = 0; i < m; i++) {
		p2 = L2->next;
		for (int j = 0; j < n; j++) {
			list[k].coefficient = p1->coefficient * p2->coefficient;
			list[k].index = p1->index + p2->index;
			k++;
			p2 = p2->next;
		}
		p1 = p1->next;
	}
	sort(list, list + m * n, compare);
	for (int i = 0; i < m * n; i++) {
		s = new LNode;
		s->coefficient = list[i].coefficient;
		s->index = list[i].index;
		r->next = s;
		r = s;
	}
	r->next = NULL;
	DeleteEqual(L3);
}
void add(LinkList L1, LinkList L2, LinkList& L3, int m, int n) {
	L3 = new LNode;
	LinkList r = L3, s, p1 = L1->next, p2 = L2->next;
	int k = 0;
	for (int i = 0; i < m; i++) {
		p2 = L2->next;
		int t = 0;
		for (int j = 0; j < n; j++) {
			if (p1->index == p2->index) {
				list[k].coefficient = p1->coefficient + p2->coefficient;
				list[k].index = p1->index;
				k++; t = 1;
				break;
			}
			p2 = p2->next;
		}
		if (t == 0) {
			list[k].coefficient = p1->coefficient;
			list[k].index = p1->index;
			k++;
		}
		p1 = p1->next;
	}
	p1 = L1->next; p2 = L2->next;
	for (int i = 0; i < n; i++) {
		p1 = L1->next;
		int t = 0;
		for (int j = 0; j < m; j++) {
			if (p1->index == p2->index) {
			    t = 1;
				break;
			}
			p1 = p1->next;
		}
		if (t == 0) {
			list[k].coefficient = p2->coefficient;
			list[k].index = p2->index;
			k++;
		}
		p2 = p2->next;
	}
	sort(list, list + k, compare);
	for (int i = 0; i < k; i++) {
		s = new LNode;
		s->coefficient = list[i].coefficient;
		s->index = list[i].index;
		r->next = s;
		r = s;
	}
	r->next = NULL;
	DeleteEqual(L3);
}
void CreateListR(LinkList& L, int n) {
	L = new LNode;
	LinkList r = L, s;
	for (int i = 0; i < n; i++) {
		s = new LNode;
		cin >> s->coefficient;
		cin >> s->index;
		r->next = s;
		r = s;
	}
	r->next = NULL;
}
void DispList(LinkList L) {
	if (L->next == NULL) {
		return;
	}
	int t = 0;
	LinkList p = L->next;
	if (p->coefficient != 0) {
		printf("%d %d", p->coefficient, p->index);
		t = 1;
	}
	p = p->next;
	while (p) {
		if (p->coefficient != 0) {
			printf(" %d %d", p->coefficient, p->index);
			t = 1;
		}
		p = p->next;
	}
	if (t == 0) printf("0 0");
}
void Destroy(LinkList& L) {
	LinkList p;
	while (L) {
		p = L;
		L = L->next;
		delete p;
	}
}
void DeleteEqual(LinkList& L) {
	LinkList p = L->next, q;
	if (L->next == NULL) return;
	while (p->next != NULL) {
		q = p->next;
		if (p->index != q->index) {
			p = q;
		}
		else {
			while (q != NULL && q->index == p->index) {
				p->coefficient += q->coefficient;
				p->next = q->next;
				delete q;
				q = p->next;
			}
		}
	}
}

推荐阅读