數(shù)據(jù)結(jié)構(gòu)算法實驗內(nèi)容與指導(dǎo)

1、PAGE PAGE 47數(shù)據(jù)結(jié)構(gòu)算法實驗內(nèi)容與指導(dǎo)實驗?zāi)康模簩谐Ｓ盟惴ň帉懗沙绦?，上機調(diào)試，驗證算法的正確性，同時理解數(shù)據(jù)結(jié)構(gòu)對于軟件開發(fā)的意義。同時又能復(fù)習(xí)C+語言的重點與難點，熟悉vc+6.0調(diào)試環(huán)境，掌握一個完整程序的構(gòu)成，為今后軟件設(shè)計打下基礎(chǔ)。實驗要求：熟練掌握c+面象對象的編程思想及vc+6.0上機調(diào)試環(huán)境。實驗內(nèi)容：（1）線性表順序存儲（順序表類）的插入、刪除等操作的實現(xiàn)（2）線性表鏈?zhǔn)酱鎯Γ▎捂湵眍悾┑慕?、插入、刪除等操作的實現(xiàn)（3）特殊線性表進棧、退棧操作的實現(xiàn)（4）順序查找及二分查找算法的實現(xiàn)（5）常用的幾種排序算法的實現(xiàn)（6）二叉樹的建立、遍歷算法的實現(xiàn)（7）圖的鄰

2、接矩陣的建立，及遍歷算法實現(xiàn)實驗一：線性表順序存儲（順序表類）的插入、刪除等操作的實現(xiàn)/SeqList.hclass SeqListprotected:DataType *list;/數(shù)組int maxSize;/最大元素個數(shù)int size;/當(dāng)前元素個數(shù)public:SeqList(int max=0); /構(gòu)造函數(shù)SeqList(void); /析構(gòu)函數(shù)int Size(void) const;/取當(dāng)前數(shù)據(jù)元素個數(shù)void Insert(const DataType& item, int i);/插入DataType Delete(const int i);/刪除DataType Get

3、Data(int i) const;/取數(shù)據(jù)元素;SeqList:SeqList(int max)/構(gòu)造函數(shù)maxSize = max;size = 0;list = new DataTypemaxSize;SeqList:SeqList(void)/析構(gòu)函數(shù)delete list;int SeqList:Size(void) const/取當(dāng)前數(shù)據(jù)元素個數(shù)return size;void SeqList:Insert(const DataType& item, int i)/插入/在指定位置i前插入一個數(shù)據(jù)元素itemif (size = maxSize) cout 順序表已滿無法插入！ e

4、ndl;exit(0);if(i size)/參數(shù)正確與否判斷cout 參數(shù)i越界出錯! i; j-) listj = listj-1; listi = item;/在i位置插入itemsize+;/當(dāng)前元素個數(shù)加1DataType SeqList:Delete(const int i)/刪除/刪除指定位置i的數(shù)據(jù)元素，刪除的元素由函數(shù)返回if (size = 0)cout 順序表已空無元素可刪！ endl;exit(0);if(i size - 1)/參數(shù)正確與否判斷cout參數(shù)i越界出錯!endl;exit(0);DataType x = listi;/取到要刪除的元素/從i+1至size

5、-1逐個元素前移for(int j = i;j size-1; j+) listj = listj+1;size-;/當(dāng)前元素個數(shù)減1return x;/返回刪除的元素DataType SeqList:GetData(int i) const/取數(shù)據(jù)元素/取位置i的數(shù)據(jù)元素，取到的數(shù)據(jù)元素由函數(shù)返回if(i size - 1)/參數(shù)正確與否判斷cout 參數(shù)i越界出錯! endl;exit(0);return listi;/返回取到的元素/ExamTest1.cpp#include #include typedef int DataType;/定義具體問題元素的數(shù)據(jù)類型#include Seq

6、List.hvoid main(void)SeqList myList(100);/定義順序表類對象myListint n = 10, x; for(int i = 0; i n; i+) /在myList中順序插入10個元素cout “請輸入插入元素x的值”x;mylist.Insert(x,i);myList.Delete(4);/刪除myList中數(shù)據(jù)元素5for(i = 0; i myList.Size(); i+)/依次取myList中的元素并顯示cout myList.GetData(i) ;分析討論：問題1：請分析上述主函數(shù)的功能及運行結(jié)果；問題2:完成P41例2-2建立學(xué)生情況

