數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)指導(dǎo)書

1、 數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)指導(dǎo)書計算機(jī)與信息學(xué)院實(shí)驗(yàn)一 順序表【實(shí)驗(yàn)?zāi)康摹渴炀氄莆站€性表在順序存儲結(jié)構(gòu)上的基本操作?！緦?shí)驗(yàn)平臺】操作系統(tǒng)：Windows2000或Windows XP開發(fā)環(huán)境：C或C+【實(shí)驗(yàn)內(nèi)容及要求】順序表的查找、插入與刪除。設(shè)計算法，實(shí)現(xiàn)線性結(jié)構(gòu)上的順序表的產(chǎn)生以及元素的查找、插入與刪除。具體實(shí)現(xiàn)要求：從鍵盤輸入10個整數(shù)，產(chǎn)生順序表，并輸出結(jié)點(diǎn)值。從鍵盤輸入1個整數(shù)，在順序表中查找該結(jié)點(diǎn)。若找到，輸出結(jié)點(diǎn)的位置；若找不到，則顯示“找不到”。從鍵盤輸入2個整數(shù)，一個表示欲插入的位置i，另一個表示欲插入的數(shù)值x，將x插入在對應(yīng)位置上，輸出順序表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。從鍵盤輸入1

2、個整數(shù)，表示欲刪除結(jié)點(diǎn)的位置，輸出順序表所有結(jié)點(diǎn)值，觀察輸出結(jié)果?！緟⒖伎蚣堋?include #include /順序表的定義：#define ListSize 100/表空間大小可根據(jù)實(shí)際需要而定，這里假設(shè)為100typedef int DataType;/DataType可以是任何相應(yīng)的數(shù)據(jù)類型如int, float或chartypedef structDataType dataListSize;/向量data用于存放表結(jié)點(diǎn)int length;/當(dāng)前的表長度SeqList;void main()SeqList L;int i,x;int n=10;/欲建立的順序表長度L.length=

3、0;void CreateList(SeqList *L,int n);void PrintList(SeqList L,int n);int LocateList(SeqList L,DataType x);void InsertList(SeqList *L,DataType x,int i);void DeleteList(SeqList *L,int i);CreateList(&L,n);/建立順序表PrintList(L,n);/打印順序表printf(輸入要查找的值：);scanf(%d,&x);i=LocateList(L,x);/順序表查找printf(輸入要插入的位置：);

4、scanf(%d,&i);printf(輸入要插入的元素：);scanf(%d,&x);InsertList(&L,x,i);/順序表插入PrintList(L,n);/打印順序表printf(輸入要刪除的位置：);scanf(%d,&i);DeleteList(&L,i);/順序表刪除PrintList(L,n);/打印順序表/順序表的建立：void CreateList(SeqList *L,int n)/在此插入必要的語句/順序表的打印：void PrintList(SeqList L,int n)/在此插入必要的語句/順序表的查找：int LocateList(SeqList L,Da

5、taType x)/在此插入必要的語句/順序表的插入：void InsertList(SeqList *L,DataType x,int i)/在此插入必要的語句/順序表的刪除：void DeleteList(SeqList *L,int i)/在此插入必要的語句【實(shí)驗(yàn)報告】數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報告一學(xué)院： 班級： 學(xué)號： 姓名： 日期： 程序名： L2211.CPP 一、上機(jī)實(shí)驗(yàn)的問題和要求：順序表的查找、插入與刪除。設(shè)計算法，實(shí)現(xiàn)線性結(jié)構(gòu)上的順序表的產(chǎn)生以及元素的查找、插入與刪除。具體實(shí)現(xiàn)要求：從鍵盤輸入10個整數(shù)，產(chǎn)生順序表，并輸出結(jié)點(diǎn)值。從鍵盤輸入1個整數(shù)，在順序表中查找該結(jié)點(diǎn)。若找到，

6、輸出結(jié)點(diǎn)的位置；若找不到，則顯示“找不到”。從鍵盤輸入2個整數(shù)，一個表示欲插入的位置i，另一個表示欲插入的數(shù)值x，將x插入在對應(yīng)位置上，輸出順序表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。從鍵盤輸入1個整數(shù)，表示欲刪除結(jié)點(diǎn)的位置，輸出順序表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。二、源程序及注釋：三、運(yùn)行輸出結(jié)果：四、調(diào)試和運(yùn)行程序過程中產(chǎn)生的問題及采取的措施：實(shí)驗(yàn)二 鏈表【實(shí)驗(yàn)?zāi)康摹渴炀氄莆站€性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)上的基本操作?！緦?shí)驗(yàn)平臺】操作系統(tǒng)：Windows2000或Windows XP開發(fā)環(huán)境：C或C+【實(shí)驗(yàn)內(nèi)容及要求】單鏈表的查找、插入與刪除。設(shè)計算法，實(shí)現(xiàn)線性結(jié)構(gòu)上的單鏈表的產(chǎn)生以及元素的查找、插入與刪除。具體實(shí)

