第一篇：數據結構實驗報告表達式求值

數據結構實驗報告

題目：

編制一個表達式求值的程序。

一． 需求分析

1.本演示程序中，利用堆棧存儲結構存儲讀入的運算符，輸入的限定范圍是數字（0—9），以及+*/()。輸入字符串限定長度為20，可以根據需要進行改變。如果遇到不是以上范圍或者連續輸入兩個運算符，如：++，則會提示輸入錯誤，請重新輸入。輸出的結果是轉換后的后序表達式，以及float型數字，不會含有非法字符。

2.演示程序采用的是文件輸入，只需要在源代碼中輸入要輸入的文件的地址，然后就可以在文本文件中進行輸入，運行過程中會自動讀取，輸出文本輸入的表達式，及運算結果。3.程序執行的命令包括：

1）構造字符優先級比較表，比較優先關系 2）文件輸入 3）構造堆棧，運算符入棧 4）堆棧輸出，變為后序表達式，并計算 5）輸出結果，結束 4.測試數據

文件地址：C:UserslenovoDesktop4.txt

1)輸入：(35+20/2)*2-4/2+12 正確輸出結果是：100.0000 2)輸入：(35+20/2)*2-/2+12 結果是:error input

3)輸入：a+ar/3=135 結果是:error input

二．概要設計

為實現以上程序功能，需運用堆棧用于存儲運算符，因此需要定義抽象數據類型。1.堆棧的抽象數據類型定義為: ADT stack｛

數據對象:D={ai|ai∈正整數，i=0，1，2，3，…n,及｛+-*/()｝} 數據關系：R1={|ai-1,ai∈D} 基本操作： Init stack（&s）

操作結果：構造一個空的堆棧s Push stack（&s, e）初始條件：存在堆棧s 操作結果:元素e壓入堆棧s，top+1 Pop（&s，e）

初始條件：棧s已經存在且非空

操作結果：刪除棧頂元素e，輸出其值，top-1 2.程序包含三個模塊： 1）運算符優先關系模塊 2）主程序模塊;Int main(void){ 初始化； Do｛

接受命令； 處理命令； ｝while（“命令”=”退出”）； ｝ 3）堆棧模塊

三．詳細設計

1.程序源代碼解釋為：

float Result(int c,float r[],int top){

//定義輸出結果

int j;

float temp;

switch(c){

//以下是四種基本運算的計算定義，運算完成后直接將top-1值賦予top

case 42:r[top-1]=r[top-1]*r[top];top=top-1;break;

//乘法

case 43:r[top-1]=r[top-1]+r[top];top=top-1;break;///加法

case 45:r[top-1]=r[top-1]-r[top];top=top-1;break;//減法

case 47:r[top-1]=r[top-1]/r[top];top=top-1;break;// 除法

case 94:for(j=1,temp=r[top-1];j

temp=r[top-1]*temp;

//循環相乘

r[top-1]=temp;

top=top-1;

break;

}

return(r[top]);}

if(temp1!=1){ while(top>=1){

//棧不空的時候，棧中元素賦給houzhi，并計數

biaozhi[b++]=i;

houzhi[i]=duizhan[top-1];

top=top-1;i=i+1;

} max=i;

//從0到i循環輸出后序表達式 for(i=0,b=0;i

if(i!=biaozhi[b])printf(“%d ”,houzhi[i]);

//輸出后序表達式中的數字

else {

printf(“%c ”,houzhi[i]);

//輸出后序表達式中的運算符

b=b+1;

}

}

top=-1;for(i=0,b=0;i

//從0到max

if(i!=biaozhi[b]){

top=top+1;

result[top]=houzhi[i];

//將后值賦予result，調用result函數，進行Result運算

}

else {Result(houzhi[i],result,top);

//運算結束，輸出棧頂值，既是運算結果

top--;

b=b+1;

}

}

printf(“nnThe result is %f ”,Result(houzhi[i],result,top));

//輸出并打印結果

} } getch();return 0;///返回0 } 2.程序的模塊調用：

主程序 ↓