7、表實驗。/ExamTest2.cpp#include #include struct StudentTypelong number;/學(xué)號數(shù)據(jù)項char name10;/姓名數(shù)據(jù)項char sex3;/性別數(shù)據(jù)項int age;/年齡數(shù)據(jù)項;/結(jié)構(gòu)體StudentTypetypedef StudentType DataType;/定義DataType為StudentType數(shù)據(jù)類型#include SeqList.h/包含順序表文件void main(void)SeqList myList(100);StudentType x3 = 2000001, 張三, 男, 20, 2000002, 李

8、四, 男, 21,2000003, 王五, 女, 22;int n = 3;DataType s; for(int i = 0; i n; i+) /在myList中順序插入n個元素myList.Insert(xi, i);for(i = 0; i myList.Size(); i+)/依次取myList中的元素并顯示s = myList.GetData(i);cout s.number s.sex s.age endl;實驗二：線性表鏈?zhǔn)酱鎯Γ▎捂湵眍悾┑慕?、插入、刪除等操作的實現(xiàn)/LinList.htemplate class LinList;/前視定義,否則友元無法定義template

9、 /模板類型為Tclass ListNodefriend class LinList;/定義類LinList為友元private:ListNode *next; /指向下一結(jié)點的指針T data;/定義為公有成員方便使用public:/構(gòu)造函數(shù)1,用于構(gòu)造頭結(jié)點ListNode(ListNode *ptrNext = NULL)next = ptrNext;/構(gòu)造函數(shù)2,用于構(gòu)造其他結(jié)點ListNode(const T& item, ListNode *ptrNext = NULL)data = item;next = ptrNext;ListNode(void)/析構(gòu)函數(shù);/單鏈表類的定義t

10、emplate class LinListprivate:ListNode *head;/頭指針int size;/當(dāng)前的數(shù)據(jù)元素個數(shù)ListNode *Index(int i);/定位public:LinList(void);/構(gòu)造函數(shù)LinList(void);/析構(gòu)函數(shù)int ListSize(void) const;/取當(dāng)前數(shù)據(jù)元素個數(shù)void Insert(const T& item, int i);/前插T Delete(int i);/刪除T GetData(int i);/取元素; /單鏈表類的實現(xiàn) template LinList:LinList(void)/構(gòu)造函數(shù)head

11、 = new ListNode();/頭指針指向頭結(jié)點size = 0;/size的初值為0template LinList:LinList(void)/析構(gòu)函數(shù) ListNode *p, *q;p = head;/p指向第一個結(jié)點while(p != NULL)/循環(huán)釋放結(jié)點空間直至初始化狀態(tài)q = p;p = p-next;delete q;size = 0;/結(jié)點個數(shù)置為初始化值0head = NULL;template ListNode *LinList:Index(int i)/定位/返回指向第i個數(shù)據(jù)元素結(jié)點的指針/參數(shù)i的取值范圍為：-1isize-1；i=-1時返回頭指針if(

12、i size-1)cout 參數(shù)i越界出錯！ endl;exit(0);if(i = -1) return head;/i為-1時返回頭指針headListNode *p = head-next;/p指向第一個數(shù)據(jù)元素結(jié)點int j = 0;/從0開始計數(shù)while(p != NULL & j next;j+;return p;/返回第i個結(jié)點的指針template int LinList:ListSize(void) const/取當(dāng)前數(shù)據(jù)元素個數(shù)并返回return size;template void LinList:Insert(const T& item, int i)/插入/在第i個

13、結(jié)點后插入一個元素值為item的新結(jié)點/參數(shù)i的取值范圍為：0isizeif(i size)cout 參數(shù)i越界出錯！ endl;exit(0);ListNode *p = Index(i - 1);/p為指向第i-1個結(jié)點的指針/構(gòu)造新結(jié)點p，p的data域值為item，next域值為 p-nextListNode *q = new ListNode(item, p-next);p-next = q;/新結(jié)點插入第i個結(jié)點前size+;/元素個數(shù)加1template T LinList:Delete(int i)/刪除/刪除第i個數(shù)據(jù)元素并返回。參數(shù)i的取值范圍為：0isize-1if(si

14、ze = 0) cout 鏈表已空無元素可刪！ endl;exit(0);if(i size-1)cout 參數(shù)i越界出錯！ endl;exit(0);ListNode *s, *p = Index(i - 1);/p為指向第i-1個結(jié)點指針s = p-next;/s指向第i個結(jié)點p-next = p-next-next;/第i個結(jié)點脫鏈T x = s-data;delete s;/釋放第i個結(jié)點空間size-;/結(jié)點個數(shù)減1return x;/返回第i個結(jié)點的data域值template T LinList:GetData(int i)/取數(shù)據(jù)元素/取第i個數(shù)據(jù)元素并返回。參數(shù)i的取值范圍為

15、：0isize-1if(i size-1)cout 參數(shù)i越界出錯！ endl;exit(0);ListNode *p = Index(i);/p指向第i個結(jié)點return p-data;/ExamTest3.cpp#include #include #include LinList.hvoid main(void) LinList myList; Int s=10,20,30,40,50,60,70,80,90,100,n=10;Int temp;For(int I=0;In;I+) MyList.Insert(sI,I); MyList.Delete(4);For(I=0;ImyList.

16、Size();I+) temp=myList.GetData(i); couttemp” “;問題1：請分析上述主函數(shù)的功能及運行結(jié)果；實驗三：各種排序算法的實驗/sort.h#include #include void InsertSort (DataType a, int n)/用直接插入法對a0-an-1排序int i, j;DataType temp;for(i=0; i -1 & temp.key = aj.key)aj+1 = aj;j-;aj+1 = temp;void ShellSort (datatype a, int n, int d, int numOfD)/用希爾排序法

