相关文献：
数据结构与算法(一)：基础理论
数据结构与算法(二)：线性表的实现
数据结构与算法(三)：线性表算法设计练习
数据结构与算法(四)：斐波那契数列
数据结构与算法(五)：LRU
数据结构与算法(六)：栈
数据结构与算法(七)：栈/队列的算法解题思想
数据结构与算法(八)：队列
数据结构与算法(九)：二叉树/线索化二叉树
数据结构与算法(十)：哈夫曼树
本章节研究内容：
递归
栈/队列思想
BF算法(暴力法)
RK算法
KMP算法
做算法题的⽅法 (必看) :
- 充分阅读题⽬.了解题⽬背后的关键意思;
- 分析题⽬,涉及到哪些数据结构,对问题进⾏分类. 到底属于链表问题, 栈思想问题, 字符串问题,⼆叉树问 题,图相关问题,排序问题; 与你之前所接触过的算法题有没有类似,找到问题的解题思路 ;
- 实现算法. 在算法的实现的过程,并不是⼀蹴⽽就, 肯定是需要不断的调试,修改的;
- 验证算法正确性 ;
- 找到题源, 看其他的开发者提供的解决思路;
- 找到题解建议之后, 对于其他优秀思路,分析它的优势,并且学习它的思路.并且写成其他解法的代码(借⼒, 不要单纯的闭⻔造⻋) ;
- 算法题的解题能⼒来⾃于两点: 对于数据结构与算法核⼼问题是否夯实 + 是否有⾜够多且⾜够耐⼼的积累。
栈的思想应⽤
指的是利⽤栈的特性(先进后出)去解决问题,那么什么问题适合⽤栈思想解决了?
- 数据是线性的；
- 问题中常常涉及到数据的来回⽐较,匹配问题;例如,每⽇温度,括号匹配,字符串解码,去掉重复字⺟等问题；
- 问题中涉及到数据的转置,例如进制问题.链表倒序打印问题等；
- 注意并不是说栈思想只是⼀个解决的的参考思想.并不是万能的.它适⽤于以上这样的情况下去解决问题。
利⽤栈思想解决问题时,⾸先需要透彻的解析问题之后,找到问题解决的规律.才能使⽤它解决; 思想只有指导作⽤,遇到不同的题⽬,需要个例分析.在基本思想上去找到具体问题具体的解决问题之道。
题型一：进制转换
注意：这里使用栈思想去解决进制转换问题不是最优解，而是展示我们可以使用这种方式去解决这样的问题。
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */
/* 顺序栈结构 */
typedef struct
{
SElemType data[MAXSIZE];
int top; /* 用于栈顶指针 */
}SqStack;
//4.1 构建一个空栈S
Status InitStack(SqStack *S){
S->top = -1;
return OK;
}
//4.2 将栈置空
Status ClearStack(SqStack *S){
//疑问: 将栈置空,需要将顺序栈的元素都清空吗?
//不需要,只需要修改top标签就可以了.
S->top = -1;
return OK;
}
//4.3 判断顺序栈是否为空;
Status StackEmpty(SqStack S){
if (S.top == -1)
return TRUE;
else
return FALSE;
}
//4.4 返回栈的长度
int StackLength(SqStack S){
return S.top + 1;
}
//4.5 获取栈顶
Status GetTop(SqStack S,SElemType *e){
if (S.top == -1)
return ERROR;
else
*e = S.data[S.top];
return OK;
}
//4.6 插入元素e为新栈顶元素
Status PushData(SqStack *S, SElemType e){
//栈已满
if (S->top == MAXSIZE -1) {
return ERROR;
}
//栈顶指针+1;
S->top ++;
//将新插入的元素赋值给栈顶空间
S->data[S->top] = e;
return OK;
}
//4.7 删除S栈顶元素,并且用e带回
Status Pop(SqStack *S,SElemType *e){
//空栈,则返回error;
if (S->top == -1) { return ERROR; }
//将要删除的栈顶元素赋值给e
*e = S->data[S->top];
//栈顶指针--;
S->top--;
return OK;
}
//4.8 从栈底到栈顶依次对栈中的每个元素打印
Status StackTraverse(SqStack S){
int i = 0;
printf("此栈中所有元素");
while (i<=S.top) {
printf("%d ",S.data[i++]);
}
printf("\n");
return OK;
}
/*
1. 初始化一个空栈S
2. 当十进制N非零时,循环执行以下操作
* 把N与8求余得到的八进制数压入栈S;
* N更新为N与8的商;
3. 当栈S非空时,循环执行以下操作
* 弹出栈顶元素e;
* 输出e;
*/
// 十进制转八进制
void conversion(int N){
SqStack S;
SElemType e;
//1.初始化一个空栈S
InitStack(&S);
//2.
while (N) {
PushData(&S, N%8); // 余数压栈
N = N/8; // 更新要被求余的值
}
//3.
while (!StackEmpty(S)) {
Pop(&S, &e);
printf("%d\n",e);
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
conversion(1348);
return 0;
}
题型二：杨辉三角
#include <stdio.h>
#include <stdlib.h>
/*
思路:
1. 第一层循环控制行数i : 默认[i][0] = 1,[i][i] = 1
2. 第二层循环控制列数j : triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
*/
int** generate(int numRows, int* returnSize){
*returnSize = numRows; // 这个可以不用要的
// 二维数组 int ** 表示每一个元素都是一个一维数组int*
int **res = (int **)malloc(sizeof(int*)*numRows);
for (int i = 0; i < numRows; i++) {
// 给每一个二维数组元素赋值一维数组
res[i] = (int *)malloc(sizeof(int)*(i+1));
res[i][0] = 1;
res[i][i] = 1;
for (int j = 1; j < i; j++) {
res[i][j] = res[i-1][j] + res[i-1][j-1];
}
}
return res;
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("杨辉三角问题\n");
int numRows = 5;
int returnSize;
int **returnResult;
returnResult = generate(numRows, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("[");
for (int j = 0; j<=i; j++) {
printf(" %d ",returnResult[i][j]);
}
printf("]\n");
}
return 0;
}
题型三：爬楼梯问题
可以参照之前分享的斐波那契数列求解是大部分雷同的。
方法一：递归(不推荐)
- f(n) = f(n-1) + f(n-2)
- f(1) = 1
- f(2) = 2
int ClimbStairs_1(int n){
if (n<1) return 0;
if (n == 1) return 1;
if (n == 2) return 2;
return ClimbStairs_1(n-1) + ClimbStairs_1(n-2);
}
和我们的斐波那契数列一样，爬楼梯使用递归法时，当n是一个很大的数会导致内存问题。
方法二：动态规划
int ClimbStairs(int n){
if(n==1) return 1;
int *sum = (int *)malloc(sizeof(int) * (n));
sum[0] = 0;
sum[1] = 1;
sum[2] = 2;
for (int i = 3; i <= n; i++) {
sum[i] = sum[i-1] + sum[i-2];
}
return sum[n];
}
检验算法结果：
int main(int argc, const char * argv[]) {
// insert code here...
printf("爬楼梯问题\n");
int reslut = 0;
reslut = ClimbStairs_1(5);
printf("%d\n",reslut);
reslut = ClimbStairs(5);
printf("%d\n",reslut);
return 0;
}
题型四：每日气温
方法一：暴力法
暴力法解题思路
/*
暴力法1:
1. 从左到右开始遍历,从第一个数到最后一个数开始遍历. 最后一个数因为后面没有元素,默认是0,不需要计算;
2. 从[i+1,TSize]遍历,每个数直到找到比它大的数,数的次数就是对应的值;
思路:
1.创建一个result 结果数组.
2.默认reslut[TSize-1] = 0;
3.从0个元素遍历到最后一个元素[0,TSize-1];
A.如果当前i >0 并且当前的元素和上一个元素相等,则没有必要继续循环. 则判断一下result[i-1]是否等于0,如果等于则直接将result[i] = 0,否则将result[i] = result[i-1]-1;
B.遍历元素[i+1,TSize]
如果当前T[j]>T[i],则result[i] = j-i;
如果当前T[j]已经是最后一个元素,则默认result[i] = 0;
*/
int *dailyTemperatures_1(int* T, int TSize, int* returnSize){
int *result = (int *)malloc(sizeof(int) * TSize);
*returnSize = TSize;
result[TSize-1] = 0; // 最后一个元素没有必要算了，因为后面没有对比值啦
for(int i = 0;i < TSize-1;i++)
if(i>0 && T[i] == T[i-1]) // 相邻两个元素相等时，后一个借前一个的力；没有必要再算啦
result[i] = result[i-1] == 0 ? 0 : result[i-1]-1;
else{
for (int j = i+1; j < TSize; j++) {
if(T[j] > T[i]){
result[i] = j-i;
break;
}
if (j == TSize-1) {
result[i] = 0;
}
}
}
return result;
}
方法二：跳跃对比法
1.我们对比是从右往左去遍历依次对比，最后一个默认是0；（这样我们就可以得到后面的结果值）
2.当前元素的结果值可以利用后面的元素的结果实现跳跃；比如当前元素是75，它的后一个元素是71，但是71已经有结果值啦，75就会跳跃到72去对比，而中间的69和71就不去对比啦。
3.跳跃对比法是在跨度越大的情况下，效果越显著。
/*
跳跃对比:
1. 从右到左遍历. 因为最后一天的气温不会再升高,默认等于0;
2. i 从[TSize-2,0]; 从倒数第二天开始遍历比较. 每次减一;
3. j 从[i+1,TSize]遍历, j+=result[j],可以利用已经有结果的位置进行跳跃,从而减少遍历次数
-若T[i]<T[j],那么Result = j - i;
-若reuslt[j] == 0,则表示后面不会有更大的值,那么当前值就应该也是0;
思路:
1.创建一个result 结果数组.
2.默认reslut[TSize-1] = 0;
3.从TSize-2个元素遍历到第一个元素[TSize-2,0];
4.从[i+1,TSize]遍历,j+=result[j];
-若T[i]<T[j],那么Result = j - i;
-若reuslt[j] == 0,则表示后面不会有更大的值,那么当前值就应该也是0;
*/
int *dailyTemperatures_2(int* T, int TSize, int* returnSize) {
// 创建结果数组
int *result = (int *)malloc(sizeof(int) * TSize);
*returnSize = TSize;
// 默认最后一天为0
result[TSize-1] = 0;
//
for (int i=TSize-2; i >= 0; i--) {
for (int j = i+1; j < TSize; j+=result[j]) {
if (T[i] < T[j]) {
result[i] = j-i;
break;
} else {
if (result[j] == 0) {
result[i] = 0;
break;
}
}
}
}
return result;
}
方法三：栈思想
1.栈中存储的是元素的索引值index;
2.将当前元素和栈顶元素⽐较;
如果栈为空,那么直接将当前元素索引index 存储到栈中;
如果栈顶元素>当前元素,则将当前元素索引index 存储到栈中;
如果栈顶元素<当前元素,则将当前元素索引index-栈顶元素index,计算完毕 则将当前栈顶元素移除,将当前元素索引index 存储到栈中
思路:
- 初始化一个栈(用来存储索引),value数组
- 栈中存储的是元素的索引值index;
- 遍历整个温度数组从[0,TSize];
(1).如果栈顶元素<当前元素,则将当前元素索引index-栈顶元素index,计算完毕则将当前栈顶元素移除,将当前元素索引index 存储到栈中; 出栈后,只要栈不为空.继续比较,直到栈顶元素不能满足T[i] > T[stack_index[top-1]]
(2).如果当前的栈为空,则直接入栈;
(3).如果当前的元素小于栈顶元素,则入栈
(4).while循环结束后,当前元素也需要入栈;
int* dailyTemperatures_3(int* T, int TSize, int* returnSize) {
*returnSize = TSize;
// 结果数组
int* result = (int*)malloc(sizeof(int)*TSize);
// 用栈记录T的下标。
int* stack_index = malloc(sizeof(int)*TSize);
// 栈顶指针
int top = 0;
// 中间变量，得到栈顶的索引
int tIndex;
for (int i = 0; i < TSize; i++)
result[i] = 0;
for (int i = 0; i < TSize; i++) {
printf("\n循环第%d次,i = %d\n",i,i);
// 若当前元素大于栈顶元素，栈顶元素出栈。即温度升高了，所求天数为两者下标的差值。
// 出栈条件
while (top > 0 && T[i] > T[stack_index[top-1]]) {
tIndex = stack_index[top-1];
result[tIndex] = i - tIndex;
top--;
printf("tIndex = %d; result[%d] = %d, top = %d \n",tIndex,tIndex,result[tIndex],top);
}
// 当前元素入栈。
stack_index[top] = i;
printf("i= %d; StackIndex[%d] = %d ",i,top,stack_index[top]);
top++;
printf(" top = %d \n",top);
}
return result;
}
注意：栈思想也能解决问题，但是并不比上面两种方法复杂度低
题型五：字符串编码问题
例如：
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回"accaccacc".
s = "2[abc]3[cd]ef", 返回"abcabccdcdcdef".
注意：题目里隐藏了数字有可能是两位数三位数，但是字符不认识它是数字的多少。
例如:12[a]为例;
思路:
1.遍历字符串 S
2.如果当前字符不为方括号"]" 则入栈stack中;
3.如果当前字符遇到了方括号"]" 则:
①首先找到要复制的字符,例如stack="12[a",那么我要首先获取字符a;将这个a保存在另外一个栈去tempStack;
② 接下来,要找到需要备份的数量,例如stack="12[a",因为出栈过字符"a",则当前的top指向了"[",也就是等于2;
③ 而12对于字符串是2个字符, 我们要通过遍历找到数字12的top上限/下限的位置索引, 此时上限curTop = 2, 下限通过出栈,top = -1;
④ 根据范围[-1,2],读取出12保存到strOfInt 字符串中来, 并且将字符"12\0",转化成数字12;
⑤ 当前top=-1,将tempStack中的字符a,复制12份入栈到stack中来;
⑥ 为当前的stack扩容, 在stack字符的末尾添加字符结束符合'\0';
char * decodeString(char * s){
/*.
1.获取字符串长度
2.设置默认栈长度50
3.开辟字符串栈(空间为50)
4.设置栈头指针top = -1;
*/
int len = (int)strlen(s);
int stackSize = 50;
char* stack = (char*)malloc(stackSize * sizeof(char));
int top = -1;
//遍历字符串,在没有遇到"]" 之前全部入栈
for (int i = 0; i < len; ++i) {
if (s[i] != ']') {
//优化:如果top到达了栈的上限,则为栈扩容;
if (top == stackSize - 1) {
stack = realloc(stack, (stackSize += 50) * sizeof(char));
}
//将字符入栈stack
stack[++top] = s[i];
printf("#① 没有遇到']'之前# top = %d\n",top);
}
else {
// temp从来存储拷贝出来的字符
int tempSize = 10;
char* temp = (char*)malloc(tempSize * sizeof(char));
int topOfTemp = -1;
printf("#② 开始获取要复制的字符信息之前 # top = %d\n",top);
//从栈顶位置开始遍历stack,直到"["结束;
//把[a]这个字母a 赋值到temp栈中来;
//简单说,就是将stack中方括号里的字符出栈,复制到temp栈中来;
while (stack[top] != '[') {
//优化:如果topOfTemp到达了栈的上限,则为栈扩容;
if (topOfTemp == tempSize - 1) {
temp = realloc(temp, (tempSize += 10) * sizeof(char));
}
//temp栈的栈顶指针自增;
++topOfTemp;
//将stack栈顶字符复制到temp栈中来;
temp[topOfTemp] = stack[top];
//stack出栈,则top栈顶指针递减;
top--;
}
printf("#② 开始获取要复制的字符信息之后 # top = %d\n",top);
//找到倍数数字.strOfInt字符串;
//注意:如果是大于1位的情况就处理
char strOfInt[11];
//p记录当前的top;
int curTop = top;
printf("#③ 开始获取数字,数字位置上限 # curTop = %d\n",curTop);
//top--的目的是把"["剔除,才能找到数字;
top--;
//遍历stack得出数字
//例如39[a] 就要找到这个数字39.
//p指向当前的top,我就知道上限了; 那么接下来通过循环来找它的数字下限;
//结束条件:栈指针指向为空! stack[top] 不等于数字
while (top != -1 && stack[top] >= '0' && stack[top] <= '9') {
top--;
}
printf("#③ 开始获取数字,数字位置下限 # top = %d\n",top);
//从top-1遍历到p之间, 把stack[top-1,p]之间的数字复制到strOfInt中来;
//39中3和9都是字符. 我们要获取到这2个数字,存储到strOfInt数组
for (int j = top + 1; j < curTop; ++j) {
strOfInt[j - (top + 1)] = stack[j];
}
//为字符串strOfInt数组加一个字符结束后缀'\0'
strOfInt[curTop - (top + 1)] = '\0';
//把strOfInt字符串转换成整数 atoi函数;
//把字母复制strOfInt份到stack中去;
//例如39[a],就需要把复制39份a进去;
int curNum = atoi(strOfInt);
for (int k = 0; k < curNum ; ++k) {
//从-1到topOfTemp 范围内,复制curNum份到stackTop中去;
int kk = topOfTemp;
while (kk != -1) {
//优化:如果stack到达了栈的上限,则为栈扩容;
if (top == stackSize - 1) {
stack = realloc(stack, (stackSize += 50) * sizeof(char));
}
//将temp栈的字符复制到stack中;
//stack[++top] = temp[kk--];
++top;
stack[top] = temp[kk];
kk--;
}
}
free(temp);
temp = NULL;
}
}
//realloc 动态内存调整;
//void *realloc(void *mem_address, unsigned int newsize);
//构成字符串stack后, 在stack的空间扩容.
char* ans = realloc(stack, (top + 1) * sizeof(char));
ans[++top] = '\0';
//stack 栈不用,则释放;
free(stack);
return ans;
}
题型六：去除重复字母
示例1:
输入:"bcabc"
输出:"abc"
示例2:
输入:"cbacdcbc"
输出:"acdb"
解题关键:
字典序: 字符串之间比较和数字比较不一样; 字符串比较是从头往后挨个字符比较,那个字符串大取决于两个字符串中第一个对应不相等的字符; 例如 任意一个a开头的字符串都大于任意一个b开头的字符串;例如字典中apple 大于 book;
题目的意思,你去除重复字母后,需要按最小的字典序返回.并且不能打乱其他字母的相对位置;
例如 bcabc 你应该返回abc, 而不是bca,cab;
例如 cbacdcbc 应该返回acdb,而不是cbad,bacd,adcb
例如 zab,应该返回zab,而不是abz;
思路:
-
判断字符串可能出现的特殊情况
-
用一个record数组记录字符串中字母出现的次数;
-
申请一个字符串栈stack用来存储去除重复字母的结果,并利用它的特性帮助我们找到正确的次序;
-
遍历字符串s
-
从0~top,遍历stack 判断当前字符s[i]是否存在于栈stack中
如果当前字符是否存在于栈的定义一个falg 标记isExist, 0表示不存在, 1表示存在; -
如果isExist存在,record[s[i]]位置上的出现次数减一，并继续遍历下一个字符; 表示当前的stack已经有这个字符了没有必要处理这个重复的字母;
-
如果isExist不存在,则
如果不存在,则需要循环一个找到一个正确的位置,然后在存储起来;
如果不存在，跳过栈中所有比当前字符大、且后面还会出现的元素，然后将当前字符入栈
top > -1表示栈非空
stack[top] > s[i]表示栈顶元素比当前元素大
record[stack[top]] > 1表示后面还会出现
通过一个while循环找到将栈中位置错误的数据,出栈. 找当前合适的位置,则结束while循环;
找到合理的位置后,则将当前字符s[i]入栈; -
直到遍历完所有字符后,则为字符串栈stack 添加一个结束符'\0',并返回当前字符串首地址;
char *removeDuplicateLetters(char *s)
{
/*
① 特殊情况处理,s为空,或者字符串长度为0;
② 特殊情况,s的长度为1,则没有必要后续的处理,则直接返回s;
*/
if (s == NULL || strlen(s) == 0) {
return "";
}
if (strlen(s) == 1) {
return s;
}
//record数组,用来记录字符串s中每个字符未来会出现的次数;
char record[26] = {0};
int len = (int)strlen(s);
//申请一个字符串stack;(用栈的特性来进行stack字符串的数据进出)
char* stack = (char*)malloc(len * 2 * sizeof(char));
//memset(void *s, int ch, size_t n) 将stack len*2*sizeof(char)长度范围的空间填充0;
memset(stack, 0, len * 2 * sizeof(char));
//stack 栈顶赋初值为-1;
int top = -1;
//1.统计每个字符的频次
//例如bcabc recod[26] = {1,2,2};
int i;
for (i = 0; i < len; i++) {
record[s[i] - 'a']++;
}
//2.遍历s,入栈
for (i = 0; i < len; i++) {
//isExist 标记, 判断当前字符是否存在栈中;
int isExist = 0;
//①从0~top,遍历stack 判断当前字符s[i]是否存在于栈stack中
//如果当前字符是否存在于栈的flag, 0表示不存在, 1表示存在
//top指向栈顶(也是执行stack字符串最后一个字符的位置,表示字符串长度上限)
for (int j = 0; j <= top; j++) {
if (s[i] == stack[j]) {
isExist = 1;
break;
}
}
//② 如果存在,record[s[i]]位置上的出现次数减一，并继续遍历下一个字符
//③ 如果不存在,则需要循环一个正确位置存储起来;
//④ 如果不存在，跳过栈中所有比当前字符大、且后面还会出现的元素，然后将当前字符入栈
// top > -1表示栈非空
//stack[top] > s[i]表示栈顶元素比当前元素大
//record[stack[top]] > 1表示后面还会出现
//例如b,c因为不符合以下条件会直接入栈.stack[] = "bc",但是当当前字符是"a"时,由于bcabc,a不应该是在stack的顺序是"bca",所以要把位置不符合的字符出栈;
//top = 1,stack[top] > s[i], c>a; 并且stack[top] 在之后还会重复的出现,所以我们可以安心的把stack中的栈顶C出栈,所以stack[]="b",top减一后等于0; 同时也需要将record[c]出现次数减一;
//top=0,stack[top]>s[i],b>a,并且stack[top] 在之后还会出现,所以stack把栈顶b出栈,所以此时栈stack[]="",top减一后等于-1, 此时栈中位置不正确的字符都已经移除;
if (isExist == 1) {
record[s[i] - 'a']--;
} else {
while (top > -1 && stack[top] > s[i] && record[stack[top] - 'a'] > 1) {
// 跳过该元素，频次要减一
record[stack[top] - 'a']--;
// 出栈
top--;
}
//⑤ 结束while 循环;
//循环结束的3种可能性:(1)移动到栈底(top == -1) ; (2)栈顶元素小于当前元素(stack[top] <= s[i]) (3)栈顶元素后面不出现(record[stack[top]] == 1)
// 此时，当前元素要插入到top的下一个位置
// top往上移动1位
top++;
// 入栈
stack[top] = s[i];
}
}
//结束栈顶添加字符结束符
stack[++top] = '\0';
return stack;
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("去掉重复字母! LeetCode-困难 \n");
char *s ;
s = removeDuplicateLetters("bcabc");
printf("%s\n",s);
// s = removeDuplicateLetters("zab");
// printf("%s\n",s);
//
// s = removeDuplicateLetters("cbacdcbc");
// printf("%s\n",s);
printf("\n");
return 0;
}
题型七：字符串匹配
方法1：BF算法(暴力法)
主字符串的子串回溯到 起始点+1 的位置，模式串回溯到起始点的位置，逐一去比较。
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 40 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef char String[MAXSIZE+1]; /* 0号单元存放串的长度 */
/* 生成一个其值等于chars的串T */
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
Status ClearString(String S)
{
S[0]=0;/* 令串长为零 */
return OK;
}
/* 输出字符串T。 */
void StrPrint(String T)
{
int i;
for(i=1;i<=T[0];i++)
printf("%c",T[i]);
printf("\n");
}
/* 输出Next数组值。 */
void NextPrint(int next[],int length)
{
int i;
for(i=1;i<=length;i++)
printf("%d",next[i]);
printf("\n");
}
/* 返回串的元素个数 */
int StrLength(String S)
{
return S[0];
}
/*
1. BF算法-爆发匹配算法
思路:
1. 分别利用计数指针i和j指示主串S和模式T中当前正待比较的字符位置,i初值为pos,j的初值为1;
2. 如果2个串均为比较到串尾,即i和j均小于等于S和T的长度时, 则循环执行以下的操作:
* S[i]和T[j]比较,若相等,则i 和 j分别指示串中下一个位置,继续比较后续的字符;
* 若不相等,指针后退重新开始匹配. 从主串的下一个字符串(i = i - j + 2)起再重新和模式第一个字符(j = 1)比较;
3. 如果j > T.length, 说明模式T中的每个字符串依次和主串S找中的一个连续字符序列相等,则匹配成功,返回和模式T中第一个字符的字符在主串S中的序号(i-T.length);否则匹配失败,返回0;
*/
int Index_BF(String S, String T,int pos){
//i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配
int i = pos;
//j用于子串T中当前位置下标值
int j = 1;
//若i小于S的长度并且j小于T的长度时，循环继续
while (i <= S[0] && j <= T[0]) {
//比较的2个字母相等,则继续比较
if (S[i] == T[j]) {
i++;
j++;
}else
{
//不相等,则指针后退重新匹配
//i 退回到上次匹配的首位的下一位;
//加1,因为是子串的首位是1开始计算;
//再加1的元素,从上次匹配的首位的下一位;
i = i-j+2;
//j 退回到子串T的首位
j = 1;
}}
//如果j>T[0],则找到了匹配模式
if (j > T[0]) {
//i母串遍历的位置 - 模式字符串长度 = index 位置
return i - T[0];
}else{
return -1;
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("字符串模式匹配!\n");
int i,*p;
String s1,s2;
StrAssign(s1, "abcdex");
printf("s1子串为");
StrPrint(s1);
StrAssign(s2, "xe");
printf("s2子串为");
StrPrint(s2);
i = Index_BF(s1, s2, 1);
printf("i = %d\n",i);
return 0;
}
BF算法虽然在实际运用中非常之常见，但是也会出现一些效率问题：
像这样的每次到最后一位都不匹配，之前所干的事情就白费啦。
于是接下来就有我们RK算法去优化出现这样的效率问题。
方法2：RK算法
RK算法的核心思想：将主串拆解成多个与模式串等长的子串，对每个子串的hash值与模式串的hash值对比。
核心思想
于是问题就解刨成：如何将模式串或者主串拆分后的子串换算成一个哈希值？
我们需要一边拆解主串得到子串的hash值，一边去比较模式串的hash值。因为如果匹配的下标靠前的话，后面的拆解和求子串hash就没有必要了。
注意：hash冲突不可避免。我们需要一个函数将不同的字母组合计算映射成不同的数字。
//将字母转换成数字
'当前字母' - 'a' = 数字
例如：（'a'代表ascii码中的97）
a - a = 0
b - a = 1
c - a = 2
d - a = 3
e - a = 4
...
使用ascii码有一个弊端，就是如果字符串很长很长呢，那映射出来的数字就会非常之大，大到我们的long类型都装不下就会产生溢出。那么我们就得想法子去降低数字的体量，尽量去避免溢出。
比如如下数字可以转换成10进制的写法：
657 = 6*10*10 + 5*10 + 7*1
657 = 6 * 10^2 + 5 * 10^1 + 7 * 10^0
那么我们也可以转换成26进制从而所小数字的体量：
(因为小写字母只有26位)
通过计算hash值去比较，大大减少了比较次数，但是计算多了哟。
求子串哈希值的规律是什么意思呢？
看下图举例：
利用这样的规律去优化计算，从而减小计算的压力。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//d 表示进制
#define d 26
//4.为了杜绝哈希冲突. 当前发现模式串和子串的HashValue 是一样的时候.还是需要二次确认2个字符串是否相等.
int isMatch(char *S, int i, char *P, int m)
{
int is, ip;
for(is=i, ip=0; is != m && ip != m; is++, ip++)
if(S[is] != P[ip])
return 0;
return 1;
}
//3.算出最d进制下的最高位
//d^(m-1)位的值;
int getMaxValue(int m){
int h = 1;
for(int i = 0;i < m - 1;i++){
h = (h*d);
}
return h;
}
/*
* 字符串匹配的RK算法
* Author：Rabin & Karp
* 若成功匹配返回主串中的偏移，否则返回-1
*/
int RK(char *S, char *P)
{
//1. n:主串长度, m:子串长度
int m = (int) strlen(P);
int n = (int) strlen(S);
printf("主串长度为:%d,子串长度为:%d\n",n,m);
// A:模式串的哈希值;
unsigned int A = 0;
// St:主串分解子串的哈希值;
unsigned int St = 0; // 边求值边比较，所以不用数组
//2.求得子串与主串中0~m字符串的哈希值[计算子串与主串0-m的哈希值]
//循环[0,m)获取模式串A的HashValue以及主串第一个[0,m)的HashValue
//此时主串:"abcaadddabceeffccdd" 它的[0,2)是ab
//此时模式串:"cc"
//cc = 2 * 26^1 + 2 *26 ^0 = 52+2 = 54;
//ab = 0 * 26^1 + 1 *26^0 = 0+1 = 1;
for(int i = 0; i != m; i++){
//第一次 A = 0*26+2;
//第二次 A = 2*26+2;
A = (d*A + (P[i] - 'a'));
//第一次 st = 0*26+0
//第二次 st = 0*26+1
St = (d*St + (S[i] - 'a'));
}
//3. 获取d^m-1值(因为经常要用d^m-1进制值)
int hValue = getMaxValue(m);
//4.遍历[0,n-m], 判断模式串HashValue A是否和其他子串的HashValue 一致.
//不一致则继续求得下一个HashValue
//如果一致则进行二次确认判断,2个字符串是否真正相等.反正哈希值冲突导致错误
//注意细节:
//① 在进入循环时,就已经得到子串的哈希值以及主串的[0,m)的哈希值,可以直接进行第一轮比较;
//② 哈希值相等后,再次用字符串进行比较.防止哈希值冲突;
//③ 如果不相等,利用在循环之前已经计算好的st[0] 来计算后面的st[1];
//④ 在对比过程,并不是一次性把所有的主串子串都求解好Hash值. 而是是借助s[i]来求解s[i+1] . 简单说就是一边比较哈希值,一边计算哈希值;
for(int i = 0; i <= n-m; i++){
if(A == St)
if(isMatch(S,i,P,m))
//加1原因,从1开始数
return i+1;
St = ((St - hValue*(S[i]-'a'))*d + (S[i+m]-'a'));
}
return -1;
}
int main()
{
char *buf="abcababcabx";
char *ptrn="abcabx";
printf("主串为%s\n",buf);
printf("子串为%s\n",ptrn);
int index = RK(buf, ptrn);
printf("find index : %d\n",index);
return 1;
}
方法3：KMP算法
假设, 主串S = “abcababca” ; 模式串 T = “abcabx”。
若是使用BF算法去解决字符串匹配的话，由于index回溯导致出现很多多余的对比判断问题。
- BF算法多余判断的分析
23步骤为什么多余：由于我们的模式串 T = “abcabx” 并没有相邻的字符是相同的，所以a与b、a与c就不需要比较了。
45也是多余的：因为我们第1步的时候，就知道了abcab前五位的比较结果了，所以第4/5步骤也是多余的。
此时模式串回溯到j=3的位置，是因为前两个字母已经笃定了是可以通过判断的。
KMP算法就是为了优化这种多余的对比判断问题的。
于是KMP算法利用 next 数组去记录模式串中最优的回溯位置，以减少对比次数，从而得到优化。
我们把 T 串(模式串)各个位置 j 值变化定义为一个 next 数组; 那么next 的长度就是 T串的长度; 于是我们可以得出下面函数的定义:
next 数组里面装的是什么数据呢？怎么得到的呢？
next 数组装是模式串回溯的位置；它是根据模式串的字符重复得到的。
来看看下面几个举例的模式串得到next 数组：
（注意下面举例与主串无关）
- 分析模式串T = “abcdex”时，
next 数组里的值：
- 分析模式串T = “abcabx”时，
next 数组里的值：
- 分析模式串T = “ababaaaba”时，
next 数组里的值：
- 分析模式串T = “aaaaaaaab”时，
next 数组里的值：
next 数组的值经验: 如果前后缀一个字符相等,K值是2; 两个字符相等是3; n个相等k值就是n+1。
我们知道next 数组是用来存储模式串的回溯位置的
- 那么
next 数组在KMP算法中是如何运用的呢？
例如我们的模式串T="abcabx"，此时它的next 数组如下：
当模式串与主串相比较的时候
- 模式串中第一个字符a匹配不成功，next[0] = 0，此时next数据需要重头开始计算； 主串下标 i++，又从模式串的a开始比较;
- 当模式串是第二个字符b匹配不成功时，next[1] = 1，此时需要回溯到模式串第一个位置，主串下标 i++，又从模式串的a开始比较;
- 当模式串前面三个字符都匹配成功，到第四个字符a匹配不成功时，next[4] = 2，主串下标 i++，从模式串的第二个字符b开始匹配。
以此类推...
注意：我们怎么知道主串与模式串完全匹配成功呢？当模式串的下标超过了模式串的大小，就说明完全匹配。
- KMP算法实现
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef char String[MAXSIZE+1]; /* 0号单元存放串的长度 */
//----字符串相关操作---
/* 生成一个其值等于chars的串T */
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
// 清空字符串
Status ClearString(String S)
{
S[0]=0;/* 令串长为零 */
return OK;
}
/* 输出字符串T。 */
void StrPrint(String T)
{
int i;
for(i=1;i<=T[0];i++)
printf("%c",T[i]);
printf("\n");
}
/* 返回串的元素个数 */
int StrLength(String S)
{
return S[0];
}
求next数组
//----KMP 模式匹配算法---
//1.通过计算返回子串T的next数组;
//注意字符串T[0]中是存储的字符串长度; 真正的字符内容从T[1]开始;
void get_next(String T,int *next){
int i,j;
j = 1;
i = 0;
next[1] = 0;
//abcdex
//遍历T模式串, 此时T[0]为模式串T的长度;
//printf("length = %d\n",T[0]);
while (j < T[0]) {
//printf("i = %d j = %d\n",i,j);
if(i ==0 || T[i] == T[j]){
//T[i] 表示后缀的单个字符;
//T[j] 表示前缀的单个字符;
++i;
++j;
next[j] = i;
//printf("next[%d]=%d\n",j,next[j]);
}else
{
//如果字符不相同,则i值回溯;
i = next[i];
}
}
}
//输出Next数组值
void NextPrint(int next[],int length)
{
int i;
for(i=1;i<=length;i++)
printf("%d",next[i]);
printf("\n");
}
匹配字符串KMP算法
//KMP 匹配算法(1)
//返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回0;
int Index_KMP(String S,String T,int pos){
//i 是主串当前位置的下标准,j是模式串当前位置的下标准
int i = pos;
int j = 1;
//定义一个空的next数组;
int next[MAXSIZE];
//对T串进行分析,得到next数组;
get_next(T, next);
//注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
//若i小于S长度并且j小于T的长度是循环继续;
while (i <= S[0] && j <= T[0]) {
//如果两字母相等则继续,并且j++,i++
if(j == 0 || S[i] == T[j]){
i++;
j++;
}else{
//如果不匹配时,j回退到合适的位置,i值不变;
j = next[j];
}
}
if (j > T[0]) {
return i-T[0];
}else{
return -1;
}
}
但是KMP依旧有问题：比如主串S=aaaaabc，模式串T=aaaaax，此时next数组=012345。
前5个字符都能匹配成功，但是：
当对比到主串中的b与模式串中的x不匹配，那就回溯到模式串第5的位置；
此时主串中的b与模式串中第5位置的a不匹配，那就回溯到模式串第4的位置；
....
最终模式串第一个a也不匹配，主串的下标才去下一个字符。
像这种重叠字符的模式串，就需要去优化算法。
- 引入一个
nextval数组去跳过这样的重复字符逐个回溯问题。(对next数组的优化)
nextval是里的元素的值是如何获得的：
分析 j=3 时
分析 j =4 时
nextVal数组的求解
//KMP 匹配算法(2)
//求模式串T的next函数值修正值并存入nextval数组中;
void get_nextVal(String T,int *nextVal){
int i,j;
j = 1;
i = 0;
nextVal[1] = 0;
while (j < T[0]) {
if (i == 0 || T[i] == T[j]) {
++j;
++i;
//如果当前字符与前缀不同,则当前的j为nextVal 在i的位置的值
if(T[i] != T[j])
nextVal[j] = i;
else
//如果当前字符与前缀相同,则将前缀的nextVal 值赋值给nextVal 在i的位置
nextVal[j] = nextVal[i];
}else{
i = nextVal[i];
}
}
}
//KMP 匹配算法(2)
//返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回0;
int Index_KMP2(String S,String T,int pos){
//i 是主串当前位置的下标准,j是模式串当前位置的下标准
int i = pos;
int j = 1;
//定义一个空的next数组;
int next[MAXSIZE];
//对T串进行分析,得到next数组;
get_nextVal(T, next);
count = 0;
//注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
//若i小于S长度并且j小于T的长度是循环继续;
while (i <= S[0] && j <= T[0]) {
//如果两字母相等则继续,并且j++,i++
if(j == 0 || S[i] == T[j]){
i++;
j++;
}else{
//如果不匹配时,j回退到合适的位置,i值不变;
j = next[j];
}
}
if (j > T[0]) {
return i-T[0];
}else{
return -1;
}
}
测试KMP算法
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, KMP匹配算法实现!\n");
int i,*p,*t;
String s1,s2;
int Status;
/*关于next数组的求解*/
StrAssign(s1,"aaaaax");
printf("子串为: ");
StrPrint(s1);
i=StrLength(s1);
p=(int*)malloc((i+1)*sizeof(int));
get_next(s1,p);
printf("Next为: ");
NextPrint(p,StrLength(s1));
t=(int*)malloc((i+1)*sizeof(int));
get_nextVal(s1, t);
printf("NextVal为: ");
NextPrint(t,StrLength(s1));
printf("\n");
//KMP算法调用
StrAssign(s1,"abcababca");
printf("主串为: ");
StrPrint(s1);
StrAssign(s2,"abcdex");
printf("子串为: ");
StrPrint(s2);
Status = Index_KMP(s1,s2,1);
printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
Status = Index_KMP2(s1, s2, 1);
printf("主串和子串在第%d个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配] \n\n",Status);
StrAssign(s1,"abccabcceabc");
printf("主串为: ");
StrPrint(s1);
StrAssign(s2,"abcce");
printf("子串为: ");
StrPrint(s2);
Status = Index_KMP(s1,s2,1);
printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
Status = Index_KMP2(s1, s2, 1);
printf("主串和子串在第%d个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配] \n\n",Status);
StrAssign(s1,"aaaabcde");
printf("主串为: ");
StrPrint(s1);
StrAssign(s2,"aaaaax");
printf("子串为: ");
StrPrint(s2);
Status = Index_KMP(s1,s2,1);
printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
Status = Index_KMP2(s1, s2, 1);
printf("主串和子串在第%d个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配] \n\n",Status);
return 0;
}
题型八：用栈实现队列
思路：使用两个栈，数据犹如倒垃圾似的加入到栈A，再倒入到栈B。这样就能实现类似于队列的能力。
值得注意的是，当栈B有数据的时候，栈A里的不能倒入栈B，因为当栈B里的任务在执行，又来了新的任务的话，就会优先处理新的任务了。
#include <stdio.h>
#include <stdlib.h>
typedef struct {
// 数组
int *next;
// 实际使用大小
int size;
// 容量大小
int capacity;
} Stack;
// 构建一个空栈
Stack* stackCreate(int cpacity) {
Stack *stk = malloc(sizeof(Stack));
stk->next = malloc(sizeof(int) * cpacity);
stk->size = 0;
stk->capacity = cpacity;
return stk;
}
// 插入元素为新栈顶元素
void stackPush(Stack* obj, int x) {
obj->size = obj->size % obj->capacity;
obj->next[obj->size] = x;
obj->size++;
}
// 删除栈顶元素
void stackPop(Stack* obj) {
obj->size--;
}
// 获取栈顶
int stackTop(Stack* obj) {
return obj->next[obj->size - 1];
}
// 判断顺序栈是否为空;
int stackEmpty(Stack* obj) {
return obj->size == 0;
}
// 将栈置空
void stackFree(Stack* obj) {
free(obj->next);
}
typedef struct {
// push
Stack* pushStack;
// pop
Stack* popStack;
} MyQueue;
MyQueue* myQueueCreate(void) {
MyQueue* queue = malloc(sizeof(MyQueue));
queue->pushStack = stackCreate(100);
queue->popStack = stackCreate(100);
return queue;
}
void pushStackToPopStack(MyQueue* obj) {
while (!stackEmpty(obj->pushStack)) {
stackPush(obj->popStack, stackTop(obj->pushStack));
stackPop(obj->pushStack);
}
}
// 将元素 x 推到队列的末尾
void myQueuePush(MyQueue* obj, int x) {
stackPush(obj->pushStack, x);
}
// 从队列的开头移除并返回元素
int myQueuePop(MyQueue* obj) {
if (stackEmpty(obj->popStack)) {
pushStackToPopStack(obj);
}
int x = stackTop(obj->popStack);
stackPop(obj->popStack);
return x;
}
// 返回队列开头的元素
int myQueuePeek(MyQueue* obj) {
if (stackEmpty(obj->popStack)) {
pushStackToPopStack(obj);
}
return stackTop(obj->popStack);
}
int myQueueEmpty(MyQueue* obj) {
return stackEmpty(obj->pushStack) && stackEmpty(obj->popStack);
}
void myQueueFree(MyQueue* obj) {
stackFree(obj->pushStack);
stackFree(obj->popStack);
}
int main(int argc, const char * argv[]) {
MyQueue *myQueue = myQueueCreate();
myQueuePush(myQueue, 1); // queue is: [1]
myQueuePush(myQueue, 2); // queue is: [1, 2] (leftmost is front of the queue)
int peek = myQueuePeek(myQueue); // return 1
int pop = myQueuePop(myQueue); // return 1, queue is [2]
int peek2 = myQueuePeek(myQueue);
int empty = myQueueEmpty(myQueue); // return false
return 0;
}
题型九：用队列实现栈
思路：
当数据1进栈，此时队列A入队数据1；
当数据2进栈，此时队列A的所有数据放到队列B，将数据2入队到队列A，再将队列B的数据1放到队列A里；此时队列A里有数据12，队头在1，对尾在2；
当数据3进栈，此时队列A的所有数据放到队列B，将数据3入队到队列A，再将队列B的数据12放到队列A里；此时队列A里有数据123，队头在1，对尾在3。
#include <stdio.h>
#include <stdlib.h>
typedef struct queue {
int *data;
// 头
int head;
// 实际使用大小， 尾
int rear;
// 容量大小
int capacity;
}Queue;
Queue *queueCreate(int cpacity) {
Queue *queue = malloc(sizeof(Queue));
queue->data = (int *)malloc(cpacity * sizeof(int));
queue->head = queue->rear = -1;
queue->capacity = cpacity;
return queue;
}
void enQueue(Queue *obj, int e) {
if (obj->head == -1) {
obj->head = 0;
}
// 超出限制从头开始
obj->rear = (obj->rear + 1) % obj->capacity;
obj->data[obj->rear] = e;
}
int deQueue(Queue *obj) {
int a = obj->data[obj->head];
if (obj->head == obj->rear) {
obj->rear = -1;
obj->head = -1;
return a;
}
// 超出限制从头开始
obj->head = (obj->head + 1) % obj->capacity;
return a;
}
int queueEmpty(Queue *obj) {
return obj->head == -1;
}
int queueGetHead(Queue *obj){
if (queueEmpty(obj)) {
return 0;
}
return obj->data[obj->head];
}
int queueGetRear(Queue *obj){
if (queueEmpty(obj)) {
return 0;
}
return obj->data[obj->rear];
}
// 将queue置空
void queueFree(Queue* obj) {
free(obj->data);
}
typedef struct {
Queue *queue1, *queue2;
}MyStack;
MyStack *myStackCreate(void) {
MyStack *obj = (MyStack *)malloc(sizeof(MyStack));
obj->queue1 = queueCreate(100);
obj->queue2 = queueCreate(100);
return obj;
}
void myStackPush(MyStack *obj, int x) {
if (queueEmpty(obj->queue1)) {
enQueue(obj->queue2, x);
} else {
enQueue(obj->queue1, x);
}
}
int myStackPop(MyStack *obj) {
if (queueEmpty(obj->queue1)) {
// 只剩一个元素
while (obj->queue2->head != obj->queue2->rear) {
enQueue(obj->queue1, deQueue(obj->queue2));
}
return deQueue(obj->queue2);
}
// 只剩一个元素
while (obj->queue1->head != obj->queue1->rear) {
enQueue(obj->queue2, deQueue(obj->queue1));
}
return deQueue(obj->queue1);
}
int myStackTop(MyStack *obj) {
if (queueEmpty(obj->queue1)) {
return queueGetRear(obj->queue2);
}
return queueGetRear(obj->queue1);
}
int myStackEmpty(MyStack *obj) {
return queueEmpty(obj->queue1) && queueEmpty(obj->queue2);
}
void myStackFree(MyStack *obj) {
queueFree(obj->queue1);
queueFree(obj->queue2);
}
int main(int argc, const char * argv[]) {
MyStack *myStack = myStackCreate();
myStackPush(myStack, 1);
myStackPush(myStack, 2);
int top = myStackTop(myStack); // 返回 2
int pop = myStackPop(myStack); // 返回 2
int empty = myStackEmpty(myStack); // 返回 0
return 0;
}
题型十：用栈实现自动释放池
Stack.h
#import <Foundation/Foundation.h>
@interface Stack : NSObject
- (id *)push;
- (void)autorelease:(id)obj;
- (void)pop:(id *)stop;
@end
Stack.m
#import "Stack.h"
#import <objc/runtime.h>
static size_t const SIZE = PAGE_MIN_SIZE;
static uint8_t const SCRIBBLE = 0xA3; // 0xA3A3A3A3 after releasing
# define POOL_BOUNDARY nil
@interface Stack() {
@package
__unsafe_unretained id * _next;
}
@end
@implementation Stack
- (instancetype)init
{
self = [super init];
if (self) {
_next = [self begin];
}
return self;
}
- (id *)push {
return [self add:POOL_BOUNDARY];
}
- (void)autorelease:(id)obj {
[self add:obj];
}
- (id *)add:(id)obj {
assert(!self.full);
id *ret = _next;
// *next = obj
// next = next + 1
*_next++ = obj;
return ret;
}
- (void)pop:(id *)stop {
while (self->_next != stop) {
id obj = *--_next;
// 0xA3A3A3A3
memset((void*)_next, SCRIBBLE, sizeof(*_next));
[obj release];
}
}
- (id *)begin {
// 头指针 + 结构体大小
return (id *)((uint8_t *)self + class_getInstanceSize(self.class));
}
- (id *)end {
return (id *) ((uint8_t *)self + SIZE);
}
- (BOOL)full {
return _next == [self end];
}
- (BOOL)empty {
return _next == [self end];
}
- (NSString *)description {
NSMutableString *all = [NSMutableString stringWithString:@"\n|----------------------Stack--------------------|\n"];
int index = 0;
id *next = self->_next;
while (next != self.begin) {
id *address = --next;
id obj = *address;
[all appendString:[NSString stringWithFormat:@"|--address:--%p---value:--%p--|\n", address,obj]];
index++;
}
return all;
}
@end
main.m
#import <Foundation/Foundation.h>
#import "Stack.h"
int main(int argc, const char * argv[]) {
NSObject *obj = [[NSObject new] retain];
NSObject *obj1 = [[NSObject new] retain];
NSObject *obj2 = [[NSObject new] retain];
NSLog(@"%ld", (long)CFGetRetainCount(obj2));
NSLog(@"%ld", (long)CFGetRetainCount(obj1));
NSLog(@"%ld", (long)CFGetRetainCount(obj));
Stack *stack = [Stack new];
void *ctx = [stack push];
[stack autorelease:obj];
[stack autorelease:obj1];
[stack autorelease:obj2];
NSLog(@"%@", stack);
// [stack pop:ctx];
NSLog(@"%@", stack);
void *ctx1 = [stack push];
[stack autorelease:obj];
[stack autorelease:obj1];
[stack autorelease:obj2];
NSLog(@"%@", stack);
[stack pop:ctx1];
NSLog(@"%@", stack);
// void *ctx = [stack push:obj];
// void *ctx1 = [stack push:obj1];
// void *ctx2 = [stack push:obj2];
// NSLog(@"%@", stack);
//
// [stack pop:ctx];
// [stack pop:ctx1];
// [stack pop:ctx2];
NSLog(@"%ld", (long)CFGetRetainCount(obj2));
NSLog(@"%ld", (long)CFGetRetainCount(obj1));
NSLog(@"%ld", (long)CFGetRetainCount(obj));
return 0;
}
网友评论