文件打開讀入字符

↓

輸入字符有效及優先級的判斷

↓ 運算模塊 ↓ 輸出結果

四.調試分析

1.本次作業的核心就是利用堆棧將中序表達式改成后序表達式，然后進行表達式的求值。具體思想就是當讀入數字時，直接輸出。當讀入運算符時如果不是后括號，直接將其進棧，順序比較讀入的運算符與棧頂元素的優先級（棧不空），如果棧頂元素的優先級高，則直接將其出棧并輸出。遇到后括號直接輸出棧中元素，直到遇到前括號。

2.算法的思想不是很復雜，在編程中只是加入了運算符的優先級比較表。以及如何獲得優先級的大小關系。起初在開始編制運算符優先級比較時，完全沒有想法，最后在網上學 習了一下，終于學會了如何建立比較表，通過練習也加深了對堆棧的掌握。總的過程還是可以的。

3.本題中也就只使用一堆棧存儲運算符，空間復雜度O與輸入的表達式中的運算符的多少有關，所以空間復雜度為O（n）(其實要小一點)，對于時間復雜度而言，不僅要

考慮讀入表達式的時間，還要考慮優先級的比較，進出棧，雖然比較多比較復雜，但是應該也是T（n）的數量級。

4.只是在WIN—TC下編譯運行了程序，并把直接運行時輸入改為了由文本文檔文件輸入，在進行改編的過程中，由于關閉文件的指針放的位置不對，還導致了輸出結果始終是0，通過改變指針的位置最終完成了文件輸入的改編。

五．心得體會

在本次實驗中，我負責表達式的輸出程序的編程，編寫了一個result函數來進行結果輸出。編程中遇到了很多困難，我們三個人也進行了很多次的討論，遇到無法解決的困難，則尋求其他大學同學的幫助。在商討算法的過程中，放棄了二叉樹的思想，改用堆棧的方式。由于我們大一學過C語言，其函數調用簡單方便，并且編寫小的程序非常方便，所以選擇了WIN-TC。

六．源代碼

#include “Stdio.h” #include “ctype.h” int find(char x){

int i;

char a[7]=“+-*/^()”;

for(i=0;;i++)

if(a[i]!=x&&i<7)continue;

else if(i<7)return(i+1);

else return(0);

}

char Compare(char c1,char c2){

char relat[7][7]={{'>','>','<','<','<','<','>'}，{'>','>','<','<','<','<','>'}，{'>','>','>','>','<','<','>'}，{'>','>','>','>','<','<','>'}，{'>','>','>','>','>','<','>'}，{'<','<','<','<','<','<','='}，{'>','>','>','>','>',' ','>'}};

return(relat[find(c1)-1][find(c2)-1]);

}

