数据结构的语言算法

数据结构的C语言算法

疑性结构o*o*o*o

树形结构

图状结构

集合结构

以下数据结构算法由C语言编译，并在TC上运行通过，其中，扩展名为”.CPP”

的为头文件，运行时只需将头文件与相应算法连接即可。

第一章绪论(预备知识)

练习1.16

/*试写一算法,自大至小输出顺序读入的三个整数X,Y和Z的值*/

#include<stdio.h>

voidswap(int*x,int*y,int*z)

{intt;

if(*x<*y)t=*x;*x=*y;*y=t;

if(*y<*z)t=*y;*y=*z;*z=t;

if(*x<*y)t=*x;*x=*y;*y=t;

)

main()

{inta,b,c;

scanf(H%d,%d,%d",&a,&b,&c);

swap(&a,&b,&c);

printf("%d%d%d",a,b,c);

1

第二章线性表

/.顺序表

实现顺序表基本算法的头文件sq.cpp为：

#include<stdio.h>

#defineMaxLen50/*顺序表中最多元素个数用

typedefintelemtype;

lypedefelemtypesqlist|MaxLen);

intcreate(sqlistA)/*创建线形表*/

{

inti,n;

printf("创建一个顺序表：\nu);

printf("输入元素个数：”)；

scanfC'%dH,&n);

fbr(i=O;i<n;i++)

(

printf("输入第%d个元素值:",i+l);

scanf(”％d”,&A[iD；

)

returnn;

)

voiddisp(sqlistA,intn)/*输出一个顺序表*/

(

inti;

printf("输出一个顺序表:\n");

if(n==0)printf("空表");

for(i=0;i<n;i++)

printf(n%dH,A[i]);

printf("\nu);

)

intins(sqlistA,intn,inti,elemtypex)

/*在顺序表第i个元素前插入一个元素X,若i=0,则新元素作为

第一个元素，若i=l,则插入在最后*/

(

intj;

if(i<O||i>n)printf("i值下溢或上溢\n");

else

(

for(j=n-l;j>=i;j-)A[j+l]=A[j];

将第i个元素及其后的元素后移*/

A[i]=x;n++J*顺序表长度加1*/

)

returnn;

)

intdel(sqlistA,intn,inti)

/*在顺序表中删除第i个元素*/

(

intj;

if(i<=O||i>n)printf(ni值下溢或上溢\n")；

else

(

for(j=i-l;j<n;j-H-)A[j]=A[j+l];

/*将第i个元素之后的元素前移覆盖A[i]*/

n-;/*顺序表长度减1*/

)

returnn;

)

intfind(sqlistA,intn,elemtypex)

*在一个有n个元素的顺序表A中查找元素值为x的元素*/

(

inti=0;

while(i<=n&&A|i|!=x)i++;

if(i<n)return1;

elsereturn0;

1

练习2.11:

/*设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序

性*/

#include"sq.cpp"

intinsert(sqlistA,intn,clemtypex)/*顺序表A的长度为n*/

intij;

if(x>=A[n-l])A[n]=x;

户若x大于最后的元素，则将其插入到最后*/

else

(

i=0;

while(x>A[i])i++;/*查找插入位置i*/

for(j=n;j>=i;j-)A|j+1]=A[j];

/*移出插入x的位置*/

A[i]=x;

I

return(n+1);/*顺序表长度增1*/

)

voidmain()

{

sqlistA;

intn;

n=create(A);

disp(A,n);

n=insert(A,n,10);/*插入元素10*/

disp(A,n);

getch();

}

/*运行结果：

创建一个顺序表

输入元素个数：3

输入第1个元素值：6

输入第1个元素值：9

输入第1个元素值：14

输出一个顺序表

6914

输出一个顺序表

691014*/

练习2.12

/*设4=(ai,...,am)和B=(b1,…,bm)均为顺序表，A♦和B，分别为A和B中除去最大共同前缀后的子表(例

如，A=(x,y,y,z,x,z),B=(x,y,y,z,y,x(x,z),则两者中最大的共同前缀为(x,y,y,z),在两表中除去最大的共同前

缀后的子表分别为A，=(x,z)和B，=(y,x,x,z)。若/V=IT=空表，则A=B;若,V=空表，IF!=空表，或者两者均不

为空表，且A，的首元小于B'的首元，则A<B；否则A>B.试写一个比较A,B大小的算法(请注意：在算

法中，不要破坏原表A和B,并且，也不一定先求得A，和B，才能进行比较)*/

#include"sq.cpp"

intcomp(sqlislA,intna,sqlistB,intnb)

{inti=0,j=0;

whiIe(i<na&&j<nb&&A[i++]==B[j++]);/*比较相同部分*/

if(i==na&&j==nb)returnO;/*a=b*/

if(i==na&&j!=nb)return-1;/*a<b*/

if(i!=na&&j==nb)return1;/*a>b*/

if(A[i]>B[j])

return1;

elsereturn-1;

)

voidmain()

{sqlistA,B；

intna,nb,n;

na=create(A);

nb=crcate(B);

n=comp(A,na,B,nb);

switch(n)

(

caseO:printf("A=B\n");break;

casel:printf("A>B\n");break;

case-l:printf("A<B\n");break;

I

getch();

1

/*运行结果

创建一个顺序表

输入元素个数：3

输入第1个元素值：2

输入第1个元素值：3

输入第1个元素值：5

创建一个顺序表

输入元素个数：4

输入第1个元素值：2

输入第1个元素值：3

输入第1个元素值：4

输入第1个元素值：5

比较结果：A>B

*/

练习2.16

/*删除A中第i个元素起的k个元素*/

#include"sq.cpp"

intdelk(sqlislA.inl*n,intk)

intj；

if(i<O||i+k-l>*n)

(

printf(ui,k参数不正确\n");

return0;

I

else

(

for(j=i+k-1;j<*n;j++)

A(j-k]=A[j];

(*n)-=k;

return1;

)

)

voidmain()

(

sqlistA;

intn,i,k;

n=create(A);

disp(A,n);

printf("输入

scanf(n%d%d",&i,&k);

if(delk(A,&n,i,k)==1)

disp(A,n);

getch();

)

/*运行结果：

创建一个顺序表

输入元素个数：5

输入第1个元素值：1

输入第1个元素值：2

输入第1个元素值：3

输入第1个元素值：4

输入第1个元素值：5

输出一个顺序表

12345

输入Lk:22

输出一个顺序表

145*/

练习2.21

/*试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表⑶加，…,而）逆置为⑶,a®…向）产/

#include"sq.cpp"

voidinvert(sqlistA,inin)

intm=n/2,i；/*m为长度的一半即[n\2]*/

elemtypetemp;

fbr(i=O;ivm;i++)/*将A[i]与人[*-1]进行交换*/

f

temp=A|i];A|i|=A[n-i-1|;A|n-i-l|=temp;

)

)

voidmain()

(

sqlistA;

intn;

n=create(A);

disp(A,n);

invert(A,n);

disp(A,n);

(

/*运行结果：

创建一个顺序表

输入元素个数：4

输入第1个元素值：2

输入第1个元素值：6

输入第1个元素值：3

输入第1个元素值：1

输出一个顺序表

2631

输出一个顺序表

1362*/

练习2.24

/*假设有两个按元素值递增有序排列的线性表A和B,均以单链表做存储结构，请编写算法将A表和B表

归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C,并要求利

用原表(即A表和B表)的结点空间构造C表*/

#includc"sq.cpp"

intintersect(sqlistA,intna,sqlistB,intnb,sqlistC)

(

inti=na,j=nb,k=0;

whiIe(i>=0&&j>=0)

if(A[i-l]>BU-l])

i-；

else

if(A[i-l]<B[j-l])

J-;

else/*A|i-l|=B|j-l]*/

(

C[k++]=A[i-l];

}

returnk-1;

)

voidmain()

(

sqlistA,B,C;

intna,nb,nc;

na=create(A);

disp(A,na);

nb=create(B);

disp(B,nb);

nc=intersect(A,na,B,nb,C);

disp(C,nc);

兴习题2.25号

/*假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合(即同一表中的元素值各不相同)，现

要求另开辟空间构成一个线性表C,其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列.

试对顺序表编写求C的算法*/

#include"sq.cpp”

intunions(sqlistAJntna,sqlistB,intnb,sqlistC)

(

inti=OJ=O,k=O;

while(i<na&&j<nb)

if(A[i]<B[j])

C[k++]=A[i++];

elseif(A[i]>B[j])

C[k++]=B[j++]；

else/*A[i]=B[i]*/

(

C[k++]=A[i];

i++;j++;

1

if(i<na)/*A还有元素*/

for(j=i；j<na;j++)

C[k++]=AQ];

elseif(j<nb)/*B还有元素*/

for(i=j;i<nb;i++)

C[k++]=B[i];

returnk;

)

voidmain()

(

sqlistA,B,C;

intna,nb»nc;

na=create(A);

disp(A,na);

nb=create(B);

disp(B,nb);

nc=unions(A,na,B,nb,C);

disp(C,nc);

2.线性表

实现线性表基本算法的头文件slink.cpp为：

#include<stdio.h>

#include<malloc.h>

typedefintelemtype;/*定义数据域的类型*/

typedefstructlinknode/*定义节点类型*/

(

elemtypedata;

structlinknode*next;

}nodetype;

nodetype"create。/*建立单链表，由用户输入各节点data域之值，以0表示输入结束*/

(

elemtyped;

nodetype*h=NULL,*s,*t;

inti=l;

peintf("建立一个单链表\n")；

while(l)

f

printf("输入第％d个节点data域值:",i);

scanf("%d",&d);

if(d==O)break;/*以0表示输入结束*/

if(i==l)/*建立第一个节点*/

{

h=(nodetype*)malloc(sizeof(nodetype));

h->data=d;h->next=NULL;t=h;

)

else/*建立其余节点*/

s=(nodetype*)malloc(sizeof(n(xletype));

s->data=d;s->next=NULL;t->next=s;

匚s;/*始终指向生成的单链表的最后一个节点*/

i++；

)

returnh;

)

voiddisp(nodetype*h)/*输出由h指向的单链表的所有data域之值*/

(

nodetype*p=h;

printf("输出一个单链表:\n");

if(p==NULL)printf(“空表”);

while(p!=NULL)

(

printf(H%d",p->data);

p=p->next;

)

printfCVn");

)

intlen(nodetype*h)/*返回单链表的长度*/

(

inti=0;

nodetype*p=h;

while(p!=NULL)

f

p=p->next;

i++；

)

returni;

)

nodetypefind(nodetype*h,inti)/*返回第i个节点的指针*/

(

nodetype*p=h;

intj=l;

if(i>len(h)||i<=0)

returnNULL;/*i上溢或下溢*/

else

(

while(p!=NULL&&j<i)/*查找第i个节点，并由p指向该节点*/

I

j++；

p=p->next;

)

returnp;

1

}

nodetype*ins(nodetype*hJnti,elemtypex)

/*单链表head中第i个节点(i>=0)之后插入一个data域为x的节点刃

(

nodetype*p,*s;

s=(nodetype*)malloc(sizeof(nodetype));/*创建节点s*/

s->data=x;

s->next=NULL;

if(i==0)/*i=0:s作为单链表的第一个节点*/

(

s->next=h;

h=s;

)

else

(

p=find(h,i);/*查找第i个节点，并由p指向该节点*/

if(p!=NULL)

(

s->next=p->next;

p->next=s;

1

else

prinlf("输入的i值不正确5");

)

returnh;

I

nodetype*del(iKxletype*n,inti)/*删除第i个节点

(

nodetype*p=h,*s;

mtj=l;

if(i==l)/*删除第一个节点*/

(

h=h->next;

free(p);

)

else

(

p=find(h,i-l);/*查找第i-1个节点，并由p指向该节点*/

if(p!=NULL&&p->next!=NULL)

s=p->ncxty*s指向要删除的节点*/

p->next=s->next;

free(s);

)

else

printf。输入的i值不正确\n”)；

I

returnh;

)

voiddispose(nodetype*h)/*释放单链表的所有节点占有的空间*/

(

nodetype*pa=h,*pb;

if(pa!=NULL)

(

pb=pa->next;

if(pb=NULL)/*只有一个节点的情况*/

free(pa);

else

(

while(pb!=NULL)/*有两个及两个以上的节点的情况*/

(

free(pa);

pa=pb;

pb=pb->next;

)

free(pa);

)

}

)

练习2.22

/*试写一算法，对单链表实现就地逆置为

#include"slink.cpp"

#include<malloc.h>

nodetype*invert(nodetype*h)/*实现单链表逆置*/

(

nodetype*p,*q,*r;

if(len(h)<=l)

(

printf("逆置的单链表至少有2个节点\n");

returnNULL;

1

else

p=h;

q=p->next;

while(q!=NULL)

(

r=q->next;

q->next=p;

p=q;q=r;

I

h->next=NULL;

h=p;

returnh;

1

)

voidmain()

(

nodetype*hcad;

head=create();

disp(hcad);

head=invert(head);

disp(hcad);

(

/*运行结果

建立一个单链表

输入第1节点data域值：1

输入第2节点data域值：2

输入第1节点data域值：3

输入第1节点data域值：4

输入第1节点data域值：5

输入第1节点data域值：0

输出一个单链表

12345

输出一个单链表

54321*/

练习2.23

/*设线性表人=(al,a2,...,am),B=(bl,b2”..,bn),试写一个按下列规则合并A,B为线性表C的算法，即使得

C=(al,bl,...,am,bm,bm+i,...,bm)当m<=n时，或者C=(ai,bi”..,a,"bn,an+i”..,a<n)当m>n时。线性表A,B

和C均以单链表做存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n

均未显示存储*/

#include"slink.cppn

nodetype*combine(nodetype*ha,nodetype*hb)

{

nodetype*hc=ha,*pa=ha,*pb=hb,*q,*r;

if(len(pa)!=len(pb))

printf("两个单链表长度不同\n”)；

returnNULL;

)

while(pa!=NULL)

f

q=pa->next;

r=pb->next;

pa->next=pb;

pb->next=q;

pa=q；

pb=r;

1

retum(hc);

}

voidmain()

(

nodetype*heada,*headb,*headc;

hcada=crcate();

headb=create();

headc=combinc(hcada.hcadb);

disp(headc);

)

练习2.26

#include"slink.cpp"

nodetype*connect(nodetype*h1,nodetype*h2)

(

nodetype*pa=hI,*pb=h2,*h3,*pc;

h3=(nodetype*)malloc(sizeof(nodetype));/*仓建哨兵*/

pc=h34pc总是指向生成的新单链表的最后一个节点*/

while(pa!=NULL&&pb!=NULL)

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

(

pc->next=pa;pc=pa;

pa=pa->next;

1

else

if(pa->data>pb->data)

pc->ncxt=pb;pc=pb;

pb=pb->next;

)

else/*pa->data=pb->data的情况*/

{

pc->next=pa;pc=pa;

pa=pa->next;pb=pb->next;

)

if(pa!=NULL)pc->next=pa;/*hl单链表还有节点时*/

if(pb!=NULL)pc->next=pb;/*h2单链表还有节点时*/

pc=h3;/*删除哨兵*/

h3=h3->next;

free(pc);

returnh3;

)

voidmain()

{

nodetype*headl,*head2,：i：head3;

head1=create();

head2=create();

disp(hcadl);

disp(head2);

head3=connect(head1,hcad2);

disp(head3);

)

练习2.34

#include<stdio.h>

#include<malloc.h>

typedefstructdnode

(

intdata;

structdnode*link;

Jdlist;

dlist*xor(dlist*pl,dlist*p2)

/*在C/C++中异或运算符不能对地址进行异或运算，所以先将地址值转换为长整形，然后进行异或运算，再

将结果强制转换成地址。这是本函数的功能用

{

intaddl,add2,add3;

addl=(long)pl;

add2=(long)p2;

add3=add1Aadd2;

return(dlist*)add3;

dlist*create(dlist**e)

inti=l,x;

dlist*head,*r,*s,*pre;

printf("创建一个双链表(以0结束)\n”)；

while(l)

(

print.”输入第％d节点值：”,i);

scanf("%dH,&x);

if(x==O)/*生成最后一个节点的link值后退出循环力

(

pre->link=xor(r,NULL);

/*将s->link置为前后节点地址之异或*/

*e=pre;

break;

)

s=(dlist*)malloc(sizeof(dlisl));/*创建—个节点*/

s->data=x;

if(i==l)/*是第一个节点的情况东/

{

pre=head=s;r=NULL;/*r为当前节点的前一个节点*/

)

else

(

pre->link=xor(r,s);

/*将s->link置为前后节点地址之异或*/

r=pre;

pre=s;

)

i++；

1

returnhead;

)

voidorder(dlist*h,dlist*e)

(

dlist*pre=NULL,*pre1,*p=h;

printf("遍历节点序列：");

if(h==NULL)

printf("空表n\");

else

(

while(p!=e)/*遍历最后一节点前的所有节点*/

(

printf(M%d",p->data);

prel=p;

p=xor(pre,p->link);/*为下一个节点的地址*/

pre=prel;

printf(n%d”,e->da⑶；

printf(n\nn);

)

1

voidmain()

(

dlist*h,*e;

inti;

h=create(&e);

printf("从左向右

order(h,e);

printf("从右向左”)；

order(e,h);

I

/*运行结果：

创建一个双链表(以0结束)

输入第1节点值:3

输入第1节点值:5

输入第1节点值:8

输入第1节点值:2

输入第1节点值:6

输入第1节点值:0

从左向右遍历节点序列：35826

从右向左遍历节点序列:62853*/

第三章栈和队列

实现栈基本算法的头文件stack.cpp为：

#include<stdio.h>

#defineMaxLen20/*顺序栈存放的最多元素个数为Maxlen-1*/

typedefcharelemtype;

typedefstructsqstack

(

elemtypedata|MaxLen];

inttop;

)stack;

voidinit(stack*st)/*初始化栈st*/

{

st->top=0;

)

intpush(stack*st,elemtypex)/*入栈*/

(

if(st->top==MaxLen-1)

printf("栈溢出\n");

return0;

)

else

(

St->tOp+4-；

st->data[st->top]=x;

return1;

)

)

intpop(stack*st,elemtype*x)/*退栈号

|

if(st->top==0)

(

printf("栈下溢出\n");

return0;

)

else

{

*x=st->data[st->top];

st->top-;

return1;

}

)

intempty(stack判断栈空*/

{

if(st->top==0)

return1;

else

return0;

1

intgettop(stack*st,elemtype*x)/*获取栈顶元素%/

(

if(st->top==0)

(

printf("栈下溢出\n");

return0;

)

else

(

*x=st->data[st->top];

return1;

)

)

voiddisp(stack*st)/*输出栈的所有元素*/

{

inti;

fbr(i=st->top;i>0;i—)

printf("%d",st->data[i]);

printf(,,\nM);

)

/*练习3.19*/

/*假设一个算术表达式中可以包含三种括号，圆括号"(“和“广、方括号“『和”「和花括号和“广，且这三

种括号可按任意的次序嵌套使用(如:・・[・・{・・}・・[・・]・・].・[・・]・・(・・)・.).编写判别给定表达式中所含括号是否正确配对

出现的算法(已知表达式已存入数据元素为字符的顺序表中*/

/*输入：{a+[b+(c+d)+e]+f)*/

#include"stack.cpp"

#include<malloc.h>

intcorrect(char*str)

(

stackst;

charx;

inti,ok=l;

init(&st);

fbr(i=O;str[i]!=^,;i++)

(

switch(str[i])

(

case'(':push(&st,'(,);break;

case'[':push(&st,T);break;

case'{':push(&st/{');break;

case,),：if(!(pop(&st,&x)&&x==,(,))

ok=0;break;

case,],:if(!(pop(&st,&x)&&x='[,))

ok=0;break;

case'}':if(!(pop(&st,&x)&&x==,{'))

ok=0;break;

)

if(!ok)break;

)

if(empty(&st)&&ok)

return1;

else

return0;

voidmain()

char*str;

str=(char*)malloc(l00*sizeof(char));

printf('rstr:");

scanf("%s",str);

if(correct(str))

printf("表达式括号匹配\n”)；

else

printf("表达式括号不匹配\n”)；

getch();

)

练习3.21

#include<stdio.h>

#defineMaxLen100

inttrans(charstr|],charexp||)

{

intst[MaxLen];/*作为栈使用”

charch;

inti=0,t=0,top=-l;/*t作为exp的下标，top作为st的下标,i作为str的下标*/

while((ch=str[i++])!-\0')

{

if(ch>=,0,&&ch<=9)/*判断为数字以

(

exp[t]=ch;t++；

while((ch=str[i++])!=,\0,&&ch>='0'&&ch<='9')

(

exp[t]=ch;t++；

)

i-S

exp[t]-#';t++;

)

elseif(ch=='(')/*判断为左括号*/

{

top++；st[top]=ch;

)

elseif(ch==')»*判断为右括号刃

(

while(st[top]!='(1)

(

exp[t]=st[top];top-;t++;

1

top-;

)

elseif(ch==』[|ch=='-')/*判断为加减号*/

while(top>=0&&st[top]!-(')

(

exp[t]=st[top];top-;t++;

)

top++；st[top]=ch;

)

elseif(ch=='*'||ch==7,)

(

while(st[top]=='*'||st[top]==7,)

(

exp[t]=st[top];top-;t++;

1

top++;st[top]=ch;

}

)

while(top>=0)

(

exp[t]=st|top|;t++;top-;

)

exp[t尸0\，；

return1;

)

intcompvalue(charexp[],int*n)

(

intst[MaxLen],d;/*作为栈使用*/

charch;

intt=0,top=-l;/*t作为exp的下标，top作为st的下标*/

while((ch=exp[t+l])!='\0r)

(

if(ch>=,0,&&chv=9)/*为数字字符时转换为数字刃

(

d=0;

do

(

d=10*d+ch-,0,;

)while((ch=exp[t+4-J)!='#');

top++;st[top]=d;/♦数字进栈*/

)

else/*为运算符时，计算并退栈*/

(

switch(ch)

case'+':st[top-l]=st[top-l]+st[top];break;

case'-'zstltop-l]=st|top-l]-st|top|;break;

case'*':st[top-1]=st[top-l]*st[top];break;

case71:if(st[top]!=0)st[top-l]=st[top-l]/st[topi;

else

return0;/*除0错误*/

break;

}

top-;

)

)

(*n)=st|top];

return1;

I

voidmain()

(

charstr[MaxLen];/*存储原算术表达式*/

charexp[MaxLen];/东存储转换成的波兰表达式*/

intn;

printf("算术表达式:")；

scanf("%s",&str);

if(trans(str,exp)==O)

printf("原算术表达式不正确\n");

else

(

printf("波兰表达式:%d\n",exp);

if(compvalue(exp,&n)==l)

printf("计算结果:%d\n",n);

else

printf("计算错误\n")；

)

)

练习3.27

/*已知Ackerman函数的定义如下：

Akm(m,n)=n+l(m=0),akni(ni-l,l)(m!=0,n=0)akm(m-l),akm(m,n-l))(m!=0,n!=0)

1.写出递归算法；2。写出非递归算法；3。根据非递归算法，画出求akm(2,l)时栈的变化过程刃

#include<stdio.h>

#defineMaxLcn5000/本此数应足够大，因为m和n值的较小增长会引起函数值的极快增长，用的栈的空间

也很大*/

intfl(intm,intn)

(

if(m==0)

returnn+1;

else

if(n==O)return

else

return

)

intno(intm,intn)

(

if(m==O)

return1;

elseif(n==O)

return2;

elsereturn3;

}

intf2(intm,intn)

(

intst[MaxLen][4],top=l,ml,nl;

st[top][O]=no(m,n);

st[top][l]=0;/*初值0进栈*/

st[topH2]=m;/*初值m进栈*/

st[top][3]=n;/*初值n进栈*/

do/*开始循环*/

(

if(st[top][1]==0)

(

if(st[top][0]==3)

(

top++;

st[top][l]=0;

st[top][2]=st[top-l][2];

stftop][3]=st[top-1][3]-1;

st[top|[0]=no(st|topH2],st|top][3]);

)

elseif(st[top][0]=2)

(

top++;

st[top][l]=0;

st[top][2]=st|top-l][2]-l;

st[top][3]=l;

st[top][0]=no(st[top][2],st[top][3]);

)

if(st[top][0]==l)

st[top][1]=st[top][3]+l;

if(top>=1&&st[top][l]!=0&&st[top-l][0]==2)

st[top-l][l]=st[top][l];

top-；

1

elseif(top>=1&&st[top][1]!=0&&st[top-1][0]==3)

(

nl=st[top][l];

ml=st[top-l][2]-l;

top-;

st[top][l]=0;

st[top][2]=ml;

st[top][3]=nl;

st[top][0]=no(st[top][2],st[top][3]);

)

if(top==1&&st[top][l]!=0)/*栈中已有一个元素，且已计算出值，则退出循环*/

break;

)while(top>=l);

return(st[l][l]);

}

voidmain()

{

intn,m;

printf("inputmn:");

scanf("%d%d",&m,&n);

printf("diguic(%d,%d)=%d\n",m,n,fl(m,n));

printf("feidiguic(%d,%d)=%d\n",m,n,f2(m,n))；

system("pause'1);

1

/*输入：38回车

diguic(3,8)=2045

feidiguic(3,8)=2045*/

练习3.28

*假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点(注意

不设头指针)，试编写相应的队列初始化、入队列和出队列的算法可

#include<stdio.h>

#defineMaxSize6

typedefcharqueue[MaxSize];

intrear=0Jen=0;/*队列初态*/

intenqueue(queuequ,charx)

{

if(len=二MaxSize)/*队满，上溢出*/

return0;

else

rear=(rear+1)%MaxSize;

qu|rear|=x;

len++;/*队列长度增1*/

returnI;

I

1

intdequeue(queuequ,char*x)

(

intfront;

if(len=0)/*队列为空时下溢出号

return0;

else

(

front=(rear-len+1+MaxSize)%MaxSize;

*x=qu[front];

len--;/*队列长度减1*/

return1;

)

)

voidmain()

1

charx;

queuequ;

printf(Ha入队\n");

enqueue®,'a');

printf(Hb入队\n");

enqueue(qu,'b');

printf(Hc入队\n");

enqueue(qu,'c');

printf(咄队一次

dequeue(qu,&x);

printf("%c\n",x);

printf(Hd入队\n");

enqueue(qu/d');

printf(He入队\n");

enqueue(qu,'e,);

printfC出对一次门;

dcqueue(qu.&x);

pnntf(H%c\nH,x);

printf("f入队\n")；

enqueue(qu/f);

printf(Hg入队\n")；

enqueue(qu,'g');

printfC出队一次

dequeue(qu,&x);

printf("%c\n",x);

printf("余下元素出列:")；

while(len>0)

(

dequeue(qu,&x);

printf(M%cM,x);

I

printf("\n");

system("pausen);

1

练习3.31

假设称正读和反读都相同的字符序列为“回文”，例如：'abba'和'abcba'是回文，'abed"和"ababab,

则不是回文。试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”.*/

#include<stdio.h>

#include<malloc.h>

#defineMaxLen100

typedefstructnode

(

chardata;

structnode*next;

Jcnode;

cnode*create(chars[])

(

inti=0;

cnode*h,*p,*r;

while(s[i]!=、0')

I

p=(cnode*)malloc(sizeofi(cnode));

p->data=s[i];p->next=NULL;

if(i==0)

(

h=p;r=h;/*r始终指向最后一个结点*/

)

else

(

r->next=p;r=p;

1

i++；

1

returnh;

intjudge(cnode*h)

charst[MaxLen];

inttop=0;

cnode*p=h;

while(p!二NULL)

f

st[topl=p->data;

top++;

p=p->next;

)

p=h;

while(p!=NULL)

{

top-;

if(p->data==st|top])

p=p->next;

else

break;

}

if(p==NULL)

return1;

else

return0;

)

voidmain()

{charstr[MaxLen];

cnode*h;

printf("输入一个字符序列：");

scanf("%s",str);

h=create(str);

if(judge(h)==l)

printf("'%s'是回文”,str);

else

不是回文”,str);

getch();

)

第四章串

实现串基本运算的头文件string.cpp为:

#include<stdio.h>

#include<string.h>

#dcfincMaxLen20

typedefstrcut

charch[MaxLen];

intlen;

}strtype;

voidcreate(strtype*s,charstr[])/*将普通字符串赋给串*/

(

strcpy(s->ch,str);

s->len=strlen(str);

}

intlength(strtype*s)/*求串长度*/

(

returns->len;

}

voidcopy(strtype*s1,strtype*s2)/*串的复制*/

{

inti;

for(i=0;i<sl->len;i++)

s2->ch[i]=s1->ch[i];

s2->len=sl->len;

s24ch添加字符串结束符刃

)

strtyprsubs(strtype*s,intpos,intn)/*求子串*/

{

inti;

strtypesub;

if(pos+n-l>length(s1))/*参数不正确*/

sub.len=0;

else

(

for(i=pos-1;i<pos+n-1;i++)

sub.ch[i-pos+l]=s->ch[i|;

sub.len=n;

sub.ch[sub.lcn]-\O';

)

returnsub;

I

)

intconcat(strtype*s,strtype*t)/*连接两个串*/

(

inti;

if(s->len+t->lcn>MaxLen)

return0;

fbr(i=O;i<t->len;i++)

s->ch[i+s->len]=t->ch[i];

s->len=s->len+t->len;

s->ch[s->len]-\O';

return1;

}

intins(strtype*s,strtypei)户插入一个子串*/

(

intj;

if(s->len+t->len>MaxLen)

return0;

for(j=s->len-1;j>=i-1;j-)/*i之后的所有元素后移t->lcn个位置*/

s->ch|j+t->len|=s->ch[j];

for(j=0;j<t->len;j++)

s->ch|j+i-l]=t->ch[j];

s->len=s->len+t->len;

s->ch[s->len]='\0,;

return1;

}

intdel(strlype*s,intpos,intn)/*删除一个子串*/

(

inti;

if(pos+n>s->lcn)

fbr(i=pos+n-1;i<s->len;i++)

s->ch[i-n]=s->