设计一个算法利用顺序栈判断一个字符串是否是对乘串。所谓对称串是指从左向右读和从右向左读的序列相同。
解：字符串str的所有元素依次进栈,产生的出栈序列正好与str的顺序相同，则str是对称串。
bool symmetry(ElemType str[]){
int i;
ElementType e;
SqStack *st;
InitStack(st); //初始化栈
for(i=0;str[i]!+'\0';i++) //将串所有元素入栈
push(st,str[i]); //元素进栈
for(i=0;str[i]!+'\0';i++){
pop(st,e); //退栈元素e
if(str[i]!=e){ //若e与当前串元素不同时则不是对称串
destroyStack(st); //销毁栈
return false;
}
}
destroyStack(st); //销毁栈
return true;
}
编写一个算法判断输入的表达式中括号是否配对。
解：一个表达式中的左右括号是按最近位置配对的。所以利用一个栈来进行求解。这里采用链栈。
遇到”(“入栈，遇到”)”出栈，匹配条件：栈为空且指针指向字符串末
bool Match(char exp[],int n){
int i=0;char e;
bool match=true;
LiStack *st;
InitStack(st); //初始化栈
whle(i<n && match){ //扫描exp中的所有字符
if(exp[i]=='(')
Push（st,exp[i]);
else if(exp[i]==')'){ //当前字符为右括号
if(e!='(') //栈顶元素不为(时表示不匹配
match=false;
else
Pop(st,e); //将栈顶元素出栈
}else match=false; //无法取栈顶元素时表示不匹配
}
if(!StackEmpty(st)) match=false; //栈不空时，表示不匹配
DestroyStack(st); //销毁栈
return match;
}
给定一个M * N的迷宫图、入口与出口、行走规则。求一条从指定入口到出口的路径。所求路径必须是简单路径，不能重复。
设置一个迷宫数组mg，其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时表示对应方块不可走
bool mgpath(int xi,int yi, int xe,int ye){
int i,j,k,di,find;
StType st;
st.top=-1; //定义栈st并初始化
st.top++; //初始方块进栈
st.data[st.top].i=xi; st.data[st.top].j=yi;
st.data[st.top].di=-1; mg[xi][yi]=-1;
while(st.top>-1){ //栈不空时循环
i=st.data[st.top].i;
j=st.data[st.top].j;
di=st.data[st.top].di; //取栈顶方块
if(i==xe && j=ye){
for(k=0;k<=st.top;k++)
}
}
}
while(从exp读取字符ch，ch!='0'){
ch为数字：将后续的所有数字均依次存放到postexp中，并以字符"#"标志数值串结束；
ch为左括号"("：将此括号进栈到Optr中；
ch为右括号")"：将Optr中出栈时遇到的第一个左括号"("以前的运算符依次出栈并存放到postexp中，然后将左括号"("出栈;
ch为其他运算符：if(栈空或者栈顶运算符为'(') 直接将ch进栈；
else if(ch的优先级高于栈顶运算符的优先级)
直接将ch进栈
else
依次出栈并存入到postexp中，直到栈顶运算符优先级小于ch的优先级，然后将ch出栈；
}
若exp扫描完毕，则将Optr中所有运算符依次出栈并存放到postexp中。
//对postexp进行求值
while(从postexp读取字符ch，ch!='\0'){
ch为'+':从Opnd栈中出栈两个数值a和b，计算c=b+a;将c入栈;
ch为'-':从Opnd栈中出栈两个数值a和b，计算c=b-a;将c入栈;
ch为'*':从Opnd栈中出栈两个数值a和b，计算c=b*a;将c入栈;
ch为'/':从Opnd栈中出栈两个数值a和b，若a不为零;计算c=b/a;将c进栈;
ch为数字字符:将连续的数字串转换成数值d，将d进栈;
}
返回Opnd栈的栈顶操作数即后缀表达式的值；
定义：句子的主体，所描述的对象。
谁来做，常由名词、代词、主语从句、有名词功能的词（doing、to do）来担任。
eg：
①The boy is very happy. n.名词
②I love you. 代词
③That he has come back is said. 主语从句
在英语中，当主语大于一个单词，习惯用形式主语 it 来代替，真正的主语放在最后。
It is said that he has come back.
That he changed surprised us. → It is surprised us that he changed.
学习英语 benefits us.
Learn English benefits us. 错误，Learn是动词。
Learning English benefits us. 正确。
见到你 is nice.
Meet you is nice. 错误，meet是动词。
Meeting you is nice. 正确。
It is nice to meet you. 正确。
当doing作主语，并且多于一个单词，一般不用 it 代替。
当to do作主语，并且多于一个单词，一般用 it 代替。
定义：形容作主语动作或状态的成分，放在主语之后。
常由实义动词、系动词（或结合助动词、情态动词一起）来担任。
动词按照语义和在谓语中的作用可分为四类：实义动词、系动词、助动词、情态动词。
实义动词
① 表示物体的动作 一般能做出来，比如：跑、走、起床、刷牙…
② 语义完整
③ 可单独做谓语
LiMing runs fast.
系动词
① 表示物体状态、性质 做不出来的动作
② be / 感官动词 / 变化动词 是
感官动词比较特殊：
比如，smell 闻，闻这个动作能做出来，是一个实义动词，但是它表示“闻起来”时，蛋糕闻起来很香甜，这个“闻起来”就做不出来，是一个感官动词。类似的还有 听起来，看起来
变化动词：
天气变冷了。 这个就做不出来，属于变化动词。
助动词
① 帮助实义动词、系动词构成
xm likes xh. xm doesn’t likes xh. 帮助 likes 完成否定
② 否定句，疑问句，各种时态，被动语态。
Does huge like xm.
Will xm like xl? xm以后会喜欢xl吗？ will帮助构成将来时。
xm is liked by himself. is作助动词，like实义动词，被动语态
③ 无语义
④ 不可单独做谓语
⑤ be / have / will
情态动词
① 表示说话人情绪、态度、语气
② 语义不完整
③ 不可单独作谓语
④ can / may / must / need 等
I may be go there. 我可能去那。 ×
I may go there. may 情态动词，表态度
- Mother bought me a new computer.
- We all have agreed on the contract.
- We are students.
- Can you do it ? 情态动词 + 实义动词 -> 谓语
定义：动作的承受者，放在谓语之后。
常由名词、代词、宾语从句，有名词功能的词（doing、to do）来担任。
① He published many books. 名词
② She said that she would come back on time. 宾语从句
I love 阅读. I love read. ×
I love reading. I love to read. √
定义：对于主语、宾语的补充
常由名词、形容词、介词短语担任
① He makes his family proud. 他使他的家人感到骄傲。
He 主语 ，makes 谓语 ，his family 宾语 ，proud 补语 使语义完整。
② I named my cat Tom. 我为我的猫取名Tom。
③ They found everything in good condition.
定义：系动词之后对主语的补语
常由名词、形容词、介词短语构成。
He looks very angry. looks 看起来
I am student.
定义：形容修饰名词的成分
常由形容词、名词、数词、定语从句、非谓语、介词短语来担任。
red big 苹果
红 和 大都是说苹果，且彼此独立，big 和 red 是 单个定语成分。
单个定语成分：
=1一个单词 → 前置 → 定语 n
>1个单词 → 后置 → the n 定语
It’s an interesting story. it 主语 ，is 系/谓语 ，interesting 定语 ，stroy 表语
I can see a lemon tree from my room.
who is the woman in red ? >1个单词
The man who is your friend is here. >1个单词，后置
定义：用于修饰动词、形容词、副词、全句的成分。
一般由 副词、介词短语、状语从句担任。
在句中表时间、地点、方式、让步、目的、原因、条件、结果、比较等语义。
He runs fast. fast 副词
Her uncle lives in Canada.
The uress is stunningly beautiful. 修饰beautiful
The American boy speeks chinese very well. American定语，very well修饰speeks
Fortunately , he survived the file. 幸运地
8.同位语
定义：若两个语法单位指同一个人或事物，并且句法功能也一样，那么后一项称前一项的同位语。
常由名词、代词、有名词功能的词、同位语从句来担任。
This is my friend Harry. my friend == Harry
We students should study hard. We == students
This is my job , teaching students.
The boss himself interviewed the job applicant.
The face that he is here is true.
已知长度为N的线性表A采用顺序存储结构。设计一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。
解：以下两种方法都不满足要求：
//解法一：设删除A中所有值等于x元素后的顺序表位A1,，显然A1包含在A中，为此A1重用A的空间
public void delonde1(SqList *&A,ElemType x){
int k=0,i; //k记录值不等于x的元素个数
for(i=0;i<arr.length;i++)
if(A->data[i]!=x){ //若当前元素不为x,将其插入A中
A->data[k] = A->data[i];
k++; //不等于x的元素增1
}
A.length=k; //顺序表A的长度等于k
}
//解法二：用k记录顺序表A中等于x的元素个数，一边扫描A以便统计k值
public void delonde1(SqList *&A,ElemType x){
int k=0,i=0; //k记录值不等于x的元素个数
while(i<A->length){
if(A->data[i]==x) k++; //当元素值为x时k增1
else A->data[i-k] = A->data[i]; //当前元素不为x时将其前移k个位置
i++;
}
A.length=k; //顺序表A的长度等于k
}
设顺序表L有10个正整数。设计一个算法，以第一个元素为分界线，将所有小于等于它的元素移到该元素的前面，将所有大于它的元素移到该元素后面。
//解法一：i从前向后找>pivot的元素，j从后向前找<=pivot的元素，两者交换
void move1(int[] arr) {
int i=0,j=arr.length-1,temp;
int pivot = arr[0];
while(i<j) {
//从后向前扫描，再找一个<=pivot的元素
while(i<j&&arr[j]>pivot)
j--;
while(i<j&&arr[i]<=pivot)
i++;
if(i<j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[0];
arr[0]=arr[j];
arr[j] = temp;
}
//解法二：j从后向前找下雨等于pivot的元素：前移；i从前向后找大于pivot的元素：后移。性能比方法一更好
void move2(int[] arr) {
int i=0,j=arr.length-1;
int pivot = arr[0];
while(i<j) {
//从后向前扫描，再找一个<=pivot的元素
while(i<j&&arr[j]>pivot)
j--;
arr[i]=arr[j];
while(i<j&&arr[i]<=pivot)
i++;
arr[j]=arr[i];
}
arr[j] = pivot;
}
设计一个算法，删除一个单链表L中元素值最大的节点。
//定义两个指针pre和p同步向后移动，指针maxpre记录最大值的前驱,maxp记录最大值位置
void delmaxnode(LinkList *&L){
LinkList *p=L->next,*pre=L,*maxpre=pre,*maxp=p;
while(p!=NULL){
if(maxp->data < p->data){ //若找到一个更大的结点
maxp = p;
maxpre = pre;
}
pre = p;
p = p->next;
}
maxpre->next = maxxp->next; //删除*maxp节点
free(maxp); //释放*maxp节点
}
有一个带头节点的单链表L，设计一个算法使其元素递增有序排列。
void sort(LinkList *&L){
LinkList *p,*pre,*p;
p=L->next->next; //P指向L的第2个数据节点
L->next->next=NULL; //构造只含一个数据节点的有序表
while(p!=NULL){
q=p->next; //q保存*p节点后继节点的指针
pre=L; //从有序表开头进行比较，pre指向插入*p的前驱节点
while(pre->next!=NULL && pre->next->data < p->data)
pre=pre->next; //在有序表中找插入*p的前驱节点*pre
p->next = pre->next;
pre->next = p;
p=q; //扫描单链表余下的结点
}
}
假设有一个带头结点的单链表L={a1,a2,…,an}。设计一个算法将所有节点逆置。
//头插法
void Reverse(LinkList *&L){
LinkList *p = L->next,*p;
L->next = NULL;
while(p!=NULL){
q = p->next;
p->next = L->next;
L->next = p;
p = q;
}
}
假设有一个带头结点的单链表L={a1,b2,a2,v2,…,an,bn}。设计一个算法将其拆分成两个带头结点的单链表L1和L2: L1={a1,a2,…}，L2={b1,b2,…}，要求L1使用L的头结点
void split(LinkList *&L,LinkList *&L1,LinkList *&L2){
LinkeList *p = L->next,*p,*r1; //p指向第1个数据节点
L1 = L; //L1利用原来L的头结点
r1 = L1; //r1四种指向L1的尾节点
L2 = （LinkList *)malloc(sizeof(LinkList)); //创建L2的头结点
L2->next = NULL; //置L2的指针域为NULL
while(p!=NULL){
r1->next = p; //采用尾插法将*p插入L1中
r1 = p;
p = p->next; //p移向后一个节点
q = p->next; //用q保存*p的后继节点
p->next = L2->next; //采用头插法将*p插入L2中
L2->next = p;
p=q; //p重新指向 a i+1 的结点
}
r1->next = NULL; //尾节点next置空
}
设有一个条块序列，每个条块为红(0)、白(1)、兰(2)三种颜色中的一种。假设该序列采用顺序表/单链表存储，设计一个时间复杂度为O(n)的算法，使得这些条块按红、白、兰的顺序排好，即排成荷兰国旗图案。
解1：用0~i表示0元素区间，k~n-1表示2元素区间，中间部分为1元素区间，用j从头开始扫描顺序表L中部的所有元素。
每一次循环：
void move1(SqList *&L){
int i=-1,j=0,k=L->length;
while(j<k){
if(L->data[j]==0){
i++;
swap(L->data[i],L->data[j]);
j++
}else if(L->data[j]==2){
k--;
swap(L->data[k],L->data[j]);
}else j++;
}
}
解2：用p指针扫描节点，根据p->data值将该节点插入到3个单链表L、L1和L2（L1和L2不带头节点的）中，最后将它们连接起来。
void move2(LinkList *&L){
LinkList *L1,*L2,*r1,*r2,*p;
L1=NULL;
L2=NULL;
p=L->next;
r=L;
while(p!=NULL){
if(p->data==0){ //建立L带头节点的单链表
r->next=p;r=p;
}else if(p->data==1){ //建立L1不带头节点的单链表
if(L1==NULL) {L1=p;r1=p;}
else {r1->next=p;r1=p;}
}else{
if(L2==NULL) {L2=p;r2=p;}
else {r2->next=p;r2=p;}
}
p=p->next;
}
r->next=r1->next=r2->next=NULL;
r->next=L1;
r1->next=L2;
}
有一个带头节点的双链表L，设计一个算法将其所有元素逆置，即第1个元素变成最后一个元素，第2个元素变成倒数第2个元素，…，最后一个元素编程第1个元素
void Reverse(DLinkList *&L){
DLinkList *p=L->next,*p; //p指向
L->next=NULL; //构造只有头节点的双链表L
while(p!=NULL){ //扫描L的数据节点
q=p->next; //用q保存其后继节点
p->next=L->next; //采用头插法将*p节点插入
if(L->next!=NULL) //修改其前驱指针
L-<next->prior=p;
L->next=p;
p->prior=L;
}
}
设计判断带头节点的循环双链表L（含两个以上的节点）是否对称相等的算法。
解：
int Equal(DLinkList *L){
int same = 1;
DLinkList *p=L->next; //p指向第一个数据节点
DLinkList *q=L->prior; //q指向最后数据节点
while(same==1){
if(p->data!=q->data)
same=0;
else{
if(p==q || p==p->prior) break;
q=q->prior; //q前移
p=p->next; //p后移
}
}
return same;
}
假设有两个有序表LA和LB。设计一个算法，将它们合并陈一个有序表LC。（归并算法）
//本算法的时间复杂度为O(m+n)，空间复杂度为O(m+n)
//采用顺序表存放有序表
void UnionList(SqList *LA,SqList *LB,SqlList *&LC){
int i=0,j=0,k=0; //i、j分别为LA、LB的下标，k为LC中元素个数
LC=(SqList *)malloc(sizeof(SqList)); //建立有序顺序表LC
while(i<LA->length && j<LB->length){
if(LA->data[i] < LB->data[j])
LC->data[k++] = LA->data[i++];
else LC->data[k++] = LB->data[j++];
}
while(i<LA->length)
LC->data[k++] = LA->data[i++];
while(j<LB->length){
LC->data[k++] = LB->data[j++];
}
LC->length = k;
}
一个长度为L的升序序列S，处在L/2向上取整的位置的数成为S的中位数。找出两个等长序列的所有元素的中位数。
解：首先可以采用归并算法，将两个序列合并，然后去中位数即可。
因为只需要找n/2，所以可以定义两个下标分别指向两个数组，要来比较。
//算法的时间复杂度为O(n)，空间复杂度为O(1)
//n是等长序列的长度
int M_Search(int A[],int B[],int n){
int i,j,k;
i=j=k=0;
while(i<n && j<n){
k++;
if(A[i]<B[j]){
if(k==n) return A[i];
i++;
}else{
if(k==n) return B[j];
j++;
}
}
}
假设一个有序表采用顺序表存储，设计一个高效算法删除重复的元素。
void deldupnode1(SqList *&L){
int k=1,i=0;
while(i<L->length-1){
if(L->data[i]!=L->data[i+1])
L->data[k++] = L->data[i++];
}
L->length=k;
}
创建类模式描述如何创建对象，行为类模式关注如何管理对象的行为，结构类模式则着重于如何建立一个软件结构。
桥梁模式关注的是抽象和实现的分离。
策略模式是使用继承和多态建立一套可以自由切换算法的模式，桥梁模式是在不破坏封装的前提下解决抽象和实现都可以独立扩展的模式。
桥梁模式必然有两个“桥墩”——抽象化角色和实现化角色，而策略模式只有一个抽象角色，可以没有实现，也可以有很多实现。
//邮件模板
public abstract class MailTemplate{
//邮件发送人
private String from;
//收件人
private String to;
//邮件标题
private String subject;
//邮件内容
public String context;
//JavaBean规范...
//允许增加邮件发送标志
public void add(String sendInfo){
context = sendInfo + context;
}
}
//文本文件
public class TextMail extends MailTemplate {
public TextMail(String from,String to,String subject,String context){
super(from,to,subject,context);
}
public String getContext() {
//文本类型设置邮件的格式为：text/plain
String context = "\nContent-Type:text/plain;charset=GB2312\n"+super.getContext();
//同时对邮件进行base64编码处理，这里用一句话代替
context = context + "\n邮件格式为：文本格式";
return context;
}
}
//超文本文件
class HtmlMail extends MailTemplate {
public HtmlMail(String from,String to,String subject,String context){
super(from,to,subject,context);
}
public String getContext() {
//文本类型设置邮件的格式为：text/plain
String context = "\nContent-Type:multipart/mixed;charset=GB2312\n"+super.getContext();
//同时对邮件进行base64编码处理，这里用一句话代替
context = context + "\n邮件格式为：超文本格式";
return context;
}
}
//邮件服务器
abstract class MailServer{
//发送的是哪封邮件
protected final MailTemplate m;
public MailServer(MailTemplate m) {
this.m = m;
}
//发送文件
public void sendMail() {
//发件人
System.out.println("发件人:"+m.getFrom());
//收件人
System.out.println("收件人:"+m.getTo());
//标题
System.out.println("标题:"+m.getSubject());
//邮件内容
System.out.println("邮件内容:"+m.getContext());
}
}
//Postfix邮件服务器
class Postfix extends MailServer{
public Postfix(MailTemplate m) {
super(m);
}
//修改邮件发送程序
public void sendMail() {
//增加邮件服务器信息DBCD
String context = "Received:from xxx (unknown [xxx.xxx.xxx.xxx]) "
+ "by aaa.aaa.com (Postfix) with ESMTP id 8DBCD172B8\n";
super.m.add(context);
super.sendMail();
}
}
//SendMail邮件服务器
class SendMail extends MailServer{
public SendMail(MailTemplate m) {
super(m);
}
//修改邮件发送程序
public void sendMail() {
//增加邮件服务器信息DBCD
String context = "Received:(sendmail);7 Nov 2009 04:14:44 +0100\n";
super.m.add(context);
super.sendMail();
}
}
//场景类
public class Client {
public static void main(String[] args) {
//创建一封TEXT格式的邮件
MailTemplate m = new HtmlMail("a@a.com", "b@b.com", "外星人攻击地球了！", "结局是外星人被地球人打败了！");
//创建一个Mail发送程序
MailServer mail = new Postfix(m);
//发送邮件
mail.sendMail();
}
}
门面模式为复杂的子系统提供一个统一的访问界面，它定义的是一个高层接口，该接口使得子系统更加容易使用，避免外部模块深入到子系统内部而产生与子系统内细节耦合的问题。
中介者模式使用一个中介对象来封装一系列同事对象的交互行为，它使各对象之间不再显示地引用，从而使其耦合松散，建立一个可扩展的应用框架。
//抽象同事类
abstract class AbsColleague{
//每个同事类都对中介者非常了解
protected AbsMediator mediator;
public AbsColleague(AbsMediator mediator) {
this.mediator = mediator;
}
}
//职位接口
interface IPosition{
//升职
public void promote();
//降职
public void demote();
}
//职位
class Position extends AbsColleague implements IPosition{
public Position(AbsMediator mediator) {
super(mediator);
}
public void promote() {
super.mediator.down(this);
}
public void demote() {
super.mediator.up(this);
}
}
//工资接口
interface ISalary{
//加薪
public void increaseSalary();
//降薪
public void decreaseSalary();
}
//工资
class Salary extends AbsColleague implements ISalary{
public Salary(AbsMediator mediator) {
super(mediator);
}
public void increaseSalary() {
super.mediator.down(this);
}
public void decreaseSalary() {
super.mediator.up(this);
}
}
//税收接口
interface ITax{
//税收上升
public void raise();
//税收下降
public void drop();
}
//税收
class Tax extends AbsColleague implements ITax{
//注入中介者
public Tax(AbsMediator mediator) {
super(mediator);
}
public void drop() {
super.mediator.down(this);
}
public void raise() {
super.mediator.up(this);
}
}
//抽象中介者
abstract class AbsMediator{
//工资
protected final ISalary salary;
//职位
protected final IPosition position;
//税收
protected final ITax tax;
public AbsMediator() {
salary = new Salary(this);
position = new Position(this);
tax = new Tax(this);
}
//工资增加了
public abstract void up(ISalary salary);
//职位提升了
public abstract void up(IPosition position);
//税收提升了
public abstract void up(ITax Tax);
//工资降低了
public abstract void down(ISalary salary);
//职位降低了
public abstract void down(IPosition position);
//税收降低了
public abstract void down(ITax tax);
}
//中介者
class Mediator extends AbsMediator{
//工资增加了
public void up(ISalary salary) {
upSalary();
upTax();
}
//职位提升了
public void up(IPosition position) {
upPosition();
upSalary();
upTax();
}
//税收增加了
public void up(ITax Tax) {
upTax();
downSalary();
}
//以下同理
public void down(ISalary salary) {}
public void down(IPosition position) {}
public void down(ITax tax) {}
private void upSalary() {}
private void upTax() {}
private void upPosition() {}
private void downSalary() {}
private void downTax() {}
private void downPosition() {}
}
//考勤情况
class Attendance{
//得到出勤天数
public int getWorkDays() {
return (new Random()).nextInt(30);
}
}
//奖金计算
class Bonus{
//考勤情况
private Attendance atte = new Attendance();
//奖金
public int getBonus() {
//获得出勤情况
int workDays = atte.getWorkDays();
//奖金计数器
int bonus = workDays * 1800 /30;
return bonus;
}
}
//基本工资
class BasicSalary{
//获得一个人的基本工资
public int getBasicSalary() {
return 2000;
}
}
//绩效
class Performance{
//基本工资
private BasicSalary salary = new BasicSalary();
//绩效奖励
public int getPerformanceValue() {
//随机绩效
int perf = (new Random()).nextInt(100);
return salary.getBasicSalary() * perf /100;
}
}
//税收
class Tax{
//获取多少税金
public int getTax() {
//交纳一个随机数量的税金
return (new Random()).nextInt(300);
}
}
//总资金计算
class SalaryProvider{
//基本工资
private BasicSalary basicSalary = new BasicSalary();
//奖金
private Bonus bonus = new Bonus();
//绩效
private Performance perf = new Performance();
//税收
private Tax tax = new Tax();
//获得用户的总收入
public int totalSalary() {
return basicSalary.getBasicSalary()+bonus.getBonus()+perf.getPerformanceValue()-tax.getTax();
}
}
//HR门面
class HRFacade{
//总工资情况
private SalaryProvider salaryProvider = new SalaryProvider();
//考勤情况
private Attendance attendance = new Attendance();
//查询一个人的总收入
public int querySalary(String name,Date date) {
return salaryProvider.totalSalary();
}
//查询一个员工一个月工作了多少天
public int queryWorkDays(String name) {
return attendance.getWorkDays();
}
}
//场景类
public class Client {
public static void main(String[] args) {
//定义门面
HRFacade facade = new HRFacade();
int salary = facade.querySalary("张三", new Date(System.currentTimeMillis()));
System.out.println("张三 11月 总收入为："+salary);
//再查询出勤天数
int workDays = facade.queryWorkDays("李四");
System.out.println("李四 本月出勤："+workDays);
}
}
行为类模式包括责任链模式、命令模式、解释器模式、迭代器模式、中介者模式、备忘录模式、观察者模式、状态模式、策略模式、模板方法模式、访问者模式。
策略模式的意图是封装算法，它认为“算法”已经是一个完整的、不可拆分的原子业务，即其意图是让这些算法独立，并且可以相互替换，让行为的变化独立于拥有行为的客户。
命令模式则是对动作的解耦，把一个动作的执行分为执行独享（接受者角色）、执行行为（命令角色），让两者互相独立而不相互影响。
关注点不同
策略模式关注的是算法替换的问题，一个新的算法投产，旧算法退休，或者提供多种算法由调用者自己选择使用，算法的自由更替是它实现的要点，关注的是算法的完整性。封装性。
命令模式关注的是解耦问题，如何让请求者和执行者解耦是它需要首先解决的，解耦的要求就是把请求的内容封装为一个一个的命令，由接受者执行。由于封装成了命令，就同时可以对命令进行多种处理，例如撤销、记录等。
角色功能不同
策略模式中的具体算法是负责一个完整算法逻辑，它是不可再拆分的院子业务单元，一旦变更就是对算法整体的变更。
命令模式关注命令的实现，也就是功能的实现，接收者的影响范围仅仅是抽象命令和具体命令，对它的修改不会扩散到模式外的模块。
使用场景不同
策略模式适用于算法要求变幻的场景，而命令模式适用于解耦两个有紧耦合关系的对象场合或者多命令多撤销的场景。
//抽象压缩算法
public interface Algorithm {
//压缩算法
public boolean compress(String source,String to);
//解压缩算法
public boolean uncompress(String source,String to);
}
//zip压缩算法
public class Zip implements Algorithm {
//zip格式的压缩算法
public boolean compress(String source,String to) {
System.out.println(source+"-->"+to+" ZIP压缩成功！");
return true;
}
//zip格式的解压缩算法
public boolean uncompress(String source,String to) {
System.out.println(source+"-->"+to+" ZIP解压缩成功！");
return true;
}
}
//gzip压缩算法
public class Gzip implements Algorithm {
//gzip格式的压缩算法
public boolean compress(String source,String to) {
System.out.println(source+"-->"+to+" GZIP压缩成功！");
return true;
}
//gzip格式的解压缩算法
public boolean uncompress(String source,String to) {
System.out.println(source+"-->"+to+" GZIP解压缩成功！");
return true;
}
}
//环境角色
public class Context {
//指向抽象算法
private Algorithm al;
//构造函数传递具体的算法
public Context(Algorithm al){ this.al = al;}
//执行压缩算法
public boolean compress(String source,String to) {
return al.compress(source,to);
}
//执行解压缩算法
public boolean uncompress(String source,String to) {
return al.uncompress(source,to);
}
}
//场景类
public class Client{
public static vod main(String[] args) {
//定义环境角色
Context context;
//对文件执行zip压缩算法
context = new Context(new Zip());
context.compress("c:\\windows","d:\\window.zip");
context.uncompress("c:\\windows.zip","d:\\windows");
}
}
//抽象压缩命令
public abstract class AbstractCmd {
//对接受者的引用
protected IReceiver zip = new ZipReceiver();
protected IReceiver gzip = new GzipReceiver();
//抽象方法，命令的具体单元
public abstract boolean execute(String source,String to);
}
//zip压缩命令
public class ZipCompressCmd extends AbstractCmd {
public boolean execute(String source,String to) {
return super.zip.compress(source,to);
}
}
//zip解压缩命令
public class ZipUnCompressCmd extends AbstractCmd {
public boolean execute(String source,String to) {
return super.zip.uncompress(source,to);
}
}
//gzip压缩命令
public class GzipCompressCmd extends AbstractCmd {
public boolean execute(String source,String to) {
return super.gzip.compress(source,to);
}
}
//gzip解压缩命令
public class GzipUnCompressCmd extends AbstractCmd {
public boolean execute(String source,String to) {
return super.gzip.uncompress(source,to);
}
}
//抽象接收者
public interface IReceiver {
//压缩
public boolean compress(String source,String to);
//解压缩
public boolean uncompress(String source,String to);
}
//zip接收者
public class ZipReceiver implements IReceiver {
public boolean compress(String source,String to){
System.out.println(source+"-->"+to+" ZIP压缩成功！");
return true;
}
public boolean uncompress(String source,String to){
System.out.println(source+"-->"+to+" ZIP解压缩成功！");
return true;
}
}
//gzip接收者
public class GzipReceiver implements IReceiver {
public boolean compress(String source,String to){
System.out.println(source+"-->"+to+" GZIP压缩成功！");
return true;
}
public boolean uncompress(String source,String to){
System.out.println(source+"-->"+to+" GZIP解压缩成功！");
return true;
}
}
//调用者
public class Invoker {
//抽象命令的引用
private AbstractCmd cmd;
public Invoker(AbstractCmd cmd){
this.cmd = cmd;
}
//执行命令
public boolean execute(String source,String to){
return cmd.execute(source,to);
}
}
//场景类
public class Client {
public static void main(String[] args) {
//定义一个命令
Abstract cmd = new ZipCompressCmd();
//定义调用者
Invoker invoker = new Invoker(cmd);
invoker.execute("c:\\windows","d:\\windows.zip");
}
}
在行为类设计模式中，状态模式和策略模式是亲兄弟，它们的类图非常相似，都是通过Context类封装一个具体的行为，都提供了一个封装的方法，是高扩展性的设计模式。区别：
策略模式封装的是不同的算法，算法之间没有交互，以达到算法可以切换的目的。
状态模式封装的是不同的状态，以达到状态切换行为随之发生改变的目的。
环境角色的职责不同
策略模式的环境角色只是一个委托作用，负责算法的替换。
状态模式的环境角色不仅仅是委托行为，它还具有登记状态变化的功能，与具体的状态类协作，共同完成随之切换的任务。
解决问题的重点不同
策略模式旨在解决内部算法如何改变的问题，也就是将内部算法的改变对外界的影响降低到最小，它保证的是算法可以自由的切换。
状态模式旨在解决内在状态的改变而引起行为改变的问题，它的出发点是事物的状态，封装状态而暴露行为。
解决问题的方法不同
策略模式只是确保算法可以自由切换，但是什么时候用什么算法它决定不了。
状态模式对外暴露的是行为，状态的变化一般是由环境角色和具体状态共同完成的，也就是说状态模式封装了状态的变化而暴露了不同的行为和行为结果。
应用场景不同
策略模式是一系列平行的、可相互替换的算法封装后的结果
状态模式要求有一系列状态发生变化的场景，它要求的是有状态且有行为的场景。
复杂度不同
策略模式结构比较简单，扩展比较容易，代码也容易阅读。
状态模式比较复杂，因为它要从连个角色看到一个对象状态和行为的改变。
//人的抽象状态
public abstract class HumanState {
//指向一个具体的人
protected Human human;
//设置一个具体的人
public void setHuman(Human human){
this.human = human;
}
//不管人是什么状态都要工作
public abstract void work();
}
//孩童状态
public class ChildState extends HumanState{
public void work(){
System.out.println("玩耍");
super.human.setState(Human.ADULT_STATE);
}
}
//成年人状态
public class AdultState extends HumanState{
public void work(){
System.out.println("养活全家");
super.human.setState(Human.OLD_STATE);
}
}
//孩童状态
public class OldState extends HumanState{
public void work(){
System.out.println("享乐");
}
}
//环境角色
public class Human{
//定义人类都有哪些状态
public static final HumanState CHILD_STATE = new ChildState();
public static final HumanState ADULT_STATE = new ADULTState();
public static final HumanState OLD_STATE = new OLDState();
//定义一个人的状态
private HumanState state;
//设置一个状态
pubilc void setState(HumanState state){
this.state = state;
this.state.setHuman(this);
}
//人类的工作
public void work(){
this.state.work();
}
}
//场景类
public class Client{
public static void mian(String[] args{
//定义一个普通的人
Human human = new Human);
//设置一个人的初始状态
human.setState(new ChiledState());
//儿童状态，之后转到成人状态，在转到老人状态
human.work();
human.work();
human.work();
}
}
链中的消息对象不同
责任链模式基本上不改变消息对象的结构，比如从首节点传进来一个String对象或者Person对象，不会到链尾的时候变成int对象或者Human对象。
触发链模式中传递的对象可以自由变化，只要上下级节点对传递对象了解即可，不要求链中的消息对象不变化，它只要求链中相邻两个节点的消息对象固定。
上下节点的关系不同
在责任链模式中，上下节点没有关系，都是接收同样的对象，所有传递的对象都是从链首传递过来，上一节点是什么没有关系，只要按照自己的逻辑处理就行。
在触发链模式中，它的上下级关系很亲密，下级对上机顶礼膜拜，上级对下级绝对信任，链中的任意两个相邻节点都是一个固定的独立团体。
消息的分销渠道不同
在责任链模式中，一个消息从链首传递进来后，就开始沿着链条向链尾运动，方向是单一的、固定的。
触发链模式，因为采用的是观察者模式，所以有很大的灵活性，一个消息传递到链首后，具体怎么传递是不固定的，可以以广播方式传递，也可以以跳跃方式传递，这取决于处理消息的逻辑。
DNS协议，将域名翻译成IP地址，每个区域的DNS服务器只保留自己区域的域名解析，对于不能解析的域名，则提交上级域名解析器解析，最终由一台位于美国洛杉矶的顶级域名服务器进行解析，返回结果。
请求者 –> 区域DNS –> 中国顶级DNS –> 全球顶级DNS
责任链模式，谁解析，便由谁返回给请求者结果。
触发链模式，谁解析，便返回给上一级，最终由第一个DNS返回给请求者结果。
所有的解析结果都是由上海服务器返回的，这才是真正的DNS解析过程。
//解析记录
public class Recorder {
//域名
private String domain;
//IP地址
pirvate String ip;
//属主
private String owner;
//javabean规范...
}
//抽象域名服务器
public abstract class DnsServer{
//上级DNS是谁
private DnsServer upperServer;
//解析域名
public final Recorder resolve(String domain){
Recoder recoder = null;
if(isLocal(domain)){//是本服务器能解析的域名
recorder = echo(domain);
}else{//本服务器不能解析
//提交上级DNS进行解析
recoder = upperServer.resolve(domain);
}
return recorder;
}
//指向上级DNS
public void setUpperServer(DnsServer upperServer){
this.upperServer = upperServer;
}
//每个DNS都有一个数据处理区（ZONE），检查域名是否在本区中
protected abstract boolean isLocal(String domain);
//每个DNS服务器都必须实现解析任务
portected Recorder echo(String domain){
Recorder recorder = new Recorder();
//获得IP地址
recorder.setIp(getIpAddress());
recorder.setDomain(domain);
return recorder;
}
//随机产生一个IP地址，工具类
private String getIpAddress(){
Random rand = new Random();
String address = rand.nextInt(255)+"."+rand.nextInt(255)+"."+rand.nextnt(255)+"."+rand.nextnt(255);
return address;
}
}
//上海DNS服务器
public class SHDnsServer extends DnsServer{
public Recorder echo(String domain){
Recorder recorder = super.echo(domain);
recorder.setOwner("上海DNS服务器");
return recorder;
}
//定义上海的DNS服务器能处理的级别
protected boolean isLocal(String domain){
return domain.endsWith(".sh.cn");
}
}
//中国顶级DNS服务器
public class ChinaTopDnsServer extends DnsServer{
public Recorder echo(String domain){
Recorder recorder = super.echo(domain);
recorder.setOwner("中国顶级DNS服务器");
return recorder;
}
protected boolean isLocal(String domain){
return domain.endsWith(".cn");
}
}
//全球顶级DNS服务器
public class TopDnsServer extends DnsServer{
public Recorder echo(String domain){
Recorder recorder = super.echo(domain);
recorder.setOwner("全球顶级DNS服务器");
return recorder;
}
protected boolean isLocal(String domain){
//所有的域名最终的解析地点
return true;
}
}
//场景类
public class Client{
public static void main(String[] args){
//上海域名服务器
DnsServer sh = new SHDnsServer();
//中国顶级域名服务器
DnsServer china = new ChinaTopDnsServer();
//全球顶级域名服务器
DnsServer top = new TopDnsServer();
//定义查询路径
china.setUpperServer(top);
sh.setUpperServer(china);
//解析域名
while(true){
System.out.println("域名解析模拟器(输入N退出):");
String domain = (new BufferedReader(new InputStreamReader(System.in))).readLine();
if(domain.equalsIgnoreCase("n")){
return ;
}
Recorder recorder = sh.resolve(domain);
System.out.println(recorder);
}
}
}
//抽象域名服务器
public abstract class DnsServer extends Observable implements Observer{
//处理请求，也是接受到事件后的处理
public void update(Observable arg0,Object arg1){
Recorder recorder = (Recorder)arg1;
//如果本机能解析
if(isLocal(recorder)){
recorder.setIp(getIpAddress());
}else{//本机不能解析，则提交到上级DNS
responseFromUpperServer(recorder);
}
//签名
sign(recorder);
}
//作为被观察者，允许增加观察者，这里上级DNS一般只有一个
public void setUpperServer(DnsServer dnsServer){
//先清空，然后在增加
super.deleteObservers();
super.addObserver(dnsServer);
}
//向父DNS请求解析，也就是通知观察者
private void responseFromUpperServer(Recorder){
super.setChanged();
super.notifyObservers(recorder);
}
//每个DNS服务器签上自己的名字
protected abstract void sign(Recorder recorder);
//每个DNS服务器都必须定义自己的处理级别
protected abstract boolean isLocal(Recorder recorder);
//随机产生一个IP地址，工具类
private String getIpAddress(){
Random rand = new Random();
String address = rand.nextInt(255)+"."+rand.nextInt(255)+"."+rand.nextnt(255)+"."+rand.nextnt(255);
return address;
}
}
//上海DNS服务器
public class SHDnsServer extends DnsServer{
public void sign(Recorder recorder){
recorder.setOwner("上海DNS服务器");
}
//定义上海的DNS服务器能处理的级别
protected boolean isLocal(Recorder recorder){
return recorder.getDomain().endsWith(".sh.cn");
}
}
//中国顶级DNS服务器
public class ChinaTopDnsServer extends DnsServer{
public void sign(Recorder recorder){
recorder.setOwner("中国顶级DNS服务器");
}
//定义上海的DNS服务器能处理的级别
protected boolean isLocal(Recorder recorder){
return recorder.getDomain().endsWith(".cn");
}
}
//全球顶级DNS服务器
public class TopDnsServer extends DnsServer{
public void sign(Recorder recorder){
recorder.setOwner("全球顶级DNS服务器");
}
//定义上海的DNS服务器能处理的级别
protected boolean isLocal(Recorder recorder){
//所有域名最终的解析地点
return true;
}
}
//场景类
public class Client{
public static void main(String[] args){
//上海域名服务器
DnsServer sh = new SHDnsServer();
//中国顶级域名服务器
DnsServer china = new ChinaTopDnsServer();
//全球顶级域名服务器
DnsServer top = new TopDnsServer();
//定义查询路径
china.setUpperServer(top);
sh.setUpperServer(china);
//解析域名
while(true){
System.out.println("域名解析模拟器(输入N退出):");
String domain = (new BufferedReader(new InputStreamReader(System.in))).readLine();
if(domain.equalsIgnoreCase("n")){
return ;
}
Recorder recorder = new Recorder();//虚拟了观察者触发动作
recorder.setDomain(domain);
sh.update(null,recorder);
System.out.println(recorder);
}
}
}
结构类模式包括适配器模式、桥梁模式、组合模式、装饰模式、门面模式、享元模式和代理模式。
为什么叫结构类模式呢？因为他们都是通过组合类或对象产生更大结构以适应更高层次的逻辑需求。
装饰模式就是代理模式的一个特殊应用，两者的共同点是都具有相同的接口，不同点则是代理模式着重对代理过程的控制，而装饰模式则是对类的功能进行加强或减弱，它着重类的功能变化。
//抽象运动员
public interface IRunner {
public void run();
}
//运动员跑步
public class Runner implements IRunner {
public void run(){
System.out.println("运动员跑步：动作很潇洒");
}
}
//代理模式：代理人
public class RunnerAgent implements IRunner {
private IRunner runner;
public RunnerAgent(IRunner runner) {
this.runner = runner;
}
//代理人控制被代理人行为
public void fun() {
Random rand = new Random();
if(rand.nextBoolean()) {
System.out.println("代理人同意安排运动员跑步");
runner.run();
}else {
System.out.println("代理人心情不好，不安排运动员跑步");
}
}
}
//场景类
public class Client {
public static void main(String[] args) {
IRunner liu = new Runner();
IRunner agent = new RunnerAgent(liu);
agent.run();
}
}
//装饰模式:装饰类
public class RunnerWithJet implements IRunner {
private IRunner runner;
public RunnerWithJet(IRunner runner) {
this.runner = runner;
}
public void run() {
System.out.println("加快运动员的速度：为运动员增加喷气装置");
runner.run
}
}
//场景类
public class Client {
public static void main(String[] args) {
IRunner liu = new Runner();
liu = new RunnerWithJet(liu);
liu.run();
}
}
代理模式是把当前的行为或功能委托给其他对象执行，代理类负责恩接口限定：是否可以调用真是角色，以及是否对发送到真是角色的消息进行变形处理，它不被主题角色的功能做任何处理，保证原滋原味的调用。代理模式使用到极致开发就是AOP，这是采用Spring架构开发必然要使用到的技术。
装饰模式是在要保证接口不变的情况下加强类的功能，它保证的是被修饰的对象功能比原始对象丰富（或减弱），但不做准入条件判断和准入参数过滤，如是否可以在执行类的功能，过滤输入参数是否合规等，这不是装饰模式关心的。
装饰模式和适配器模式在通用类图上没有太多的相似点，但是它们的功能有相似的地方：都是包装作用，都是通过委托方式实现其功能。
不同点是：装饰模式包装的是自己的兄弟类，隶属于同一个家族，适配器模式则修饰非血缘关系类，把一个非本家族的对象伪装成本家族的对象，它的本质还是非相同接口的对象，但是可用相同抽象类或接口声明引用。
意图不同
装饰模式的意图是加强对象的功能，不改变类的属性和行为。
适配器模式关注的则是两个不同对象之间的转化。
施与对象不同
装饰模式装饰的对象必须是自己的同宗，也就是相同的接口或父类。
适配器模式则必须是两个不同的对象，因为它着重于转换。
场景不同
装饰模式在任何时候都可以使用，只要是向增强类的功能。
适配器模式则是一个补救模式，一般出现在系统成熟或已经构建完毕的项目中，作为一个紧急处理手段使用。
扩展性不同
装饰模式很容易扩展，并且可以继续扩展下去。
适配器模式在两个不同对象之间架起一座沟通的桥梁，建立容易，去掉就比较困难了，需要从新系统整体考虑是否能够撤销。
####适配器实现替身演员
//明星接口
interface IStar{
//明星都要演戏
public void act(String context);
}
//电影明星
class FilmStar implements IStar{
public void act(String context){
System.out.println("明星演戏："+context);
}
}
//普通演员接口
interface IActor{
//普通演员演戏
public void playact(String context);
}
//普通演员
class UnknownActor implements IActor{
public void playact(String context){
System.out.println("普通演员："+context);
}
}
//替身演员
class Standin implements IStar{
private IActor actor;
//替身是谁
public Standin(IActor actor){
this.actor = actor;
}
public void act(String context){
actor.playact(context);
}
}
//导演类
public class direcotr{
publoc staticvoid mian(String[] args){
//定义一个大明星
IStar star= new FilmStar();
star.act("前十五分钟，明星本人在演戏");
//导演把一个普通演员当做明星演员来用
IActor actor = new UnknownActor();
IStar standin = new Standin(actor);
standin.act("中间五分钟，替身在演戏");
star.act("后十五分钟，明星本人演戏");
}
}