7、現(xiàn)要求：從鍵盤輸入20個整數(shù)，產(chǎn)生帶表頭的單鏈表，并輸出結(jié)點(diǎn)值。從鍵盤輸入1個整數(shù)，在單鏈表中查找該結(jié)點(diǎn)。若找到，則顯示“找到了”；否則，則顯示“找不到”。從鍵盤輸入2個整數(shù)，一個表示欲插入的位置i，另一個表示欲插入的數(shù)值x，將x插入在對應(yīng)位置上，輸出單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。從鍵盤輸入1個整數(shù)，表示欲刪除結(jié)點(diǎn)的位置，輸出單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果表中個結(jié)點(diǎn)值均不相同，輸出單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。刪除其中所有數(shù)據(jù)值為偶數(shù)的結(jié)點(diǎn)，輸出單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。把單鏈表變成帶表頭結(jié)點(diǎn)的循環(huán)鏈表，輸出循環(huán)單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果

8、。（）將單鏈表分解成兩個單鏈表A和B，使A鏈表中含有原鏈表中序號為奇數(shù)的元素，而B鏈表中含有原鏈表中序號為偶數(shù)的元素，且保持原來的相對順序，分別輸出單鏈表A和單鏈表B的所有結(jié)點(diǎn)值，觀察輸出結(jié)果。【參考框架】#include #include /單鏈表的定義：typedef int DataType;/DataType可以是任何相應(yīng)的數(shù)據(jù)類型如int, float或chartypedef struct node/結(jié)點(diǎn)類型定義DataType data;/結(jié)點(diǎn)的數(shù)據(jù)域struct node *next;/結(jié)點(diǎn)的指針域ListNode;typedef ListNode *LinkList;void

9、main()int i;DataType key,x;LinkList head;ListNode *p;LinkList CreateList(void);void PrintList(LinkList head);LinkList LocateNode(LinkList head,DataType key);LinkList GetNode(LinkList head,int i);void InsertList(LinkList head,DataType x,int i);void DeleteList(LinkList head,int i);void DeleteManyList(

10、LinkList head);void DeleteEvenList(LinkList head);void ChangeCircList(LinkList head);void PrintCircList(LinkList head);head=CreateList();/建立單鏈表PrintList(head);/打印單鏈表printf(輸入要查找的值：);scanf(%d,&key);p=LocateNode(head,key);/單鏈表查找printf(請輸入欲插入元素的位置：);scanf(%d,&i);printf(請輸入欲插入的元素：);scanf(%d,&x);InsertLi

11、st(head,x,i);/單鏈表插入PrintList(head);/打印單鏈表printf(請輸入欲刪除結(jié)點(diǎn)的位置：);scanf(%d,&i);DeleteList(head,i);/單鏈表刪除PrintList(head);/打印單鏈表DeleteManyList(head);/刪除重復(fù)值PrintList(head);/打印單鏈表DeleteEvenList(head);/刪除偶數(shù)值PrintList(head);/打印單鏈表ChangeCircList(head);/修改為循環(huán)單鏈表PrintCircList(head);/打印循環(huán)單鏈表/*void DivideList(Link

12、List head,LinkList *A,LinkList *B); /分割成兩個單鏈表DivideList(head, &A, &B);PrintList(A);PrintList(B);*/單鏈表的建立：LinkList CreateList(void)/在此插入必要的語句/單鏈表的打?。簐oid PrintList(LinkList head)/在此插入必要的語句/單鏈表的查找1：LinkList LocateNode(LinkList head,DataType key)/在此插入必要的語句/單鏈表的查找2：LinkList GetNode(LinkList head,int i)/

13、在此插入必要的語句/單鏈表的插入：void InsertList(LinkList head,DataType x,int i)/在此插入必要的語句/單鏈表的刪除：void DeleteList(LinkList head,int i)/在此插入必要的語句/刪除單鏈表中重復(fù)值：void DeleteManyList(LinkList head)/在此插入必要的語句/刪除單鏈表中偶數(shù)值：void DeleteEvenList(LinkList head)/在此插入必要的語句/修改為循環(huán)單鏈表：void ChangeCircList(LinkList head)/在此插入必要的語句/循環(huán)單鏈表的打

14、?。簐oid PrintCircList(LinkList head)/在此插入必要的語句/*/分割成兩個單鏈表void DivideList(LinkList head,LinkList *A,LinkList *B);/在此插入必要的語句*/【實(shí)驗(yàn)報告】數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報告二學(xué)院： 班級： 學(xué)號： 姓名： 日期： 程序名： L2311.CPP 一、上機(jī)實(shí)驗(yàn)的問題和要求：單鏈表的查找、插入與刪除。設(shè)計算法，實(shí)現(xiàn)線性結(jié)構(gòu)上的單鏈表的產(chǎn)生以及元素的查找、插入與刪除。具體實(shí)現(xiàn)要求：從鍵盤輸入20個整數(shù)，產(chǎn)生帶表頭的單鏈表，并輸出結(jié)點(diǎn)值。從鍵盤輸入1個整數(shù)，在單鏈表中查找該結(jié)點(diǎn)。若找到，則顯示“找

15、到了”；否則，則顯示“找不到”。從鍵盤輸入2個整數(shù)，一個表示欲插入的位置i，另一個表示欲插入的數(shù)值x，將x插入在對應(yīng)位置上，輸出單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。從鍵盤輸入1個整數(shù)，表示欲刪除結(jié)點(diǎn)的位置，輸出單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果表中個結(jié)點(diǎn)值均不相同，輸出單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。刪除其中所有數(shù)據(jù)值為偶數(shù)的結(jié)點(diǎn)，輸出單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。把單鏈表變成帶表頭結(jié)點(diǎn)的循環(huán)鏈表，輸出循環(huán)單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。（）將單鏈表分解成兩個單鏈表A和B，使A鏈表中含有原鏈表中序號為奇數(shù)的元素，而B鏈表中含有原鏈表中序號為偶數(shù)的元素，且保持

