7_1base.cpp 图

发表于 2017-10-06 更新于 2020-06-08 分类于 b计算机基础/h_算法/算法学习过程/2017 阅读次数：
本文字数： 18k 阅读时长 ≈ 16 分钟

2017年10月6日下午4:15

图的存储结构

邻接矩阵
typedef struct 
{
	int no;
	char info;
}VertexType;

typedef struct 
{
	int edges[maxSize][maxSize];//邻接矩阵，若果是有权图，则在此句中将int改为float
	int n,e;//分别存放顶点数和边数
	VertexType vex[maxSize];//存放节点信息
}MGraph;


邻接表
typedef struct ArcNode
{
	int adjvex;
	struct ArcNode *nextarc;
	int info;
}ArcNode;


typedef struct VNode
{
	char data;
	ArcNode *firstarc;
}VNode;


typedef struct 
{
	VNode adjlist[maxSize];
	int n,e;
}AGraph;




图的遍历
int visit[maxSize];

void DFS(AGraph *G,int v){//输入：遍历哪个图中的哪个节点（这里的节点使用int类型表示的）
	ArcNode *p;//这里体现了图是以边(arc)为单位进行构建的，而不是节点。着一定一点要注意
	visit[v] = 1;
	visit(v);//cout<<v<<endl;

	p = G->adjlist[v].firstarc;//图比树多这么一步，原因在于下面的总结
	while(p != NULL){
		if(visit[p->adjvex] == 0){

			DFS(G,p->adjvex);//深度遍历当前p节点下的所有节点
		}
		p = p->nextarc;
	}
}




我要将当前节点（AGraph *G,int v）的相连的所有边都要遍历（p = p->nextarc）
树的当前节点（BTNode *bt） 遍历的是（bt->lchild  bt->rchild）
对比总结：
这一对比就体现出了树和图在struct类型定义时最大的不同：如何去找节点？
图中的节点是放在数组中的，我们想拿就必须通过数组下标。数组下标是int类型，所以我们在DFS函数传参只能是int类型。
如果一个图不是用int类型的数字去标识一个节点的话，例如使用A,B,C等，这些不能直接转换成图。或者说要在生成树的时候就必须人为的给他们编号。
总之，图中的每个节点必须从0开始编号！！！


总结树和图的不同（链式存储）：
树是以节点为单位的，图是以边为单位的
树可以直接寻找下一个节点，图必须以数组下表去寻找下一个节点，但图也可以直接通过当前边寻找下一条边。



广度优先遍历
基本思路：
要求是：我先把直接和我相连的节点看一遍，然后再按我看的顺序，和我第一个节点直接相连的节点，然后和第二个节点之间相连的节点......
做法：同样是涉及到一个“路径保存的问题”，这里使用队列


void BFS(AGraph *G,int v,int visit[maxSize]){
	
	if(G != NULL){
		// 定义一个队列
		int que[maxSize];
		int front = 0;
		int rear = 0;

		//初始化队列
		que[rear++] = v;//从传来的参数v开始
		visit[v] = 1;

		// 循环遍历开始，知道队列que为空
		while(front != rear){
			//从队列中取出一个节点
			int temp = que[++font];
			cout<<temp->adjvex<<endl;//temp带代表的是节点的下表，不是链表节点。这里错了

			//将这个节点下的直接相连的节点遍历，并放在队列中
			while(temp->nextarc != NULL){
				if(visit[temp->adjvex] == 0){
					que[rear++] = temp->adjvex;
				}
				temp = temp->nextarc;
			}

		}

	}
}


void BFS(AGraph *G,int v,int visit[maxSize]){
    
    if(G != NULL){
        // 定义一个队列
        int que[maxSize];
        int front = 0;
        int rear = 0;
        
        // 一个节点
        ArcNode *node;//这里是指针类型
        
        //初始化队列
        Visit(v);

        rear = (rear + 1)%maxSize;//是循环队列
        que[rear] = v;//从传来的参数v开始
        visit[v] = 1;
        
        // 循环遍历开始，知道队列que为空
        while(front != rear){
            //从队列中取出一个节点
            front = (front + 1)%maxSize;//是循环队列
            int temp = que[front];
            node = G->adjlist[temp].firstarc;//这句一定要注意，不能写错、少写
            
            //将这个节点下的直接相连的节点遍历，并放在队列中
            while(node->nextarc != NULL){
                if(visit[node->adjvex] == 0){
                	// 输出
                	Vist(p->adjvex);//实在如队列的时候输出。ps 我觉得队列输出的时候也行

                	visit[node->adjvex] = 1;//这里不要忘了赋值
                	rear = (rear + 1)%maxSize;//是循环队列
                    que[rear] = node->adjvex;
                }
                node = node->nextarc;
            }
        }
    }
}



总结：
BFS使用队列来记录遍历的过程，所以就不用使用递归了
忘了循环队列赋值
没有思考清楚什么时候输出
忘了node = G->adjlist[temp].firstarc;这个关键的一句。写图的遍历第一个想起来的就应该是这个。


非连通图的遍历
void dfs(AGraph *g){
	int i;
	for(i = 0; i<g->n;++i){//g是知道图中的节点个数的，这个我就忽略了
		if(visit[i] == 0){
			DFS(g,i);
		}
	}
}

void bfs(AGraph *g){
	int i;
	for(i = 0; i < g->n;i++){
		if(visit[i] == 0){
			BFS(g,i,visit);//这里不是递归，visit不是全局变量。所以这里把visit[]当做了参数传入
		}
	}
}


有向图和无向图，他们的遍历方式一样吗？
一样！
是否有向，只影响图的建立过程，不影响遍历过程。



（7-1）p190
我有个疑惑：一个节点可能多次遍历，在BFS和DFS中，我们使用的是visit[]作为是否遍历过的标志。在寻找最远节点时，如果出现重复遍历的情况，并且一进一远，路径长度该如何计算？
答案：按最近的算（没啥为啥，记住就行）


基本思路：一共就两种遍历方式BFS和DFS ，在这道题中使用BFS。在BFS上进行改进

输入：图G 和节点下标v
输出：最后一个节点

问题：如果多个节点都是最远的，输出哪个？
BFS输出最后一个，也就是队列最后一个


int BFS(AGraph *G,int v,int visit[maxSize]){
	// 输出队列最后一个，那么这就很简单了
	// front + 1 = rear 就是最后一个了
    
    if(G != NULL){
        // 定义一个队列
        int que[maxSize];
        int front = 0;
        int rear = 0;

        //队列中取出的节点
        int temp;
        
        // 一个节点
        ArcNode *node;//这里是指针类型
        
        //初始化队列
        Visit(v);

        rear = (rear + 1)%maxSize;//是循环队列
        que[rear] = v;//从传来的参数v开始
        visit[v] = 1;
        
        // 循环遍历开始，知道队列que为空
        while(front != rear){
            //从队列中取出一个节点
            front = (front + 1)%maxSize;//是循环队列
            temp = que[front];
            node = G->adjlist[temp].firstarc;//这句一定要注意，不能写错、少写

            //将这个节点下的直接相连的节点遍历，并放在队列中
            while(node->nextarc != NULL){
                if(visit[node->adjvex] == 0){
                	// 输出
                	Vist(p->adjvex);//实在如队列的时候输出。ps 我觉得队列输出的时候也行

                	visit[node->adjvex] = 1;//这里不要忘了赋值
                	rear = (rear + 1)%maxSize;//是循环队列
                    que[rear] = node->adjvex;

                }
                node = node->nextarc;
            }
            
        }
        
        return temp;//temp 存储了队列中拿出的最后一个节点名（下标）
    }
    return -1;
}


总结：
我就没有发现temp就直接存储了最后一个节点名（下标）。
我想到方法是每次遍历visit数组，只要visit全为1，我这时取出队列中的最后一个元素就行。


(7-2)p191
基本思路：还是那就话，遍历方式就那两种，没啥难度。关键之找到判断条件是最关键的地方。

我认为的判断条件：树是没有回路的，图有
书上给的判断条件：n-1条边的连通图，n为图中的顶点个数

边与顶点的数目是否满足条件可以由图的信息直接判断，连通与否可以用遍历能够访问到所有的节点来判断


我采用的是广度遍历，因为这个使用的是非递归，可以在函数的最后方便的添加功能，而递归就比较麻烦了
先遍历完，然后通过visit[]是否全部置1，来判断是否是连通图。

int BFS(AGraph *G,int v,int visit[maxSize]){
	// 输出队列最后一个，那么这就很简单了
	// front + 1 = rear 就是最后一个了
    
    if(G != NULL){
        // 定义一个队列
        int que[maxSize];
        int front = 0;
        int rear = 0;

        //队列中取出的节点
        int temp;
        
        // 一个节点
        ArcNode *node;//这里是指针类型

        //初始化队列
        Visit(v);

        rear = (rear + 1)%maxSize;//是循环队列
        que[rear] = v;//从传来的参数v开始
        visit[v] = 1;
        
        // 循环遍历开始，知道队列que为空
        while(front != rear){
            //从队列中取出一个节点
            front = (front + 1)%maxSize;//是循环队列
            temp = que[front];
            node = G->adjlist[temp].firstarc;//这句一定要注意，不能写错、少写

            //将这个节点下的直接相连的节点遍历，并放在队列中
            while(node->nextarc != NULL){
                if(visit[node->adjvex] == 0){
                	// 输出
                	Vist(p->adjvex);//实在如队列的时候输出。ps 我觉得队列输出的时候也行

                	visit[node->adjvex] = 1;//这里不要忘了赋值
                	rear = (rear + 1)%maxSize;//是循环队列
                    que[rear] = node->adjvex;
                }
                node = node->nextarc;
            }
        }
        int tag = 1;//tag = 1 是连通的

        //检查是否所有的visit[]都设置为1了
        for(int j = 0 ; j < G->n;j++){
        	if(visit[j] == 0){
        		tag = 0 ;//标志位不连通
        	}
        }

        if(tag == 0){//不连通，那么一定不是树
        	return 0;
        }
        else{
        	if((G->n - 1) == G->e){
        		return 1;
        	}
        	else{
        		return 0;
        	}
        }

    }
}

作者的思路：先通过dfs来计算出当前节点下，图的节点个数和边数；然后，和已知的G中的进行比较，通过比较结果是否相等来判断是否是树/是否连通

void DFS2(AGraph *G,int v ,int &vn,int &en){
	ArcNode *p;
	visit[v] = 1;
	++vn;//本题中当对当前定点的访问即为vn计数器自增1
	p = G->adjlist[v].firstarc;
	while(p != NULL){
		++en;//边数自增1
		if(visit[p->adjvex] == 0){
			DSF2(G,p->adjvex,vn,en);
		}
		p = p->nextarc;
	}
}

int GisTree(AGraph *G){
	int vn = 0;
	int en = 0;
	int i ;
	for(i = 0; i < G->n;++i){
		visit[i] = 0;
	}

	DFS2(G,1,vn,en);
	if(v == G->n && (G->n - 1) == en/2){
		return 1;
	}
	else{
		return 0;
	}

}


总结：这道题中也包含了两道小题，1.如何计算一个树的节点个数 2.如何计算一个边的个数
易错点：无向图中一个节点要在G中出现两次，所以，算出所有节点个数后要en/2来进行比较


总结：
现在遇见的关于给递归家参数的：
1.有外部变量 参数使用& 递归中只加不减  eg：图中统计节点和边的个数
2.有外部变量 参数使用& 递归中有加有减  eg：树中的p166思考题




（7-3）p192
先提出几个问题：
有向图如何遍历？对于有向图来说，不同的顶点开始遍历，很有可能造成不同的遍历结果（遍历的节点个数和边数都不一样）
eg p192我举的一个例子，用i点开始遍历，那么就能遍历到所有的点，而从i点开始遍历则遍历不到j点


题目分析：
我们一般的题目要求是无向图，那么这就说明了一颗树中的所有边和节点，从任意一点开始都可以遍历得到，最后结果的个边和节点的个数是相通的。
但是这道题他没有具体说明，但是我们可以设计一种判断方式，使得不区分有向还是无向。

答案：从顶点i开始DFS，遍历过程中遇到j，则说明连通

int DFSTrave(AGraph *G,int i , int j){
	int k;
	//visit置0
	for(k = 0;k < G->n;k++){
		visit[k] = 0;
	}

	DFS(G,i);

	if(visit[j] == 0){
		return 0;
	}
	else{
		return 1;
	}
}


最小生成树：只针对无向图！！！！！！！！！！！！！！！！
我是这么理解为啥这里只是针对于无向图？
因为：目的是生成最小生成树，要的是一个树的形状。一个形状我要你方向干啥。


