内蒙古科技大学 经管学院 数据结构上机试题Word格式文档下载.docx
《内蒙古科技大学 经管学院 数据结构上机试题Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《内蒙古科技大学 经管学院 数据结构上机试题Word格式文档下载.docx（19页珍藏版）》请在冰点文库上搜索。
for（i=0;
i<
length;
i++）
{
scanf（"
%d"
&
k）;
elem[i]=k;
}
returnOK;
}
intListInsert（SqList*L,inti,inte）
{int*newbase,*q,*p;
if（i<
1||i>
length+1）returnERROR;
if（L->
length>
=L->
listsize）{
newbase=（int*）realloc（L->
elem,（L->
listsize+LISTINCREMENT）*sizeof（int））;
newbase）exit（OVERFLOW）;
elem=newbase;
listsize+=LISTINCREMENT;
q=&
（L->
elem[i-1]）;
for（p=&
elem[L->
length-1]）;
p>
=q;
--p）*（p+1）=*p;
*q=e;
++L->
intListDelete（SqList*L,inti,inte）{
int*p,*q;
if（i<
1||i>
length）returnERROR;
p=&
e=*p;
q=L->
elem+L->
length-1;
for（++p;
p<
++p）*（p-1）=*p;
--L->
}
intdisplay（SqList*L）
inti;
printf（"
L->
elem[i]）;
"
）;
intmain（）
SqListL;
chare;
inti,num;
请初始化10个元素：
\n"
InitList（&
L）;
printf（"
初始化后"
display（&
\n请输入你要删除的元素的位置\n"
scanf（"
i）;
ListDelete（&
L,i,e）;
删除后：
\n请输入插入位置和元素（格式“位置”，“元素”）"
%d,%d"
i,&
num）;
ListInsert（&
L,i,num）;
插入后：
returnOK;
二、单链表的操作
（1）创建一个带头结点的单链表；
（2）插入元素操作：
将新元素x插入到单链表中第i个元素之后；
（3）删除元素操作：
删除单链表中值为x的元素；
#defineNull0
typedefintElement;
typedefstructLNode
Elementdate;
structLNode*next;
}LNode,*LinkeList;
LNode*Create（intn）
inti;
LNode*head,*now;
head=（LNode*）malloc（sizeof（LNode））;
head->
next=Null;
for（i=0;
n;
now=（LNode*）malloc（sizeof（LNode））;
now->
date）;
next=head->
next;
next=now;
returnhead;
intInsertNode（LNode*l,inti,Elemente）
LNode*now=l;
intj=0;
while（now&
&
j<
i-1）
{now=now->
j++;
if（!
now||j>
插入位置I不恰当！
"
return0;
LNode*s;
s=（LNode*）malloc（sizeof（LNode））;
s->
date=e;
next=now->
next=s;
return1;
intDleteNode（LinkeList&
l,inti）
Elemente;
LNode*now,*d;
now=l;
while（now->
next&
d=now->
next=d->
e=d->
date;
free（d）;
returne;
voidDisplayList（LinkeList&
l）
LNode*now;
now=l->
while（now!
=Null）
%d"
now->
now=now->
voidmain（）
LNode*l;
intnum=0,ch=0;
输入链表长度:
请输入个元素：
l=Create（num）;
初始化为：
DisplayList（l）;
num,&
ch）;
if（InsertNode（l,num,ch））printf（"
\n插入后为:
\n请输入删除位置：
\n第%d个位置元素为“%d”\n删除后为：
num,DleteNode（l,num））;
三、在顺序栈上实现将非负十进制数转换成二进制数。
#defineMAX30
typedefstruct
intsize;
int*base,*top;
}SqStack;
intInitStack（SqStack&
s）
s.base=（int*）malloc（MAX*sizeof（int））;
s.base）return0;
s.top=s.base;
s.size=MAX;
intPush（SqStack&
s,inte）
if（s.top-s.base>
s.size）
s.base=（int*）realloc（s.base,（s.size+10）*sizeof（int））;
s.base）return0;
s.top=s.base+s.size;
s.size+=10;
*s.top++=e;
intPop（SqStack&
s,int&
e）
if（s.base==s.top）return0;
e=*--s.top;
intnum,k;
SqStackl;
InitStack（l）;
while
（1）
请输入欲转换的十进制数！
while（（num/2）!
=0||（num）!
=1）
Push（l,num%2）;
num=num/2;
Push（l,num%2）;
转化结果为：
while（Pop（l,k））printf（"
k）;
四、在顺序表中采用顺序查找算法和折半查找算法寻找关键字X在顺序表中的位置。
#defineTYPEint
TYPE*elem;
elem=（TYPE*）malloc（LIST_INIT_SIZE*sizeof（TYPE））;
elem[i]=i*i;
intSequanceSearch（SqList&
l,intn,TYPEc）
inti=1;
intposition;
while（i<
n）
if（l.elem[i-1]==c）
{position=i;
break;
elseposition=-1;
i++;
if（position<
=n）returnposition;
elsereturnERROR;
intBinSearch（SqList&
l,TYPEc）
intlow=0,mid,high=l.length;
while（low<
=high）
mid=（low+high）/2;
if（c==l.elem[mid]）returnmid;
else
if（c<
l.elem[mid]）high=mid-1;
elselow=mid+1;
returnERROR;
TYPEe;
inti
;
InitList（&
初始化顺序表为：
while
（1）
\n顺序查找查什么？
e）;
i=SequanceSearch（L,LIST_INIT_SIZE,e）;
if（i==ERROR）printf（"
顺序表没有该元素！
！
elseprintf（"
所查元素所在位置为：
%d\n"
i）;
\n折半查找查什么？
i=BinSearch（L,e）;
i+1）;
}returnOK;
五、将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列。
#include<
#defineMAX15
#defineSWAP（x,y）{intt;
t=x;
x=y;
y=t;
voidDisplay（inta[],intn）
{
for（inti=0;
i<
i++）
a[i]）;
}
voidInsertSort（inta[],intn）
inti,j,temp;
for（i=1;
temp=a[i];
for（j=i-1;
j>
=0&
temp<
a[j];
j--）
a[j+1]=a[j];
a[j+1]=temp;
Display（a,MAX）;
voidQuickSort（inta[],intlow,inthigh）
intz=0,y=0,k=0;
if（low<
=high）
z=low;
y=high;
k=a[z];
do{
while（（z<
y）&
（a[y]>
=k））y--;
if（z<
y）a[z]=a[y];
（a[z]）<
k）z++;
y）
{
a[y]=a[z];
Display（a,MAX）;
}while（z<
y）;
a[z]=k;
QuickSort（a,low,z-1）;
QuickSort（a,z+1,high）;
voidmain（）
{
inta[MAX]={7,3,5,8,9,1,2,4,6};
charch;
数组初始为：
Display（a,MAX）;
\n请选择排序方法（“q”为快速排序，“i”为插入排序）：
do{scanf（"
%c"
while（!
（ch=='
i'
||ch=='
I'
q'
Q'
））;
if（ch=='
）
{printf（"
插入法排序过程为：
InsertSort（a,MAX）;
else{printf（"
快速排序过程为：
QuickSort（a,0,MAX）;
升级会员 