{"id":286,"date":"2019-03-13T12:34:00","date_gmt":"2019-03-13T04:34:00","guid":{"rendered":"http:\/\/fankasy.xyz\/?p=286"},"modified":"2019-04-17T20:16:21","modified_gmt":"2019-04-17T12:16:21","slug":"%e5%b8%b8%e7%94%a8%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e5%ba%93","status":"publish","type":"post","link":"http:\/\/fankasy.xyz\/index.php\/2019\/03\/13\/%e5%b8%b8%e7%94%a8%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e5%ba%93\/","title":{"rendered":"\u5e38\u7528\u6570\u636e\u7ed3\u6784\u5e93"},"content":{"rendered":"

\u5c31\u8ddf\u6807\u9898\u5199\u7684\u4e00\u6837\u3002<\/p>\n

\u5806\u6808<\/h2>\n

Stack.h<\/h3>\n
#pragma once\r\n#include<stdio.h>\r\n#include<stdlib.h>\r\n\r\ntypedef int Elemtype ;\r\ntypedef struct\r\n{\r\n\tint maxSize;\r\n\tint loaded;\r\n\tElemtype *key;\r\n}*Stack;\r\n\r\nStack StackBuild(int max);\r\nvoid StackDestory(Stack s);\r\nint isSFull(Stack s);\r\nint isSEmpty(Stack s);\r\nvoid Stackin(Stack s, Elemtype key);\r\nElemtype Stackout(Stack s);\r\nElemtype Peek(Stack s);\r\nvoid StackClear(Stack s);\r\nint StackSize(Stack s);\r\n\r\n\r\n<\/pre>\n
Stack.c<\/h3>\n
#include\"Stack.h\"\r\n\r\n\r\nStack StackBuild(int max)\r\n{\r\n\tStack s = calloc(1,sizeof(Stack));\r\n\ts->loaded = 0;\r\n\ts->maxSize = max;\r\n\ts->key = calloc(1, sizeof(int) * (max+1));\r\n\ts->key[0] = INT_MAX;\r\n\treturn s;\r\n}\r\nvoid StackDestory(Stack s)\r\n{\r\n\tfree(s->key);\r\n\tfree(s);\r\n}\r\nint isSFull(Stack s)\r\n{\r\n\treturn s->maxSize == s->loaded ? 1 : 0;\r\n}\r\nint isSEmpty(Stack s)\r\n{\r\n\treturn !s->loaded;\r\n}\r\nvoid Stackin(Stack s, Elemtype key)\r\n{\r\n\tif (isFull(s))\r\n\t\treturn;\r\n\ts->key[++s->loaded] = key;\r\n}\r\nElemtype Stackout(Stack s)\r\n{\r\n\tif (isEmpty(s))\r\n\t\treturn NULL;\r\n\treturn s->key[s->loaded--];\r\n}\r\nElemtype Peek(Stack s)\r\n{\r\n\tif (isEmpty(s))\r\n\t\treturn;\r\n\treturn s->key[s->loaded];\r\n}\r\nvoid StackClear(Stack s)\r\n{\r\n\ts->loaded = 0;\r\n}\r\nint StackSize(Stack s)\r\n{\r\n\treturn s->loaded;\r\n}\r\n<\/pre>\n
\u961f\u5217<\/h2>\n
Queue.h<\/h3>\n
#pragma once\r\n#include\r\n#include\r\n\r\ntypedef int Elemtype ;\r\ntypedef struct\r\n{\r\n\tint maxSize;\r\n\tint loaded;\r\n\tint begin;\r\n\tint end;\r\n\tElemtype *key;\r\n}*Queue;\r\n\r\nQueue QueueBuild(int max);\r\nvoid QueueDestory(Queue q);\r\nint isQFull(Queue q);\r\nint isQEmpty(Queue q);\r\nvoid Queuein(Queue q, Elemtype key);\r\nElemtype Queueout(Queue q);\r\nvoid QueueClear(Queue q);\r\nint QueueSize(Queue q);\r\n\r\n<\/pre>\n
Queue.c<\/h3>\n
#include\"Queue.h\"\r\n\r\nQueue QueueBuild(int max)\r\n{\r\n\tQueue q = calloc(1,sizeof(Queue));\r\n\tq->loaded = q->begin = q->end = 0;\r\n\tq->maxSize = max;\r\n\tq->key = calloc(1, sizeof(int) * (max+1));\r\n\treturn q;\r\n}\r\nvoid QueueDestory(Queue q)\r\n{\r\n\tfree(q->key);\r\n\tfree(q);\r\n}\r\nint isQFull(Queue q)\r\n{\r\n\treturn q->loaded == q->maxSize? 1:0;\r\n}\r\nint isQEmpty(Queue q)\r\n{\r\n\treturn !q->loaded;\r\n}\r\nvoid Queuein(Queue q, Elemtype key)\r\n{\r\n\tif (isQFull(q))\r\n\t\treturn;\r\n\tq->key[(q->begin++)%q->maxSize]=key;\r\n\tq->loaded++;\r\n}\r\nElemtype Queueout(Queue q)\r\n{\r\n\tif (isQEmpty(q))\r\n\t\treturn -INT_MAX;\r\n\tq->loaded--;\r\n\treturn q->key[(q->end++)%q->maxSize];\r\n}\r\nvoid QueueClear(Queue s)\r\n{\r\n\ts->loaded = 0;\r\n}\r\nint QueueSize(Queue q)\r\n{\r\n\treturn q->loaded;\r\n}\r\n<\/pre>\n
 <\/p>\n
\u4e8c\u53c9\u6811\uff08\u904d\u5386\u548c\u521b\u5efa\uff09<\/h2>\n
BinaryTree.h<\/h3>\n
#pragma once\r\n#include\r\n#include\r\n\r\ntypedef int ElemType;\r\n\r\ntypedef struct BinaryTreeNode\/\/ P.75\r\n {\r\n ElemType Data;\r\n struct BinaryTreeNode *lChild, *rChild;\r\n }BinaryTreeNode;\r\n typedef BinaryTreeNode* BiTree, *TNode;\r\n\r\ntypedef struct BinaryTree\/\/ I made it, also shown in course slides\r\n {\r\n BinaryTreeNode *root;\r\n }BinaryTree;\r\n\r\n\r\n void PreOrderTransverse(BiTree t);\r\n void InOrderTransverse(BiTree t);\r\n void PostOrderTransverse(BiTree t);\r\n BinaryTreeNode* PreCreateBt(BinaryTreeNode *t);\r\n<\/pre>\n
BinaryTree.c<\/h3>\n
\/*\r\nI don't have the copyright of these code.\r\n*\/\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n \/\/ BinaryTree PreOrder\/InOrder\/PostOrder Traverse Demo Program\r\n \/\/ Please note: This is a minimal functional traverse program\r\n \/\/ that lacks most of the functions in ADT 5.2\r\n \/\/ I will made another full version of BinaryTree program\r\n#include \"BinaryTree.h\"\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n \/\/ I don\u2019t know why the author used \u201cBiTree\u201d here,\r\n \/\/ so I made a typedef in Line 17, as below:\r\n \/\/ typedef BinaryTreeNode* BiTree;\r\n \/\/ Program 5.1-5.3\r\n void PreOrderTransverse(BiTree t)\r\n {\r\n if(t == NULL)\r\n return;\r\n\r\nprintf(\u201c%c\u201d, t->Data);\r\n PreOrderTransverse(t->lChild);\r\n PreOrderTransverse(t->rChild);\r\n }\r\n\r\nvoid InOrderTransverse(BiTree t)\r\n {\r\n if(t == NULL)\r\n return;\r\n\r\nInOrderTransverse(t->lChild);\r\n printf(\u201c%c\u201d, t->Data);\r\n InOrderTransverse(t->rChild);\r\n }\r\n\r\nvoid PostOrderTransverse(BiTree t)\r\n {\r\n if(t == NULL)\r\n return;\r\n\r\nPostOrderTransverse(t->lChild);\r\n PostOrderTransverse(t->rChild);\r\n printf(\u201c%c\u201d, t->Data);\r\n }\r\n\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n \/\/ Before traverse, you need to create a BinaryTree first\r\n \/\/ Here we use PreOrder manner to create one\r\n \/\/ In this function, you can input a string like ABEH###C#D##MN###\r\n \/\/ Program 5.4\r\n BinaryTreeNode* PreCreateBt(BinaryTreeNode *t)\r\n {\r\n char ch;\r\n\r\nch = getchar();\r\n if(ch == \u2018#\u2019)\r\nt = NULL;\r\n else\r\n {\r\n t = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));\r\n t->Data = ch;\/\/ A mistake in textbook\r\n t->lChild = PreCreateBt(t->lChild);\r\n t->rChild = PreCreateBt(t->rChild);\r\n }\r\n\r\nreturn t;\r\n }\r\n\r\n<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
\u5c31\u8ddf\u6807\u9898\u5199\u7684\u4e00\u6837\u3002 \u5806\u6808 Stack.h #pragma once #include<stdio.h&g […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"_links":{"self":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/posts\/286"}],"collection":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/comments?post=286"}],"version-history":[{"count":0,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/posts\/286\/revisions"}],"wp:attachment":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/media?parent=286"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/categories?post=286"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/tags?post=286"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}