普里姆算法
void Prim(MGraph g,int v0,int &sum){
	int lowcost[maxSize];
	int vest[maxSize];
	int v;
	int i , j ,k,min;

	v = v0;

	//0.手工处理第一个
	//将v0节点到各个节点的距离，放入lowcost中
	for(i = 0; i<g.n;i++){
		lowcost[i] = g.edges[v0][i];
		vest[i] = 0;
	}
	//放入第一个
	vest[v0] = 1;
	sum = 0;

	for(i = 0; i < g.n-1;i++){//单纯的计数，i不用，一共还要找g.n-1个
		min = INF;
		// 1.从lowcast中找到最小的边权值，并将次边值对应的节点取出（k）
		for(j = 0; j < g.n;j++){//就是一个数组中，我选取最小的值；这种简单的问题
			if(vest[j] == 0 && lowcost[j]<min){
				min = lowcost[j];
				k = j;
			}
		}

		// 2.找到之后做处理
		vest[k] = 1;
		v = k;
		sum +=min;

		// 3.对lowcast进行更新，在原来的基础上进行更改就行
		for(j = 0; j < g.n ;++j){//这里就是书本比我的方法强的地方，只需要一层循环，而我的这里需要二层循环
			// 理解成：两个一维数组相同位置比大小，根据结果赋值
			if(vest[j] == 0 && g.edges[v][j] < lowcost[j]){
				lowcost[j] = g.edges[v][j];
			}
		}
	}
}

总结:先提出问题，然后在解决问题的思路来说明这道题。
问题：如何选择当前生成树最小连接边？
回答：从lowcast中寻找没有使用，并且还是最小权值的节点

问题：如何给lowcast赋值？
回答：lowcast中保存的是当前子树和各个节点的最短距离权值。那么，我们将我们子树中的每一个节点，都计算一下他到各个没使用节点的距离，保存在lowcast中。到下一节点的时候，判断一下和上一个节点到相同节点的距离谁大谁小，然后小的保留在lowcast中。知道当前在子树的全部节点遍历完成。
书本回答：我的这种想法，没找到一个新的节点，那么所有的子树节点都要去遍历一次。而书中的方法，只需每次遍历新添加的那一个节点就行，原来的节点就不用管了。


总结：
我的抽象概括能力：
注意：由于这里涉及到权值，所有使用的是顺序结构

想到的一个问题：如何能打印出生成的最小生成树？
这里的算法是为了算最小生成树的权sum，是没有保存所选择的边的信息，只有零散的点，但不知道点之间是如何连接的。

重要总结：
我以前总结的（4+1） +  递归  +  想法转换成步骤
首先强调：要将思路和编程实现分开来思考
1.“想法转换成步骤”属于思路上的，他的目的是通过不断地测试，普通取样，特殊取样等等，最后找到所谓的“思路上的通解步骤”
2.“1”同样也是属于思路上的，他作为“想法转换成步骤”补充，因为：“1”是当出现问题难点的时候，解决问题的技巧，同样强调这是思路上的解决，尽量的联系上已知学过的简单知识点，把难点编程知识点的拼凑或者简单变形。
3.最后编码时才会去落实“4”，“4”能很大程度上减少我们的错误。这时出现问题，要跳出代码，返回1，2 去重新思考。



克鲁斯卡尔

typedef struct 
{
	int a,b;//a b 为一条边所连得两个顶点
	int w;//边的权值
}Road;


Road road[maxSize];
int v[maxSize];//定义并查集数组

int getRoot(int a){//在并查集中查找根节点的函数
	while(a != v[a]) a = v[a];
	return a;
}

void Kruskal(MGraph g ,int &sum,Road road[]){
	int i;
	int N,E,a,b;

	N =g.n;
	E =g.e;

	sum = 0;
	// 并查集初始化，各自为一个整体
	for(i = 0; i < N;i++){
		v[i] = i;
	}
	// 按边的权值，从小到大排序
	sort(road,E);
	// 每次拿road[]中最小的，判断是否有回路
	for(i = 0; i < E;i++){
		a = getRoot(road[i].a);
		b = getRoot(road[i].b);

		// 判断有没有回路
		if(a != b){
			// 更新并查集
			v[a] = b;
			// 更新权值和sum
			sum += road[i].w;
		}
	}
}

总结：
这道题的思路很简单：
1.先找出剩余边中最小的
2.检查是否有回路

补充总结1：
克鲁斯卡尔算法最牛的地方就是用一个数组去表示多棵树，执行算法的过程中，就是将这个数组中的各个树进行合并的过程。
数组中包含多种树：单独节点  两个节点  ....等多节点的树。目的就是他们连接起来，并且还不能有回路
并且发现了连接的手段：v[a] = b;这种连接手段不论ab是单独的节点，还是ab其中有一个已经不是单独节点，还是ab已经属于不同的多节点树，这一招都通用。

补充总结2：
注意这里的树的是没有结构的，给你的时候给的是一个以为数组，其中是图中的所有的边，但是他们是零散的，零散的！！！
简单是简单，但是针对于解决这个问题来说就足够了。

上面这两个步骤就是我以前总结出来的“想法转换成步骤”的思想，只不过这里不需要像树一样有很多特殊情况，步骤得一步步的测试，推倒。这里就是很简单的两两步
然后，我们就需要将这个步骤实现。这时我们使用“1”，如何找到最小，首先得给他们排序把。如何判断有回路，这个问题可以难死了？
最后书中给出了并查集的解法，这个很类似于数据库设计中的无限分类。关于这个解法，我的意见是直接记住，’检查是否有回路就用并查集来解决‘。



对比总结：
prim算法：是从中间向两边一点点的扩展的感觉
Kruskal：是站在一个稍微高点的角度从整体上去考虑了一下


我总是在担心如何获取权值的问题，这个可以从顺序图中直接获得每个点到其他所有点的权值。这是属于图如何建立的问题，而我们现在要想的问题是如何在已知建立好图之后，有效的使用图中的信息去做处理。
这时候就不能像建立图的内容！！！！！！！！！！！！！！！



最短路径
首先要明白他的最终目的：某一顶点到剩余顶点的最短路径。
与最小生成树对比，最短路径要的就不是一个形状，而是一个段路径，路径自然要考虑方向了！

迪杰斯特拉
void Dijkstra(MGraph g,int v,int dist[],int path[]){
	int set[maxSize];
	int min,i ,j,u;

	// 对各数组进行初始化
	for(i = 0; i < g.n;i++){
		// v到各个顶点的距离
		dist[i] = g.edges[v][i];
		// 标志该点是否并入最短路径中
		set[i] = 0;
		// 标志v0到vi最短路径上vi的前一个顶点
		if(g.edges[v][i] < INF){
			// 初始时，前一个顶点一定是v
			path[i] = v;
		}
		else{
			path[i] = -1;
		}
	}

	set[v] = 1;
	path[v] = -1;

	// 关键操作开始

	for(i = 0; i < g.n -1;i++){
		min = INF;
		// 遍历数组，挑选出数组中最小的值对应的节点
		for(j = 0; j < g.n;j++){
			if(set[j] == 0 && dist[j] < min){
				u = j;//保存位置
				min = dist[j];//获取最小值
			}
		}
		// 将u点，放入到最短路径中
		set[u] = 1;
		// 看看新并入的节点u，有没有让v到其节点(他没有使用的)的距离变短
		for(j = 0; j < g.n;j++){
			if(set[j] == 0 && dist[u]+g.edges[u][j] < dist[j]){
				dist[j] = dist[u] + g.edges[u][j];
				// path存放了v点到其余各顶点的最短路径
				// 只有在新添加的这个顶点u满足使v点到某个点j距离变短的情况下，这个某个点j才可以将自己的前驱设置为这个新添加的节点u
				path[j] = u;
			}
		}
	}
}

如何去理解一维数组：eg：path[]
可以把path[]理解成一组人，这组人只有一个共同的任务--记住自己的前驱。他们要清楚的知道在什么样的条件下才可以去更改自己的前驱，自己留心着点！
path[j] = u; 翻译过来就是：我是j，我的前驱要改变成u了（u也是一个人）


总结：
迪杰斯特拉和prim算法的基本思路是完全一样的：都是从中间向两边扩散
迪杰斯特拉在prim上改变的地方是：在添加了新的节点之后，我们要更新的是起始点v到其他顶点（没有使用的）的距离；而不是新生成子树到其他顶点的距离。简单的说，就是判断的条件发生了改变


问题：如何保存我们在生成最短路径时路径？
path[]来解决。
用来记录v点到其余各顶点的最短路径（每个节点记住自己的前驱就行，那么，我们就可以遍历这个数组来获得我们遍历的路径，前面的题中是不记录路径的）
问题：如何确定节点的前驱是谁？
每当当前最短路径中添加新的节点时，对于其他节点（没有使用的）来说，他们的对于原始点v0的最短距离就有可能发生变化。这时，就要对每一个其他点进行重新的判断处理。
只要其余节点（没使用的）到v0的距离发生改变，那么其余节点的前驱就会发生改变！！！！！！！！这两个是必然关系



问题：每当添加一个新的节点，那些数据需要发生变化？
1.其余节点（没使用的）到v0的最短距离
2.其余节点（没使用的）的前驱节点
注：这里一定是其余没有使用过的节点，已经包含在最短路径中的节点是不可以改变的，因为那条路已经选定了。
注：1一定会导致2



弗洛伊德算法：求任意两点之间的的最短路径长度 + 路径保存

void Floyd(MGraph g,int path[][maxSize]){
	int i, j, k;
	int A[maxSize][maxSize];

	// 双重循环对数组A[][]和path[]进行初始化
	for(i = 0; i < g.n;i++){
		for(j = 0; j < g.n; j++){
			A[i][j] = g.edges[i][j];
			path[i][j] = -1;
		}
	}

	for(k = 0; k < g.n; k++){
		for(i = 0; i < g.n;i++){
			for(j = 0; j < g.n; j++){
				if(A[i][j]>A[i][k]+A[k][j]){
					A[i][j] = A[i][k] + A[k][j];
					path[i][j] = k;
				}
			}
		}
	}
}


这本书中关于floyd算法讲的方式我不喜欢，我在网上找见了这个：
http://developer.51cto.com/art/201403/433874.htm

总结：
这本书中的最短路径两种求法都记录了路径，通过path数组，但是原理不同
弗洛伊德输出路径要使用递归：
void printPath(int u,int v ,int path[][max]){
	// 输出从u到v的路径
	if(path[u][v] ==  -1){
		cout<<v<<endl;
	}
	else{
		int mid = path[u][v];
		printPath(u, mid, path);
		// 输出的顺序是从左到右
		cout<<mid<<endl;
		printPath(u, mid, path);
	}
}

我觉得加上一句path[i][j] = k;没想到会起到这么神奇的效果！！！！我就想问个为啥？？？？
要想想通这个问题，首先也是要跳出代码，从思路上去分析。
那么，我们从头来，先提出一个问题：如何能在弗洛伊德算法的基础上记录上路径，而且是全部点的路径？
可以将每次两点之间依靠外界点来使距离变短时，可以使用path数组来表示：两点之间依靠于哪个点，使得距离变短。
假设u,v两点尝试完所有的g.n个时，在这过程中path[u][v]可能会变化多次。代表的意思是：在u,v两点之间，我试了所有的能插入一个点的情况，最后使得某一点，让u到v的距离最短。
注意：path只代表中间我只使用一个点来过渡，不包括2个3个等等。
但是这也足够了，因为我么可以在path中查任意两点依靠于哪一个点，使得距离最短。
不断地查，直到有两点之间不用依靠于其他点就可以达到最小权值距离为止。




拓扑排序p207

图中要提前有节点的入度统计count
typedef struct VNode
{
	char data;
	int count;
	ArcNode *firstarc;
}VNode;

基本思路：利用栈去临时保存入度为0的节点，然后从保存的入度为0的节点中随便找一个（栈中找栈顶的就行，反正随便一个就行）,把和他相邻的边去掉，把相连节点的入度减1
int TopSort(AGraph *G){
	// 返回1，代表这个拓扑任务可以完成

	int stack[maxSize],
	int top = -1;

	int i ;
	int n = 0;

	// 遍历整个所有的节点，然后将count == 0的放入到stack中
	for(i = 0; i < G->n;i++){
		if(G->adjvex[i].count == 0){
			// stack[++top] = G->adjvex[i];
			stack[++top] = i;//这里使用int类型就可代表一个节点，解决问题
		}
	}
	// 拿出一个来删除，更改一些东西。关键是要检查相邻的节点是否入度为0了，然后放入栈中
	while(top != -1){
		int temp = stack[top--];
		// 输出
		cout<<temp<<endl;
		//n++
		n++;
		// 处理相邻节点
		ArcNode *arc = G->adjlist[temp].firstarc;
		while(arc != NULL){
			// 修改相连节点入度
			int j = arc->adjvex;
			int count = G->adjlist[j].count--; 
			// 判断相连节点入度是否为0
			if(count == 0){
				stack[++top] = j;
			}
			arc = arc.nextarc;
		}
	}
	// 如果能是所有的节点入度都为0，说明这个拓扑代表的任务是可以完成的,即n == G->n，返回1
	if(n == G->n){
		return 1;
	}
	else{
		return 0;
	}
}

