數(shù)據(jù)結(jié)構(gòu)課設(shè)樹的應(yīng)用

1、南京航空航天大學(xué)第1頁共8頁?數(shù)據(jù)結(jié)構(gòu)?上機(jī)實驗報告年第 學(xué)期 第 次上機(jī)上機(jī)日期：年 月 日班號學(xué)號姓名一題目:二提醒：源代碼請聯(lián)微信xg取樹的應(yīng)用必做樹問題描述JSON JavaScript Object Notation是一種輕量級的數(shù)據(jù)交換格式,可以用來描述半結(jié)構(gòu)化的數(shù)據(jù).JSON格式中的根本單元是值value,出于簡化的目的此題 只涉及2種類型的值：*字符串string:字符串是由雙引號"括起來的一組字符可以為空.如 果字符串的內(nèi)容中出現(xiàn)雙引號,在雙引號前面加反斜杠,也就是用"表示；如果 出現(xiàn)反斜杠 ,那么用兩個反斜杠表示.反斜杠后面不能

2、出現(xiàn)"和以外的字符. 例如：""、"hello" 、""".*對象object:對象是一組鍵值對的無序集合可以為空.鍵值對表示對象 的屬性,鍵是屬性名,值是屬性的內(nèi)容.對象以左花括號開始,右花括號結(jié)束, 鍵值對之間以逗號,分隔.一個鍵值對的鍵和值之間以冒號：分隔.鍵必須是字符 用,同一個對象所有鍵值對的鍵必須兩兩都不相同；值可以是字符串,也可以是另一 個對象.例如：、"foo": "bar"、"Mon": "weekday", &quo

3、t;Tue": "weekday", "Sun": "weekend".除了字符串內(nèi)部的位置,其他位置都可以插入一個或多個空格使得 JSON的呈現(xiàn) 更加美觀,也可以在一些地方換行,不會影響所表示的數(shù)據(jù)內(nèi)容.例如,上面舉例的 最后一個JSON數(shù)據(jù)也可以寫成如下形式."Mon": "weekday","Tue": "weekday","Sun": "weekend"給出一個JSON格式描述的數(shù)據(jù),以及假設(shè)干查詢

4、,編程返回這些查詢的結(jié)果. 輸入格式第一行是兩個正整數(shù)n和m,分別表示JSON數(shù)據(jù)的行數(shù)和查詢的個數(shù).接下來n行,描述一個JSON數(shù)據(jù),保證輸入是一個合法的JSON對象.接下來m行,每行描述一個查詢.給出要查詢的屬性名,要求返回對應(yīng)屬性的第2頁(共8頁)內(nèi)容.需要支持多層查詢,各層的屬性名之間用小數(shù)點.連接.保證查詢的格式都是合法的.根本要求輸出格式對于輸入的每一個查詢,按順序輸出查詢結(jié)果,每個結(jié)果占一行.如果查詢結(jié)果是一個字符用,那么輸出 STRING<string> ,其中<string> 是字符用的值,中間用一個空格分隔.如果查詢結(jié)果是一個對象,那么輸出 OBJE

5、CT不需要輸出對象的內(nèi)容.如果查詢結(jié)果不存在,那么輸出 NOTEXIST樣例輸入10 5"firstName": "John","lastName": "Smith","address": "streetAddress": "2ndStreet","city": "NewYork","state": "NY","escaped": ""h

