1、 數據結構實驗報告 班 級：信計 1202 班 學 號：1 2 0 8 0 6 0 2 2 0 姓 名：韓 雪 平 設計日期：2014年6月1日 西安科技大學計算機學院1，實驗題目： 編寫一個函數，實現利用折半查找算法在一個有序表中插入一個數據元素x,并保持表的有序性。2，需求分析： 此程序用c語言編寫，完成線性表的構造，初始化，函數的調用及依次實現折半插入某一元素。 （1）輸入的形式和輸入值的范圍。 （2）輸出形式，即輸出時的元素個數和順序。 （3）程序所能達到的功能：完成線性表的生產以及某一元素的插入操作。 （4）測試數據： 先輸入一列有序數字：1 2 3 4 5 6 （偶數個），插入4。

2、 再重輸入一列有序數字：1 2 3 4 5 6 7 8 9（奇數個），插入5。3，概要設計： 本程序包含個函數：（1） 主函數main()；（2） 初始化線性表函數 linear_list()；（3） 插入元素函數 insert_linear_list()；各函數間的關系如下： Iinear_list Main Insert_linear_list4，詳細設計： 實現概要設計中定義的基本數據類型：（1）線性表類型和數組類型typedef struct Linear_list int aMaxSize; int last; ;（2） 線性表的基本操作 定義一個線性表指針變量，定義一個一維數組用于

3、存儲有序數字。再用一個折半插入算法進行插入操作。 Linear_list *InitList() Linear_list *L; L= (Linear_list *)malloc(sizeof(Linear_list); L->last = -1; return L;int Insert_Linear_list(Linear_list *L,int x)， ， ，5，調試分析（略）6，使用說明 直接進行編譯，連接，運行。 （1）首先要求輸入線性表的元素個數（在線性表的存儲范圍之類）； （2）其次初始化線性表，輸入一個有序數列； （3）再要求輸入插入的值x,再調用插入函數進行插入排序。 （

4、4）最后輸入排好的有序表。7，測試結果： （1）建立一個線性表：輸入：1 2 3 4 5 6 或者1 2 3 4 5 6 7 8 9 （2）插入：輸入3或者5得到線性表1 2 3 3 4 5 6或者1 2 3 4 5 5 6 7 8 9.（程序源代碼：）#include<stdio.h>#include<stdlib.h>#define MaxSize 100 typedef struct Linear_list int aMaxSize; int last; ;Linear_list *InitList() Linear_list *L; L= (Linear_lis

5、t *)malloc(sizeof(Linear_list); L->last = -1; return L;int Insert_Linear_list(Linear_list *L,int x)int low,mid1,mid2,high,i;low=0; high=L->last;mid1=(low+high)/2;if(L->last+1 > MaxSize) printf("此時存儲空間不夠，已越界!");if(x>L->amid1)low=mid1+1;if(x<L->amid1)high=mid1-1;else

6、if(x=L->amid1)printf("%d",mid1);mid2=mid1+1;for(i=L->last;i>=mid2&&i>=0;i-) L->ai+1=L->ai; L->amid2=x; L->last+;return(1);void main()struct Linear_list *L; int x,n; L = InitList(); printf("請輸入一個有序表的元素個數n(n<100)!:n");scanf("%d",&n);printf(" n");printf("請輸入有序表的元素值!n");for(int i=0; i < n; i+) scanf("%d", &L->ai);L->last+; printf(" n"); printf("請輸入需要插入元素x的值:"); scanf("%d",&x);printf("n"); Insert_Linear_list(L,x); printf("當x插入新元素后的有