总结：
有两个地方有错：
1.一下想不起来栈是怎么定义的了，以及top=-1还是top = 0？
2.栈中保存的是int类型的节点，而不是VNode类型的节点。不是说VNode功能上完不成，而是小题大作。越简练越好


真题仿造 p213

（1）
基本思路：
题中要求的是有向图！
还让我想起来一个有向图与无向图之间的不同：在一个连通图中，如果这个图是有向的，随机的一个顶点开始遍历，有些点可能会便利不到。

那么这题就简单了，直接遍历DFS BFS都行，从Vi开始就行，如果能够到达vj,就成了。

int visit[maxSize]
int DFS(AGraph *G,int v, int vj){
	// return 1 代表找到
	//使用的数据结构是链式存储
	if(G != NULL){
		if(v == vj){
			return 1;
		}
		visit[v] = 1;
		// 找到当前节点第一个条边
		ArcNode *p = G->adjvex[v].firstarc;
		// 然后将没有遍历过得遍历了
		while(p != NULL){
			// 节点
			int temp = p->adjvex;
			if(visit[temp] != 0){
				if(DFS(G,temp) == 1){
					return 1;
				}
			}
			p = p->nextarc;
		}
		// 前面有两次返回1的机会：当前节点时vj或者是DFS返回的结果=1
		return 0;
	}
	return 0;
}




下面使用BFS
基本思路：当我遍历到一个节点时，我就要将他的连接的节点放入队列中，现在不用，要为以后做好准备。

int BFS(AGraph *G,int v,int vj){
	if(G != NULL){
		int que[maxSize];
		int front = 0;
		int rear  = 0;
		// 检查点
		int visit[maxSize];
		for(int i = 0; i < G->n; i++){//这句话也忘了
			visit[i] =0;
		}
		// 初始化
		rear = (rear + 1)%maxSize;
		que[rear] = v;
		visit[v] = = 1;//这句话忘了
		// 从队列中拿，然后放，直到队列为空
		while(front != rear){
			// 取出
			front = (front + 1)%maxSize;
			int temp = que[front];
			
			// 去G中找到
			ArcNode *arc = G->adjlist[temp].firstarc;
			// 把于temp相邻的节点都放队中
			while(arc != NULL){
				int n = arc->adjvex;
				if(visit[n] == 0){
					rear = (rear + 1)%maxSize;
					que[rear] = n;
					visit[n] = 1;//这句话忘了
				}
				arc = arc->nextarc;
			}
		}
	}
	if(visit[vj] == 0){
		return 0;
	}
	else{
		return 1;
	}
}

上面的是我的方法

int BFS(AGraph *G,int v,int vj){
	if(G != NULL){
		int que[maxSize];
		int front = 0;
		int rear  = 0;
		// 检查点
		int visit[maxSize];
		for(int i = 0; i < G->n; i++){//这句话也忘了
			visit[i] =0;
		}
		// 初始化
		rear = (rear + 1)%maxSize;
		que[rear] = v;
		visit[v] = = 1;//这句话忘了
		// 从队列中拿，然后放，直到队列为空
		while(front != rear){
			// 取出
			front = (front + 1)%maxSize;
			int temp = que[front];
			// 去G中找到
			ArcNode *arc = G->adjlist[temp].firstarc;
			// 把于temp相邻的节点都放队中
			while(arc != NULL){
				int n = arc->adjvex;

				if(n == vj){
					return 1;//其实在BFS的基础上加上这么一句话就可以了
				}

				if(visit[n] == 0){
					rear = (rear + 1)%maxSize;
					que[rear] = n;
					visit[n] = 1;//这句话忘了
				}
				arc = arc->nextarc;
			}

		}
	}
}

总结：这个书中的方法就是比我的要简单
判断书中是放在了出队列的，这样可以防止v和vj是同一点的时候。我在这里是放在了入队列的时候
只要在队列中出现了，那么一定可以遍历到

（2）p213
基本思路：
题中要求是有向图
DFS一个变量来统计遍历到的节点个数，和G->n作比较
这个题要遍历每一个节点，调用G->n次DFS函数



int visit[maxSize]
void DFS(AGraph *G,int v,int &n){
	//使用的数据结构是链式存储
	if(G != NULL){
		n++;

		visit[v] = 1;
		// 找到当前节点第一个条边
		ArcNode *p = G->adjvex[v].firstarc;
		// 然后将没有遍历过得遍历了
		while(p != NULL){
			// 节点
			int temp = p->adjvex;
			if(visit[temp] != 0){
				DFS(G,temp);
			}
			p = p->nextarc;
		}
	}
}


void print(AGraph *G){
	int i;
	int n = 0;
	for(i = 0; i < G->n; i++){
		// 忘了给visit清0了
		for(j = 0; j < G->n ;j++){
			visit[j] = 0;
		}
		// n清零
		n = 0;

		DFS(G,i);
		if(n == G->n){
			cout<<i<<endl;
		}
		
	}
}

总结:
两个地方容易忘：visit清空 于visit赋值


？？？？？？？？？？？？？？？？？？？没讲图的生成？？？？？？？？？？？？？？？？？？

写算法的思路总结（数据结构之后）

发表于 2017-10-06 更新于 2020-06-08 分类于 b计算机基础/h_算法/算法学习过程/2017 阅读次数：
本文字数： 724 阅读时长 ≈ 1 分钟

2017年10月6日下午4:15

概述

主要的目的是为了能够提升自己的分析问题的能力，这是脑力劳动，不局限于某一门语言的语法。
写程序就是一个自己提出问题，然后自己解决问题的过程。

正文：有个整体概念

我以前总结的（4+1） + 递归 + 想法转换成步骤
首先强调：要将思路和编程实现分开来思考

“想法转换成步骤”属于思路上的，他的目的是通过不断地测试，普通取样，特殊取样等等，最后找到所谓的“思路上的通解步骤”
“1”同样也是属于思路上的，他作为“想法转换成步骤”补充，因为：“1”是当出现问题难点的时候，解决问题的技巧，同样强调这是思路上的解决，尽量的联系上已知学过的简单知识点，把难点编程知识点的拼凑或者简单变形。
最后编码时才会去落实“4”，“4”能很大程度上减少我们的错误。这时出现问题，要跳出代码，返回1，2 去重新思考。

补充：这一步决定了你的算法能否成的70%

我现在对“把思路转换成步骤”，这一步比较有经验了，主要有以下几点

要特意的去考虑特殊情况
先抓主干去思考，然后再去找枝干（这样就条例很多了）
1. 枝干有一种情况值得专门的去注意一下，就是这里的并列情况

注：如何判断自己写程序的时候思路没有走偏，不用返工？这是否做好了，就这这个问题的答案

递归：这一神奇的偷懒方法

如何判断可否使用递归？
1. 将整个问题分成两部分：当前位置元素（1个）+后面所有元素（n-1个)———-整体的思想
2. 尾部中解决一个就删除一个———–简化思想，处理的问题规模越来越小
3. 永远解决的都是最后一个相同的问题————最终的目的
在能使用递归之后，如何真正的去写这个递归函数具体内容？
1. 其实我说的就是废话：一个函数，首先要确定的是：输入参数有啥，输出参数最后是啥。
2. 有哪些并列的情况，这个问题的答案就是函数的主体算法

2017/10/2 Mac中配置php的步骤记录

发表于 2017-10-02 更新于 2020-03-12 分类于 web开发/czh_blog/PHP 阅读次数：
本文字数： 24k 阅读时长 ≈ 22 分钟

2017年10月2日下午8:39

概述：

主要内容在
MAC下的java环境

安装brew

localhost:~ czh$ ruby -e "$(curl -fsSL https://raw.github.com/mxcl/homebrew/go/install)"
curl: (22) The requested URL returned error: 404 Not Found
localhost:~ czh$ brew doctor
-bash: brew: command not found
localhost:~ czh$ ruby -e "$(curl -fsSL https://raw.github.com/mxcl/homebrew/go/install)"
curl: (22) The requested URL returned error: 404 Not Found
localhost:~ czh$ ruby -e "$(curl --insecure -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"
==> This script will install:
/usr/local/bin/brew
/usr/local/share/doc/homebrew
/usr/local/share/man/man1/brew.1
/usr/local/share/zsh/site-functions/_brew
/usr/local/etc/bash_completion.d/brew
/usr/local/Homebrew
==> The following new directories will be created:
/usr/local/Cellar
/usr/local/Homebrew
/usr/local/Frameworks
/usr/local/bin
/usr/local/etc
/usr/local/include
/usr/local/lib
/usr/local/opt
/usr/local/sbin
/usr/local/share
/usr/local/share/zsh
/usr/local/share/zsh/site-functions
/usr/local/var

1 2	localhost:~ czh$ brew doctor Your system is ready to brew.

1	localhost:~ czh$ brew install brew-cask-completion

安装mysql

Last login: Sun Oct  1 23:33:35 on ttys001
localhost:~ czh$ brew install mysql
Updating Homebrew...
==> Auto-updated Homebrew!
Updated 1 tap (homebrew/core).
==> Updated Formulae
youtube-dl

==> Downloading https://homebrew.bintray.com/bottles/mysql-5.7.19.sierra.bottle.
######################################################################## 100.0%
==> Pouring mysql-5.7.19.sierra.bottle.tar.gz
==> /usr/local/Cellar/mysql/5.7.19/bin/mysqld --initialize-insecure --user=czh -
==> Caveats
We've installed your MySQL database without a root password. To secure it run:
    mysql_secure_installation

MySQL is configured to only allow connections from localhost by default

To connect run:
    mysql -uroot

To have launchd start mysql now and restart at login:
  brew services start mysql
Or, if you don't want/need a background service you can just run:
  mysql.server start
