数据结构与算法
课程简介：本课程总学时需要64学时,其中实验课10学时,共有5个实验,每个实验为2学时,从其中的7个实验选其中的5个。 本课程的先行课为《C++程序设计》
实验一 线性表及其应用
一、实验目的
1、掌握用上机调试线性表的基本方法；
2、掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。
硬件：PC 微型计算机、256M以上内存，40G以上硬盘。 软件：Windows XP，VC或VS.Net
二、实验环境
三、实验内容
线性表基本操作的实现
当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。
四、实验步骤
1、 本实验的程序清单如下。
下面只是根据实验指导书上的程序，各位同学要按照实际上机调试后的结果程序附上： typedef Null 0; typedef int datatype; #define maxsize 1024; typedef struct
{ datatype data[maxsize]; int last; }sequenlist;
int insert(L, x, i) sequenlist *L; int i; { int j;
if ((*L).last= =maxsize-1)
{
printf(“overflow”); return Null; } else
if ((i<1)‖(i>(*L).last+1) { printf(“error”);
return Null; } else
{ for(j=(*L).last; j>=i-1; j--)
(*L).data[j+1]=(*L).data[j]; (*L).data[i-1]=x;
(*L).last=(*L).last+1; }
return(1); }
int delete(L,i) sequenlist *L; int i; { int j;
if ((i<1)‖(i>(*L).last+1)) {printf (“error”); return Null; } else
{ for(j=i, j<=(*L).last; j++) (*L).data[j-1]=(*L).data[j]; (*L).data - -; }
return(1); }
void creatlist( ) { sequenlist *L;
int n, i, j;
printf(“请输入n个数据\\n”); scanf(“%d”,&n); for(i=0; i { printf(“data[%d]=”, i); scanf (“%d”, (*L).data[i]); } (*L).last=n-1; printf(“\\n”); } printout (L) sequenlist *L; { int i; for(i=0; i<(*L).last; i++) { printf(“data[%d]=”, i); printf(“%d”, (*L).data[i]); } } void main( ) { sequenlist *L; char cmd; int i, t; clscr( ); printf(“i, I?..插入\\n”); printf(“d,D?..删除\\n”); printf(“q,Q??退出\\n”); do { do { cmd =getchar( ); } while((cmd!=‘d’)‖(cmd!=‘D’) ‖(cmd!=‘q’) ‖ (cmd!=‘Q’) ‖(cmd!=‘i’) ‖(cmd!=‘I’)); switch (cmd) { case ‘i’,‘I’; scanf(&x); scanf(&i); insert(L, x, i); printout(L); break; case ‘d’,‘D’; scanf(&i); delete(L, i); printout(L); break; } } while ((cmd!=‘q’)&&( cmd!=‘Q’)); } 2、 本程序运行的结果如下： 根据各位同学的实际调试数据编写。 3、 结合以上程序如何进行分析和改进。并把分析和改进的内容附上。 五、实验小结 实验过程中的体会和收获。 六、实验思考题与练习 线性表的非顺序存储结构如何实现？链表是如何操作的？模仿线性表的顺序存储结构的实验编写线性表的非顺序存储结构的实验报告并进行相应的实验。 实验二 栈的基本操作 一、 实验目的 1．掌握栈的基本操作： 2．初始化栈、判栈为空、出栈、入栈等运算。 二、实验要求 1． 认真阅读和掌握本实验的算法。 2． 上机将本算法实现。 3． 保存和打印出程序的运行结果，并结合程序进行分析。 三、实验内容 利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为： 1、定义栈的顺序存取结构 2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3、定义一个函数用来实现上面问题： 十进制整数X和R作为形参 初始化栈 只要Ｘ不为０重复做下列动作 将Ｘ％Ｒ入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素 四、实验思考题与练习 1、如何实现队列的操作 2、利用栈实现数学表达式的转换 3、迷宫问题 选择一个以上题目进行实验，并编写实验报告