17、對記錄a0-an-1排序/各組內(nèi)采用直接插入法排序int i, j, k, m, span;datatype temp;for(m = 0; m numOfD; m+)span = dm;for(k = 0; k span; k+)for(i = k; i -1 & temp.key = aj.key)aj+span = aj;j = j-span;aj+span = temp;void SelectSort(datatype a, int n)/*用直接選擇排序法對a0-an-1排序*/int i, j, small;datatype temp;for(i=0; i n-1; i+)smal

18、l = i;for(j = i+1; j n; j+)if(aj.key asmall.key) small=j;if(small != i)temp = ai;ai = asmall;asmall = temp;void BubbleSort(datatype a, int n)/用冒泡排序法對a0-an-1排序int i, j, flag=1;datatype temp;for(i = 1; i n & flag = 1; i+)flag = 0;for(j = 0; j aj+1.key)flag = 1;temp = aj;aj = aj+1;aj+1 = temp;void Quic

19、kSort(datatype a, int low, int high)/用遞歸方法對對象alow-ahigh進行快速排序int i, j;datatype temp;i = low;j = high;temp = alow;while(i j)/在數(shù)組的右端掃描while(i j & temp.key = aj.key) j-;if(i j)ai = aj;i+;/在數(shù)組的左端掃描while(i j & ai.key temp.key) i+;if(i j)aj = ai;j-;ai = temp;/對子對象數(shù)組進行遞歸快速排序if(low i) QuickSort(a, low, i-1)

20、;if(i high) QuickSort(a, j+1, high);void Merge(DataType a, int n, DataType swap, int k)/k為有序子數(shù)組的長度，一次二路歸并排序后的有序子序列存于數(shù)組swap中int m = 0, u1,l2,i,j,u2;int l1 = 0;/第一個有序子數(shù)組下界為0while(l1+k = n-1)l2 = l1 + k;/計算第二個有序子數(shù)組下界u1 = l2 - 1;/計算第一個有序子數(shù)組上界u2 = (l2+k-1 = n-1)? l2+k-1: n-1;/計算第二個有序子數(shù)組上界/兩個有序子數(shù)組合并for(i

21、= l1, j = l2; i = u1 & j = u2; m+)if(ai.key = aj.key)swapm = ai;i+;elseswapm=aj;j+;/子數(shù)組2已歸并完，將子數(shù)組1中剩余的元素存放到數(shù)組swap中while(i = u1)swapm = ai;m+;i+;/子數(shù)組1已歸并完，將子數(shù)組2中剩余的元素存放到數(shù)組swap中while(j = u2)swapm = aj;m+;j+;l1 = u2 + 1;/將原始數(shù)組中只夠一組的數(shù)據(jù)元素順序存放到數(shù)組swap中for(i = l1; i n; i+, m+) swapm = ai;void MergeSort(Data

22、Type a, int n)int i, k = 1;/歸并長度從1開始DataType *swap = new DataTypen;/申請動態(tài)數(shù)組空間while(k n)Merge(a, n, swap, k);/調(diào)用歸并函數(shù)Merge(a, n, swap, k)for(i = 0; i n; i+)ai = swapi; /將元素從臨時數(shù)組swap放回數(shù)組a中k = 2 * k; /歸并長度加倍delete swap;/釋放動態(tài)數(shù)組空間/exam.cpp#include #include #define N 8typedef int KeyType;struct DataTypeKeyT

