数据结构常用算法数据结构算法

数据结构常用算法集合

voidUnion(List&La,ListLb){//算法2.1

//将全部在线性表Lb中但不在La中的数据元素插入到La中

intLa_len,Lb_len,i；

ElemTypee;

La_len=ListLength(La);//求线性表的长度

Lb_len=ListLength(Lb);

for(i=l;i<=Lb_len;i++){

GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e

if(!LocateElem(La,e,equal))//La中不存在和e相同的数据元素

ListInsert(La,++La」en,e);//插入

)

}//union

voidMergeList(ListLa,ListLb,List&Lc){//算法2.2

//已知线性表La和Lb中的元素按值非递减排列。

//归并La和Lb得到新的线性表Lc,Lc的元素也按值非递减排列。

intLa_len,Lb_len;

ElemTypeai,bj;

inti=l,j=l,k=O;

InitList(Lc);

La_len=ListLength(La);

Lbjen=ListLength(Lb);

while((i<=La_len)&&(j<=Lb_len)){//La和Lb均非空

GetElem(La,i,ai);

GetElem(Lb,j,bj);

if(ai<=bj){

ListInsert(Lc,++k,ai);

++i；

}else{

ListInsert(Lc,++k,bj);

++j；

)

)

while(i<=La_len){

GetElem(La,i++,ai);ListInsert(Lc,++k,ai);

}

while(j<=Lb_len){

GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);

}//MergeList

StatusInitList_Sq(SqList&L){//算法2.3

//构造一个空的线性表L。

L.elem=(ElemType*)manoc(LIST_INIT_SIZE*sizeof(ElemType));

if(JL.elem)returnOK;//存储安排失败

L.length=0;//空表长度为0

L.listsize=LISTJNIT_SIZE;//初始存储容量

returnOK;

}//InitList_Sq

StatusListInsert_Sq(SqList&L,inti,ElemTypee){//算法2.4

//在挨次线性表L的第i个元素之前插入新的元素e,

〃i的合法值为lWiWListLength_Sq(L)+l

ElemType*p;

if(i<1||i>L.length+1)returnERROR;//i值不合法

if(L.length>=L.listsize){//当前存储空间已满，增加容量

ElemType*newbase=(ElemType*)realloc(L.elem,

(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)returnERROR;//存储安排失败

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增力口存储容量

)

ElemType*q=&(L.elem[i-l]);//q为插入位置

for(p=&(L.elem[L.length-1]);p>=q;—p)*(p+l)=*p;

//插入位置及之后的元素右移

*q=e;//插入e

++L.length;//表长增1

returnOK;

}//ListInsert_Sq

StatusListDelete_Sq(SqList&L,inti,ElemType&e){//算法2.5

//在挨次线性表L中删除第i个元素，并用e返回其值。

〃i的合法值为lWiWLislLength_Sq(L)。

ElemType*p,*q;

if(i<l||i>L.length)returnERROR;//i值不合法

p=&(L.elem[i-l]);//p为被删除元素的位置

e=*p;//被删除元素的值赋给e

q=L.elem+L.length-l;//表尾元素的位置

for(++p;p<=q;++p)*(p-l)=*p;//被删除元素之后的元素左移

—L.length;//表长减1

returnOK;

}//ListDelete_Sq

intLocateElem_Sq(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){//算法2.6

//在挨次线性表L中查找第1个值与e满意compare。的元素的位序。

〃若找到，则返回其在L中的位序，否则返回0。

inti;

ElemType*p;

i=l；//i的初值为第1个元素的位序

p=L.elem;//p的初值为第1个元素的存储位置

while(i<=L.length&&!(*compare)(*p++,e))

++i；

if(i<=L.length)returni;

elsereturn0;

)//LocateElem_Sq

voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){//算法2.7

//已知挨次线性表La和Lb的元素按值非递减排列。

//归并La和Lb得到新的挨次线性表Lc,Lc的元素也按值非递减排列。

ElemType*pa,*pb,*pc,*pa_last,*pb_last;

pa=La.elem;pb=Lb.elem;

Lc.listsize=Lc.length=La.length+Lb.length;

pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));

if(ILc.elem)