==> Summary
🍺  /usr/local/Cellar/mysql/5.7.19: 322 files, 233MB
localhost:~ czh$ ln -sfv /usr/local/opt/mysql/*.plist ~/Library/LaunchAgents
/Users/czh/Library/LaunchAgents/homebrew.mxcl.mysql.plist -> /usr/local/opt/mysql/homebrew.mxcl.mysql.plist
localhost:~ czh$ launchctl load ~/Library/LaunchAgents/homebrew.mxcl.mysql.plist
localhost:~ czh$ /usr/local/opt/mysql/bin/mysql_secure_installation

Securing the MySQL server deployment.

Connecting to MySQL using a blank password.

VALIDATE PASSWORD PLUGIN can be used to test passwords
and improve security. It checks the strength of password
and allows the users to set only those passwords which are
secure enough. Would you like to setup VALIDATE PASSWORD plugin?

Press y|Y for Yes, any other key for No: Y

There are three levels of password validation policy:

LOW    Length >= 8
MEDIUM Length >= 8, numeric, mixed case, and special characters
STRONG Length >= 8, numeric, mixed case, special characters and dictionary                  file

Please enter 0 = LOW, 1 = MEDIUM and 2 = STRONG: 0
Please set the password for root here.

New password:

Re-enter new password:

Estimated strength of the password: 50
Do you wish to continue with the password provided?(Press y|Y for Yes, any other key for No) : Y
By default, a MySQL installation has an anonymous user,
allowing anyone to log into MySQL without having to have
a user account created for them. This is intended only for
testing, and to make the installation go a bit smoother.
You should remove them before moving into a production
environment.

Remove anonymous users? (Press y|Y for Yes, any other key for No) : Y
Success.


Normally, root should only be allowed to connect from
'localhost'. This ensures that someone cannot guess at
the root password from the network.

Disallow root login remotely? (Press y|Y for Yes, any other key for No) : n

 ... skipping.
By default, MySQL comes with a database named 'test' that
anyone can access. This is also intended only for testing,
and should be removed before moving into a production
environment.


Remove test database and access to it? (Press y|Y for Yes, any other key for No) : n

 ... skipping.
Reloading the privilege tables will ensure that all changes
made so far will take effect immediately.

Reload privilege tables now? (Press y|Y for Yes, any other key for No) : Y
Success.

All done!

安装php

Last login: Mon Oct  2 08:25:24 on ttys000
localhost:~ czh$ brew install php70 --with-fpm --with-gmp --with-imap --with-tidy --with-debug --with-mysql --with-libmysql
Updating Homebrew...
==> Installing php70 from josegonzalez/php
==> Installing dependencies for josegonzalez/php/php70: gmp, icu4c, imap-uw, libxml2, unixodbc
==> Installing josegonzalez/php/php70 dependency: gmp
==> Downloading https://homebrew.bintray.com/bottles/gmp-6.1.2.sierra.bottle.1.t
######################################################################## 100.0%
==> Pouring gmp-6.1.2.sierra.bottle.1.tar.gz
🍺  /usr/local/Cellar/gmp/6.1.2: 18 files, 3.1MB
==> Installing josegonzalez/php/php70 dependency: icu4c
==> Downloading https://homebrew.bintray.com/bottles/icu4c-59.1.sierra.bottle.ta
######################################################################## 100.0%
==> Pouring icu4c-59.1.sierra.bottle.tar.gz
==> Caveats
This formula is keg-only, which means it was not symlinked into /usr/local,
because macOS provides libicucore.dylib (but nothing else).

If you need to have this software first in your PATH run:
  echo 'export PATH="/usr/local/opt/icu4c/bin:$PATH"' >> ~/.bash_profile
  echo 'export PATH="/usr/local/opt/icu4c/sbin:$PATH"' >> ~/.bash_profile

For compilers to find this software you may need to set:
    LDFLAGS:  -L/usr/local/opt/icu4c/lib
    CPPFLAGS: -I/usr/local/opt/icu4c/include

==> Summary
🍺  /usr/local/Cellar/icu4c/59.1: 246 files, 65.4MB
==> Installing josegonzalez/php/php70 dependency: imap-uw
==> Downloading https://homebrew.bintray.com/bottles/imap-uw-2007f.sierra.bottle
######################################################################## 100.0%
==> Pouring imap-uw-2007f.sierra.bottle.tar.gz
🍺  /usr/local/Cellar/imap-uw/2007f: 151 files, 9.0MB
==> Installing josegonzalez/php/php70 dependency: libxml2
==> Downloading https://homebrew.bintray.com/bottles/libxml2-2.9.5.sierra.bottle
######################################################################## 100.0%
==> Pouring libxml2-2.9.5.sierra.bottle.tar.gz
==> Caveats
This formula is keg-only, which means it was not symlinked into /usr/local,
because macOS already provides this software and installing another version in
parallel can cause all kinds of trouble.

If you need to have this software first in your PATH run:
  echo 'export PATH="/usr/local/opt/libxml2/bin:$PATH"' >> ~/.bash_profile

For compilers to find this software you may need to set:
    LDFLAGS:  -L/usr/local/opt/libxml2/lib
    CPPFLAGS: -I/usr/local/opt/libxml2/include


If you need Python to find bindings for this keg-only formula, run:
  echo /usr/local/opt/libxml2/lib/python2.7/site-packages >> /usr/local/lib/python2.7/site-packages/libxml2.pth
  mkdir -p /Users/czh/Library/Python/2.7/lib/python/site-packages
  echo 'import site; site.addsitedir("/usr/local/lib/python2.7/site-packages")' >> /Users/czh/Library/Python/2.7/lib/python/site-packages/homebrew.pth
==> Summary
🍺  /usr/local/Cellar/libxml2/2.9.5: 281 files, 10.4MB
==> Installing josegonzalez/php/php70 dependency: unixodbc
==> Downloading https://homebrew.bintray.com/bottles/unixodbc-2.3.4.sierra.bottl
######################################################################## 100.0%
==> Pouring unixodbc-2.3.4.sierra.bottle.2.tar.gz
🍺  /usr/local/Cellar/unixodbc/2.3.4: 43 files, 1.8MB
Warning: josegonzalez/php/php70: this formula has no --with-fpm option so it will be ignored!
Warning: josegonzalez/php/php70: this formula has no --with-mysql option so it will be ignored!
Warning: josegonzalez/php/php70: this formula has no --with-tidy option so it will be ignored!
==> Installing josegonzalez/php/php70 --with-gmp --with-debug --with-i
==> Downloading https://php.net/get/php-7.0.23.tar.bz2/from/this/mirror
==> Downloading from https://secure.php.net/get/php-7.0.23.tar.bz2/from/this/mir
######################################################################## 100.0%
==> ./configure --prefix=/usr/local/Cellar/php70/7.0.23_15 --localstatedir=/usr/
==> make
==> make install
==> Caveats
The php.ini file can be found in:
    /usr/local/etc/php/7.0/php.ini

✩✩✩✩ Extensions ✩✩✩✩

If you are having issues with custom extension compiling, ensure that you are using the brew version, by placing /usr/local/bin before /usr/sbin in your PATH:

      PATH="/usr/local/bin:$PATH"

PHP70 Extensions will always be compiled against this PHP. Please install them using --without-homebrew-php to enable compiling against system PHP.

✩✩✩✩ PHP CLI ✩✩✩✩

If you wish to swap the PHP you use on the command line, you should add the following to ~/.bashrc, ~/.zshrc, ~/.profile or your shell's equivalent configuration file:
  export PATH="$(brew --prefix homebrew/php/php70)/bin:$PATH"

GMP has moved to its own formula, please install it by running: brew install php70-gmp

✩✩✩✩ FPM ✩✩✩✩

To launch php-fpm on startup:
    mkdir -p ~/Library/LaunchAgents
    cp /usr/local/opt/php70/homebrew.mxcl.php70.plist ~/Library/LaunchAgents/
    launchctl load -w ~/Library/LaunchAgents/homebrew.mxcl.php70.plist

The control script is located at /usr/local/opt/php70/sbin/php70-fpm

OS X 10.8 and newer come with php-fpm pre-installed, to ensure you are using the brew version you need to make sure /usr/local/sbin is before /usr/sbin in your PATH:

  PATH="/usr/local/sbin:$PATH"

You may also need to edit the plist to use the correct "UserName".

Please note that the plist was called 'homebrew-php.josegonzalez.php70.plist' in old versions of this formula.

With the release of macOS Sierra the Apache module is now not built by default. If you want to build it on your system you have to install php with the --with-httpd24 option. See  brew options php70 for more details.

To have launchd start josegonzalez/php/php70 now and restart at login:
  brew services start josegonzalez/php/php70
==> Summary
🍺  /usr/local/Cellar/php70/7.0.23_15: 313 files, 42.1MB, built in 6 minutes 36 seconds
localhost:~ czh$ echo 'export PATH="$(brew --prefix php70)/bin:$PATH"' >> ~/.bash_profile  #for php
localhost:~ czh$ echo 'export PATH="$(brew --prefix php70)/sbin:$PATH"' >> ~/.bash_profile  #for php-fpm
localhost:~ czh$ echo 'export PATH="/usr/local/bin:/usr/local/sbib:$PATH"' >> ~/.bash_profile #for other brew install soft
localhost:~ czh$ source ~/.bash_profile
localhost:~ czh$ php -v
PHP 7.0.23 (cli) (built: Oct  2 2017 08:35:23) ( NTS DEBUG )
Copyright (c) 1997-2017 The PHP Group
Zend Engine v3.0.0, Copyright (c) 1998-2017 Zend Technologies
localhost:~ czh$

php简单配置

localhost:~ czh$ brew services restart php70
==> Tapping homebrew/services
Cloning into '/usr/local/Homebrew/Library/Taps/homebrew/homebrew-services'...
remote: Counting objects: 12, done.
remote: Compressing objects: 100% (8/8), done.
remote: Total 12 (delta 0), reused 7 (delta 0), pack-reused 0
Unpacking objects: 100% (12/12), done.
Tapped 0 formulae (40 files, 54.0KB)
==> Successfully started `php70` (label: homebrew.mxcl.php70)
localhost:~ czh$ lsof -Pni4 | grep LISTEN | grep php
php-fpm   62115  czh    8u  IPv4 0x95bccd2b0d57769      0t0  TCP 127.0.0.1:9000 (LISTEN)
php-fpm   62118  czh    0u  IPv4 0x95bccd2b0d57769      0t0  TCP 127.0.0.1:9000 (LISTEN)
php-fpm   62119  czh    0u  IPv4 0x95bccd2b0d57769      0t0  TCP 127.0.0.1:9000 (LISTEN)
localhost:~ czh$ ln -sfv /usr/local/opt/php70/*.plist ~/Library/LaunchAgents
/Users/czh/Library/LaunchAgents/homebrew.mxcl.php70.plist -> /usr/local/opt/php70/homebrew.mxcl.php70.plist
localhost:~ czh$ launchctl load ~/Library/LaunchAgents/homebrew.mxcl.php70.plist
/usr/local/Cellar/php70/7.0.23_15/homebrew.mxcl.php70.plist: service already loaded
localhost:~ czh$ brew install composer
Updating Homebrew...
==> Installing composer from josegonzalez/php
==> Downloading https://homebrew.bintray.com/bottles-php/composer-1.5.2.sierra.b
######################################################################## 100.0%
==> Pouring composer-1.5.2.sierra.bottle.tar.gz
==> Caveats
      composer no longer depends on the homebrew php Formulas since the last couple of macOS releases
      contains a php version compatible with composer. If this has been part of your workflow
      previously then please make the appropriate changes and `brew install php71` or other appropriate
      Homebrew PHP version.
==> Summary
🍺  /usr/local/Cellar/composer/1.5.2: 5 files, 1.8MB

安装nginx

localhost:~ czh$ composer --version
Composer version 1.5.2 2017-09-11 16:59:25
localhost:~ czh$ brew install nginx --with-http_geoip_module
==> Installing dependencies for nginx: pcre
==> Installing nginx dependency: pcre
==> Downloading https://homebrew.bintray.com/bottles/pcre-8.41.sierra.bottle.tar
######################################################################## 100.0%
==> Pouring pcre-8.41.sierra.bottle.tar.gz
🍺  /usr/local/Cellar/pcre/8.41: 204 files, 5.3MB
Warning: nginx: this formula has no --with-http_geoip_module option so it will be ignored!
==> Installing nginx
==> Downloading https://homebrew.bintray.com/bottles/nginx-1.12.1.sierra.bottle.
######################################################################## 100.0%
==> Pouring nginx-1.12.1.sierra.bottle.tar.gz
==> Caveats
Docroot is: /usr/local/var/www

The default port has been set in /usr/local/etc/nginx/nginx.conf to 8080 so that
nginx can run without sudo.

nginx will load all files in /usr/local/etc/nginx/servers/.

To have launchd start nginx now and restart at login:
  brew services start nginx
Or, if you don't want/need a background service you can just run:
  nginx
==> Summary
🍺  /usr/local/Cellar/nginx/1.12.1: 23 files, 1MB
localhost:~ czh$ nginx -t
nginx: the configuration file /usr/local/etc/nginx/nginx.conf syntax is ok
nginx: configuration file /usr/local/etc/nginx/nginx.conf test is successful
localhost:~ czh$ ln -sfv /usr/local/opt/nginx/*.plist ~/Library/LaunchAgents
/Users/czh/Library/LaunchAgents/homebrew.mxcl.nginx.plist -> /usr/local/opt/nginx/homebrew.mxcl.nginx.plist
localhost:~ czh$ launchctl load ~/Library/LaunchAgents/homebrew.mxcl.nginx.plist
localhost:~ czh$ sudo chown root:wheel /usr/local/Cellar/nginx/1.12.1/bin/nginx
Password:
Sorry, try again.
Password:
localhost:~ czh$

nginx的配置

localhost:~ czh$ vim /usr/local/etc/nginx/sites-available/default-ssl
localhost:~ czh$ vim /usr/local/etc/nginx/sites-available/phpmyadmin
localhost:~ czh$ mkdir -p /usr/local/etc/nginx/ssl
localhost:~ czh$ openssl req -new -newkey rsa:4096 -days 365 -nodes -x509 -subj "/C=US/ST=State/L=Town/O=Office/CN=localhost" -keyout /usr/local/etc/nginx/ssl/localhost.key -out /usr/local/etc/nginx/ssl/localhost.crt
Generating a 4096 bit RSA private key
.....................................................................................................................................................................++
.....................................................................++
writing new private key to '/usr/local/etc/nginx/ssl/localhost.key'
-----
localhost:~ czh$ openssl req -new -newkey rsa:4096 -days 365 -nodes -x509 -subj "/C=US/ST=State/L=Town/O=Office/CN=phpmyadmin" -keyout /usr/local/etc/nginx/ssl/phpmyadmin.key -out /usr/local/etc/nginx/ssl/phpmyadmin.crt
Generating a 4096 bit RSA private key
.........................................++
.....................................................................++
writing new private key to '/usr/local/etc/nginx/ssl/phpmyadmin.key'
-----
localhost:~ czh$ ln -sfv /usr/local/etc/nginx/sites-available/default /usr/local/etc/nginx/sites-enabled/default
/usr/local/etc/nginx/sites-enabled/default -> /usr/local/etc/nginx/sites-available/default
localhost:~ czh$ ln -sfv /usr/local/etc/nginx/sites-available/default-ssl /usr/local/etc/nginx/sites-enabled/default-ssl
/usr/local/etc/nginx/sites-enabled/default-ssl -> /usr/local/etc/nginx/sites-available/default-ssl
localhost:~ czh$ ln -sfv /usr/local/etc/nginx/sites-available/phpmyadmin /usr/local/etc/nginx/sites-enabled/phpmyadmin
/usr/local/etc/nginx/sites-enabled/phpmyadmin -> /usr/local/etc/nginx/sites-available/phpmyadmin
localhost:~ czh$ launchctl load -w ~/Library/LaunchAgents/homebrew.mxcl.nginx.plist
/usr/local/Cellar/nginx/1.12.1/homebrew.mxcl.nginx.plist: service already loaded
localhost:~ czh$ php -v
PHP 7.0.23 (cli) (built: Oct  2 2017 08:35:23) ( NTS DEBUG )
Copyright (c) 1997-2017 The PHP Group
Zend Engine v3.0.0, Copyright (c) 1998-2017 Zend Technologies
localhost:~ czh$ nginx.start
-bash: nginx.start: command not found
localhost:~ czh$ launchctl load -w ~/Library/LaunchAgents/homebrew.mxcl.nginx.plist
/usr/local/Cellar/nginx/1.12.1/homebrew.mxcl.nginx.plist: service already loaded
localhost:~ czh$ launchctl load -w ~/Library/LaunchAgents/homebrew.mxcl.php70.plist
/usr/local/Cellar/php70/7.0.23_15/homebrew.mxcl.php70.plist: service already loaded
localhost:~ czh$

nginx排错

1
2
3

localhost:~ czh$ nginx -t
nginx: [emerg] unknown directive "erver" in /usr/local/etc/nginx/sites-enabled/default:1
nginx: configuration file /usr/local/etc/nginx/nginx.conf test failed

报错[emerg] bind() to 0.0.0.0:80 failed (13: Permission denied)

czhdeMacBook-Pro:~ czh$ nginx -t
nginx: [warn] conflicting server name "localhost" on 0.0.0.0:80, ignored
nginx: the configuration file /usr/local/etc/nginx/nginx.conf syntax is ok
nginx: [emerg] bind() to 0.0.0.0:80 failed (13: Permission denied)
nginx: configuration file /usr/local/etc/nginx/nginx.conf test failed

czhdeMacBook-Pro:~ czh$ sudo nginx -t
Password:
nginx: [warn] conflicting server name "localhost" on 0.0.0.0:80, ignored
nginx: the configuration file /usr/local/etc/nginx/nginx.conf syntax is ok
nginx: configuration file /usr/local/etc/nginx/nginx.conf test is successful
czhdeMacBook-Pro:~ czh$

修改nginx配置文件

nginx完美支持thinkphp3.2.2(需配置URL_MODEL=>1pathinfo模式） - ThinkPHP框架

zhdeMacBook-Pro:~ czh$ sudo nginx -s reload
Password:
nginx: [warn] conflicting server name "localhost" on 0.0.0.0:80, ignored
czhdeMacBook-Pro:~ czh$ sudo nginx -s reload
nginx: [warn] conflicting server name "localhost" on 0.0.0.0:80, ignored
czhdeMacBook-Pro:~ czh$ sudo nginx -s reload
nginx: [emerg] directive "root" is not terminated by ";" in /usr/local/etc/nginx/sites-enabled/default:5
czhdeMacBook-Pro:~ czh$ sudo nginx -s reload
czhdeMacBook-Pro:~ czh$ sudo nginx -s reload
czhdeMacBook-Pro:~ czh$ sudo nginx -s reload
czhdeMacBook-Pro:~ czh$ sudo nginx -s reload
Password:
nginx: [warn] conflicting server name "localhost" on 0.0.0.0:80, ignored
czhdeMacBook-Pro:~ czh$ sudo nginx -s reload
nginx: [warn] conflicting server name "localhost" on 0.0.0.0:80, ignored
czhdeMacBook-Pro:~ czh$ sudo nginx -s reload
nginx: [warn] conflicting server name "localhost" on 0.0.0.0:80, ignored
czhdeMacBook-Pro:~ czh$ sudo nginx -s reload
nginx: [warn] conflicting server name "localhost" on 0.0.0.0:80, ignored

mac系统升级之后,出现错误,并排错

Last login: Sat Oct  7 10:09:27 on ttys000
localhost:~ czh$ sudo nginx -s reload
Password:
nginx: [warn] conflicting server name "localhost" on 0.0.0.0:80, ignored
nginx: [error] open() "/usr/local/var/run/nginx.pid" failed (2: No such file or directory)
localhost:~ czh$ sudo nginx -t
nginx: [warn] conflicting server name "localhost" on 0.0.0.0:80, ignored
nginx: the configuration file /usr/local/etc/nginx/nginx.conf syntax is ok
nginx: configuration file /usr/local/etc/nginx/nginx.conf test is successful
localhost:~ czh$ sudo nginx -s reload
nginx: [warn] conflicting server name "localhost" on 0.0.0.0:80, ignored
nginx: [error] invalid PID number "" in "/usr/local/var/run/nginx.pid"
localhost:~ czh$ sudo nginx -c /usr/local/etc/nginx/nginx.conf
nginx: [warn] conflicting server name "localhost" on 0.0.0.0:80, ignored
localhost:~ czh$ $ sudo nginx -s reload
-bash: $: command not found
localhost:~ czh$ sudo nginx -s reload
nginx: [warn] conflicting server name "localhost" on 0.0.0.0:80, ignored
localhost:~ czh$ ln -sfv /usr/local/opt/nginx/*.plist ~/Library/LaunchAgents
/Users/czh/Library/LaunchAgents/homebrew.mxcl.nginx.plist -> /usr/local/opt/nginx/homebrew.mxcl.nginx.plist
localhost:~ czh$ launchctl load ~/Library/LaunchAgents/homebrew.mxcl.nginx.plist
/usr/local/Cellar/nginx/1.12.1/homebrew.mxcl.nginx.plist: service already loaded
localhost:~ czh$

注：最后两句是设置开机启动

sudo nginx -s reload报错的原因

提问：
issued a nginx -s stop and after that I got this error when trying to reload it.
[error]: invalid PID number “” in “_var_run/nginx.pid”
That _var_run_nginx_pid file is empty atm.
What do I need to do to fix it?
回答:
nginx -s reload is only used to tell a running nginx process to reload its config. After a stop, you don’t have a running nginx process to send a signal to. Just run nginx (possibly with a -c _path_to_config_file)

新Mac的php环境配置笔记 2017/10

发表于 2017-10-02 更新于 2020-03-12 分类于 web开发/czh_blog/PHP 阅读次数：
本文字数： 3k 阅读时长 ≈ 3 分钟

2017年10月2日下午8:39

概述：

在安装mysql之前要可以安装很多小的软件，也可以不按。重要的是，如果这些小软件安装的过程中warring 或者 error就用纠结了，无所谓
Brew的安装指令原来的不能用了，如果下次还变，百度上查就行了，多试几个没事
sudo 更多使用Mac解决权限的问题，在ubuntu中更多的使用chown等指令，这是一个不同。遇见permission deny 要想sudo
最花时间的是nginx的配置文件，这里给出两个，原来我使用的是老朱的，这次就不行了，不知道为啥，我又找了一个可以了
php5.5以后关于数据库操作的函数废弃了很多，这点要注意，附录中有。
步骤代码在 2017/10/2 Mac中配置php的步骤记录

几个重要文档

最重要的

server {
        listen 80;
        server_name localhost;
        error_page 404 /404.html;
        error_page 500 502 503 504 /50x.html;
        location ~ \.php {
                root /var/www;
                fastcgi_pass 127.0.0.1:9000;
                include   fastcgi.conf;
                set $path_info "";
                set $fastcgi_script_name_new $fastcgi_script_name;

              if ($fastcgi_script_name ~*   "^(.+\.php)(/.+)$"  ) {
                        set $fastcgi_script_name_new $1;
                        set $path_info $2;
                }
                   

                        fastcgi_param   SCRIPT_FILENAME   $document_root$fastcgi_script_name_new;
                        fastcgi_param   SCRIPT_NAME   $fastcgi_script_name_new;
                        fastcgi_param   PATH_INFO $path_info;
        }

        location / {
                root /var/www;
                index index.php index.html index.htm;
                if (!-e  $request_filename){
                        rewrite ^(.*)$ /index.php$1 last;
                }
        }
    }


#测试php-fpm配置
php-fpm -t
php-fpm -c /usr/local/etc/php/5.6/php.ini -y /usr/local/etc/php/5.6/php-fpm.conf -t

#启动php-fpm——这个命令报错
php-fpm -D
php-fpm -c /usr/local/etc/php/5.6/php.ini -y /usr/local/etc/php/5.6/php-fpm.conf -D

#关闭php-fpm
kill -INT `cat /usr/local/var/run/php-fpm.pid`

#重启php-fpm
kill -USR2 `cat /usr/local/var/run/php-fpm.pid`

#也可以用上文提到的brew命令来重启php-fpm，不过他官方不推荐用这个命令了
brew services restart php56

#还可以用这个命令来启动php-fpm
launchctl load -w ~/Library/LaunchAgents/homebrew.mxcl.php56.plist


由于Mac自带了php和php-fpm，因此需要添加系统环境变量PATH来替代自带PHP版本。
echo 'export PATH="$(brew --prefix php56)/bin:$PATH"' >> ~/.bash_profile  #for php
echo 'export PATH="$(brew --prefix php56)/sbin:$PATH"' >> ~/.bash_profile  #for php-fpm
echo 'export PATH="/usr/local/bin:/usr/local/sbib:$PATH"' >> ~/.bash_profile #for other brew install soft
source ~/.bash_profile


sudo chown root:wheel /usr/local/Cellar/nginx/1.10.2_1/bin/nginx
sudo chmod u+s /usr/local/Cellar/nginx/1.10.2_1/bin/nginx

ln -sfv /usr/local/opt/php56/*.plist ~/Library/LaunchAgents
launchctl load ~/Library/LaunchAgents/homebrew.mxcl.php56.plist

更换php7.0

#关闭php-fpm
kill -INT `cat /usr/local/var/run/php-fpm.pid`

#php7.0
echo 'export PATH="$(brew --prefix php70)/bin:$PATH"' >> ~/.bash_profile  #for php
echo 'export PATH="$(brew --prefix php70)/sbin:$PATH"' >> ~/.bash_profile  #for php-fpm
echo 'export PATH="/usr/local/bin:/usr/local/sbib:$PATH"' >> ~/.bash_profile #for other brew install soft
source ~/.bash_profile

#php开机自启
ln -sfv /usr/local/opt/php70/*.plist ~/Library/LaunchAgents
launchctl load -w ~/Library/LaunchAgents/homebrew.mxcl.php70.plist

[assets/php配置笔记.pages]

附录：

MAC下的java环境

发表于 2017-10-02 更新于 2020-03-12 分类于 web开发/czh_java/非框架Web技术阅读次数：
本文字数： 97 阅读时长 ≈ 1 分钟

2017年10月2日下午8:39

Mac下安装及配置Eclipse - Mac.Manon - 博客园
 Mac下如何安装JDK - Mac.Manon - 博客园
 Mac下如何配置环境变量 - Mac.Manon - 博客园

2_3practice.cpp 线性表

发表于 2017-09-24 更新于 2020-06-08 分类于 b计算机基础/h_算法/算法学习过程/2017 阅读次数：
本文字数： 12k 阅读时长 ≈ 11 分钟

2017年9月24日下午4:15

#include<iostream>
using namespace std;

// 真题仿造
// 这里的题目要求我就不写出来了，看书就行

分析：这个是顺序表的合并，前面的合并是链表的
#define maxSize = 1000;

typedef struct 
{
	int data[1000];
	int lenght;
}SqlList;

void merger(SqlList *&L,int A[],int m,int n){
	int q = 0;
	int p = m;
	int k = m; 


	while(q){
		if(L.data[q] > L.data[p]){
			k = L.data[p];
			for(int i = p; i > q;i++){
				L.data[p] = L.data[p-1];
			}
			L.data[q] = k;

			q++;
			p++;
		}
		else{
			q++;
		}
	}
		
}

void insertElem(int A[],int m,int n){
	int i ,j; 
	int temp;
	for(i = m ;i < m+n;++i){
		temp = A[i];
		for(j = i -1; j >=0 && temp < A[j];--j){
			 A[j+1] = A[j];
		}

		A[j+1] = temp;//这里要记得+1，因为上面j在for中多移动了一位，这一位是没有走for循环过程的。
	}
}


// 总结：有一下几个问题
// 1.没有明确操作对象，这里是要你操作A[],而是Sqlist 
// 2.这里从右往左比较更加方便，边比较便移动，如果是从左边开始，则需要先找到位置，然后在写一个循环移动
// 3.最重要的问题：描述思路很模糊，造成写程序的时候模模糊糊，写不出来。
		// 改进的第一步：描述的时候，对于操作对象要使用语言变量（多种）来表示，不能说这个、那个的


// 思路描述：A中p->data 是否和B中的一个元素 q->data 相等，如果不相等那么就保留，如果不相等则从A中删除


typedef struct LNode
{	
	int data;
	struct LNode * next;
	
}LNode;

void difference(LNode *A,LNode *B){
	LNode *p = A;
	LNode *q = B->next;
	LNode *k;

	while(p->next != NULL){
		q= B->next;//每次开始新的一轮，要初始化q为B的开始节点
		while(q!= NULL){
			if(p->next->date == q->data){
				k = p->next;
				p->next = p->next->next;
				free(k);
				p= p->next;	
				break;
			}
			else{
				q = q->next;
			}
		}
		p=p->next;//如果最后没有找到一个q与p->next 的data相等 ，那么这个点就不删除，但是p要移动到下一位
	}
}

// 上面的两个注释地方是我没有考虑到的

// 比较书上的那个算法：他不是像我一样每次拿A中的一个和B中的全部进行比较。这样就降低的算法的复杂度。
// 我对待这种人家的算法比自己的好的情况：我选择直接记住，简单实用的方式
// 与这种方法配合的有一个pre指针，用来指向当前p的前一个。也就说他和p = p->next;同时出现

void difference(LNode *A,LNode *B){
	LNode *p = A->next;
	LNode *q = B->next;
	LNode *pre = A;//初始化
	LNode *r ;

	while(p!= NULL && q != NULL){
		if(p->data > q->data){
			pre = p;
			p = p->next;
		}
		else if(p->data < q->data){
			q = q->next;
		}
		else{
			//删掉
			r = pre->next;
			pre->next = pre->next->next;
			free(r);

			//重新配置p的指向
			p = pre->next;

		}
	}
}

// 总结：我在2_2中所说的，和高数题的分析思路有很大的相似，尤其是取特征和反向分析。
// 现在看来，取特征我还保留，这个反向分析其实不对。
// 应该按这节中的带明确变量的思路描述才是重点。然后按这个思路描述写成完整程序就很简单了。


// 综合应用题
// 基础题


// （3）
// 思路描述：将L.date中data[0]<->data[lenght - 1],data[1]<->data[lenght - 2].....直到data[i]<->data[lenght-i-1]，其中的i >= (lenght )/2
void reserver(SqlList *&L){
	int temp;
	int i;
	for(i = 0; i < (L.lenght-1)/2 ;i++){//这里的条件是< 不能是 <=  可以举例测试
		temp = L.data[i];
		L.data[i] = L.data[L.lenght -1 - i];
		L.data[L.lenght - 1 - i] = L.temp; 
	}
}

// 我对思路描述的要求：能做到一个不会的人，也能很快的理解写出程序，那么这个思路描述就成功了

// （4）
// 思路描述：i,j题目中说是合法的，所以不用判断了。顺序表的删除，这里要对L.lenght--。L.data[i] = L.data[j],L.data[i+1] = L.data[j+1] ,直到j=L.lenght 及到达最后顺序表的长度

void deleteSqList(SqlList *&L,int i ,int j ){
	int len = j - i ;
	int  k;
	for(k = j ; k < L.lenght;k++){
		L.data[k-len] = L.data[k];
	}

	L.lenght = L.lenght - k - 1;//这里要记得加个多减个1 
} 



// (5)
// 思路描述：两个指针i,j i从前向后，指向第一个大于头值的节点a;j从后向前，指向第一个小于头值的节点a。L.data[i]<->L.date[j]交换，i++,直到i > a;j++,直到j < a;接着交换，最后 i >=j 截止

void move(SqlList &L){
	int a= L.data[0;
	int i ,j;
	i = 0;
	j = L.lenght-1;

	int temp ;


	while(i < j){
		for(i++; i < j ; i++){
			if(L.data[i] > a)break;
		}

		for(j--; i < j ; j--){
			if(L.data[j] < a)break;
		}


		temp = L.data[i];
		L.data[i] = L.data[j];
		L.data[j] = temp;

 	}
}



#include<iostream>
using namespace std;

#define maxSize = 1000;

typedef struct
{
    int data[1000];
    int lenght;
}SqlList;


void move(SqlList &L){
    int a= L.data[0];
    int i ,j;
    i = 0;
    j = L.lenght;
    
    int temp ;
    
    
    while(i < j){
        for(i++; i < j ; i++){
            if(L.data[i] > a)break;
        }
        
        for(j--; i < j ; j--){
            if(L.data[j] < a)break;
        }
        
        if(i < j){//这个判断我就丢了，造成了中间两个元素4，6换了两次，等于没换。当第二次换的时候他没有执行上面的两个for循环，但是进行了i++,j++两个操作。
        			// 总结：外层循环while(i<j)并不能保证，里面的i<j,因为当满足i<j进入while循环之后，还是会操作i，j两个变量的
            temp = L.data[i];
            L.data[i] = L.data[j];
            L.data[j] = temp;

        }
        
    }
}

// 总结：关于边界条件的是最容易错的，最容易少的。这道题中的关于循环条件的注意点，还是那就话，记住就行了，不要研究为啥
// 一个原则：条件能多不能少。


// （6）
思路描述：这里说的是递增非空。保存start = i,我们直接L.data[i] == L.data[i+i]判断，循环i++直到 L.data[i]!=L.data[i+1],
此时将len = i - start,并从i+1到L.lenght-1循环向前移动len个长度；最后： i++,进行下一轮比较

i
void deleteRepeat(SqlList &l){
	int i;
	int j; 
	int start;
	int len ;


	while(i < L.lenght){
		start = i ;
		while(i < L.lenght && L.data[i]!=L.data[i+1]){
			if(L.data[i] == L.data[i+i])break;
		}
		len = i - start;

		for(j = i+1; j<L.lenght -1;j++){
			L.data[j-len] = L.data[j]; 
		}
		L.lenght -=len;

		i++;
	}
	
}



#include<iostream>
using namespace std;

#define maxSize = 1000;

typedef struct
{
    int data[1000];
    int lenght;
}SqlList;


void deleteRepeat(SqlList &L){
    int i = 0;
    int j;
    int start;
    int len ;
    
    
    while(i < L.lenght){
        start = i;
        while(i < L.lenght && L.data[i]==L.data[i+1]){
            i++;
        }
 


int main(){
    SqlList L;
    L.data[0] = 1;
    L.data[1] = 1;
    L.data[2] = 2;
    L.data[3] = 3;
    L.data[4] = 3;
    L.data[5] = 3;
    L.data[6] = 4;
    L.lenght = 7;
    
    deleteRepeat(L);
    
    int i = 0;
    for(i = 0; i < L.lenght ;i++){
        cout<<L.data[i]<<endl;
    }
    

    return 0;
}




 // 如若加上if(L.data[i] != L.data[i+i])break;其实没啥用，而且还会跳过最后一个i++，使i少1
 // 这里也说明了，在循环中一定要注意多一，少一情况的出现
//        while(i < L.lenght && L.data[i]==L.data[i+1]){
//            if(L.data[i] != L.data[i+i])break;
//            i++;
//        }
        
        len = i - start;
        
       if(len!=0){//这个判断加不加都行。加上是为了让自己更加放心，省事。
            for(j = i+1; j<L.lenght;j++){
                L.data[j-len] = L.data[j];
            }
            L.lenght -=len;
       }
       
        
//        i++;//这里的由于删除元素，i指向的元素会被动变化，所以不能直接使用i++
        i = start+1;
    }
    
}


// 总结：在编码阶段出现这些问题，很大程度是由于自己的思路描述没有描述清楚。
// 现在尝试一下从抽象到具体，分层次的进行描述方法。


// 题中说的是链表，shit 我用的顺序表

typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode;

思路描述：
删除一组重复数据为一个操作集，循环的条件是：p!= NULL;
保存起点
	s = p;
重复的个数
	i = 0；
	循环条件是p->data = p->next->data;每次i++
删除
	s->next = s->next->next;
	循环i次
循环
	p找到下一次循环的位置 p = s->next;

void deleteRepeat(LNode *&LNode){
	LNode *s;
	LNode *p = L->next;

	int i ;

	while(p!= NULL){
		s = p;
		i = 0;

		while(p->data == p->next->data)i++;

		while(i--){
			s->next = s->next->next;
		}

		p = s->next;
	}
}

int main(){
	LNode *L = (LNode *)malloc(sizeof LNode);
	L->next = NULL;
	LNode *r;
	r = L;


	int i = 5;
	while(--i){
		r->next = (LNode *)malloc(sizeof LNode);
		r->next->next = NULL;
		r= r->next;
	}

	p=L->next;
	for(i = 0;i < 3; i++){
		p->data = 1;

		p = p->next;
	}

	for(i = 3;i < 5; i++){
		p->data = 2;
		p = p->next;
	}

	p = L->next;

	while(p!= NULL){
		cout<<p->data<<endl;
		p = p->next;
	}

	return 0 ;
}

#include<iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode;

void deleteRepeat(LNode *&L){
    LNode *s;
    LNode *p = L->next;
    
    int i ;
    
    while(p!= NULL){
        s = p;
        i = 0;
    
        while(p->next != NULL && p->data == p->next->data){//上面少了p->next != NULL 。这就上以前总结的外层循环的条件，拿到循环内部很有可能是不满足的。
            i++;
            p=p->next;//上面少了这句，导致程序无法停止
        }
        
        while(i--){
            s->next = s->next->next;
        }
        
        p = s->next;
    }
}


int main(){
    LNode *L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *r;
    r = L;
    
    LNode *p;//新产生的
    
    int a[7] = {1,1,1,2,3,3,3};
    int n = 7;//数组长度
    int i ;
    
    for(i = 0; i < n ;i++){
        p = (LNode *)malloc(sizeof(LNode));
        p->data=a[i];
        p->next = NULL;
        r->next =  p ;
        
        r = p;
        
    }
    

    deleteRepeat(L);
    
    
    p = L->next;
    
    while(p!= NULL){
        cout<<p->data<<endl;
        p=p->next;
    }
    
    return 0 ;
}

// 总结：
// 再次强调循环条件的内部不一定满足！
// 我两次写的程序都造成了死循环，所以每次写循环都要专门思考一下是跳出循环的条件是啥，否能跳出循环

// 现在做一下总体的总结，因为上面的总结的小点多了之后，比较杂乱，不容易记忆。
// 总体总结：
// 分两部分：
// 第一部分：对思路描述的改进
// 第二部分：易错点的总结（以上总结那么多，其实汇总就是易错点而已。易错点是有他的标志的，抓住标志去解决问题）
// （这章完成之后要将这些标志全部总结在一起）

// (7)
// 思路描述：
// 先找到
// 	假设第一是做小的min = L->next;
// 	p = L->next;
// 	pre = L;
// 	q用来跟随p

// 	判断的条件是：p->data < min->data;则min = p;pre = q;
// 	然后q = p;p= p->next;
// 	知道p=NULL;
// 在删除
// 	由于要删除，所以要在找的过程中保留pre节点。
// 	pre->next = pre->next->next;


void deleteMin(LNode *&L){
	LNode *p= L->next;
	LNode *q= L;

	LNode *min = L->next;
	LNode *pre = L;
	LNode *temp;


	while(p!=NULL){
		if(p->data < min->data){
			min = q;
			pre = p;
		}
		else{
			q = p;
			p = p->next;
		}
	}

	temp = pre->next;
	pre->next = pre->next->next;
	free(temp);

}


#include<iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode;

void deleteMin(LNode *&L){
    LNode *p= L->next;
    LNode *q= L;
    
    LNode *min = L->next;
    LNode *pre = L;
    LNode *temp;
    
    
    while(p!=NULL){
        if(p->data < min->data){
            min = p;
            pre = q;
        }
        //这里是不能有条件判断的，又没有注意循环的跳出，造成了死循环
        q = p;
        p = p->next;
    }
    
    temp = pre->next;
    pre->next = pre->next->next;
    free(temp);
    
}


// （8）
// 思路描述：
// 采用头插法；
// 编造一个带头元素的头结点：
// 	p = L->next->next;
// 	L->next = NUll;
// 使用头插法插入：
// 	q= p->next;

// 	p->next = L->next;
// 	L->next = p;

// 	p=q;
// 循环直到p==NULl



void reverter(LNode *&L){
	LNode *p = L->next->next;
	L->next = NULL;

	LNode *q;

	while(p!=NULL){
		q = p->next;
		p->next = L->next;
		L->next = p;
		p = q;
	}

}


#include<iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode;



void reverter(LNode *&L){
    LNode *p = L->next->next;
    L->next->next = NULL;//这里不能是 L->next 的意思是：只要L，L后面的不要了，而我们的要求是：L 后面从第二开始要了，而不是第一个。
    
    LNode *q;
    
    while(p!=NULL){
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }    
}

// （9）
// 思路分析：
// 对A来说是删除，所以要保存前节点
// 对B来说是添加

// pre = L;
// p = L->next;

// 删除A，并添加B
// pre = p; p=p->next;
//  pre->next = pre->next->next; 
//  r->next = p; r = r->next;
// p=p->next;

// 直到p = NULl


void split2(LNode *&L){
	LNode *pre = L;
	LNode *p = L->next;
	// 建立B头结点
	LNode *B = (LNode *)malloc(sizeof(LNode));
	// 把第一偶数拿过来
	B->next = L->next->next;
	B->next->next = NULL;
	//使用尾插法
	LNode *r = B->next;


	while(p!=NULL){
		// 删除之前保存下来
		pre = p;
		p=p->next;

		pre->next = pre->next->next;

		r->next = p;
		p->next = NULL;
		r=r->next;
		// 恢复p，指向下一个奇数，再次循环
		p=pre->next;


	}
}


void split2(LNode *&L){
    LNode *pre = L;
    LNode *p = L->next;
    // 建立B头结点
    LNode *B = (LNode *)malloc(sizeof(LNode));
    B->next = NULL;
    
    LNode *r = B;
    
    while(p!=NULL){
        // 删除之前保存下来
        pre = p;
        p=p->next;
        
        if(p!=NULL){//p==NULL 说明此时pre为最后一个元素，让pre在A里面就行，不用动
            pre->next = pre->next->next;
            
            r->next = p;
            p->next = NULL;
            r=r->next;
            // 恢复p，指向下一个奇数，再次循环
            p=pre->next;

        }
        
    }
}

// 总结：
// 遇见奇偶问题时一定区分来考虑
// 尽量不要把第一个处理点拿出循环单独处理。

3_2thinking.cpp 栈和队列

发表于 2017-09-24 更新于 2020-06-08 分类于 b计算机基础/h_算法/算法学习过程/2017 阅读次数：
本文字数： 1.1k 阅读时长 ≈ 1 分钟

2017年9月24日下午4:15

// (1)p78
float sqart(float A,float p ,float e){//不能写成int sqart(int A,int p , int e)，要使用float类型，这里涉及到了浮点运算
	if(fabs(p*p - A) < e){
		return p;
	}
	else{
		return sqart(A,(p+A/p)/2,e);
	}
}



第二层：抓住区别
递归的参数改变 = 下回循环的初始化
递归的出口 = 循环的出口


float sqart(float A,float p , float e){

	while(fabs(p*p - A) >= e){//这里条件反了，不能是fabs(p*p - A) < e
		p = (p+A/p)/2;
	}

	return p;
}

总结:
当递归算法代码中只有一个递归语句，并且在程序的最后的话，可以直接改写成循环形式

// （2）p78
void perm2(char str[],int k , int n){
	int i ,j; 
	char temp ;
	if(k == 0){
		for(j = 0 ;j <= n-1;++j){
			cout<<str[i];
		}
	}
	else{
		for(i = 0; i <= k ;++i){
			temp = str[k];
			str[k] = str[i];
			str[i] = temp;

			perm2(str,k-1,n);

			temp = str[i];
			str[i] = str[k];
			str[k] = temp;
		}
	}
}



dp + 回溯+分治教会了我们怎样的思考问题的方式（这里我是回忆了刘汝佳的入门白皮书,因为有好几道题是用递归解决的，我的思路上有问题）
1.有些问题我们发现他的特点是：问题在某一个特定的情况下特别简单，特定的情况一般都是指的元素个数少（比如说两个数进行排序）等等，弱者都会的问题。但是当相同的问题，横向
扩充后，就会变得异常复杂。这时，我们能不能将问题在变回原来弱智的问题去解决？这就需要我们从内--->外去解决，让问题变成一个个弱者的问题，然后就轻松的解决了。
那么，递归就给了我们一个进入到内部的方式。
2.而回溯，其实就是一种循环。他的步骤中每次循环（一层递归）都维持着解的一部分（这是他与1的最大的思路的不同的点），这也就是为啥我把他也称作是循环。

2_4thinking.cpp 线性表

发表于 2017-09-24 更新于 2020-06-08 分类于 b计算机基础/h_算法/算法学习过程/2017 阅读次数：
本文字数： 4.7k 阅读时长 ≈ 4 分钟

2017年9月24日下午4:15

(1)
思路描述：
使用冒泡法。但是会交换变量，一个变量i不够用。这种方式不行；
i%10
i/10

i = 0*10 + 0 ;
while(i/10 < N-1){
	if(A[i/10] < A[i/10 + 1]){
		i = i/10 * 10 + A[i/10];
	}
	i = (i/10 +1) * 10 + A[i/10];
}

cout<<(i%10)<<endl;


#include<iostream>
using namespace std;
#define N  9
int main(){
    int i = 0;
    int A[N] = {8,2,3,4,5,6,7,1,9};
    i = 0 * 10 + A[0];//这里不能写成i = 0*10 + 0，否则0会作为比较的对象；这里用A中的谁都行
    
    while(i/10 < N-1){
        if(A[i/10] < i%10){//A[i/10] < A[i/10 + 1] 这里的比较对象错了。
            i = i/10 * 10 + A[i/10];
        }
        i = (i/10 +1) * 10 + i%10;
    }
    
    cout<<(i%10)<<endl;
}


// (2)
// 思路描述:
// 这要求L指向开始节点。
// 先统计一下一共有i个节点
// 然后统计每次i--;

void reprint(LNode *&L){
	LNode *
	while()
}

// 书本解释：在表不为空的情况下先递归的逆序打印表中的第一个数据之后的数据
我的解释：题可以这样理解：先打印出当前节点后面的data值，然后再打印当前节点的data值。
如果这么理解，把这句话翻译成程序的时候，不就自然使用递归了吗。
关键是你不会这么想
void rePrint(LNode *&L){
	if(L! = NULL){
		rePrint(L->next);
		cout<<L->data<<" ";
	}
}




// (3)
// 这道题中的一个条件3n/2这个条件，
// 我认为需要两个变量max min ，每次循环到一个A[i]的时候，就要比较两次，那么一共就要比较2n次
// 但是我忽略了min 和 max是相互矛盾的，所以比较一次就行了

// 其实也可以这样理解：书中的这种解法，就是抓住了矛盾，然后将我的算法优化了。
// 所以，优化的时候抓住矛盾对立面也是一种优化方式
void FindMaxMin(int A[],int n,int &max,int &min){
	max = min = A[1];
	for(int i = 2; i <= n;++i){
		if(A[i] > max){
			max = A[i];
		}
		else if(A[i] < min ){
			min = A[i];
		}
	}
}




// 综合应用题

// (1)
思路描述：
每个递归传入的都是i= 0；
先查询出当前节点后面的节点的个数，
然后自己本节点再i++;
判断自己是不是i==5
如果是则输出，并break
最后返回i，给上一个层


int findElem(LNode *&L,int i){

	if(L! = NULL){
		i = rePrint(L->next,i);
		i++;

		if(i==5){
			cout<<L->data<<" ";
			break;
		}
		return i;

	}
}



#include<iostream>
using namespace std;


typedef struct LNode{
    int data;
    struct LNode *next;
}LNode;


int findElem(LNode *&L){//由于这里每次都是传入i=0，所以可以直接写在程序里，不用作为参数。
    int i = 0;
    if(L != NULL){
        i = rePrint(L->next);
        i++;
        
        if(i==5){
            cout<<L->data<<endl;
            return 1;
        }
        return i;
        
    }
    return 0;
}

int main(){
    LNode *L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *r;
    r = L;
    
    LNode *p;//新产生的
    
    int a[7] = {1,2,3,4,5,6,7};
    int n = 7;//数组长度
    int i ;
    
    for(i = 0; i < n ;i++){
        p = (LNode *)malloc(sizeof(LNode));
        p->data=a[i];
        p->next = NULL;
        r->next =  p ;
        
        r = p;
        
    }
    findElem(L);
    
    
}



// 总结：我的这种使用递归的解法启发来源于上面的题，我在原来的基础上添加了返回值，也按上面说的把题概括成了能用递归来实现的语言。
// 但是我忽略了，题中要求返回值=1 代表成功，=0代表失败，这就说明我不能用返回值来表示层数，这就混乱了。
// 因此，我的解法是错的。


int findElem(LNode *&L){
	LNode *p = L->next;
	LNode *q = L;
	int i = 0;

	while(p!= NULL){

		p=p->next;
		i++;
		if(i>=5){ //这里不能写等于，大于5之后还有继续后移呢。
			q = q->next;
		}
	}

	if(q == L ){
		return 0;
	}
	else{
		cout<<q->data<<endl;
		return 1;
	}
		
}

// 总结：
// 我一开始的分析思路是：
// 第一步先循环到第5个
// 第二步判断是否有五个，如果有才开始从这里q才开始q = q->next;
// 如果没有5个直接return 0；

// 其实上面这的写程序也没问题。但是像书中的程序，他将第一步和第二步进行的融合，最后对于有没有5个，融合之后也有了统一的判断标准。

整体总结：
这篇thinking的题真的需要你思考
这些题不仅仅需要我们有在practice中总结的思维描述+特征
还加上了一些在完成功能的情况下，如何将代码进行优化，多个步骤的融合（上面这道题）+ 解决问题的技巧（第一道题） + 选择递归（第二题，需要对题进行递归的概括）+不是能完成功能的就是对的（上面这道题）


prictice :保证不要在思考算法过程中，还在为操作发愁。即便有了思维还担心自己写不出来，或者写的过程中被打断
thinking :需要一些思考，设计一些算法了。不是那种一看题就会的了。


// 如何提高自己设计算法的效率。

// （2）
// 基本思想：利用模n，比如说R[i]--> R[n-(k-i)] R[n-(k-i)]-->R[n-(k-i)]
// 实现步骤：

// 这道题我不会做！我知道最笨的方法。一个个移动。
// 问题出现哪里？：找不到其中的特点，不会使用其中的技巧。
这些题不是不会做，是找不到更好的方法。
好方法来源于哪呢？

void Reverse(int R[],int l ,int r){
	int i,j;
	int temp;
	for(i = l,j = r;i<j;++i,++j){
		temp = R[i];
		R[i] = R[j];
		R[j] = temp;
	}
}


void RCR(int R[],int n,int p){
	if(p<0||p>n){
		cout<<"ERROR"<<endl;
	}
	else{
		Reverse(R,0,p-1);
		Reverse(R,p,n-1);
		Reverse(R,0,n-1);
	}
}


// （3）
基本思想：计算全部元素出现的次数，直达一个元素个数过半。
优化：添加一个数组，标志每个元素是否已被查询过
实现步骤：双层循环遍历，复杂度（n方）

书中的算法：自己是肯定想不出来，我们不可能去推理证明这种算法的正确性，直接背会。
这些算法是其实是需要严格的理论证明，才可以使用的。
给我的感觉就是一道高数题，让你证明这个理论是正确的。

这么做的目的：将复杂度降为n（n)

int majority(int A[],int n){
	int i ,c ,count=1;
	c = A[0];
	for(i= 1; i<n;i++){
		if(A[i]==c){
			count++;
		}
		else{
			if(count > 0){
				count--;
			}
			else{
				if(cout>0){
					count--;
				}
				else{
					c= A[i];
					count= 1;
				}
			}
		}
	}


	if(count > 0 ){
		for(i = count = 0 ; i < n ;i++){//将count的清零，放在了for中
			if(A[i] == c){
				count++;
			}
		}
	}

	if(count>n/2){
		return c;
	}
	else{
		return -1;
	}


}

3_1base.cpp 栈和队列

发表于 2017-09-24 更新于 2020-06-08 分类于 b计算机基础/h_算法/算法学习过程/2017 阅读次数：
本文字数： 9.9k 阅读时长 ≈ 9 分钟

2017年9月24日下午4:15


// 第三章：栈和队列

// 他们两个都是两种实现方式：顺序表+链表

// 原则：不管是栈还是队列，能用顺序表就用顺序表，因为链表操作起来要复杂不少。特别是队列的链表，有少地方需要特殊处理。

// 记忆的重点：他们的判空、判满条件+增加/删除的操作步骤。（这个是要直接背会的，除了队列的链表）


// （1）p71
// 模仿书本上讲述一个概念的步骤：
// 结构体定义  判空判满条件 增加/删除操作


#define maxSize 100

typedef struct 
{
	int data[maxSize];
	int topS0;
	int topS1;
}SqStack;

判空：topS0 = -1 topS1 = maxSize;
盘满：topS0+1 = topS1 / topS1 -1 = topS0

增加：
	盘满

	topS0++;
	st.data[topS0] = x

	topS1--;
	st.data[topS1] =x;

减少：
	判空

	x = st.data[topS0]
	topS0--;

	
	x = st.data[topS1];
	topS1++;


int push(SqStack *&st,int stNo ,int x){//这个接口的选择其实也需要你分析，比如说这里的int stNo，我就没有意识到要有这么一个参数

	if(st.topS0 + 1 = topS1 ) return 0;
	if(stNo == 0){

		topS0++;
		st.data[topS0] = x;
	}
	else{
		topS1--;
		st.data[topS1] =x;
	}

	return 1;
}


int pop(SqStack *&st,int stNo,int &x){
	if(stNo == 0){
		if(st.topS0 == -1) return 0;
		x = st.data[st.topS0];
		st.top--;

	}
	else{
		if(st.topS0 == maxSize) return 0;
		x = st.data[st.topS1];
		st.top++;
	}

	return 1;
}



#include<iostream>
using namespace std;


#define maxSize 2

typedef struct
{
    int data[maxSize];
    int topS0;
    int topS1;
}SqStack;

int push(SqStack &st,int stNo ,int x){//这个接口的选择其实也需要你分析，比如说这里的int stNo，我就没有意识到要有这么一个参数
//    接口不能写成push(SqStack *&st,int stNo ,int x),这个参数不能使用SqStack *&st。哥你这现在操作的是顺序表，不是链表，没有指针类型，不要搞笑好吗！
    
    if(st.topS0 + 1 == st.topS1 ) return 0;
    if(stNo == 0){
        
        st.topS0++;
        st.data[st.topS0] = x;
    }
    else{
        st.topS1--;
        st.data[st.topS1] =x;
    }
    
    return 1;
}


int pop(SqStack &st,int stNo,int &x){
//    我要重新梳理一下* 和 & 的用法，混了。*在参数中由传过来参数的类决定，而&是用来说明我用不用重新生成一个新的变量，还是使用传过来的那个变量（一个空间两个名字而已，记住这句话）。
    if(stNo == 0){
        if(st.topS0 == -1) return 0;
        x = st.data[st.topS0];
        st.topS0--;
        
    }
    else{
        if(st.topS0 == maxSize) return 0;
        x = st.data[st.topS1];
        st.topS0++;
    }
    
    return 1;
}


int main(){
    SqStack st;
    st.topS0 = -1;
    st.topS1 = maxSize;//定义完一个结构体，要记得初始化其中的一些变量。我第一次这里设置成了-1，shit
    int i;
    int x;
    
    
    cout<<push(st,0,100)<<endl;
    cout<<push(st,0,100)<<endl;
    cout<<push(st,0,100)<<endl;
    
//    cout<<pop(st,0,x)<<endl;
//    cout<<"x="<<x<<endl;
//
    for(i =0;i < st.topS0;i++){
        cout<<st.data[i]<<endl;
    }
    
}




// 总结：
第一点：语法都错。我觉得这里的原因还是自己没有意识，没有错过。比如说这里的.和-> 只要稍微考虑一下也就知道了，并不是不知道。
第二点：赋初值也没有注意

所以：以前说的特征+思路描述 + 背算法这三个肯定是重中之重，但是，易错点也是特别需要留心的。程序这东西错一点就完蛋,这种一般都是没有专门来考虑引来的祸





// （2）p71
基本思想：栈是FILO，编程队列之后，需要取到栈底的那个元素，哪我们能如何拿到呢？把栈中的元素倒入到另一个栈中，那么最后一个就在上面了。
这道题不会做，反思过来，是我在分析的时候没有把问题具体化（像上面分析一样），问题不明确，自然找不到答案！！！

实现步骤：
实现的重点是：栈的倒替



入队：只能从st中入
int	enQueue(SqStack &st,SqStack &rst,int x){
	//st判满
	if(st.top == maxSize-1) return 0;

	//确保st中有值，而不是在rst中
	if(!isEmpty(rst)){
		if(reserve(st,rst) ==0 )return 0;
	}


	//push
	push(st,x);
	
	return 1;
}

出队：只能从rst出
int deQueue(SqStack &st,SqStack &rst,&x){

	//全空不能出队
	if(isEmpty(st)&&isEmpty(rst)) return 0 ;


	//保证值在rst中
	if(!isEmpty(st)){
		if(reserve(st,rst)==0)return 0 ;
	}

	//pop
	pop(rst,x);
}
int isQueueEmpty(SqStack &st){
	//全空
	if(isEmpty(st)&&isEmpty(rst)) return 0 ;


}


int reserve(SqStack &st,SqStack &rst){
	//全空
	if(isEmpty(st)&&isEmpty(rst)) return 0 ;

	//翻转
	int x;

	if(!isEmpty(st)){
		//利用pop 和 push,直到st为空，isEmpty()
		while(!isEmpty(st)){
			pop(st,x);

			push(rst,x);
		}
	}
	else{
		while(!isEmpty(rst)){
			pop(rst,x);

			push(st,x);
		}
	}

	return 1;

}




// (1)p61

这些题就不要想自己能不能设计出一种算法来解决问题。
是要问自己，别人想好了算法，你能不能实现。
这里锻炼的其实不是你的创造性思维，其实是考验你的实现已知算法的基本功。
考验的还是基本功！！！！！
当然，前提是你要将这个特定的算法步骤，理解并背会！！！

步骤概念参考：http://blog.csdn.net/antineutrino/article/details/6763722/
运算符优先级：https://baike.baidu.com/item/%E8%BF%90%E7%AE%97%E7%AC%A6%E4%BC%98%E5%85%88%E7%BA%A7/4752611?fr=aladdin
int match(char exp[],int n){
	//遍历exp数组，根据最终stack中的括号情况来判断是否正确
	char stack[maxSize];
	int i ;
	int top =  -1;//标志stack

	//添加stack

	for(i = 0 ; exp[i]=='\0' ;i++){
		//不同的情况

		if(exp[i] == '('){
			stack[++top] = '(';
		}
		else if(exp[i] == ')'){
			//先判断stack中前面的，分'(' ')'

			if(stack[top] == '('){
				top--;//不用stack[top--];
			}
			else if(top == -1){
				return 0;
			}

		}
		//如果两个情况都不满足，那么进行下一次循环
	}

	//判断最后结果

	if(top != -1){
		return 0;
	}
	else{
		return 1;
	}

}

总结：
这里要抓住 stack栈中是一定没有')' 这一基本条件
我现在将基本思路和实现步骤融到了注释中，所以，在编码和注释交替的来，以注释为先！



// (2)p62
int com(char exp[]){
	//从左至右扫描表达式，if数字时，将数字压入堆栈;if运算符时，弹出栈顶的两个数，计算（次顶元素 op 栈顶元素），并将结果入栈；
	// 重复上述过程直到表达式最右端，exp[] = '\0'。

	int i ;
	int stack[maxSize];
	top = -1;

	//遍历并计算值
	for(i = 0 ;exp[i] = '\0';i++){
		
		if (exp[i] == '*'){
			stack[top-1] = stack[top-1]*stack[top];
			top--;
		}
		else if(exp[i] == '/'){
			stack[top-1] = stack[top-1]/stack[top];
			top--;
		}
		else if(exp[i] == '+'){
			stack[top-1] = stack[top-1]+stack[top];
			top--;
		}
		else if(exp[i] == '-'){
			stack[top-1] = stack[top-1]-stack[top];
			top--;
		}
		else{//数字
			stack[++top] = exp[i];
		}
	}

	return stack[top];

}

出现的问题：
这里的类型是char，对数字的处理要留意
这里的除法要判断分母不能为0

字符转数字：a = '5'  ; b = '5' -'0' = 5  



#include<iostream>
using namespace std;


#define maxSize 20


int com(char exp[]){
    //从左至右扫描表达式，if数字时，将数字压入堆栈;if运算符时，弹出栈顶的两个数，计算（次顶元素 op 栈顶元素），并将结果入栈；
    // 重复上述过程直到表达式最右端，exp[] = '\0'。
    
    int i ;
    int stack[maxSize];
    int top = -1;
    
    //遍历并计算值
    for(i = 0 ;exp[i] != '\0';i++){
        
        if (exp[i] == '*'){
            stack[top-1] = (stack[top-1])*(stack[top]);
            top--;
        }
        else if(exp[i] == '/'){
            stack[top-1] = (stack[top-1])/(stack[top]);
            top--;
        }
        else if(exp[i] == '+'){
            stack[top-1] = (stack[top-1])+(stack[top]);
            top--;
        }
        else if(exp[i] == '-'){
            stack[top-1] = (stack[top-1])-(stack[top]);//(stack[top-1] - '0')-(stack[top] - '0')明确stack是int类型，左右都是int ，转啥转
            top--;
        }
        else{//数字
            stack[++top] = exp[i]-'0';//左右两边类型不同的 int = char 时 才需要转
        }
    }
    
    return stack[top];
    
}

int main(){
    char exp[10]="34+5*6-";//这里的* 不要写成×
    cout<<com(exp)<<endl;
    
}




// （6）p77
typedef struct  QNode
{	
	int data;
	struct QNode *next;
}QNode;

QNode * rear;

void enQueue(QNode *&rear,int x){
	//这里要使用引用，并传入x变量

	//兴建节点
	QNode *s = (QNode *)malloc(sizeof(QNode));
	s->next = NULL;
	s->data = x;

	//添加节点

	s->next = rear->next;
	rear->next =s;

	//忘了移动rear指向最后一个了
	rear = s;
}

int deQueue(QNode *&rear,int &x){
	//将删除的值放到x中

	QNode *p= NULL;

	//第一步：判空
	if(rear->next == rear) return 0 ;

	//第二步：删除
	p = rear->next->next;
	rear->next->next = p->next;

		//忘记了删除后队列为空的特殊情况
		if(s == rear){//if原来就一个元素
			rear=rear->next;
		}
	free(p);
	return 1;

}

总结：
一般检查的点有：
	边界
	空
	只有一个时 




// （7）p77

结构体：我一开始想的是用双向链表，然后分别front[2] rear[2]，这么做是为了方便的链表的增加和删除
但是我一看答案，人家用的是顺序表，不是链表！！！！！
shit，自己给自己增加难度！！！

像这种没有具体场景的题，他其实是让你根据基本的数据结构，来设计更加复杂的数据结构或者操作。
这时最先想的是：判空+判满条件



typedef struct Queue
{
	int data[maxSize];
	int front;
	int rear;
}Queue;


判空，判满条件不变
#include<iostream>
using namespace std;


#define maxSize 20

typedef struct Queue
{
    int data[maxSize];
    int front;
    int rear;
}Queue;


int enQueue(Queue &qu,int x){
    //从队头插入，其实就是将front作为插入。
    // 与原来的不同点是：font指向的是空的，而rear指向的是实的
    
    //判满
    if(qu.rear+1 == qu.front) return 0;
    //添加
    qu.data[qu.front] = x;
    //移动初始化 ----这一步要专门写出来，要不就忘了
    
    qu.front = (qu.front-1+maxSize)%maxSize;
    
    return 1;
}

int deQueue(Queue &qu,int &x){
    
    //判空
    if(qu.front == qu.rear) return 0 ;
    
    //删除(rear已经指向一个有值的空间了)
    x = qu.data[qu.rear];
    
    //移动
    // qu.rear--;//特殊情况是0-1 = -1,这是不可能的
    qu.rear = (qu.rear-1 + maxSize)%maxSize;//这里用/ 不能用%
    
    return 1;
}

int main(){
    Queue qu;
    qu.front = 0;
    qu.rear = 0;
    int x;
    
    cout<<enQueue(qu, 999)<<endl;
    cout<<enQueue(qu, 888)<<endl;
    cout<<enQueue(qu, 777)<<endl;
    
    
    cout<<deQueue(qu, x)<<endl;
    cout<<"x= "<<x<<endl;
    cout<<deQueue(qu, x)<<endl;
    cout<<"x= "<<x<<endl;
    cout<<deQueue(qu, x)<<endl;
    cout<<"x= "<<x<<endl;
    
    
    cout<<deQueue(qu, x)<<endl;
    
    
    
    int i;
    
    for(i = 0; i < maxSize;i++ ){
        cout<<"i = "<<qu.data[i]<<endl;
    }
    
}




总结：这道题有几个关键要点要发现：
判空，判满条件不变
知道front和rear的区别：空还是非空

// （8）
这道题依然还是对于基本数据结构的扩展
算法只改变判空判满的条件，其他的都不变。

判满：上一个操作为进栈，此时front = rear
判空：上一个操作为出栈，此时front = rear

这里要明确的知道tag的意思：何时赋值我就没有想，也没有思考tag表示的意思，对判空和判满的条件也没有认识错误。
这里是组合条件判断，和我们平常的判断方式有很大的不同，如果没有经验，简单，但是你也想不到。




整体总结：
第一层：算法设计不出来。这个没办法
第二层：事件的基本规律原则没有总结出来。这些规律原则是本事事件的属性，但是我们常常发现不了。
第三层：基本步骤的缺失不完整。其实就是步骤描述的注释少东西
第四层：语法出错。当程序不按自己的期望走时，很多时候都是自己的语法有问题，自己的意思和程序的意思是两张皮。


// （9）p78
一：除二取余法
二：
三：

int baseTrans(int N){
	//栈的初始化
	int stack[maxSize];
	top = -1;
	int i ;

	//放入栈中
	while(N==0){
		stack[++top]=N%2;
		N = N/2;
	}

	//从栈中取出
	for(i = 0;i<=top;i++){
		cout<<stack[i]<<endl;
	}
}




int baseTrans(int N){
    if(N<=0)return 0;
    //栈的初始化
    int stack[maxSize];
    int top = -1;
    
    //放入栈中
    while(N!=0){
        stack[++top]=N%2;
        N = N/2;
    }
    
    //从栈中取出
    while(top!=-1){
        cout<<stack[top--];//上面写的那个这里就不是出栈，那是遍历数组。shit，脑子有病
    }
    
    cout<<endl;
    return 1;
}

数据结构源码

发表于 2017-09-24 更新于 2020-06-08 分类于 b计算机基础/h_算法/算法学习过程/2017 阅读次数：
本文字数： 184 阅读时长 ≈ 1 分钟

2017年9月24日下午4:15

2_1.cpp 2_2.cpp
wrong.cpp
2_3practice.cpp 2_4thinking.cpp

3_1base.cpp 3_2thinking.cpp

5_1base.cpp

6_1base.cpp 6_2practice.cpp

7_1base.cpp 7_2practice.cpp

8_1base.cpp 8_2practice.cpp