23、ype key;#include Sort.hvoid main(void)DataType test8;int dN,I=0,p,cnt=0,low,high; char c;cout”請輸入”N”個”endl;for(I=0;ItestI;cout”請選擇排序方式”endl;cout”1-直接插入排序”endl;cout”2-希爾排序”endl;cout”3-直接選擇排序”endl;cout”4-冒泡排序”endl;cout”5-快速排序”endl;cout”6-歸并排序”endl;cout”0-退出”c;switch( c) case 1: InsertSort(test,N);brea

24、k; case 2:p=N; while(p/2)!=1) dI=p/2; cnt+;p=p/2;I+;dI=1;cnt+;ShellSort(text,N,d,cnt);break;case 3:SelectSort(test,N);break;case 4:BubbleSort(text,N);break;case 5: low=0;high=N-1;QuickSort(text,low,high); break;case 6:MergeSort(text,N);break;case 0: exit(0);break;附錄資料:不需要的可以自行刪除 libxml2應(yīng)用實例Libxml2 是

25、一個xml的c語言版的解析器，本來是為Gnome項目開發(fā)的工具，是一個基于MIT License的免費開源軟件。它除了支持c語言版以外，還支持c+、PHP、Pascal、Ruby、Tcl等語言的綁定，能在Windows、Linux、Solaris、MacOsX等平臺上運行。功能還是相當(dāng)強大的，相信滿足一般用戶需求沒有任何問題。二、 Libxml2安裝：一般如果在安裝系統(tǒng)的時候選中了所有開發(fā)庫和開發(fā)工具的話(Fedora Core系列下)，應(yīng)該不用安裝，下面介紹一下手動安裝： 1) 從xmlsoft站點或ftp()站點下載libxml壓縮包(libxml2-xxxx.tar.gz)2) 對壓縮包

26、進行解壓縮 tar xvzf libxml2-xxxx.tar.gz3) 進入解壓縮后的文件夾中運行 ./configure -prefix /home/user/myxml/xmlinst(此處為待安裝的路徑)或者直接使用 ./configure make make install 4) 添加路徑 export PATH=/home/user/myxml/xmlinst/bin:$PATH 說明：為了結(jié)構(gòu)清晰，最好將libxml2不安裝在解壓目錄中。安裝完成后就可以使用簡單的代碼解析XML文件，包括本地和遠程的文件，但是在編碼上有一些問題。Libxml默認只支持UTF8的編碼，無論輸入輸出都

27、是UTF-8，所以如果你解析完一個XML得到的結(jié)果都是UTF8的，如果需要輸出GB2312或者其它編碼，需要ICONV來做轉(zhuǎn)碼(生成UTF8編碼的文件也可以用它做),如果系統(tǒng)中沒有安裝iconv的話，需要安裝libiconv。 1) 下載libiconv壓縮包(例如libiconv-1.11.tar.gz) 2) 對壓縮包進行解壓縮tar xvzf libiconv-1.11.tar.gz 3) 進入解壓縮后的文件夾中運行 ./configure make make install三、關(guān)于XML：在開始研究 Libxml2 庫之前，先了解一下XML的相關(guān)基礎(chǔ)。XML 是一種基于文本的格式，它可