float Result(int c,float r[],int top){

int j;

float temp;

switch(c){

case 42:r[top-1]=r[top-1]*r[top];top=top-1;break;

case 43:r[top-1]=r[top-1]+r[top];top=top-1;break;

case 45:r[top-1]=r[top-1]-r[top];top=top-1;break;

case 47:r[top-1]=r[top-1]/r[top];top=top-1;break;

case 94:for(j=1,temp=r[top-1];j

temp=r[top-1]*temp;

r[top-1]=temp;

top=top-1;

break;

}

return(r[top]);}

int transe(char c[],int len){

int sum=0,i,j,temp;

for(i=0;i

for(j=0,temp=1;j

temp=temp*10;

sum=sum+(c[i]-'0')*temp;

}

return(sum);}

Int main(void){ char s[20],duizhan[20],temp[10];

float result[10];int houzhi[20]={0},biaozhi[10]={0};int i=0,j=0,m=0,top=0,b=0,done,n,temp1=0,cont,max;

FILE* fp = fopen(“C:UserslenovoDesktop4.txt”, “r”);

if(fp==NULL){printf(“cannot open filen”);

exit(0);} fscanf(fp, “%s”, s);

printf(“%sn”,s);

n=strlen(s);

for(j=0;j

if(!isdigit(s[j])&&!isdigit(s[j+1])&&s[j]!='('&&s[j+1]!='('&&s[j]!=')'&&s[j+1]!=')')

printf(“Eeeor input!nPress any key to continue!”);

else continue;

done=2;

}

if(done!=2){ for(j=0;j

if(isdigit(s[j])){

m=0;cont=1;

temp[m++]=s[j++];

done=0;

while(isdigit(s[j])&&j

temp[m++]=s[j++];

done=1;

cont++;

}

if(done==1)

houzhi[i++]=transe(temp,cont);

else houzhi[i++]=s[j-1]-'0';

}

else if(find(s[j])!=7&&(find(s[j])!=0))

{

if(top==0)duizhan[top++]=s[j++];

else{

done=0;

while(done==0){

switch(Compare(duizhan[top-1],s[j])){

case '<':duizhan[top]=s[j];

top=top+1;j++;

done=1;

break;

case '=':biaozhi[b++]=i;

houzhi[i]=duizhan[top-1];

top=top-1;

if(top==0){duizhan[top]=s[j];

top=top+1;j++;

done=1;

}

i=i+1;

break;

case '>':biaozhi[b++]=i;

houzhi[i]=duizhan[top-1];

top=top-1;

if(top==0){duizhan[top]=s[j];

top=top+1;j++;

done=1;

}

i=i+1;

break;

}

}

}

}

else if(find(s[j])==7){

while(duizhan[top-1]!='('){

biaozhi[b++]=i;

top=top-1;

houzhi[i]=duizhan[top];

i=i+1;

}

top=top-1;

j++;

}

else {

printf(“Eeeor input!nPress any key to continue!”);

temp1=1;

break;

} } if(temp1!=1){ while(top>=1){

biaozhi[b++]=i;

houzhi[i]=duizhan[top-1];

top=top-1;i=i+1;

} max=i;

for(i=0,b=0;i

if(i!=biaozhi[b])printf(“%d ”,houzhi[i]);

else {

printf(“%c ”,houzhi[i]);

b=b+1;

}

} top=-1;for(i=0,b=0;i

if(i!=biaozhi[b]){

top=top+1;

result[top]=houzhi[i];

}

else {Result(houzhi[i],result,top);

top--;

b=b+1;

}

}

printf(“nnThe result is %f ”,Result(houzhi[i],result,top));

} } getch();return 0;}

1.本程序的運行環境是WIN—TC，也可以是DOS操作系統，執行文件是***.exe。

2.文件的輸入直接是通過文本文檔，或其他，直接在源代碼中輸入打開文件的地址，然后操作均在文本中進行，比較方便。界面如下： 源代碼中地址輸入：

運行中界面：

七．測試結果

1.輸入正確的表達式：(24/2+12－4/2)+25/5*2

2.輸入：(32+1/3+14)*2+3^2/2

3.輸入字母，非法字符：ad+12xg

4.輸入連續的運算符：23++12

第二篇：數據結構實驗報告

注意：實驗結束后提交一份實驗報告電子文檔

電子文檔命名為“學號+姓名”，如：E01214058宋思怡

《數據結構》實驗報告

（一）學號：姓名：專業年級：

實驗名稱：線性表

實驗日期：2014年4月14日

實驗目的：

1、熟悉線性表的定義及其順序和鏈式存儲結構；

2、熟練掌握線性表在順序存儲結構上實現基本操作的方法；

3、熟練掌握在各種鏈表結構中實現線性表基本操作的方法；

4、掌握用 C/C++語言調試程序的基本方法。

實驗內容：

一、編寫程序實現順序表的各種基本運算，并在此基礎上設計一個主程序完成如下功能：

（1）初始化順序表L；

（2）依次在L尾部插入元素-1,21,13,24,8；

（3）輸出順序表L；

（4）輸出順序表L長度；

（5）判斷順序表L是否為空；

（6）輸出順序表L的第3個元素；

（7）輸出元素24的位置；

（8）在L的第4個元素前插入元素0；

（9）輸出順序表L；

（10）刪除L的第5個元素；

（11）輸出順序表L。

源代碼

調試分析（給出運行結果界面）

二、編寫程序實現單鏈表的各種基本運算，并在此基礎上設計一個主程序完成如下功能：

????

????

小結或討論:

（1）實驗中遇到的問題和解決方法

（2）實驗中沒有解決的問題

（3）體會和提高

第三篇：數據結構實驗報告

南京信息工程大學實驗（實習）報告

實驗（實習）名稱數據結構實驗（實習）日期 2011-11-2得分指導教師周素萍

系公共管理系專業信息管理與信息系統年級10級班次1姓名常玲學號2010230700

3實驗一順序表的基本操作及C語言實現

【實驗目的】

1、順序表的基本操作及 C 語言實現

【實驗要求】

1、用 C 語言建立自己的線性表結構的程序庫，實現順序表的基本操作。

2、對線性表表示的集合，集合數據由用戶從鍵盤輸入（數據類型為整型），建立相應的順序表，且使得數據按從小到大的順序存放，將兩個集合的并的結果存儲在一個新的線性表集合中，并輸出。

【實驗內容】

1、根據教材定義的順序表機構，用 C 語言實現順序表結構的創建、插入、刪除、查找等操作；

2、利用上述順序表操作實現如下程序：建立兩個順序表表示的集合（集合中無重

復的元素），并求這樣的兩個集合的并。

【實驗結果】

[實驗數據、結果、遇到的問題及解決]

一． Status InsertOrderList(SqList &va,ElemType x)

{

}

二． Status DeleteK(SqList &a,int i,int k)

{//在非遞減的順序表va中插入元素x并使其仍成為順序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x

}

//注意i的編號從0開始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK;

三．// 將合并逆置后的結果放在C表中，并刪除B表

Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)

{

LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驅指針 // 保存pb的前驅指針 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data

data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//將當前最小結點插入A表表頭 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//將當前最小結點插入A表表頭 A->next=qa;

}

} pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;

