求数据结构题目答案

发布网友 发布时间：2022-04-23 11:57

我来回答

共1个回答

热心网友 时间：2023-06-24 23:32

#include "stdlib.h"
#include<stdio.h>

//1、
typedef struct TreeNode
{
int data;
TreeNode* leftChild;
TreeNode* rightChild;
}*Tree;

int CountTree(Tree t)
{
if(t==NULL)
return 0;
return 1+CountTree(t->leftChild)+CountTree(t->rightChild);
}
//2、
void CheckExp(char* expresion)
{
int bracket = 0;
char* exp = expresion;
while(*exp!=0)
{
if(*exp=='(')
bracket++;
if(*exp==')')
bracket--;
if(bracket<0)
{
printf("缺少左括号\n");
return;
}
exp++;
}
if(bracket>0)
printf("缺少右括号\n");
else
printf("括号配对\n");
}
//3、
#define M0 100
struct sqlist
{
int elem[M0+1];//M0为足够大的常数
int Length;
};
//其中数据从1号开始存放数据，0号单元用作哨兵？
//请采用插入排序的思想进行排序，写出排序算法并指出该算法时间度
void sort(sqlist &l)
{
if(l.Length<=0)
return;
int i=1;
int j=i+1;
int temp;
while(j<=l.Length)
{
l.elem[0]=l.elem[j];
while(l.elem[j]<l.elem[j-1])
{
temp=l.elem[j];
l.elem[j]=l.elem[j-1];
l.elem[j-1]=temp;
j--;
}
i++;
j=i+1;
}
}

int main()
{
//1
Tree tl = new TreeNode;
tl->data=1;
tl->leftChild = NULL;
tl->rightChild = NULL;
Tree t = new TreeNode;
t->data = 0;
t->leftChild = tl;
t->rightChild = NULL;
printf("二叉树t中的节点个数为：%d\n",CountTree(t));

//2
char* exp;
exp="(1+432*243)+((5-1)*234+(234*(24-234))))";
puts(exp);
CheckExp(exp);
exp="(1+432*243)+(((5-1)*234+(234*(24-234)))";
puts(exp);
CheckExp(exp);
exp="(1+432*243)+((5-1)*234+(234*(24-234)))";
puts(exp);
CheckExp(exp);

//3
sqlist l;
l.elem[0]=0;
l.elem[1]=23;
l.elem[2]=2;
l.elem[3]=10;
l.elem[4]=34;
l.elem[5]=50;
l.elem[6]=1220;
l.elem[7]=130;
l.elem[8]=77;
l.Length=8;
int i;
printf("排序前：");
for(i=1;i<=l.Length;i++)
printf("%d ",l.elem[i]);
printf("\n");
sort(l);
printf("排序后：");
for(i=1;i<=l.Length;i++)
printf("%d ",l.elem[i]);
printf("\n");

system("pause");
return 0;
}
插入排序算法有两层循环，外层循环共n-1次，内层循环次数在0~n-1之间。因此算法的时间复杂度为o(n^2)。