28、用來創(chuàng)建能夠通過各種語言和平臺訪問的結(jié)構(gòu)化數(shù)據(jù)。它包括一系列類似 HTML 的標(biāo)記，并以樹型結(jié)構(gòu)來對這些標(biāo)記進行排列。例如，可參見清單 1 中介紹的簡單文檔。為了更清楚地顯示 XML 的一般概念，下面是一個簡化的XML文件。清單 1. 一個簡單的 XML 文件 root delete 10清單 1 中的第一行是 XML 聲明，它告訴負責(zé)處理 XML 的應(yīng)用程序，即解析器，將要處理的 XML 的版本。大部分的文件使用版本 1.0 編寫，但也有少量的版本 1.1 的文件。它還定義了所使用的編碼。大部分文件使用 UTF-8，但是，XML 設(shè)計用來集成各種語言中的數(shù)據(jù)，包括那些不使用英語字母的語言。接

29、下來出現(xiàn)的是元素。一個元素以開始標(biāo)記 開始(如 )，并以結(jié)束標(biāo)記 結(jié)束(如 )，其中使用斜線 (/) 來區(qū)別于開始標(biāo)記。元素是 Node 的一種類型。XML 文檔對象模型 (DOM) 定義了幾種不同的 Nodes 類型，包括:Elements(如 files 或者 age)Attributes(如 units)Text(如 root 或者 10)元素可以具有子節(jié)點。例如，age 元素有一個子元素，即文本節(jié)點 10。XML 解析器可以利用這種父子結(jié)構(gòu)來遍歷文檔，甚至修改文檔的結(jié)構(gòu)或內(nèi)容。LibXML2 是這樣的解析器中的其中一種，并且文中的示例應(yīng)用程序正是使用這種結(jié)構(gòu)來實現(xiàn)該目的。對于各種不同的

30、環(huán)境，有許多不同的解析器和庫。LibXML2 是用于 UNIX 環(huán)境的解析器和庫中最好的一種，并且經(jīng)過擴展，它提供了對幾種腳本語言的支持，如 Perl 和 Python。四、Libxml2中的數(shù)據(jù)類型和函數(shù)一個函數(shù)庫中可能有幾百種數(shù)據(jù)類型以及幾千個函數(shù)，但是記住大師的話，90%的功能都是由30%的內(nèi)容提供的。對于libxml2，我認為搞懂以下的數(shù)據(jù)類型和函數(shù)就足夠了。1）內(nèi)部字符類型xmlCharxmlChar是Libxml2中的字符類型，庫中所有字符、字符串都是基于這個數(shù)據(jù)類型。事實上它的定義是：xmlstring.htypedef unsigned char xmlChar;使用unsig

31、ned char作為內(nèi)部字符格式是考慮到它能很好適應(yīng)UTF-8編碼，而UTF-8編碼正是libxml2的內(nèi)部編碼，其它格式的編碼要轉(zhuǎn)換為這個編碼才能在libxml2中使用。還經(jīng)常可以看到使用xmlChar*作為字符串類型，很多函數(shù)會返回一個動態(tài)分配內(nèi)存的xmlChar*變量，使用這樣的函數(shù)時記得要手動刪除內(nèi)存。2） xmlChar相關(guān)函數(shù)如同標(biāo)準(zhǔn)c中的char類型一樣，xmlChar也有動態(tài)內(nèi)存分配、字符串操作等相關(guān)函數(shù)。例如xmlMalloc是動態(tài)分配內(nèi)存的函數(shù)；xmlFree是配套的釋放內(nèi)存函數(shù)；xmlStrcmp是字符串比較函數(shù)等等。基本上xmlChar字符串相關(guān)函數(shù)都在xmlstrin

32、g.h中定義；而動態(tài)內(nèi)存分配函數(shù)在xmlmemory.h中定義。3）xmlChar*與其它類型之間的轉(zhuǎn)換另外要注意，因為總是要在xmlChar*和char*之間進行類型轉(zhuǎn)換，所以定義了一個宏BAD_CAST，其定義如下：xmlstring.h#define BAD_CAST (xmlChar *)原則上來說，unsigned char和char之間進行強制類型轉(zhuǎn)換是沒有問題的。4）文檔類型xmlDoc、指針xmlDocPtrxmlDoc是一個struct，保存了一個xml的相關(guān)信息，例如文件名、文檔類型、子節(jié)點等等；xmlDocPtr等于xmlDoc*，它搞成這個樣子總讓人以為是智能指針，其實

