數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)：基于線(xiàn)性表的圖書(shū)信息管理

1、X X X X X 大 學(xué)11學(xué)年12學(xué)年第2學(xué)期數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告書(shū)專(zhuān) 業(yè)： 班 級(jí)： 姓 名： 學(xué) 號(hào)： 實(shí)驗(yàn)地點(diǎn)： 計(jì)算中心B6機(jī)房 任課教師： 實(shí)驗(yàn)題目： 基于線(xiàn)性表的圖書(shū)信息管理 實(shí)驗(yàn)環(huán)境： Visual Studio 6.0 實(shí)驗(yàn)?zāi)康模?、掌握線(xiàn)性表的定義；2、掌握線(xiàn)性表的基本操作，如建立、查找、插入和刪除等。實(shí)驗(yàn)內(nèi)容：1、必做分別定義一個(gè)包含圖書(shū)信息（書(shū)號(hào)，書(shū)名，定價(jià)）的順序表和鏈表，使其具有如下功能：(1) 從給定的文件book.txt逐個(gè)讀入圖書(shū)信息；(2) 逐個(gè)顯示圖書(shū)表中所有圖書(shū)的相關(guān)信息；(3) 統(tǒng)計(jì)表中圖書(shū)個(gè)數(shù)；(4) 輸出圖書(shū)價(jià)格最高的圖書(shū)信息（考慮可能有多個(gè)）；(5

2、) 計(jì)算所有圖書(shū)的平均價(jià)格；(6) 根據(jù)書(shū)名進(jìn)行查找，返回相應(yīng)書(shū)名的圖書(shū)的書(shū)號(hào)和定價(jià)（考慮重名情況）； (7) 根據(jù)指定的位置，返回相應(yīng)位置的圖書(shū)的全部信息；(8) 給定一本圖書(shū)相關(guān)信息，插入到表中指定的位置，將插入后的結(jié)果重新寫(xiě)入文件book.txt；(9) 刪除指定位置的圖書(shū)記錄，將刪除后的結(jié)果重新寫(xiě)入文件book.txt；(10) 將圖書(shū)表信息逆序存儲(chǔ)，將逆序的圖書(shū)信息存入文件book_inverser.txt中。2、選做（1）按照?qǐng)D書(shū)價(jià)格進(jìn)行排序，將排序的結(jié)果以格式（定價(jià)，書(shū)號(hào)，書(shū)名）存入文件book_sort.txt中。（2）實(shí)現(xiàn)兩個(gè)一元多項(xiàng)式的加法、減法、乘法運(yùn)算。實(shí)現(xiàn)方法、實(shí)驗(yàn)結(jié)

3、果及結(jié)論分析等：（一）實(shí)現(xiàn)方法1. 所用數(shù)據(jù)結(jié)構(gòu)的定義及其相關(guān)說(shuō)明（相關(guān)結(jié)構(gòu)體或類(lèi)的定義及其含義）/定義一個(gè)結(jié)構(gòu)體Bookstruct Book /定義結(jié)構(gòu)體char no30; /編碼char name30; /書(shū)名int price; /價(jià)格;/順序表的定義typedef struct LNode /定義順序表struct Book *elem; /指向數(shù)據(jù)元素的基地址int length; /順序表當(dāng)前長(zhǎng)度SqList;/鏈表的定義typedef struct LNode /定義鏈表struct Book data; /數(shù)據(jù)域struct LNode *next; /指針域LNode,

4、*LinkList;/一元二次多項(xiàng)式的定義typedef struct PNodefloat coef; /參數(shù)int expn; /指數(shù)struct PNode *next; /指針域PNode, *Polynomial;2. 自定義函數(shù)的名稱(chēng)及其功能說(shuō)明/函數(shù)聲明（順序表）Status InitList( SqList &L )； /順序表初始化void Input( SqList &L )； /輸入函數(shù)void Output( SqList L )； /輸出函數(shù)void Count( SqList L )； /輸出數(shù)據(jù)長(zhǎng)度函數(shù)void Compare( SqList L )； /比較價(jià)格

