數據結構實驗 實驗四 - 下載本文

設計四

查找和排序

一、 設計目的

1.掌握順序查找,二分法查找,分塊查找的算法; 2.掌握各種排序算法及其性能的比較。

二、 設計內容

1. 任務描述

任務1:編寫一個程序輸出在順序表{13,22,35,43,54,68,71,82,98,1005}中采用順序方法和折半方法查找某個關鍵字的過程。

任務2:編寫一個程序實現直接插入排序過程,并輸出{94,28,57,66,35,84,63,42,71,10}的排序過程。

任務3:編寫一個程序實現快速排序算法,并輸出{94,28,57,66,35,84,63,42,71,10}的排序過程。

2. 問題的表示方案

使用一個順序表存儲所有輸入數據,一個整型變量存儲數據長度

3. 主要數據類型與變量

int data[MAXSIZE]; int Count;

4. 算法或程序模塊

任務1:

void Sequence(ostream &out, int key)

功能:順序查找

void Half(ostream &out, int key)

功能:折半查找 任務2:

void InsertSort(ostream &out)

功能:直接插入排序 任務3:

int Partition(int low, int high)

功能:把待排序數組分為兩部分,使基準元素左邊的元素都小于基準元素,右邊的都大于基準元素。

void QuickSort(ostream &out, int left, int right)

功能:快速排序

三、 測試

1. 方案

任務1:

測試方案:輸入表中存在的元素,輸入表中不存在的元素

測試數據:順序表{13,22,35,43,54,68,71,82,98,1005},key=68,key=32。 任務2、3:

測試數據:數組{94,28,57,66,35,84,63,42,71,10}

2. 結果

四、 總結與討論

本設計還存在的問題有:

1、 使用int型的一維數組存儲數據,未考慮數據不為整型等情況。 可以做的改進:

1、 使用double類型進行存放

附:程序模塊的源代碼

class Find {

protected:

int data[MAXSIZE]; int Count; //初始化查找實例 //Data:數組數據 //length:數組長度

Find(int Data[], int length) { }

//順序查找 //out:輸出流 //key:查找的關鍵字

void Sequence(ostream &out, int key) { }

//折半查找 //out:輸出流 //key:查找的關鍵字

void Half(ostream &out, int key) {

int high = Count - 1; int low = 0; int mid = 0; while(low <= high) {

mid = (low + high) / 2; out << data[mid] << \; //小于則向后查找

for(int i = 0; i < Count; i++) { }

out << endl;

out << data[i] << \; if(data[i] == key)

break;

Count = length;

for(int i = 0; i < length; i++) { }

data[i] = Data[i];

public:

};

}

}

if(data[mid] < key)

low = mid + 1; //大于則向前查找

else if(data[mid] > key)

high = mid - 1; //相等則停止 else { }

out << \查找成功!\ << endl; return;

out << \查找失敗!\ << endl;

class Sort {

protected:

int data[MAXSIZE]; int Count;

int Partition(int low, int high) { }

void Swap(int i, int j) { }

int temp = data[i]; data[i] = data[j]; data[j] = temp; int i, k = low; int pivot = data[low];

for(i = low + 1; i <= high; i++) { }

data[low] = data[k]; data[k] = pivot; return k;

if(data[i] < pivot) { }

k++; if(k != i)

Swap(i, k);

public:





黑龙江22选5兑奖期限