16、原來的相對順序，分別輸出單鏈表A和單鏈表B的所有結(jié)點(diǎn)值，觀察輸出結(jié)果。二、源程序及注釋：三、運(yùn)行輸出結(jié)果：四、調(diào)試和運(yùn)行程序過程中產(chǎn)生的問題及采取的措施：實(shí)驗(yàn)三 樹【實(shí)驗(yàn)?zāi)康摹渴炀氄莆赵阪準(zhǔn)蕉鏄湓诙骀湵泶鎯Y(jié)構(gòu)上的基本操作?！緦?shí)驗(yàn)平臺】操作系統(tǒng)：Windows2000或Windows XP開發(fā)環(huán)境：C或C+【實(shí)驗(yàn)內(nèi)容及要求】要求采用二叉鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，前序、中序和后序遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作等。具體實(shí)現(xiàn)要求：基于先序遍歷的構(gòu)造算法：輸入是二叉樹的先序序列，但必須在其中加入虛結(jié)點(diǎn)以示空指針的位置。假設(shè)虛結(jié)點(diǎn)輸入時用空格字符表示。用廣義表表示所建二叉樹。分別利

17、用前序遍歷、中序遍歷、后序遍歷所建二叉樹。求二叉樹結(jié)點(diǎn)總數(shù)，觀察輸出結(jié)果。求二叉樹葉子總數(shù)，觀察輸出結(jié)果。交換各結(jié)點(diǎn)的左右子樹，用廣義表表示法顯示新的二叉樹。（）二叉樹采用鏈接存儲結(jié)構(gòu)，其根結(jié)點(diǎn)指針為T，設(shè)計一個算法對這棵二叉樹的每個結(jié)點(diǎn)賦值：（注意要修改DataType類型）葉結(jié)點(diǎn)的值為3只有左孩子或右孩子的結(jié)點(diǎn)則其值分別等于左孩子或右孩子的值左、右孩子均有的結(jié)點(diǎn)，則其值等于左、右孩子結(jié)點(diǎn)的值之和用廣義表表示法顯示所建二叉樹【參考框架】#include #include /二叉樹的鏈?zhǔn)酱鎯Ρ硎総ypedef char DataType;/應(yīng)由用戶定義DataType的實(shí)際類型typedef

18、struct nodeDataType data;struct node *lchild, *rchild;/左右孩子指針 BinTNode;/結(jié)點(diǎn)類型typedef BinTNode *BinTree;void main()void ListBinTree(BinTree T);/用廣義表表示二叉樹void DisplayBinTree(BinTree T);/用凹入表表示二叉樹void CreateBinTree(BinTree *T);/構(gòu)造二叉鏈表void Preorder(BinTree T);/前序遍歷二叉樹void Inorder(BinTree T);/中序遍歷二叉樹void

19、Postorder(BinTree T);/后序遍歷二叉樹int nodes(BinTree T);/計算總結(jié)點(diǎn)數(shù)int leafs(BinTree T);/計算總?cè)~子數(shù)BinTree swap(BinTree T);/交換左右子樹BinTree T;printf(請輸入先序序列（虛結(jié)點(diǎn)用空格表示）：n);CreateBinTree(&T);ListBinTree(T);printf(n);DisplayBinTree(T);printf(前序遍歷：n);Preorder(T);printf(n);printf(中序遍歷：n);Inorder(T);printf(n);printf(后序遍歷：

20、n);Postorder(T);printf(n);printf(二叉樹的總結(jié)點(diǎn)數(shù)為%dn,nodes(T);printf(二叉樹的總?cè)~子結(jié)點(diǎn)數(shù)為%dn,leafs(T);T=swap(T);ListBinTree(T);printf(n);/構(gòu)造二叉鏈表void CreateBinTree(BinTree *T)/在此插入必要的語句/用廣義表表示二叉樹void ListBinTree(BinTree T)/在此插入必要的語句/用凹入表表示二叉樹void DisplayBinTree(BinTree T)/在此插入必要的語句/前序遍歷二叉樹void Preorder(BinTree T)/在此

21、插入必要的語句/中序遍歷二叉樹void Inorder(BinTree T)/在此插入必要的語句/后序遍歷二叉樹void Postorder(BinTree T)/在此插入必要的語句/計算總結(jié)點(diǎn)數(shù)int nodes(BinTree T)/在此插入必要的語句/計算總?cè)~子數(shù)int leafs(BinTree T)/在此插入必要的語句/交換左右子樹BinTree swap(BinTree T)/在此插入必要的語句【實(shí)驗(yàn)報告】數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報告三學(xué)院： 班級： 學(xué)號： 姓名： 日期： 程序名： L61.CPP 一、上機(jī)實(shí)驗(yàn)的問題和要求：要求采用二叉鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，前序、中序和后

