java web上机课作业延伸出的坑爹问题 今天老师要我们用记事本写一个Servlet.java理解一下Servlet的基本原理的实现过程 于是乎，我看到了一个要求：代码中的符号应该修改为英文符号 为什么中文就不可以呢？然后我尝试写了中文，迎面而来的是疯狂的翻车。百度看了一堆也是没有解决 最终解决方案 坑点 由于是GBK编码，Notepad++中编码一定要选ANSI编码！！一定要选ANSI编码！！一定要选ANSI编码！！ 原因 在整个Servlet访问过程中牵扯到 浏览器,Tomcat,Java程序三者 浏览器默认编码方式:gbk, Tomcat默认编码:iso-8859-1 , java代码中的编码一般常用utf-8 从Servlet传输数据到浏览器的过程是:Servlet —> Tomcat —> 浏览器 因为只写了Servlet.java所以只能够在这之中控制Servlet和Tomcat与浏览器统一为GBK。 核心代码 response.setContentType("text/html;charset=GBK"); request.setCharacterEncoding("GBK"); ……

快速认识KMP算法 阮一峰老师带你认识KMP算法 从头到尾彻底理解KMP 浅谈我对KMP中next数组的认识与理解 next数组是因为总是要找失配字符的上一位字符不方便而产生的 next数组的出现使得只用找失配字符对应的next值即为失配字符的上一位字符的最大长度值 根据《最大长度表》，失配时，模式串向右移动的位数 = 已经匹配的字符数 - 失配字符的上一位字符的最大长度值 而根据《next 数组》，失配时，模式串向右移动的位数 = 失配字符的位置 - 失配字符对应的next 值 有上述得匹配的字符数=失配字符的位置，失配字符的上一位字符的最大长度值=失配字符对应的next 值 next数组与最大长度表都是对模式串特征的一种映射，使得不需要像BF算法那样匹配多次，相同部分可以跳过 next数组的第一位为何是-1 由于第一位匹配就失配时，默认向右移动1位，即模式串向右移动的位数=1，此时失配字符的位置=0，代入（模式串向右移动的位数 = 失配字符的位置 - 失配字符对应的next 值）改式之中，即可解得next值为-1 next数组核心代码 //优化过后的next 数组求法 void GetNextval(char* p, int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while (j < pLen - 1) { //p[k]表示前缀，p[j]表示后缀 if (k == -1 || p[j] == p[k]) { ++j; ++k; //较之前next数组求法，改动在下面4行 if (p[j] !……

