數(shù)據(jù)結(jié)構(gòu)上機(jī)試題

數(shù)據(jù)結(jié)構(gòu)上機(jī)試題

一、順序表的操作

(1)插入元素操作：將新元素X插入到順序表a中第

i個(gè)位置。

(2)刪除元素操作：刪除順序表a中第i個(gè)元素。

#include<iostream.h>

#include<stdlib.h>

#defineMAX100；

typedefstruct{

intdata[100];

intlength;

}sqlist;

voidinit(sqlist&a)//線性表初始化

(

a.length=0;

}

voidinsert(sqlist&a,inti,intx)//插入兀素操作

(

intj;

if(i<0||i>a.length+l||a.length==100)

else{

for(j=a.length+l;j>i;j")

a.data[j]=a.data[j-l];

a.data[j]=x;

a.length++;

}

)

voiddeleted(sqlist&a,inti)//刪除元素操作

(

intj;

if(i<0&&i>a.length)

else

for(j=i;j<a.length;j++)

a.data[j]=a.data[j+l];

a.length";

}

voidmainQ

sqlista;〃線性表為a

inti,e,x,n,j,s;//i插入位置，e動(dòng)態(tài)建線性表要用，X插

精品

入元素，n表長(zhǎng)

精品

init(a)，/構(gòu)造一個(gè)空表

coutvv”輸入表長(zhǎng)n:

cin>>n;

coutvv”輸入表長(zhǎng)為"?n?"個(gè)數(shù)：

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

(

cin>>e;

insert(a,j,e);

}

coutvv"插入前：

for(j=0;j<a.length;j++)

cout<<a.data[j]<<"

coutvv”輸入要插入位置i:

cin>>i;

coutvv”輸入要插入的元素x:

cin>>x;

coutvv”打算在第"<vivv”個(gè)位置插入元素”VVx;

insert(a,i-l,x);//由于從0開(kāi)始，要構(gòu)造顯示從一開(kāi)始,

所以減1

coutvv”插入后結(jié)果：”；

for(j=O;j<a.length;j++)

精品

cout<<a.data[j]<<"

coutvv”輸入要?jiǎng)h除的位置s:"；

cin>>s;

deleted(a,s-l);//由于從0開(kāi)始，要構(gòu)造顯示從一開(kāi)始,

所以減1

cout<<"刪除后結(jié)果：”；

for(j=0;j<a.length;j++)

cout<<a.data[j]<<"

二、單鏈表的操作

(1)創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的單鏈表；

(2)插入元素操作：將新元素x插入到單鏈表中第i

個(gè)元素之后；

(3)刪除元素操作：刪除單鏈表中值為x的元素；

#include<iostream.h>

#include<stdlib.h>

精品

typedefstructLNode

intdata;

structLNode*next;

}LNode;

//創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的長(zhǎng)度長(zhǎng)度長(zhǎng)度為n的鏈表

L；

voidcreatelist(LNode*&L,intn)

(

inti;

LNode*p;

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

L->next二NULL;

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

(

p=(LNode*)malloc(sizeof(LNode));

COUtVV”請(qǐng)輸入鏈表第”<vivv"個(gè)元素”；

cin>>p->data;

p->next=L->next;

L->next=p;

}

精品

//插入元素操作：將新元素X插入到單鏈表L中第i

個(gè)元素之后

voidinsert(LNode*&L,inti,intx)

intj=0;

LNode*p,*q;

p=L;

while(p->next!=:NULL)

(

j++；

if(尸二i)

{

q=(LNode*)malloc(sizeof(LNode));〃找到位置

q-〉data二x;//放入數(shù)據(jù)

q->next=p->next;

p->next=q;

break;

}

p=p->next;

}

if(p->next==NULL)

精品

q=(LNode*)malloc(sizeof(LNode));〃找到位置

q->data=x;//放入數(shù)據(jù)

q->next=p->next;

p->next=q;

)

}

//刪除元素操作：刪除單鏈表中值為x的元素；

voiddeleted(LNode*&L,intx)

(

LNode*p,*q;

p=L;

while(p->next!=NULL)

{

if(p->next->data==x)

{

q=p->next;

p->next=p->next->next;

free(q);

)

p=p->next;

}

精品

voidprint(LNode*&L)

LNode*p;

p=L->next;

while(p!=NULL)

(

cout<<p->data<<"

p=p->next;

}

)