22、序遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作等。具體實(shí)現(xiàn)要求：基于先序遍歷的構(gòu)造算法：輸入是二叉樹的先序序列，但必須在其中加入虛結(jié)點(diǎn)以示空指針的位置。假設(shè)虛結(jié)點(diǎn)輸入時用空格字符表示。用廣義表表示所建二叉樹。分別利用前序遍歷、中序遍歷、后序遍歷所建二叉樹。求二叉樹結(jié)點(diǎn)總數(shù)，觀察輸出結(jié)果。求二叉樹葉子總數(shù)，觀察輸出結(jié)果。交換各結(jié)點(diǎn)的左右子樹，用廣義表表示法顯示新的二叉樹。（）二叉樹采用鏈接存儲結(jié)構(gòu)，其根結(jié)點(diǎn)指針為T，設(shè)計一個算法對這棵二叉樹的每個結(jié)點(diǎn)賦值：（注意要修改DataType類型）葉結(jié)點(diǎn)的值為3只有左孩子或右孩子的結(jié)點(diǎn)則其值分別等于左孩子或右孩子的值左、右孩子均有的結(jié)點(diǎn)，則其值等于左、右孩子結(jié)

23、點(diǎn)的值之和用廣義表表示法顯示所建二叉樹二、源程序及注釋：三、運(yùn)行輸出結(jié)果：四、調(diào)試和運(yùn)行程序過程中產(chǎn)生的問題及采取的措施：實(shí)驗(yàn)四 Huffman樹【實(shí)驗(yàn)?zāi)康摹坷斫饨uffman樹的算法?！緦?shí)驗(yàn)平臺】操作系統(tǒng)：Windows2000或Windows XP開發(fā)環(huán)境：C或C+【實(shí)驗(yàn)內(nèi)容及要求】閱讀理解建立Huffman樹的算法，對該算法進(jìn)行運(yùn)行及調(diào)試。具體實(shí)現(xiàn)要求：調(diào)試并運(yùn)行Huffman算法。（）求Huffman樹的帶權(quán)路徑長度WPL。【參考框架】#include #include #include /Huffman樹的存儲結(jié)構(gòu)#define n 100/葉子數(shù)目#define m 2*n-1

24、/樹中結(jié)點(diǎn)總數(shù)typedef struct/結(jié)點(diǎn)類型float weight;/權(quán)值，不妨設(shè)權(quán)值均大于零int lchild,rchild,parent;/左右孩子及雙親指針HTNode;typedef HTNode HuffmanTreem;/HuffmanTree是向量類型typedef structchar ch;/存儲字符char bitsn+1;/存放編碼位串CodeNode;typedef CodeNode HuffmanCoden;void InitHuffmanTree(HuffmanTree T);/初始化Huffman樹void InputWeight(HuffmanTre

25、e T);/輸入權(quán)值void SelectMin(HuffmanTree T,int i,int *p1,int *p2);void main()void CreateHuffmanTree(HuffmanTree T);/構(gòu)造Huffman樹void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H);HuffmanTree T;HuffmanCode H;CreateHuffmanTree(T);CharSetHuffmanEncoding(T,H);void CreateHuffmanTree(HuffmanTree T) /構(gòu)造Huf

26、fman樹，Tm-1為其根結(jié)點(diǎn)int i,p1,p2;InitHuffmanTree(T);/將T初始化InputWeight(T);/輸入葉子權(quán)值至T0.n-1的weight域for(i=n;im;i+)/共進(jìn)行n-1次合并，新結(jié)點(diǎn)依次存于Ti中SelectMin(T,i-1,&p1,&p2);/在T0.i-1中選擇兩個權(quán)最小的根結(jié)點(diǎn)，其序號分別為p1和p2Tp1.parent=Tp2.parent=i;Ti.lchild=p1;/最小權(quán)的根結(jié)點(diǎn)是新結(jié)點(diǎn)的左孩子Ti.rchild=p2;/次小權(quán)的根結(jié)點(diǎn)是新結(jié)點(diǎn)的右孩子Ti.weight=Tp1.weight+Tp2.weight;void

27、InitHuffmanTree(HuffmanTree T)/初始化Huffman樹int i;for (i=0;im;i+)Ti.weight=0;Ti.lchild=Ti.rchild=Ti.parent=NULL;void InputWeight(HuffmanTree T)/輸入權(quán)值int i;for (i=0;in;i+)printf(請輸入第%d個權(quán)值：,i+1);scanf(%f,&Ti.weight);void SelectMin(HuffmanTree T,int i,int *p1,int *p2)/在T中選擇兩個權(quán)最小的根結(jié)點(diǎn)int j;float min1,min2;m

28、in1=min2=-1;for(j=0;j=i;j+)if(Tj.parent=NULL)if(Tj.weightmin1|min1=-1)if(min1!=-1)min2=min1;*p2=*p1;min1=Tj.weight;*p1=j;elseif(Tj.weightmin2|min2=-1)min2=Tj.weight;*p2=j;void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H)/根據(jù)Huffman樹T求Huffman編碼表Hint c,p,i;/c和p分別指示T中孩子和雙親的位置char cdn+1;/臨時存放編碼int

