TYUT数据结构课设_输入的每一行都包含一条指令。每行都以一个字母(或者是“i”或者是 “d”)开头,后

作者：凡人多烦事01 | 2024-06-12 20:48:03

踩

输入的每一行都包含一条指令。每行都以一个字母(或者是“i”或者是 “d”)开头,后

- 以学习为目的，仅供参考

1. 字符串和堆栈

【问题描述】

编写一个程序，检查字符串是否包含正确嵌套和平衡的圆括号、方括号和花括号。

【基本要求】

运行程序时，输入一个包含圆括号、方括号和花括号的字符串，分析其中的圆括号、方括号和花括号是否正确嵌套和平衡。如果字符串是平衡的，程序将不输出任何内容，并以EXIT_SUCCESS状态退出。其他情况，将输出一条错误消息，并以失败状态退出。

在扫描字符串遇到(、[或{时，将该该括号入栈；遇到)、]或}时，将从栈中弹出顶部括号，并检查它是否与字符串中遇到的右括号匹配；如果括号不匹配，或者栈为空，程序将输出不匹配的括号和遇到的不匹配的括号的索引；如果扫描字符串结束时，栈不为空，输出信息： open:对应右括号列表。如表1-1所示。

输入	输出
)	0:)
([)]	2:)
([{	open:}])

代码


