第二章 线性表

顺序表

定义

T *aList;	//实例
int maxSize;	//最大长度
int curLen;	//当前长度
int position;	//当前处理位置

检索

按位置：直接计算地址
按内容：遍历。平均比较次数为(n+1)/2，平均时间开销为O(n)

插入

1. 检查表是否溢出
2. 检查插入位置是否合法
3. 从表尾开始将需要移动的元素向后移动一位
4. 在指定位置插入新元素
   平均移动元素次数为n/2，时间开销为O(n)

删除

插入反向操作。

链表

定义

//结点
T data;
Link<T>* next;
//单链表
Link<T>* head, * tail;

检索

无论按位置还是按内容都只能顺序检索。

插入/删除

O(1)
双链表和循环链表的讨论类似。

第三章 栈与队列

栈

ADT

class Stack{
public:
	void clear();
	bool push(const T item);
	bool pop();
	bool top();
	bool isEmpty();
	bool isFull();
}

顺序栈

需要事先知道或估算栈的大小。本质是简化的顺序表。
如果将第0个位置作为栈顶，则每次push和pop的时间代价都是O(n)
如果将最后一个位置作为栈顶，则每次push和pop的时间代价都是O(1)

1. 保存当前栈顶位置
2. push或pop前检查是否上溢或下溢

链式栈

本质是简化的链表。栈顶元素应该设置为链表头。
push和pop的代价都是O(1)

栈的应用：表达式求值

中缀表达式：

1. 先执行括号内
2. 无括号时，先乘除后加减
3. 无优先运算符时，从左到右

后缀表达式（逆波兰）：

1. 不含括号
   2 运算符放在参与运算的两个语法成分后面
2. 严格从左向右执行

中缀转后缀：

1. 操作数直接输出到后缀表达式序列
2. 开括号入栈
3. 闭括号，清空栈至输出序列
4. 遇到运算符时，若（栈非空&&栈顶不是开括号&&栈顶运算符的优先级不低于输入的运算符的优先级），循环弹出栈顶元素。结束上一过程后将输入运算符入栈。
5. 栈中剩余元素弹出

理解方式：
比如说考虑3 op1 4 op2 5这个中缀表达式转换成后缀表达式，前三步是固定的，即：输出3、op1入栈、输出4.
那么处理op2的时候我们需要考虑要不要输出op1，显然如果输出op1，后缀表达式就是3和4先算；不输出就是4和5先算。所以如果op2的优先级比op1更高，就不能先输出op1。同理，假设这个中缀表达式延长，如果op3优先级比op2高，那op2也不能输出；平级的话按从左到右算，意味着平级的运算符是左边的高于右边（所以理解为什么是不低于）。
书上的这个算法描述挺绕的，实际上就是要维护这个运算符栈，保证：1.括号匹配，2.栈内运算符以开括号为界，优先级严格递增

栈与递归

递归由两部分组成：递归基础，即递归出口，也就是递归必须能够结束；递归规则，也就是存在由高阶到低阶的计算规则。
考虑经典的背包问题：背包中可放入重量s，现有n件物品，重量分别为w0,...wn-1，求是否存在解使得背包中重量之和刚好为s。
假设knap(n,s)存在解，考虑这个解和对n降阶的解的关系，显然把解中的物品拿掉一个就得到了一个n-1阶的解，但我们无法确定被拿掉的是哪个物品，甚至根本不知道解里有哪些物品，这种降阶的计算规则是不可得的。
从另一个角度考虑降阶：knap(n,s)的解中是否存在物品wn-1。如果否，则knap(n,s)等价于knap(n-1,s)，相当于在没有wn-1的集合求解同样的问题；如果是，则knap(n,s)等价于knap(n-1,s-wn-1).
反过来想，这两个子阶问题中任意一个有解，则原问题也有解。所以递推关系是knap(n,s) = knap(n-1,s)||knap(n-1,s-wn-1)
边界条件: s=0, true; s!=0 && n=0, false

将递归用栈实现，本质就是把程序运行时栈转换成程序中维护的栈结构。