29、 start;/指示編碼在cd中的起始位置cdn=0;/編碼結(jié)束符printf(請輸入字符：);for(i=0;in;i+)/依次求葉子Ti的編碼Hi.ch=getchar();/讀入葉子Ti對應(yīng)的字符start=n;/編碼起始位置的初值c=i;/從葉子Ti開始上溯while(p=Tc.parent)!=NULL)/直至上溯到Tc是樹根為止/若Tc是Tp的左孩子，則生成代碼0；否則生成代碼1cd-start=(Tp.lchild=c)?0:1;c=p;/繼續(xù)上溯strcpy(Hi.bits,&cdstart);/復(fù)制編碼位串for(i=0;in;i+)printf(第%d個字符%c的編碼為%s

30、n,i+1,Hi.ch,Hi.bits);【實(shí)驗(yàn)報告】數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報告四學(xué)院： 班級： 學(xué)號： 姓名： 日期： 程序名： L62.CPP 一、上機(jī)實(shí)驗(yàn)的問題和要求：閱讀理解建立Huffman樹的算法，對該算法進(jìn)行運(yùn)行及調(diào)試。具體實(shí)現(xiàn)要求：調(diào)試并運(yùn)行Huffman算法。（）求Huffman樹的帶權(quán)路徑長度WPL。二、源程序及注釋：三、運(yùn)行輸出結(jié)果：四、調(diào)試和運(yùn)行程序過程中產(chǎn)生的問題及采取的措施：實(shí)驗(yàn)五 查找（二叉排序樹）【實(shí)驗(yàn)?zāi)康摹渴炀氄莆斩媾判驑渖系牟檎宜惴?。【?shí)驗(yàn)平臺】操作系統(tǒng)：Windows2000或Windows XP開發(fā)環(huán)境：C或C+【實(shí)驗(yàn)內(nèi)容及要求】實(shí)現(xiàn)二叉排序樹上的查找算法

31、。具體實(shí)現(xiàn)要求：用二叉鏈表做存儲結(jié)構(gòu)，輸入鍵值序列，建立一棵二叉排序樹。用廣義表表示所建二叉樹。按中序遍歷這棵二叉排序樹。在二叉排序樹上插入結(jié)點(diǎn)。刪除二叉排序樹上的結(jié)點(diǎn)。在二叉排序樹上實(shí)現(xiàn)查找算法。【參考框架】#include #include typedef int InfoType;typedef int KeyType;/假定關(guān)鍵字類型為整數(shù)typedef struct node/結(jié)點(diǎn)類型KeyType key;/關(guān)鍵字項(xiàng)InfoType otherinfo;/其它數(shù)據(jù)域，InfoType視應(yīng)用情況而定 下面不處理它struct node *lchild,*rchild;/左右孩子指針B

32、STNode;typedef BSTNode *BSTree;/BSTree是二叉排序樹的類型void main()void InsertBST(BSTree *Tptr,KeyType key);/將關(guān)鍵字key插入二叉排序樹中BSTree CreateBST(void);/建立二叉排序樹void ListBinTree(BSTree T);/用廣義表表示二叉樹void DelBSTNode(BSTree *Tptr,KeyType key);/在二叉排序樹中刪除關(guān)鍵字keyBSTNode *SearchBST(BSTree T,KeyType key);/在二叉排序樹中查找關(guān)鍵字keyBS

33、Tree T;BSTNode *p;int key;printf(請輸入關(guān)鍵字（輸入0為結(jié)束標(biāo)志）：n);T=CreateBST();ListBinTree(T);printf(n);printf(請輸入欲插入關(guān)鍵字：);scanf(%d,&key);InsertBST(&T,key);ListBinTree(T);printf(n);printf(請輸入欲刪除關(guān)鍵字：);scanf(%d,&key);DelBSTNode(&T,key);ListBinTree(T);printf(n);printf(請輸入欲查找關(guān)鍵字：);scanf(%d,&key);p=SearchBST(T,key);

34、if(p=NULL)printf(沒有找到%d！n,key);elseprintf(找到%d！n,key);ListBinTree(p);printf(n);/將關(guān)鍵字key插入二叉排序樹中void InsertBST(BSTree *Tptr,KeyType key)/在此插入必要的語句/建立二叉排序樹BSTree CreateBST(void)/在此插入必要的語句/在二叉排序樹中刪除關(guān)鍵字keyvoid DelBSTNode(BSTree *Tptr,KeyType key)/在此插入必要的語句/用廣義表表示二叉樹void ListBinTree(BSTree T)/在此插入必要的語句/在

35、二叉排序樹中查找關(guān)鍵字keyBSTNode *SearchBST(BSTree T,KeyType key)/在此插入必要的語句【實(shí)驗(yàn)報告】數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報告五學(xué)院： 班級： 學(xué)號： 姓名： 日期： 程序名： L8.CPP 一、上機(jī)實(shí)驗(yàn)的問題和要求：實(shí)現(xiàn)二叉排序樹上的查找算法。具體實(shí)現(xiàn)要求：用二叉鏈表做存儲結(jié)構(gòu)，輸入鍵值序列，建立一棵二叉排序樹。用廣義表表示所建二叉樹。按中序遍歷這棵二叉排序樹。在二叉排序樹上插入結(jié)點(diǎn)。刪除二叉排序樹上的結(jié)點(diǎn)。在二叉排序樹上實(shí)現(xiàn)查找算法。二、源程序及注釋：三、運(yùn)行輸出結(jié)果：四、調(diào)試和運(yùn)行程序過程中產(chǎn)生的問題及采取的措施：實(shí)驗(yàn)六 排序【實(shí)驗(yàn)?zāi)康摹渴炀氄莆詹迦搿?/p>

