数据结构严蔚敏 习题.docx
- 文档编号:8750870
- 上传时间:2023-05-14
- 格式:DOCX
- 页数:29
- 大小:21.40KB
数据结构严蔚敏 习题.docx
《数据结构严蔚敏 习题.docx》由会员分享,可在线阅读,更多相关《数据结构严蔚敏 习题.docx(29页珍藏版)》请在冰点文库上搜索。
数据结构严蔚敏习题
第三章
intLikeStack()
{//判断字符序列是否形如序列1&序列2
InitStack(S1);InitStack(S2);//构造两空栈,序列正序入S1栈逆序入S2栈
i=0;count=1;//i标记&的个数,count标记字符个数
ch=getchar();
while(ch!
='@')
{//字符依次s1进栈
if(ch=='&')i++;
Push(S1,ch);
ch=getchar();
count++;
}
if(i!
=1)return0;//序列中不含&或序列1序列2中含&
if(count%2!
=1)return0;//序列2不可能是序列1的逆序(字符个数不等)
for(j=1;j<=count;j++)
{//序列逆序入S2栈
e=*(S1.top-j);
Push(S2,e);
}
while(!
StackEmpty(S1))
{//依次对应比较的S1S2栈顶元素,相同则删除继续比较
Pop(S1,c1);Pop(S2,c2);
if(c1!
=c2)return0;
}
return1;//此时s1s2均为空栈且字符对应相同
}
bollMatch()
{//检验表达式中两种括号是否配对
InitStack(S);//构造空栈S
ch=getchar();//接收第一个字符
while(ch!
='#')
{//若为左括号则入栈
if(ch=='('||ch=='[')
Push(S,ch);
else
{//若为右括号
if(ch==')'||ch==']')
{if(StackEmpty(S))returnFALSE;//若接受的第一个字符为右括号
GetTop(S,e);//否则取栈顶元素e
//若与栈顶元素配对则删除栈顶元素
if(ch==')'&&e=='(')
Pop(S,c);
if(ch==']'&&e=='[')
Pop(S,c);
}
}
ch=getchar();//接收下一个字符
}
if(StackEmpty(S))returnTRUE;//括号都配对
elsereturnFALSE;
}
intLikeStack()
{//判断字符序列是否形如序列1&序列2
InitStack(S1);InitStack(S2);//构造两空栈,序列正序入S1栈逆序入S2栈
i=0;count=1;//i标记&的个数,count标记字符个数
ch=getchar();
while(ch!
='@')
{//字符依次s1进栈
if(ch=='&')i++;
Push(S1,ch);
ch=getchar();
count++;
}
if(i!
=1)return0;//序列中不含&或序列1序列2中含&
if(count%2!
=1)return0;//序列2不可能是序列1的逆序(字符个数不等)
for(j=1;j<=count;j++)
{//序列逆序入S2栈
e=*(S1.top-j);
Push(S2,e);
}
while(!
StackEmpty(S1))
{//依次对应比较的S1S2栈顶元素,相同则删除继续比较
Pop(S1,c1);Pop(S2,c2);
if(c1!
=c2)return0;
}
return1;//此时s1s2均为空栈且字符对应相同
}
bollMatch()
{//检验表达式中两种括号是否配对
InitStack(S);//构造空栈S
ch=getchar();//接收第一个字符
while(ch!
='#')
{//若为左括号则入栈
if(ch=='('||ch=='[')
Push(S,ch);
else
{//若为右括号
if(ch==')'||ch==']')
{if(StackEmpty(S))returnFALSE;//若接受的第一个字符为右括号
GetTop(S,e);//否则取栈顶元素e
//若与栈顶元素配对则删除栈顶元素
if(ch==')'&&e=='(')
Pop(S,c);
if(ch==']'&&e=='[')
Pop(S,c);
}
}
ch=getchar();//接收下一个字符
}
if(StackEmpty(S))returnTRUE;//括号都配对
elsereturnFALSE;
}
第五章
5.8对角矩阵存于一维数组B[k]中对应(i,j)
i为奇数时,k=i+j-2
i为偶数时,k=i+j-1
5.21
intAid_TSMatrix(TSMatrixMa,TSMatrixMb,TSMatrix&Mc)
{//稀疏矩阵A,B一三元组顺序表Ma,Mb存储,求C=A+B并以三元组顺序表Mc存储
if((Ma.nu!
=Mb.nu)||(Ma.mu!
=Mb.mu))
return0;//A,B维数不同,不能进行加法运算
Mc.nu=Mb.nu;Mc.mu=Mb.mu;Mc.tu=0;
p=q=k=1;
while(p<=Ma.tu&&q<=Mb.tu)
{
if(Ma.data[p].i==Mb.data[q].i)
{//A,B当前元素行相同
if(Ma.data[p].j==Mb.data[q].j)//若列也相同,对应元素求和
{if(Ma.data[p].e+Mb.data[q].e)//若和不为0,存入Mc,k下移;否则,k不改变
{
Mc.data[k].e=Ma.data[p].e+Mb.data[q].e;
Mc.data[k].i==Ma.data[p].i;
Mc.data[k].j==Ma.data[p].j;
k++;
}
p++;q++;//p,q下移
}
else//列数不同时,列数较小的存入Mc,对应指针下移
Mc.data[k++]=(Ma.data[p].j Ma.data[p++]: Mb.data[q++]); } else//行数不同时,行数较小的存入Mc,对应指针下移 Mc.data[k++]=(Ma.data[p].i Ma.data[p++]: Mb.data[q++]); }//while if(p<=Ma.tu)//若Ma,Mb中有一个先结束,则将未结束的部分依次存入Mc for(p;p<=Ma.tu;p++) Mc.data[k++]=Ma.data[p]; if(q<=Mb.tu) for(q;q<=Mb.tu;q++) Mc.data[k++]=Ma.data[q]; Mc.tu=k-1; return1; }//end 实验一 //本实验要求实现以下功能: //1.以邻接矩阵或邻接表作为存储结构建立一个无向图。 //2.深度(或广度)优先搜索该无向图,输出遍历序列。 //[测试数据]: 对如图的无向图建立存储并遍历: #include"stdio.h" #include"stdlib.h" //图的邻接表存储表示 #defineMAX_VERTEX_NUM20//最大定点数 #defineMAX100 typedefstructArcNode {intadjvex;//邻接点域,存放与Vi邻接的点在表头数组中的位置 structArcNode*next;//链域,指示下一条边或弧 }JD; //表头接点: typedefstructVNode {chardata;//存放顶点信息 JD*firstrarc;//指示第一个邻接点 }TD,AdjList[MAX_VERTEX_NUM]; typedefstruct { TDvertices; intvexnum,arcnum;//图的当前顶点数和边数 intkind;//图的种类标志 }AGraph; //图的邻接矩阵存储表示 typedefstructArcCell { int*info;//存储边的相关信息(权值等) intadj;//用0,1表示顶点是否相邻 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedefstruct { charvexs[MAX_VERTEX_NUM]; AdjMatrixarcs;//邻接矩阵 intvexnum,arcnum;//图的当前顶点数和边数 }MGraph; intLocate(MGraphG,charv) {//顶点定位 inti; for(i=0;i if(G.vexs[i]==v) returni; } intLocateVex(AGraphG,charv) { inti; for(i=0;i if(G.vertices[i].data==v) returni; } voidCreatUNGM(MGraph&G) {//采用邻接矩阵构建一个无向图 inti,j,k;charv1,v2; scanf("%d%d",&G.vexnum,&G.arcnum); for(i=0;i for(i=0;i for(j=0;j G.arcs[i][j]=0;//初始化邻接矩阵 for(k=0;k {//构造邻接矩阵 scanf("%c%c",&v1,&v2);//输入依附一条边的顶点 i=Locate(G,v1);j=Locate(G,v2);//确定的v1v2在G中的位置 G.arcs[i][j]=1; G.arcs[j][i]=G.arcs[i][j]; } for(i=0;i {for(j=0;j printf("%3d",G.arcs[i][j]); printf("\n"); } } voidCreatUNGA(AGraph&G) {//采用邻接表构建一个无向图 inti,j,k;charv1,v2; scanf("%d%d",&G.vexnum,&G.arcnum); for(i=0;i {//构造表头 scanf("%c",&G.vertices[i].data);//输入顶点信息 G.vertices[i].firsttarc=NULL;//初始化指针 } for(k=0;k { scanf("%c%c",&v1,&v2);//输入依附一条边的顶点 i=LocateVex(G,v1);j=LocateVex(G,v2);//确定的v1v2在G中的位置 p1=(JD*)malloc(sizeof(JD)); p2=(JD*)malloc(sizeof(JD)); p1.adjvex=j;p1=G.vertices[i].firstrarc;p1.next=NULL; p2.adjvex=i;p2=G.vertices[j].firstrarc;p2.next=NULL;//结点赋值 G.vertices[i].firstrarc=p1; G.vertices[j].firstrarc=p2; } } voidDFS(AGraphG,intv) {intvisited[MAX],I; JD*W; printf(“%C”,G.vertices[V].data); visited[v]=1; w=G.vertices[V].firstarc;//获取v的邻接点 while(w! =NULL) {I=w->adjvex;//邻接点在数组中的下标位置 if(visited[I]==0) DFS(G,I); w=w->next; } } voidBFS(TDg,intv) {intvisited[MAX],f=0,r=0;//设置队列的头尾指针 printf(“%d”,v); visited[v]=1; qu[0]=v;//结点v入队 while(f<=r)//队列不为空 {v=qu[f++];//出队 p=g[v].firstarc;//求v的第一个邻接点 while(p! =NULL)//求v其余的邻接点 {v=p->adjvex;//求该结点在访问标志数组中的下标 if(visited[v]==0) {visited[v]=1;printf("%d\n",v); qu[++r]=v; } p=p->next; } } } voidmain() { intvisited[MAX]; AGraphG; CreatUNGA(G);//采用邻接表构建一个无向图 DFS(G,1); } #include #include typedefintElemType; typedefstructLNode { ElemTypedata; structLNode*next; }LNode,*LinkList;//定义结点类型 voidInsert_List(LinkList&L,intX) {//在带头结点非递减有序单链表中插入一同类型元素并保持有序性 LinkListpre=L,p=L->next,s;//p指向当前,pre指向其前驱 intflag=1; s=(LinkList)malloc(sizeof(LNode)); s->data=X;//给待插入元素分配空间 while(p&&flag) {//S结点定位 if(X>p->data) {pre=p;p->next;} elseflag=0; } s->next=pre->nex; pre->next=s;//插入s结点 }//Insert_List voidCreat_SortList(LinkList&L,intn) {//输入n个数并建立带头结点的非递减有序数列 intX; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; for(inti=1;i<=n;i++) { scanf("%d",&X); Insert_List(L,X); } } voidDispList(LinkListL) {//输出单链表L LinkListp=L->next; while(P! =NULL) { printf("%d",p->data); p=p->next; } printf("\n"); } voidMergeList_L(LinkListLa,LinkListLb,LinkList&Lc) {//已知非递减顺序单链表La和Lb//归并La和Lb得到新非递减链表Lc LinkListpa=La->next,pb=Lb->next,pc=La; Lc=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;} } pc->next=pa? pa: pb;//插入剩余段 free(Lb);//释放Lb的头结点 } voidmain() { LinkListL1,L2,L3; Creat_SortList(L1,5); DispList(L1); Creat_SortList(L2,5); DispList(L2); MergeList_L(L1,L2,L3); DispList(L3); } 练习二 //本实验要求实现以下功能: //1.以邻接矩阵或邻接表作为存储结构建立一个无向图。 //2.深度(或广度)优先搜索该无向图,输出遍历序列。 //[测试数据]: 对如图的无向图建立存储并遍历: #include"stdio.h" #include"stdlib.h" //图的邻接表存储表示 #defineMAX_VERTEX_NUM20//最大定点数 #defineMAX100 typedefstructArcNode {intadjvex;//邻接点域,存放与Vi邻接的点在表头数组中的位置 structArcNode*next;//链域,指示下一条边或弧 }JD; //表头接点: typedefstructVNode {chardata;//存放顶点信息 JD*firstrarc;//指示第一个邻接点 }TD,AdjList[MAX_VERTEX_NUM]; typedefstruct { TDvertices; intvexnum,arcnum;//图的当前顶点数和边数 intkind;//图的种类标志 }AGraph; //图的邻接矩阵存储表示 typedefstructArcCell { int*info;//存储边的相关信息(权值等) intadj;//用0,1表示顶点是否相邻 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedefstruct { charvexs[MAX_VERTEX_NUM]; AdjMatrixarcs;//邻接矩阵 intvexnum,arcnum;//图的当前顶点数和边数 }MGraph; intLocate(MGraphG,charv) {//顶点定位 inti; for(i=0;i if(G.vexs[i]==v) returni; } intLocateVex(AGraphG,charv) { inti; for(i=0;i if(G.vertices[i].data==v) returni; } voidCreatUNGM(MGraph&G) {//采用邻接矩阵构建一个无向图 inti,j,k;charv1,v2; scanf("%d%d",&G.vexnum,&G.arcnum); for(i=0;i for(i=0;i for(j=0;j G.arcs[i][j]=0;//初始化邻接矩阵 for(k=0;k {//构造邻接矩阵 scanf("%c%c",&v1,&v2);//输入依附一条边的顶点 i=Locate(G,v1);j=Locate(G,v2);//确定的v1v2在G中的位置 G.arcs[i][j]=1; G.arcs[j][i]=G.arcs[i][j]; } for(i=0;i {for(j=0;j printf("%3d",G.arcs[i][j]); printf("\n"); } } voidCreatUNGA(AGraph&G) {//采用邻接表构建一个无向图 inti,j,k;charv1,v2; scanf("%d%d",&G.vexnum,&G.arcnum); for(i=0;i {//构造表头 scanf("%c",&G.vertices[i].data);//输入顶点信息 G.vertices[i].firsttarc=NULL;//初始化指针 } for(k=0;k { scanf("%c%c",&v1,&v2);//输入依附一条边的顶点 i=LocateVex(G,v1);j=LocateVex(G,v2);//确定的v1v2在G中的位置 p1=(JD*)malloc(sizeof(JD)); p2=(JD*)malloc(sizeof(JD)); p1.adjvex=j;p1=G.vertices[i].firstrarc;p1.next=NULL; p2.adjvex=i;p2=G.vertices[j].firstrarc;p2.next=NULL;//结点赋值 G.vertices[i].firstrarc=p1; G.vertices[j].firstrarc=p2; } } voidDFS(AGraphG,intv) {intvisited[MAX],I; JD*W; printf(“%C”,G.vertices[V].data); visited[v]=1; w=G.vertices[V].firstarc;//获取v的邻接点 while(w! =NULL) {I=w->adjvex;//邻接点在数组中的下标位置 if(visited[I]==0) DFS(G,I); w=w->next; } } voidBFS(TDg,intv) {intvisited[MAX],f=0,r=0;//设置队列的头尾指针 printf(“%d”,v); visited[v]=1; qu[0]=v;//结点v入队 while(f<=r)//队列不为空 {v=qu[f++];//出队 p=g[v].firstarc;//求v的第一个邻接点 while(p! =NULL)//求v其余的邻接点 {v=p->adjvex;//求该结点在访问标志数组中的下标 if(visited[v]==0) {visited[v]=1;printf("%d\n",v); qu[++r]=v; } p=p->next; } } } void
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构严蔚敏 习题 数据结构 严蔚敏