- 1双人贪吃蛇@botzone数据格式_botzone数据怎么用
- 2将金融文件转化为ASP.NET Core C#中的智能且安全的表单
- 3【HarmonyOS】ArkUI - 自定义组件_arkui 自定义组件
- 4windows环境下ElasticSearch+kibana+ElasticSearch-Head安装搭建_windows es
- 5python上海房价数据分析统计服_(干货)数据分析案例--以上海二手房为例
- 6华为大佬的“百万级”MySQL笔记，基础+优化+架构一键搞定_百万级数据,需要用什么数据库
- 7Datahub安装教程
- 8Nginx 面试分享(十一)：部署与集群_nginx tomcat 集群
- 9gitlab-runner k8s cicd小demo_gitlab-runner测试demo
- 10集成学习1——voting、bagging&stacking_voting集成学习
2021SCAU数据结构复习(实验1-实验3)_#include #include struct tree {
赞
踩
题1:8576 顺序线性表的基本操作
题目描述
Description 编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。本题目给出部分代码，请补全内容。
#include<stdio.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
typedef struct
{
int *elem;
int length;
int listsize;
}SqList;
int InitList_Sq(SqList &L)
{
// 算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE
// 请补全代码
}
int Load_Sq(SqList &L)
{
// 输出顺序表中的所有元素
int i;
if() printf(“The List is empty!”); // 请填空
else
{
printf("The List is: ");
for() printf("%d “,_________________________); // 请填空
}
printf(”\n");
return OK;
}
int ListInsert_Sq(SqList &L,int i,int e)
{
// 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e
// i的合法值为1≤i≤L.length +1
// 请补全代码
}
int ListDelete_Sq(SqList &L,int i, int &e)
{
// 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值
// i的合法值为1≤i≤L.length
// 请补全代码
}
int main()
{
SqList T;
int a, i;
ElemType e, x;
if() // 判断顺序表是否创建成功
{
printf(“A Sequence List Has Created.\n”);
}
while(1)
{
printf(“1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n”);
scanf("%d",&a);
switch(a)
{
case 1: scanf("%d%d",&i,&x);
if() printf(“Insert Error!\n”); // 判断i值是否合法，请填空
else printf(“The Element %d is Successfully Inserted!\n”, x);
break;
case 2: scanf("%d",&i);
if(_________________________) printf(“Delete Error!\n”); // 判断i值是否合法，请填空
else printf(“The Element %d is Successfully Deleted!\n”, e);
break;
case 3: Load_Sq(T);
break;
case 0: return 1;
}
}
}
AC代码
#include<stdio.h> #include<malloc.h> #include <iostream> #define OK 1 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemType int typedef struct { int *elem; int length; int listsize; }SqList; int InitList_Sq(SqList &L) { // 算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE L.elem=new ElemType[LIST_INIT_SIZE]; if(!L.elem) { return ERROR; } L.length=0; return OK; } int Load_Sq(SqList &L) { // 输出顺序表中的所有元素 if(L.length==0) printf("The List is empty!"); // 请填空 else { printf("The List is: "); for(int i=0;i<L.length;i++) printf("%d ",L.elem[i]); // 请填空 } printf("\n"); return OK; } int ListInsert_Sq(SqList &L,int i,int e) { // 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e // i的合法值为1≤i≤L.length +1 /*insert*/ if(i<1||i>L.length+1) { return ERROR; } if(L.length==LIST_INIT_SIZE) { return ERROR; } for(int k=L.length;k>=i;k--) { L.elem[k]=L.elem[k-1]; } L.elem[i-1]=e; L.length++; return OK; } int ListDelete_Sq(SqList &L,int i, int &e) { // 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值 // i的合法值为1≤i≤L.length if(i<1||i>L.length) { return ERROR; } e=L.elem[i-1]; for(int k=i;k<L.length;k++) { L.elem[k-1]=L.elem[k]; } L.length--; return OK; } int main() { SqList T; int a, i; ElemType e, x; if(InitList_Sq(T)) // 判断顺序表是否创建成功 { printf("A Sequence List Has Created.\n"); } while(1) { printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a) { case 1: scanf("%d%d",&i,&x); if(!ListInsert_Sq(T,i,x)) printf("Insert Error!\n"); // 判断i值是否合法，请填空 else printf("The Element %d is Successfully Inserted!\n", x); break; case 2: scanf("%d",&i); if(!ListDelete_Sq(T,i,e)) printf("Delete Error!\n"); // 判断i值是否合法，请填空 else printf("The Element %d is Successfully Deleted!\n", e); break; case 3: Load_Sq(T); break; case 0: return 1; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
#include<stdio.h> #include<malloc.h> #define OK 1 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemType int typedef struct { int *elem; int length; int listsize; }SqList; int InitList_Sq(SqList &L) { // 算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE L.elem=new ElemType[LIST_INIT_SIZE]; if(!L.elem) { return ERROR; } L.length=0; return OK; } int Load_Sq(SqList &L) { // 输出顺序表中的所有元素 if(L.length==0) printf("The List is empty!"); // 请填空 else { printf("The List is: "); for(int i=1;i<=L.length;i++) printf("%d ",L.elem[i]); // 请填空 } printf("\n"); return OK; } int ListInsert_Sq(SqList &L,int i,int e) { // 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e // i的合法值为1≤i≤L.length +1 if(i<1||i>L.length+1||L.length==LIST_INIT_SIZE) { return ERROR; } /*搬动元素*/ for(int k=L.length+1;k>=i;k--) { L.elem[k]=L.elem[k-1]; } L.length++; L.elem[i]=e; return OK; } int ListDelete_Sq(SqList &L,int i, int &e) { // 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值 // i的合法值为1≤i≤L.length if(i<1||i>L.length) { return ERROR; } e=L.elem[i]; for(int k=i;k<L.length;k++) { L.elem[k]=L.elem[k+1]; } L.length--; return OK; } int main() { SqList T; int a, i; ElemType e, x; if(InitList_Sq(T)) // 判断顺序表是否创建成功 { printf("A Sequence List Has Created.\n"); } while(1) { printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a) { case 1: scanf("%d%d",&i,&x); if(!ListInsert_Sq(T,i,x)) printf("Insert Error!\n"); // 判断i值是否合法，请填空 else printf("The Element %d is Successfully Inserted!\n", x); break; case 2: scanf("%d",&i); if(!ListDelete_Sq(T,i,e)) printf("Delete Error!\n"); // 判断i值是否合法，请填空 else printf("The Element %d is Successfully Deleted!\n", e); break; case 3: Load_Sq(T); break; case 0: return 1; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
关键是插入和删除函数的编写，这两个函数的编写易错点在于容易溢出，考虑的话就是把边界值下标带入就可以了，为了加强对这道题的印象的话，编写两种算法，这两种的下标对应是不一样的，据此可以加强记忆。
题2：8577 合并顺序表
题目描述
Description
若线性表中数据元素相互之间可以比较，且数据元素在表中按值递增或递减，则称该表为有序表。
编写算法，将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序表C。
输入格式
第一行：顺序表A的元素个数
第二行：顺序表A的各元素（非递减），用空格分开
第三行：顺序表B的元素个数
第四行：顺序表B的各元素（非递减），用空格分开
输出格式
第一行：顺序表A的元素列表
第二行：顺序表B的元素列表
第三行：合并后顺序表C的元素列表
输入样例
5
1 3 5 7 9
5
2 4 6 8 10
输出样例
List A:1 3 5 7 9
List B:2 4 6 8 10
List C:1 2 3 4 5 6 7 8 9 10
提示
输出时注意大小写和标点。
作者 yqm
AC代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(false); int n,m; cin>>n; int *a=new int[n+5]; for(int i=1;i<=n;i++) { cin>>a[i]; } cin>>m; int *b=new int[m+5]; for(int i=1;i<=m;i++) { cin>>b[i]; } int *c=new int[n+m+10]; int i=1,j=1,k=1; while(i<=n&&j<=m) { if(a[i]<=b[j]) { c[k++]=a[i++]; } else { c[k++]=b[j++]; } } while(i<=n) { c[k++]=a[i++]; } while(j<=m) { c[k++]=b[j++]; } cout<<"List A:"; for(int i=1;i<=n;i++) { cout<<a[i]<<" "; } cout<<endl; cout<<"List B:"; for(int i=1;i<=m;i++) { cout<<b[i]<<" "; } cout<<endl; int len=n+m; cout<<"List C:"; for(int i=1;i<=len;i++) { cout<<c[i]<<" "; } cout<<endl; delete(a);delete(b);delete(c); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
题3:8578 顺序表逆置
题目描述
额，这是怎么会事呢
AC代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(false); int n;cin>>n; int *a=new int[n+5]; for(int i=1;i<=n;i++) { cin>>a[i]; } cout<<"The List is:"; for(int i=1;i<=n;i++) { cout<<a[i]<<" "; } cout<<endl<<"The turned List is:"; for(int i=n;i>=1;i--) { cout<<a[i]<<" "; } cout<<endl; delete(a); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
题4:8579 链式线性表的基本操作
题目描述
Description 编写算法，创建一个含有n个元素的带头结点的单链表L并实现插入、删除、遍历操作。本题目提供部分代码，请补全内容。
#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define ElemType int
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;
int CreateLink_L(LinkList &L,int n){
// 创建含有n个元素的单链表
LinkList p,q;
int i;
ElemType e;
L = new LNode;
L->next = NULL; // 先建立一个带头结点的单链表
q = new LNode;
q = L;
for (i=0; i<n; i++) {
scanf("%d", &e);
p = new LNode; // 生成新结点
// 请补全代码
}
return OK;
}
int LoadLink_L(LinkList &L){
// 单链表遍历
LinkList p = L->next;
if(___________________________)printf(“The List is empty!”); // 请填空
else
{
printf(“The LinkList is:”);
while(___________________________) // 请填空
{
printf("%d “,p->data);
___________________________ // 请填空
}
}
printf(”\n");
return OK;
}
int LinkInsert_L(LinkList &L,int i,ElemType e){
// 算法2.9
// 在带头结点的单链线性表L中第i个位置之前插入元素e
// 请补全代码
}
int LinkDelete_L(LinkList &L,int i, ElemType &e){
// 算法2.10
// 在带头结点的单链线性表L中，删除第i个元素，并用e返回其值
// 请补全代码
}
int main()
{
LinkList T;
int a,n,i;
ElemType x, e;
printf(“Please input the init size of the linklist:\n”);
scanf("%d",&n);
printf(“Please input the %d element of the linklist:\n”, n);
if(___________________________) // 判断链表是否创建成功，请填空
{
printf(“A Link List Has Created.\n”);
LoadLink_L(T);
}
while(1)
{
printf(“1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n”);
scanf("%d",&a);
switch(a)
{
case 1: scanf("%d%d",&i,&x);
if(___________________________) printf(“Insert Error!\n”); // 判断i值是否合法，请填空
else printf(“The Element %d is Successfully Inserted!\n”, x);
break;
case 2: scanf("%d",&i);
if(___________________________) printf(“Delete Error!\n”); // 判断i值是否合法，请填空
else printf(“The Element %d is Successfully Deleted!\n”, e);
break;
case 3: LoadLink_L(T);
break;
case 0: return 1;
}
}
}
AC代码
#include<stdio.h> #include<malloc.h> #define ERROR 0 #define OK 1 #define ElemType int typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList; int CreateLink_L(LinkList &L,int n){ // 创建含有n个元素的单链表 LinkList p,q; int i; ElemType e; L = new LNode; L->next = NULL; // 先建立一个带头结点的单链表 q = new LNode; q = L; for (i=0; i<n; i++) { scanf("%d", &e); p = new LNode; // 生成新结点 q->next=p; p->data=e; q=p; } q->next=NULL; return OK; } int LoadLink_L(LinkList &L){ // 单链表遍历 LinkList p = L->next; if(!p)printf("The List is empty!"); // 请填空 else { printf("The LinkList is:"); while(p) // 请填空 { printf("%d ",p->data); p=p->next; // 请填空 } } printf("\n"); return OK; } int LinkInsert_L(LinkList &L,int i,ElemType e){ // 算法2.9 // 在带头结点的单链线性表L中第i个位置之前插入元素e LinkList p=L,newnode=new LNode; for(int k=0;k<i-1;k++) { p=p->next; if(!p) { return ERROR; } } newnode->data=e; newnode->next=p->next; p->next=newnode; return OK; } int LinkDelete_L(LinkList &L,int i, ElemType &e){ // 算法2.10 // 在带头结点的单链线性表L中，删除第i个元素，并用e返回其值 LinkList p=L->next,pre=L; for(int k=1;k<i;k++) { pre=p; p=p->next; if(!p) { return ERROR; } } e=p->data; pre->next=p->next; p->next=NULL; free(p); return OK; } int main() { LinkList T; int a,n,i; ElemType x, e; printf("Please input the init size of the linklist:\n"); scanf("%d",&n); printf("Please input the %d element of the linklist:\n", n); if(CreateLink_L(T,n)) // 判断链表是否创建成功，请填空 { printf("A Link List Has Created.\n"); LoadLink_L(T); } while(1) { printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a) { case 1: scanf("%d%d",&i,&x); if(!LinkInsert_L(T,i,x)) printf("Insert Error!\n"); // 判断i值是否合法，请填空 else printf("The Element %d is Successfully Inserted!\n", x); break; case 2: scanf("%d",&i); if(!LinkDelete_L(T,i,e)) printf("Delete Error!\n"); // 判断i值是否合法，请填 else printf("The Element %d is Successfully Deleted!\n", e); break; case 3: LoadLink_L(T); break; case 0: return 1; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
题5:8580 合并链表
题目描述
设计一个算法将两个非递减有序链表A和B合并成一个新的非递减有序链表C。
输入格式
第一行：单链表A的元素个数
第二行：单链表A的各元素（非递减），用空格分开
第三行：单链表B的元素个数
第四行：单链表B的各元素（非递减），用空格分开
输出格式
第一行：单链表A的元素列表
第二行：单链表B的元素列表
第三行：合并后单链表C的元素列表
输入样例
6
12 24 45 62 84 96
4
15 31 75 86
输出样例
List A:12 24 45 62 84 96
List B:15 31 75 86
List C:12 15 24 31 45 62 75 84 86 96
AC代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(false); int n,m; cin>>n; int *a=new int[n+5]; for(int i=1;i<=n;i++) { cin>>a[i]; } cin>>m; int *b=new int[m+5]; for(int i=1;i<=m;i++) { cin>>b[i]; } int *c=new int[n+m+10]; int i=1,j=1,k=1; while(i<=n&&j<=m) { if(a[i]<=b[j]) { c[k++]=a[i++]; } else { c[k++]=b[j++]; } } while(i<=n) { c[k++]=a[i++]; } while(j<=m) { c[k++]=b[j++]; } cout<<"List A:"; for(int i=1;i<=n;i++) { cout<<a[i]<<" "; } cout<<endl; cout<<"List B:"; for(int i=1;i<=m;i++) { cout<<b[i]<<" "; } cout<<endl; int len=n+m; cout<<"List C:"; for(int i=1;i<=len;i++) { cout<<c[i]<<" "; } cout<<endl; delete(a);delete(b);delete(c); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
不会真的有人会去写链表吧，不会吧（思路就是归并，不同的是 是用指针进行遍历归并，大量重复的工作就不做了。）
题6:8581 线性链表逆置
这道题比较有价值，对于编程思路有较好的训练
题目描述
输入格式
第一行：输入n，表示单链表的元素个数
第二行：输入单链表的各元素，用空格分开
输出格式
第一行：输出单链表逆置前的元素列表
第二行：输出单链表逆置后的元素列表
输入样例
8
32 97 54 65 35 84 61 75
输出样例
The List is:32 97 54 65 35 84 61 75
The turned List is:75 61 84 35 65 54 97 32
AC代码
#include<stdio.h> #include<malloc.h> #define ERROR 0 #define OK 1 #define ElemType int typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList; int CreateLink_L(LinkList &L,int n){ // 创建含有n个元素的单链表 LinkList p,q; int i; ElemType e; L = new LNode; L->next = NULL; // 先建立一个带头结点的单链表 q = L; for (i=0; i<n; i++) { scanf("%d", &e); p = new LNode; // 生成新结点 p->data=e; q->next=p; q=p; } q->next=NULL; return OK; } void Reserve(LinkList &T) { LNode *Cur,*Pre,*Next; /*init*/ Pre=T;Cur=T->next;Next=Cur->next; Cur->next=NULL; while(Next) { Pre=Cur; Cur=Next; Next=Next->next; Cur->next=Pre; } T->next=Cur; return ; } void ShowAns(LinkList &L) { LNode *p=L->next; while(p) { printf("%d ",p->data); p=p->next; } printf("\n"); return ; } int main() { LinkList T; int n; scanf("%d",&n); CreateLink_L(T,n); LNode *p=T; p=p->next; if(!p->next)/*单节点情形*/ { printf("The List is:"); ShowAns(T); printf("The turned List is:"); ShowAns(T); return 0;/*exit*/ } /*双结点及其以上*/ printf("The List is:"); ShowAns(T); Reserve(T); printf("The turned List is:"); ShowAns(T); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
题1:8583 顺序栈的基本操作
题目描述
Description 创建一个空的顺序栈，并实现栈的入栈、出栈、返回栈的长度、返回栈顶元素、栈的遍历等基本算法。请将下面的程序补充完整。
输入格式
测试样例格式说明：
根据菜单操作：
1、输入1，表示要实现Push操作，紧跟着输入要Push的元素
2、输入2，表示要实现Pop操作
3、输入3，返回栈顶元素
4、输入4，返回栈的元素个数
5、输入5，表示从栈顶到栈底输出栈的所有元素
6、输入0，表示程序结束
AC代码
#include<malloc.h> #include<stdio.h> #define OK 1 #define ERROR 0 #define STACK_INIT_SIZE 100 // 存储空间初始分配量 #define STACKINCREMENT 10 // 存储空间分配增量 typedef int SElemType; // 定义栈元素类型 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 struct SqStack { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }; // 顺序栈 Status InitStack(SqStack &S) { // 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE S.base=new SElemType[STACK_INIT_SIZE]; if(!S.base) { return ERROR; } S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } Status Push(SqStack &S,SElemType e) { // 在栈S中插入元素e为新的栈顶元素 if(S.top-S.base==STACK_INIT_SIZE) { return ERROR; } *S.top=e; S.top++; return OK; } Status Pop(SqStack &S,SElemType &e) { // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(S.base==S.top) { return ERROR; } e=*(S.top-1); S.top--; return OK; } Status GetTop(SqStack S,SElemType &e) { // 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(S.base==S.top) { return ERROR; } e=*(S.top-1); return OK; } int StackLength(SqStack S) { // 返回栈S的元素个数 return S.top-S.base; } Status StackTraverse(SqStack S) { // 从栈顶到栈底依次输出栈中的每个元素 SElemType *p =S.top; if(S.base==S.top)printf("The Stack is Empty!"); //请填空 else { printf("The Stack is: "); while(p!=S.base) //请填空 { p--; printf("%d ", *p); } } printf("\n"); return OK; } int main() { int a; SqStack S; SElemType x, e; if(InitStack(S)) // 判断顺序表是否创建成功，请填空 { printf("A Stack Has Created.\n"); } while(1) { printf("1:Push \n2:Pop \n3:Get the Top \n4:Return the Length of the Stack\n5:Load the Stack\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a) { case 1: scanf("%d", &x); if(!Push(S,x)) printf("Push Error!\n"); // 判断Push是否合法，请填空 else printf("The Element %d is Successfully Pushed!\n", x); break; case 2: if(!Pop(S,e)) printf("Pop Error!\n"); // 判断Pop是否合法，请填空 else printf("The Element %d is Successfully Poped!\n", e); break; case 3: if(!GetTop(S,e))printf("Get Top Error!\n"); // 判断Get Top是否合法，请填空 else printf("The Top Element is %d!\n", e); break; case 4: printf("The Length of the Stack is %d!\n",StackLength(S)); //请填空 break; case 5:StackTraverse(S); break; case 0: return 1; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
题2:8584 循环队列的基本操作
题目描述
Description 创建一个空的循环队列，并实现入队、出队、返回队列的长度、返回队头元素、队列的遍历等基本算法。请将下面的程序补充完整。
输入格式
测试样例格式说明：
根据菜单操作：
1、输入1，表示要实现入队操作，紧跟着输入要入队的元素
2、输入2，表示要实现出队操作
3、输入3，返回队头元素
4、输入4，返回队列的元素个数
5、输入5，表示从队头到队尾输出队的所有元素
6、输入0，表示程序结束
输入样例
1
1
1
2
1
3
5
2
3
5
0
AC代码
#include<malloc.h> #include<stdio.h> #define OK 1 #define ERROR 0 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int QElemType; #define MAXQSIZE 100 // 最大队列长度(对于循环队列，最大队列长度要减1) using namespace std; typedef struct { QElemType *base; // 初始化的动态分配存储空间 int head; // 头指针,若队列不空,指向队列头元素 int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置 }SqQueue; Status InitQueue(SqQueue &Q) { // 构造一个空队列Q，该队列预定义大小为MAXQSIZE Q.base=new QElemType[MAXQSIZE]; if(!Q.base) { return ERROR; } Q.head=Q.rear=0; return OK; } Status EnQueue(SqQueue &Q,QElemType e) { // 插入元素e为Q的新的队尾元素,如果队伍满了怎么办 if((Q.rear+1)%MAXQSIZE==Q.head) { return ERROR; } Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; } Status DeQueue(SqQueue &Q, QElemType &e) { // 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR if(Q.head==Q.rear) { return ERROR; } e=Q.base[Q.head]; Q.head=(Q.head+1)%MAXQSIZE; return OK; } Status GetHead(SqQueue Q, QElemType &e) { // 若队列不空，则用e返回队头元素，并返回OK，否则返回ERROR if(Q.head==Q.rear) { return ERROR; } e=Q.base[Q.head]; return OK; } int QueueLength(SqQueue Q) { // 返回Q的元素个数 return (Q.rear-Q.head+MAXQSIZE)%MAXQSIZE; } Status QueueTraverse(SqQueue Q) { // 若队列不空，则从队头到队尾依次输出各个队列元素，并返回OK；否则返回ERROR. int i; i=Q.head; if(Q.head==Q.rear)printf("The Queue is Empty!"); //请填空 else{ printf("The Queue is: "); while(i!=Q.rear) //请填空 { printf("%d ",Q.base[i]); //请填空 i =(i+1)%MAXQSIZE; //请填空 } } printf("\n"); return OK; } int main() { int a; SqQueue S; QElemType x, e; if(InitQueue(S)) // 判断顺序表是否创建成功，请填空 { printf("A Queue Has Created.\n"); } while(1) { printf("1:Enter \n2:Delete \n3:Get the Front \n4:Return the Length of the Queue\n5:Load the Queue\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a) { case 1: scanf("%d", &x); if(!EnQueue(S,x)) printf("Enter Error!\n"); // 判断入队是否合法，请填空 else printf("The Element %d is Successfully Entered!\n", x); break; case 2: if(!DeQueue(S,e)) printf("Delete Error!\n"); // 判断出队是否合法，请填空 else printf("The Element %d is Successfully Deleted!\n", e); break; case 3: if(!GetHead(S,e))printf("Get Head Error!\n"); // 判断Get Head是否合法，请填空 else printf("The Head of the Queue is %d!\n", e); break; case 4: printf("The Length of the Queue is %d!\n",QueueLength(S)); //请填空 break; case 5: QueueTraverse(S) ;//请填空 break; case 0: return 1; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
主要是要理解取余和循环之间的关系。
题3:8585 栈的应用——进制转换
水题
AC代码
#include <iostream> #include <cstring> #include <algorithm> #include <stack> using namespace std; stack <long long >s; void tranf(long long n) { while(n) { s.push(n%8); n/=8; } while(!s.empty()) { cout<<s.top(); s.pop(); } } int main() { ios::sync_with_stdio(false); long long n;cin>>n; tranf(n); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
题4: 8586 括号匹配检验
题目描述
时间限制:1000MS 代码长度限制:10KB
提交次数:4447 通过次数:1864
题型: 编程题 语言: G++;GCC
Description 利用栈编写满足下列要求的括号匹配检验程序：假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即()或[([][])]等为正确的格式，[(]或([())或(()])均为不正确的格式。输入一个包含上述括号的表达式，检验括号是否配对。本题给出部分check()函数，要求将check()函数补充完整，并完成整个程序。
typedef char SElemType;
#include"malloc.h"
#include"stdio.h"
#include"math.h"
#include"stdlib.h" // exit()
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACKINCREMENT 2 // 存储空间分配增量
struct SqStack
{
SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}; // 顺序栈
Status InitStack(SqStack &S)
{
}
Status StackEmpty(SqStack S)
{
}
Status Push(SqStack &S,SElemType e)
{
}
Status Pop(SqStack &S,SElemType &e)
{
}
void check()
{ // 对于输入的任意一个字符串，检验括号是否配对
SqStack s;
SElemType ch[80],p,e;
if(InitStack(s)) // 初始化栈成功
{
//printf(“请输入表达式\n”);
_____________________;
p=ch;
while(*p) // 没到串尾
switch(*p)
{
case ‘(’:
case ‘[’:_______________________;
break; // 左括号入栈，且p++
case ‘)’:
case ‘]’:if(!StackEmpty(s)) // 栈不空
{
; // 弹出栈顶元素
if(*p==’)’&&e!=’(’||&&)
// 弹出的栈顶元素与p不配对
{
printf(“isn’t matched pairs\n”);
exit(ERROR);
}
else
{
__________________________;
break; // 跳出switch语句
}
}
else // 栈空
{
printf(“lack of left parenthesis\n”);
exit(ERROR);
}
default: ______________________; // 其它字符不处理，指针向后移
}
if(StackEmpty(s)) // 字符串结束时栈空
printf(“matching\n”);
else
printf(“lack of right parenthesis\n”);
}
}
int main()
{
check();
}
输入格式
第一行：输入一个包含圆括号或方括号、不超过80个字符的表达式串。
输出格式
第一行：若输入表达式括号匹配，输出"matching"; 若不匹配，输出具体信息:“isn’t matched pairs”, 或"lack of left parenthesis"或"lack of right parenthesis"
输入样例
8*[3*(35-23)]
输出样例
matching
作者 yqm
AC代码
typedef char SElemType; #include"malloc.h" #include"stdio.h" #include"math.h" #include"stdlib.h" // exit() #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 struct SqStack { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }; // 顺序栈 Status InitStack(SqStack &S) { S.base=new SElemType[STACK_INIT_SIZE]; if(!S.base) { return ERROR; } S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } Status StackEmpty(SqStack S) { if(S.top==S.base) { return TRUE; } else { return FALSE; } } Status Push(SqStack &S,SElemType e) { /*入栈操作，要保证栈不为满*/ if(S.top-S.base==S.stacksize) { return ERROR; } else { *S.top=e; S.top++; return OK; } } Status Pop(SqStack &S,SElemType &e) { /*出栈操作，要保证栈不为空*/ if(S.top==S.base) { return ERROR; } else { S.top--; e=*S.top; return OK; } } void check() { // 对于输入的任意一个字符串，检验括号是否配对 SqStack s; SElemType ch[80],*p,e; if(InitStack(s)) // 初始化栈成功 { //printf("请输入表达式\n"); gets(ch); p=ch; while(*p) // 没到串尾 switch(*p) { case '(': case '[':Push(s,*p++); break; // 左括号入栈，且p++ case ')': case ']':if(!StackEmpty(s)) // 栈不空 { Pop(s,e); // 弹出栈顶元素 if(*p==')'&&e!='('||*p==']'&&e!='[') // 弹出的栈顶元素与*p不配对 { printf("isn't matched pairs\n"); exit(ERROR); } else { p++; break; // 跳出switch语句 } } else // 栈空 { printf("lack of left parenthesis\n"); exit(ERROR); } default: p++; // 其它字符不处理，指针向后移 } if(StackEmpty(s)) // 字符串结束时栈空 printf("matching\n"); else printf("lack of right parenthesis\n"); } } int main() { check(); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
自己即兴写的 写的不好
#include <iostream> #include <cstring> #include <stack> using namespace std; const int M=1e5+5; stack <char> s; char a[M]; int main() { ios::sync_with_stdio(false); cin>>a;int len=strlen(a); for(int i=0;i<len;i++) { if(a[i]=='('||a[i]=='[') { s.push(a[i]); } else if(a[i]==')') { if(!s.empty() && s.top()=='(') { s.pop(); } else if(!s.empty() && s.top()!='(') { cout<<"isn't matched pairs"; return 0; } else if(s.empty()) { cout<<"lack of left parenthesis"; return 0; } } else if(a[i]==']') { if(!s.empty() && s.top()=='[') { s.pop(); } else if(!s.empty() && s.top()!='[') { cout<<"isn't matched pairs"; return 0; } else if(s.empty()) { cout<<"lack of left parenthesis"; return 0; } } } if(!s.empty()) { if(s.top()==')'||s.top()==']') { cout<<"lack of left parenthesis"; return 0; } else if(s.top()=='['||s.top()=='(') { cout<<"lack of right parenthesis"; return 0; } } cout<<"matching"; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
题5:8587 行编辑程序
题目描述
Description 利用栈编写简单的行编辑程序：接受用户从终端输入的程序或数据，在输入过程中，允许用户输入出差错，并在发现有误时可以及时更正。例如：当用户发现刚刚键入的一个字符是错的时，可以补进一个退格符“#”，以表示前一个字符无效；如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符“@”，以表示当前行中的字符均无效。例如：假设从终端接受了这样两行字符： whli##ilr#e (s#*s) outcha@putchar(*s=#++); 则实际有效的是下列两行： while (*s) putchar(*s++); 本题目给出部分函数，要求将行编辑函数补充完整，并完成整个程序。
typedef char SElemType;
#include"malloc.h"
#include"stdio.h"
#include"math.h"
#include"stdlib.h" // exit()
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACKINCREMENT 2 // 存储空间分配增量
struct SqStack
{
SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}; // 顺序栈
Status InitStack(SqStack &S)
{ // 构造一个空栈S
}
Status StackEmpty(SqStack S)
{ // 若栈S为空栈，则返回TRUE，否则返回FALSE
}
Status ClearStack(SqStack &S)
{ // 把S置为空栈
S.top=S.base;
return OK;
}
Status DestroyStack(SqStack &S)
{ // 销毁栈S，S不再存在
free(S.base);
S.base=NULL;
S.top=NULL;
S.stacksize=0;
return OK;
}
Status Push(SqStack &S,SElemType e)
{ // 插入元素e为新的栈顶元素
}
Status Pop(SqStack &S,SElemType &e)
{ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
}
Status StackTraverse(SqStack S,Status(*visit)(SElemType))
{ // 从栈底到栈顶依次对栈中每个元素调用函数visit()。
// 一旦visit()失败，则操作失败
while(S.top>S.base)
visit(*S.base++);
printf("\n");
return OK;
}
Status visit(SElemType c)
{
printf("%c",c);
return OK;
}
void LineEdit()
{ // 利用字符栈s，从终端接收一行并送至调用过程的数据区。算法3.2
SqStack s;
char ch,c;
int n,i;
InitStack(s);
scanf("%d",&n);
ch=getchar();
for(i=1;i<=n;i++)
{ ch=;
while(ch!=’\n’)
{
switch()
{
case ‘#’:Pop(s,c);
break; // 仅当栈非空时退栈
case ‘@’:ClearStack(s);
break; // 重置s为空栈
default :_______________________; // 有效字符进栈
}
____________________________; // 从终端接收下一个字符
}
StackTraverse(s,visit); // 将从栈底到栈顶的栈内字符输出
_____________________________________; // 重置s为空栈
}
DestroyStack(s);
}
void main()
{
LineEdit();
}
输入格式
第一行：第一个字符为输入文本的行数n;
第二行至第n行：每行均为一串字符，其间可以含有“#”和“@”符号，以回车键结束本行的输入；
输出格式
输出第一至第n行的内容如下：
第一行：第一行从终端输入的有效字符。
第二行：第二行从终端输入的有效字符。
…… ……
第n行：第n行从终端输入的有效字符。
输入样例
2
defne##ine OK 1
typp cila@type int element
输出样例
define OK 1
type int element
AC代码
typedef char SElemType; #include"malloc.h" #include"stdio.h" #include"math.h" #include"stdlib.h" // exit() #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 struct SqStack { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }; // 顺序栈 Status InitStack(SqStack &S) { S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) { return ERROR; } else { S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } } Status StackEmpty(SqStack S) { // 若栈S为空栈，则返回TRUE，否则返回FALSE if(S.base==S.top) { return TRUE; } else { return FALSE; } } Status ClearStack(SqStack &S) { // 把S置为空栈 S.top=S.base; return OK; } Status DestroyStack(SqStack &S) { // 销毁栈S，S不再存在 free(S.base); S.base=NULL; S.top=NULL; S.stacksize=0; return OK; } Status Push(SqStack &S,SElemType e) { // 插入元素e为新的栈顶元素 /*入栈则栈不为满*/ if(S.top-S.base>=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));/*关键语句*/ if(!S.base) { return ERROR; } S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *(S.top)=e; S.top++; return OK; } Status Pop(SqStack &S,SElemType &e) { // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(S.top==S.base) { return ERROR; } else { --S.top; e=*(S.top); return OK; } } Status StackTraverse(SqStack S,Status(*visit)(SElemType))//传入函数类型的参数 { // 从栈底到栈顶依次对栈中每个元素调用函数visit()。 // 一旦visit()失败，则操作失败 while(S.top>S.base) visit(*S.base++); printf("\n"); return OK; } Status visit(SElemType c) { printf("%c",c); return OK; } void LineEdit() { // 利用字符栈s，从终端接收一行并送至调用过程的数据区。算法3.2 SqStack s; char ch,c; int n,i; InitStack(s); scanf("%d",&n); ch=getchar(); for(i=1;i<=n;i++) { ch=getchar(); while(ch!='\n') { switch(ch) { case '#':Pop(s,c); break; // 仅当栈非空时退栈 case '@':ClearStack(s); break; // 重置s为空栈 default :Push(s,ch); // 有效字符进栈 } ch=getchar(); // 从终端接收下一个字符 } StackTraverse(s,visit); // 将从栈底到栈顶的栈内字符输出 ClearStack(s); // 重置s为空栈 } DestroyStack(s); } int main() { LineEdit(); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
原始代码就比较简单，就不自己写了。
题6：18937 阿克曼(Ackmann)函数
AC代码
#include <iostream> #include <cstdio> using namespace std; int ackman(int m,int n) { if(m==0) { return n+1; } if(m>0&&n==0) { return ackman(m-1,1); } if(m>0 && n>0) { return ackman(m-1,ackman(m,n-1)); } } int main() { ios::sync_with_stdio(false);/*关闭同步流*/ int n,m; cin>>n>>m; int ans=ackman(n,m); cout<<ans; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
题1:8591 计算next值
题目描述
Description 编写算法，录入多个字符串计算并验证NEXT值，输入0结束。本题目给出部分代码，请补全内容。]
#include “stdio.h”
#include “stdlib.h”
#include “iostream.h”
#define MAXSTRLEN 255 // 用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1]; // 0号单元存放串的长度
void get_next(SString T,int next[]){
// 算法4.7
// 求模式串T的next函数值并存入数组next
// 请补全代码
}
void main(){
int next[MAXSTRLEN];
SString S;
int n,i,j;
char ch;
scanf("%d",&n); // 指定要验证NEXT值的字符串个数
ch=getchar();
for(i=1;i<=n;i++)
{
ch=getchar();
for(j=1;j<=MAXSTRLEN&&(ch!=’\n’);j++) // 录入字符串
{
S[j]=ch;
ch=getchar();
}
S[0]=j-1; // S[0]用于存储字符串中字符个数
get_next(S,next);
printf(“NEXT J is:”);
for(j=1;j<=S[0];j++)
printf("%d",next[j]);
printf("\n");
}
}
输入格式
第一行：输入n，表示有n个需计算NEXT值的字符串
第二至n+1行：每行输入一个字符串
输出格式
第1至第n行：通过计算每相应行的字符串得出的NEXT值
输入样例
4
abcdefg
aaaaab
abaabcac
aaabaaab
输出样例
NEXT J is:0111111
NEXT J is:012345
NEXT J is:01122312
NEXT J is:01231234
作者 yqm
解题思路
KMP算法的难度较大，建议的是看视频动画理解算法过程
AC代码
#include "stdio.h" #include "stdlib.h" #include <iostream> #define MAXSTRLEN 255 // 用户可在255以内定义最大串长 typedef unsigned char SString[MAXSTRLEN+1]; // 0号单元存放串的长度 void get_next(SString T,int next[]) { // 算法4.7 // 求模式串T的next函数值并存入数组next //初始化指针 int i=1,j=0; next[i]=0;/*next的第一位总是为0*/ while(i<T[0])/*当i指针未指向模式串的末尾时*/ { if(j==0||T[i]==T[j]) { i++,j++; next[i]=j;/*模式串i位置预处理的位置是j*/ } else { j=next[j];/*相当于一次回溯*/ /*为什么是这样回溯？*/ /*需要注意的是:i的位置始终没有改变，因此这是一个扫描整个字符串的指针*/ /*而在每一次的匹配过程中，都会记录下当前与之匹配的最大前缀的位置(是先自增后再得到的)*/ /*当不匹配的时候,j就需要回到上一次开始的地方，开始新一轮的模式字符串匹配*/ } } } int main() { int next[MAXSTRLEN]; SString S; int n,i,j; char ch; scanf("%d",&n); // 指定要验证NEXT值的字符串个数 ch=getchar(); for(i=1; i<=n; i++) { ch=getchar(); for(j=1; j<=MAXSTRLEN&&(ch!='\n'); j++) // 录入字符串 { S[j]=ch; ch=getchar(); } S[0]=j-1; // S[0]用于存储字符串中字符个数 get_next(S,next); printf("NEXT J is:"); for(j=1; j<=S[0]; j++) printf("%d",next[j]); printf("\n"); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
题2:8592 KMP算法
题目描述
Description 用KMP算法对主串和模式串进行模式匹配。本题目给出部分代码，请补全内容。
#include “stdio.h”
#include “stdlib.h”
#include “iostream.h”
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASLBLE -1
#define OVERFLOW -2
#define MAXSTRLEN 255 //用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度
void get_next(SString T,int next[]){
// 算法4.7
// 求模式串T的next函数值并存入数组next
// 请补全代码
}
int Index_KMP(SString S,SString T,int pos){
// 算法4.6
// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置
// KMP算法。请补全代码
}
void main()
{
SString T,S;
int i,j,n;
char ch;
int pos;
scanf(“%d”,&n); // 指定n对需进行模式匹配的字符串
ch=getchar();
for(j=1;j<=n;j++)
{
ch=getchar();
for( i=1;i<=MAXSTRLEN&&(ch!=’\n’);i++) // 录入主串
{
S[i]=ch;
ch=getchar();
}
S[0]=i-1; // S[0]用于存储主串中字符个数
ch=getchar();
for( i=1;i<=MAXSTRLEN&&(ch!=’\n’);i++) // 录入模式串
{
T[i]=ch;
ch=getchar();
}
T[0]=i-1; // T[0]用于存储模式串中字符个数
pos= ; // 请填空
printf("%d\n",pos);
}
}
输入格式
第一行：输入n，表示有n对字符串需要匹配
第二行：输入第1个主串
第三行：输入第1个模式串
第四行：输入第2个主串
第五行：输入第2个模式串
……
倒数二行：输入第n个主串
最后一行：输入第n个模式串
输出格式
第一至第n行：输出每相应模式串的匹配值
输入样例
4
oadhifgoarhglkdsa
oar
abcdefg
dec
algeojflas
ojf
jfaweiof
of
输出样例
8
0
5
7
作者 yqm
AC代码
#include "stdio.h" #include "stdlib.h" #include <iostream> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASLBLE -1 #define OVERFLOW -2 #define MAXSTRLEN 255 //用户可在255以内定义最大串长 typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度 void get_next(SString T,int next[]) { // 算法4.7 // 求模式串T的next函数值并存入数组next /*初始化指针*/ int i=1,j=0; next[i]=0; while(i<T[0]) { if(j==0||T[i]==T[j]) { i++,j++; next[i]=j; } else { j=next[j]; } } } int Index_KMP(SString S,SString T,int pos) { // 算法4.6 // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置 int i=pos,j=1; int next[MAXSTRLEN]={0}; get_next(T,next); while(i<=S[0]&&j<=T[0]) { if(j==0||S[i]==T[j]) { i++; j++; } else { j=next[j]; } } if(j>T[0])/*这是一个边界的检查*/ { return i-T[0]; } else { return 0; } } int main() { SString T,S; int i,j,n; char ch; int pos; scanf("%d",&n); // 指定n对需进行模式匹配的字符串 ch=getchar(); for(j=1; j<=n; j++) { ch=getchar(); for( i=1; i<=MAXSTRLEN&&(ch!='\n'); i++) // 录入主串 { S[i]=ch; ch=getchar(); } S[0]=i-1; // S[0]用于存储主串中字符个数 ch=getchar(); for( i=1; i<=MAXSTRLEN&&(ch!='\n'); i++) // 录入模式串 { T[i]=ch; ch=getchar(); } T[0]=i-1; // T[0]用于存储模式串中字符个数 pos=Index_KMP(S,T,1); ; // 请填空 printf("%d\n",pos); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