36、冒泡、直接選擇、快速、歸并等排序算法?！緦?shí)驗(yàn)平臺】操作系統(tǒng)：Windows2000或Windows XP開發(fā)環(huán)境：C或C+【實(shí)驗(yàn)內(nèi)容及要求】實(shí)現(xiàn)直接插入、冒泡、直接選擇、快速、歸并等排序算法。具體實(shí)現(xiàn)要求：利用L91.CPP實(shí)現(xiàn)直接插入排序算法。利用L92.CPP實(shí)現(xiàn)冒泡排序算法。利用L93.CPP實(shí)現(xiàn)直接選擇排序算法。利用L94.CPP實(shí)現(xiàn)快速排序算法。利用L95.CPP實(shí)現(xiàn)歸并排序算法?！緦?shí)驗(yàn)報告】數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報告六學(xué)院： 班級： 學(xué)號： 姓名： 日期： 程序名：L91.CPP L92.CPP L93.CPP L94.CPP L95.CPP 一、上機(jī)實(shí)驗(yàn)的問題和要求：實(shí)現(xiàn)直接插入、冒

37、泡、直接選擇、快速、歸并等排序算法。具體實(shí)現(xiàn)要求：利用L91.CPP實(shí)現(xiàn)直接插入排序算法。利用L92.CPP實(shí)現(xiàn)冒泡排序算法。利用L93.CPP實(shí)現(xiàn)直接選擇排序算法。利用L94.CPP實(shí)現(xiàn)快速排序算法。利用L95.CPP實(shí)現(xiàn)歸并排序算法。二、源程序及注釋：三、運(yùn)行輸出結(jié)果：四、調(diào)試和運(yùn)行程序過程中產(chǎn)生的問題及采取的措施：附錄資料:不需要的可以自行刪除 libxml2應(yīng)用實(shí)例Libxml2 是一個xml的c語言版的解析器，本來是為Gnome項(xiàng)目開發(fā)的工具，是一個基于MIT License的免費(fèi)開源軟件。它除了支持c語言版以外，還支持c+、PHP、Pascal、Ruby、Tcl等語言的綁定，能在W

38、indows、Linux、Solaris、MacOsX等平臺上運(yùn)行。功能還是相當(dāng)強(qiáng)大的，相信滿足一般用戶需求沒有任何問題。二、 Libxml2安裝：一般如果在安裝系統(tǒng)的時候選中了所有開發(fā)庫和開發(fā)工具的話(Fedora Core系列下)，應(yīng)該不用安裝，下面介紹一下手動安裝： 1) 從xmlsoft站點(diǎn)或ftp()站點(diǎn)下載libxml壓縮包(libxml2-xxxx.tar.gz)2) 對壓縮包進(jìn)行解壓縮 tar xvzf libxml2-xxxx.tar.gz3) 進(jìn)入解壓縮后的文件夾中運(yùn)行 ./configure -prefix /home/user/myxml/xmlinst(此處為待安裝的

39、路徑)或者直接使用 ./configure make make install 4) 添加路徑 export PATH=/home/user/myxml/xmlinst/bin:$PATH 說明：為了結(jié)構(gòu)清晰，最好將libxml2不安裝在解壓目錄中。安裝完成后就可以使用簡單的代碼解析XML文件，包括本地和遠(yuǎn)程的文件，但是在編碼上有一些問題。Libxml默認(rèn)只支持UTF8的編碼，無論輸入輸出都是UTF-8，所以如果你解析完一個XML得到的結(jié)果都是UTF8的，如果需要輸出GB2312或者其它編碼，需要ICONV來做轉(zhuǎn)碼(生成UTF8編碼的文件也可以用它做),如果系統(tǒng)中沒有安裝iconv的話，需要安

40、裝libiconv。 1) 下載libiconv壓縮包(例如libiconv-1.11.tar.gz) 2) 對壓縮包進(jìn)行解壓縮tar xvzf libiconv-1.11.tar.gz 3) 進(jìn)入解壓縮后的文件夾中運(yùn)行 ./configure make make install三、關(guān)于XML：在開始研究 Libxml2 庫之前，先了解一下XML的相關(guān)基礎(chǔ)。XML 是一種基于文本的格式，它可用來創(chuàng)建能夠通過各種語言和平臺訪問的結(jié)構(gòu)化數(shù)據(jù)。它包括一系列類似 HTML 的標(biāo)記，并以樹型結(jié)構(gòu)來對這些標(biāo)記進(jìn)行排列。例如，可參見清單 1 中介紹的簡單文檔。為了更清楚地顯示 XML 的一般概念，下面是一個

41、簡化的XML文件。清單 1. 一個簡單的 XML 文件 root delete 10清單 1 中的第一行是 XML 聲明，它告訴負(fù)責(zé)處理 XML 的應(yīng)用程序，即解析器，將要處理的 XML 的版本。大部分的文件使用版本 1.0 編寫，但也有少量的版本 1.1 的文件。它還定義了所使用的編碼。大部分文件使用 UTF-8，但是，XML 設(shè)計用來集成各種語言中的數(shù)據(jù)，包括那些不使用英語字母的語言。接下來出現(xiàn)的是元素。一個元素以開始標(biāo)記 開始(如 )，并以結(jié)束標(biāo)記 結(jié)束(如 )，其中使用斜線 (/) 來區(qū)別于開始標(biāo)記。元素是 Node 的一種類型。XML 文檔對象模型 (DOM) 定義了幾種不同的 No

