2022SCAU数据结构题库汇总（最简单最详细）

预习即复习，陪你们到最后一刻实验1.1 8576 顺序线性表的基本操作

时间限制:1000MS 代码长度限制:10KB
提交次数:9027 通过次数:2456

题型: 编程题语言: G++;GCC

Description

编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。本题目给出部分代码，请补全内容。

#include
#include
#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 elementn2:Delete elementn3:Load all elementsn0:ExitnPlease 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;
		}
	}
}

输入格式

测试样例格式说明：
根据菜单操作：
1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开
2、输入2，表示要实现删除操作，紧跟着要输入删除的位置
3、输入3，表示要输出顺序表的所有元素
4、输入0，表示程序结束

输入样例

输出样例

A Sequence List Has Created.
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 2 is Successfully Inserted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 3 is Successfully Inserted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 3 is Successfully Deleted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The List is: 2 
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:

#include
#include
#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)
{
    L.elem=new ElemType[LIST_INIT_SIZE];
    if(!L.elem)return ERROR;
    L.length=0;
    return OK;
// 算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE
// 请补全代码

}

int Load_Sq(SqList &L)
{
// 输出顺序表中的所有元素
	int i;
	if(L.length==0) printf("The List is empty!");  // 请填空
	else
	{
		printf("The List is: ");
		for(i=0;iL.length+1)return ERROR;
    if(L.length==LIST_INIT_SIZE) return ERROR;
    for(int j=L.length-1;j>=i-1;j--)
    {
        L.elem[j+1]=L.elem[j];
    }
    L.elem[i-1]=e;
    L.length++;
    return OK;
// 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e
// i的合法值为1≤i≤L.length +1
// 请补全代码

}

int ListDelete_Sq(SqList &L,int i, int &e)
{
    if(i<1||i>L.length)return ERROR;
    e=L.elem[i-1];
    for(int j=i;j<=L.length-1;j++)
    {
        L.elem[j-1]=L.elem[j];
    }
    L.length--;
    return e;
// 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值
// i的合法值为1≤i≤L.length
// 请补全代码

}

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 elementn2:Delete elementn3:Load all elementsn0:ExitnPlease choose:n");
		scanf("%d",&a);
		switch(a)
		{
			case 1: scanf("%d%d",&i,&x);
					if(ListInsert_Sq(T,i,x)==ERROR) 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)==ERROR) 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 8577 合并顺序表

时间限制:1000MS 代码长度限制:10KB
提交次数:5339 通过次数:2251

题型: 编程题语言: G++

Description

若线性表中数据元素相互之间可以比较，且数据元素在表中按值递增或递减，则称该表为有序表。

编写算法，将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序表C。

输入格式

第一行：顺序表A的元素个数
第二行：顺序表A的各元素（非递减），用空格分开
第三行：顺序表B的元素个数
第四行：顺序表B的各元素（非递减），用空格分开

输出格式

第一行：顺序表A的元素列表
第二行：顺序表B的元素列表
第三行：合并后顺序表C的元素列表

输入样例

输出样例

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

提示

输出时注意大小写和标点。

#include 
#include 

using namespace std;

int main()
{
    int a[105]={0},i,len1=0,len2=0;
    cin>>len1;              //输入两个顺序表
    for(i=1;i<=len1;i++)
        cin>>a[i];
    cin>>len2;
    for(i=len1+1;i<=len1+len2;i++)//len1+len2就是a数组的总长度
        cin>>a[i];

    cout<<"List A:";        //输出两个顺序表
    for(i=1;i<=len1;i++)
        cout<

实验1.3 8578 顺序表逆置

时间限制:1000MS 代码长度限制:10KB
提交次数:3660 通过次数:2149

题型: 编程题语言: G++;GCC

Description

顺序表的基本操作代码如下：
#include
#include
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int

typedef int Status;
typedef struct
{
    int *elem;
    int length;
    int listsize;
}SqList;

Status InitList_Sq(SqList &L) 
{  // 算法2.3
  // 构造一个空的线性表L。
  L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
  if (!L.elem) return OK;        // 存储分配失败
  L.length = 0;                  // 空表长度为0
  L.listsize = LIST_INIT_SIZE;   // 初始存储容量
  return OK;
} // InitList_Sq

Status ListInsert_Sq(SqList &L, int i, ElemType e) 
{  // 算法2.4
  // 在顺序线性表L的第i个元素之前插入新的元素e，
  // i的合法值为1≤i≤ListLength_Sq(L)+1
  ElemType *p;
  if (i < 1 || i > L.length+1) return ERROR;  // i值不合法
  if (L.length >= L.listsize) {   // 当前存储空间已满，增加容量
    ElemType *newbase = (ElemType *)realloc(L.elem,
                  (L.listsize+LISTINCREMENT)*sizeof (ElemType));
    if (!newbase) return ERROR;   // 存储分配失败
    L.elem = newbase;             // 新基址
    L.listsize += LISTINCREMENT;  // 增加存储容量
  }
  ElemType *q = &(L.elem[i-1]);   // q为插入位置
  for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;
                                  // 插入位置及之后的元素右移
  *q = e;       // 插入e
  ++L.length;   // 表长增1
  return OK;
} // ListInsert_Sq

Status ListDelete_Sq(SqList &L, int i, ElemType &e) 
{  // 算法2.5
  // 在顺序线性表L中删除第i个元素，并用e返回其值。
  // i的合法值为1≤i≤ListLength_Sq(L)。
  ElemType *p, *q;
  if (i<1 || i>L.length) return ERROR;  // i值不合法
  p = &(L.elem[i-1]);                   // p为被删除元素的位置
  e = *p;                               // 被删除元素的值赋给e
  q = L.elem+L.length-1;                // 表尾元素的位置
  for (++p; p<=q; ++p) *(p-1) = *p;     // 被删除元素之后的元素左移
  --L.length;                           // 表长减1
  return OK;
} // ListDelete_Sq

设有一顺序表A=（a0,a1,..., ai,...an-1)，其逆顺序表定义为A'=( an-1,..., ai,...,a1, a0)。设计一个算法，将顺序表逆置，要求顺序表仍占用原顺序表的空间。

