數(shù)據(jù)結構-最短路徑

江南大學物聯(lián)網(wǎng)工程學院上機報告

課程名稱數(shù)據(jù)結構上機名稱排序上機日期2022-5-22

班級計科1203姓名汪俊學號1030412314

上機報告要求1.上機名稱2.上機要求3.上機環(huán)境4.程序清單(寫明運行結果)5.上機體味

1.上機名稱

排序，實驗5

2.上機要求

調試實驗一，補充實驗2主函數(shù)，完成實驗3

3.上機環(huán)境

VisualC++6.0

4.程序清單(寫明運行結果)

、

#include<stdio.h>

#defineN10

#defineFALSE0

#defineTRUE1

typedefintKeyType;

typedefcharInfoType;

typedefstruct

(

KeyTypekey;

InfoTypeotherinfo;

JRecType;

typedefRecTypeSeqlist[N+1];

intm,num;〃全局變量m存儲輸出的是第幾趟結果，num存儲遞歸調用的次數(shù)

SeqlistR;

voidInsertsort();

voidBubblesort();

voidSelectsort();

voidmain()

(

SeqlistS;

inti;

charchl,ch2;

請輸入10個待排序的數(shù)據(jù)：每兩個數(shù)據(jù)間用空格隔開

for(i=l;i<=N;i++)

chl-y';

while(ch1=-y'||ch1='Y')

(

菜單

請選擇下列操作

更新待排序數(shù)據(jù)

直接插入排序

冒泡排序

直接選擇排序

退出

請選擇操作類別

switch(ch2)

{

caseT:

請輸入更新待排序數(shù)據(jù)

for(i=l;i<=N;i++)

break;

case2:

請輸入要輸出第幾趟排序結果

for(i=l;i<=N;i++)

R[i].key=S[i].key;

Insertsort();

break;

case3:

請輸入要輸出第幾趟排序結果

for(i=l;i<=N;i++)

R[i].key=S[i].key;

Bubblesort();

break;

case4:

請輸入要輸出第幾趟排序結果

for(i=l;i<=N;i++)

R[i].key=S[i].key;

Selectsort();

break;

case5:

chl-n*;

break;

default:

chl-n1;

voidInsertsort()

(

inti,j,k;

for(i=2;i<=N;i++)

(

if(R[i].key<R[i-l].key)

{

R[0]=R[i];

j=i-l；

while(R[O].key<R[j].key)

{/*從右向左在有序區(qū)R[1....i+1查]找R[i]的插入位置*/

RU+1]=RU1；

R[j+1]=R[O];

)

if(i-l==m)

!

第％d趟的結果是

for(k=1;k<=N;k++)

請輸入還想輸出第幾趟結果，不想輸出時請輸入

if(m!=0)

(

最終排序結果是

for(k=l;k<=N;k++)

voidBubblesort()

〃自下向上

inti,j,k;

intexchange;

for(i=l;i<=N;i++)

{〃最多做N-l趟排序

exchange=FALSE;

for(j=N-l;j>=i;j-)

!

if(R[j+l].key<R[j].key)

(

R[O]=R[j+l];

R[j+1]=RU]；

R[j]=R[O]；

exchange=TRUE;

)

)

if(i==m)

(

第％(1趟的結果是

for(k=l;k<=N;k++)

請輸入還想輸出第幾趟結果，不想輸出時請輸入

)

ifi；(!exchange)11(m=0))

break;

)

if(m!=O)

(

最終排序結果是

for(k=1;k<=N;k++)

voidSelectsort()

(

inti,j,k,h;

for(i=l;i<N;i++)

h=i；

for(j=i+1；j<=N;j++)

if(R[j].keyvR[h].key)

h=j；

)

if(h!=i)

!

R[O]=R[i];

R[i]=R[h];

R[h]=R⑼；

)

if(i==m)

[

第％d趟的結果是

for(k=l;k<=N;k++)

請輸入還想輸出第幾趟結果，不想輸出時請輸入

if(m!=O)

{

最終排序結果是

for(k=l;k<=N;k++)

--?、

#include<stdio.h>

#defineN4

#definefalse0

#defineture1

typedefintkeytype;

typedefcharinfotype;

typedefstruct

{

keytypekey;

infotypeotherinfb;

Jrectype;

typedefrectypeseqlist[N+1];

intm,num;

seqlistR;

voidquicksort(seqlist&R,ints,intt)

(

inti=s,j=t;

if(i<j)

(

R[0]=R[i];

do

while(i<j&&R[j].key>=R[O].key)

j-;

if(i<j)

(

R[i]=RUl；

i++；

)

while(i<j&&R|i].key<=R[O].key)

i++；

if(i<j)

(

R|j]=R|i]；

j-；

}

}while(i<j);

R[i]=R[O]；

quicksort(R,s,j-l);

quicksort(R,j+l,t);

)

)

voidshellsort(seqlist&R,intn)

(

inti,j,gap;

gap=n/2;

while(gap>0)

!

for(i=gap;i<=n;i++)

(

R[0]=R[i];

j=i-gap;

while(j>-l&&R[O].key<R[j].key)

(

R|j+gap]=R[j];

j=j-gap；

)

R|j+gap]=R[0];

j=j-gap；

)

gap=gap/2;

)

)

voidsift(seqlist&R,intv,intn)

inti,j;

1=V；

j=2*i;

R[O]=R[i];

while(j<=n)

(

if(j<n&&R[j].key<R[j+l].key)

j++;

if(R|O].key<R[j].key)

(

i=j；

j=2*i；

}

else

j=n+l；

}

R[i]=R[O];

)

