数据结构实训一(顺序表)

数据结构实训一（顺序表）

#include<srdio.h>

#mclude<conio.h>〃包含getchQ函数

#include<stdlib.h>

^defineMAXSIZE1000

"定义顺序表类型

typedefmtElemTpe;

typedefstiuct(

ElemTypedatafMAXSIZE];

intlength;

}SeqList;〃给顺序表类型起-个别名SeqList;

〃定义接II

mtLiputChoice(jy/iS择函数

voidInitList(SeqList*List);//初始化顺序表

voidDisphy(SeqListList);n显示函数

voidlusE(SeqList*List);〃插入函数

voidSearch(SeqListList)〃查找函数

voidDelete(SeqList*List);//删除函数

voidSiinpleSort(SeqListList)〃简单选择排序

intPanition(SeqListList,mtleftjntright);〃，快排分割调整

voidQuicksort(SeqListintleft,intright);〃'快速其F序

voidBuiaiySeaich(SeqListList)〃折半查找

voidInveser(SeqListList);〃逆置顺序表

voidInseiISoit(SeqListList);〃直接插入排序

voidBubbleSoit(SeqListList)〃冒泡排序

voidOrderliisert(SeqList*List);〃W序插入

voidDeleteBehveeiiXY(SeqList礼ist);〃®|I除介于X和Y之间的俱

voidMergeList(SeqList*List_LSeqList*List_2.SeqLisr*List_3);u合并顺序表voidSplitList(SeqList

*List_l,SeqList*List_2,SeqList*List_3)〃拆分顺序表voidSheUSon(SeqListList);〃希尔排序

voidHeapAdjust(SeqList*List,mtroot,inrlength);〃建立大顶堆

voidHcapSort(SeqListList);〃堆排序

voidmain。

(

intmyChoice;

SeqListList;

SeqListList1;

SeqListList2;

SeqListList.3;

wlule(l)

(

systein(McisM);

myClioice=IiiputChoiceO;

switch(my*Choice)

(

case0:

exit(0);

break;

case1:

TnitList(&List);

break;

case2:

printf("当前顺序表为：“)；

Display(List);

getchO；

break;

case3:

liisert(&List);

break;

case4:

Seaich(IJst);

break;

case5:

Delete(ftList);

break;

case6:

SmipleSon(List);

break;

case7:

prmrf(排序前：”)；

Display(List);

Quicksort(&List,0,List.length-1);

prmtf(”“快速排序成功!S由于能力有限,暂无法计算挪移和比较次数…‘心山”);

printf(”排序后：〃)；

Display(List);

getchO;

break;

case8:

BinarySearch(List);

break;

case9:

Inveser(List);

break:

case10:

InsenSon(List);break;

case11:

BubbleSort(List);

break;

case12:

Orderhisen(&List);

break;

case13:

DeleteBetweeiiXY(&List);break;

case14:

MergeList(&List_l,&List_2,&List_3);break;

case15:

Spli(List(&List_L&List_2.&List_3);break;

case16:

HeapSon(List);break;

case17:

ShellSon(List);break;

default:

break;

}

)

)

〃选择函数

mtliiputChoiceQ

(

mtmyChoice;

print町\n\iT);

pimtf*\t\t\t\t网页序表操作\n"):

pnntff,\t\t----------------------------------------------\n");

pnntR>>\t\t1：初始化\t")；pnntRu\t\t2:显示W);

priiitfC\t\t3：插入W);

prmtff\t\t4：查找\n")；

prmtfC\t\t5：删除\t")：

prmtf(*\t\t6：简单选择排序\n”)；

pnntRw\t\t7：快速排序\t")；

pnntff\t\t8：折半查找\n”)：

prmtfr\t\t9：逆置线性表\t”)：

priiitf(*\t\t10：直接插入排序\n")；

pimtf^VtXt11：冒泡排序\t")；

prmtfl*\t\t12：有序插入山”)；

printf(M\t\t13：删除介于X&Y值之问的数“);prmtf("\t14：合并顺序表

E");prmtf15：拆分M页序表\f)；

pnntff,t16：堆排序\n")；prmtf("\t\t17：希尔排序W);

priiitf(*\t\t0：退出\n");

print---------------------------------------------------〃)；

pnntR〃\l\t\r请选择：")：scaiif(w%d\&myChoice);

pnntRW);

retuinmyClioice;

)

〃初始化

voidImtList(SeqList*List)

{

iiitlength,seed;

pimrfT请输入元素个数(0-%d)：M,MAXSIZE);

while(1)

(

scaiif(M%d\<Srlength);

if-lengtli>=0&&lengtli<=MAXSIZE)break;

else

printf("您的输入不合法，请重新输入;

}

pun顷-请输入随机数种子(0-32767):;whUe(1)

(

scaiif(W,&seed);ifseed>=0&&seed<=32767)break;

else

printf("您的输入不合法，请重新输入;

)

srand(seed);

"初始化数据和长度

fbr(inti=0:i<length;i++)List->data[i]=rand()%90+10;

