2022SCAU数据结构题库汇总
实验1.1
8576 顺序线性表的基本操作
时间限制:1000MS 代码长度限制:10KB
提交次数:9027 通过次数:2456
题型: 编程题 语言: G++;GCC
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 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，表示程序结束
输入样例
1 1 2 1 1 3 2 1 3 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<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)
{
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;i<L.length;i++) printf("%d ",L.elem[i]); // 请填空
}
printf("n");
return OK;
}
int ListInsert_Sq(SqList &L,int i,int e)
{
if(i<1||i>L.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的元素列表
输入样例
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
提示
输出时注意大小写和标点。
#include <iostream>
#include <algorithm>
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<<a[i]<<" ";
cout<<endl;
cout<<"List B:";
for(i=len1+1;i<=len1+len2;i++)
cout<<a[i]<<" ";
cout<<endl;
sort(a+1,a+1+len1+len2);
cout<<"List C:";
for(i=1;i<=len1+len2;i++)
printf("%d ",a[i]);
return 0;
}
实验1.3
8578 顺序表逆置
时间限制:1000MS 代码长度限制:10KB
提交次数:3660 通过次数:2149
题型: 编程题 语言: G++;GCC
Description
顺序表的基本操作代码如下：
#include<stdio.h>
#include<malloc.h>
#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 <stdio.h>
#include <stdlib.h>
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<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; // 生成新结点
// 请补全代码
}
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 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，表示程序结束
输入样例
3 3 6 9 3 1 4 12 2 1 3 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<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; // 生成新结点
p->data=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&&(j<i-1))///这里是i-1，因为是在i前面插入
{
p=p->next;
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)&&(j<i-1))///这里是p->next，不能到尽头，要不然没东西删了，同样是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<stdio.h>
#include<malloc.h>
#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 <iostream>
#include <algorithm>
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<<a[i]<<" ";
cout<<endl;
cout<<"List B:";
for(i=len1+1;i<=len1+len2;i++)
cout<<a[i]<<" ";
cout<<endl;
sort(a+1,a+1+len1+len2);
cout<<"List C:";
for(i=1;i<=len1+len2;i++)
printf("%d ",a[i]);
return 0;
}实验1.6
19080 反转链表
时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 填空题 语言: 不限定
Description
一道经典的题目
给定一个单链表的头结点L，长度为n，反转该链表后，返回新链表的表头。
要求：空间复杂度 O(1) ，时间复杂度 O(n)。
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
#include <iostream>//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<<L->data<<' ';
L=L->next;
}
}
void reverseList(LNode * &L)
{
LNode *pre = NULL;/**< 用三个指针分别表示前驱，当前，后继 */
LNode *cur = L->next;/**< 当前是第一个节点a1 */
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 <iostream>//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<<L->data<<' ';
L=L->next;
}
}
void reverseList(LNode * &L)
{
LNode *pre = NULL;/**< 用三个指针分别表示前驱，当前，后继 */
LNode *cur = L->next;/**< 当前是第一个节点a1 */
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<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
// 请补全代码
}
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，表示程序结束
输入样例
1 2 1 4 1 6 5 3 4 2 5 2 2 2 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<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.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<malloc.h>
#include<stdio.h>
#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，表示程序结束
输入样例
1 1 1 2 1 3 5 2 3 5 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<malloc.h>
#include<stdio.h>
#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
利用顺序栈的基本操作算法，编写满足下列要求的数制转换程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。
输入格式
第一行：输入一个非负的十进制整数
输出格式
第一行：与输入等值的八进制数
输入样例
15
输出样例
17
#include <algorithm>
#include <iostream>
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 <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;///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
输出样例
8 0 5 7
#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[]){
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
17121 求二叉树各种节点数
时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC
Description
构造二叉链表表示的二叉树：按先序次序输入二叉树中结点的值（一个字符），'#'字符表示空树，构造二叉链表表示的二叉树T,并求此二叉树中度为2的节点总数，度为1的节点总数，度为0的节点总数
#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
int main() //主函数
{
//补充代码
}//main
输入格式
第一行输入先序次序二叉树中结点
输出格式
第一行输出度为2的节点数 第二行输出度为1的节点数 第三行输出度为0的节点数
输入样例
ABC###D##
输出样例
1 1 2
#include <cstdio>
#include <malloc.h>
#include <iostream>
#define OK 1
#define ERROR 0
using namespace std;
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;
}
int d2=0,d1=0,d0=0;
void nodeDegree(BiTree T)
{
if(T)
{
if(T->lchild&&T->rchild)
d2++;
else if(T->lchild==NULL&&T->rchild==NULL)
d0++;
else
d1++;
nodeDegree(T->lchild);
nodeDegree(T->rchild);
}
}
int main() //主函数
{
std::ios::sync_with_stdio(false);
BiTree T;
CreateBiTree(T);
nodeDegree(T);
cout << d2 << endl << d1 << endl <<d0;
}
实验4.3
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为左孩子
输出格式
输出二叉树的宽度。
输入样例
5 1 2 1 3 2 4 2 5
输出样例
2
#include<stdio.h>
#include<math.h>
///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;i<n;i++)
{
scanf("%d %d",&a,&b);
Createtree(a,b);
}
root=findroot(n);
findans(root,1);///从根节点、第一层开始
for(int i=1;i<=100;i++)
{
if(level[i]>ans)
ans=level[i];
}
printf("%d",ans);
return 0;
}实验4.5
18923 二叉树的直径
时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC
Description
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
1
/
2 3
/
4 5
答案为3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
输入格式
共n行。 第一行一个整数n，表示有n个结点，编号为1至n。 第二行至第n行，每行有两个整数x和y，表示在二叉树中x为y的父节点。x第一次出现时y为左孩子
输出格式
输出二叉树的直径。
输入样例
5 1 2 1 3 2 4 2 5
输出样例
3
#include<stdio.h>
#include<math.h>
int tree[100]={0};
int treenum[100]={0};
int k=0;
void th(int p,int c)
{
if(tree[2*treenum[p]]==0)
{
tree[2*treenum[p]]=c;
treenum[c]=2*treenum[p];
}
else{
tree[2*treenum[p]+1]=c;
treenum[c]=2*treenum[p]+1;}
}
int dfs(int root)
{
if(tree[root]==0)
{
return 0;
}
int left=dfs(2*treenum[tree[root]]);
int right=dfs(2*treenum[tree[root]]+1);
if(k<left+right+1)
k=left+right+1;
if(left>right)
return left+1;
else
return right+1;
}
int main()
{
int n,p,c;
scanf("%d %d %d", &n,&p,&c);
tree[1]=p;
treenum[p]=1;
tree[2]=c;
treenum[c]=2;
for(int i=0;i<n-2;i++)
{
scanf("%d %d",&p,&c);
th(p,c);
}
dfs(1);
printf("%d",k-1);
}实验4.6
8609 哈夫曼树
时间限制:1000MS 代码长度限制:10KB
提交次数:3178 通过次数:1263
题型: 编程题 语言: G++;GCC
Description
利用静态链表建立赫夫曼树，建树过程中要求左子树权值小于右子树权值，求各结点的编码。要求：叶子结点的个数n及结点值由键盘录入。本题给出程序代码,要求填空以满足测试要求.
#include "stdio.h"
#include "string.h"
#include
using namespace std;
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void select(HuffmanTree &HT, int n, int &s1, int &s2)
{//在HT[1..n]中选择parent为0且weight最小的两个结点， 其序号分别为s1（最小）和s2（次小）。
__________________________
}
void createHuffmanTree(HuffmanTree &HT, int n)
{ //构造哈夫曼树HT
int i, m, s1, s2;
if (n<=1) return;
m = 2 * n - 1;
HT = new HTNode[m+1]; // 0号单元未用
for (i=1; i<=m; i++) { //初始化HT数组
HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;
}
for (i=1; i<=n; i++)
cin>>HT[i].weight;
for (i=n+1; i<=m; i++) // 建哈夫曼树
{ //在HT[1..i-1]中选择parent为0且weight最小的两个结点， 其序号分别为s1(最小)和s2(次小)
_______________________________
}
}
void createHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
{//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
char *cd = new char[n]; // 分配求编码的工作空间
cd[n-1] = ''; // 编码结束符。
int i,c,f,start;
for (i=1; i<=n; ++i)
{
start = n-1;
c=i, f=HT[i].parent;
while(f)// 从叶子到根逆向求编码
{
--start;
if (HT[f].lchild==c) cd[start] = '0';
else cd[start] = '1';
c=f,f=HT[f].parent;
}
HC[i] = new char[n-start];// 为第i个字符编码分配空间
strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC
}
}
int main()
{
int i,n;
int *w;
HuffmanTree HT;
HuffmanCode HC;
scanf("%d",&n); //权值个数
HC=new char*[n+1]; //0空间未用
createHuffmanTree(HT,n);
createHuffmanCode(HT,HC,n);
for (i = 1; i<=n; i++)
printf("%sn",HC[i]); //输出哈夫曼编码
}
输入格式
第一行：权值个数 第二行：输入n个权值，用空格分隔
输出格式
输出n行 每行表示各权值对应的哈夫曼编码
输入样例
8 5 29 7 8 14 23 3 11
输出样例
0001 10 1110 1111 110 01 0000 001
#include "stdio.h"
#include "string.h"
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void select(HuffmanTree &HT, int n, int &s1, int &s2)
{//在HT[1..n]中选择parent为0且weight最小的两个结点， 其序号分别为s1（最小）和s2（次小）。
/*整段填空*/
s1=-1;
s2=-1;
for(int i=1;i<=n;i++)
{
if(HT[i].parent==0)
{
if(s1==-1)
{
s1=i;
}
else if(HT[s1].weight>HT[i].weight)
{
s2=s1;
s1=i;
}
else if(s2==-1)
{
s2=i;
}
else if(HT[s2].weight>HT[i].weight)
{
s2=i;
}
}
}
}
void createHuffmanTree(HuffmanTree &HT, int n)
{ //构造哈夫曼树HT
int i, m, s1, s2;
if (n<=1) return;
m = 2 * n - 1;
HT = new HTNode[m+1]; // 0号单元未用
for (i=1; i<=m; i++) { //初始化HT数组
HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;
}
for (i=1; i<=n; i++)
cin>>HT[i].weight;
for (i=n+1; i<=m; i++) // 建哈夫曼树
{ //在HT[1..i-1]中选择parent为0且weight最小的两个结点， 其序号分别为s1(最小)和s2(次小)
select(HT,i-1,s1,s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}
void createHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
{//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
char *cd = new char[n]; // 分配求编码的工作空间
cd[n-1] = ''; // 编码结束符。
int i,c,f,start;
for (i=1; i<=n; ++i)
{
start = n-1;
c=i, f=HT[i].parent;
while(f)// 从叶子到根逆向求编码
{
--start;
if (HT[f].lchild==c) cd[start] = '0';
else cd[start] = '1';
c=f,f=HT[f].parent;
}
HC[i] = new char[n-start];// 为第i个字符编码分配空间
strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC
}
}
int main()
{
int i,n;
int *w;
HuffmanTree HT;
HuffmanCode HC;
scanf("%d",&n); //权值个数
HC=new char*[n+1]; //0空间未用
createHuffmanTree(HT,n);
createHuffmanCode(HT,HC,n);
for (i = 1; i<=n; i++)
printf("%sn",HC[i]); //输出哈夫曼编码
}实验5.1
8610 顺序查找
时间限制:1000MS 代码长度限制:10KB
提交次数:2303 通过次数:1423
题型: 编程题 语言: G++;GCC
Description
编写Search_Seq函数，实现在一个无序表ST中采用顺序查找算法查找值为key的元素的算法.
#include"malloc.h" /* malloc()等 */
#include"stdio.h"
#include"stdlib.h"
typedef int ElemType;
typedef struct /*静态查找表的顺序存储结构 */
{
ElemType *elem; /* 数据元素存储空间基址，建表时按实际长度分配，0号单元留空 */
int length; /* 表长度 */
}SSTable;
void Creat_Seq(SSTable &ST,int n)
{ /* 操作结果: 构造一个含n个数据元素的静态顺序查找表ST(数据来自数组r) */
int i,temp;
ST.elem=(ElemType *)malloc((n+1) * sizeof(ElemType)); /* 动态生成n个数据元素空间(0号单元不用) */
if(!(ST).elem)
{
printf("ERRORn");
exit(0);
} /*内存分配失败结束程序*/
for(i=1;i<=n;i++)
{
scanf("%d",&temp);
*(ST.elem+i)=temp; /* 依次赋值给ST */
}
ST.length=n;
}
int Search_Seq(SSTable &ST,ElemType key)
{ /* 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为 */
/* 该元素在表中的位置，否则为0。算法9.1 */
}
main()
{
SSTable ST;
int loc,key;
int n;
scanf("%d",&n);
Creat_Seq(ST,n);
//printf("Please input the key value：");
scanf("%d",&key);
loc = Search_Seq(ST,key);
if(loc!=0)
printf("The element position is %d.n",loc);
else
printf("The element is not exist.n");
}
输入格式
第一行:元素个数n 第二行：依次输入n个元素的值 第三行：输入要查找的关键字key的值
输出格式
输出分两种情形： 1.如果key值存在，则输出其在表中的位置x(表位置从1开始),格式为The element position is x. 2.如果key值不存在输出："The element is not exist."
输入样例
6 1 3 5 7 9 10 5
输出样例
The element position is 3.
#include<stdio.h>
#include<math.h>
int tree[100]={0};
int treenum[100]={0};
int k=0;
void th(int p,int c)
{
if(tree[2*treenum[p]]==0)
{
tree[2*treenum[p]]=c;
treenum[c]=2*treenum[p];
}
else{
tree[2*treenum[p]+1]=c;
treenum[c]=2*treenum[p]+1;}
}
int dfs(int root)
{
if(tree[root]==0)
{
return 0;
}
int left=dfs(2*treenum[tree[root]]);
int right=dfs(2*treenum[tree[root]]+1);
if(k<left+right+1)
k=left+right+1;
if(left>right)
return left+1;
else
return right+1;
}
int main()
{
int n,p,c;
scanf("%d %d %d", &n,&p,&c);
tree[1]=p;
treenum[p]=1;
tree[2]=c;
treenum[c]=2;
for(int i=0;i<n-2;i++)
{
scanf("%d %d",&p,&c);
th(p,c);
}
dfs(1);
printf("%d",k-1);
}#include"malloc.h" /* malloc()等 */
#include"stdio.h"
#include"stdlib.h"
typedef int ElemType;
typedef struct /*静态查找表的顺序存储结构 */
{
ElemType *elem; /* 数据元素存储空间基址，建表时按实际长度分配，0号单元留空 */
int length; /* 表长度 */
}SSTable;
void Creat_Seq(SSTable &ST,int n)
{ /* 操作结果: 构造一个含n个数据元素的静态顺序查找表ST(数据来自数组r) */
int i,temp;
ST.elem=(ElemType *)malloc((n+1) * sizeof(ElemType)); /* 动态生成n个数据元素空间(0号单元不用) */
if(!(ST).elem)
{
printf("ERRORn");
exit(0);
} /*内存分配失败结束程序*/
for(i=1;i<=n;i++)
{
scanf("%d",&temp);
*(ST.elem+i)=temp; /* 依次赋值给ST */
}
ST.length=n;
}
int Search_Seq(SSTable &ST,ElemType key)
{ /* 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为 */
/* 该元素在表中的位置，否则为0。算法9.1 */
int i=1;
for(int i=1;i<=ST.length;i++){
if(ST.elem[i]==key)
return i;
}
return 0;
}
int main()
{
SSTable ST;
int loc,key;
int n;
scanf("%d",&n);
Creat_Seq(ST,n);
//printf("Please input the key value：");
scanf("%d",&key);
loc = Search_Seq(ST,key);
if(loc!=0)
printf("The element position is %d.n",loc);
else
printf("The element is not exist.n");
return 0;
}实验5.2
8621 二分查找
时间限制:1000MS 代码长度限制:10KB
提交次数:4655 通过次数:1446
题型: 编程题 语言: G++;GCC
Description
编写Search_Bin函数，实现在一个递增有序数组ST中采用折半查找法确定元素位置的算法.
输入格式
第一行:元素个数n 第二行：依次输入n个元素的值（有序） 第三行：输入要查找的关键字key的值
输出格式
输出分两种情形： 1.如果key值存在，则输出其在表中的位置x(表位置从0开始),格式为The element position is x. 2.如果key值不存在输出："The element is not exist."
输入样例
6 1 3 5 7 9 10 5
输出样例
The element position is 2.
#include"stdio.h"
#include"stdlib.h"
#include <iostream>
using namespace std;
int main()
{
int n,k,flag=0;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cin>>k;
for(int i=0;i<n;i++)
{
if(a[i]==k){
printf("The element position is %d.",i);
flag=1;
break;}
}
if(flag==0)
printf("The element is not exist.");
return 0;
}实验5.3
8622 哈希查找
时间限制:1000MS 代码长度限制:10KB
提交次数:2013 通过次数:1250
题型: 编程题 语言: G++;GCC
Description
使用哈希函数：H(k)=3*k MOD length，并采用开放定址法处理冲突。试对输入的关键字序列构造哈希表，哈希表长度为length，求等概率情况下查找成功的平均查找长度，并设计构造哈希表的完整的算法。本题给出部分代码，请补全Hash函数和解决冲突的collison函数。
#include"malloc.h" /* malloc()等 */
#include"stdlib.h" /* exit() */
#include"stdio.h"
#define EQ(a,b) ((a)==(b))
#define SUCCESS 1
#define UNSUCCESS 0
#define NULLKEY -1 /*哈希表无元素时值为-1*/
typedef int ElemType;
int length;
typedef struct
{
ElemType *elem; /* 数据元素存储基址，动态分配数组 */
int count; /* 当前数据元素个数 */
}HashTable;
void InitHashTable(HashTable *H)
{ /* 操作结果: 构造一个长度为length的哈希表,length为全局变量 */
int i;
(*H).count=0; /* 当前元素个数为0 */
(*H).elem=(ElemType*)malloc(length*sizeof(ElemType));
if(!(*H).elem)
exit(0); /* 存储分配失败 */
for(i=0;i<length;i++)
(*H).elem[i]=NULLKEY; /* 未填记录的标志 */
}
unsigned Hash(ElemType K)
{ /* 一个简单的哈希函数*/
}
void collision(int *p) /*线性探测再散列 */
{ /* 开放定址法处理冲突 */
}
int SearchHash(HashTable H,ElemType K,int *p,int *c)
{ /* 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据 */
/* 元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS */
/* c用以计冲突次数，其初值置零，供建表插入时参考。算法9.17 */
*p=Hash(K); /* 求得哈希地址 */
while(H.elem[*p]!=NULLKEY&&!EQ(K,H.elem[*p]))
{ /* 该位置中填有记录,并且关键字不相等 */
(*c)++;
if(*c<length)
collision(p); /* 求得下一探查地址p */
else
break;
}
if EQ(K,H.elem[*p])
return SUCCESS; /* 查找成功，p返回待查数据元素位置 */
else
return UNSUCCESS; /* 查找不成功(H.elem[p].key==NULLKEY)，p返回的是插入位置 */
}
int InsertHash(HashTable *H,ElemType e)
{ /* 查找不成功时插入数据元素e到开放定址哈希表H中，并返回查找长度 */
int c,p;
c=0;
if(SearchHash(*H,e,&p,&c)) /* 表中已有与e有相同关键字的元素 */
printf("哈希表中已有元素%d。n",e);
else{ /* 插入e */
(*H).elem[p]=e;
++(*H).count;
}
return c+1; /*查找长度为冲突次数加1*/
}
void TraverseHash(HashTable H)
{ /* 按哈希地址的顺序打印哈希表，无元素位置用X表示 */
int i;
printf("HashTable Address:0～%dn",length-1);
for(i=0;i<length;i++)
if(H.elem[i]==NULLKEY) /* 有数据 */
printf("X ");
else
printf("%d ",H.elem[i]);
printf("n");
}
main()
{
float i=0,j=0;
ElemType e;
HashTable H;
//printf("Input Table length:");
scanf("%d",&length);
InitHashTable(&H);
//printf("Input key words sequence, -1 conclusion input：");
scanf("%d",&e);
while(e!=-1)
{
j ++; /*j记录输入元素个数*/
i = i + InsertHash(&H,e); /*i记录查找长度的和*/
scanf("%d",&e);
}
TraverseHash(H);
printf("Average search length=%fn",i/j);
}
输入格式
第一行：输入哈希表的长度； 第二行：输入关键字序列，用空格分隔，-1结束(-1不作为关键字)。
输出格式
第一行：输出哈希表里的数据，未使用的单元用X表示； 第二行：输出平均查找长度,格式为"Average search length="。
输入样例
11 22 41 53 46 30 13 1 67 -1
输出样例
22 X 41 30 1 53 46 13 67 X X Average search length=2.000000
#include"cstdlib" /* exit() */
#include"cstdio"
#define EQ(a,b) ((a)==(b))
#define SUCCESS 1
#define UNSUCCESS 0
#define NULLKEY -1 /*哈希表无元素时值为-1*/
typedef int ElemType;
int length;
typedef struct
{
ElemType *elem; /* 数据元素存储基址，动态分配数组 */
int count; /* 当前数据元素个数 */
}HashTable;
void InitHashTable(HashTable *H)
{ /* 操作结果: 构造一个长度为length的哈希表,length为全局变量 */
int i;
(*H).count=0; /* 当前元素个数为0 */
(*H).elem=(ElemType*)malloc(length*sizeof(ElemType));
if(!(*H).elem)
exit(0); /* 存储分配失败 */
for(i=0;i<length;i++)
(*H).elem[i]=NULLKEY; /* 未填记录的标志 */
}
unsigned Hash(ElemType K)///这个函数要填
{ /* 一个简单的哈希函数*/
int p;
p=(3*K)%length;
return p;
}
void collision(int *p) /*线性探测再散列 */
{ /* 开放定址法处理冲突 */
///这个函数要填
*p=(*p+1)%length;
}
int SearchHash(HashTable H,ElemType K,int *p,int *c)
{ /* 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据 */
/* 元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS */
/* c用以计冲突次数，其初值置零，供建表插入时参考。算法9.17 */
*p=Hash(K); /* 求得哈希地址 */
while(H.elem[*p]!=NULLKEY&&!EQ(K,H.elem[*p]))
{ /* 该位置中填有记录,并且关键字不相等 */
(*c)++;
if(*c<length)
collision(p); /* 求得下一探查地址p */
else
break;
}
if EQ(K,H.elem[*p])
return SUCCESS; /* 查找成功，p返回待查数据元素位置 */
else
return UNSUCCESS; /* 查找不成功(H.elem[p].key==NULLKEY)，p返回的是插入位置 */
}
int InsertHash(HashTable *H,ElemType e)
{ /* 查找不成功时插入数据元素e到开放定址哈希表H中，并返回查找长度 */
int c,p;
c=0;
if(SearchHash(*H,e,&p,&c)) /* 表中已有与e有相同关键字的元素 */
printf("哈希表中已有元素%d。n",e);
else{ /* 插入e */
(*H).elem[p]=e;
++(*H).count;
}
return c+1; /*查找长度为冲突次数加1*/
}
void TraverseHash(HashTable H)
{ /* 按哈希地址的顺序打印哈希表，无元素位置用X表示 */
int i;
///printf("HashTable Address:0～%dn",length-1);这个要删掉
for(i=0;i<length;i++)
if(H.elem[i]==NULLKEY) /* 有数据 */
printf("X ");
else
printf("%d ",H.elem[i]);
printf("n");
}
int main()///加int和return 0;
{
float i=0,j=0;
ElemType e;
HashTable H;
//printf("Input Table length:");
scanf("%d",&length);
InitHashTable(&H);
//printf("Input key words sequence, -1 conclusion input：");
scanf("%d",&e);
while(e!=-1)
{
j ++; /*j记录输入元素个数*/
i = i + InsertHash(&H,e); /*i记录查找长度的和*/
scanf("%d",&e);
}
TraverseHash(H);
printf("Average search length=%fn",i/j);
return 0;
}实验6.1
8638 直接插入排序
时间限制:1000MS 代码长度限制:10KB
提交次数:2050 通过次数:1393
题型: 编程题 语言: G++;GCC
Description
用函数实现直接插入排序，并输出每趟排序的结果.
输入格式
第一行：键盘输入待排序关键的个数n 第二行：输入n个待排序关键字，用空格分隔数据
输出格式
每行输出一趟排序结果，数据之间用一个空格分隔
输入样例
10 5 4 8 0 9 3 2 6 7 1
输出样例
4 5 8 0 9 3 2 6 7 1 4 5 8 0 9 3 2 6 7 1 0 4 5 8 9 3 2 6 7 1 0 4 5 8 9 3 2 6 7 1 0 3 4 5 8 9 2 6 7 1 0 2 3 4 5 8 9 6 7 1 0 2 3 4 5 6 8 9 7 1 0 2 3 4 5 6 7 8 9 1 0 1 2 3 4 5 6 7 8 9
#include"cstdio"
#include <iostream>
using namespace std;
int main()
{
int n,j;
cin>>n;
int a[n];
a[0]=n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=2;i<=n;i++)
{
if(a[i-1]>a[i])///此时a[i]为小数，需要调动
{
a[0]=a[i];///将a[i]保存在a[0]里
a[i]=a[i-1];
for(j=i-1;a[j]>a[0];j--)
{
a[j]=a[j-1];
}
a[j+1]=a[0];///此时a[j]<=a[0]
}
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
printf("n");
}
return 0;
}实验6.2
8639 折半插入排序
时间限制:1000MS 代码长度限制:10KB
提交次数:1738 通过次数:1371
题型: 编程题 语言: G++;GCC
Description
用函数实现折半插入排序，并输出每趟排序的结果.
输入格式
第一行：键盘输入待排序关键的个数n 第二行：输入n个待排序关键字，用空格分隔数据
输出格式
每行输出一趟排序结果，数据之间用一个空格分隔
输入样例
10 5 4 8 0 9 3 2 6 7 1
输出样例
4 5 8 0 9 3 2 6 7 1 4 5 8 0 9 3 2 6 7 1 0 4 5 8 9 3 2 6 7 1 0 4 5 8 9 3 2 6 7 1 0 3 4 5 8 9 2 6 7 1 0 2 3 4 5 8 9 6 7 1 0 2 3 4 5 6 8 9 7 1 0 2 3 4 5 6 7 8 9 1 0 1 2 3 4 5 6 7 8 9
#include"cstdio"
#include <iostream>
using namespace std;
int main()
{
int n,j;
cin>>n;
int a[n];
a[0]=n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=2;i<=n;i++)
{
if(a[i-1]>a[i])///此时a[i]为小数，需要调动
{
a[0]=a[i];///将a[i]保存在a[0]里
a[i]=a[i-1];
for(j=i-1;a[j]>a[0];j--)
{
a[j]=a[j-1];
}
a[j+1]=a[0];///此时a[j]<=a[0]
}
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
printf("n");
}
return 0;
}实验6.3
8640 希尔(shell)排序
时间限制:1000MS 代码长度限制:10KB
提交次数:1858 通过次数:1304
题型: 编程题 语言: G++;GCC
Description
用函数实现希尔(shell)排序，并输出每趟排序的结果,初始增量d=n/2,其后d=d/2
输入格式
第一行：键盘输入待排序关键的个数n 第二行：输入n个待排序关键字，用空格分隔数据
输出格式
每行输出一趟排序结果，数据之间用一个空格分隔
输入样例
10 5 4 8 0 9 3 2 6 7 1
输出样例
3 2 6 0 1 5 4 8 7 9 1 0 3 2 4 5 6 8 7 9 0 1 2 3 4 5 6 7 8 9
#include <iostream>
#include <cstdio>
using namespace std;
int n,a[100005];
void ShellInsert(int a[],int d)
{
for(int i=d+1;i<=n;i++)
{
if(a[i-d]>a[i])
{
int j;
a[0]=a[i];
a[i]=a[i-d];
for(j=i-d;j>0 && a[0]<a[j];j=j-d )
a[j]=a[j-d];
a[j+d]=a[0];///此时a[j]<=a[0]
}
}
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
printf("n");
}
void ShellSort(int n)
{
int d=n/2;
while(d>=1)
{
ShellInsert(a,d);
//print();
d=d/2;
}
}
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
cin >> a[i];
ShellSort(n);
return 0;
}实验6.4
8641 冒泡排序
时间限制:1000MS 代码长度限制:10KB
提交次数:3093 通过次数:1361
题型: 编程题 语言: G++;GCC
Description
用函数实现冒泡排序，并输出每趟排序的结果(要求当一趟冒泡过程中不再有数据交换，则排序结束)
输入格式
第一行：键盘输入待排序关键的个数n 第二行：输入n个待排序关键字，用空格分隔数据
输出格式
每行输出每趟排序结果，数据之间用一个空格分隔
输入样例
10 5 4 8 0 9 3 2 6 7 1
输出样例
4 5 0 8 3 2 6 7 1 9 4 0 5 3 2 6 7 1 8 9 0 4 3 2 5 6 1 7 8 9 0 3 2 4 5 1 6 7 8 9 0 2 3 4 1 5 6 7 8 9 0 2 3 1 4 5 6 7 8 9 0 2 1 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int n;
cin >> n;
int a[n];
for(int i=0;i<n;i++)
cin >> a[i];
for(int i=0;i<n-1;i++)
{
int flag=0;
for(int j=1;j<n;j++)
{
if(a[j-1]>a[j])
{
int k;
k=a[j];
a[j]=a[j-1];
a[j-1]=k;
flag=1;
}
}
for(int j=0;j<n;j++)
{
printf("%d ",a[j]);
}
if(flag==0)
break;
printf("n");
}
return 0;
}实验6.5
8642 快速排序
时间限制:1000MS 代码长度限制:10KB
提交次数:2105 通过次数:1352
题型: 编程题 语言: G++;GCC
Description
用函数实现快速排序，并输出每次分区后排序的结果
输入格式
第一行：键盘输入待排序关键的个数n 第二行：输入n个待排序关键字，用空格分隔数据
输出格式
每行输出每趟排序的结果，数据之间用一个空格分隔
输入样例
10 5 4 8 0 9 3 2 6 7 1
输出样例
1 4 2 0 3 5 9 6 7 8 0 1 2 4 3 5 9 6 7 8 0 1 2 4 3 5 9 6 7 8 0 1 2 3 4 5 9 6 7 8 0 1 2 3 4 5 8 6 7 9 0 1 2 3 4 5 7 6 8 9 0 1 2 3 4 5 6 7 8 9
#include <iostream>
using namespace std;
int n,a[100005];
int kuaipai(int i,int j)
{
a[0]=a[i];///用a[0]暂存基准点，这个在while循环前面的
while(i<j)
{
while(i<j&&a[j]>=a[0])
j--;
a[i]=a[j];///此时a[i]空，把a[j]填进去
while(i<j&&a[i]<=a[0])
i++;///此时a[j]空，把a[i]填进去
a[j]=a[i];///此时a[j]空，把a[i]填进去
}
a[i]=a[0];///归位
return i;
}
void th(int i,int j)
{
if(i<j)
{
int k;
k=kuaipai(i,j);
for(int r=1;r<=n;r++)
{
printf("%d ",a[r]);
}
printf("n");
th(i,k-1);
th(k+1,j);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
th(1,n);
return 0;
}实验6.6
8643 简单选择排序
时间限制:1000MS 代码长度限制:10KB
提交次数:2235 通过次数:1301
题型: 编程题 语言: G++;GCC
Description
用函数实现简单选择排序，并输出每趟排序的结果
输入格式
第一行：键盘输入待排序关键的个数n 第二行：输入n个待排序关键字，用空格分隔数据
输出格式
每行输出每趟排序的结果，数据之间用一个空格分隔
输入样例
10 5 4 8 0 9 3 2 6 7 1
#include"stdlib.h"
#include"stdio.h"
#include <iostream>
#include <algorithm>
typedef int ElemType;
using namespace std;
int a[100005],n;
void th()
{
for(int i=1;i<n;i++)
{
a[0]=a[i];/*记录最小数*/
int k=i; /*记录最小数位置*/
for(int j=i+1;j<=n;j++)
{
if(a[0]>a[j])
{
a[0]=a[j];
k=j;
}
}
a[k]=a[i];
a[i]=a[0];
for(int j=1;j<=n;j++)
printf("%d ",a[j]);
printf("n");
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
th();
return 0;
}实验6.9
8646 基数排序
时间限制:1000MS 代码长度限制:10KB
提交次数:1581 通过次数:1071
题型: 编程题 语言: G++;GCC
Description
用函数实现基数排序，并输出每次分配收集后排序的结果
输入格式
第一行：键盘输入待排序关键的个数n 第二行：输入n个待排序关键字，用空格分隔数据
输出格式
每行输出每趟每次分配收集后排序的结果，数据之间用一个空格分隔
输入样例
10 278 109 063 930 589 184 505 069 008 083
输出样例
930 063 083 184 505 278 008 109 589 069 505 008 109 930 063 069 278 083 184 589 008 063 069 083 109 184 278 505 589 930
#include <iostream>
#include <algorithm>
using namespace std;
int x=1;
bool cmp(int a,int b)
{
a=a/x;
b=b/x;
return a%10<b%10;
}
int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
while(x<=100)
{
sort(a,a+n,cmp);
for(int i=0;i<n;i++)
{
printf("%03d ",a[i]);
}
printf("n");
x=x*10;
}
return 0;
}实验7.1
8647 实现图的存储结构
时间限制:1000MS 代码长度限制:10KB
提交次数:1499 通过次数:1092
题型: 编程题 语言: G++;GCC
Description
实现有向图的邻接矩阵存储结构。
输入格式
第一行：输入图的顶点个数n（各个顶点的默认编号为1~n）， 边的条数m。 第二 ~ m+1行：每行输入两个顶点编号i、j，表示连接顶点i到顶点j的一条边。
输出格式
分n行输出n*n的邻接矩阵，表示所输入的图存储，顶点i和顶点j之间如果有边相连，则输出1，没边相连则输出0。
输入样例
4 4 1 2 1 3 3 4 4 1
输出样例
0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,m,a,b;
cin>>n>>m;
int Map[100][100]={0};
for(int i=1;i<=m;i++)
{
cin>>a>>b;
Map[a][b]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",Map[i][j]);
}
printf("n");
}
return 0;
}实验7.2
8648 图的深度遍历
时间限制:1000MS 代码长度限制:10KB
提交次数:1821 通过次数:1037
题型: 编程题 语言: G++;GCC
Description
实现图的邻接表存储结构及一些基本操作函数。在此基础上实现图的深度遍历算法并加以测试。本题只给出部分代码,请补全内容。
#include"string.h"
#include"malloc.h" /* malloc()等 */
#include"stdio.h" /* EOF(=^Z或F6),NULL */
#include"stdlib.h" /* exit() */
typedef int InfoType; /* 顶点权值类型 */
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
typedef char VertexType[MAX_NAME]; /* 字符串类型 */
/*图的邻接表存储表示 */
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct ArcNode
{
int adjvex; /* 该弧所指向的顶点的位置 */
struct ArcNode *nextarc; /* 指向下一条弧的指针 */
InfoType *info; /* 网的权值指针） */
}ArcNode; /* 表结点 */
typedef struct
{
VertexType data; /* 顶点信息 */
ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */
}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */
typedef struct
{
AdjList vertices;
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
int kind; /* 图的种类标志 */
}ALGraph;
int LocateVex(ALGraph G,VertexType u)
{ /* 初始条件: 图G存在,u和G中顶点有相同特征 */
/* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
void CreateGraph(ALGraph *G)
{ /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图) */
int i,j,k;
int w; /* 权值 */
VertexType va,vb;
ArcNode *p;
//printf("Enter the type of map:(0~3): ");
scanf("%d",&(*G).kind);
//printf("Enter Vertex number,Arc number: ");
scanf("%d%d",&(*G).vexnum,&(*G).arcnum);
//printf("Enter %d Vertex :n",(*G).vexnum);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
{
scanf("%s",(*G).vertices[i].data);
(*G).vertices[i].firstarc=NULL;
}
//if((*G).kind==1||(*G).kind==3) /* 网 */
// printf("Enter order every arc weight,head and tail (Takes the gap by the blank space ):n");
//else /* 图 */
// printf("Enter order every arc head and tail (Takes the gap by the blank space ):n");
for(k=0;k<(*G).arcnum;++k) /* 构造表结点链表 */
{
if((*G).kind==1||(*G).kind==3) /* 网 */
scanf("%d%s%s",&w,va,vb);
else /* 图 */
scanf("%s%s",va,vb);
i=LocateVex(*G,va); /* 弧尾 */
j=LocateVex(*G,vb); /* 弧头 */
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if((*G).kind==1||(*G).kind==3) /* 网 */
{
p->info=(int *)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 图 */
p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */
(*G).vertices[i].firstarc=p;
if((*G).kind>=2) /* 无向图或网,产生第二个表结点 */
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if((*G).kind==3) /* 无向网 */
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 无向图 */
p->nextarc=(*G).vertices[j].firstarc; /* 插在表头 */
(*G).vertices[j].firstarc=p;
}
}
}
VertexType* GetVex(ALGraph G,int v)
{ /* 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */
if(v>=G.vexnum||v<0)
exit(0);
return &G.vertices[v].data;
}
int FirstAdjVex(ALGraph G,VertexType v)
{ /* 初始条件: 图G存在,v是G中某个顶点 */
/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
ArcNode *p;
int v1;
v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */
/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */
/* 若w是v的最后一个邻接点,则返回-1 */
ArcNode *p;
int v1,w1;
v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */
w1=LocateVex(G,w); /* w1为顶点w在图G中的序号 */
p=G.vertices[v1].firstarc;
while(p&&p->adjvex!=w1) /* 指针p不空且所指表结点不是w */
p=p->nextarc;
if(!p||!p->nextarc) /* 没找到w或w是最后一个邻接点 */
return -1;
else /* p->adjvex==w */
return p->nextarc->adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */
}
/*深度遍历*/
int visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量),未访问标记0，访问标记1 */
void(*VisitFunc)(char* v); /* 函数变量(全局量) */
void DFS(ALGraph G,int v)
{ /* 从第v个顶点出发递归地深度优先遍历图G。算法7.5 */
/* 设置访问标志为TRUE(已访问) */
/* 访问第v个顶点 */
/* 对v的尚未访问的邻接点w递归调用DFS */
}
void DFSTraverse(ALGraph G)
{ /* 对图G作深度优先遍历。算法7.4 */
/* 使用全局变量VisitFunc,使DFS不必设函数指针参数 */
/* 访问标志数组初始化 */
/* 对尚未访问的顶点调用DFS */
printf("n");
}
void print(char *i)
{
printf("%s ",i);
}
int main()
{
ALGraph g;
CreateGraph(&g);
DFSTraverse(g);
return 1;
}
输入格式
第一行：输入0到3之间整数(有向图:0,有向网:1,无向图:2,无向网:3)； 第二行：输入顶点数和边数； 第三行：输入各个顶点的值（字符型，长度〈3）；(遍历从输入的第一个顶点开始) 第四行：输入每条弧(边)弧尾和弧头(以空格作为间隔),如果是网还要输入权值；
输出格式
输出对图深度遍历的结果。
输入样例
0 3 3 a b c a b b c c b
输出样例
a b c
提示
注意题目的邻接表采用的是头插法，也就是后出现的边节点先被访问。
#include"string.h"
#include"stdio.h" /* EOF(=^Z或F6),NULL */
#include"stdlib.h" /* exit() */
typedef int InfoType; /* 顶点权值类型 */
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
typedef char VertexType[MAX_NAME]; /* 字符串类型 */
/*图的邻接表存储表示 */
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct ArcNode
{
int adjvex; /* 该弧所指向的顶点的位置 */
struct ArcNode *nextarc; /* 指向下一条弧的指针 */
InfoType *info; /* 网的权值指针） */
}ArcNode; /* 表结点 */
typedef struct
{
VertexType data; /* 顶点信息 */
ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */
}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */
typedef struct
{
AdjList vertices;
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
int kind; /* 图的种类标志 */
}ALGraph;
int LocateVex(ALGraph G,VertexType u)
{ /* 初始条件: 图G存在,u和G中顶点有相同特征 */
/* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
void CreateGraph(ALGraph *G)
{ /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图) */
int i,j,k;
int w; /* 权值 */
VertexType va,vb;
ArcNode *p;
//printf("Enter the type of map:(0~3): ");
scanf("%d",&(*G).kind);
//printf("Enter Vertex number,Arc number: ");
scanf("%d%d",&(*G).vexnum,&(*G).arcnum);
//printf("Enter %d Vertex :n",(*G).vexnum);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
{
scanf("%s",(*G).vertices[i].data);
(*G).vertices[i].firstarc=NULL;
}
//if((*G).kind==1||(*G).kind==3) /* 网 */
// printf("Enter order every arc weight,head and tail (Takes the gap by the blank space ):n");
//else /* 图 */
// printf("Enter order every arc head and tail (Takes the gap by the blank space ):n");
for(k=0;k<(*G).arcnum;++k) /* 构造表结点链表 */
{
if((*G).kind==1||(*G).kind==3) /* 网 */
scanf("%d%s%s",&w,va,vb);
else /* 图 */
scanf("%s%s",va,vb);
i=LocateVex(*G,va); /* 弧尾 */
j=LocateVex(*G,vb); /* 弧头 */
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if((*G).kind==1||(*G).kind==3) /* 网 */
{
p->info=(int *)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 图 */
p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */
(*G).vertices[i].firstarc=p;
if((*G).kind>=2) /* 无向图或网,产生第二个表结点 */
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if((*G).kind==3) /* 无向网 */
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 无向图 */
p->nextarc=(*G).vertices[j].firstarc; /* 插在表头 */
(*G).vertices[j].firstarc=p;
}
}
}
VertexType* GetVex(ALGraph G,int v)
{ /* 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */
if(v>=G.vexnum||v<0)
exit(0);
return &G.vertices[v].data;
}
int FirstAdjVex(ALGraph G,VertexType v)
{ /* 初始条件: 图G存在,v是G中某个顶点 */
/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
ArcNode *p;
int v1;
v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */
/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */
/* 若w是v的最后一个邻接点,则返回-1 */
ArcNode *p;
int v1,w1;
v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */
w1=LocateVex(G,w); /* w1为顶点w在图G中的序号 */
p=G.vertices[v1].firstarc;
while(p&&p->adjvex!=w1) /* 指针p不空且所指表结点不是w */
p=p->nextarc;
if(!p||!p->nextarc) /* 没找到w或w是最后一个邻接点 */
return -1;
else /* p->adjvex==w */
return p->nextarc->adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */
}
/*深度遍历*/
int visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量),未访问标记0，访问标记1 */
void(*VisitFunc)(char* v); /* 函数变量(全局量) */
void DFS(ALGraph G,int v)
{
/* 从第v个顶点出发递归地深度优先遍历图G。算法7.5 */
/*开始*/
/* 设置访问标志为TRUE(已访问) */
visited[v]=1;
/* 访问第v个顶点 */
printf("%s ",G.vertices[v].data);
/* 对v的尚未访问的邻接点w递归调用DFS */
for(int i=FirstAdjVex(G,G.vertices[v].data);i!=-1;i=NextAdjVex(G,G.vertices[v].data,G.vertices[i].data))
{
if(!visited[i])DFS(G,i);
}
/*结束*/
}
void DFSTraverse(ALGraph G)
{
/*开始*/
for(int i=0;i<G.vexnum;i++)
{
if(!visited[i])
DFS(G,i);
}
/*结束*/
/* 对图G作深度优先遍历。算法7.4 */
/* 使用全局变量VisitFunc,使DFS不必设函数指针参数 */
/* 访问标志数组初始化 */
/* 对尚未访问的顶点调用DFS */
printf("n");
}
void print(char *i)
{
printf("%s ",i);
}
int main()
{
ALGraph g;
CreateGraph(&g);
DFSTraverse(g);
return 1;
}实验6.3
8649 图的广度遍历
时间限制:1000MS 代码长度限制:10KB
提交次数:1573 通过次数:975
题型: 编程题 语言: G++;GCC
Description
使用图的深度遍历实现的邻接表存储结构和基本操作函数，在此基础上实现图的广度遍历算法并加以测试。注意正确使用队列存储结构。
输入格式
第一行：输入0到3之间整数(有向图:0,有向网:1,无向图:2,无向网:3)； 第二行：输入顶点数和边数； 第三行：输入各个顶点的值（字符型，长度〈3）；(遍历从输入的第一个顶点开始) 第四行：输入每条弧(边)弧尾和弧头(以空格作为间隔),如果是网还要输入权值；
输出格式
输出对图广度遍历的结果
输入样例
0 3 3 a b c a b b c c b
输出样例
a b c
提示
注意题目的邻接表采用头插法，也就是后出现的边节点插入到邻接表的表头。
#include <iostream>
#include <vector>
using namespace std;
int book[10000]={0};
vector<int>e[10000];
void dfs(int temp)
{
cout<<(char)(temp+'a')<<" ";
int len=e[temp].size();
for(int i=0;i<len;i++)
{
int k=e[temp][i];
if(book[k]==0)
{
book[k]=1;
dfs(k);
}
}
}
int main()
{
int t,n,m,temp;
cin>>t>>n>>m;
for(int i=0;i<n;i++)
{
char o;
cin>>o;
}
for(int i=0;i<m;i++)
{
char x,y;
cin>>x>>y;
int a=(char)(x-'a');
int b=(char)(y-'a');
if(i==0)
temp=i;
if(t<=1)
{
e[a].insert(e[a].begin(),b);
}
else
{
e[a].insert(e[a].begin(),b);
e[b].insert(e[b].begin(),a);
}
}
book[temp]=1;
dfs(temp);
return 0;
}