42、des 類型，包括:Elements(如 files 或者 age)Attributes(如 units)Text(如 root 或者 10)元素可以具有子節(jié)點(diǎn)。例如，age 元素有一個子元素，即文本節(jié)點(diǎn) 10。XML 解析器可以利用這種父子結(jié)構(gòu)來遍歷文檔，甚至修改文檔的結(jié)構(gòu)或內(nèi)容。LibXML2 是這樣的解析器中的其中一種，并且文中的示例應(yīng)用程序正是使用這種結(jié)構(gòu)來實(shí)現(xiàn)該目的。對于各種不同的環(huán)境，有許多不同的解析器和庫。LibXML2 是用于 UNIX 環(huán)境的解析器和庫中最好的一種，并且經(jīng)過擴(kuò)展，它提供了對幾種腳本語言的支持，如 Perl 和 Python。四、Libxml2中的數(shù)據(jù)類型和函數(shù)

43、一個函數(shù)庫中可能有幾百種數(shù)據(jù)類型以及幾千個函數(shù)，但是記住大師的話，90%的功能都是由30%的內(nèi)容提供的。對于libxml2，我認(rèn)為搞懂以下的數(shù)據(jù)類型和函數(shù)就足夠了。1）內(nèi)部字符類型xmlCharxmlChar是Libxml2中的字符類型，庫中所有字符、字符串都是基于這個數(shù)據(jù)類型。事實(shí)上它的定義是：xmlstring.htypedef unsigned char xmlChar;使用unsigned char作為內(nèi)部字符格式是考慮到它能很好適應(yīng)UTF-8編碼，而UTF-8編碼正是libxml2的內(nèi)部編碼，其它格式的編碼要轉(zhuǎn)換為這個編碼才能在libxml2中使用。還經(jīng)?？梢钥吹绞褂脁mlChar*

44、作為字符串類型，很多函數(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ù)都在xmlstring.h中定義；而動態(tài)內(nèi)存分配函數(shù)在xmlmemory.h中定義。3）xmlChar*與其它類型之間的轉(zhuǎn)換另外要注意，因?yàn)榭偸且趚mlChar*和char*之間進(jìn)行類型轉(zhuǎn)換，所以定義了一個宏BAD_CAST

45、，其定義如下：xmlstring.h#define BAD_CAST (xmlChar *)原則上來說，unsigned char和char之間進(jìn)行強(qiáng)制類型轉(zhuǎn)換是沒有問題的。4）文檔類型xmlDoc、指針xmlDocPtrxmlDoc是一個struct，保存了一個xml的相關(guān)信息，例如文件名、文檔類型、子節(jié)點(diǎn)等等；xmlDocPtr等于xmlDoc*，它搞成這個樣子總讓人以為是智能指針，其實(shí)不是，要手動刪除的。xmlNewDoc函數(shù)創(chuàng)建一個新的文檔指針。xmlParseFile函數(shù)以默認(rèn)方式讀入一個UTF-8格式的文檔，并返回文檔指針。xmlReadFile函數(shù)讀入一個帶有某種編碼的xml文檔

46、，并返回文檔指針；細(xì)節(jié)見libxml2參考手冊。xmlFreeDoc釋放文檔指針。特別注意，當(dāng)你調(diào)用xmlFreeDoc時，該文檔所有包含的節(jié)點(diǎn)內(nèi)存都被釋放，所以一般來說不需要手動調(diào)用xmlFreeNode或者xmlFreeNodeList來釋放動態(tài)分配的節(jié)點(diǎn)內(nèi)存，除非你把該節(jié)點(diǎn)從文檔中移除了。一般來說，一個文檔中所有節(jié)點(diǎn)都應(yīng)該動態(tài)分配，然后加入文檔，最后調(diào)用xmlFreeDoc一次釋放所有節(jié)點(diǎn)申請的動態(tài)內(nèi)存，這也是為什么我們很少看見xmlNodeFree的原因。xmlSaveFile將文檔以默認(rèn)方式存入一個文件。xmlSaveFormatFileEnc可將文檔以某種編碼/格式存入一個文件中。

47、5）節(jié)點(diǎn)類型xmlNode、指針xmlNodePtr節(jié)點(diǎn)應(yīng)該是xml中最重要的元素了，xmlNode代表了xml文檔中的一個節(jié)點(diǎn)，實(shí)現(xiàn)為一個struct，內(nèi)容很豐富：tree.htypedef struct _xmlNode xmlNode;typedef xmlNode *xmlNodePtr;struct _xmlNode void *_private;/* application data */ xmlElementType type; /* type number, must be second ! */ const xmlChar *name; /* the name of the

48、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 sibling link*/ struct _xmlNode *prev; /* previous sibling link*/ struct _xmlDoc*doc;/* the containing

49、document */ /* End of common part */ xmlNs *ns; /* pointer to the associated namespace */ xmlChar *content; /* the content */ struct _xmlAttr *properties;/* properties list */ xmlNs *nsDef; /* namespace definitions on this node */ void *psvi;/* for type/PSVI informations */ unsigned short line; /* l

50、ine number */ unsigned short extra;/* extra data for XPath/XSLT */;可以看到，節(jié)點(diǎn)之間是以鏈表和樹兩種方式同時組織起來的，next和prev指針可以組成鏈表，而parent和children可以組織為樹。同時還有以下重要元素：節(jié)點(diǎn)中的文字內(nèi)容：content；節(jié)點(diǎn)所屬文檔：doc；節(jié)點(diǎn)名字：name；節(jié)點(diǎn)的namespace：ns；節(jié)點(diǎn)屬性列表：properties；Xml文檔的操作其根本原理就是在節(jié)點(diǎn)之間移動、查詢節(jié)點(diǎn)的各項(xiàng)信息，并進(jìn)行增加、刪除、修改的操作。xmlDocSetRootElement函數(shù)可以將一個節(jié)點(diǎn)設(shè)置為某個