//递归实现
bool knap(int n, int s){
	if(s==0) return true;
	if(n==0) return false;
	if(knap(n-1, s-w[n-1])){
		cout<<w[n-1];
		return true;
	}
	else return knap(n-1, s);
}

将递归转化为栈最关键是要把栈增长的规则想清楚。设根结点（也就是主函数入口）的返回地址rd=0，knap(n-1,s-w[n-1])调用的返回地址rd=1，knap(n-1,s)调用的返回地址为2.
一开始会往栈里一直压1，直到s或n减到0。如果是s先减到0，说明找到可行解了，开始清栈，遇到rd=1的打印出w[knap.n-1]。如果n先减到0，说明栈顶的1无解，但是还可以压入2，如果这个2有解，清栈打印；无解的话再压下一级的2.

	stack<Node> mystack;
	mystack.push(Node(10,10,0));
	while(!mystack.empty()){
		Node top = mystack.top();
		if(top.s==0){
			while(!mystack.empty()){
				if(mystack.top().rd==1){
					cout<<w[mystack.top().n]<<" ";
				}
				mystack.pop();
			}
			break;
		}
		if((top.s<0 || top.n==0)&& top.rd==1){
			mystack.pop();
			Node tmp=mystack.top();
			mystack.push(Node(tmp.n-1,tmp.s,2));
		}
		else if((top.s<0 || top.n==0 )&& top.rd==2){
			mystack.pop();
			Node tmp=mystack.top();
			mystack.push(Node(tmp.n,tmp.s+w[tmp.n],2));
		}
		top = mystack.top();
		mystack.push(Node(top.n-1,top.s-w[top.n-1],1));
	}

只测了一个很简单的demo，感觉思路上没什么问题。

队列

只能在队头删除，队尾插入。

ADT

class Queue{
public:
	void clear();
	bool enQueue(const T item);
	bool deQueue(T& item);
	bool getFront(T& item);
	bool isEmpty();
	bool isFull();
}

顺序队列

可以利用%将队列实现成一个环，这样插入和删除都可以在O(1)完成。不过还是要考虑溢出的问题。

链式队列

和链式栈差不多。

第四章 字符串

字符串的存储结构与实现

顺序存储

即char s[M]数组，是定长的。
<string.h>提供了若干处理字符串的常用函数。

//求s的长度，不计结束符
size_t strlen(char* s);
//将s2复制到s1，返回指针指向s1的开始
char* strcpy(char* s1, const char* s2);
//将s2拼接到s1尾部
char* strcat(char* s1, const char* s2);
//比较s1和s2
int strcmp(const char* s1, const char* s2);
//返回指向第一次出现在s中的c的指针
char* strchr(char* s, char c);
//逆向搜索
char* strrchr(char* s, char c);

字符串类class String

变长，动态管理长度。

字符串的模式匹配

模式匹配问题，即对于字符串T和模式P，在T中寻找P。假设T长度为n，P长度为m，通过对P预先处理的方式来降低复杂度。
也就是找P的前缀P[0:i-1]，找到其最长的前缀和尾缀，使得P[0:k-1]=P[(i-k):(i-1)]，这样的P在P(i)和T失配时，我们可以直接P右移k位，保证不做多余的比较，也不会漏掉匹配。
对于每一个i，将它的k值保存在数组next[i]中.
next数组的求解可以递推进行，假设next[i-1]=k，即P[0:k-1]=P[(i-k-1):(i-2)]是最长匹配对，现在我们要求解next[i]，考虑P(k)和P(i-1)
(1)如果P(k)=P(i-1)，则P[0:k]=P[(i-k-1):(i-1)]，next[i]=k+1
(2)如果P(k)!=P(i-1)，且k=0，则next[i]=0
(3)如果P(k)!=P(i-1)，且k!=0，考察P(n[k])和P(i-1)的关系，循环(3)直至条件不满足

数据结构与算法复习-第2-4章

原文：https://www.cnblogs.com/winterwinds/p/14995514.html