voidheapsort(seqlist&R,intn)

(

inti;

for(i=n/2;i>=l;i—)

sift(R,i,n);

for(i=n;i>=2;i—)

{

R[0]=R[i];

R[i]=R[l]；

R[1J=R[O];

sift(R,l,i-l)；

)

)

voidshow(seqlist&R,intn)

(

inti;

for(i=l;i<=n;i++)

voidmain()

seqlistS;

inti;

charchl,ch2;

請輸入4個待排元素：(每兩個數(shù)據(jù)間用空格隔開)

for(i=l;i<=N;i++)

chi=y；

while(chl==y||chl—Yf)

(

菜單

請選擇下列操作：

更新待排數(shù)據(jù)

快速排序

希爾排序

堆排序

退出

請選擇操作類型：

switch(ch2)

{

case'l':

請輸出更新待排數(shù)據(jù)：

for(i=l;i<=N;i++)

break;

case'2':

quicksorts』,4);

show(S,4)；

break;

case'S*:

shellsort(S,4)；

show(S,4)；

break;

case14':

heapsort(S,4);

show(S,4)；

break;

case5:

chl-n';

break;

default:

chl=H;

三、#include<stdio.h>

#include<string>

#include<iostream>

usingnamespacestd;

#defineN6

#definefalse0

#defineture1

typedefintkeytype;

typedefstrinjinfotype;

typedefstruct

(

keytypepaim;

keytypekey;

infbtypeotherinfb;

Jrectype;

typedefrectypeseqlist[N+1];

intm,num;

seqlistR;

voidquicksort(seqlist&R,ints,intt)

inti=s,j=t;

if(i<j)

(

R[O]=R[i];

do

{

while(i<j&&R[j].key>=R[0].key)

j-；

if(i<j)

{

R[i]=R[j]；

i++；

)

while(i<j&&R[i].key<=R[O].key)

i++；

if(i<j)

(

R[j]=R[i]；

j-；

)

}while(i<j);

R[i]=R[0];

quicksort(R,s,j-l);

quicksort(R,j+l,t);

}

1

voidshellsort(seqlist&R,intn)

(

inti,j,gap;

gap=n/2;

while(gap>0)

I

for(i=gap;i<=n;i++)

(

R[0]=R[i];

j=i-gap;

while(j>=l&&R[O].key<R[j].key)

(

RU+gap]=R[j]；

j=j-gap；

}

RU+gap]=R[0];

j=j-gap；

gap=gap/2;

voidsift(seqlist&R,intv,intn)

inti,j;

i=v;

j=2*i;

R[0]=R[i];

while(j<=n)

(

ifG<n&&R[j].key<R[j+l].key)

j++;

if(R[O].key<R[j].key)

{

R[i]=RUl;

i=j；

j=2*i;

)

else

j=n+l;

)

R[i]=R[0];

)

voidheapsort(seqlist&R,intn)

(

inti;

for(i=n/2;i>=l;i—)

sift(R,i,n);

for(i=n;i>=2;i—)

{

R[0]=R[i];

R[i]=R[U;

R[1]=R[O]；

sift(R,l,i-l)；

)

)

voidshow(seqlist&R,intn)

(

int

for(i=6;i>=l;i-)

(

R[i].paim=7-i;

if(R|i|.key==R|i+1J.key)

R[i].paim=R[i+l].paim;

姓名為：

成績?yōu)?

名次為：

)

)

voidmain()

seqlistS;

inti;

charchl,ch2;

請輸入6個成績：

fbr(i=l;i<=N;i++)

請輸入6個學生姓名：

for(i=l;i<=N;i++)

cin?S[i].otherinfo;

chl=y；

while(chl='y'||chl—Y*)

(

菜單

請選擇下列操作：