for(intj=lengtliMAXSIZEj++)List->dataIj]=O,

List->leiigth=length;

pnntfT初始化成功...’n")；

getchO；

〃显示函数

voidDisplay(SeqListList)

i=0;i<List.length;i++)printR"%dWJ.istdata[i]);

pnntffp")；

)

〃插入函数

voidInsen(SeqList*List)

{

intlocauon.element,

prints当前顺序表为：");

Display(*List);

〃判断是否溢出

if(List.>lengrh—MAXSIZE)

printf—该顺序表存储空间己满.无法继续插入…侦)；else

(

pnnif(”\n请输入插入位置：”)；

while(1)

(

scanfV*%d”,&locau(m);

if(location>0&&location<=List->length)break;

else

pnntf(“插入位置不合法，请重新输入■>：")；}prmrf(〃请输入插入的

元素：”);

scanf("%d”.&eleinent),

List->length++;

foi(inti=List->leugth-l;i>=location;i-)

List->data[i]=IJst->data[i-1];

List->data[location-1]=element;

pnniR“兀素%d插入％d位置成功…\n‘,elementJoca(ion);pnntR”插入后顺序表

为：”);

Display(*List);

getchO；

"查找函数

voidSeaicli(SeqListList)

(

ElemTypeelement;

inti=0;

pimtff请输入要查找的兀素：“)；scanf(%d\&element);

while(i<List.lengtli)

if^List.data[i++]=elemeuT)

break;

pnntfT整个查找过程共挪移了％d次

if(i<List.lengtli)

(

pnntR"查找成功…"”)；

prmtfl"兀素%d在顺序表中的位置是：版I",element,i);}else

(

pimtfl〃查找失败..An“)；

pnntR”在该顺序表中未找到兀素％delement);

}

getcliQ;

}

"删除函数

voidDelete(SeqList*List)

(

intelement;

血i=0j;

pnntfC请输入要删除的元素：“)；

scanf("%(!1\<Sre1emenr);

while(i<List->leng±)

if"IJst->data[i++]=element)break;

prints本次删除共比较次，挪移%一次

if(i<List->length)

(

fdr(j=ij<List->length;j++)List->data[j-l]=List->data[j];

prmtR”删除成功..NT);

prmtff•删除后的顺序表为：”)；

〃顺序表长度减一

List->length—;

Display(*List);

)

else

pnnifC删除失败，该顺序表中不含有一元素刎element);getch(J;

)

〃简单选择排序

voidSimpleSort(SeqListList)

intij.nun;

iiitiCount=0jCount=0;

pnntf(n排序前：”)；

Display(List);

fbr(i=0;i<List.lengtli-1;i++)

{

mm=i;

for(j=i+lj<List.lengtlij++)

{

if(List,datalj]<List.datafmin])

mm二j;

jCouiit++;

List.data[i]List.data[i]+List.data[min];

List.data[niin]=List.data[i]-Lisr.data[min];List.data[i]=List.data[i]-List.data[miii];

)

iCount+*;

)

pnntfC简单选择排序共挪移：%d次,比较了:%d次…\n”，iCoimt+jCoimt,jCoimt);pnntf("

排序后：”);

Display(List);

getchO；

)

〃分割数据将无序数列首项中间(左小-首项-右大)位置

intPanitiou(SeqList*List,mtleft,intlight)

{

inti=leftj=nght,temp;

temp=List->data[i];

whileo!』J

(

while(i<j&&List->data[j]>=Temp)

1R1VJ)

List->data[i]=List->data[j];

while(i<j&&List->data[i]<=teinp)

1++;

如勺)

List->data[j]=Lis(->data[i],

)

List->dcita[i]=temp;

returni:

"快速排序

voidQinckSort(SeqList*Lisr.mtleft,mtright)

(

inti;

if(left<nght)

(

i=Panition(List,left,right);

Quicksort(List1);

QuickSon(List4+1jight);

"折半查找

voidBuiaiySeaich(SeqListList)

iiitcount=0//i己录比较次数mtelementJow.mid.high;1ow=0:

high二List,length-1;

pnntfT请输入要查找的元素：");scanf("%d\&element);

"快速排序使其成为有序数列

Quicksort(&List,0,List,lengthJ)；

wlnle(low<=higli)

(

mid=(low+high)/2;

coxuit-1~;

if-List,data[mid]—element)

break;

else

if(List,data[nud]<element)low=mid+];

else

lugli=mid-l;

)

pirntfC,本次查找次数为：.\i『count);

if(low<=lugh)

(

pnntf(w查找成功…W);

pnntR"兀素刎在顺序表中的位置是：%d.element.nud-l);}else

(

pnntR”查找失败…，iT)；

pnntR“兀素%d不在该顺序表中...8"，element);

)

getcliQ;

}

〃逆置顺序表

voidInvesei(SeqIJstList)

(

mtj=List.lengtli-1;

pimtfc逆置前：”);

Display(List);

fbr(inti=0:i<Lisr.lengthA;i++)