33、不是，要手動刪除的。xmlNewDoc函數(shù)創(chuàng)建一個新的文檔指針。xmlParseFile函數(shù)以默認方式讀入一個UTF-8格式的文檔，并返回文檔指針。xmlReadFile函數(shù)讀入一個帶有某種編碼的xml文檔，并返回文檔指針；細節(jié)見libxml2參考手冊。xmlFreeDoc釋放文檔指針。特別注意，當(dāng)你調(diào)用xmlFreeDoc時，該文檔所有包含的節(jié)點內(nèi)存都被釋放，所以一般來說不需要手動調(diào)用xmlFreeNode或者xmlFreeNodeList來釋放動態(tài)分配的節(jié)點內(nèi)存，除非你把該節(jié)點從文檔中移除了。一般來說，一個文檔中所有節(jié)點都應(yīng)該動態(tài)分配，然后加入文檔，最后調(diào)用xmlFreeDoc一次釋放所有

34、節(jié)點申請的動態(tài)內(nèi)存，這也是為什么我們很少看見xmlNodeFree的原因。xmlSaveFile將文檔以默認方式存入一個文件。xmlSaveFormatFileEnc可將文檔以某種編碼/格式存入一個文件中。5）節(jié)點類型xmlNode、指針xmlNodePtr節(jié)點應(yīng)該是xml中最重要的元素了，xmlNode代表了xml文檔中的一個節(jié)點，實現(xiàn)為一個struct，內(nèi)容很豐富：tree.htypedef struct _xmlNode xmlNode;typedef xmlNode *xmlNodePtr;struct _xmlNode void *_private;/* application da

35、ta */ xmlElementType type; /* type number, must be second ! */ const xmlChar *name; /* the name of the node, or the entity */ struct _xmlNode *children;/* parent-childs link */ struct _xmlNode *last; /* last child link */ struct _xmlNode *parent;/* child-parent link */ struct _xmlNode *next; /* next

36、 sibling link*/ struct _xmlNode *prev; /* previous sibling link*/ struct _xmlDoc*doc;/* the containing document */ /* End of common part */ xmlNs *ns; /* pointer to the associated namespace */ xmlChar *content; /* the content */ struct _xmlAttr *properties;/* properties list */ xmlNs *nsDef; /* name

37、space definitions on this node */ void *psvi;/* for type/PSVI informations */ unsigned short line; /* line number */ unsigned short extra;/* extra data for XPath/XSLT */;可以看到，節(jié)點之間是以鏈表和樹兩種方式同時組織起來的，next和prev指針可以組成鏈表，而parent和children可以組織為樹。同時還有以下重要元素：節(jié)點中的文字內(nèi)容：content；節(jié)點所屬文檔：doc；節(jié)點名字：name；節(jié)點的namespace：

38、ns；節(jié)點屬性列表：properties；Xml文檔的操作其根本原理就是在節(jié)點之間移動、查詢節(jié)點的各項信息，并進行增加、刪除、修改的操作。xmlDocSetRootElement函數(shù)可以將一個節(jié)點設(shè)置為某個文檔的根節(jié)點，這是將文檔與節(jié)點連接起來的重要手段，當(dāng)有了根結(jié)點以后，所有子節(jié)點就可以依次連接上根節(jié)點，從而組織成為一個xml樹。6）節(jié)點集合類型xmlNodeSet、指針xmlNodeSetPtr節(jié)點集合代表一個由節(jié)點組成的變量，節(jié)點集合只作為Xpath的查詢結(jié)果而出現(xiàn)（XPATH的介紹見后面），因此被定義在xpath.h中，其定義如下：/* A node-set (an unordered

39、 collection of nodes without duplicates).*/typedef struct _xmlNodeSet xmlNodeSet;typedef xmlNodeSet *xmlNodeSetPtr;struct _xmlNodeSet int nodeNr; /* number of nodes in the set */ int nodeMax; /* size of the array as allocated */ xmlNodePtr *nodeTab;/* array of nodes in no particular order */ /* with

40、_ns to check wether namespace nodes should be looked at */;可以看出，節(jié)點集合有三個成員，分別是節(jié)點集合的節(jié)點數(shù)、最大可容納的節(jié)點數(shù)，以及節(jié)點數(shù)組頭指針。對節(jié)點集合中各個節(jié)點的訪問方式很簡單，如下：xmlNodeSetPtr nodeset = XPATH查詢結(jié)果;for (int i = 0; i nodeNr; i+)nodeset-nodeTabi;注意，libxml2是一個c函數(shù)庫，因此其函數(shù)和數(shù)據(jù)類型都使用c語言的方式來處理。如果是c+，我想我寧愿用STL中的vector來表示一個節(jié)點集合更好，而且沒有內(nèi)存泄漏或者溢出的擔(dān)憂。

