数据结构与算法之:字符串和KMP算法(五)
字符串 串(String)是由零个或多个祖父组成的有限序列,又叫做 字符串 传可以使空串 子串与主串,例如 "Matrix" 是 "Matrix42" 的子串,反之"Matrix42" 为 "Matrix" 的主串 字符串的比较 字符串比较大小跟传统的数字比较大小有点差别,很容易我们可以知道2比1要大,可是"matrix" 和 "Matrix42"呢?,要怎么比较呢?比长短还是比大小? 比大小!逼得就是字符串里每个字符的ASCII码的大小,因为'M'== 77 , 'f'==109,所以"matrix" > "Matrix42" 其实这样的比较大小没有多大意义,字符串的比较我们更重视是否相等! 字符串的存储结构 字符串的存储结构与线性表相同,也分顺序存储结构和链式存储结构 字符串的顺序存储结构使用一组地址连续的存储单元来存储串中的字符串序列的 按照预定义的大小,为每个定义的字符串变量分配一个固定长度的存储区,一般用定长数组来定义 与线性表相似,既然是固定长度的存储区,就存在一个空间分配不灵活的问题,那么会考虑用链式存储结构 不同的是字符串我们一般都是连在一起表述的,"断章取义"的情况并不多,所以习惯上我们通常还是会直接定义一个足够长度的存储区来存储的 BF(Brute Force)算法 BF算法属于朴素的模式匹配算法,它的核心思想是: 有两个字符串S和T,长度为N和M,首先S[1]和T[1]比较,若相等,则再比较S[2]和T[2],一直到T[M];若S[1]和T[1]不等,则T向右移动一个字符的位置,再依次进行比较 该算法最坏情况下要进行M*(N-M+1)次比较,时间复杂度为O(M*N) 在这里S是主串,T是子串,这种子串的定位操作通常称作串的模式匹配 KMP算法 KMP算法是三位老前辈(D.E.Knurh,J.HMorris和V.R.Paratt)的研究结果,大大的避免重复遍历的情况,全称叫做克努特-莫里斯-普拉特算法,简称KMP算法 KMP算法的核心是避免不必要的回溯,问题由模式串决定,不是由目标串决定 KMP算法之next数组代码原理分析 next数组:当模式匹配串T失配的时候,next数组对应的元素指导应该用T串的哪个元素进行下一轮匹配 j= 0; i = 1; next[1] = 0; //T[0]为串的长度 while(i<T[0]) { //匹配上了 if(j==0 || T[i] == T[j]) { //前缀 i++; //后缀 j++; next[i] = j; } //失配 else { //j回溯 j = next[j]; } } KMP算法之实现及优化 typedef char* String; void get_next(String T,int *next) { int j = 0; int i = 1; next[1] = 0; while(i<T[0]) { if(0==j || T[i] == T[j]) { i++; j++; if(T[i]!=T[j]) { next[i] = j; } else { next[i] = next[j]; } } else { j = next[j]; } } } //返回子串T在主串S第POS个字符之后的位置 //若不存在,则返回0 int Index_KMP(String S,String T,int pos) { int i = pos; int j = 1; int next[255]; get_next(T,next); while(i<S[0] && j<=T[0]) { if(0==j || S[i]==T[j]) { i++; j++; } else { j = next[j]; } } if(j>T[0]) { return i-T[0]; } else { return 0; } }
递归效率比较低,能用循环尽量用循环 Sierpinski三角形就是递归实现的 斐波那契数列的递归实现 如果兔子在出生两个月后就有繁殖能力,一堆兔子每个月能生出一对小兔子来.假设所有兔子都不会死去,那么一年后可以繁殖多少兔子呢? 月数-兔子个数 所经过的月数 1 2 3 4 5 6 7 8 9 10 11 12 兔子的总对数 1 1 2 3 5 8 13 21 34 55 89 144 我们可以用数学函数来定义 0,当 n=0 F(n) = 1, 当n = 1 F(n-1)+F(n-2),当n>1 递归实现 int Fib(int i) { if(i<2) return i == 0?0:1; return Fib(i-1) + Fib(i-2); } 递归树 递归定义 在高级语言中,函数调用自己和调用其他函数并没有本质的不同.我们把一个一直调用自己或通过一系列的调用语句简介的调用自己的函数,称作递归函数 写递归程序最怕的就是陷入永不结束的无穷递归中.切记每个递归定义必须至少有一个条件,当满足这个条件时递归不再进行,即函数不再调用自身而返回 大量的递归会建立函数的副本,会消耗大量的时间和内存,而迭代则不需要 递归函数分为调用和回退阶段,递归的回退顺序是它调用顺序的逆序 分治思想 当一个问题规模较大且不易求解的时候,就可以考虑将问题分成几个小的模块,逐一求解 分治思想和递归算是亲兄弟关系,因为采用分支思想处理问题,其各个小模块通常具有与大问题相同的结构,这种特性也使递归技术有了用武之地. 折半查找算的的递归实现 折半查找是一种常用的查找方法,该方法通过不断 缩小一半查找的范围,知道达到目的,所以效率比较高 汉诺塔 一位法国数学家曾经编写过一个印度的古老传说:在世界中心拿勒斯的圣庙里,一块黄铜板上插着三根宝石针.印度的主神梵天在创造世界的时候,在其中一根针上从下到上的穿4好了由大到小的64片金片,这就是所谓的汉诺塔.不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上小片必须在大片上面. 我们可以做这样的考虑 先将前63个盘子移动到Y上,确保大盘在小盘下 再将最底下的第64个盘子移动到Z上 最后将Y上的63个盘子移动到Z上 在游戏中,我们发现由于每次只能移动一个圆盘,所以在移动的过程中显然要借助另外一根针才行 也就是说第1步将1~63个盘子借助Z移动到Y上,第3步将Y针上的63个盘子借助X移动到Z针上.那么我们把所有新的思路聚集为一下两个问题: 问题一:将X上的63个盘子借助Z移动到Y上 问题二:将Y上的63个盘子借助X移动到Z上 解决上述两个问题依然用相同的方法: 问题一的圆盘移动步骤为 先将62个盘子移动到Z上,确保大盘在小盘下 再将底下的第36个盘子移动到Y上 最后将Z上的62个盘子移动到Y上 问题二的圆盘移动步骤为: 先将前62个盘子移动到X上,确保大盘在小盘下 再将最底下的第63个盘子移动到Z上 最后将X上的62个盘子移动到Y上 #include <stdio.h> //将n个盘子从x借助y移动到x void move(int n,char x,char y,char z) { if(1==n) { printf("%c-->%c\n",x,z); } else { //将n-1个盘子从x借助z移动到y上 move(n-1,x,z,y); //将第n个盘子从x移动到z上 printf("%c-->%c\n",x,z); //将n-1个盘子从y借助x移动到z上 move(n-1,y,x,z); } } int main() { int n; printf("请输入汉诺塔的层数:"); scanf("%d",&n); printf("移动步骤如下:\n"); move(n,'X','Y','Z'); return 0; } 八皇后问题 八皇后问题是一个古老而著名的问题,是回溯算法的典型例题(先用递归算法求解) 该问题由十九世纪著名的数学家搞死18550年提出: 在8x8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行,同一列或同一斜线上,问有多少种摆法 #include <stdio.h> int count = 0; int noDanger(int row,int j,int (*chess)[8]) { int i,k,flag1=0,flag2=0,flag3=0,flag4=0,flag5=0; //判断列方向 for(i=0;i<8;i++) { if(*(*(chess+i)+j)!=0) { flag1 = 1; break; } } //判断左上方 for(i=row,k=j;i>=0&&k>=0;i--,k--) { if(*(*(chess+i)+k)!=0) { flag2 = 1; break; } } //判断右下方 for(i=row,k=j;i<8&&k<8;i++,k++) { if(*(*(chess+i)+k)!=0) { flag3 = 1; break; } } //判断右上方 for(i=row,k=j;i>=0&&k<8;i--,k++) { if(*(*(chess+i)+k)!=0) { flag4 = 1; break; } } //判断左下方 for(i=row,k=j;i<0&&k>=0;i++,k--) { if(*(*(chess+i)+k)!=0) { flag5 = 1; break; } } if(flag1||flag2||flag3||flag4||flag5) { return 0; } else { return 1; } } //参数row表示起始行 //参数n表示列数 //参数(*chess)[8]表示指向棋盘每一行的指针 void EightQueen(int row,int n,int (*chess)[8]) { int chess2[8][8],i,j; for(i=0;i<8;i++) { for(j=0;j<8;j++) { chess2[i][j] = chess[i][j]; } } if(8==row) { printf("第%d种\n",++count); for(i=0;i<8;i++) { for(j=0;j<8;j++) { printf("%d ",*(*(chess2+i)+j)); } printf("\n"); } printf("\n"); } else { //如果有危险继续往下 for(j=0;j<n;j++) { //判断这个位置是否有危险 if(noDanger(row,j,chess)) { for(i=0;i<8;i++) { *(*(chess2+row)+i) = 0; } *(*(chess2+row)+j) = 1; EightQueen(row+1,n,chess2); } } } } int main() { int chess[8][8],i,j; for(i=0;i<8;i++) { for(j=0;j<8;j++) { chess[i][j] = 0; } } EightQueen(0,8,chess); printf("总共有%d种方式!\n",count); return 0; }
栈 栈的定义 栈是一种后进先出(Last in first out,LIFO)的线性表,只能在表尾进行插入和删除操作 栈的插入和删除操作 站的插入操作(push),叫做进栈,也称为压栈,入栈 栈的删除操作(pop),叫做出栈,也叫做弹栈 栈的顺序存储结构 因为栈的本质是一个线性表,线性表有两种存储形式,那么栈也分为栈的顺序存储结构和栈的链式存储结构 最开始栈中不含有任何数据,叫做空栈,此时栈顶就是栈底.然后数据从栈顶进入,栈顶栈底分离,整个栈的当前容量变大.数据出栈时从栈顶弹出,栈顶下移,整个栈的当前容量变小 栈的顺序存储结构 typedef struct { ElemType *base; ElemType *top; int stackSize; }sqStack; 这里定义了一个顺序存储的栈,它包含了三个元素:base,top,stackSize.其中base是指向栈底的指针变量,top是指向栈顶的指针变量,stsck Size指示栈的当前可使用的最大容量 创建一个栈 #define STACK_INIT_SIZE 100 void initStack(sqStack *s) { s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!s->base) exit(0); s->top = s->base; s->stackSize = STACK_INIT_SIZE; } 入栈操作 入栈操作要在栈顶进行,每次向栈中压入一个数据,top指针就要+1,指导栈满为止 #define STACKINCREMENT 10 void push(sqStack *s,ElemType e) { //如果栈满,追加空间 if(s->top - s->base >= s->stackSize) { s->base = (ElemType *)realloc(s->base,(s->stackSize + STACKINCREMENT) * sizeof(ElemType)); if(!s->base) exit(0); s->top = s->base + s->stackSize;//设置栈顶 s->stackSize = s->stackSize + STACKINCREMENT;//设置栈的最大容量 } *(s->top) = e; s->top++; } 出栈操作 出栈操作就是在栈顶取出数据,栈顶指针随之下移的操作 每当从栈内弹出一个数据,栈的当前容量就-1 void pop(sqStack *s,ElemType *e) { //如果栈为空返回 if(s->top == s->base) return; *e = *--(s->top); } 清空一个栈 void ClearStack(sqStack *s) { s->top = s->base; } 销毁一个栈 void DestoryStack(sqStack *s) { int i,len; len = s->stackSize; for(i=0;i<len;i++) { free(s->base); s->base++; } s->base = s->top = NULL; s->stackSize = 0; } 当前容量 int StackLen(sqStack s) { return (s.top - s.base); } 二进制转10进制 #include <stdio.h> #include <stdlib.h> #include <math.h> #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef char ElemType; typedef struct { ElemType *base; ElemType *top; int stackSize; }sqStack; void initStack(sqStack *s) { s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!s->base) exit(0); s->top = s->base; s->stackSize = STACK_INIT_SIZE; } void push(sqStack *s,ElemType e) { //如果栈满,追加空间 if(s->top - s->base >= s->stackSize) { s->base = (ElemType *)realloc(s->base,(s->stackSize + STACKINCREMENT) * sizeof(ElemType)); if(!s->base) exit(0); s->top = s->base + s->stackSize;//设置栈顶 s->stackSize = s->stackSize + STACKINCREMENT;//设置栈的最大容量 } *(s->top) = e; s->top++; } void pop(sqStack *s,ElemType *e) { //如果栈为空返回 if(s->top == s->base) return; *e = *--(s->top); } void ClearStack(sqStack *s) { s->top = s->base; } void DestoryStack(sqStack *s) { int i,len; len = s->stackSize; for(i=0;i<len;i++) { free(s->base); s->base++; } s->base = s->top = NULL; s->stackSize = 0; } int StackLen(sqStack s) { return (s.top - s.base); } int main() { ElemType c; sqStack s; int len,i,sum = 0; initStack(&s); printf("请输入二进制数,输入#号表示结束!\n"); scanf("%c",&c); while(c!='#') { push(&s,c); scanf("%c",&c); } //把回车从缓冲区去掉 getchar(); len = StackLen(s); printf("栈的容量为:%d\n",len); for(i=0;i<len;i++) { pop(&s,&c); sum = sum + (c-48)*pow(2,i); } printf("%d\n",sum); return 0; } 括号匹配 二进制转八进制 二进制与十六进制对应关系 0 0 1 1 10 2 11 3 100 4 101 5 110 6 111 7 1000 8 1001 9 1010 A 1011 B 1100 C 1101 D 1110 E 1111 F 一个字节(8bit)刚好用两个十六进制数可以表示完整,大大街上了显示空间 先把每三位取出来,转换成8进制压入另一个栈,再从另外一个栈弹出 栈的链式储结构 typedef struct StackNode { ElemType data; struct StackNode *next; }StackNode,LinkStackPtr; typedef struct LinkStack { //top指针 LinkStack top; //栈元素计数器 int count; } 进栈操作 Status push(LinkStack *s,ElemType e) { LinkStackPtr p = (LinkStackPtr)malloc (sizeof(StackNode)); p->data = e; p->next = s->top; s->top = p; s->count++; return OK; } 出栈操作 Ststus pop(LinkStack *s,ElemType *e) { LinkStackPtr p; if(StackEmpty(*s)) return ERROR; *e = s->top->data; p = s->top; s->top = s->top->next; free(p); s->count--; return OK; } 逆波兰表达式 20世纪三十年代,波兰逻辑学家Jan.Lukasiewicz发明了一种不需要括号的后缀表达式,我们通常把它称为逆波兰表达式(RPN) 对于(1-2)(4+5),如果用逆波兰表示发,应该是这样:1 2 - 4 5 + 数字1和2进栈,遇到减号运算符则弹出两个元素进行运算,并把结果入栈 4和5入栈,遇到加号运算符,4和5弹出栈,相加后结果9入栈 然后又遇到乘法运算符,将9和-1弹出栈进行乘法计算,此时栈空并无数据压栈,-9为最终结果 逆波兰表达式计算器 #include <stdio.h> #include <stdlib.h> #include <ctype.h> #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define MAXBUFFER 10 typedef double ElemType; typedef struct { ElemType *base; ElemType *top; int stackSize; }sqStack; void initStack(sqStack *s) { s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!s->base) exit(0); s->top = s->base; s->stackSize = STACK_INIT_SIZE; } void push(sqStack *s,ElemType e) { //如果栈满,追加空间 if(s->top - s->base >= s->stackSize) { s->base = (ElemType *)realloc(s->base,(s->stackSize + STACKINCREMENT) * sizeof(ElemType)); if(!s->base) exit(0); s->top = s->base + s->stackSize;//设置栈顶 s->stackSize = s->stackSize + STACKINCREMENT;//设置栈的最大容量 } *(s->top) = e; s->top++; } void pop(sqStack *s,ElemType *e) { //如果栈为空返回 if(s->top == s->base) return; *e = *--(s->top); } int main() { sqStack s; char c; double d,e; int i = 0; char str[MAXBUFFER]; initStack(&s); printf("请按逆波兰表达式输入待计算数据,数据与运算符之间用空格隔开,以#作为结束标志!\n"); scanf("%c",&c); while(c!='#') { while(isdigit(c)||c=='.') { str[i++] = c; str[i] = '\n'; if(i>=10) { printf("出错:输入的单个数据过大!\n"); return -1; } //过滤空格 scanf("%c",&c); if(c==' ') { d = atof(str); push(&s,d); i = 0; break; } } switch(c) { case '+': pop(&s,&e); pop(&s,&d); push(&s,d+e); break; case '-': //下面减上面 pop(&s,&e); pop(&s,&d); push(&s,d-e); break; case '*': pop(&s,&e); pop(&s,&d); push(&s,d*e); break; case '/': pop(&s,&e); pop(&s,&d); if(e!=0) { push(&s,d/e); } else { printf("\n出错:除0!\n"); } break; } scanf("%c",&c); } pop(&s,&d); printf("最终的计算结果为:%lf",d); return 0; } 中缀表达式转换为后缀表达式 从左到右遍历中缀表达式的每个数字和符号,若是数字则直接输出,若是符号,则判断其与栈顶符号的优先级,是右括号或者优先级低于栈顶符号,则栈顶元素一次出栈并输出,直到遇到左括号或栈空才将那个符号入栈 #include <stdio.h> #include <stdlib.h> #include <ctype.h> #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define MAXBUFFER 10 typedef char ElemType; typedef struct { ElemType *base; ElemType *top; int stackSize; }sqStack; void initStack(sqStack *s) { s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!s->base) exit(0); s->top = s->base; s->stackSize = STACK_INIT_SIZE; } void push(sqStack *s,ElemType e) { //如果栈满,追加空间 if(s->top - s->base >= s->stackSize) { s->base = (ElemType *)realloc(s->base,(s->stackSize + STACKINCREMENT) * sizeof(ElemType)); if(!s->base) exit(0); s->top = s->base + s->stackSize;//设置栈顶 s->stackSize = s->stackSize + STACKINCREMENT;//设置栈的最大容量 } *(s->top) = e; s->top++; } void pop(sqStack *s,ElemType *e) { //如果栈为空返回 if(s->top == s->base) return; *e = *--(s->top); } int StackLen(sqStack s) { return (s.top - s.base); } int main() { sqStack s; char c,e; initStack(&s); printf("请输入中缀表达式,以#作为结束标志:\n"); scanf("%c",&c); while(c!='#') { while(c>='0'&&c<='9') { printf("%c",c); scanf("%c",&c); if(c<'0'||c>'9') { printf(" "); } } if(')' == c) { pop(&s,&e); while('('!=e) { printf("%c ",e); pop(&s,&e); } } else if('+'==c || '-'==c) { if(!StackLen(s)) { push(&s,c); } else { do { pop(&s,&e); if('('==e) { push(&s,e); } else { printf("%c ",e); } }while(StackLen(s)&&'('!=e); push(&s,c); } } else if('*'==c||'/'==c||'('==c) { push(&s,c); } else if('#'==c) { break; } else { printf("\n输入错误!\n"); return -1; } scanf("%c",&c); } while(StackLen(s)) { pop(&s,&e); printf("%c ",e); } return 0; } 队列 什么是队列 队列(queue)是只允许在一段进行插入操作,而在另一端进行删除操作的线性表 与栈相反,队列是一种先进先出(First In First Out,FIFO)的线性表 与栈相同的是,队列也是一种重要的线性结构,实现一个队列同样需要顺序表或链表作为基础 队列既可以用链表实现,也可以用顺序表实现.跟栈相反的是,栈一般用顺序表来实现,二队列常4用链表来实现,简称为链队列 队列的链式存储结构 typedef struct QNode { ElemType data; struct QNode *next; }QNode,*queuePrt; typedef struct { //队头,尾指针 queuePrt front,rear; }LinkQueue; 我们将头指针指向队列的头结点,而队尾指针指向终端节点.(注:头结点不是必须的,但为了方便操作,我们加上了) 空队列时,front和rear都指向头结点 创建一个队列 void initQueue(LinkQueue *q) { q->front = q->rear = (queuePrt)malloc(sizeof(QNode)); if(!q->front) exit(0); q->front->next=NULL; } 入队列操作 void InsertQueue(LinkQueue *q,ElemType) { p = (queuePrt)malloc(sizeof(QNode)); if(p==NULL) exit(0); p->data = e; p->next = NULL; q->rear->next = p; q->rear = p; } 出队列操作 出队列操作是将队列中的第一个元素移除,队头指针不发生改变,改变头结点的next指针即可 void DeleteQueue(LinkQueue *q,ElemType *e) { queuePrt p; if(q->front == q->rear) return; p = q->front->next; *e = p->data; q->front->next = p->next; if(q->rear==p) q->rear = q->front; free(p); } 销毁一个队列 由于连队列建立在内存的动态区,因此当一个队列不在有用时应当把它及时销毁掉,以免过多的占用空间 void DestoryQueue(LinkQueue *q) { while(q->front) { q->rear = q->front->next; free(q->front); q->front = q->rear; } } 队列的顺序存储结构 队列顺序存储会出现对头有空余而队尾溢出的情况,这种情况叫做假溢出. 循环队列的定义 要解决假溢出的办法就是如果后面满了,就再从头开始,也就是头尾相接的循环 循环队列它的容量是固定的,并且它的队头和队尾指针都可以随着元素出入队列而发生改变,这样循环队列逻辑上就好像是一个环形的存储空间 循环队列的实现只需要灵活改变front和rear指针即可 也就是让front或rear指针不断加1,即使超出了地址范围,也会自动从头开始,我们可以采取取模运算处理 (rear+1) % QueueSize (front+1) % QueueSize 定义一个循环队列 #define MAXSIZE 100 typedef struct { ElemType *base; int front; int rear; } 初始化一个循环队列 void initQueue(cycleQueue *q) { q->base = (ElemType *)malloc(MAXSIZE * sizeof(ElemType)); if(!q->base) exit(0); q->front = q->rear = 0; } 如队列操作 void InsertQueue(cycleQueue *q,ElemType e) { if((q->rear+1)%MAXSIZE == q->front) return; q->base[q->rear] = e; q->rear = (q->rear+1)%MAXSIZE; } 出队列操作 void DeleteQueue(cycleQueue *q,ElemType *e) { if(q->front == q->rear) return; *e = q->base[q->front]; q->front = (q->front+1)%MAXSIZE; }
线性表的定义 由零个或多个数据元素组成的有限序列 若元素存在多个,则第一个元素无前驱,而最后一个元素无后继,其他元素都有且只有一个前驱和后继 抽象数据类型(Abstract Data Type,ADT) 数据类型:一组性质相同的值得集合及定义在此集合上的一些操作的总称 抽象:抽取出事物具有的普遍性的本质.它要求抽出问题的特征而忽略非本质的细节,是对具体事务的一个概括.抽象是一种思考问题的方式,它隐藏了繁杂的细节 抽象数据类型:是指一个数据模型以及定义在该模型上的一组操作 线性表的抽象数据类型 Data:线性表的数据对象集合为{a1,a2,...an},每个元素的类型均为DataType.其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素.数据元素之间的关系是一对一的关系 Operation: InitList(*L):初始化操作,建立一个空的线性表L ListEmpty(L):判断线性表是否为空表,若线性表为空,返回true,否则返回false ClearList(*L):将线性表清空 GetElement(L,i,*e):将线性表L中的第i个元素位置返回给e LocateElement(L,e):在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功;否则,返回0表示失败 ListInsert(*L,i,e):在线性表L中第i个位置插入新的元素e ListDelete(L,i,e):删除线性表L中第i个位置元素,并用e返回其值 ListLength(L):返回线性表L的元素个数 线性表的顺序存储 顺序存储的结构代码: #define MAXSIZE 20 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; //线性表当前长度 int length; }SQList; 获得元素操作 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; Status GetElem(SQList L,int i,ElemType *e) { if(L.length==0 || i<1 || i>L.length) { return ERROR; } *e = L.data[i-1]; return OK; } 插入操作 Status ListInsert(SQList *L, int i,ElemType e) { int k; //线性表已将满了 if(L->length == MAXSIZE) { return ERROR; } //不在范围内 if(i < 1 || i>L->length + 1) { return ERROR; } if(i <= L->length) { //将要插入位置后数据元素相互移动一位 for(k=L->length-1; k>=i-1; k--) { L->data[k+1] = L->data[k]; } } //插入新元素 L->data[i-1] = e; L->length++; return OK; } 删除操作 Status ListDelete(SQList *L,int i,ElemType *e) { int k; if(L->length ==0) { return ERROR; } if(i<1 || i>L->length) { return ERROR; } *e = L->data[i-1]; if(i< L->length) { for(k=i; k<L->length; k++) { L->data[k-1] = L->data[k]; } } L->length--; return OK; } 线性表顺序存储的优缺点 优点 无需为表中元素之间的逻辑关系而增加额外的存储空间 可以快速地存取表中任意位置的元素 缺点 插入和删除操作需要移动大量元素 当线性表长度变化较大时,难以确定存储空间的容量 容易造成存储空间的"碎片" 线性表链式存储结构定义 线性表链式存储的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以存储在内存中未被占用的任意位置 比起顺序存储结构每个元素只需要存储一个位置就可以了.现在链式存储结构中,处理要存储数据元素信息外,还要存储它的后继元素的存储地址(指针) 我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域.指针域中存储的信息称为指针或链.这两部分信息组成的数据元素称为存储映像,称为结点(Node) n个节点链接成一个链表,即为线性表的链式存储结构 单链表 因为此链表的每个节点中只包含一个指针域,所以叫做单链表 我们把链表中的第一个节点的存储位置叫做头指针,最后一个节点指针为空(NULL) 头指针 头指针是指链表指向第一个节点的指针,若链表有头结点,则是指向头结点的指针 头指针具有标志作业,所以常用头指针冠以链表的名字 无论链表是否为空,头指针均不为空 头结点 头结点是为了操作的同一和方便而设立的,放在第一个元素结点之前,其数据域一般无意义(也可以用来存放链表的长度) 由来头结点,对在第一个元素结点前插入结点和删除第一个节点的操作与其他结点的操作就统一了 头结点不是链表必须元素 单链表存储结构 typedef int ElemType; typedef struct Node { ElemType data; struct Node* next; }Node; typedef struct Node* LinkList; 假设p是指向线性表第i个元素的指针,则该节点ai的数据域我们可以用p->data的值是一个数据元素,结点ai的指针域可以用p->next来表示,p->next的值是一个指针 获取元素操作 Status GetElem(LinkList L,int i,ElemType *e) { //当前位置 int j; LinkList p; p = L->next; j = 1; while(p && j>i) { p = p->next; ++j; } if(!p || j>i) { return ERROR; } *e = p->data; return OK; } 插入元素操作 Status ListInsert(LinkList *L,int i,ElemType e) { int j; LinkList p,s; p = *L; j = 1; while(p && j < i) { p = p->next; ++j; } if(!p || j>i) { return ERROR; } s = (LinkList)malloc(sizeof(Node)); s->data = e; s->next = p->next; p->next = s; return OK; } 删除操作 Status ListDelete(LinkList *L,int i,ElemType *e) { int j; LinkList p,q; p = *L; j = 1; while(p && j < i) { p = p->next; ++j; } if(!p || j>i) { return ERROR; } q = p->next; p->next = q->next; *e = q->data; free(q); return OK; } 头插发简历单链表 头插法从一个空表开始,生成新节点,读取数据存放到新节点的数据域中,然后将新节点插入到当前链表的表头上,知道结束为止 简单来说就是把新加进来的元素放到表头后的第一个位置 void CreateListHead(LinkList *L,int n) { LinkList p; int i; //初始化随机数种子 srand(time(0)); *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; for(i = 0;i < n; i++) { //生成新节点 p = (LinkList)malloc(sizeof(Node)); p->data = rand()%100+1; p->next = (*L)->next; (*L)->next = p; } } 尾插法建立单链表 头插法建立链表虽然算法简单,但生成的链表中节点的顺序和输入的顺序相反 void CreateListTail(LinkList *L,int n) { LinkList p,r; int i; //初始化随机数种子 srand(time(0)); *L = (LinkList)malloc(sizeof(Node)); r = *L; for(i = 0;i < n; i++) { //生成新节点 p = (LinkList)malloc(sizeof(Node)); p->data = rand()%100+1; r->next = p; //r指向p,重点 r = p; } r->next = NULL; } 单链表的整表删除 Status ClearList(LinkList *L) { LinkList p,q; p = (*L)->next; while(p) { q = p->next; free(p); p = q; } (*L)->next = NULL; return OK; } 单链表结构与顺序存储结构优缺点 我们分别从存储分配方式,时间性能,空间性能三方面来做对比 存储分配方式 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素 时间性能 查找 顺序存储结构O(1) 单链表O(n) 插入和删除 顺序存储结构需要平均移动表长一般的元素,时间为O(n) 单链表在计算出某位置的指针后,插入和删除时间仅为O(1) 空间性能 顺序存储结构需要预分配存储空间,分大了,容易造成空间浪费,分小了,容易发生溢出 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制 结论 若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构 若需要频繁插入和删除操作时,宜采用单链表结构 静态链表 头指向第一个没有数据的地方,尾指向第一个有数据的地方 线性表的静态链表存储结构 #define MAXSIZE 1000 typedef struct { //数据 ElemType data; //游标 int cur; }Component,StaticLinkList[MAXSIZE]; 对静态链表进行初始化(相当于初始化数组) Status InitList(StaticLinkList space) { int i; for(i=0;i<MAXSIZE-1;i++) { space[i].cur = i+1; } space[MAXSIZE-1].cur = 0; return OK; } 数组的第一个元素,即下标为0的那个元素的cur就存放在没有存数据的第一个节点的下标 数组的最后一个元素,即下标为MAXSIZE-1的cur则存放第一个有数值的元素的下标,相当于单链表中的头结点的作用 最后一个可用元素的游标为0 静态链表的插入操作 为了辨明数组中哪些分量未被使用,解决的办法是将所有未被使用过的及已被删除的用游标链成一个备用链表 获取空闲分量的下标 int Malloc_SLL(StaticLinkList space) { int i = space[0].cur; if(space[0].cur) space[0].cur = space[i].cur; return i; } 插入操作 Status ListInsert(StaticLinkList L,int i,ElemType e) { int j,k,l; k = MAX_SIZE - 1; if(i<1 || i>ListLength(L)+1) { return ERROR; } j = Malloc_SLL(L); if(j) { L[j].data = e; for(l=1;l<=i-1;l++) { k = L[k].cur; } L[j].cur = L[k].cur; L[k].cur = j; return OK; } return ERROR; } 删除操作 Status ListDelete(StaticLinkList L,int i) { int j,k; if(i<1 || i>ListLength(L)) { return ERROR; } k = MAX_SIZE - 1; for(j=1;j<=i-1;j++) { k = L[k].cur; } j = L[k].cur; L[k].cur = L[j].cur; Free_SLL(L,j); return OK; } //将下标为k的空间回收到备用链表 void Free_SLL(StaticLinkList space,int k) { space[k].cur = space[0].cur; space[0].cur = k; } int ListLength(StaticLinkList L) { int j = 0; int i = L[MAXSIZE - 1].cur; while(i) { i = L[i].cur; j++; } return j; } 静态链表优缺点 优点 在插入和删除操作时,只需要修改游标,不需要移动元素,从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点 缺点 没有解决连续存储分配带来的表长难以确定的问题 失去了顺序存储结构随机存取的特性 单链表小结:腾讯面试题 题目:快速找到未知长度单链表的中间节点 普通方法很简单,首先遍历一遍单链表以确定单链表的长度L.然后再次从头结点出发循环L/2次找到单链表的中间节点,算法复杂度为:O(L+L/2)=O(3L/2) 利用快慢指针原理:设置两个指针*search,*mid都指向单链表的头节点.其中*search的移动速度是*mid的2倍.当*search指向末尾节点的时候,mid正好就在中间了.这也是标尺的思想,时间复杂度为O(L/2) Status GetMidNode(LinkList L,ElemType *e) { LinkList search,mid; mid = search = L; while(search->next!=NULL) { if(search->next->next!=NULL) { search = search->next->next; mid = mid->next; } else { search = search->next; } } *e = mid->data; return OK; } 循环链表 循环链表不一定要有头结点 其实循环链表的单链表的主要差异就在于循环的判断空链表的条件上,原来判断head->next是否为null,现在则是head->next是否等于head 链表存储结构的定义 typedef struct CLinkList { int data; struct CLinkList *next; }node; 初始化部分 void ds_init(node **pNode) { int item; node *temp; node *target; printf("输入节点的值,输入0完成初始化\n"); while(1) { scanf("%d",&item); fflush(stdin); if(item == 0) return; //循环链表只有一个节点 if((*pNode) == NULL) { *pNode = (node*)malloc(sizeof(struct CLinkList)); if(!(*pNode)) exit(0); (*pNode)->data = item; (*pNode)->next = *pNode; } else { /*找到next指向第一个节点的节点*/ for(target = (*pNode);target->next != (*pNode);target=target->next); //生成一个新节点 temp = (node *)malloc(sizeof(struct CLinkList)); if(!temp) exit(0); temp->data = item; temp->next = *pNode; target->next = temp; } } } 插入部分 void ds_insert(node **pNode,int i) { node *temp; node *target; node *p; int item; int j=1; printf("输入要插入节点的值:"); scanf("%d",&item); if(i==1) { //新插入节点作为第一个节点 temp = (node*)malloc(sizeof(struct CLinkList)); if(!temp) exit(0); temp->data = item; //寻找最后一个节点 for(target = (*pNode);target->next!=(*pNode);target=target->next); temp->next = (*pNode); target->next = temp; *pNode = temp; } else { target = *pNode; for(;j<(i-1);j++) { target = target->next; } temp = (node*)malloc(sizeof(struct CLinkList)); if(!temp) exit(0); temp->data = item; p = target->next; target->next = temp; temp->next = p; } } 删除部分 void ds_delete(node **pNode,int i) { node *target; node *temp; int j = 1; if(i==1) { for(target = (*pNode);target->next!=(*pNode);target=target->next); temp = *pNode; *pNode = (*pNode)->next; target->next = *pNode; free(temp); } else { target = *pNode; for(;j<i-1;j++) { target = target->next; } temp = target->next; target->next = temp->next; free(temp); } } 返回节点所在位置 int ds_search(node *pNode,int elem) { node *target; int i = 1; for(target = pNode;target->data!=elem&&target->next!=pNode;i++) { target = target->next; } if(target->next==pNode) return 0; else return 1; } 约瑟夫问题 据说注明犹太历史学家Josephus有过以下故事:在罗马人占领桥塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被抓到,于是决定了一个自杀的方式,41个人排成一圈,由第1个人开始报数,没报到第3人该人就必须自杀,然后再由下一个重新报数,知道所有人都自杀身亡为止.然而Josephus和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏 代码 #include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node *next; }node; node *create(int n) { node *p = NULL,*head; head = (node*)malloc(sizeof(node)); p = head; node *s; int i=1; if(0!=n) { while(i<=n) { s = (node*)malloc(sizeof(node)); s->data = i++; p->next = s; p = s; } s->next = head->next; } free(head); return s->next; } int main() { int n = 41; int m = 3; int i; node *p = create(n); node *temp; m%=n; while(p!=p->next) { for(i=1;i<m-1;i++) { p = p->next; } printf("%d->",p->next->data); temp = p->next; p->next = temp->next; free(temp); p = p->next; } printf("%d\n",p->data); return 0; } 提高难度 变化为1-N的N个人按顺时针方向围坐一圈,没人持有一个秘密(正整数,可以自由输入),开始人选一个正整数作为上报数上限值M,从第一个人按顺时针方向自1开始顺序报数,报到M时停止报数.报M的人出列,将他的密码作为新的M值,从他顺时针方向上的下一个人开始从1报数,如此下去,直至所有人全部出列为止 将两个带尾指针的循环链表合并 //两个参数为非空链表尾指针 LinkList Connect(LinkList A,LinkList B) { //保存A表的头结点位置 LinkList p = A->next; //B表的开始结点连接到A表尾 A->next = B->next->next; //释放B表的头结点,初学容易忘记 free(B->next); B->next=P; //返回新增循环链表的尾指针 return B; } 判断单链表中是否有环 方法一:使用p,q两个指针,p总是向前走,但q每次都从头开始走,对于每个节点,看p走的步数是否和q一样.如图,当p从6走到3时,用了6部,此时若q从head出发,则只需两步就到3,因而步数不等,出现矛盾,存在环 int HasLoop1(LinkList L) { LinkList cur1 = L; int pos1 = 0; while(cur1) { LinkList cur2 = L; int pos2 = 0; while(cur2) { if(cur2==cur1) { if(pos1 == pos2) break; else{ printf("环的位置在第%d个结点处.\n\n,pos2"); return 1; } } cur2 = cur2->next; pos2++; } cur1 = cur1->next; pos1++; } return 0; } 方法二:使用p,q两个指针,p每次向前走一步,q每次向前走两步,若在某个时候p==q,则存在环 int HasLoop2(LinkList L) { int step1 = 1; int step2 = 2; LinkList p = L; LinkList q = L; while(p!=NULL && q!= NULL && q->next!= NULL) { p = p->next; if(q->next!=NULL) q = q->next->next; printf("p:%d,q:%d \n",p->data,q->data); if(p==q) return 1; } return 0; } 魔术师发牌问题 问题描述:魔术师利用一副牌中的13张黑牌,预先将它们排好后叠到一起,牌面朝下.对观众说:"我不看牌,只数数就可以猜到每张牌是什么,我大声数数,你们听,不信?现场演示"魔术师将最上面的那张牌数为1,把它反过来正好是黑桃A,将黑桃A放在桌子上,第二次数1,2,强![第一张牌放在这些牌的下面,将第二张牌翻过了,正好是黑桃2,也将它放在桌子上这样依次进行将13张牌全部翻出,准确无误 #include <stdio.h> #include <stdlib.h> #define CardNumber 13 typedef struct node { int data; struct node *next; }sqlist,*linklist; linklist CreateLinkList() { linklist head = NULL; linklist s,r; int i; r = head; for(i=1;i<=CardNumber;i++) { s = (linklist)malloc(sizeof(sqlist)); s->data = 0; if(head == NULL) head = s; else r->next = s; r = s; } r->next = head; return head; } //发牌顺序计算 void Magician(linklist head) { linklist p; int j; int Countnumber = 2; p = head; p->data = 1; while(1) { for(j=0;j<Countnumber;j++) { p = p->next; if(p->data!=0) { //p->next; j--; } } if(p->data == 0) { p->data = Countnumber; Countnumber ++; if(Countnumber == 14) break; } } } void DestoryList(linklist *list) { linklist ptr = *list; linklist buff[CardNumber]; int i = 0; while(i<CardNumber) { buff[i++] = ptr; ptr = ptr->next; } for(i=0;i<CardNumber;i++){ free(buff[i]); *list = 0; } } int main() { linklist p; int i; p=CreateLinkList(); Magician(p); printf("按如下顺序排列:\n"); for(i=0;i<CardNumber;i++) { printf("黑桃%d ",p->data); p = p->next; } DestoryList(&p); return 0; } 拉丁方阵问题 拉丁方阵是一种n×n的方阵,方阵中恰有n种不同的元素,每种元素恰有n个,并且每种元素在一行和一列恰好出现一次.著名数学家和物理学家欧拉使用拉丁字母来作为拉丁方阵里元素的符号,拉丁方阵因此而得名 双向链表 双向链表结点结构 typedef struct DualNode { ElemType data; //前驱结点 struct DualNode *prior; //后继结点 struct DualNode *next; }DualNode,*DuLinkList; 插入操作 s->next = p; s->prior = p->prior; p->prior->next = s; p->prior = s 删除操作 p->prior->next = p->next; p->next->prior = p->prior; free(p); 双向循环链表实践 要求用户输入一个数使得26个字母的排列发生变化,例如用户输入3,输出结果: DEFGHIJKLMNOPQRSTUVWXYZABC 同时需要支持负数,例如用户输入-3,输出结果: XYZABCDEFGHIJKLMNOPQRSTUVW #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 typedef char ElemType; typedef int Status; typedef struct DualNode { ElemType data; struct DualNode *prior; struct DualNode *next; }DualNode,*DuLinkList; Status InitList(DuLinkList *L) { DualNode *p,*q; int i; *L = (DuLinkList)malloc(sizeof(DualNode)); if(!(*L)) { return ERROR; } (*L)->next = (*L)->prior = NULL; p = (*L); for(i=0;i<26;i++) { q = (DualNode *)malloc(sizeof(DualNode)); if(!q) { return ERROR; } q->data = 'A'+i; q->prior = p; //为了程序灵活? q->next = p->next; p->next = q; p = q; } p->next = (*L)->next; (*L)->next->prior = p; return OK; } void Caesar(DuLinkList *L,int i) { if(i>0) { do { (*L) = (*L)->next; }while(--i); } if(i<0) { do { (*L) = (*L)->next; }while(++i); } } int main() { DuLinkList L; int i,n; scanf("%d",&n); InitList(&L); Caesar(&L,n); for(i=0;i<26;i++) { L = L->next; printf("%c ",L->data); } printf("\n"); return 0; } 维吉尼亚(Vigenere)加密 当输入明文,自动生成随机密匙匹配明文中每个字母并移位加密 随机密匙不能丢掉,丢掉了就很难把明文还原了,建议把随机密匙和密文存储到一起
什么是数据结构? 数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科 简单来说就是数据元素相互之间存在的一种或多种特定关系的集合 逻辑结构和物理结构 逻辑结构:是指数据对象中数据元素之间的相互关系,也是我们今后最需要关注和讨论的问题 物理结构:是指数据的逻辑结构在计算机中的存储形式 四大逻辑结构: 集合结构:元素之间除了同属一个集合之外没有其他关系 线性结构:元素之间是一对一的关系 树形结构:元素之间是一对多的层次关系 图形结构:元素之间是多对多的关系 物理结构: 根据物理结构的定义,我们实际上研究的就是如何把数据元素存储到计算机的存储器中 存储器主要是针对内存而言的,像硬盘,软盘,光盘等外部存储器的数据组织通常用文件结构来描述 数据元素的存储结构形式有两种:顺序存储和链式存储 顺序存储结构 顺序存储结构:把元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的 例如我们编程语言的数组结构就是这样的 链式存储结构 链式存储结构:是把数据元素放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的 显然,链式存储结构的数据元素存储关系,并不能反映其逻辑关系,因此需要用一个指针存放数据元素的地址,这样子通过地址就可以找到相关联数据元素的位置 什么是算法? 算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有序序列,并且每条指令表示一个或多个操作 算法的特性 输入:算法具有另个或多个输入 输出:有一个或多个输出 有穷性:算法在执行有限步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成 确定性:算法的每一个步骤都具有确定的含义,不会出现二义性 可行性:算法的每一步必须都是可行的,也就是说,每一步都能够通过执行有限次数完成 算法设计的要求 正确性:算法的正确性是指算法至少应该具有输入,输出和加工处理无歧义性,能正确反映问题的需求,能够得到问题的正确答案 四个层次: 算法程序没有语法错误 算法程序对于合法输入能够产生满足要求的出处 算法程序对于非法输入能够产生满足规格的说明 算法程序对于故意刁难的测试输入都有满足要求的输出结构 可读性:算法设计的另一个目的是为了便于阅读,理解和交流 健壮性:当输入数据不合法时,算法也能做出相关处理,二不是产生异常,崩溃或莫名奇妙的结果 时间效率高和存储量低 算法时间复杂度 在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级.算法的时间复杂度,也就是算法的时间度量.它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度.其中f(n)是问题规模n的某个函数 用大写O()来提现算法时间复杂度的记法,称之为大O记法 一般情况,随着输入规模n的增大,T(n)增长最慢的算法为最优算法 常见的时间复杂度 O(1) 常数阶 O(n) 线性阶 O(n^2) 平方阶 O(logn) 对数阶 O(nlogn) nlogn阶 O(n^3) 立方阶 O(2^n) 指数阶 算法的空间复杂度 算法的空间复杂度通过计算算法所需的存储空间实现,算法的空间复杂度的计算公式记作:S(n)=O(f(n)),其中n为问题的规模,f(n)为语句关于n所占存储空间的函数 通常我们用 "时间复杂度" 来指运行时间的需求,使用 "空间复杂度" 指空间需求
ORM(Object RelationShip Mapping)的基本思想 表结构跟类对应;表中的字段和类的属性对应;表中的记录和对象对应 让javabean的属性名和类型尽量和数据库保持一致 一条记录对应一个对象,将这些查询到的对象放到容器中 将表中的一条记录封装到Object数组中 将表中的一条记录封装到map中 将表中一条记录封装到javabean对象中 封装连接和关闭 import java.io.IOException; import java.sql.Connection; import java.sql.DriverManager; import java.sql.ResultSet; import java.sql.SQLException; import java.sql.Statement; import java.util.Properties; public class JDBCUtil { //用于读取资源文件中的信息 static Properties pros = null; //加载JDBCUtil类的时候调用 static { pros = new Properties(); try { pros.load(Thread.currentThread().getContextClassLoader() .getResourceAsStream("db.properties")); } catch (IOException e) { e.printStackTrace(); } } public static Connection getConnection(){ try { Class.forName(pros.getProperty("Driver")); return DriverManager.getConnection(pros.getProperty("Url"), pros.getProperty("User"), pros.getProperty("Password")); } catch (ClassNotFoundException e) { e.printStackTrace(); } catch (SQLException e) { e.printStackTrace(); } return null; } public static void close(ResultSet rs,Statement st,Connection conn){ try { if(rs!=null){ rs.close(); } } catch (SQLException e) { e.printStackTrace(); } try { if(st!=null){ st.close(); } } catch (SQLException e) { e.printStackTrace(); } try { if(conn!=null){ conn.close(); } } catch (SQLException e) { e.printStackTrace(); } } } 使用Object数组封装一条记录 import java.sql.Connection; import java.sql.PreparedStatement; import java.sql.ResultSet; import java.sql.SQLException; import java.util.ArrayList; import java.util.List; /** * 测试使用Object[]来封装一条记录 * 使用List<Object[]>存储多条记录 * @author Matrix42 * */ public class Demo01 { public static void main(String[] args) { Connection conn = JDBCUtil.getConnection(); PreparedStatement ps = null; ResultSet rs = null; Object[] obj = null; List<Object[]> list = new ArrayList<Object[]>(); //Alt+Shift+Z add try-catch block try { ps = conn.prepareStatement("select empname,salary,age from emp where id = ?"); ps.setObject(1, 1); rs = ps.executeQuery(); while(rs.next()){ //System.out.println(rs.getString("empname")); obj = new Object[3]; //一个Object封装一条数据 //多条可以用容器 obj[0] = rs.getObject(1); obj[1] = rs.getObject(2); obj[2] = rs.getObject(3); list.add(obj); } } catch (SQLException e) { e.printStackTrace(); }finally{ JDBCUtil.close(rs, ps, conn); } //连接关闭后还可以获取内容 for (Object[] objs : list) { System.out.println(""+objs[0]+"\n"+objs[1]+"\n"+objs[2]); } } } 使用Map封装一条记录 import java.sql.Connection; import java.sql.PreparedStatement; import java.sql.ResultSet; import java.sql.SQLException; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /** * 测试使用Map来封装一条记录 * 使用List<Map>存储多条记录 * @author Matrix42 * */ public class Demo02 { public static void main(String[] args) { Connection conn = JDBCUtil.getConnection(); PreparedStatement ps = null; ResultSet rs = null; //使用一个Map封装一条记录 List<Map<String, Object>> list = new ArrayList<Map<String, Object>>(); //Alt+Shift+Z add try-catch block try { ps = conn.prepareStatement("select empname,salary,age from emp where id < ?"); ps.setObject(1, 3); rs = ps.executeQuery(); while(rs.next()){ Map<String, Object> row = new HashMap<String, Object>(); row.put("empname", rs.getObject(1)); row.put("salary", rs.getObject(2)); row.put("age", rs.getObject(3)); list.add(row); } } catch (SQLException e) { e.printStackTrace(); }finally{ JDBCUtil.close(rs, ps, conn); } //连接关闭后还可以获取内容 for (Map<String, Object> map : list) { System.out.println(map.get("empname")); System.out.println(map.get("salary")); System.out.println(map.get("age")); } } } 使用javabean对象封装一条记录 import java.sql.Date; //表和类对应 /** * emp表的javabean * @author Matrix42 * */ public class Emp { private Integer id; private String empname; private Double salary; private Date birthday; private Integer age; private Integer deptId; //javabean一定要有空构造器 public Emp() { super(); } public Emp(String empname, Double salary, Date birthday, Integer age, Integer deptId) { super(); this.empname = empname; this.salary = salary; this.birthday = birthday; this.age = age; this.deptId = deptId; } public Emp(Integer id, String empname, Double salary, Date birthday, Integer age, Integer deptId) { super(); this.id = id; this.empname = empname; this.salary = salary; this.birthday = birthday; this.age = age; this.deptId = deptId; } public Integer getId() { return id; } public void setId(Integer id) { this.id = id; } public String getEmpname() { return empname; } public void setEmpname(String empname) { this.empname = empname; } public Double getSalary() { return salary; } public void setSalary(Double salary) { this.salary = salary; } public Date getBirthday() { return birthday; } public void setBirthday(Date birthday) { this.birthday = birthday; } public Integer getAge() { return age; } public void setAge(Integer age) { this.age = age; } public Integer getDeptId() { return deptId; } public void setDeptId(Integer deptId) { this.deptId = deptId; } //方便打印 @Override public String toString() { return "Emp [id=" + id + ", empname=" + empname + ", salary=" + salary + ", birthday=" + birthday + ", age=" + age + ", deptId=" + deptId + "]"; } } /** * dept表的javabean * @author Matrix42 * */ public class Dept { private Integer id; private String address; private String dname; public Dept() { super(); } public Dept(String address, String dname) { super(); this.address = address; this.dname = dname; } public Dept(Integer id, String address, String dname) { super(); this.id = id; this.address = address; this.dname = dname; } public Integer getId() { return id; } public void setId(Integer id) { this.id = id; } public String getAddress() { return address; } public void setAddress(String address) { this.address = address; } public String getDname() { return dname; } public void setDname(String dname) { this.dname = dname; } } import java.sql.Connection; import java.sql.PreparedStatement; import java.sql.ResultSet; import java.sql.SQLException; import java.util.ArrayList; import java.util.List; /** * 测试使用javabean来封装一条记录 * 使用List<javabean>存储多条记录 * @author Matrix42 * */ public class Demo03 { public static void main(String[] args) { Connection conn = JDBCUtil.getConnection(); PreparedStatement ps = null; ResultSet rs = null; //使用一个Map封装一条记录 List<Emp> list = new ArrayList<Emp>(); //Alt+Shift+Z add try-catch block try { ps = conn.prepareStatement("select empname,salary,age from emp where id < ?"); ps.setObject(1, 3); rs = ps.executeQuery(); while(rs.next()){ Emp emp = new Emp(rs.getString(1),rs.getDouble(2),null,rs.getInt(3),null); list.add(emp); } } catch (SQLException e) { e.printStackTrace(); }finally{ JDBCUtil.close(rs, ps, conn); } //连接关闭后还可以获取内容 for (Emp emp : list) { System.out.println(emp); } } }
CLOB CLOB(Character Large Object) 用于存储大量的文本数据 大字段有些特殊,不同数据库处理的方式不一样,大字段的操作常常是以流的方式来处理的,而非一般的字段,一次即可读出数据 MySQL中相关类型 TINYTEXT最大长度为255(2^[8]-1)字符的TEXT列 TEXT(M)最大长度为65535(2^[16]-1)字符的TEXT列 MEDIUMTEXT最大长度为16777215(2^[24]-1)字符的TEXT列 LONGTEXT最大长度为4294967295或4G(2^[32]-1)字符的TEXT列 BLOB BLOB (Binary Large Object) 用于存储大量的二进制数据 大字段有些特殊,不同数据库处理的方式不一样,大字段的操作常常是以流的方式来处理的,而非一般的字段,一次即可读出数据 Code import java.io.IOException; import java.io.Reader; import java.sql.Clob; import java.sql.Connection; import java.sql.DriverManager; import java.sql.PreparedStatement; import java.sql.ResultSet; import java.sql.SQLException; /** * 测试CLOB文本大对象的使用 * 将字符串,文件内容插入到数据库中的CLOB字段,将CLOB字段读取出来 * @author Matrix42 * */ public class Demo09 { public static void main(String[] args) { Connection conn = null; PreparedStatement ps = null; ResultSet rs = null; try { // 加载驱动 Class.forName("com.mysql.jdbc.Driver"); conn = DriverManager.getConnection( "jdbc:mysql://localhost:3306/testjdbc", "root", "123456"); ps = conn.prepareStatement("insert into t_user(username,myinfo) values (?,?)"); ps.setString(1, "Matrix42"); //将文本文件输入到数据库 //ps.setClob(2, new FileReader(new File("D:/a.txt"))); //将程序中的字符串写入到数据库 //ps.setClob(2,new BufferedReader(new InputStreamReader(new ByteArrayInputStream("asasasas".getBytes())))); //ps.execute(); ps = conn.prepareStatement("select * from t_user where id = ?"); ps.setObject(1, 6); rs = ps.executeQuery(); while(rs.next()){ Clob clob = rs.getClob("myinfo"); Reader reader = clob.getCharacterStream(); int tmp = 0; while((tmp=reader.read())!=-1){ System.out.print((char)tmp); } } } catch (ClassNotFoundException e) { e.printStackTrace(); } catch (SQLException e) { e.printStackTrace(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } finally { //一定要分开,防止一个出现异常其余不能关闭 try { if (conn != null) { conn.close(); } } catch (SQLException e) { e.printStackTrace(); } try { if (ps!=null) { ps.close(); } } catch(SQLException e){ e.printStackTrace(); } try { if (conn!=null) { conn.close(); } } catch(SQLException e){ e.printStackTrace(); } } } } MySQL中相关类型 TINYTBLOB最大长度为255(2^[8]-1)字符的BLOB列 BLOB(M)最大长度为65535(2^[16]-1)字符的BLOB列 MEDIUMBLOB最大长度为16777215(2^[24]-1)字符的BLOB列 LONGBLOB最大长度为4294967295或4G(2^[32]-1)字符的BLOB列 import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.io.InputStream; import java.sql.Blob; import java.sql.Connection; import java.sql.DriverManager; import java.sql.PreparedStatement; import java.sql.ResultSet; import java.sql.SQLException; /** * 测试BLOB二进制大对象的使用 * @author Matrix42 * */ public class Demo10 { public static void main(String[] args) { Connection conn = null; PreparedStatement ps = null; ResultSet rs = null; try { // 加载驱动 Class.forName("com.mysql.jdbc.Driver"); conn = DriverManager.getConnection( "jdbc:mysql://localhost:3306/testjdbc", "root", "123456"); ps = conn.prepareStatement("insert into t_user(username,myinfo) values (?,?)"); ps = conn.prepareStatement("insert into t_user(username,head) values (?,?)"); ps.setObject(1, "Lorinda"); ps.setBlob(2, new FileInputStream(new File("D:100.jpg"))); ps.execute(); ps = conn.prepareStatement("select * from t_user where id = ?"); ps.setObject(1, 8); rs = ps.executeQuery(); FileOutputStream fos = new FileOutputStream(new File("D:/head.jpg")); while(rs.next()){ Blob blob = rs.getBlob("head"); InputStream is = blob.getBinaryStream(); int tmp = 0; while((tmp=is.read())!=-1){ fos.write(tmp); } } } catch (ClassNotFoundException e) { e.printStackTrace(); } catch (SQLException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } finally { //各种关闭就不写了 //一定要分开,防止一个出现异常其余不能关闭 try { if (conn != null) { conn.close(); } } catch (SQLException e) { e.printStackTrace(); } try { if (ps!=null) { ps.close(); } } catch(SQLException e){ e.printStackTrace(); } try { if (conn!=null) { conn.close(); } } catch(SQLException e){ e.printStackTrace(); } } } }
时间类型 java.util.Date 子类:java.sql.Date 示年月日 子类:java.sql.Time 表示时分秒 子类:java.sql.Timestamp 表示年月日时分秒 日期比较处理 插入随机日期 取出指定日期范围的记录 Code /** * 测试事件处理(java.sql.Date,Time,Timestamp) * @author Matrix42 * */ public class Demo07 { public static void main(String[] args) throws InterruptedException { Connection conn = null; PreparedStatement ps = null; PreparedStatement ps1 = null; try { Class.forName("com.mysql.jdbc.Driver"); conn = DriverManager.getConnection("jdbc:mysql://localhost:3306/testjdbc","root","123456"); String sql = "insert into t_user(username,pwd,regTime,lastLoginTime) values(?,?,?,?)"; ps = conn.prepareStatement(sql); ps.setObject(1, "Matrix42"); ps.setObject(2, 123456); Date date = new java.sql.Date(System.currentTimeMillis()); ps.setObject(3, date); //如果需要插入指定日期,可以使用Calendar,DateFormat类 ps.setTimestamp(4, new java.sql.Timestamp(System.currentTimeMillis())); //随机日期 //int rand = 10000000 + new Random().nextInt(100000000); //Timestamp stamp = new Timestamp(System.currentTimeMillis()-rand); ps.execute(); } catch (ClassNotFoundException e) { e.printStackTrace(); } catch (SQLException e) { try { conn.rollback(); } catch (SQLException e1) { e1.printStackTrace(); } e.printStackTrace(); } //关闭连接 } } /** * 取出指定时间段的内容 * @author Matrix42 * */ public class Demo08 { /** * 将字符串代表的日趋转换为long(格式: yyyy-MM-dd hh:mm:ss) * @param args * @throws InterruptedException */ public static long str2Date(String dateStr){ DateFormat format = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss"); try { return format.parse(dateStr).getTime(); } catch (ParseException e) { e.printStackTrace(); } return 0; } public static void main(String[] args) throws InterruptedException { Connection conn = null; PreparedStatement ps = null; ResultSet rs = null; try { Class.forName("com.mysql.jdbc.Driver"); conn = DriverManager.getConnection("jdbc:mysql://localhost:3306/testjdbc","root","123456"); ps = conn.prepareStatement("select * from t_user where regTime > ? and regTime < ?"); java.sql.Date start = new java.sql.Date(str2Date("2016-11-11 10:23:45")); java.sql.Date end = new java.sql.Date(str2Date("2016-12-23 10:23:45")); ps.setObject(1, start); ps.setObject(2, end); rs = ps.executeQuery(); while (rs.next()) { System.out.println(rs.getInt("id")); System.out.println(rs.getString("username")); System.out.println(rs.getDate("regTime")); System.out.println(rs.getTimestamp("lastLoginTime")); } } catch (ClassNotFoundException e) { e.printStackTrace(); } catch (SQLException e) { e.printStackTrace(); } //关闭连接 } }
批处理 Batch 对于大量的批处理,建议使用Statement,因为PreparedStatement的预编译空间有限,当数据量特别大时,会发生异常 Code import java.sql.Connection; import java.sql.DriverManager; import java.sql.SQLException; import java.sql.Statement; /** * 批处理的基本用法 * @author Matrix42 * */ public class Demo05 { public static void main(String[] args) { Connection conn = null; Statement stmt = null; try { Class.forName("com.mysql.jdbc.Driver"); conn = DriverManager.getConnection("jdbc:mysql://localhost:3306/testjdbc","root","123456"); stmt = conn.createStatement(); //把事物设置为手动提交 conn.setAutoCommit(false); long start = System.currentTimeMillis(); for(int i=0;i<20000;i++){ stmt.addBatch("insert into t_user(username,pwd,regTime) values('matrix"+i+"',666666,now())"); } stmt.executeBatch(); //提交事物 conn.commit(); long end = System.currentTimeMillis(); System.out.println("插入20000条数据,耗时(ms):"+(end-start)); } catch (ClassNotFoundException e) { e.printStackTrace(); } catch (SQLException e) { // TODO Auto-generated catch block e.printStackTrace(); } //关闭连接 } } 事务 事物的概念 一组要么同时执行成功,要么同时执行失败的SQL语句.是数据库操作的一个执行单元 事务开始于: 连接到数据库上,并执行一条DML语句(INSERT,UPDATE或DELETE) 前一个事务结束后,又输入了另外一条DML语句 事务结束于: 执行COMMIT或ROLLBACK语句 执行一条DDL语句,例如CREATE TABLE语句;在这种情况下会自动执行COMMIT语句 执行一条DCL语句,例如GRANT语句;在这种情况下,会自动执行COMMIT语句 断开与数据库的连接 执行了一条DML语句,改语句却失败了;在这种情况下,会为这个无效的DML语句执行ROLLBACK语句 事物的四大特性(ACID) atomicity(原子性) 表示一个事务内的所有操作是一个整体,要么全部成功,要么全部失败 consistency(一致性) 表示一个事务内有一个操作失败时,所有的更改过的数据都必须回滚到修改前的状态 isolation(隔离性) 事务查看数据时数据所处的状态,要么是另一个并发事物修改它之前的状态,要么是另一事物修改它之后的状态,事物不会查看中间状态的数据 durablity(持久性) 持久性事物完成之后,它对于系统的影响是永久性的 事务隔离级别从低到高 读取未提交(Read Uncommitted) 读取已提交(Read Committed)(默认) 可重复读(Repleatable Read) 序列化(serializable) Code 第二条会报错,会回滚 import java.sql.Connection; import java.sql.DriverManager; import java.sql.PreparedStatement; import java.sql.SQLException; /** * 事务的基本用法 * @author Matrix42 * */ public class Demo06 { public static void main(String[] args) throws InterruptedException { Connection conn = null; PreparedStatement ps = null; PreparedStatement ps1 = null; try { Class.forName("com.mysql.jdbc.Driver"); conn = DriverManager.getConnection("jdbc:mysql://localhost:3306/testjdbc","root","123456"); //JDBC中默认自动提交事物 conn.setAutoCommit(false); String sql = "insert into t_user(username,pwd) values(?,?)"; ps = conn.prepareStatement(sql); ps.setObject(1, "Matrix42"); ps.setObject(2, 123456); ps.execute(); System.out.println("插入一个用户!"); Thread.sleep(6000); ps1 = conn.prepareStatement("insert into t_user(username,pwd) values(?,?,?)"); ps1.setObject(1, "Matrix42"); ps1.setObject(2, 123456); ps1.execute(); System.out.println("插入另外一个用户!"); conn.commit(); } catch (ClassNotFoundException e) { e.printStackTrace(); } catch (SQLException e) { try { conn.rollback(); } catch (SQLException e1) { e1.printStackTrace(); } e.printStackTrace(); } //关闭连接 } }
依赖 Kafka需要依赖ZooKeeper,在搭建Kafka集群前先要搭建好ZooKeeper集群 参考搭建ZooKeeper集群 下载Kafka 下载地址 我们使用的版本是:0.9.0.0 解压 tar -zxvf kafka_2.10-0.9.0.0.tgz 配置 配置文件为config下的server.properties broker.id=0 #broker.id为broker的唯一标识,不能重复,不能为负数 listeners=PLAINTEXT://:9981 #Kafka监听地址 port=9981 #broker server服务端口 host.name=node3 # hostname,可以是字符串也可以是ip log.dirs=/tmp/kafka9-logs #log存放地址,当你更改broker id时要清理log再启动 zookeeper.connect=node1:2181,node2:2181,node3:2181/kafka9 #zookeeper地址,有多个用逗号分隔,如果使用子目录只在最后一个加上地址即可 使用Kafka 启动Kafka ./kafka-server-start.sh -daemon ../config/server.properties #不显示日志 ./kafka-server-start.sh ../config/server.properties #显示日志 建立topic ./kafka-topics.sh --create --zookeeper node1:2181/kafka9 --replication-factor 1 --partitions 1 --topic matrix81 删除topic ./kafka-topics.sh --delete --zookeeper node1:2181 --topic matrix 列出所有topic ./kafka-topics.sh --list --zookeeper node1:2181 console producer ./kafka-console-producer.sh --broker-list node4:9981 --top matrix81 console consumer ./kafka-console-consumer.sh --zookeeper node1:2181 --topic matrix81 --from-beginning 资料 Kafka Quickstart kafka参数配置详解 kafka 系统配置说明