6、ello""firstNameaddressaddress.cityaddress.postalescaped樣例輸出STRING JohnOBJECTSTRING NewYorkNOTEXISTSTRING "hello"根本要求(1)要求從文本文件中輸入；(2)此題目其實就是一棵普通的樹(即每個結(jié)點的孩子數(shù)不固定,不能單純采用n叉樹來解決),可以考慮使用孩子兄弟表示法等進(jìn)行表示和存儲；(3)嚴(yán)格根據(jù)要求的輸入輸出格式進(jìn)行數(shù)據(jù)的輸入、輸出(練習(xí)CSP測試中的格式化輸入輸出的正確性)；(4)選做：使用圖形界面(或字符格式化擺成的樹形結(jié)構(gòu),參考 Linux

7、下的tree命第3頁(共8頁)令),以樹狀形式顯示輸入的JSON&式數(shù)據(jù).(二)算法思想：1 .首先對讀入的字符串處理,得到真正應(yīng)該需要的字符串,代碼實現(xiàn)如下Status Getchar(FILE *fp,char *b)(int i = 0;char a = fgetc(fp);while(a !='"')(if(a = '')(a = fgetc(fp);bi = a;i +;a = fgetc(fp); else(bi = a;i +;a = fgetc(fp);bi尸0'2 .得到字符串后,開始建立孩子-兄弟樹首先建立一個根結(jié)點

8、,值域設(shè)為Root,接著重新讀入,如果字符串之前的字符為“ 那么將這個字符設(shè)為根結(jié)點的兄弟,如果這個字符串之前的字符為“那么建立此結(jié)點的孩子,接著根據(jù)之前操作進(jìn)行,繼續(xù)讀,繼續(xù)建立結(jié)點,直到讀到“結(jié)束子樹的建立.CSTree IN(CSTree &T,FILE *fp,int number)第4頁共8頁(int i = number + 1;T = (CSTree)malloc(sizeof(Node);T->child=NULL;T->sibling=NULL;char c20="Root"strcpy(T->str,c);CSTree p;ch

9、ar a;char b20;while(a != '')(while(a !='"')(a = fgetc(fp);Getchar(fp,b);CreateCSTree(p,b);a = fgetc(fp);while(a != '"' && a != '')(a = fgetc(fp);if(a = 34)Getchar(fp,b);CreateCSTree(p->child,b);a = fgetc(fp);while(a != '"' &&

10、a != '')第5頁共8頁a = fgetc(fp);)else if(a = '')(IN(p->child,fp,i);)p->sibling = T->sibling;T->sibling = p;)return T;)3 .遍歷二叉樹,根據(jù)輸入的鍵值,找到對應(yīng)結(jié)點,然后取他的孩子結(jié)點判斷即可.如果孩子結(jié) 點是字符串那么輸出STRING字符串,如果孩子結(jié)點是字符“"那么輸出OBJECTchar a = 0;char b20;int i = 0;CSTree p = T->sibling;int j = 0;a =

11、fgetc(fp);while(a != '.'&& a != 10 && !feof(fp)bj = a;j +;a = fgetc(fp);)bj = '0'while(p != NULL)第6頁共8頁if(strcmp(b,p->str) = 0)(i +；break;)p = p->sibling;)if(i = 0)*count = 1;T = p;return a;)Status OUT(FILE *fp,CSTree T)(char a = 0;CSTree p = T;int *count = (int

12、*)malloc(sizeof(int);(*count) = 0;char c20 = "Root"a = fgetc(fp);while(!feof(fp)(p = T;(*count)=0;a = Judge(fp,p,count);if(a = 10)(if(*count) = 0)(第7頁共8頁if(strcmp(p->child->str,c) = 0)printf("OBJECTn");elseprintf("STRING %sn",p->child->str);else printf("

13、;NOTEXISTn");elsewhile(a != 10 && !feof(fp)p=p->child;a=Judge(fp,p,count);if(*count) = 0)if(strcmp(p->child->str,c) = 0)printf("OBJECTn");elseprintf("STRING %sn",p->child->str);else printf("NOTEXISTn");(三)運行結(jié)果以及結(jié)果分析：以下為輸入的內(nèi)容 10 5("firstN

14、ame": "John", "lastName": "Smith",第8頁共8頁"address": "streetAddress": "2ndStreet", "city": "NewYork", "state": "NY", "escaped": ""hello"" firstName address address.city addres