5、函數(shù)void Average( SqList L )； /求平均價(jià)格函數(shù)void Search_name( SqList L )； /按名字查找圖書(shū)信息函數(shù)void Search_no( SqList L )； /按輸入圖書(shū)位置查找圖書(shū)信息void Insert( SqList &L )； /插入函數(shù)void Delete( SqList &L )； /刪除函數(shù)void Inverse( SqList &L )； /逆轉(zhuǎn)函數(shù)/函數(shù)聲明（鏈表）Status InitList( LinkList &L )； /初始化鏈表void Input( LinkList &L )； /輸入函數(shù)void Ou

6、tput( LinkList &L )； /輸出函數(shù)void Count( LinkList L )； /輸出數(shù)據(jù)個(gè)數(shù)的函數(shù)void Compare( LinkList L )； /比較價(jià)格函數(shù)void Average( LinkList L )； /求平均價(jià)格函數(shù)void Search_name( LinkList L )； /按照書(shū)名查找圖書(shū)信息的函數(shù)Status Search_no( LinkList L )； /按照輸入位置查找圖書(shū)信息Status Insert( LinkList &L )； /插入函數(shù)Status Delete( LinkList &L )； /刪除函數(shù)Status

7、 Inverse( LinkList &L )； /逆序函數(shù)Status Sort( LinkList &L )； /排序函數(shù)/函數(shù)聲明（一元多項(xiàng)式）Status InitPolyn( Polynomial &P )； /初始化一元多項(xiàng)式void CreatePolyn( Polynomial &P )； /創(chuàng)建一元多項(xiàng)式void CopyPolyn( Polynomial &P1, Polynomial &P2 )； /一元多項(xiàng)式的拷貝void AddPolyn( Polynomial &PA, Polynomial &PB )； /一元多項(xiàng)式相加函數(shù)void MinusPolyn( Pol

8、ynomial &PA, Polynomial &PB )；/一元多項(xiàng)式相減void MultiplyPolyn( Polynomial &Pa, Polynomial &Pb )；/一元多項(xiàng)式相乘3. 主要功能算法的時(shí)間復(fù)雜度順序表函數(shù)名稱(chēng)時(shí)間復(fù)雜度Status InitList( SqList &L )；/順序表初始化O(1)void Input( SqList &L )；/輸入函數(shù)O(n)void Output( SqList L )；/輸出函數(shù)O(n)void Count( SqList L )； /輸出數(shù)據(jù)長(zhǎng)度函數(shù)O(1)void Compare( SqList L )；/比較價(jià)格函

9、數(shù)O(n)void Average( SqList L )；/求平均價(jià)格函數(shù)O(n)void Search_name( SqList L )；/按照書(shū)名查找O(n)void Search_no( SqList L )；/按照輸入位置查找O(1)void Insert( SqList &L )；/插入函數(shù)O(n)void Delete( SqList &L )；/刪除函數(shù)O(n)void Inverse( SqList &L )；O(n)鏈表函數(shù)名稱(chēng)時(shí)間復(fù)雜度Status InitList( LinkList &L )；/初始化鏈表O(1)void Input( LinkList &L )；/輸