順序表就是把線性表的元素存儲在數組中，元素之間的關系直接通過相鄰元素的位置來表達。

優點：簡單，數據元素的提取速度快；

缺點：（1）靜態存儲，無法預知問題規模的大小，可能空間不足，或浪費存儲空間；（2）插入元素和刪除元素時間復雜度高——O（n）

求兩個集合的并集

該算法是求兩個集合s1和s2的并集，并將結果存入s引用參數所表示的集合中帶回。首先把s1集合復制到s中，然后把s2中的每個元素依次插入到集合s中，當然重復的元素不應該被插入，最后在s中就得到了s1和s2的并集，也就是在s所對應的實際參數集合中得到并集。

第四篇：數據結構實驗報告

數據結構實驗報告

一． 題目要求

1）編程實現二叉排序樹，包括生成、插入，刪除； 2）對二叉排序樹進行先根、中根、和后根非遞歸遍歷；

3）每次對樹的修改操作和遍歷操作的顯示結果都需要在屏幕上用樹的形狀表示出來。4）分別用二叉排序樹和數組去存儲一個班(50人以上)的成員信息(至少包括學號、姓名、成績3項),對比查找效率，并說明在什么情況下二叉排序樹效率高,為什么? 二． 解決方案

對于前三個題目要求，我們用一個程序實現代碼如下 #include #include #include #include “Stack.h”//棧的頭文件，沒有用上

typedefintElemType;

//數據類型 typedefint Status;

//返回值類型 //定義二叉樹結構 typedefstructBiTNode{ ElemType

data;

structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉樹函數

if(T==NULL){

T =(BiTree)malloc(sizeof(BiTNode));

T->data=key;

T->lChild=T->rChild=NULL;

return 1;} else if(keydata){ InsertBST(T->lChild,key);} else if(key>T->data){

InsertBST(T->rChild,key);} else

return 0;} BiTreeCreateBST(int a[],int n){//創建二叉樹函數 BiTreebst=NULL;inti=0;while(i

//數據域

InsertBST(bst,a[i]);

i++;} returnbst;} int Delete(BiTree&T)