输入格式

第一行：输入顺序表的元素个数
第二行：输入顺序表的各元素，用空格分开

输出格式

第一行：逆置前的顺序表元素列表
第二行：逆置后的顺序表元素列表

输入样例

10
1 2 3 4 5 6 7 8 9 10

输出样例

The List is:1 2 3 4 5 6 7 8 9 10 
The turned List is:10 9 8 7 6 5 4 3 2 1

#include 
#include 
int main()
{
    int i,t,n;
    scanf("%d",&n);
    int a[n];
    for(i=1;i<=n;i++)
    {
    scanf("%d",&a[i]);
    }
    printf("The List is:");
    for(i=1;i<=n;i++)
    {
    printf("%d ",a[i]);
    }
    printf("n");
    printf("The turned List is:");
    for(i=n;i>=1;i--)
    {
     printf("%d ",a[i]);
    }
    return 0;
}

实验1.4 8579 链式线性表的基本操作

时间限制:1000MS 代码长度限制:10KB
提交次数:5567 通过次数:2176

题型: 编程题语言: G++;GCC

Description

编写算法，创建一个含有n个元素的带头结点的单链表L并实现插入、删除、遍历操作。本题目提供部分代码，请补全内容。

#include
#include
#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; inext;
 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 elementn2:Delete elementn3:Load all elementsn0:ExitnPlease 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;
		}
	}
}

输入格式

测试样例格式说明：
根据菜单操作：
1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开
2、输入2，表示要实现删除操作，紧跟着要输入删除的位置
3、输入3，表示要输出顺序表的所有元素
4、输入0，表示程序结束

输入样例

输出样例

Please input the init size of the linklist:
Please input the 3 element of the linklist:
A Link List Has Created.
The LinkList is:3 6 9 
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The LinkList is:3 6 9 
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 12 is Successfully Inserted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 3 is Successfully Deleted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The LinkList is:6 9 12 
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:

