数据结构实验报告全集
实验一
线性表基本操作与简单程序
1。
实验目得 (1)掌握使用Visual C++ 6、0 上机调试程序得基本方法;)2( 本基得表性线握掌ﻫ操作:初始化、插入、删除、取数据元素等运算在顺序存储结构与链表存储结构上得程序设计方法。
2. 实验要求 (1)
认真阅读与掌握与本实验相关得教材内容。
(2) 认真阅读与掌握本章相关内容得程序. (3)
上机运行程序。
(4)
保存与打印出程序得运行结果,并结合程序进行分析. (5)
按照您对线性表得操作需要,重新改写主程序并运行,打印出文件清单与运行结果 实验代码:
1) ) 头文件模块
#inc l ude i ostr eam 、h h 〉 // 头文件
#inc lud d e< mallo c、h h 〉 // 库头文件- - - -- — 动态分配内存空间
typ ed d ef f
i nt e lemtype ; // 定义数据域得类型
typede f
str uc c t
linknode// 定义结点类型
{ {
e e l em t ype dat a; // 定义数据域
s tr u ct l ink no o de e
*next ; // 定义结点指针
}n od d e type ;
2) 创建单链表
n od e ty p e * cr e ate ()/ / /建立单链表, , 由用户输入各结点 a data 域之值, ,
/ / /以 0 0 表示输入结束
{
elem t ype d ; // 定义数据元素 d d
nodetype * h=NU LL L , *s ,*t t ; // 定义结点指针
i i nt
i=1;
cou t <<" 建立一个单链表”〈 <end l;
whi le e (1 1 )
{
cou t
<<”
输入第”〈〈
i < 〈" " 结点 a data 域值:”;
c c i n 〉>
d;
if(d d ==0 )
bre ak k ;/ / /以 0 0 表示输入结束
if (i i ==1)// 建立第一个结点
{
h h =( nodetype * )m al l l oc(sizeof( n odetype)) ; // 表示指针h
h h- - >d a ta=d ;h h —> > ne xt =N UL L;t =h; //h就是头指针
} }
els e/ / /建立其余结点
{ {
s =( n odet y pe*) ma l loc(size of f ( node t ype )); ;
s- - >d ata = d;s — 〉 next =NU U LL ;t — >nex x t =s ;
t=s ;t //t 始终指向生成得 单链表得最后一个节点
}
i++ ;
}
retu r n h ;
} }
3)输出单链表中得元素
v oi d
disp ( node ty y pe*h h )// / 输出由h指向得单链表得所有daa ta 域之值
{
nodetype * p=h;
c ou t< < 〈”输出一个单链表 :"<<en dl<<”
";
i f(p== N ULL )co o ut t <〈”空表”;
w w h il e( p!=NU LL L )
{ {
cou t< < 〈p p- - 〉da ta< 〈 ”
” ;p p =p- - 〉 nex t;
} }
c c out t 〈<e e n dl ;
}
4 4 )计算单链表得长度
int len(no de ty p e *h)/ / /返回单链表得长度
{
int i =0 0 ;
nod d e type * p=h;
w w h ile(p!=NULL)
{ {
p p =p p — 〉 nex t ;i++ ;
}
re t urn
i i ;
} }
5) 寻找第 i i 个节点
node type
*find(n o detype *h , int i)// 返回第 i i 个节点得指针
{ {
nod e ty pe e
* p=h ;
i nt j=1 1 ;
if(i 〉l en ( h) | |i<=0)
r r e tu r n NUL L;/ / /i i 上溢或下溢 c c
els e
{ {
while ( p!=N ULL && & j〈 1)// 查找第 i i 个节点,并由 p p 指向该节点
{ {
j++; p =p- - 〉 next ;
} }
retu rn
p;
}
} }
6 6 )单链表得插入操作
n n ode e ty pe * i ns ( node typ p e
* * h ,i n t i , el e mtype
x x )// / 在单链表he e ad d 中第 第 i i 个节点
// / (i i 〉 =0) 之后插入一个 dat a域为 x x 得节点
{ {
nodetype * p,* s;
s =(nodet y pe *) ) m alloc(si z eo f( no d ety pe e )); // 创建节点 s s
s s — 〉d ata =x;s- >n e xt =N N U LL;
i i f( i==0)//i=0 :s s 作为该单链表得第一个节点
{ {
s — >nex t =h ;h =s;
}
else
{ { p= fi nd(h h ,i i )
;// 查找第 i i 个节点,并由 p p 指向该节点
if (p p !
=NUL L) )
{
s- - > next=p — 〉 ne xt t ;
p p — 〉 next=s;
} }
r r e tu r n h;
}
} }
7 7 )单链表得删除操作
node t ype * del ( nod et yp e
*h, int
i)// 删除第 i i 个节点
{ {
n odetype * p=h, *s s ;
int
j= = 1; ;
if (i= = =1 1 )//删除第 1 1 个节点
{ {
h= = h — >next ; free ( p) ;
} }
else
{ {
p p = fi n d(h ,i i -1 1 )
;// 查找第i-1 1 个节点, , 并由 p p 指向该节点
if(p != = NU U LL L & &p - >n e xt !
=NULL)
{
s =p -〉 next; //s s 指向要删除得节点
p p - >ne x t=s - >n e xt ;
free ( s) ;
} }
el l se
co ut t < <" 输入i得值不正确 ”< < < endl ;
}
retu r n h; ;
}
8 8 )释放节点空间
void di spose (n n o det y pe *h)// 释放单链表得所有节点占用得空间
{
no de typ e
*p p a =h ,*p b;
if (pa a !
=N UL L L) )
{ {
pb=p a — 〉n ex t; ;
if(pb= = NUL L)// / 只有一个节点得情况
fr e e( p a);
el s e
{ {
whil e
(p p b!=N N U LL )//有 两个及以上节点得情况
{ {
f f r ee ( pa );p p a =pb ; pb = pb — 〉 next ;
} }
free ( pa);
}
}
}
9 9 )主程序模块:
#i nc l ud e"s s li i nk、h h ”/ / /包含头文件 sli nk k
v v o id main( )
{
no de e typ p e
* hea d; // 定义节点指针变量
he ad d =c c reat t e () ; // 创建一个单链表
disp ( hea d); ; // / 输出单链表
c c out 〈 <" 单链表长度:”< < 〈l en(h ead d )〈〈end d l;
ins( h ea d, ,
2,0 ); // 在第二个节点之后插入以 0 0 为元素得节点
d isp ( he a d) ;// / 输出新链表
del (h h e ad ,2) ) ;/ / /删除第二个节点
d isp(he ad d ); // 输出新链表
}
5 5 。实验结果
建立一个单链表:
输入第 1 1 结点 d d aa ta 域值:1 1
输入第2结点 dat a域值:2 2
输入第 3 3 结点da ata 域值 :3
输入第 4 4 结点 da ta a 域值:4
输入第 5 5 结点da a ta域值 :5
输入第 6 6 结点 d d at t a域值:6
输入第 7 7 结点 d d at t a域值:7
输入第 8 8 结点 d d aa ta 域值:8
输入第9结点 d d at t a域值: : 9
输入第 0 10 结点 a data 域值0: :
输出一个单链表:
1
2
3 4 5 6
7 8
9
单链表长度:9 9
输出一个单链表:
1 0
2
3 4
5
6
7 8
9 9
输出一个单链表:
1 2 3 4 5 6 7 8
实验二
顺序栈得实现
1、实验目得 掌握顺序栈得基本操作:初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。
2、实验要求 (1)
认真阅读与掌握与本实验相关得教材内容。
(2) 分析问题得要求,编写与调试完成程序. (3)
保存与打印出程序得运行结果,并分析程序得运行结果。
3、实验内容
是就号括方、号括圆含包中式达表术算断判个一现实作操本基得栈用利ﻫ否正确配对得程序。具体完成如下:
(1)
定义栈得顺序存取结构。
(2) 分别定义顺序栈得基本操作(初始化栈、判栈空否、入栈、出栈等)。
(3)
定义一个函数用来判断算术表达式中包含圆括号、方括号就是否正确配对。其中,括号配对共有四种情况:左右括号配对次序不正确;右括号多于左括号;左括号多于右括号;左右括号匹配正确.
(4)
设计一个测试主函数进行测试。
(5) 对程序得运行结果进行分析. 实验代码:
#include <stdio、h >#ﻫ001 eziSxaM enifedﻫ
typedef struct {
int data[MaxSize];
int top; }SqStack; void InitStack(SqStack *st)
//初始化栈 {
;1—=pot>—tsﻫ}ﻫint StackEmpty(SqStack *st) //判断栈为空 {
;)1—==pot〉-ts( nruterﻫ}ﻫvoid Push(SqStack *st,int x)
//元素进栈
ﻫ{pot>-ts(fiﻫ==MaxSize-1)
printf("栈上溢出!\n");
esleﻫ{
ﻫ
st-〉top++;
;x=]pot〉-ts[atad>-tsﻫ
} }ﻫvoid Pop(SqStack *st)
//退栈
ﻫ{)1-==pot>-ts(fiﻫ
;)”n\出溢下栈"(ftnirpﻫ
esleﻫ
st—〉top-—; } int Gettop(SqStack *st)
//获得栈顶元素 {
if(st—〉top==—1) {
ﻫ
printf("栈空\n”);
;0 nruterﻫ
}
esleﻫ
return st—〉data[st->top]; } void Display(SqStack *st)
//打印栈里元素 {ﻫ
int i;
printf("栈中元素:");
for(i=st-〉top;i>=0;--i)
d%”(ftnirpﻫ",st->data[i]);
ﻫ;)"n\”(ftnirpﻫ}测// )(niam tniﻫ试
ﻫ{ ;L kcatSqSﻫ
;L&=ts* kcatSqSﻫ
nIﻫitStack(st);
;))ts(ytpmEkcatS,"n\d%:空栈"(ftnirpﻫ
)i++;01<i;1=i tni(rofﻫ
;)i,ts(hsuPﻫ
;)ts(yalpsiDﻫ
printf("退一次栈\n");
Pop(st);
printf("栈顶元素:%d\n",Gettop(st));
poPﻫ(st);
;)ts(yalpsiDﻫ
ﻫ};0 nruterﻫ
实验结果: :
实验三
串得基本操作与简程序 1。
实验目得 掌握串基本操作:初始化、联接、替换、子串等运算在堆分配存储储结构上得程序设计方法。
2. 实验要求 (1) 认真阅读与掌握与本实验相关得教材内容. (2)
认真阅读与掌握本章相关内容得算法并设计程序序。
(3)
上机运行程序。
(4) 保存与打印出程序得运行结果,并结合程序进行分析. 实验代码:
#inc l ude < stdio 、 h>
#d d e fi ne e
MaxSize 50
type d ef s tr u ct
{ {
ch h a r data [ Ma x Siz e];
// 存放字符串
int len gth h ;
// 字符串 长度
} SqString ;
// / 将一个字符串常量赋给串 s s
v oid
StrAssign(SqStr in n g
& s,c ha a r
c c st r[])
{
i i nt t
i i ;
for(i =0 ;cstr[i] != = '\ \ 0";i++ )
// / 这个'\ \0 0 '代表字符串结束标志, , 编译系统自动加上得
s、 dat a [i]=cs t r[i];
s s 、 len g th=i;
}
// 字符串得复制
vo i d StrCopy (S qStr i ng & s,S S q St ri i n g t)
{ {
in t i;
f or(i=0;i 〈t、le ngt h;i ++ )
s s 、d at a [i ] =t 、 data[i];
s、 le n gt h =t 、l ength ;
p p r intf( "字符串复制成功了\ \n n ”) ) ;
}
// 判断字符串就是否相等
vo id
St rEq q ual (SqStrin g
s s ,S qSt ri i n g t)
{
in t
i, s ame= 1;
if f (s s 、l ength!=t 、l en g th )
sa m e=0 ;
el se
{ {
for ( i= 0;i i 〈s s 、 length;i++ )
if( s、 da t a[i ] !=t 、da a ta a [i])
{
sa me e =0; ;
b reak ;
}
}
i f(same==0 )
p p rin n t f(" 这两个字符串不相等\ \ n" ); ;
else
p p r int f(" " 这两个字符串相等\ \n n ”) ) ;
}
/ / /字符串得长度
v oid
S trLe n gth(SqS tr r in n g
s)
{
pr in n tf f (”此字符串长度为:%d d\ \ n" ,s s 、l eng th) ); ;
}
// 合并字符串
Sq S tring Co n cat (S qString
s,Sq S tring t)
{ {
S qS t ri ng
s s tr;
in t
i i ;
s tr 、len gth=s 、 len g th+t 、l en gt t h;
for( i =0 ;i<s s 、 le n gt h; i++ )
str 、d d at t a[ i] =s s 、 data [i i ]; ;
for(i=0 ;i〈t t 、l eng t h;i++)
str 、da a ta a [s、l l e ngt h+ i] =t、 data [ i];
r eturn str;
}
/ / /求子字符串
void
SubStr (SqS S t ri n g s , in t
i i ,in n t
j)
{
SqStr i ng
st t r; ;
i nt
k;
s tr 、l l e ngth= 0;
i i fi (i 〈 =0| |i i〉 〉s s、 、 len gt t h| | | j<0 | |i+j- - 1> > s、le e ngth)
pri n tf(" 子字符串复制失败\n n " );
f or ( k= i- 1;k 〈 i+j- -1 1 ;k k ++ + )
st r、 dat a[k k —i i + 1]=s 、d d a ta[k] ;
str r 、l ength=j;
printf (" " 子字符串复制成功
长度为:
%d\ \ n", , j) ) ;
print f( ( ”下面输出此子字符串:\n n " );
f f or r (i =0 ;i <j ; i++)
pr r i ntf ( ” %c ”, st t r、 data[i ]) ) ;
printf(”\ \ n ” );
} }
// 插入字符串
S qStri n g I ns e rStr(S q Str ing
s1 , int i ,SqS tring s 2) )
{ {
int
j j ;
Sq S tr in n g
str;
s tr 、 length=0 ;
if (i i 〈= = 0|| i>s1 、 length+1)
{ {
pr in n tf f (”字符串插入失败\ n" ); ;
retu rn
str ;
} }
for ( j= 0; ; j <i- -1 1 ;j ++ )
str r 、d ata [j]= s1 、da ta[j];
for ( j=0; j〈s2 2 、 lengt h; j++)
s s tr r 、 dat a [i- -1 1 +j j ] =s2 、d d a ta[j ];
fo o r(j =i -1 1 ;j j <s s 1、l eng t h;j++ )
st r、 da ta [s2 、le ngt h +j] = s1 、 data [ j];
s tr 、 leng th h =s1 1 、 le ng th+ s2 2 、l l eng th ;
printf (" " 插入字符串成功
长度为:%d d\ \n n ”,s s tr、length );
retu r n st r; ;
}
/ / /删除字符串
Sq St ring DeleS tr( SqStri n g s , int i,i nt
)
j)
{
i nt k ;
Sq q St t ri i ng
s s tr r ;
s s tr r 、l eng th h = 0;
if ( i<=0 | |i>s 、l engt h|| i+ j >s 、 le ngt h+1)
{ {
pri i n tf ("字符串删除失败\n n ”);
return
str;
}
f f o r( k= = 0;k k 〈i i- - 1;k k + +)
s tr 、 da t a[k] =s s 、d ata [k ];
for ( k=i+j — 1;k〈s、 leng th h ; k++ )
s s tr、 data [k k -j ]=s 、 data[k ];
str 、 length=s 、l l e ngt h —j j ;
pri nt t f( ( "删除子字符串成功
剩余长度为: : %d d \ n", str 、 le n gth) ;
re tu rn str ;
}
// 替换字符串
voi d
R R ep Str(SqStr in g s,int
i i ,i nt t
j, S qString t)
{
i i nt t
k;
S S q String
str ;
s s tr、 length =0 0 ;
if(i<= 0||i i 〉s s 、 le ng th||i+j — 1>s 、l eng th h )
pri n tf (" " 字符串替换失败了\ \n n "); ;
f or(k=0;k <i i — 1; k++)
st r、 dat a [k ]= = s、dat t a[k k ];
for( k =0;k<t 、l l eng g th h ;k++ + )
str 、d at a[ i+k- - 1] =t 、d d a ta [k k ];
for ( k=i +j j -1; ; k <s 、 le n gt h; k++)
str 、d d ata [t t 、l ength+k- -j j ] =s 、d ata[k ];
s s tr、l l eng g t h= s、 le n gth- - j+t 、l l en n g th ;
p p ri i nt t f( ( ”替换字符串成功
新字符串长度为:%d d\ \n n ”,str 、 length) ;
}
// 字符串得输出
v oi d
Di sp St r( SqString
s s )
{
int i ;
if( s、le ng t h> 0) )
{
pri nt f("下面输出这个字符串\ \n n ") ) ;
fo r(i i = 0;i 〈s s 、le e ng g t h;i ++ + )
p p r intf(" %c",s、 da ta a [i]); ;
p ri nt t f( ( "\ \ n”) ;
} }
el se
print f("目前空字符串
无法输出\ n" );
} }
void main ()
{ {
S S qS S t ring s;
char a [] ] ={ { " we n
x x ian n
lia ng "} } ;
// 字符串常量a
St t rA ssig n(s s ,a);
D ispS t r(s );
StrL engt t h( s);
SqS tr r i ng
s s 1 ,s2,t;
1 //s1 就是待复制得字符串变量
pr r in n t f(" 请输入一个字符串t:\ \n n ”) ) ;
scan f (" %s s " ,t 、d ata );
StrAssi gn (t ,t t 、da a t a);
S S t rCopy(s1 ,t t );
// 复制字符串
St t rLe e ngth h ( s1) ;
Dis p Str(s 1) ) ;
p p r in t f("串 下面判断字符串 1 s1 串 与字符串 s s 就是否相等\n");
StrE q ua l(s s , s1) ;
printf(" 下面将字符串 s s 1与字符串 s s 合并一起\n" " );
Sq S trin g
str ;
s s tr r = Concat(s , s1) ;
// / 合并字符串
DispStr(st r);
StrLength ( str) ;
Su u bS tr ( st r, , 22 2 ,7 7 );
/ / /求子字符串
s s tr r = DeleS tr (st r ,1 5 ,4) ;
// 删除字符串
Di i sp p S tr ( st r); ;
St r Length ( str) ;
p p ri i n tf(" 请插入一个字符串s2 2\ \n n ”); ;
s s c anf ( ” %s ",s 2、d d at t a) ) ;
St r As s ig n (s2, s2、 dat a );
str= Ins e rS t r(s tr, 15 , s2 )
;
// / 插入字符串
D D i spS t r(st r);
Str L ength ( st r); ;
printf( "顺序字符串得基本运算到此结束了\ \ n”) ) ;
}
实验结果:
实验四
编程建立二叉树, 对树进行插入删除及遍历得程序
1、实验目得 (1)
进一步掌握指针变量得用途与程序设计方法。
(2)
掌握二叉树得结构特征,以及链式存储结构得特点及程序设计方法。
(3)
掌握构造二叉树得基本方法。
(4)
掌握二叉树遍历算法得设计方法. 3. 实验要求 (1)认真阅读与掌握与本实验相关得教材内容。
(2)掌握一个实际二叉树得创建方法. (3)掌握二叉链存储结构下二叉树操作得设计方法与遍历操作设计方法。
4。
实验内容 (1)定义二叉链存储结构. (2)设计二叉树得基本操作(初始化一棵带头结点得二叉树、左结点插入、右结点插入、中序遍历二叉树等)。
(3)按照建立一棵实际二叉树得操作需要,编写建立二叉树、遍历二叉树得函数. (4)编写测试主函数并上机运行。打印出运行结果,并结合程序运行结果进行分析。
实验代码: #i nclu d e<i os s t re am m 、h h >
t ypede f
s s t ruc t
bi t nod e{
ch h a r da a ta; ;
s tr uc t bitnod e
* * l chi l d, * rchi ld d ;
}bino de e ,* * b itre e;
void createbit r ee(bi tr e e *T){
ch ar c h;
c c i n>>ch ;
if(ch = ="0 ')
(*T )= NULL ;
else {
*(=)Tﻩ (*T)= ne w
b it n ode;
( *T)- -> > data= = ch;
crea t ebitree ( &( * T) — 〉l l c hild) ;
create bi tre e( ( &(*T T )
— 〉r r c hil d); ;
} }ﻩ}
void in n o rd e rout (b itr e e T) {
if (T ){
droniﻩ inord e ro u t(T- -> > lc c hild d ); ;
oc cﻩﻩ o ut <<T T- - >data < <end d l; ;
tuoredroniﻩﻩ inorderout (T- - 〉 rchi ld d );
} }ﻩ} }
void p os s t ord er r ( bitree T) {
if(T) {
po s torder(T- - >l c hi l d) ;
postor de e r (T — >r r c hil d) ) ;
cout<<T -〉 data 〈 <endl ;
}
}
in n t
countleaf ( bit r ee
bt ){
i i f( !bt)
erﻩ re t urn 0;
if f (b b t- >lc hi i ld ==N U LL&& bt t- - >rchild==NUL)
L)
ret urn n
1 1 ;
r r e turn ( c oun t lea f(bt- - 〉 lc hi i ld d )+ + co untl eaf (b b t- - >rc c hi ld )); ;
} }
voi d
m ai n( ( ){ {
b it ree
b t;
creat e bit r ee (&bt t );
in o rd er out( b t) ;
cou t <<" "< < 〈 endl ;
postorder ( bt) ;
countlea f( ( bt t );
}
实验五 建立有序表并进行折半查找 1、 实验目得 掌握递归算法求解问题得基本思想与程序实现方法. 2.实验要求)1(
.想思法算得验实本握掌与读阅真认ﻫ(2)编写与调试完成程序. (3)保存与打印程序得运行结果,并对运行结果进行分析。
3、实验内容 (1) 分析掌握折半查找算法思想,在此基础上,设计出递归算法与循环结构两种实现方法得折半查找函数. (2)
编写程序实现:在保存于数组得 1000个有序数据元素中查找数据元素x就是否存在。数据元素x要包含两种情况:一种就是数据元素 x 包含在数组中;另一种就是数据元素x 不包含在数组中 (3)
数组中数据元素得有序化既可以初始赋值时实现,也可以设计一个排序函数实现。
(4) 根据两种方法得实际运行时间,进行两种方法时间效率得分析对比。
实验代码: #include<stdio、h> #include<stdlib、h> #define MAX_LENGTH
100 typedef int KeyType;
typedef struct {
int key; }ElemType; typedef struct {
出空元单号 0 //
;]HTGNEL_XAM[mele epyTmelEﻩ
int length; }SSTable; int Search_Bin(SSTable ST,KeyType key) {
int low,high,mid;
low = 1;high = ST、length;
while(low <=high)
{
mid = (low+high)/2;
)yek、]dim[mele、TS== yek(fiﻩﻩ
ﻩ
return mid;
esleﻩ ﻩ
)yek、]dim[mele、TS〈yek(fiﻩ ﻩ
;1—dim = hgihﻩ ﻩﻩ
else
ﻩ
low=mid+1;
}
ﻩ
return 0; } void main() {
int i,result;
;TS elbaTSSﻩ ;yek epyTyeKﻩ printf("please input length:");
scanf("%d",&ST、length);
)++i;htgnel、TS=<i;1=i(rofﻩ {ﻩ
;)":mele、TS tupni esaelp"(ftnirpﻩ
scanf("%d",&ST、elem[i]);
}
printf("please input keyword:");
scanf("%d",&key);
result=Search_Bin(ST,key);
)0==tluser(fiﻩ
printf(”Don"t find\n");
esleﻩ
printf(”Find the key,the position is %d\n",result); } 实验结果:
实验六 建立一组记录并进行插入排序 1、 实验目得 (1)
掌握插入排序算法得思想. (2)
掌握顺序队列下插入排序算法得程序设计方法。
2、 实验要求 )1(
。想思得法算序排入插中材教握掌与读阅真认ﻫ(3) 编写基于顺序队列得插入排序排序算法并上机实现。
3、 实验内容 (1) 编写基于顺序队列得插入排序函数。
(2) 设计一个测试主函数,实现对基于顺序队列结构得插入排序算法得测试. (3)
分析程序得运行结果。
实验代码: #include〈stdio、h> #include〈stdlib、h> #define MAXSIZE 100 typedef struct
{
int key; }sortkey; typedef struct {
sortkey elem[MAXSIZE];
int length; }sortelem; void InsertSort(sortelem *p) {
int i,j;
for(i=2;i<=p-〉length;i++)
{
if(p->elem[i]、key<p->elem[i-1]、key)/*小于时,需将 elem[i]插入有序表*/
{
p—>elem[0]、key=p—>elem[i]、key; /*为统一算法设置监测*/
for(j=i—1;p->elem[0]、key〈p->elem[j]、key;j—-)
p->elem[j+1]、key=p—〉elem[j]、key;/*记录后移*/
p-〉elem[j+1]、key=p->elem[0]、key; /*插入到正确位置*/
}
} } void main() {
sortelem *p; int i; int b[6]={45,23,54,6,4,46}; p=(sortelem *)malloc(sizeof(sortelem)); p—〉length=0; for(i=1;i<7;i++)
{
p—>elem[i]、key=b[i—1];
p->length++; } InsertSort(p); for(i=1;i<7;i++) {
printf(”%d
",p—>elem[i]、key); } system("pause"); } 实验结果:
实验七
建立一组记录并进行快速排序 1、 实验目得 (1)
掌握快速排序算法得思想. (2) 掌握顺序队列下快速排序算法得程序设计方法。
2、 实验要求 )1(
。想思得法算序排速快中材教握掌与读阅真认ﻫ(3)
编写基于顺序队列得快速排序排序算法并上机实现。
3、 实验内容 (1) 编写基于顺序队列得快速排序函数。
(2) 设计一个测试主函数,实现对基于顺序队列结构得快速排序算法得测试. (3)
分析程序得运行结果。
实验代码: #include〈iostream、h〉 void quick_sort(int a[],int low, int high)
{
int i,j,pivot;
if (low < high)
{
pivot = a[low];
i = low;
j = high;
while (i < j)
{
//从顶端开始比较值,如果小于标准值,停止
while (i < j && a[j] >= pivot)
{
j--;
}
//将比 pivot 小得元素移到低端,下标加加
if (i < j)
a[i++] = a[j];
//从底端开始比较值,如果大于标准值,停止
while (i < j && a[i] <= pivot)
{
i++;
}
//将比 pivot 大得元素移到顶端,下标减减
if (i 〈 j)
a[j--] = a[i];
}
//pivot 移动到最终位置
a[i] = pivot;
//对左区间进行递归排序
quick_sort(a, low, i—1);
//对右区间进行递归排序
quick_sort(a, i+1, high);
}
}
void print_array(int a[], int n)
{
for(int i = 0; i 〈 n; i++)
{
cout <〈 a[i] 〈< ",";
}
}
int main()
{
int data[9] = {54,38,96,23,15,72,60,45,83};
quick_sort(data, 0, 8);
print_array(data,9);
return 0;
}
实验结果:
版权所有:格斯文档网 2010-2024 未经授权禁止复制或建立镜像[格斯文档网]所有资源完全免费共享
Powered by 格斯文档网 © All Rights Reserved.。浙ICP备19042928号