数据结构复习

第三章 栈和队列
一、栈
top=base，栈空
1、顺序栈
（1）存储结构
（2）顺序栈算法
2、链栈
（1）存储结构
（2）链栈算法
3、应用
（1）数制转换
（2）

二、队列
1、顺序队列（算法实现为循环队列）
附设两个头指针，头指针指向队首元素，尾指针指向队尾元素的下一个位置。
（1）存储结构
（2）顺序队列（循环队列算法）
2、链队列
（1）存储结构
（2）链队列算法

第四章 串
一、基本概念
长度：串中字符的数目n
空串：零个字符的串
子串：
主串：
位置：
真子串：
相等：
空格串：
空串：
字典序：
二、定长顺序存储
1、存储结构
2、顺序串算法
（1）创建串
（2）串复制
（3）求串长
（4）串连接
（5）求子串
（6）串插入
（7）删除子串
（8）输出串
二、堆分配存储表示（链串）
1.存储结构
2、链串算法
（1）创建串
（2）串复制
（3）求串长
（4）串连接
（5）求子串
（6）串插入
（7）删除子串
（8）输出串

三、串的块链存储表示
除头指针外，还可以附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。设尾指针的目的是为了便于进行连接操作。注意：连接时需处理第一个串尾无效字符。
1、存储结构

#define Maxsize 100
typedef struct chunk{
	char ch[Maxsize];
	struct chunk *next;
}chunk;
typedef struct Lstring{
	struct Lstring*head,*tail;
	int curlen; //串的当前长度
}Lstring;

2、存储密度
存储密度=串值所占的存储位/实际分配的存储位

四、C/C++的标准string

五、串的模式匹配算法