51、文檔的根節(jié)點(diǎn)，這是將文檔與節(jié)點(diǎn)連接起來的重要手段，當(dāng)有了根結(jié)點(diǎn)以后，所有子節(jié)點(diǎn)就可以依次連接上根節(jié)點(diǎn)，從而組織成為一個xml樹。6）節(jié)點(diǎn)集合類型xmlNodeSet、指針xmlNodeSetPtr節(jié)點(diǎn)集合代表一個由節(jié)點(diǎn)組成的變量，節(jié)點(diǎn)集合只作為Xpath的查詢結(jié)果而出現(xiàn)（XPATH的介紹見后面），因此被定義在xpath.h中，其定義如下：/* A node-set (an unordered collection of nodes without duplicates).*/typedef struct _xmlNodeSet xmlNodeSet;typedef xmlNodeSet *xm

52、lNodeSetPtr;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_ns to check wether namespace nodes should be looked at */;可以看出，節(jié)點(diǎn)集合有三個成員，分別是節(jié)點(diǎn)集合的節(jié)點(diǎn)數(shù)、最大可容納的節(jié)點(diǎn)數(shù)，以及節(jié)點(diǎn)數(shù)組頭

53、指針。對節(jié)點(diǎn)集合中各個節(jié)點(diǎn)的訪問方式很簡單，如下：xmlNodeSetPtr nodeset = XPATH查詢結(jié)果;for (int i = 0; i nodeNr; i+)nodeset-nodeTabi;注意，libxml2是一個c函數(shù)庫，因此其函數(shù)和數(shù)據(jù)類型都使用c語言的方式來處理。如果是c+，我想我寧愿用STL中的vector來表示一個節(jié)點(diǎn)集合更好，而且沒有內(nèi)存泄漏或者溢出的擔(dān)憂。五、使用Libxml2項(xiàng)目中要實(shí)現(xiàn)一個管理XML文件的后臺程序，需要對XML文件進(jìn)行創(chuàng)建，解析，修改，查找等操作，下面介紹如何利用libxml2提供的庫來實(shí)現(xiàn)上述功能。1、創(chuàng)建XML文檔：我們使用xmlNe

54、wDoc()來創(chuàng)建XML文檔，然后使用xmlNewNode(),xmlNewChild(),xmlNewProp(),xmlNewText()等函數(shù)向XML文件中添加節(jié)點(diǎn)及子節(jié)點(diǎn)，設(shè)置元素和屬性，創(chuàng)建完畢后用xmlSaveFormatFileEnc()來保存XML文件到磁盤(該函數(shù)可以設(shè)置保存XML文件時的編碼格式)。示例1： #include #include #include int main(int argc, char *argv) xmlDocPtr doc = NULL; /* document pointer */ xmlNodePtr root_node = NULL, nod

55、e = 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); xmlDocSetRootElement(doc, root_node); /creates a new node, which is attached as child node of root_node node. xmlNewChild(

56、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 attributes); xmlNewProp(node, BAD_CAST attribute, BAD_CAST yes); /Here goes another way to create nodes. nod

57、e = 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 xmlSaveFormatFileEnc(argc 1 ? argv1 : -, doc, UTF-8, 1); /*free the document */ xmlFreeDoc(doc); xmlCleanupParser(

58、); 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 （綠色文字為libxml2安裝路徑） -I后接頭文件目錄 -L后接lib庫目錄2、解析XML文檔 解析文檔時僅僅需要文件名并只調(diào)用一個函數(shù)，并有錯誤檢查，常用的相關(guān)函數(shù)有xmlParseFile(),xmlParseDoc(),

59、獲取文檔指針后，就可以使用xmlDocGetRootElement()來獲取根元素節(jié)點(diǎn)指針，利用該指針就可以在DOM樹里漫游了，結(jié)束后要調(diào)用xmlFreeDoc()釋放。示例2： xmlDocPtr doc; /定義解析文檔指針 xmlNodePtr cur; /定義結(jié)點(diǎn)指針(你需要它為了在各個結(jié)點(diǎn)間移動) xmlChar *key; doc = xmlReadFile(url, MY_ENCODING, 256); /解析文件 /*檢查解析文檔是否成功，如果不成功，libxml將指一個注冊的錯誤并停止。一個常見錯誤是不適當(dāng)?shù)木幋a。XML標(biāo)準(zhǔn)文檔除了用UTF-8或UTF-16外還可用其它編碼保

60、存。如果文檔是這樣，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); /確定文檔根元素 /*檢查確認(rèn)當(dāng)前文檔中包含內(nèi)容*/ if (cur = NULL) fprintf(stderr,empty documentn); xmlFreeDoc(doc); return; /*在這個例子中，我們需要確認(rèn)文檔是正確的類型?！皉oot”是在這