{

BiTreeq,s;

} if(!(T)->rChild){ //右子樹為空重接它的左子樹

q=T;T=(T)->lChild;free(q);}else{

if(!(T)->lChild){ //若左子樹空則重新接它的右子樹

q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){

q=s;s=s->rChild;}

(T)->data=s->data;//s指向被刪除結點的前驅

if(q!=T)

q->rChild=s->lChild;

else

q->lChild=s->lChild;

free(s);} } return 1;

//刪除函數，在T中刪除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{

if(key==(T)->data)return Delete(T);

else{

if(key<(T)->data)

returnDeleteBST(T->lChild,key);

else

returnDeleteBST(T->rChild,key);

} } } intPosttreeDepth(BiTree T){//求深度

inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else

return 0;

} void printtree(BiTreeT,intnlayer){//打印二叉樹 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i

”);} printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){

while(NULL!=p)

{

printf(“%d ”,p->data);

stack[num++]=p;

p=p->lChild;

}

num--;

p=stack[num];

p=p->rChild;} printf(“n”);} void InOrderNoRec(BiTree root)//中序非遞歸遍歷 { BiTree p=root;

} intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){

stack[num++]=p;

p=p->lChild;} num--;p=stack[num];printf(“%d ”,p->data);p=p->rChild;} printf(“n”);void PostOrderNoRec(BiTree root)//后序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL;

while(NULL!=p||num>0){

while(NULL!=p)

{

stack[num++]=p;

p=p->lChild;

}

p=stack[num-1];

if(NULL==p->rChild||have_visited==p->rChild)

{

printf(“%d ”,p->data);

num--;

have_visited=p;

p=NULL;

}

else

{

p=p->rChild;

} } printf(“n”);}

int main(){//主函數

printf(“

---------------------二叉排序樹的實現-------------------”);printf(“n”);int layer;inti;intnum;printf(“輸入節點個數:”);scanf(“%d”,&num);printf(“依次輸入這些整數（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i

scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉樹創建成功!”);printf(“n”);layer=PosttreeDepth(bst);printf(“樹狀圖為:n”);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(“n”);printf(“

***********************按提示輸入操作符************************:”);printf(“n”);printf(“

1:插入節點

2:刪除節點

3:打印二叉樹

4:非遞歸遍歷二叉樹

5:退出”);scanf(“%d”,&j);

switch(j){

case 1:

printf(“輸入要插入的節點:”);

scanf(“%d”,&T);

InsertBST(bst,T);

printf(“插入成功!”);printf(“樹狀圖為:n”);

printtree(bst,layer);

break;

case 2:

}

printf(“輸入要刪除的節點”);scanf(“%d”,&K);DeleteBST(bst,K);printf(“刪除成功!”);printf(“樹狀圖為:n”);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4:

printf(“非遞歸遍歷二叉樹”);printf(“先序遍歷:n”);PreOrderNoRec(bst);printf(“中序遍歷:n”);InOrderNoRec(bst);

printf(“后序遍歷:n”);

PostOrderNoRec(bst);

printf(“樹狀圖為:n”);

printtree(bst,layer);

break;case 5:

printf(“程序執行完畢!”);

return 0;} goto loop;} return 0;對于第四小問，要儲存學生的三個信息，需要把上面程序修改一下，二叉樹結構變為 typedefintElemType;

//數據類型 typedefstring SlemType;

typedefint Status;

//返回值類型 //定義二叉樹結構 typedefstructBiTNode{ SlemType name;ElemType score;ElemType no;

//數據域 structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;參數不是key,而是另外三個

intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉樹函數

if(T==NULL){

T =(BiTree)malloc(sizeof(BiTNode));

T->no=no;T->name=name;T->score=score;

T->lChild=T->rChild=NULL;

return 1;} else if(nono){ InsertBST(T->lChild,no,score,name);} else if(key>T->data){

InsertBST(T->rChild,no,score,name);} else

return 0;} 其他含參函數也類似 即可完成50個信息存儲

用數組存儲50個信息，查看以往代碼