exit(OVERFLOW);//存储安排失败

pa_last=La.elem+La.length-1;

pb_last=Lb.elem+Lb.length-1;

while(pa<=pa_last&&pb<=pb_last){〃归并

if(*pa<=*pb)*pc++=*pa++;

else*pc++=*pb++;

)

while(pa<=pa_lasl)*pc++=*pa++;//插入La的剩余元素

while(pb<=pb」ast)*pc++=*pb++;//插入Lb的剩余元素

)//MergeList

StatusGetElem_L(LinkList&L,inti,ElemType&e){//算法2.8

//L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK,否则返回ERROR

LinkListp;

p=L->next;intj=1;//初始化，p指向第一个结点，j为计数器

while(p&&j<i){〃顺指针向后查找，直到p指向第i个元素或p为空

p=p->next;

}

if(!p||j>i)returnERROR;//第i个元素不存在

e=p->data;//取第i个元素

returnOK;)//GetElem_L

StatusListInsert_L(LinkList&L,inti,ElemTypee){//算法2.9

//在带头结点的单链线性表L的第i个元素之前插入元素e

LinkListp,s;

P=L;

intj=0;

while(p&&j<i-1){//查找第i-1个结点

p=p->next;

++j；

)

if(!p||j>i-l)returnERROR;//i小于1或者大于表长

s=(LinkList)malloc(sizeof(LNode));//生成新结点

s->data=e;s->next=p->next;//插入L中

p->next=s;

returnOK;

}//LinstInsert_L

StatusListDelete_L(LinkList&L,inti,ElemType&e){//算法2.10

〃在带头结点的单链线性表L中，删除第i个元素，并由e返回其值

LinkListp,q;

p=L;intj=0;

while(p->next&&j<i-1){〃查找第i个结点，并令p指向其前趋

p=p->next;++j；

)

if(!(p->next)||j>i-1)returnERROR;//删除位置不合理

q=p->next;

p->next=q->next;//删除并释放结点

e=q->data;

free(q);

returnOK;

}//ListDelete_L

voidCreateList_L(LinkList&L,intn){//算法2.11

//逆位序输入(随机产生)n个元素的值，建立带表头结点的单链线性表L

LinkListp;

inti;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;//先建立一个带头结点的单链表

for(i=n;i>0;-i){

p=(LinkList)malloc(sizeof(LNode));//生成新结点

p->data=random(200);//改为一个随机生成的数字(200以内)

p->next=L->next;L->next=p;//插入到表头

)

}//CreateList_L