#include
#include
#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; idata=e;
    p->next=NULL;
    q->next=p;
    q=p;
  }
  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){
   int j;
   LNode *p,*s;
   p=L;///这句话不要忘记
   j=0;
   while(p&&(jnext;
       j++;
   }
   if(!p||j>i-1)
   return ERROR;
   s=new LNode;///这句话也不要忘了
   s->data=e;
   s->next=p->next;
   p->next=s;
   return OK;
}

int LinkDelete_L(LinkList &L,int i, ElemType &e){
// 算法2.10
// 在带头结点的单链线性表L中，删除第i个元素，并用e返回其值
   int j;LNode *p,*q;
   p=L;j=0;
   while((p->next)&&(jnext，不能到尽头，要不然没东西删了，同样是i-1
   {
       p=p->next;
       j++;
   }
   if(!(p->next)||(j>i-1))///不能到尽头，要不然没东西删了
      return ERROR;
    q=p->next;
    p->next=q->next;
    e=q->data;
    delete q;
    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 elementn2:Delete elementn3:Load all elementsn0:ExitnPlease choose:n");
		scanf("%d",&a);
		switch(a)
		{
			case 1: scanf("%d%d",&i,&x);
				  if(LinkInsert_L(T,i,x)==ERROR) 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)==ERROR) 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.5 8580 合并链表

时间限制:1000MS 代码长度限制:10KB
提交次数:3724 通过次数:2077

题型: 编程题语言: G++;GCC

Description

线性链表的基本操作如下：
#include
#include
#define ERROR 0
#define OK 1 
#define ElemType int

typedef int Status;
typedef struct LNode
{
 int data;
 struct LNode *next;
}LNode,*LinkList;


Status ListInsert_L(LinkList &L, int i, ElemType e) {  // 算法2.9
  // 在带头结点的单链线性表L的第i个元素之前插入元素e
  LinkList p,s;
  p = L;   
  int j = 0;
  while (p && j < i-1) {  // 寻找第i-1个结点
    p = p->next;
    ++j;
  } 
  if (!p || j > i-1) return ERROR;      // i小于1或者大于表长
  s = (LinkList)malloc(sizeof(LNode));  // 生成新结点
  s->data = e;  s->next = p->next;      // 插入L中
  p->next = s;
  return OK;
} // LinstInsert_L

Status ListDelete_L(LinkList &L, int i, ElemType &e) {  // 算法2.10
  // 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
  LinkList p,q;
  p = L;
  int j = 0;
  while (p->next && j < i-1) {  // 寻找第i个结点，并令p指向其前趋
    p = p->next;
    ++j;
  }
  if (!(p->next) || j > i-1) return ERROR;  // 删除位置不合理
  q = p->next;
  p->next = q->next;           // 删除并释放结点
  e = q->data;
  free(q);
  return OK;
} // ListDelete_L

设计一个算法将两个非递减有序链表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

#include 
#include 

using namespace std;

int main()
{
    int a[105]={0},i,len1=0,len2=0;
    cin>>len1;              //输入两个顺序表
    for(i=1;i<=len1;i++)
        cin>>a[i];
    cin>>len2;
    for(i=len1+1;i<=len1+len2;i++)//len1+len2就是a数组的总长度
        cin>>a[i];

    cout<<"List A:";        //输出两个顺序表
    for(i=1;i<=len1;i++)
        cout<

实验1.5 19080 反转链表

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 填空题语言: 不限定

Description

一道经典的题目

给定一个单链表的头结点L，长度为n，反转该链表后，返回新链表的表头。

要求：空间复杂度 O(1) ，时间复杂度 O(n)。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

#include //C++
using namespace std;
struct LNode
{
    int data;
    LNode * next;
};
void createList(LNode * &L,int n)
{

    LNode *r, *p;
    r=L=new LNode;
    L->next=NULL;
    for(int i=1; i<=n; i++)
    {
        p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void trv(LNode * L)
{

    L=L->next;
    while(L)
    {
        cout<data<<' ';
        L=L->next;
    }
}
void reverseList(LNode * &L)
{
    LNode *pre = NULL;
    LNode *cur = L->next;
    LNode *nex = NULL;
    while (cur)
    {
        _______________________
    }
    L->next=pre;
}
int main()
{
    int n;
    LNode *L;
    cin>>n;
    createList(L,n);
    reverseList(L);
    trv(L);
    return 0;
}

输入格式

第一行一个整数n，代表链表长度。
第二行n个整数。

输出格式

输出逆置后的单链表。

输入样例

5
1 2 3 4 5

输出样例

5 4 3 2 1

#include //C++
using namespace std;
struct LNode
{
    int data;
    LNode * next;
};
void createList(LNode * &L,int n)
{
    
    LNode *r, *p;
    r=L=new LNode;
    L->next=NULL;
    for(int i=1; i<=n; i++)
    {
        p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void trv(LNode * L)
{
    
    L=L->next;
    while(L)
    {
        cout<data<<' ';
        L=L->next;
    }
}
void reverseList(LNode * &L) 
{
    LNode *pre = NULL;
    LNode *cur = L->next;
    LNode *nex = NULL; 
    while (cur)
    {
        ///请填空
        nex=cur->next;
        cur->next=pre;
        pre=cur;
        cur=nex;
        if(nex)
        {
            nex=nex->next;
        }
    }
    L->next=pre;
}
int main()
{
    int n;
    LNode *L;
    cin>>n;
    createList(L,n);
    reverseList(L);
    trv(L);
    return 0;
}

实验2.1 8583 顺序栈的基本操作

时间限制:1000MS 代码长度限制:10KB
提交次数:4189 通过次数:2059

题型: 编程题语言: G++;GCC

Description

创建一个空的顺序栈，并实现栈的入栈、出栈、返回栈的长度、返回栈顶元素、栈的遍历等基本算法。请将下面的程序补充完整。

#include 
#include 
#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
// 请补全代码
	
}

Status Push(SqStack &S,SElemType e)   
{
// 在栈S中插入元素e为新的栈顶元素
// 请补全代码
	
}

Status Pop(SqStack &S,SElemType &e)   
{
// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
// 请补全代码
	
}

Status GetTop(SqStack S,SElemType &e)   
{ 
// 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
// 请补全代码
	
}

int StackLength(SqStack S) 
{
// 返回栈S的元素个数
// 请补全代码
	
}

Status StackTraverse(SqStack S)
{
// 从栈顶到栈底依次输出栈中的每个元素
	SElemType *p  =  ______________________        //请填空
	if(______________________)printf("The Stack is Empty!"); //请填空
	else
	{
		printf("The Stack is: ");
		while(______________________)            //请填空
		{
                       ______________________               //请填空
			printf("%d ", *p);
			
		}
	}
	printf("n");
	return OK;
}

int main()
{
     int a;
     SqStack S;
SElemType x, e;
     if(______________________)    // 判断顺序表是否创建成功，请填空
{
	printf("A Stack Has Created.n");
}
while(1)
	{
    printf("1:Push n2:Pop n3:Get the Top n4:Return the Length of the Stackn5:Load the Stackn0:ExitnPlease choose:n");
	scanf("%d",&a);
		switch(a)
		{
			case 1: scanf("%d", &x);
		      if(______________________) printf("Push Error!n"); // 判断Push是否合法，请填空
		      else printf("The Element %d is Successfully Pushed!n", x); 
		      break;
		case 2: if(______________________) printf("Pop Error!n"); // 判断Pop是否合法，请填空
			  else printf("The Element %d is Successfully Poped!n", e);
		  	  break;
		case 3: if(______________________)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",______________________); //请填空
				  break;
			case 5: ______________________  //请填空
				  break;
			case 0: return 1;
		}
	}
}

输入格式

测试样例格式说明：
根据菜单操作：
1、输入1，表示要实现Push操作，紧跟着输入要Push的元素
2、输入2，表示要实现Pop操作
3、输入3，返回栈顶元素
4、输入4，返回栈的元素个数
5、输入5，表示从栈顶到栈底输出栈的所有元素
6、输入0，表示程序结束

输入样例

输出样例

A Stack Has Created.
1:Push 
2:Pop 
3:Get the Top 
4:Return the Length of the Stack
5:Load the Stack
0:Exit
Please choose:
The Element 2 is Successfully Pushed!
1:Push 
2:Pop 
3:Get the Top 
4:Return the Length of the Stack
5:Load the Stack
0:Exit
Please choose:
The Element 4 is Successfully Pushed!
1:Push 
2:Pop 
3:Get the Top 
4:Return the Length of the Stack
5:Load the Stack
0:Exit
Please choose:
The Element 6 is Successfully Pushed!
1:Push 
2:Pop 
3:Get the Top 
4:Return the Length of the Stack
5:Load the Stack
0:Exit
Please choose:
The Stack is: 6 4 2 
1:Push 
2:Pop 
3:Get the Top 
4:Return the Length of the Stack
5:Load the Stack
0:Exit
Please choose:
The Top Element is 6!
1:Push 
2:Pop 
3:Get the Top 
4:Return the Length of the Stack
5:Load the Stack
0:Exit
Please choose:
The Length of the Stack is 3!
1:Push 
2:Pop 
3:Get the Top 
4:Return the Length of the Stack
5:Load the Stack
0:Exit
Please choose:
The Element 6 is Successfully Poped!
1:Push 
2:Pop 
3:Get the Top 
4:Return the Length of the Stack
5:Load the Stack
0:Exit
Please choose:
The Stack is: 4 2 
1:Push 
2:Pop 
3:Get the Top 
4:Return the Length of the Stack
5:Load the Stack
0:Exit
Please choose:
The Element 4 is Successfully Poped!
1:Push 
2:Pop 
3:Get the Top 
4:Return the Length of the Stack
5:Load the Stack
0:Exit
Please choose:
The Element 2 is Successfully Poped!
1:Push 
2:Pop 
3:Get the Top 
4:Return the Length of the Stack
5:Load the Stack
0:Exit
Please choose:
Pop Error!
1:Push 
2:Pop 
3:Get the Top 
4:Return the Length of the Stack
5:Load the Stack
0:Exit
Please choose:

#include
#include
#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.base=new SElemType[STACK_INIT_SIZE];
    if(!S.base)return ERROR;
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
    return OK;
// 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE
// 请补全代码

}

Status Push(SqStack &S,SElemType e)
{
    if(S.top-S.base==S.stacksize)return ERROR;
    *S.top=e;
    S.top++;
    return OK;
// 在栈S中插入元素e为新的栈顶元素
// 请补全代码

}

Status Pop(SqStack &S,SElemType &e)
{
    if(S.base==S.top)return ERROR;
    S.top--;
    e=*S.top;
    return e;
// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
// 请补全代码

}

Status GetTop(SqStack S,SElemType &e)
{
     if(S.base==S.top)return ERROR;
     e=*(S.top-1);
    return e;
// 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
// 请补全代码

}

int StackLength(SqStack S)
{
    if(S.base==S.top)return ERROR;
    return S.top-S.base;
// 返回栈S的元素个数
// 请补全代码

}

Status StackTraverse(SqStack S)
{
// 从栈顶到栈底依次输出栈中的每个元素
	SElemType *p  =  S.top;      //请填空
	if(S.top==S.base)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 Stackn5:Load the Stackn0:ExitnPlease choose:n");
	scanf("%d",&a);
		switch(a)
		{
			case 1: scanf("%d", &x);
		      if(Push(S,x)==ERROR) printf("Push Error!n"); // 判断Push是否合法，请填空
		      else printf("The Element %d is Successfully Pushed!n", x);
		      break;
		case 2: if(Pop(S,e)==ERROR) printf("Pop Error!n"); // 判断Pop是否合法，请填空
			  else printf("The Element %d is Successfully Poped!n", e);
		  	  break;
		case 3: if(GetTop(S,e)==ERROR)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;
		}
	}
}

实验2.2 8584 循环队列的基本操作

时间限制:1000MS 代码长度限制:10KB
提交次数:3772 通过次数:1884

题型: 编程题语言: G++;GCC

Description

创建一个空的循环队列，并实现入队、出队、返回队列的长度、返回队头元素、队列的遍历等基本算法。请将下面的程序补充完整。

#include 
#include 
#define OK 1
#define ERROR 0
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int QElemType;
#define MAXQSIZE 100 // 最大队列长度(对于循环队列，最大队列长度要减1)

typedef struct
{
   QElemType *base; // 初始化的动态分配存储空间
   int front; // 头指针,若队列不空,指向队列头元素
   int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置
 }SqQueue;

Status InitQueue(SqQueue &Q)   
{
// 构造一个空队列Q，该队列预定义大小为MAXQSIZE
// 请补全代码
	
}

Status EnQueue(SqQueue &Q,QElemType e)  
{ 
// 插入元素e为Q的新的队尾元素
// 请补全代码
	
}

Status DeQueue(SqQueue &Q, QElemType &e) 
{  
// 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR
// 请补全代码
	
}

Status GetHead(SqQueue Q, QElemType &e)
{	
// 若队列不空，则用e返回队头元素，并返回OK，否则返回ERROR
// 请补全代码
	
}

int QueueLength(SqQueue Q)  
{
// 返回Q的元素个数
// 请补全代码
	
}

Status QueueTraverse(SqQueue Q)  
{ 
// 若队列不空，则从队头到队尾依次输出各个队列元素，并返回OK；否则返回ERROR.
	int i;
	i=Q.front;
	if(______________________)printf("The Queue is Empty!");  //请填空
	else{
		printf("The Queue is: ");
		while(______________________)     //请填空
		{
			printf("%d ",______________________ );   //请填空
			i = ______________________;   //请填空
		}
	}
	printf("n");
	return OK;
}

int main()
{
	int a;
  SqQueue S;
	QElemType x, e;
  if(______________________)    // 判断顺序表是否创建成功，请填空
	{
		printf("A Queue Has Created.n");
	}
	while(1)
	{
	printf("1:Enter n2:Delete n3:Get the Front n4:Return the Length of the Queuen5:Load the Queuen0:ExitnPlease choose:n");
		scanf("%d",&a);
		switch(a)
		{
			case 1: scanf("%d", &x);
				  if(______________________) printf("Enter Error!n"); // 判断入队是否合法，请填空
				  else printf("The Element %d is Successfully Entered!n", x); 
				  break;
			case 2: if(______________________) printf("Delete Error!n"); // 判断出队是否合法，请填空
				  else printf("The Element %d is Successfully Deleted!n", e);
				  break;
			case 3: if(______________________)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",______________________);  //请填空
				  break;
			case 5: ______________________ //请填空
				  break;
			case 0: return 1;
		}
	}
}

输入格式

测试样例格式说明：
根据菜单操作：
1、输入1，表示要实现入队操作，紧跟着输入要入队的元素
2、输入2，表示要实现出队操作
3、输入3，返回队头元素
4、输入4，返回队列的元素个数
5、输入5，表示从队头到队尾输出队的所有元素
6、输入0，表示程序结束

输入样例

输出样例

A Queue Has Created.
1:Enter 
2:Delete 
3:Get the Front 
4:Return the Length of the Queue
5:Load the Queue
0:Exit
Please choose:
The Element 1 is Successfully Entered!
1:Enter 
2:Delete 
3:Get the Front 
4:Return the Length of the Queue
5:Load the Queue
0:Exit
Please choose:
The Element 2 is Successfully Entered!
1:Enter 
2:Delete 
3:Get the Front 
4:Return the Length of the Queue
5:Load the Queue
0:Exit
Please choose:
The Element 3 is Successfully Entered!
1:Enter 
2:Delete 
3:Get the Front 
4:Return the Length of the Queue
5:Load the Queue
0:Exit
Please choose:
The Queue is: 1 2 3 
1:Enter 
2:Delete 
3:Get the Front 
4:Return the Length of the Queue
5:Load the Queue
0:Exit
Please choose:
The Element 1 is Successfully Deleted!
1:Enter 
2:Delete 
3:Get the Front 
4:Return the Length of the Queue
5:Load the Queue
0:Exit
Please choose:
The Head of the Queue is 2!
1:Enter 
2:Delete 
3:Get the Front 
4:Return the Length of the Queue
5:Load the Queue
0:Exit
Please choose:
The Queue is: 2 3 
1:Enter 
2:Delete 
3:Get the Front 
4:Return the Length of the Queue
5:Load the Queue
0:Exit
Please choose:

#include
#include
#define OK 1
#define ERROR 0
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int QElemType;
#define MAXQSIZE 100 // 最大队列长度(对于循环队列，最大队列长度要减1)
//把所有的i+1形式换成(i+1)%MAXQSIZE形式
typedef struct
{
   QElemType *base; // 初始化的动态分配存储空间
   int front; /// 头，指向队列头元素,类似于i、j，实际上是数组来存东西
   int rear; /// 尾，指向队列尾元素的下一个位置，rear在前，front在后
 }SqQueue;

Status InitQueue(SqQueue &Q)
{
    Q.base=new QElemType[MAXQSIZE];
    if(!Q.base)return ERROR;
    Q.rear=Q.front=0;
    return OK;
// 构造一个空队列Q，该队列预定义大小为MAXQSIZE
// 请补全代码
}

Status EnQueue(SqQueue &Q,QElemType e)
{
    if((Q.rear+1)%MAXQSIZE==Q.front)return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    return OK;
// 插入元素e为Q的新的队尾元素
// 请补全代码

}

Status DeQueue(SqQueue &Q, QElemType &e)
{
    if(Q.front==Q.rear)return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXQSIZE;
    return OK;
// 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR
// 请补全代码

}

Status GetHead(SqQueue Q, QElemType &e)
{
    if(Q.front==Q.rear)return ERROR;
    e=Q.base[Q.front];
    return OK;
// 若队列不空，则用e返回队头元素，并返回OK，否则返回ERROR
// 请补全代码

}

int QueueLength(SqQueue Q)
{
    if(Q.front==Q.rear)return ERROR;
    return Q.rear-Q.front;
// 返回Q的元素个数
// 请补全代码

}

Status QueueTraverse(SqQueue Q)
{
// 若队列不空，则从队头到队尾依次输出各个队列元素，并返回OK；否则返回ERROR.
	int i;
	i=Q.front;
	if(Q.front==Q.rear)printf("The Queue is Empty!");  //请填空
	else{
		printf("The Queue is: ");
		while(i!=Q.rear)     ///请填空,这里是i
		{
			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 Queuen5:Load the Queuen0:ExitnPlease choose:n");
		scanf("%d",&a);
		switch(a)
		{
			case 1: scanf("%d", &x);
				  if(EnQueue(S,x)==ERROR) printf("Enter Error!n"); // 判断入队是否合法，请填空
				  else printf("The Element %d is Successfully Entered!n", x);
				  break;
			case 2: if(DeQueue(S, e)==ERROR) printf("Delete Error!n"); // 判断出队是否合法，请填空
				  else printf("The Element %d is Successfully Deleted!n", e);
				  break;
			case 3: if(GetHead(S,e)==ERROR)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;
		}
	}
}

实验2.3 8585 栈的应用——进制转换

时间限制:1000MS 代码长度限制:10KB
提交次数:2572 通过次数:1925

题型: 编程题语言: G++

Description

利用顺序栈的基本操作算法，编写满足下列要求的数制转换程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。

输入格式

第一行：输入一个非负的十进制整数

输出格式

第一行：与输入等值的八进制数

输入样例

输出样例

#include 
#include 
using namespace std;
typedef struct stack
{
    int *base;
    int *top;
}stack;
void createstack(stack &S)
{
    S.base=new int [100];
    S.top=S.base;
}
void push(stack &S,int e)
{
    *S.top=e;
    S.top++;
}
void Pop(stack S)
{
    int *p=S.top;
    while(p!=S.base)
    {
        p--;
        cout<<*p;
    }
}
int main()
{
    stack S;
    int n;
    cin>>n;
    createstack(S);
    while(n)
    {
        push(S,n%8);
        n=n/8;
    }
    Pop(S);
    return 0;
}

实验2.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 pairsn");
                      exit(ERROR);
                    }
                    else
                    {
                     __________________________;
                      break; // 跳出switch语句
                    }
                  }
                  else // 栈空
                  {
                    printf("lack of left parenthesisn");
                    exit(ERROR);
                  }
         default: ______________________; // 其它字符不处理，指针向后移
       }
     if(StackEmpty(s)) // 字符串结束时栈空
       printf("matchingn");
     else
       printf("lack of right parenthesisn");
   }
 }
int main()
 {
   check();
 }

输入格式

第一行：输入一个包含圆括号或方括号、不超过80个字符的表达式串。

输出格式

第一行：若输入表达式括号匹配，输出"matching"; 若不匹配，输出具体信息:"isn't matched pairs", 或"lack of left parenthesis"或"lack of right parenthesis"

输入样例

8*[3*(35-23)]

输出样例

matching

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 50 // 存储空间初始分配量
#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)
{
    ///栈空是1，栈不空是0
    if(S.base==S.top)return OK;
    return ERROR;

 }
Status Push(SqStack &S,SElemType e)
{
    if(S.top-S.base==S.stacksize)return ERROR;
    *S.top=e;
    S.top++;
    return OK;
 }
 Status Pop(SqStack &S,SElemType &e)
{
    if(S.base==S.top)return ERROR;
    S.top--;
    e=*S.top;
    return OK;
 }
void check()
 { // 对于输入的任意一个字符串，检验括号是否配对
   SqStack s;
   SElemType ch[80],*p,e;
   if(InitStack(s)) // 初始化栈成功
   {
    //printf("请输入表达式n");
     scanf("%s",&ch);///填空
     p=ch;
     while(*p) // 没到串尾
       switch(*p)
       {
         case '(':
         case '[':Push(s,*p++);///填空,注意p是指针，要加*号，而且要++，下面提醒到
                  break; // 左括号入栈，且p++
         case ')':
         case ']':if(!StackEmpty(s)) // 栈不空
                  {
                   Pop(s,e); ///填空， 弹出栈顶元素
                    if(*p==')'&&e!='('||(*p==']'&&e!='[')) ///填空
                                                // 弹出的栈顶元素与*p不配对
{
                      printf("isn't matched pairsn");
                      exit(ERROR);
                    }
                    else
                    {
                      p++;///填空
                      break; // 跳出switch语句
                    }
                  }
                  else // 栈空
                  {
                    printf("lack of left parenthesisn");
                    exit(ERROR);
                  }
         default: p++; ///填空 其它字符不处理，指针向后移
       }
     if(StackEmpty(s)) // 字符串结束时栈空
       printf("matchingn");
     else
       printf("lack of right parenthesisn");
   }
 }
int main()
 {
   check();
 }

实验2.5 8587 行编辑程序

时间限制:1000MS 代码长度限制:10KB
提交次数:3976 通过次数:1807

题型: 编程题语言: G++;GCC

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

#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 char SElemType;
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
#define STACK_INIT_SIZE 20 ///懒得写realloc，干脆将这里改成20存储空间初始分配量
#define STACKINCREMENT 2 // 存储空间分配增量
struct SqStack
{
    SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
    SElemType *top; // 栈顶指针
    int stacksize; // 当前已分配的存储空间，以元素为单位
}; // 顺序栈

Status InitStack(SqStack &S)
{
    // 构造一个空栈S
    S.base = S.top = new SElemType[STACK_INIT_SIZE];
    if (!S.base)return ERROR;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}
Status StackEmpty(SqStack S)
{
    if(S.base==S.top)return TRUE;
    return FALSE;
    // 若栈S为空栈，则返回TRUE，否则返回FALSE
}
Status ClearStack(SqStack &S)
{
    ///不用填空
    // 把S置为空栈
    S.top=S.base;
    return OK;
}
Status DestroyStack(SqStack &S)
{
    // 销毁栈S，S不再存在
    //其实free是c的，而new是c++的，一般来说free搭配malloc，delete搭配new，但混搭oj也能过，不管了
    free(S.base);
    S.base=NULL;
    S.top=NULL;
    S.stacksize=0;
    return OK;
}
Status Push(SqStack &S,SElemType e)
{
    // 插入元素e为新的栈顶元素
    *S.top=e;
    S.top++;
    return OK;
}
Status Pop(SqStack &S,SElemType &e)
{
    // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
    if (S.top == S.base)return ERROR;
    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); // 将从栈底到栈顶的栈内字符输出
        s.top = s.base; ///填空，重置s为空栈
    }
    DestroyStack(s);
}
int main()///题目是void，要改成int
{
    LineEdit();
    return 0;
}

