资料-树的孩子兄弟表示法及相关操作

[Copy to clipboard]View Code CPP

//basic.h 常用头文件 1

2

3 #include<string.h>

4 #include<ctype.h>

5 #include<malloc.h>

6 #include<limits.h>

7 #include<stdio.h>

8 #include<stdlib.h>

9 //#include<io.h>

#include<math.h> 10

//#include<process.h> 11

#include<iostream> 12

using namespace std; 13

14

15 //函数结果状态代码 16

#define TRUE 1 17

#define FALSE 0 18

#define OK 1 19

#define ERROR 0 20

#define INFEASIBLE -1 21

22

typedef int Status; 23

typedef int Boolean;

[Copy to clipboard]View Code CPP

1 // LinkQueue-define.h 队列的链式存储结构 2

3

4 typedef struct QNode

5 {

6 QElemType data;

7 QNode *next;

8 }*QueuePtr;

9

struct LinkQueue 10

{ 11

QueuePtr front,rear; 12

};

[Copy to clipboard]View Code CPP

1 //LinkQueue-operations.h 链队列的基本操作 2

3

4 Status InitQueue(LinkQueue &Q)

5 {//构造一个空队列Q。 6

7 if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)))) 8 exit(OVERFLOW);

9 Q.front->next=NULL;

10 return OK;

11 }

12

13 Status DestroyQueue(LinkQueue &Q)

14 {//销毁队列。 15

16 while(Q.front)

17 {

18 Q.rear=Q.front->next;

19 free(Q.front);

20 Q.front=Q.rear;

21 }

22 return OK;

23 }

24

25 Status ClearQueue(LinkQueue &Q)

26 {//清空队列。 27

28 QueuePtr p,q;

29 Q.rear=Q.front;

30 p=Q.front->next;

31 Q.front->next=NULL;

32 while(p)

33 {//释放每一个结点。 34

35 q=p;

36 p=p->next;

37 free(q);

38 }

39 return OK;

40 }

41

42 Status QueueEmpty(LinkQueue Q)

43 {//判空。 44

45 if(Q.rear==Q.front)

46 return TRUE;

47 else

48 return FALSE;

49 }

50

51 int QueueLength(LinkQueue Q)

52 {//求队列长度。 53

54 int i=0;

55 QueuePtr p;

56 p=Q.front;

57 while(Q.rear!=p)

58 {

59 i++;

60 p=p->next;

61 }

62 return i;

63 }

64

65 Status GetHead(LinkQueue Q,QElemType &e)

66 {//取队头元素，用e返回其值。 67

68 QueuePtr p;

69 if(Q.front==Q.rear)

70 return ERROR;

71 p=Q.front->next;

72 e=p->data;

73 return OK;

74 }

75

76 Status EnQueue(LinkQueue &Q,QElemType e)

77 {//将元素e入队。 78

79 QueuePtr p;

80 if(!(p=(QueuePtr)malloc(sizeof(QNode))))

81 exit(OVERFLOW);

82 p->data=e;

83 p->next=NULL;

84 Q.rear->next=p;

85 Q.rear=p; //注意此步！ 先连接上，后转移。 86

87 return OK;

88 }

89

90 Status DeQueue(LinkQueue &Q,QElemType &e)

91 {//队头元素出列，并用e返回其值。 92

93 QueuePtr p;

94 if(Q.front==Q.rear)

95 return ERROR;

96 p=Q.front->next;

97 e=p->data;

98 Q.front->next=p->next;

99 if(Q.rear==p) //队列中只有一个元素。 100

Q.rear=Q.front; 101

free(p); 102

return OK; 103

} 104

105

Status QueueTraverse(LinkQueue Q,void (*vi)(QElemType)) {//从队头到队尾，依次对队列中每个元素调用函数vi。

QueuePtr p;

p=Q.front->next;

while(p)

{

vi(p->data);

p=p->next;

}

printf("\n");

return OK;

}

看到这。。。 [Copy to clipboard]View Code CPP

// Children-Sibling-Tree-define.h 树的二叉链表（孩子兄弟）存1 储表示。 2 // typedef char TElemType; 3 typedef struct CSNode 4 { 5

6 TElemType data; //TElemType定义在后边。

7 CSNode *firstchild,*nextsibling;

}CSNode,*CSTree;

[Copy to clipboard]View Code CPP

1 // Children-Sibling-Tree-operations.h 树的孩子兄弟存储表示2

3 的常用操作。

4

5 Status InitTree(CSTree &T)

6 { //构造空树T。 7

8 T=NULL;

9 return OK;

10 }

11

12 void DestroyTree(CSTree &T)

13 { //销毁树T。 14

15 if(T)

16 {

17 if(T->firstchild)

18 DestroyTree(T->firstchild);

19 if(T->nextsibling)

20 DestroyTree(T->nextsibling);

21 free(T);

22 T=NULL;

23 }

24 }

25

26 typedef CSTree QElemType;

27 #include"LinkQueue-define.h"

28 #include"LinkQueue-operations.h"

29

30 Status CreateTree(CSTree &T)

31 { //根据孩子兄弟法建立树T。 32

33 char c[20]; //临时存放孩子结点（设不超过20个）的值。 34

35 CSTree p,p1;

36 LinkQueue q;

37 int i,l;

38 InitQueue(q);

39 printf("请输入根结点（字符型，空格为空）："); 40

41 scanf("%c%*c",&c[0]); //%*c用来接收回车符。 42

43 if(c[0]!=Nil) // 构造的树不空。 44

45 {

46 T=(CSTree)malloc(sizeof(CSNode));

47 T->data=c[0];

48 T->nextsibling=NULL; //建根结点。 49

50 EnQueue(q,T);

51 while(!QueueEmpty(q)) //队列中不空，未建立完毕。 52

53 {

54 DeQueue(q,p); //队中结点出队。 55

56 printf("请按长幼顺序输入结点%c的所有孩子：57

58 ",p->data);

59 gets(c);

60 l=strlen(c); //当前结点的孩子树为l。 61

62 if(l>0)

63 {//有孩子。 64

65

66 p1=p->firstchild=(CSTree)malloc(sizeof(CSNode)); 67 p1->data=c[0]; //为长子赋值。 68

69 for(i=1;i<l;i++)

70 …… 此处隐藏：3197字，全部文档内容请下载后查看。喜欢就下载吧 ……