BF算法 BF算法又称朴素的模式匹配算法，属于串匹配中的暴力法 即在S的所有字符中逐个匹配P的每个字符。 局限性 如果情况最坏的时候，假设在一个长度为n的文本串中查找一个长度为m的模式串，则需要匹配n*m次。复杂度将会由O（m+n）退化到O（mn） 核心代码 void BF(string s, string p) { int i = 0, j = 0, count = 0,sum=0,ans=0;//i记录文本串位置，j记录模式串位置，count统计该趟匹配次数,sum统计总判断次数，ans统计匹配轮数 while (i < s.size()) { if (s.at(i) == p.at(j)) {//匹配成功，下一位 i++; j++; count++; sum++; } else {//匹配失败 j回溯，i回滚起始的下一位 i=i-count+1; j = 0; count = 0; sum++; ans++; } if (count == p.size()) { ans++; cout << "模式匹配成功，共走了" << ans << "轮" << endl; cout << "判断了" << sum << "次" << endl; return; } } cout << "匹配失败" << endl; cout << "判断了" << sum << "次" << endl; } ……

7-11问题 一位顾客在7-11买了4件商品，这4件商品相乘的价格是7.11元，相加的价格也是7.11元，请用蛮力法编写程序，输出这4件商品的价格分别是多少。 思路：蛮力（暴力）法 约束条件就2个，a+b+c+d=7.11，abcd=7.11。写3个for循环遍历出所有答案即可 坑点：C/C++浮点数误差分析 如上图，C语言的浮点数是有一定误差的，在误差范围内，我们一般默认实际值为正确答案 难点： 本题难点就在于如何解决该误差 方法1： 避免浮点数的计算 #include<iostream>#include<math.h>using namespace std; /*711000000*/ /*2147483648*/ int main() { double a,b,c,d; cout<<"a\tb\tc\td"<<endl; for(a=1;a<711;a++) for(b=1;b<711;b++) for(c=1;c<711;c++) { d=711-(a+b+c); if(a*b*c*d==711000000) { cout<<a/100<<"\t"<<b/100<<"\t"<<c/100<<"\t"<<d/100<<endl; } } return 0; } 方法2： 标明精度进行运算 #include<iostream>#include<math.h>using namespace std; /*711000000*/ /*2147483648*/ int main() { double a,b,c,d; cout<<"a\tb\tc\td"<<endl; for(a=0.01;a<7.11;a=a+0.01) for(b=0.01;b<7.11;b=b+0.01) for(c=0.01;c<7.11;c=c+0.01) { d=7.11-(a+b+c); if(fabs(a*b*c*d-7.11)<10e-8) { cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl; } } return 0; } ……

题意 给你一个数n，你要找出一个只由0和1组成的不超过100位的数，使得该数是n的m倍 思路 这是一道BFS题，入队的时候有两种情况：一种是10t；一种是10t+1；这题还有个坑点是用C++的STL的队列会T,所以需要自己写一个队列 题目链接 http://poj.org/problem?id=1426 代码 #include<iostream>#include<queue>using namespace std; long long a[10000000]; long long bfs(int N) { int front = 0; int rear = 0; a[rear++] = 1; while (front != rear) { long long tmp = a[front++]; if (tmp % N == 0) { return tmp; } a[rear++] = tmp * 10; a[rear++] = tmp * 10 + 1; } return -1; } int main() { int N; while (cin >> N) { if (N == 0)break; cout << bfs(N) << endl; } return 0; } ……

什么是BFS BFS又称为广度优先搜索。举个例子：一群老鼠走迷宫。假设老鼠是无限多的，这群老鼠进去后，在每个路口派出部分老鼠探索所有没走过的路。走某条路的老鼠，如果碰壁无法前行，就停下；如果到达的路口已经有其他老鼠探索过了，也停下。很显然，所有的道路都会走到，而且不会重复。这个思路就是BFS。BFS看起来像“并行计算”，不过，由于程序是单机顺序运行的，所以可以把BFS看成是并行计算的模拟。 如何实现BFS 在具体编程时，一般用队列这种数据结构来具体实现BFS，甚至可以说“BFS=队列”。 代码如下： #include<iostream>#include<queue>#define CHECK(x,y)(x>=0&&x<=wx&&y>=0&&y<=hy) using namespace std; int wx,hy,num; char room[23][23]; int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; struct node{ int x,y; } void BFS(int dx,int dy){ num=1; queue<node>q; node start,next; start.x=dx; start.y=dy; q.push(start); while(!q.empty()){ next=q.front(); q.pop(); for(int i=0;i<4;i++){ next.x=start.x+dir[i][0]; next.y=start.y+dir[i][1]; if(CHECK(next.y,next.y)&&room[next.x][next.y]=='.'){ room[next.x][next.y]='#'; num++; q.push(next); } } } } int main(){ int dx,dy,x,y; while(cin>>wx>>hy){ if(wx==0&&hy==0)break; for(y=0;y<hy;y++){ for(x=0;x<wx;x++){ cin>>room[x][y]; if(room[x][y]=='@'){ dx=x; dy=y; } } } num=0; BFS(dx,dy); cout<<num<<endl; } return 0; } ……

什么是归并排序 归并排序（Merge Sort）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略将问题分成一些小的问题然后递归求解，即分而治之。 图解 代码实现 #include<iostream>using namespace std; const int maxsize=5; typedef int datatype; typedef char othertype; typedef struct{ datatype key; othertype other; }rec; typedef rec list[maxsize+1]; list a; list b; void Inser(){ cout<<"请输入:"<<endl; for(int i=1;i<maxsize+1;i++){ cin>>a[i].other>>a[i].key; } } void Merge(list r,list r1,int low,int mid,int high){ int i,j,k; i=low; j=mid+1; k=low; while(i<=mid&&j<=high){ if(r[i].key<=r[j].key)r1[k++]=r[i++]; else r1[k++]=r[j++]; } while(i<=mid)r1[k++]=r[i++]; while(j<=high)r1[k++]=r[j++]; } void Merge_passage(list r,list r1,int n,int len){ int i=1; while(i+2*len-1<=n){ Merge(r,r1,i,i-1+len,i-1+2*len); } if(i-1+len<n){ Merge(r,r1,i,i-1+len,n); } else{ for(int j=i;j<n;j++){ r1[j]=r[j]; } } } void Merge_sort(list r,list r1,int n){ int len; len=1; while(len<n){ Merge_passage(r,r1,n,len);len=len*2; Merge_passage(r1,r,n,len);len=len*2; } } int main(){ Insert(); Merge_sort(a,b,maxsize); for (int i = 1; i < maxsize + 1; i++) { cout << b[i].……

什么是哈夫曼树 哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1L1+W2L2+W3L3+…+ WnLn)，N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树的WPL是最小的。 构造哈夫曼树的算法如下： 1）对给定的n个权值{W1,W2,W3,…,Wi,…,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,…,Ti,…, Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 4）重复2）和3），直到集合F中只有一棵二叉树为止。 例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图所示： 哈夫曼树的算法实现 #include<iostream>#include<iomanip>#include<cfloat>using namespace std; const int n=5; const int m=2*n-1; typedef struct{ float weight; int parent,lchild,rchild; }nodetype; typedef nodetype hftree[m]; hftree T; void huffman(hftree T){ int p1,p2,i,j; float small1,small2; for(i=0;i<n;i++){ T[i].parent=T[i].lchild=T[i].rchild=-1; } for(i=0;i<n;i++){ cin>>T[i].weight; } for(i=n;i<m;i++){ p1=p2=-1; small1=small2=FLT_MAX; for(j=0;j<=i-1;j++){ if(T[j].parent!=-1)continue; if(T[j].weight<small1){ small2=small1; small1=T[j].weight; p2=p1; p1=j; } else if(T[j].weight<small2){ small2=T[j].weight; p2=j; } } T[p1].parent=T[p2].parent=i; T[i].parent=-1; T[i].lchild=p1; T[i].rchild=p2; T[i].weight=small1+small2; } } 输出哈夫曼树 这里用到了头文件，主要是运用setw()控制一下输出的格式……

算法的基本思想：依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点；若新结点是第1个结点，则令其为根节点；否则将新结点作为孩子链接到它的双亲结点上。如此重复下去，直到输入字符“#”为止 核心代码： Bitree level_create(){ char ch; pointer Q[maxsize+1]; int front,rear; pointer root,s; root=NULL; front=rear=0; while(cin>>ch,ch!='#'){ if(ch!='@'){ s=new node; s->data=ch; s->lchild=s->rchild=NULL; } else s=NULL; rear++;//不管结点是否为虚，都要入队 Q[rear]=s; if(rear==1){//第一个结点是根，要修改头指针，它不是孩子 root=s; front=1; } else{ if(s&&Q[front]){ if(rear%2==0)Q[front]->lchild=s; else Q[front]->rchild=s; } if(rear%2==1)front++;//不论是否为虚，右孩子入队后，双亲出队 } } return root; } ……

在学习算法spfa的过程之中，其代码的实现过程是用了链式前向星结构实现，因此了解并学习了一下链式前向星 什么是链式前向星 前向星的本质其实是静态链表，如果说邻接表存的是点的集合，那么链式前向星是存的是边的集合。 为什么要采用链式前向星 如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好些，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。 主要代码实现 struct Edge { int next;//下一条边的编号 int to;//这条边到达的点 int dis;//这条边的长度 }edge[maxm]; void add_edge(int from,int to,int dis) //加入一条从from到to距离为dis的单向边 { edge[++num_edge].next=head[from]; edge[num_edge].to=to;//将to记录 edge[num_edge].dis=dis;//将dis记录 head[from]=num_edge;// } head[i]数组与next 关于head[i]的含义，我们理解为指向 i 结点的第一条边。这是方便于我们在接下来调用的时候能够完好的访问：i结点第一条边通过head访问，剩下的边通过next指针指向。 总的来说： head[i]来指向 i 结点的第一条边 next指向下一条边 调用核心代码 for(int i=head[k];i!=0;i=edge[i].next) ……