voidmain。

(

LNode*L,*p;//節(jié)點(diǎn)為L(zhǎng)

inti,x,y,s,n;//i插入位置，X插入元素，y為刪除元

素，n表長(zhǎng)

coutvv”輸入表長(zhǎng)n:

cin>>n;

createlist(L,n);

coutvv”輸出插入之前：”；

print(L);

精品

coutvv”請(qǐng)輸入插入的位置i:

cin>>i;

coutvv”請(qǐng)輸入插入的元素x:"；

cin>>x;

insert(L,i,x);

cout<<"輸出插入后：”；

print(L);

cout<v”請(qǐng)輸入刪除的元素y:"；

cin>>y;

deleted(L,y);//刪除元素操作：刪除單鏈表中值為y

的元素；

coutvv”輸出刪除后：”;

print(L);

}

IS1*C:\DOCUIEHTSATOSETTINGS\ADIIKISTRATOR\^ffi\111111\Debug\111111.exe*jjn]X

輸

人.n6

<外

表

布

元

青

人11

鏈

表

元

清22

入4

鏈-

表

元

丘

請(qǐng)

入33

鏈

翦

表

元

丘

清

入44

鏈

元

表

布

莆

入

鏈55

元

表

清

入

鏈66

^-

之

前

輸

插

入65

出:

人請(qǐng)輸入插入的位置：

三

乒21i2

入-

M插

的9

J￡KX

后

插7T-

f入699

.?

后321請(qǐng)輸入刪除的元素y：3

刪

除69954

?

?21Pressanykeytocontinue

三、在順序棧上實(shí)現(xiàn)將非負(fù)十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)

#include<iostream.h>

精品

#include<stdlib.h>

#defineMAX100

//在順序棧上實(shí)現(xiàn)將非負(fù)十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)

voidconversion(int&x)

(

intstack[MAX];

inttop=-l;

intt;

while(x)

stack[++top]=x%2;

x=x/2;

}

while(top!=-l)

(

t=stack|top—];

cout<<t;

}

)

voidmain。

intx?t;

精品

coutvv”請(qǐng)輸入你要轉(zhuǎn)換的非負(fù)十進(jìn)制數(shù)X："v<endl;

cin>>x;

coutvv”輸出轉(zhuǎn)換后的二進(jìn)制數(shù):"；

conversion(x);

cout<<endl;

四、在順序表中采用順序查找算法和折半查找算法尋

找關(guān)鍵字X在順序表中的位置。

#include<iostream.h>

#include<stdlib.h>

#defineMAX100

//在順序表中采用順序查找算法和折半查找算法尋找

關(guān)鍵字X在順序表中的位置

typedefstruct

(

intdata[MAX];

intlength;

精品

}sqlist;

voidinit(sqlist&a)//線性表初始化

a.length=0;

}

voidinsert(sqlist&a,inti,intx)//插入元素操作

(

intj;

if(i<01|i>a.length+l||a.length==100)

else{

for(j=a.length+1;j>i;j—)

a.data[j]=a.data[j-l];

a.data[j]=x;

a.length++;

}

}

intsearch(sqlist&sq,intx)//順序查找算法

I

inti;

for(i=0;i〈sq.length;i++)//順序表存儲(chǔ)從0開(kāi)始

if(sq.data[i]==x)

精品

returni;

inthsearch(sqlist&sq,intlow,inthigh,intx)//折半查找算

法

(

intmid;

while(low<=high)

(

mid=(low+high)/2;

if(sq.data[mid]==x)

returnmid;

elseif(sq.data[mid]>x)

high=mid-1;

elseif(sq.data[mid]<x)

low=mid+l;

}

}

voidmain。