#include #include using namespace std;class student{ private: intnum;string name;int ob1;int ob2;intara;public: void set(inta,stringb,intc,int d);void show();int average();};void student ::set(inta,stringb,intc,int d){ num=a;name=b;ob1=c;ob2=d;ara=(c+d)/2;} void student::show(){ cout<<“學號：”<

int main(){ cout<<“ 歡迎來到學生管理系統”<>numlock;switch(numlock){ case 0: cout<<“輸入想查詢的學號”<>i;if(i==j){ cout<<“該學號信息已被刪除”<>j;delete[j]ptr;cout<<“刪除成功”<>k;if(k!=j){

cout<<“該學號信息已經存在，添加失敗”<

break;} cout<<“重新輸入添加的學號”<>q;cout<<“輸入姓名”<>w;cout<<“輸入科目一的成績”<>e;cout<<“輸入科目二的成績”<>r;ptr[k].set(q,w,e,r);break;case 3: for(m=1;m<20;m++){

for(int n=m+1;n<20;n++){

if(ptr[m].average()

student a;

a=ptr[m];

ptr[m]=ptr[n];

ptr[n]=a;

}}

ptr[m].show();} break;case 4: cout<<“謝謝使用”<

二叉排序樹儲存數據界面（儲存學生信息略）

創建二叉樹：

插入節點：

刪除節點：

非遞歸遍歷：

退出：

數組儲存學生信息界面

分析查找效率：

因為二叉樹查找要創建二叉樹，而數組查找只創建一個數組，二叉樹的創建時間比較長，所以對于數據量較少的情況下數組的查找效率比較高。但當數據量增加時，二叉樹的查找優勢就顯現出來。所以數據量越大的時候，二叉樹的查找效率越高。

四． 總結與改進

這個實驗工作量還是很大的，做了很久。樹狀圖形輸出還是不美觀，還需要改進。

一開始打算用棧實現非遞歸，但是根據書里面的偽代碼發現部分是在C++編譯器里運行不了的（即使補充了頭文件和數據的定義），所以之后參考了網上的數組非遞歸，發現其功能和棧相似。

遞歸遍歷的實現比非遞歸的遍歷真的簡單很多。

開始時只看到前三問，所以沒有寫到儲存學生數據的代碼，里面還可以用clock（）函數加一個計算查找所要數據時間的代碼，讓二叉樹查找與數組查找到效率比較更加直觀。

第五篇：數據結構實驗報告

實驗報告4 排序

一、實驗目的

1、掌握常用的排序方法，并掌握用高級語言實現排序算法的方法。

2、深刻理解排序的定義和各種排序方法的特點，并能加以靈活應用。

3、了解各種方法的排序過程及其依據的原則，并掌握各種排序方法的時間復雜度的分析方法。

二、實驗要求及內容

要求編寫的程序所能實現的功能包括：

1、從鍵盤輸入要排序的一組元素的總個數

2、從鍵盤依次輸入要排序的元素值

3、對輸入的元素進行快速排序

4、對輸入的元素進行折半插入排序

三、實驗代碼及相關注釋

#include using namespace std;#include “malloc.h”

typedef struct { int key;}RedType;

typedef struct { RedType r[100];int length;}SqList;

//1 快速排序的結構體

typedef struct {

int data[100];

int last;}Sequenlist;//2 折半插入排序的結構體

int Partition(SqList &L, int low, int high)

//1 尋找基準

{

L.r[0]=L.r[low];//子表的第一個記錄作基準對象

int pivotkey = L.r[low].key;//基準對象關鍵字 while(low

while(low= pivotkey)--high;

L.r[low] = L.r[high];//小于基準對象的移到區間的左側

while(low

L.r[high] = L.r[low];//大于基準對象的移到區間的右側 }

L.r[low] = L.r[0];return low;}

void QuickSort(SqList &L, int low, int high)

//1 快速排序 { //在序列low-high中遞歸地進行快速排序

if(low < high)

{

int pivotloc= Partition(L, low, high);

//尋找基準

QuickSort(L, low, pivotloc-1);//對左序列同樣遞歸處理

QuickSort(L, pivotloc+1, high);//對右序列同樣遞歸處理

} }

Sequenlist *Sqlset()

//2 輸入要折半插入排序的一組元素

{

Sequenlist *L;

int i;

L=(Sequenlist *)malloc(sizeof(Sequenlist));

L->last=0;

cout<<“請輸入要排序的所有元素的總個數：”;

cin>>i;

cout<

cout<<“請依次輸入所有元素的值：”;

if(i>0)

{

for(L->last=1;L->last<=i;L->last++)

cin>>L->data[L->last];

L->last--;

}

return(L);}

middlesort(Sequenlist *L)

//2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){

L->data[0]=L->data[i];

low=1;

high=i-1;

while(low<=high)

{

mid=(low+high)/2;

if(L->data[0]data[mid])

high=mid-1;//插入點在前半區

else

low=mid+1;//插入點在后半區

}

for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移

L->data[high+1]=L->data[0];//插入 } return 0;}

int main(){ gg: cout<<“請選擇功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout<

if(m==1){ SqList L;int n;cout<<“請輸入要排序的所有元素的總個數：”;cin>>n;cout<

cin>>L.r[i].key;

} cout<

QuickSort(L,1,L.length);

for(int j=1;j<=L.length;j++)

{

cout<

}

cout<

cout<

}

if(m==2){

Sequenlist *L;

int i;

L=Sqlset();

cout<

middlesort(L);

cout<<“折半插入排序后為：”;

for(i=1;i<=L->last;i++)

{

cout<data[i]<<“ ”;

}

cout<

cout<

goto gg;}

if(m==3){

exit(0);

cout<

四、重要函數功能說明

1、Sequenlist *Sqlset()

輸入要折半插入排序的一組元素

2、int Partition(SqList &L, int low, int high)

尋找快速排序的基準

3、void QuickSort(SqList &L, int low, int high)

快速排序

4、middlesort(Sequenlist *L)

折半插入排序

五、程序運行結果

下圖僅為分別排序一次，可多次排序，后面有相關截圖：

六、實驗中遇到的問題、解決及體會

1、起初編寫快速排序的程序時，我是完全按照老師PPT上的算法敲上去的，然后建立了一個SqList的結構體，調試運行時出現錯誤，仔細查看才意識到Partition函數中L中應該包含元素key，而我建立結構體時沒有注意，然后我將key這個元素補充進去，繼續調試，又出現錯誤，提示我Partition沒有定義，我就覺得很奇怪，我明明已經寫了函數定義，為什么會這樣，當我又回過頭來閱讀程序時，我發現QuickSort函數中調用了Partition函數，但是我的Partition函數的定義在QuickSort函數的后面，于是我將Partition函數放到了QuickSort函數的前面，再次調試運行，就可以正常運行，得出結果了。這讓我懂得，編程一定要認真仔細，不可大意馬虎，否則又會花很多時間回過頭來檢查修改程序，得不償失。

運行程序錯誤截圖：

2、本來我是編寫了兩個程序，分別實現快速排序和折半插入排序的功能，但我后來想我是否可以將其合二為一，于是我想到用if選擇語句用來實現不同的功能，從鍵盤輸入功能選項m，if（m==1），可以進行快速排序，if（m==2），可以進行折半插入排序，于是我繼續思考，我是否可以在一次運行程序中，多次對含有不同元素的序列進行排序，于是我用了goto語句，每次排序一次后，自動循環到選擇語句，當不需要在排序的時候，可以從鍵盤輸入3，退出程序，這樣一來，程序變得更加實用和清晰明朗。這讓我懂得，想要編出好的程序，要善于思考，在實現所需功能的前提下，多想問題，看是否能使程序更加實用簡便。

修改程序前兩個運行結果截圖

（兩個程序，調試運行兩次，每次只能進行一次排序）

1、快速排序程序運行結果截圖：

2、折半插入排序程序結果截圖：

程序重要模塊修改截圖：

修改程序后運行截圖：

（一個程序，調試運行一次，可多次進行不同序列的不同排序）