數據結構實驗報告專業信息管理學生姓名馬鑫學號3140561030班號信管142任課教師原欣偉指導教師祝明偉報告日期2015年11月經濟與管理學院2015年11月

驗證性實驗1、驗證性實驗名稱：在單鏈表查找值為x的數據元素2、驗證性程序設計1）需要學生完成的函數名稱、功能的簡要說明2）需要學生完成的函數的具體算法，并編程實現voidSearchList(charx)/*在單鏈表查找值為x的數據元素*/{printf("\t\t\t未找到值為%c的結點！\n",x);printf("\t\t\t請同學自己實現程序代碼！\n");return;}3．調試和測試1）對上述算法和程序進行調試，發現問題并改正，使程序調試通過。2）建立一組數據實例，對程序的所有功能進行測試，并記錄測試過程和結果。

綜合設計實驗一、實驗名稱：直接插入排序的單鏈表實現方法二、實驗目的1.對前面所學的數據結構進行復習總結；2.對有一定難度的題目，學會分解問題，自上而下，逐步解決；

3.在掌握現有數據結構的基礎上，對不同的問題，嘗試改進相應的數據結構。三、實驗內容1.采用單鏈表存儲待排序數據；2.設計直接插入排序算法。四、概要設計1）為了實現上述程序功能，需要定義單鏈表的數據類型：首先將待排序數據建立一個帶頭結點的單鏈表，具體算法請參見單鏈表的操作。在單鏈表中進行直接插入排序的基本思想是：將單鏈表劃分為有序區和無序區，初始時有序區只包含一個元素結點，依次取無序區中的每一個結點，在有序區中查找待插入結點的插入位置，然后把該結點從單鏈表中刪除，再插入到相應位置。例如，有一組待排序數據存儲在單鏈表head中，排序過程如下：分析上述排序過程，需要設一個工作指針q在無序區中指向待插入的結點，為了查找正確的插入位置，每趟排序前需將工作指針pre和p指向頭結點和開始結點，在找到插入位置后，將q所指結點插在結點pre和p之間。這相當于在單鏈表中刪除q所指結點，然后將其插入到結點pre和p之間。為了成功刪除結點q，且鏈表不斷開，需要一個工作指針L指向結點q的前一個結點，即有序區的最后一個結點。2）函數名和函數的簡要功能說明voidCreateList()：尾插法建立單鏈表voidShowList()：顯示單鏈表所有元素voidinsertsortl(node*head)：直接插入排序算法.五、詳細設計實現概要設計中定義的所有的數據類型，對主程序和每個函數需要寫出具體算法，并編程實現。#include<stdio.h>#include<stdlib.h>typedefstructlinknode{ intdata; structlinknode*next;}node;intn=0;node*head;voidCreateList()/*尾插法建立單鏈表*/{ node*p,*s; intx; head=(node*)malloc(sizeof(node)); p=head; printf("\n\t\t建立一個線性表"); printf("\n\t\t說明：請逐個輸數字，結束以0：\n"); printf("\t\t輸入："); scanf("%d",&x); while(x!=0) { s=(node*)malloc(sizeof(node));/*申請一個新結點*/ n++; s->data=x;/*對新結點的data域賦值*/ s->next=NULL; /*對新結點的next域賦空值*/ p->next=s;/*將新結點連接到表的末尾*/ p=s;/*P指向最后結點*/ scanf("%d",&x); }}voidShowList()/*顯示單鏈表所有元素*/{ node*p=head; printf("\n\t\t顯示線性表的所有元素："); if(head->next==NULL||p==NULL) printf("\n\t\t鏈表為空！\n"); else { printf("\n"); while(p->next!=NULL) { printf("%5d",p->next->data); p=p->next; } }}voidinsertsortl(node*head)/*直接插入排序算法*/{node*curr,*pre,*p,*q;p=head->next;head->next=NULL;while(p!=NULL){ curr=head->next; pre=head; while(curr!=NULL&&curr->data<=p->data) { pre=curr; curr=curr->next; } q=p; p=p->next; q->next=pre->next; pre->next=q;}}voidmain(){ intchoice,j=1; head=NULL; while(j!=0) { printf("\n\n\n\n"); printf("\t\t\t直接插入排序的單鏈表實現\n"); printf("\n\t\t***************************************"); printf("\n\t\t*1-------建表*"); printf("\n\t\t*2-------排序*");printf("\n\t\t*3-------顯示*");printf("\n\t\t*0-------返回*"); printf("\n\t\t***************************************\n"); printf("\t\t請選擇菜單號(0--3)："); scanf("%d",&choice);getchar(); if(choice==1) CreateList(); elseif(choice==2) insertsortl(head); elseif(choice==3) { if(head==NULL) printf("\n\t\t請先建立線性表！"); else ShowList(); } elseif(choice==0) j=0; else printf("\n\t\t輸入錯誤！請重新輸入！\n"); }}建立一個線性表：直接插入排序的單鏈表實現****************************************1-------建表**2-------排序**3-------顯示**0-------返回****************************************請選擇菜單號(0--3)：1建立一個線性表說明：請逐個輸數字，結束以0：輸入：2681930顯示排序結果：****************************************1-------建表**2-------排序**3-------顯示**0-------返回****************************************請選擇菜單號(0--3)：2直接插入排序的單鏈表實現****************************************1-------建表**2-------排序**3-------顯示**0-------返回****************************************請選擇菜單號(0--3)：3顯示線性表的所有元素：123689六、調試和測試1）對上述算