(

List.data[i]=List.data[i]+List.data[j];

List.data[j]=List.data[i]-List.data(j];

List.data[i]=List.data[i]-List.data[j];

)prmtT逆置后：”);Display(List);

getcho;

)

〃直接插入排序

voidInseiISoit(SeqListList)

(

intij.k,temp;printfC升F序育If:")；Display(Lisr);

j<List.lengthj++)

if(List.data(j]>List.data[i])break:

tenip=List.data[j]tfbr(k=j;k>i+l;k••)

List.data[k]=List.data[k­l];

List.data[i+l]=teinp;

)

}pnntff排序后：”);Display(Lisr);

getchO；

1

〃冒泡排序

voidBubbleSoil(SeqListList)

pant町,封E序刖：");Display(Lisr);

inti,j=List.lengtli-1;

\vhile(j>0)

(

for(i=0;i<j;i++)

if(List.data[i]>List.data[i+l])

(

List.data[i]=List.data[i]+List.data[i+l];

List.data[i+l]=List.data[i]-Listdata[i+l];

List.data[i]=List.data[i]-List.data[i+l];

pnntff•排序后：");

Display(List);

getcliQ;

}

"有序插入

voidOrderliisert(SeqList*List)

(

〃溢出判断

if(List->length>=MAXSIZE)

prmtfC•顺序表存储空间己满，无法进行插入操作...3)；else

(

uu1j.element;

"快排使其成为有序数列

QuickSoil(List,0,List->lengtli~l);

printf("插入前：");

Display(*List);

pnntff");

prinlf(”请输入要插入的元素：");scanf(,，%dv,&element);

〃根据数值大小找到插入位置for(i=0;i<List->length;i-H-)if(element<List->data[i])

break;

List->length++;//表长加一1〃空出插入位置后赋值插入for(j=List->Iengtli-1j>ij—)

List->data[j]=List->data[j­l];

List->data[iJ=element;

printf(“本次插入比较的次数为：%d,挪移的次数为：％d.\n\iJList^>length-M);

pnnif("插入后：”);

Display(*List);

)getcho；

〃删除X利Y之间的值

voidDeleteBerweeiiXY(SeqList*List)

{

mtm,n,maxjnui;

mti,j=0;

pnntfT删除前：”),

Display(*List);

pnntf("请输入要删除的范围…公司；

pnntR”最大值：”)；

pnntf("最小值：”)；

(

prmtf("您的输入不和逻辑，系统将自动更正m=m+n;

n=m-n;

m=ni-n;

)

niax=m;

miii=n;

fbi(i=0;i<List->lengdi;i++)

〃遍历所有数值，不在*和丫之问的值赋值给U]

if^List->data[i]<niui||List->data[i]>max)

List->data[j++]=List->data[i];

List->length=j;

pnntf(w删除后i");

Display"List);

getchO；

)

"合并顺序表

voidMergeList(SeqList*List_l.SeqList*List_2.SeqList*List_3){

intij.k;

prmtfT初始化顺序表L..M")；

IiutList(List_l);

pnntffW);

pimtfT初始化顺序表2...3);

ImtList(List2),

pimtif侦');

QuickSon(List1.0,List1->length-l);

QuickSoiT(List_2.0Xist_2->lengtli-l);pnntR”合并前..An")；pnntfT顺序表1：”）；

Display(*List1);

pnntR”顺序表2：”);

Display(*List_2);

"比较两个表中是否存在相同的值

fbr(i=0;i<List_l->lengthsi++)

for(j=0:j<List_2->lengthj++)

if(List_2->data[j]=List_l->data[i])

List_l->data[i]=-l;

1=0；j=0;k=0;

"当两个表同时存在时

wlule(i<List_1->length&&j<List_2->length)

if(List_l->data[i]<LisC2->data|j])

->data[i]==•1)

i++:

else

List_3->data[k++]=List」-〉data[i++];el

LisC3->data[k++]=List_2->data[j—I-];

"当仅有表1存在时

\vhile(i<List_l->lengtli)

if*List_l->data[i]=-l)

1++;

else

Lisc3->data[k+]=Listl->data[i++];

"当仅有表2存在时

\vhile(j<List_2->lengtli)

List_3->data[k一F]=List_2->data[j++];

〃表3的长度为k

List_3->length=k;

pnntfC'合并后

pnntR”顺序表为：”);

Display(逗Lis七3);

getchQ；

〃拆分顺序表

voidSplitIJst(SeqListSeqList*List_25eqList*List_3)

intij=0,k=0;

prmtfT初始化顺序表•..W)；

ImtList(List1),

pmitf({[^，);拆分前pnntfC顺序表为：”)Display(*List」)；

pnntf(*\n");foi(i=0;i<List_l->length5i++)

if(Liscl->data[i]%2-=0)

List_2->data[j++]=List」->data[i];

else

List_3->data[k++]=LisCl->data[i];

List2->length);

List_3->length=k;

pnntfC拆分后

pirntfC偶数顺序表为：”)：

Display(*List_2);

pirntf(-奇数顺序表为：”)；

Display(*List_3)