41、五、使用Libxml2項目中要實現(xiàn)一個管理XML文件的后臺程序，需要對XML文件進行創(chuàng)建，解析，修改，查找等操作，下面介紹如何利用libxml2提供的庫來實現(xiàn)上述功能。1、創(chuàng)建XML文檔：我們使用xmlNewDoc()來創(chuàng)建XML文檔，然后使用xmlNewNode(),xmlNewChild(),xmlNewProp(),xmlNewText()等函數(shù)向XML文件中添加節(jié)點及子節(jié)點，設(shè)置元素和屬性，創(chuàng)建完畢后用xmlSaveFormatFileEnc()來保存XML文件到磁盤(該函數(shù)可以設(shè)置保存XML文件時的編碼格式)。示例1： #include #include #include int m

42、ain(int argc, char *argv) xmlDocPtr doc = NULL; /* document pointer */ xmlNodePtr root_node = NULL, node = NULL, node1 = NULL;/* node pointers */ / Creates a new document, a node and set it as a root node doc = xmlNewDoc(BAD_CAST 1.0); root_node = xmlNewNode(NULL, BAD_CAST root); xmlDocSetRootElemen

43、t(doc, root_node); /creates a new node, which is attached as child node of root_node node. xmlNewChild(root_node, NULL, BAD_CAST node1,BAD_CAST content of node1); / xmlNewProp() creates attributes, which is attached to an node. node=xmlNewChild(root_node, NULL, BAD_CAST node3, BAD_CASTnode has attri

44、butes); xmlNewProp(node, BAD_CAST attribute, BAD_CAST yes); /Here goes another way to create nodes. node = xmlNewNode(NULL, BAD_CAST node4); node1 = xmlNewText(BAD_CASTother way to create content); xmlAddChild(node, node1); xmlAddChild(root_node, node); /Dumping document to stdio or file xmlSaveForm

45、atFileEnc(argc 1 ? argv1 : -, doc, UTF-8, 1); /*free the document */ xmlFreeDoc(doc); xmlCleanupParser(); xmlMemoryDump();/debug memory for regression tests return(0); 編譯：gcc -o xmlCreator xmlCreator.cpp-I/home/usr/libxml2/xmlinst/include/libxml2/ -L /home/usr/libxml2/xmlinst/lib/ -lxml2 （綠色文字為libxm

