《数据结构》实验程序设计

《数据结构》实验程序设计,第1张

#include"stdafx.h"

#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)

}


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/yw/11153843.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-05-14
下一篇 2023-05-14

发表评论

登录后才能评论

评论列表(0条)

保存