#include<iostream>
#include<string>
using namespace std#define size 100class Node
{
public:
string data
Node * lchild, * rchild
public:
Node():lchild(NULL),rchild(NULL){ }
}class BiTree
{
public:
char a[size]
int length
Node * root
public:
BiTree(){ length=1}
void input()
void create(Node **p,int i)
void preOrder(Node *p)
int nodeNumber(Node *p)
void output(BiTree a)
}void BiTree::input()
{
cout<<"请输入节点字符(空格用#表示,输0结束):"<<endl
for(int i=1i<=sizei++)
{
cin>>a[i]
length++
if(a[i]=='0') return
}
}
void BiTree::create(Node **p,int i)
{
if (a[i] == '#') return
if (i>length) return
Node * temp = new Node()
temp->data = a[i]
*p = temp
create(&(*p)->lchild, 2*i)
create(&(*p)->rchild, 2*i+1)
}void BiTree::preOrder(Node *p)
{
if (p != NULL)
{
cout<<p->data
preOrder(p->lchild)
preOrder(p->rchild)
}
}int BiTree::nodeNumber(Node *p)
{
if(p == NULL) return 0
return (nodeNumber(p->lchild) + nodeNumber(p->rchild) + 1)
}void BiTree::output(BiTree a)
{
cout<<"前序遍历输出:"
a.preOrder(a.root)
cout<<"节点数:"<<a.nodeNumber(a.root)<<endl
}
int _tmain(int argc, _TCHAR* argv[])
{
BiTree a
a.input()
a.create(&a.root,1)
a.output(a)
return 0
}
1.建个堆栈,遇到( [ {就压栈,遇到) ] } 就看现在栈顶里放的跟遇到的是不是匹配。是,出栈,不是,报错。2.如果遇到) ] } 栈为空,报错
3.所有输入完成时栈不为空,报错
const
ok='OK'
wrong='Wrong'
ans:array[false..true]of string=(wrong,ok)
zuo=['[','(']you=[')',']']
var
s:string
i,j,k,n_b,n_e,m_b,m_e,top,zz:integer
a:array[1..10]of char
function zhankong:boolean
begin
exit(top=0)
end
function chuzhan:char
begin
dec(top)
exit(a[top+1])
end
procedure jinzhan(c:char)
begin
inc(top)a[top]:=c
end
function jishuan:boolean
var
c:char
begin
repeat
if s[zz]in zuo then jinzhan(s[zz])
if (s[zz]in you) and zhankong then exit(false)
if s[zz]in you then
begin c:=chuzhan
if ((c='(')and(s[zz]=')'))or((c='[')and(s[zz]=']'))
then zz:=zz else exit(false)
end
inc(zz)
until (zhankong)or(zz=length(s)+1)
if not( zhankong) then if not(zz=length(s)+1) then exit(false)
exit(true)
end
begin
readln(s)
n_b:=0
n_e:=0
m_b:=0
m_e:=0
for i:=1 to length(s) do
case s[i] of
'(':inc(n_b)
')':inc(n_e)
'[':inc(m_b)
']':inc(m_e)
end
if (n_b<>n_e)or(m_b<>m_e) then begin writeln(wrong)haltend
top:=0zz:=1
writeln(ans[jishuan])
end.
//线性表函数 *** 作#include <stdio.h>
#include <string.h>
#define MaxSize 30
#define Error 0
#define True 1
typedef char ElemType
typedef struct
{
ElemType elem[MaxSize]
int length
}SqList/*顺序表类型定义*/
void InitList(SqList * &L) /*初始化顺序表L*/
{
L = (SqList *)malloc(sizeof(SqList))
L ->length = 0
}
void DestroyList( SqList *L ) /*释放顺序表L*/
{
free(L)
}
int ListEmpty( SqList *L )/*判断顺序表L是否为空表*/
{
return( L ->length == 0)
}
int ListLength( SqList *L ) /*返回顺序表L的元素个数*/
{
return( L ->length)
}
void DispList( SqList *L )/*输出顺序表L*/
{
int i
if( ListEmpty(L))
return
for( i = 0i <L ->lengthi++ )
printf("%c", L ->elem[i])
printf("\n")
}
int GetElem( SqList *L, int i, ElemType &e) /*获取顺序表中的第i个元素*/
{
if( i <1 || i >L ->elem[i])
return Error
e = L ->elem[i - 1]
return True
}
int LocateElem( SqList *L, ElemType e) /*在顺序表中查找元素e*/
{
int i = 0
while( i <L ->length &&L ->elem[i] != e)
i++
if(i >= L ->length)
return Error
else
return i+1
}
int ListInsert( SqList * &L, int i, ElemType e) /*在顺序表L中第i个位置插入元素e*/
{
int j
if( i <1 || i >L ->length + 1)
return 0
i-- /*将顺序表位序转化为elem下标*/
for( j = L ->lengthj >ij--)/*将elem[i]及后面元素后移一个位置*/
L ->elem[j] = L ->elem[j - 1]
L ->elem[i] = e
L ->length++ /*顺序表长度增1*/
return True
}
int ListDelete( SqList * &L, int i, ElemType &e) /*顺序表L中删除第i个元素*/
{
int j
if( i <1 || i >L ->length)
return Error
i-- /*将顺序表位序转化为elem下标*/
e = L ->elem[i]
for(j = ij <L ->length - ij++)
L ->elem[j] = L ->elem[j + 1]
L ->length-- /*顺序表长度减1*/
return True
}
void main()
{
SqList *L
ElemType e
printf("(1)初始化顺序表L\n")
InitList(L)
printf("(2)依次采用尾插法插入a,b,c,d,e元素\n")
ListInsert(L, 1, 'a')
ListInsert(L, 2, 'b')
ListInsert(L, 3, 'c')
ListInsert(L, 4, 'd')
ListInsert(L, 5, 'e')
printf("(3)输出顺序表L:")
DispList(L)
printf("(4)顺序表L长度 = %d\n", ListLength(L))
printf("(5)顺序表L为%s\n", (ListEmpty(L) ?"空" :"非空"))
GetElem(L, 3, e)
printf("(6)顺序表L的第3个元素 = %c\n", e)
printf("(7)元素a的位置 = %d\n", LocateElem(L,'a'))
printf("(8)在第4个元素位置上插入f元素\n")
ListInsert(L, 4, 'f')
printf("(9)输出新的顺序表L:")
DispList(L)
printf("(10)删除L的第3个元素\n")
ListDelete(L, 3, e)
printf("(11)输出新的顺序表L:")
DispList(L)
printf("(12)释放顺序表L\n")
DestroyList(L)
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)