实验3.1

#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

#include "stdio.h"
#include "stdlib.h"
#include 
#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;///i指向当前匹配字符的前一个字符的位置，j就代表某k处next[k]的值
    next[1]=0;
    while(T[i]!='')
    {
        if((T[i]==T[j])||j==0)
        {
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
    }
}

int main()///改main加return 0
{
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");
}
return 0;
}

实验3.2 8592 KMP算法

时间限制:1000MS 代码长度限制:10KB
提交次数:3113 通过次数:1558

题型: 编程题语言: G++;GCC

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("%dn",pos);
}
    }

输入格式

第一行：输入n，表示有n对字符串需要匹配
第二行：输入第1个主串
第三行：输入第1个模式串
第四行：输入第2个主串
第五行：输入第2个模式串
……
倒数二行：输入第n个主串
最后一行：输入第n个模式串

输出格式

第一至第n行：输出每相应模式串的匹配值

输入样例

4
oadhifgoarhglkdsa
oar
abcdefg
dec
algeojflas
ojf
jfaweiof
of

输出样例

#include "stdio.h"
#include "stdlib.h"
#include 
#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[]){
    int i=1,j=0;
    next[1]=0;
    while(T[i]!='')
    {
        if(T[i]==T[j]||j==0)
        {
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
    }
// 算法4.7
// 求模式串T的next函数值并存入数组next
   // 请补全代码




}