voidMergeList_L(LinkList&La,LinkList&Lb.LinkList&Lc){

//算法2.12

//已知单链线性表La和Lb的元素按值非递减排列。

//归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列。

LinkListpa,pb,pc;

pa=La->next;pb=Lb->next;

Lc=pc=La;//用La的头结点作为Lc的头结点

while(pa&&pb){

if(pa->data<=pb->data){

pc->next=pa;pc=pa;pa=pa->next;

)

else{pc->next=pb;pc=pb;pb=pb->next;}

I

pc->next=pa?pa:pb;//插入剩余段

free(Lb);//释放Lb的头结点

}//MergeList_L

intLocateElem_SL(SLinkListS,ElemTypee){//算法2.13

//在静态单链线性表L中查找第1个值为e的元素。

〃若找到，则返回它在L中的位序，否则返回0。

inti;

i=S[0].cur;//i指示表中第一个结点

while(i&&S[i].data!=e)i=S[i].cur;//在表中顺链查找

returni;

}//LocateElem_SL

voidInitSpace_SL(SLinkListspace){//算法2.14

//将一维数组space中各重量链成一个备用链表，space[0].cur为头指针，

//“0"表示空指针

for(inti=0;i<MAXSIZE-l;++i)

space[i].cur=i+1;

space[MAXSIZE-1].cur=0;

}//InitSpace_SL

intMalloc_SL(SLinkList&space){//算法2.15

〃若备用空间链表非空，则返回安排的结点下标，否则返回0

inti=space[0].cur;

if(space[0].cur)space[0].cur=space[space[O].cur].cur;

returni;

}//Malloc_SL

voidFree_SL(SLinkList&space,intk){//算法2.16

//将下标为k的空闲结点回收到备用链表

space[k].cur=space[0].cur;space[0].cur=k;

}//Free_SL

voiddifference(SLinkList&space,int&S){//算法2.17

//依次输入集合A和B的元素，在一维数组space中建立表示集合(A-B)U(B-A)

//的静态链表,S为头指针。假设施用空间足够大，space⑼.cur为头指针。

inti,j,k,m,n,p,r;

ElemTypeb;

InitSpace_SL(space);//初始化备用空间

S=Malloc_SL(space);//生成S的头结点

r=S;〃r指向S的当前最终结点

m=random(2,8);//输入A的元素个数

n=random(2,8);//输入B的元素个数

printf(uA=(M);

initrandom_cl();

for(j=l;j<=m;++j){//建立集合A的链表

i=Malloc_SL(space);//安排结点

//printf(ui=%dn,i);

space[i].data=random_next_c1();〃输入A的元素值

printf(n%cn,space[i].data);〃输出A的元素

space[r].cur=i;r=i;//插入到表尾

printf(u)\n");

space[r].cur=0;//尾结点的指针为空

initrandom_cl();

printf(uB=(")；

for(j=l;j<=n;++j){

//依次输入B的元素，若不在当前表中，则插入，否则删除

b=random_next_c1();//输入B的元素值

printf(H%c",b);//输出B的元素

p=S;k=space[S].cur;//k指向集合A中第一个结点

while(k!=space[r].cur&&space[k].data!=b){//在当前表中查找

p=k;k=space[k].cur;

)

if(k==space[r].cur){

//当前表中不存在该元素,插入在r所指结点之后，且r的位置不变

i=Malloc_SL(space);

space[i|.data=b;

space[i].cur=space[r].cur;

space[r].cur=i;

}else{//该元素已在表中,删除之

space[p].cur=space[k].cur;

Free_SL(space,k);

if(r==k)r=p;〃若删除的是尾元素，则需修改尾指针

)

printf(")\n");

}//difference

DuLinkListGetElemP_DuL(DuLinkListva,inti){

//L为带头结点的单链表的头指针。

〃当第i个元素存在时，其值赋给e并返回OK,否则返回ERROR

DuLinkListp;

p=va->next;

intj=1;//初始化，p指向第一个结点，j为计数器

while(p!=va&&j<i){〃顺指针向后查找，直到p指向第i个元素或p为空

p=p->next;

++j；

)

if(p==va&&j<i)returnNULL;//第i个元素不存在

elsereturnp;

)//GetElem_L

StatusListInsert_DuL(DuLinkList&L,inti,ElemTypee){//算法2.18

//在带头结点的双链循环线性表L的第i个元素之前插入元素e,

〃i的合法值为IWiW表长+1。

DuLinkListp,s;

if(!(p=GetElemP_DuL(L,i)))〃在L中确定第i个元素的位置指针p

returnERROR;//p=NULL,即第i个元素不存在

if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))

returnERROR;

s->data=e;

s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;

returnOK;

}//ListInsert_DuL

DuLinkListGetElemP_DuL(DuLinkListva,inti){

//L为带头结点的单链表的头指针。

//当第i个元素存在时，其值赋给e并返回OK,否则返回ERROR

DuLinkListp;

p=va->next;

intj=1;//初始化，p指向第一个结点，j为计数器

while(p!=va&&j<i){//顺指针向后查找，直到p指向第i个元素或p为空

p=p->next;

++j；

)

if(p==va||j<i)returnNULL;//第i个元素不存在

elsereturnp;

}//GetElem_L

StatusListDelete_DuL(DuLinkList&L,inti,ElemType&e){//算法2.19

//删除带头结点的双链循环线性表L的第i个元素，i的合法值为IWiW表长

DuLinkListp;

if(!(p=GetElemP_DuL(L,i)))〃在L中确定第i个元素的位置指针p

returnERROR;//p=NULL,即第i个元素不存在

e=p->data;

p->prior->next=p->next;

p->next->prior=p->prior;

free(p);

returnOK;

}//ListDelete_DuL

StatusListInserl_L(NLinkListL,inti,ElemTypee){//算法2.20

//在带头结点的单链线性表L的第i个元素之前插入元素e

NLinkh,s;

if(!LocatePos(L,i-1,h))

returnERROR;//i值不合法

if(!MakeNode(s,e))

returnERROR;//结点存储安排失败

InsFirst(h,s);//对于从第i结点开头的链表，第i-1结点是它的头结点

returnOK;

}//ListInsert_L

StatusMergeList_L(NLinkList&La,NLinkList&Lb,NLinkList&Lc,

int(*compare)(ElemType,ElemType)){//算法2.21

//已知单链线性表La和Lb的元素按值非递减排列。

//归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列。

NLinkha,hb;

Positionpa,pb,q;

ElemTypea,b;

if(!InitList(Lc))returnERROR;//存储空间安排失败

ha=GetHead(La);//ha和hb分别指向La和Lb的头结点

hb=GetHead(Lb);

pa=NextPos(La,ha);//pa和pb分别指向La和Lb中当前结点

pb=NextPos(Lb,hb);

while(pa&&pb){//La和Lb均非空

a=GetCurElem(pa);//ab为两表中当前比较元素

b=GetCurElem(pb);

if((*compare)(a,b)<=0){〃aWb

DelFirst(ha,q);Append(Lc,q);pa=NextPos(La,pa);

}else{//a>b

DelFirst(hb,q);Append(Lc,q);pb=NextPos(Lb,pb);

)

}//while

if(pa)Append(Lc,pa);//链接La中剩余结点

elseAppend(Lc,pb);//链接Lb中剩余结点

FreeNode(ha);FreeNode(hb);//释放La和Lb的头结点

returnOK;

}//MergeList_L

Statuscmp(PElemTypea,PElemTypeb){

if(a.expn>=b.expn)return1;

elsereturn0;

)

voidCreatPolyn(PLinkList&P,intm){//算法2.22

〃输入m项的系数和指数，建立表示一元多项式的有序链表P

PLinkh,q,s;

PElemTypee;

inti;

InitList(P);h=GetHead(P);

e.coef=0.0;e.expn=-1;

SetCurElem(h,e);//设置头结点

for(i=l;i<=m;++i){//依次输入m个非零项

//scanf("%f,%d\nn,&e,coef,&e.expn);

e.coef=(float)(random(l,90)+random(l0)/10.0);

if(random(2))e.coef=-e.coef;

e.expn=e.expn+random(1,10);,但是expn值是递增的

if(!LocateElem(P,e,q,cmp)){//当前链表中不存在该指数项

if(MakeNode(s,e))InsFirst(q,s);//生成结点并插入链表

if(q==P.tail)P,tail=s;

}elsei-;//假如没有产生插入，则将i值减1

)

}//CreatPolyn

StatusPrintfPoly(PLinkListP){

inti=0;

PLinkq=P.head->next;

while(q){

if(fabs(q->data.coef)>0.005){

if(i>0){

if(q->data.coef>0.005)printf(u+*');

elseprintf(n-");

printf("％.2f",fabs(q->data.coef))；

}elseprintf(n%.2f',q->data.coef)；

if(q->data.expn>=1)printff'x”);

if(q->data.expn>l)printf(,，A%d",q->data.expn);

)

q=q->next;

if(++i%6==0)printf(M\n");

)

printf(u\nu);

returnOK;

)

intCompare(PElemTypea,PElemTypeb){

if(a.expn<b.expn)return-1;

if(a.expn>b.expn)return1;

return0;

)

voidAddPolyn(PLinkList&Pa,PLinkList&Pb){//算法2.23

〃多项式加法：Pa=Pa+Pb,采用两个多项式的结点构成”和多项式”。

PLinkha,hb,qa,qb;

PElemTypea,b,temp;

floatsum;

ha=GetHead(Pa);//ha和hb分别指向Pa和Pb的头结点

hb=GetHead(Pb);

qa=NextPos(Pa,ha);//qa和qb分别指向La和Lb中当前结点

qb=NextPos(Pb,hb);

while(qa&&qb){//Pa和Pb均非空

a=GetCurElem(qa);〃a和b为两表中当前比较元素

b=GetCurElem(qb);

switch(Compared,b)){

case-1:〃多项式PA中当前结点的指数值小

ha=qa;

qa=NextPos(Pa,qa);

break;

case0://两者的指数值相等

sum=a.coef+b.coef;

if(sum!=0.0){〃修改多项式PA中当前结点的系数值

temp.coef=sum;

temp.expn=a.expn;

SetCurElem(qa,temp);

ha=qa;

}else{//删除多项式PA中当前结点

DelFirst(ha,qa);

FreeNode(qa);

DelFirst(hb,qb);

FreeNode(qb);

qb=NexlPos(Pb,hb);

qa=NextPos(Pa,ha);

break;

case1://多项式PB中当前结点的指数值小

DelFirst(hb,qb);

InsFirst(ha,qb);

qb=NextPos(Pb,hb);

ha=NextPos(Pa,ha);

break;

}//switch

}//while

if(!Empty(Pb))Append(Pa,qb);//链接Pb中剩余结点

FreeNode(hb);//释放Pb的头结点

}//AddPolyn

voidconversion(intNum){//算法3.1

//对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数

ElemTypee;

SqStackS;

InitStack(S);//构造空栈

while(Num){

Push(S,Num%8);

Num=Num/8;

)

while(!StackEmpty(S)){

Pop(S,e);

printf("%d",e);

)

printf(n\nH);

}//conversion

voidLineEdit(){//算法3.2

〃采用字符栈S,从终端接收一行并传送至调用过程的数据区。

charch,*temp;

SqStackS;

InitStack(S);〃构造空栈S

printf("请输入一行(#:退格；@:清行):\n")；

ch=getchar();〃从终端接收第一个字符

while(ch!=EOF){//EOF为全文结束符

while(ch!=EOF&&ch!=*\n'){

switch(ch){

case*#,:Pop(S,ch);break;//仅当栈非空时退栈

caseClearStack(S);break;//重置S为空栈

default:Push(S,ch);break;//有效字符进栈，未考虑栈满情形

)

ch=getchar();//从终端接收下一个字符

)

while(temp!=S.top){

printf(M%c,',*temp);

+4-temp;

)

//将从栈底到栈顶的栈内字符传送至调用过程的数据区；

ClearStack(S);//重置S为空栈

printf("\nu);

if(ch!=EOF){

printf("请输入一行(#:退格;@:清行):\n");

ch=getchar();

)

)

DestroyStack(S);

)

StatusPass(MazeTypeMyMaze,PosTypeCurPos);

voidFootPrint(MazeType&MyMaze,PosTypeCurPos);

voidMarkPrint(MazeType&MyMaze,PosTypeCurPos);

PosTypeNextPos(PosTypeCurPos,iniDir);

StatusMazePalh(MazeType&maze,PosTypestart,PosTypeend){

//算法3.3

//若迷宫maze中从入口start到出口end的通道，则求得一条存放在栈中

//(从栈底到栈顶)，并返回TRUE；否则返回FALSE

StackS;

PosTypecurpos;

intcurstep;

SElemTypee;

InitStack(S);

curpos=start;//设定”当前位置“为“入口位置”

curstep=1;//探究第一步

do{

if(Pass(maze,curpos)){//当前位置可通过，即是未曾走到过的通道块

FootPrint(maze,curpos);//留下脚印

e.di=1;

e.ord=curstep;

e.seat=curpos;

Push(S,e);//加入路径

if(curpos.r==end.r&&curpos.c==end.c)

return(TRUE);//到达终点(出口)

curpos=NextPos(curpos,1);//下一位置是当前位置的东邻

curst叩++;//探究下一步

}else{//当前位置不能通过

if(!StackEmpty(S)){

Pop(S,e);

while(e.di==4&&!StackEmpty(S)){

MarkPrint(maze,e.seat);

Pop(S,e);//留下不能通过的标记，并退回一步

}//while

if(e.di<4){

e.di++;

Push(S,e);//换下一个方向探究

curpos=NextPos(e.seat,e.di);//当前位置设为新方向的相邻块

}//if

}//if

}//else

}while(!StackEmpty(S));

returnFALSE;

}//MazePath

StatusPass(MazeTypeMyMaze,PosTypeCurPos){

if(MyMaze.arr[CurPos.r][CurPos.c]==,*)

return1;//假如当前位置是可以通过，返回1

elsereturn0;//其它状况返回0

)

voidFootPrint(MazeType&MyMaze,PosTypeCurPos){

MyMaze.arr[CurPos.r][CurPos.c]=,*1;

)

voidMarkPrint(MazeType&MyMaze,PosTypeCurPos){

MyMaze.arr[CurPos.r][CurPos.c]-!*;

PosTypeNextPos(PosTypeCurPos,intDir){

PosTypeReturnPos;

switch(Dir){

case1:

ReturnPos.r=CurPos.r;

ReturnPos.c=CurPos.c+1;

break;

case2:

ReturnPos.r=CurPos.r+1;

ReturnPos.c=CurPos.c;

break;

case3:

ReturnPos.r=CurPos.r;

ReturnPos.c=CurPos.c-l;

break;

case4:

ReturnPos.r=CurPos.r-1;

ReturnPos.c=CurPos.c;

break;

}

returnReturnPos;

#defineOPSETSIZE7

unsignedcharPrior[7][7]={〃表3.1算符间的优先关系

>;>>V>;

•>'；>>7>',

>>7>

*>7>>?>>,

1>7>；>7>77>7>;

V'v;<7<*;<7v=*

)；

floatOperate(floata,unsignedchartheta,floatb);

charOPSET[OPSETSIZE]={'+*

StatusIn(charTest,char*TestOp);

charprecede(charAop,charBop);

floatEvaluateExpression(char*MyExpression){//算上去3.4

//算术表达式求值的算符优先算法。

//设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。

StackCharOPTR;//运算符栈，字符元素

StackFloatOPND;〃运算数栈，实数元素

charTempData[20];

floatData,a,b;

chartheta,*c,x,Dr[2];

InitStack(OPTR);

Push(OPTR,

InitStack(OPND);

c=MyExpression;

strcpy(TempData,,,\On);

while(*c!='#'||GetTop(OPTR)!=#){

if(!In(*c,OPSET)){

Dr[0]=*c;Dr[l]=>\0';

strcat(TempData,Dr);c++;

if(In(*c,OPSET)){

Data=(float)atof(TempData);

Push(OPND,Data);

strcpy(TempData,n\O");

}

}else{//不是运算符则进栈

switch(precede(GetTop(OPTR),*c)){

case,<\//栈顶元素优先权低

Push(OPTR,*c);

C++；

break;

case'h〃脱括号并接收下一字符

Pop(OPTR,x);

C++；

break;

case'>\//退栈并将运算结果入栈

Pop(OPTR,theta);

Pop(OPND,b);

Pop(OPND,a);

Push(OPND,Operate(a,theta,b));

break;

)//switch

)

}//while

returnGetTop(OPND);

}//EvaluateExpression

floatOperate(floata,unsignedchartheta,floatb){

switch(theta){

casereturna+b;

casereturna-b;

casereturna*b;

case7*:returna/b;

default:return0;

StatusIn(charTest,char*TestOp){

boolFind=false;

for(inti=0;i<OPSETSIZE;i++){

if(Test==TestOp[i])Find=true;

)

returnFind;

intReturnOpOrd(charop,char*TestOp){

inti;

for(i=0;i<OPSETSIZE;i++){

if(op==TestOp[i])returni;

)

return0;

)

charprecede(charAop,charBop){

returnPrior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];

)

intCount=0;

voidmove(charx,intn,charz);

voidhanoi(intn,charx,chary,charz){//算法3.5

//将塔座x上按直径由小到大且至上而下编号为1至n的n个圆盘按规章搬到

//塔座z上，y可用作帮助塔座。

//搬动操作move(x,n,z)可定义为：

//(c是初值为0的全局变量，对搬动计数)

//printf(n%i.Movedisk%ifrom%cto%c\nM,++c,n,x,z);

if(n==l)

move(x,1,z);〃将编号为1的圆盘从x移到z

else{

hanoi(n-l,x,z,y);

move(x,n,z);〃将编号为n的圆盘从x移到z

hanoi(n-l,y,x,z);//将y上编号为1至n-1的圆盘移到z,x作帮助塔

voidmove(charx,intn,charz){

printf(u%2i.Movedisk%ifrom%cto%c\n,\++Count,n,x,z)

//程序中用到的主要变量

EventListev;//大事表

Eventen;//大事

LinkQueueq[5];//4个客户队列,q[0]未用

QElemTypecustomer;//客户纪录

intTotalTime,CustomerNum;//累计客户逗留时间，客户数

intCloseTime;

//-----------算法3.7—-

intcmp(Eventa,Eventb){

//依大事a的发生时刻<或=或>大事b的发生时刻分别返回或。或1

if(a.OccurTime<b.OccurTime)return-1;

if(a.OccurTime>b.OccurTime)return+1;

return0;

)

voidRandom(int&durtime,int&intertime){//生成随机数

durtime=random(2,10);

intertime=random(lO);

)

intMinimum(LinkQueueq[]){//求长度最短队列

intminlen=QueueLength(q[1]);

inti=1;

for(intj=2;j<=4;j++)

if(QueueLength(q[j])<minlen){

minlen=QueueLength(q[j]);

i=j；

)

returni;

voidOpenForDayO{

//初始化操作

TotalTime=0;CustomerNum=0;//初始化累计时间和客户数为0

InitList(ev);//初始化大事链表为空表

en.OccurTime=0;en.NType=0;//设定第一个客户到达大事

Orderlnsert(ev,en,cmp);//按大事发生时刻的次序插入大事表

for(inti=l;i<=4;++i)InitQueue(q[i]);//置空队列

}//OpenForDay

voidCustomerArrived(){

//处理客户到达大事，en.NType=0

intdurtime,intertime,i,t;

++CustomerNum;

printf(uCustomer%darrivedat%dand",CustomerNum,en.OccurTime);

Random(durtime,intertime);//生成随机数

t=en.OccurTime+intertime;//下一客户到达时刻

if(t<CloseTime)//银行尚未关门，插入大事表

Orderlnsert(ev,MakeElem(t,0),cmp);

i=Minimum(q);//求长度最短队列

printf(uentertheQueue%d\n",i);

EnQueue(q[i],MakeQElem(en.OccurTime,durtime));

if(QueueLength(q[i])==1)//设定第i队列的一个离开大事并插入大事表

Orderlnsert(ev,MakeElem(en.OccurTime+durtime,i),cmp);

}//CustomerArrived

voidCustomerDeparture(){

//处理客户离开大事，en.NType>0

printf(nCustomerdepartureat%d\nu,en.OccurTime);

inti=en.NType;DeQueue(q[i],customer);〃册lj除第i队列的排头客户

TotalTime+=en.OccurTime-customer.ArrivalTime;//累计客户逗留时间

if(!QueueEmpty(q[i])){//设定第i队列的一个离开大事并插入大事表

GetHead(q[i],customer);

Orderlnsert(ev,MakeElem(en.OccurTime+customer.Duration,i),cmp);

)

}//CustomerDeparture

voidBank_Simulation(intclosetime){

inti=0;

BLinkp;

CloseTime=closetime;

printf(uBank_Simulation(%d)-----银行业务模拟\n”,closetime);

OpenForDayO;//初始化

while(!ListEmpty(ev)){

printList(ev);

if(DeIFirst(GetHead(ev),p)){

en=GetCurElem(p);

if(en.NType==0)

CustomerArrived();//处理客户到达大事

elseCustomerDeparture();//处理客户离开大事

)

if(++i%9==0){

printf(M\n——按任意键,连续

getch();

printf(n\n\nn);

)

)

//计算并输出平均逗留时间

printf("\nTheAverageTimeis%f\nH,(float)TotalTime/CustomerNum);

}//Bank_Simulation

#includeualgo0403.cpp"

intIndex(SStringS,SStringT,intpos){//算法4.1

〃T为非空串。若主串S中第pos个字符之后存在与T相等的子串，

〃则返回第一个这样的子串在S中的位置，否则返回0

intn,m,i;

SStringsub;

if(pos>0){

n=StrLength(S);m=StrLength(T);i=pos;

while(i<=n-m+l){

SubString(sub,S,i,m);

if(StrCompare(sub,T)==0)++i;

elsereturni;

}//while

}//if

return0;

)

StatusConcat(SString&T,SStringSI,SStringS2){//算法4.2

〃用T返回由SI和S2联接而成的新串。若未截断，则返回TRUE,否则FALSE。

inti;

Statusuncut;

if(S1[0]+S2[0]<=MAXSTRLEN){//未截断

for(i=l;i<=Sl[0];i++)T[i]=Sl[i];

for(i=l;i<=S2[0];i++)T[i+Sl[0]]=S2[i];

T[0]=S1[0]+S2[0];uncut=TRUE;

}elseif(Sl[0]<MAXSTRLEN){〃截断

for(i=1;i<=S1[0];i++)T[i]=Sl[i];

for(i=Sl[0]+1;i<=MAXSTRLEN;i++)T[i]=S2[i-S1[0]];

T[0]=MAXSTRLEN;uncut=FALSE;

}else{//截断(仅取SI)

for(i=0;i<=MAXSTRLEN;i++)T[i]=Sl[i];

uncut=FALSE;

)

returnuncut;

)//Concat

StatusSubSlring(SString&Sub,SStringS,inipos,intlen){

//算法4.3

//用Sub返回串S的第pos个字符起长度为len的子串。

//其中，1WposWStrLength(S)且OWlenWStrLength(S)-pos+l。

inti;

if(pos<1||pos>S[0]||len<0||len>S[0]-pos+l)

returnERROR;

for(i=l;i<=len;i++)

Sub[i]=S[pos+i-l];

Sub[0]=len;

returnOK;

}//SubString

StatusStrInsert(HString&S,intpos,HStringT){//算法4.4

〃lWposWStrLength(S)+l。在串S的第pos个字符之前插入串To

inti;

if(pos<1||pos>S.length+l)//pos不合法

returnERROR;

if(T.length){〃T非空，则重新安排空间，插入T

if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length+1)

*sizeof(char))))

returnERROR;

for(i=S.length-1;i>=pos-l;—i)//为插入T而腾出位置

S.ch[i+T.length]=S.ch[i];

for(i=0;i<T.length;i++)〃插入T

S.ch[pos-l+i]=T.chfi];

S.length+=T.length;

returnOK;

}//Strinsert

intIndex(SStringS,SStringT,intpos){//算法4.5

//返回子串T在主串S中第pos个字符之后的位置。

//若不存在，则函数值为0。

〃其中，T非空，IWposWStrLength(S)。

inti=pos;

intj=1;

while(i<=S[0]&&j<=T[0]){

if(S[i]==T[j]){//连续比较后继字符

++i；

++j；

}else{//指针后退重新开头匹配

i=i-j+2；

j=1；

)

)

if(j>T[O])returni-T[0];

elsereturn0;

}//Index

voidget_next(SStringT,int*next){//算法4.7

inti=l;

nextfl]=0;

intj=O;

while(i<T[0]){

if(j==O||T[i]==T[j]){

++i;++j;next[i]=j;

}elsej=next[j];

intIndex_KMP(SStringS,SStringT,intpos){//算法4.6

//采用模式串T的next函数求T在主串S中第pos个字符之后的位置的

〃KMP算法。其中，T非空，iWposWStrLength(S)。

intnext[255];

inti=pos;

intj=1;

get_next(T,next);

while(i<=S[OJ&&j<=T[OJ){

if(j==01|S[i]==T[j])(//连续比较后继字符

++i；++j；

}elsej=nextfj];//模式串向右移动

)

if(j>T[O])returni-T[O];〃匹配成功

elsereturn0;

)//Index_KMP

voidget_next(SStringT,int*next){//算法4.7

inti=l;

next[l]=0;

intj=0;

while(i<T[0]){

ifO==0||T[i]==T[j]){

++i;++j;next[i]=j;

}elsej=next[j];

intIndex_KMP(SStringS,SStringT,intpos){//算法4.6

//采用模式串T的next函数求T在主串S中第pos个字符之后的位置的

〃KMP算法。其中，T