#include <bits/stdc++.h>
using namespace std;
#define MAXN 2000
char s[MAXN];
char stk[MAXN];
int top = 0;
int main()
{
    scanf("%s",s);
 
    for(int i = 0; i < strlen(s); i++){
        if(s[i] == '('){ stk[top++] = '('; }
        if(s[i] == '['){ stk[top++] = '['; }
        if(s[i] == '{'){ stk[top++] = '{'; }
        if(s[i] == ')'){
            if (top-1 >= 0 && stk[top-1] == '(' ){ top--; continue; }
            else{
                cout <<i <<":" <<s[i];
                return EXIT_FAILURE;
            }
        }
        if(s[i] == ']'){
            if (top-1 >= 0 && stk[top-1] == '[' ){ top--; continue; }
            else{
                cout <<i <<":" <<s[i];
                return EXIT_FAILURE;
            }
        }
        if(s[i] == '}'){
            if (top-1 >= 0 && stk[top-1] == '{' ){ top--; continue; }
            else{
                cout <<i <<":" <<s[i];
                return EXIT_FAILURE;
            }
        }
    }
    if (top != 0){
        cout <<"open:";
        for(int i = top-1; i >= 0; i--){
            if (stk[i] == '(') cout <<')';
            if (stk[i] == '[') cout <<']';
            if (stk[i] == '{') cout <<'}';
        }
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

2. 有序链表的维护

2.1 【问题描述】

编写一个程序，根据从标准输入接收的指令来维护和操作排序的链表。链表是按顺序维护的，这意味着链表中的数据在每次操作后都以递增的数字顺序存储。

请注意，在创建新节点时，需要使用malloc为它们分配空间；一旦不再需要任何已

分配的空间，就应该使用free将其释放。还要注意，链表不包含重复的值。

2.2 【基本要求】

链表支持两种操作指令。

插入n：向链表中添加一个整数n。如果链表中已经存在n，则它什么也不做。指令格式是一个i后跟一个空格和一个整数n。

删除n：从链表中删除一个整数n。如果链表中不存在n，它什么也不做。指令格式是d后跟一个空格和一个整数n。

在每个命令之后，程序将输出链表的长度，然后是链表的内容，按照从第一个(最小)到最后一个(最大)的顺序。

输入格式：输入的每一行都包含一条指令。每行都以一个字母(或者是“i”或者是 “d”)开头，后跟一个空格，然后是一个整数。以“i”开头的一行表示该整数应该插入链表中。以 “d”开头的一行表示应从链表中删除该整数。输入i和d以外的字符程序结束运行。

输出格式：执行每个指令后，程序将输出一行文本，其中包含链表的长度、一个冒号以及按顺序排列的链表元素，所有内容都用空格分隔。

代码


#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    int data;
    struct node *nxt;
}node;
 
typedef node *linklist;
int cnt;
 
void init(linklist &l){
    l = (linklist)malloc(sizeof(linklist));
    if(!l){
        puts("initial fail");
        exit(0);
    }
    l->data = 0;
    l->nxt = NULL;
}
 
void insert(linklist &l,int data){
    linklist p,x;
    p = l;
    while(p->nxt != NULL){
        if(p->data <= data && p->nxt->data >= data)
            break;
        p = p->nxt;
    }
    x = (linklist)malloc(sizeof(linklist));
    x->data = data;
    x->nxt = p->nxt;
    p->nxt = x;
    cnt++;
}
 
void del(linklist &l,int data){
    linklist p, temp;
    int ans = 0;
    p = l;
    //寻找要删除的节点
    while(p->nxt != NULL){
        if(p->nxt->data == data){
            temp = p->nxt;
            ans = 1;
            break;
        }
        p = p->nxt;
    }
    //未找到
    if(p->nxt == NULL)
        return;
    //删除释放节点
    if (ans){
        p->nxt = p->nxt->nxt;
        free(temp);
        cnt--;
    }
}
        
int main(){
    linklist L;
    init(L);
    char op;
    int num;
    while(scanf("%c %d",&op, &num)!=EOF){
        getchar();
        if(op =='d') del(L,num);
        if(op =='i') insert(L,num);
        printf("%d:",cnt);
        linklist p = L;
        for(int i = 1; i <= cnt; i++){
            p = p->nxt;
            printf(" %d",p->data);
        }
        putchar('\n');
    }
    return 0;
}
/*
i 5
d 3
i 3
i 500
d 5
*/

3. 二叉查找树操作

3.1 【问题描述】

编写一个操纵二叉查找树的程序。它将从标准输入接收命令，并将这些命令的响应打印到标准输出。

二叉查找树是一棵二叉树，它在内部节点存储整数值。特定节点的值大于存储在其

左侧子树中的每个值，小于存储在其右侧子树中的每个值。该树不包含重复值。

请注意，在创建新节点时，需要使用malloc为它们分配空间；一旦不再需要任何已

分配的空间，就应该使用free将其释放。

3.2 【基本要求】

操纵二叉查找树的命令有4个:

插入n：向树中添加一个值，如果还没有的话，新节点将始终作为现有节点的子节点或根节点添加，现有节点不会因为插入数据而改变或移动。如果n不存在，因此将被插入，程序打印插入；否则，它将打印不插入。指令格式是一个i后跟一个十进制整数n。

搜索n：在树中搜索值n。如果n存在，程序将打印存在；否则会打印缺席。指令格式是一个s后跟一个空格和一个整数n。

打印：空树(即空)被打印为空字符串。节点被打印为一个(，后跟左边的子树、该节点的项、右边的子树和)，没有空格。指令格式是一个p。例如，对应于图3-1的输出是((1)2((3(4))5(6)))

删除n：从树中删除一个值。删除二叉树排序中的节点有几种策略。如果一个节点没有子节点，可以简单地删除它；也就是说，指向它的指针可以更改为空指针。如果一个节点有一个子节点，它可以被那个子节点替换。如果一个节点有两个子节点，其值将被更改为其左子树中的最大元素，之前包含该值的节点将被删除。请注意，正在删除的值可能在根节点上。指令格式是一个d后跟一个空格和一个整数n。

代码


#include<bits/stdc++.h>
using namespace std;
 
typedef struct bnode{
	int data;
	struct bnode *lchild,*rchild;
}bnode;
typedef bnode *btree;
//递归打印路径 
void printbst(btree t){
	if(t == NULL)
		return;
	printf("(");
	printbst(t->lchild);
	printf("%d",t->data);
	printbst(t->rchild);
	printf(")");
}
 
int insert(btree t,btree fa,int data){
	if(t == NULL){
		btree x = (btree)malloc(sizeof(btree)); 
		x->lchild = NULL;
		x->rchild = NULL;
		x->data = data;
		if(data > fa->data) fa->rchild = x;
		else fa->lchild = x;
		return 1;
	}
	if(t->data==data) return 0;
	if(t->data>data) return insert(t->lchild,t,data);
	if(t->data<data) return insert(t->rchild,t,data);
}
 
int search(btree t,int data){
	if(t == NULL) return 0;
	if(t->data == data) return 1;
	if(t->data > data) return search(t->lchild,data);
	if(t->data < data) return search(t->rchild,data);
}
 
void del(btree t,btree fa){
	//没有子节点 
	if(t->lchild == NULL && t->rchild == NULL){
		free(t);
		if(fa->data > t->data) fa->lchild = NULL;
		else fa->rchild = NULL;
	}
	//子节点只有一个 
	else if(t->lchild == NULL){
		if(fa->data > t->data){
			fa->lchild = t->rchild;
			free(t);
		}
		else{
			fa->rchild = t->rchild;
			free(t);
		}
	}
	else if(t->rchild == NULL){
		if(fa->data > t->data){
			fa->lchild = t->lchild;
			free(t);
		}
		else{
			fa->rchild = t->lchild;
			free(t);
		}
	}
	//子节点都在，将子树中最大的元素变为根节点 
	else{
		btree p = t;
		while(p->rchild != NULL)	p = p->rchild;
		p->rchild = t->rchild;
		p->lchild = t->lchild;
		if(fa->data > t->data){
			fa->lchild = p;
			free(t);
		}
		else{
			fa->rchild = p;
			free(t);
		}
	}
}
//寻找要删除的节点 
int delsearch(btree t,btree fa,int data){
	if(t == NULL)
		return 0;
	 if(t->data == data)
	 	del(t,fa);
	if(t->data > data) return delsearch(t->lchild,t,data);
	if(t->data < data) return delsearch(t->rchild,t,data);
}
 
int main(){
	char op;
	int num;
	btree t = NULL;
	while(scanf("%c",&op) != EOF){
		if(op == 'p'){
			printbst(t);
			putchar('\n');
			getchar();
			continue;
		}
		scanf("%d",&num);
		if(op == 'i'){
			if(t == NULL){
				t = (btree)malloc(sizeof(btree)); 
				t->lchild = NULL;
				t->rchild = NULL;
				t->data = num;
				puts("inserted");
				getchar();
				continue;
			}
			if(insert(t,NULL,num))
				puts("inserted");
			else
				puts("not inserted");
		}
		if(op == 's'){
			if(search(t,num))
				puts("present");
			else
				puts("absent");
		}
		if(op == 'd'){
			if(delsearch(t,NULL,num))
				puts("deleted");
			else
				puts("not deleted");
		}
		getchar();
	}
	return 0;
}
/*
i 50
i 70
i 25
i 70
i 55
d 55
p
s 55
s 60
p
*/

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】