int Index_KMP(SString S,SString T,int pos)
{
    int next[MAXSTRLEN+1],i=pos,j=0;///i,j都是从0开始的
    get_next(T,next);///这一行不要忘记写
    while(i<=S[0]&&j<=T[0])
    {
        if(S[i]==T[j]||j==0)
        {
            i++;
            j++;
        }
        else
            j=next[j];
    }
    if(j>=T[0])///当成立时，说明模式串的所有字符都比较了，说明在主串中找到了相应的模式串
        return i-T[0];///此时i走到了主串中的模式串的后一字符，应减去模式串长度
    else
        return 0;///说明在主串没找到模式串
// 算法4.6
// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置
// KMP算法。请补全代码



}
int main()///改main加return 0
{
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,0);    // 请填空
printf("%dn",pos);
}
return 0;
}

实验4.1 8606 二叉树的构建及遍历操作

时间限制:1000MS 代码长度限制:10KB
提交次数:2653 通过次数:1597

题型: 编程题语言: G++;GCC

Description

构造二叉链表表示的二叉树：按先序次序输入二叉树中结点的值（一个字符），'#'字符表示空树，构造二叉链表表示的二叉树T；再输出三种遍历序列。本题只给出部分代码,请补全内容。

#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int  Status;

typedef char  ElemType;
typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;