{

sqlistsq;//線性表為sq

inti,e,x,y,n;〃i插入位置，x,y要查找元素，n表長(zhǎng)

init(sq);〃構(gòu)造一個(gè)空表

精品

coutvv”輸入表長(zhǎng)n:

cin>>n;

coutvv”輸入表長(zhǎng)為個(gè)數(shù)：”；

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

(

cin>>e;

insert(sq,i,e);

coutvv”查找前(便于判斷):"<<endl;

for(i=O;i<sq.length;i++)

cout<<sq.data[i]<<"

cout<<endl;

coutvv”采用順序查找算法：”v〈endl;

cout<<endl;

coutvv”輸入要查找元素關(guān)鍵字x

cin>>x;

cout<<endl;

cout?"關(guān)鍵字H?X?H在順序表中的位置為

”VVsearch(sq,x)+lVVendl;〃下表從0開(kāi)始,+1顯示時(shí),

轉(zhuǎn)化成從1開(kāi)始了

coutvv"采用折半查找算法："?endl;

cout<<endl;

精品

coutvv”輸入要查找元素關(guān)鍵字y

cin>>y;

cout<<endl;

cout?"關(guān)鍵字n?y?"在順序表中的位置為

"<<hsearch(sq,l,sq.length,y)+1<<endl;

OS*C:\DOCUlEinSANDSETTINGS\ADIIHISTRATOR\^ffi\qqq\Debug\qqq.exe-口X

n：

腌入表長(zhǎng)為個(gè)數(shù):

103635296418566482514

性找箭（便于判斷）：

3635296418566482514

采用順序查找算法：

輸入要查找元素關(guān)鍵字x64

關(guān)鍵字64在順底表中的位置為4

采用折半查找算法：

輸入要查找元素關(guān)鍵字964

關(guān)鍵字64在順序表中的位置為4

Pressanykeytocontinue

五、將無(wú)序數(shù)列使用直接插入排序算法和快速排序算

法將其排成遞增有序數(shù)列。

#include<iostream.h>

#include<stdlib.h>

#defineMAX100

//將無(wú)序數(shù)列使用直接插入排序算法和快速排序算法

將其排成遞增有序數(shù)列

typedefstruct

精品

intdata[MAX];

intlength;

}sqlist;

voidinit(sqlist&a)//線性表初始化

(

a.length=0;

voidinsert(sqlist&a,inti,intx)//插入元素，構(gòu)造無(wú)序數(shù)

列

intj;

if(i<0||i>a.length+l||a.length==100)

else{

for(j=a.length+l;j>i;j")

a.data[j]=a.data[j-l];

a.data[j]=x;

a.length++;

}

//將哨兵放在a.data[n]中，被排序的記錄放在

精品

a.data[O.nl]中，直接插入排序算法。

精品

voidinsertsort(sqlist&a)〃直接插入排序算法

inti,j;

intn=a.length;

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

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

(

a.data[n]=a.data[i];//a.data[n]是哨兵

j=i+l；

do{

a.data[j-l]=a.data[j];

j++；

}while(a.data[j]<a.data[n]);

a.data[j-1]=a.data[n];

}

}

intPartition(sqlist&a,inti,intj)

(

intpivot=a.data[i];

while(i<j)

精品

while(i<j&&a.data[j]>=pivot)

j-s

if(ivj)

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

while(i<j&&a.data[i]<=pivot)

i++；

if(i<j)

a.data[j—]=a.data[i];

}

a.data[i]=pivot;

returni;

}

voidQuickSort(sqlist&a,intlow,inthigh)//快速排序

(

intpivotpos;//劃分后的基準(zhǔn)記錄的位置

if(low<high)

{//僅當(dāng)區(qū)間長(zhǎng)度大于1時(shí)才須排序

pivotpos=Partition(a,low,high);

QuickSort(a,low,pivotpos-l);

QuickSort(a,pivotpos+1,high);

}

精品

voidmainQ

sqlistsql,sq2;//線性表為sql,sq2

inti,e,x,nl,n2;//n表長(zhǎng)

init(sql);//構(gòu)造一個(gè)空表

coutvv”輸入表長(zhǎng)nl:

cin>>nl;

coutvv”輸入表長(zhǎng)為"?nl?"個(gè)數(shù)：”；

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

(

cin>>e;

insert(sql,i,e);//插入元素,構(gòu)造無(wú)序數(shù)列

}

coutvv”無(wú)序數(shù)列為:“vvendl;

for(i=O;i<sql.length;i++)

cout<<sql.data[i]<<"

cout<<endl;

insertsort(sql);

coutvv”直接插入排序后數(shù)列為:“vvendl;

for(i=O;i<sql.length;i++)

cout<<sql.data[i]<<"

精品

cout<<endl;

cout<<endl;

cout<<endl;

init(sq2);//構(gòu)造一個(gè)空表

cout<<"輸入表長(zhǎng)n2:

cin>>n2;

coutvv”輸入表長(zhǎng)為"?n2?"個(gè)數(shù)：”；

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

{

cin>>e;

insert(sq2,i,