46、l2安裝路徑） -I后接頭文件目錄 -L后接lib庫目錄2、解析XML文檔 解析文檔時僅僅需要文件名并只調(diào)用一個函數(shù)，并有錯誤檢查，常用的相關(guān)函數(shù)有xmlParseFile(),xmlParseDoc(),獲取文檔指針后，就可以使用xmlDocGetRootElement()來獲取根元素節(jié)點指針，利用該指針就可以在DOM樹里漫游了，結(jié)束后要調(diào)用xmlFreeDoc()釋放。示例2： xmlDocPtr doc; /定義解析文檔指針 xmlNodePtr cur; /定義結(jié)點指針(你需要它為了在各個結(jié)點間移動) xmlChar *key; doc = xmlReadFile(url, MY_EN

47、CODING, 256); /解析文件 /*檢查解析文檔是否成功，如果不成功，libxml將指一個注冊的錯誤并停止。一個常見錯誤是不適當(dāng)?shù)木幋a。XML標(biāo)準(zhǔn)文檔除了用UTF-8或UTF-16外還可用其它編碼保存。如果文檔是這樣，libxml將自動地為你轉(zhuǎn)換到UTF-8。更多關(guān)于XML編碼信息包含在XML標(biāo)準(zhǔn)中。*/ if (doc = NULL ) fprintf(stderr,Document not parsed successfully. n); return; cur = xmlDocGetRootElement(doc); /確定文檔根元素 /*檢查確認當(dāng)前文檔中包含內(nèi)容*/ if (

48、cur = NULL) fprintf(stderr,empty documentn); xmlFreeDoc(doc); return; /*在這個例子中，我們需要確認文檔是正確的類型?！皉oot”是在這個示例中使用文檔的根類型。*/ if (xmlStrcmp(cur-name, (const xmlChar *) root) fprintf(stderr,document of the wrong type, root node != root); xmlFreeDoc(doc); return; cur = cur-xmlChildrenNode; while(cur!=NULL) i

49、f (!xmlStrcmp(cur-name, (const xmlChar *)keyword) key = xmlNodeListGetString(doc, cur-xmlChildrenNode, 1); printf(keyword: %sn, key); xmlFree(key); cur = cur-next; xmlFreeDoc(doc); 3、修改XML元素及屬性等信息要修改XML文檔里的元素及屬性等信息，先需要解析XML文檔，獲得一個節(jié)點指針(xmlNodePtr node),利用該節(jié)點指針漫游DOM樹，就可以在XML文檔中獲取，修改，添加相關(guān)信息。示例3： 得到一個節(jié)點

50、的內(nèi)容： xmlChar *value = xmlNodeGetContent(node); 返回值value應(yīng)該使用xmlFree(value)釋放內(nèi)存得到一個節(jié)點的某屬性值： xmlChar *value = xmlGetProp(node, (const xmlChar *)prop1); 返回值需要xmlFree(value)釋放內(nèi)存 設(shè)置一個節(jié)點的內(nèi)容： xmlNodeSetContent(node, (const xmlChar *)test);設(shè)置一個節(jié)點的某屬性值： xmlSetProp(node, (const xmlChar *)prop1, (const xmlChar

51、*)v1); 添加一個節(jié)點元素： xmlNewTextChild(node, NULL, (const xmlChar *)keyword, (const xmlChar *)test Element); 添加一個節(jié)點屬性： xmlNewProp(node, (const xmlChar *)prop1, (const xmlChar *)test Prop);4、查找XML節(jié)點有時候?qū)σ粋€XML文檔我們可能只關(guān)心其中某一個或某幾個特定的Element的值或其屬性，如果漫游DOM樹將是很痛苦也很無聊的事，利用XPath可以非常方便地得到你想的Element。下面是一個自定義函數(shù)：示例4： xm

52、lXPathObjectPtr get_nodeset(xmlDocPtr doc, const xmlChar *xpath) xmlXPathContextPtr context; xmlXPathObjectPtr result; context = xmlXPathNewContext(doc); if (context = NULL) printf(context is NULLn); return NULL; result = xmlXPathEvalExpression(xpath, context); xmlXPathFreeContext(context); if (resu

53、lt = NULL) printf(xmlXPathEvalExpression return NULLn); return NULL; if (xmlXPathNodeSetIsEmpty(result-nodesetval) xmlXPathFreeObject(result); printf(nodeset is emptyn); return NULL; return result; 在doc指向的XML文檔中查詢滿足xpath表達式條件的節(jié)點，返回滿足這一條件的節(jié)點集合查詢條件xpath的寫法參見xpath相關(guān)資料。在查詢完畢獲取結(jié)果集后，就可以通過返回的 xmlXPathObjec

54、tPtr 結(jié)構(gòu)訪問該節(jié)點：示例5： xmlChar *xpath = (/root/node/key=keyword); xmlXPathObjectPtr app_result = get_nodeset(doc,xpath); if (app_result = NULL) printf(app_result is NULLn); return; int i = 0; xmlChar *value; if(app_result) xmlNodeSetPtr nodeset = app_result-nodesetval; for (i=0; i nodeNr; i+) cur = nodeset-nodeTabi; cur = cur-xmlChildrenNode; while(cur!=NULL) value = xmlGetProp(cur,(const xmlChar *)key); if (value != NULL) printf(value: %snn, d_ConvertCharset(utf-8, GBK, (char *)value); xmlFree(value); value = xmlNodeGetContent(cur); if (value != NULL) printf