Status CreateBiTree(BiTree &T) {  // 算法6.4
  // 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
  // 构造二叉链表表示的二叉树T。
  char ch;
  scanf("%c",&ch);
  if (ch=='#') T = NULL;
  else {
    if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
    ________________________ // 生成根结点
     _______________________   // 构造左子树
    _________________________  // 构造右子树
  }
  return OK;
} // CreateBiTree





Status PreOrderTraverse( BiTree T) {
   // 前序遍历二叉树T的递归算法
   //补全代码,可用多个语句
  
} // PreOrderTraverse

Status InOrderTraverse( BiTree T) {
     // 中序遍历二叉树T的递归算法
    //补全代码,可用多个语句
    
  
} // InOrderTraverse

Status PostOrderTraverse( BiTree T) {
     // 后序遍历二叉树T的递归算法
     //补全代码,可用多个语句
    
} // PostOrderTraverse



int main()   //主函数
{
                      //补充代码
 }//main

#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int  Status;

typedef char  ElemType;
typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;

Status CreateBiTree(BiTree &T) {  // 算法6.4
  // 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
  // 构造二叉链表表示的二叉树T。
  char ch;
  scanf("%c",&ch);
  if (ch=='#') T = NULL;
  else {
    if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
    T->data=ch;// 生成根结点
     CreateBiTree(T->lchild);// 构造左子树
    CreateBiTree(T->rchild); // 构造右子树
  }
  return OK;
} // CreateBiTree