10、入函數(shù)O(n)void Output( LinkList &L )；/輸出函數(shù)O(n)void Count( LinkList L )；/輸出數(shù)據(jù)個(gè)數(shù)的函數(shù)O(1)void Compare( LinkList L )；/比較價(jià)格函數(shù)O(n)void Average( LinkList L )；/求平均價(jià)格函數(shù)O(n)void Search_name( LinkList L )；/按照書(shū)名查找O(n)Status Search_no( LinkList L )；/按照輸入位置查找O(n)Status Insert( LinkList &L )；/插入函數(shù)O(n)Status Delete( Li

11、nkList &L )；/刪除函數(shù)O(n)Status Inverse( LinkList &L )；/逆序函數(shù)O(n)Status Sort( LinkList &L )；/排序函數(shù)O(n*n)一元多項(xiàng)式函數(shù)名稱(chēng)時(shí)間復(fù)雜度Status InitPolyn( Polynomial &P )；/初始化一元多項(xiàng)式O(1)void CreatePolyn( Polynomial &P )； /創(chuàng)建一元多項(xiàng)式O(n)void CopyPolyn( Polynomial &P1, Polynomial &P2 )； O(n)void AddPolyn( Polynomial &PA, Polynomia

12、l &PB )；O(m+n)void MinusPolyn( Polynomial &PA, Polynomial &PB )； O(m+n)void MultiplyPolyn( Polynomial &Pa, Polynomial &Pb )； O(m*n*m*n)4. 實(shí)驗(yàn)任務(wù)書(shū)中要求畫(huà)的流程圖鏈表根據(jù)指定位置進(jìn)行查找的算法流程圖鏈表插入算法的流程圖（二）實(shí)驗(yàn)結(jié)果1順序表（1）菜單：當(dāng)輸入超出菜單所給的數(shù)字時(shí)出現(xiàn)提示（2）輸出函數(shù)：輸出全部圖書(shū)信息（3）統(tǒng)計(jì)圖書(shū)個(gè)數(shù)（4）找出價(jià)格最高的圖書(shū)，并輸出其信息。當(dāng)出現(xiàn)多個(gè)價(jià)格同時(shí)最高的圖書(shū)時(shí)依然可以正確輸出 （5）求出所有圖書(shū)的平均價(jià)格（6）按

13、書(shū)名查找圖書(shū)，并輸出其信息；當(dāng)沒(méi)有此書(shū)時(shí)會(huì)有提示 （7）按照指定的位置查找圖書(shū)信息，當(dāng)輸入非法時(shí)有提示 （8）在指定位置插入圖書(shū)信息，當(dāng)位置不合法或者空間不足時(shí)有提示 （9）刪除指定位置的圖書(shū)信息，當(dāng)輸入位置不合法是提示（10）圖書(shū)信息逆序2. 鏈表（1）當(dāng)輸入超出菜單所給選項(xiàng)的數(shù)字時(shí)有提示 （2）輸出所有的圖書(shū)信息 （3）統(tǒng)計(jì)圖書(shū)個(gè)數(shù)（4）查找價(jià)格最高的圖書(shū)，如果有多本書(shū)同時(shí)為最高價(jià)可全部輸出 （5）計(jì)算所有圖書(shū)的平均價(jià)格 （6）按書(shū)名查找圖書(shū)，可查找多本同名圖書(shū)，當(dāng)無(wú)查找書(shū)籍信息時(shí)有提示 （7）按輸入位置查找圖書(shū)信息，當(dāng)位置不合法是有提示 （8）在指定位置插入信息，當(dāng)位置不合法是有提示 （

14、9）刪除指定位置的圖書(shū)信息，當(dāng)位置不合法是有提示 （10）將所有圖書(shū)信息逆序 （11）將所有圖書(shū)信息按照價(jià)格由高到低排序3一元多項(xiàng)式（1）創(chuàng)建一元多項(xiàng)式（2）彈出菜單，當(dāng)輸入錯(cuò)誤選項(xiàng)時(shí)有提示，還有選項(xiàng)可以跳出菜單（3）一元多項(xiàng)式相加（4）一元多項(xiàng)式相減 （5）一元多項(xiàng)式相乘 （三）結(jié)論分析1. 問(wèn)題與解決方法在寫(xiě)菜單的代碼時(shí)，我設(shè)法讓菜單能夠循環(huán)，但是也要有出口，所以選擇了一個(gè)循環(huán)；在選擇菜單選項(xiàng)時(shí)，由于選項(xiàng)較多，用if語(yǔ)句進(jìn)行選擇會(huì)套用多層if語(yǔ)句，而且對(duì)于非選項(xiàng)的數(shù)字處理也較麻煩，于是我選擇了switch語(yǔ)句。但是要菜單不斷重復(fù)，只是在選擇退出菜單選項(xiàng)時(shí)停止循環(huán)，所以我選擇了while循環(huán)語(yǔ)句，并讓條件永遠(yuǎn)為真，當(dāng)保存選項(xiàng)的變量為退