2011-軟件技術基礎實驗指導書

《2011-軟件技術基礎實驗指導書》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、《軟件技術基礎》課程實驗指導書實驗環(huán)境：C/C++語言編程TurboC3.0/VisualC++6.0一、實驗內容序號實驗內容實驗類型學時要求1單鏈表的操作設計2必做2堆棧操作設計2必做3二叉樹操作設計2必做4數(shù)據(jù)的查找與排序設計2必做二、實驗指導實驗一單鏈表的操作一、實驗目的1.掌握線性表的鏈式存儲結構(1)線性表的鏈式存儲原理(2)鏈式存儲結構的優(yōu)缺點2.掌握結構體的應用以及數(shù)據(jù)結點的生成(1)結構體的定義(2)動態(tài)存儲分配函數(shù)的使用(3)強制類型轉換的方法3.掌握指針的應用(1)鞏固指針的含義和用法(2)結構體指針的使用二、預習要求1.復習C語言(1)鞏固C語言程序設計的基

2、本方法(2)鞏固在TC或VC環(huán)境中編寫和調試C程序2.復習指針和結構體兩部分的知識(1)鞏固指針的含義以及定義方式(2)理解結構體的定義以及其成員的賦值和引用3.理解課本關于單鏈表部分的知識(1)掌握單鏈表的生成原理和過程(2)在草稿紙上畫出簡單程序流程圖三、實驗內容1.通過C語言編程，用函數(shù)實現(xiàn)不低于五個結點的單鏈表的建立：(1)要求編寫功能函數(shù)實現(xiàn)單鏈表的建立；(2)鏈表中結點的數(shù)據(jù)類型為任意原子類型，以下參考算法假設的是整型；(3)采用循環(huán)結構建表，請同學自定義循環(huán)結束標志，以下是次數(shù)循環(huán)，同學們可設計為輸入某個鍵值結束，如數(shù)字‘-1’結束；(4)編寫訪問各結點的算法，把建

3、成的單鏈表順序輸出。2.實現(xiàn)單鏈表的插入和刪除算法。3.編寫主函數(shù)調用以上各算法函數(shù)，調試并運行整個程序，分析運行結果。一、實驗原理1．尾插法建立單鏈表(1)算法原理：從一個空表開始,循環(huán)讀入數(shù)據(jù),生成新結點,將讀入數(shù)據(jù)存放在新結點的數(shù)據(jù)域中,然后將新結點插入到當前鏈表的表尾上,直到循環(huán)結束為止。12345L^(2)算法示意圖如下，若要建立L=（1，2，3，4，5）的單鏈表，則鏈表結構為：(3)算法描述：//結點結構體定義structnode{intdata;structnode*next;};//尾插法建立n個結點的單鏈表Lstructnode*CreateList(struc

4、tnode*L,intn){inti;intx;structnode*p,*q;L=(structnode*)malloc(sizeof(structnode));L->data=n;L->next=NULL;q=L;for(i=n;i>0;i--){p=(structnode*)malloc(sizeof(structnode));scanf("%d",&x);p->data=x;q->next=p;p->next=NULL;q=p;}returnL;}2.單鏈表的訪問從頭節(jié)點開始，依次輸出每個節(jié)點的值。voidaccess(structnode*h){structnode*p

5、;p=h;while(p->next!=NULL){p=p->next;printf("%d",p->data);}}3．單鏈表的插入算法(1)算法原理：在以上算法的基礎上，在指定位置插入一個新結點。首先定義一個搜索指針p，從頭開始搜索(p=p->next)直到指定位置的前一個位置；然后建立新結點，修改指針使之插入。(2)算法示意圖：若要在3號位置插入一個數(shù)據(jù)域為6的結點t，則鏈表結構變?yōu)椋?2345L^6(3)算法描述：//在第i個位置上插入一個新結點tstructnode*insert(structnode*L,inti){p=L;j=0;while(p->next!=NUL

6、L&&jnext;j++;}if(j!=i-1){printf("iisinvalid!");exit(0);}t=(structnode*)malloc(sizeof(structnode));scanf("%d",&x);t->data=x;t->next=p->next;p->next=t;returnL;}4.單鏈表的刪除算法請同學們參見課本P14的算法5，注意相關定義和語句的修改和完善。5.同學自行編寫主程序，完成整個實驗。一、實驗報告要求1.按教務處印發(fā)的標準的計算機實驗報告格式填寫實驗報告(1)字跡工整，內容屬實規(guī)范；(2)報告不得打印或復

7、印，也不得抄襲或有雷同。2.本實驗為軟件設計，報告中應先畫程序流程圖，再闡述你的設計思路和過程；3.避免純粹的抄寫源程序，應適當?shù)靥顚懸恍┱{試情況以及問題的產(chǎn)生原因和處理辦法；4.設計感想可包括你對本次實驗的收獲、啟示以及不足和希望。一、思考題1.如果結點指針P指向鏈表中某一中間結點，問：如何用P表示P之后的每一個結點？2.單鏈表可以按隨意順序輸出嗎？3.單鏈表和順序表所花的存儲空間相同嗎？二、注意事項1.算法和程序是不同的，課本上的算法不能直接拿來調試和運行，必須將其改寫為程序