Status PreOrderTraverse( BiTree T) {
    if(T)
    {
        printf("%c",T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
    return 0;
   // 前序遍历二叉树T的递归算法
   //补全代码,可用多个语句

} // PreOrderTraverse

Status InOrderTraverse( BiTree T) {
    if(T)
    {

        InOrderTraverse(T->lchild);
        printf("%c",T->data);
        InOrderTraverse(T->rchild);
    }
    return 0;
     // 中序遍历二叉树T的递归算法
    //补全代码,可用多个语句


} // InOrderTraverse

Status PostOrderTraverse( BiTree T) {
    if(T)
    {

        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c",T->data);
    }
    return 0;
     // 后序遍历二叉树T的递归算法
     //补全代码,可用多个语句

} // PostOrderTraverse



int main()   //主函数
{
    BiTree T;
    CreateBiTree(T);
    PreOrderTraverse(T);
    printf("n");
    InOrderTraverse(T);
    printf("n");
    PostOrderTraverse(T);
    printf("n");
    return 0;                  //补充代码
 }//main

实验4.2 18924 二叉树的宽度

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题语言: G++;GCC

Description

二叉树的宽度指的是具有节点数目最多的那一层的节点个数。
          1
         / 
        2   3
       /     
      4     
答案为2, 第二层节点数最多，为2个节点。

输入格式

共n行。
第一行一个整数n，表示有n个结点，编号为1至n,结点1为树根。（1<=n<=50）
第二行至第n行，每行有两个整数x和y，表示在二叉树中x为y的父节点。x第一次出现时y为左孩子

输出格式

输出二叉树的宽度。

输入样例

输出样例

#include
#include
///dfs方法
int level[100];
struct Tree
{
    int p;///父亲
    int l;///左孩子
    int r;///右孩子
}tree[100];
void Createtree(int f,int z)
{
    tree[z].p=f;
    if(!tree[f].l)
        tree[f].l=z;
    else
        tree[f].r=z;
}
int findroot(int n)
{
    for(int i=1;i<=n;i++)
    {
        if(tree[i].p==0)
            return i;
    }
}
void findans(int root,int k)
{
    level[k]++;
    if(tree[root].l)
        findans(tree[root].l,k+1);
    if(tree[root].r)
        findans(tree[root].r,k+1);
}
int main()
{
    int n,ans=0,root,a,b;
    scanf("%d",&n);
    for(int i=1;ians)
            ans=level[i];
    }
    printf("%d",ans);
    return 0;
}

2022SCAU数据结构题库汇总（最简单最详细）

C/C++/C#相关栏目本月热门文章