实验一：线性表的基本操作
【实验目的】
学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。
【实验内容】
1. 顺序表的实践
1) 建立4个元素的顺序表s=sqlist[]={1，2，3，4，5}，实现顺序表建立的基本操作。
2) 在sqlist []={1，2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。
3) 在sqlist []={1，2，3，4，9，5}中删除指定位置（i=5）上的元素9，实现顺序表的删除的基本操作。
2. 单链表的实践
3. 1) 建立一个包括头结点和4个结点的（5，4，2，1）的单链表，实现单链表建立的基本操作。
2) 将该单链表的所有元素显示出来。
3) 在已建好的单链表中的指定位置（i=3）插入一个结点3，实现单链表插入的基本操作。
4) 在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置（如i=2）删除一个结点，实现单链表删除的基本操作。
5) 实现单链表的求表长操作。
【实验步骤】
1. 打开VC++。
2. 建立工程：点File->New，选Project 标签，在列表中选Win32 Console Application ，再在右边的框里为工程起好名字，选好路径，点OK->finish。至
此工程建立完毕。
3. 创建源文件或头文件：点File->New，选File 标签，在列表里选C++ Source File 。给文件起好名字，选好路径，点OK 。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
#include "stdio.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int Status;
typedef int ElemType;
typedef struct {
ElemType *elem;
int length;
int listsize;
} SqList;
Status InitList( SqList &L ) {
int i,n;
L.elem = (ElemType*) malloc (LIST_INIT_SIZE*sizeof (ElemType));
if (!L.elem) return (OVERFLOW);
printf("请输入元素的个数:");
scanf("%d",&n);
printf("请输入各元素的值:");
for (i=0;i
scanf("%d",&L.elem[i]);
L.length = n;
L.listsize = LIST_INIT_SIZE;
return OK;
}
void VisitList( SqList L ) {
int i;
}
printf("%d\t",L.elem[i]);
Status ListInsert(SqList &L, int i, ElemType e) {
ElemType *newbase,*p,*q;
if (i L.length+1) return ERROR; if (L.length >= L.listsize) { newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType)); if (!newbase) return (OVERFLOW);
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
q = &(L.elem[i-1]);
for (p = &(L.elem[L.length-1]); p >= q; --p)
*(p+1) = *p;
*q = e;
++L.length;
return OK;
}
Status ListDelete(SqList &L, int i, ElemType &e) {
ElemType *p,*q;
if ((i L.length)) return ERROR;
p = &(L.elem[i-1]);
e = *p;
q = L.elem+L.length-1;
for (++p; p
--L.length;
return OK;
}
void main(){
SqList L;
int i;
ElemType e;
InitList(L);
VisitList(L);
printf("请输入插入的位置和数值:");
scanf("%d %d",&i,&e);
ListInsert(L,i,e);
printf("插入完成后的各元素:");
VisitList(L);
printf("请输入删除的元素的位置:");
scanf("%d",&i);
ListDelete(L,i,e);
printf("删除完成后的各元素:");
VisitList(L);
}
#include "stdio.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode,*LinkList;
Status CreateList(LinkList &L, int n) {
int i;LinkList p;
L = (LinkList) malloc (sizeof (LNode));
L->next = NULL;
printf("输入元素的个数和相应值：");
scanf("%d",&n);
for (i = n; i > 0; --i) {
p = (LinkList) malloc (sizeof (LNode));
scanf("%d",&p->data);
p->next = L->next;
L->next = p;
}
return OK;
}
Status ListInsert(LinkList &L,int i,ElemType e){
LinkList s,p;
int j;
p=L;j=0;
while (p&&j
p=p->next;++j;
}
if (!p||j>i) return ERROR;
s=(LinkList)malloc(sizeof (LNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
Status ListDelete(LinkList &L,int i,ElemType &e){
LinkList p,q;
int j;
p=L;j=0;
while (p->next&&j
p=p->next;++j;
}
if (!(p->next)||j>i-1) return ERROR;
q=p->next;p->next=q->next;
e=q->data;free(q);
return OK;
}
void VisitList(LinkList L){
LNode *p;
p=L->next;
while (p){
printf("%d\t",p->data);
p=p->next;
}
}
void main(){
LinkList L;
ElemType e;
int i,n;
CreateList(L,n);
VisitList(L);
printf("请输入插入元素的位置和数值：");
scanf("%d %d",&i,&e);
} ListInsert(L,i,e); printf("插入完成后的各元素:"); VisitList(L); printf("请输入删除元素的位置:"); scanf("%d",&i); ListDelete(L,i,e); printf("删除完成后的各元素:"); VisitList(L);
【实验心得】
1. 通过这次的上机实习，我深刻理解了这门课的本质，数据结构是个框架，模
型，抽象数据结构中列举了各种操作，而所用的c++把各种操作描绘了出来构成算法。
2. 顺序表是按顺序存储的，用了一堆数组来存储，又结合了c++的程序设计，但
是在执行中出了很多错误，在通过同学的帮助下，我把顺序表的基本操作写完了。
3. 单链表写起来简单多了，但是细节上出了问题，有些变量没有定义，有些变
量重复定义，在调用函数时，直接复制过来，没有改变参数，所以一定要注意细节，
4. 实验后，我认识到对顺序表的实现运用不熟练，对结构体不能熟练掌握，认识与编译环境不同，代码可能运行受阻。
实验二：栈的表示与实现及栈的应用
【实验目的】
掌握栈的顺序存储结构及其基本操作的实现。
（1） 掌握栈后进先出的特点，并利用其特性在解决实际问题中的应用。
（2） 掌握用递归算法来解决一些问题。
【实验内容】
1. 编写程序，对于输入的任意一个非负十进制整数，输出与其等值的八进
制数。
2. 编写递归程序，实现N ！的求解。
3. 编写递归程序，实现以下函数的求解。
n , ⎧Fib (n ) =⎨⎩Fib (n -1) +Fib (n -2),
程序，实现Hanoi 塔问题。 n =0,1n >14. 编写
【实验步骤】
1. 打开VC++。
2. 建立工程：点File->New，选Project 标签，在列表中选Win32 Console Application ，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。
3. 创建源文件或头文件：点File->New，选File 标签，在列表里选C++ Source File 。给文件起好名字，选好路径，点OK 。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
#include "stdio.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int SElemType;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S){ S.base=(SElemType *)malloc
(STACK_INIT_SIZE*sizeof (SElemType));
if (!S.base) return (OVERFLOW); S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack &S, SElemType e){
if (S.top-S.base>=S.stacksize)
{ S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)
*sizeof (SElemType));
if (!S.base) return (OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S, SElemType &e)
{
if (S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
Status StackEmpty(SqStack S)
{
if (S.top==S.base)
return OK;
else
return ERROR;
}
void conversion(){
SqStack S;
int e,N;
InitStack(S);
printf("请输入转换的数据:");
scanf("%d",&N);
while (N){
Push(S,N%8);
N=N/8;
}
printf("转换后的数据:");
while (!StackEmpty(S)){
Pop(S,e);
printf("%d",e);
}
}
#include "stdio.h"
int fib( int n){
if (n>1)
return fib(n-1)+fib(n-2);
else
return n;
}
void main(){
int n;
printf("请输入递归的数据:");
scanf("%d",&n);
printf("fib(%d)=%d\n",n,fib(n));
}
#include "stdio.h"
void move(char x,int n,char z){
printf("对%d号盘从%c号柱移动到%c号柱:\n",n,x,z);
}
void hanoi (int n, char x, char y, char z) {
if (n==1)
move(x,1,z);
else
{
hanoi(n-1, x, z, y);
move(x, n, z);
hanoi(n-1, y, x, z);
}
}
void main(){
int n;
printf("请输入圆盘的个数:");
scanf("%d",&n);
hanoi(n,'x','y','z');
}
【实验心得】
：涌过这次上机实验，我认识到了
在写主函数时，如果是用void main 的形式，那么可以不用有返回值，如果是int main或|status main的话，要有返回值，既末尾要有return 语句。 2. 分号的忘记那还是很经常的，要加强注意。
3. 在定义栈的时候Num 中的元素最好使用int 类型的而不是char 类型的。
因为这样会简化char Operatecxz()的计算复杂度
4. 在做表达式的计算的时候一定要注意何时入栈何时出栈。如果如栈与出栈的情况判断不清楚就无法得出答案。 1.
实验三：二叉树的建立及遍历
【实验目的】
（3） 掌握利用先序序列建立二叉树的二叉链表的过程。
（4） 掌握二叉树的先序、中序和后序遍历算法。
【实验内容】
5. 编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。
如：输入先序序列abc###de###，则建立如下图所示的二叉树。
并显示其先序序列为：abcde
中序序列为：cbaed
后序序列为：cbeda
【实验步骤】
1. 打开VC++。
2. 建立工程：点File->New，选Project 标签，在列表中选Win32 Console Application ，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。
3. 创建源文件或头文件：点File->New，选File 标签，在列表里选C++ Source File 。给文件起好名字，选好路径，点OK 。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
#include "stdio.h"
#include "malloc.h"
#define OK 1
#define OVERFLOW -2
typedef int Status;
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree &T)
{
TElemType ch;
printf("请输入先序序列:");
scanf("%c",&ch);
if (ch=='#')
T= NULL;
else
{
if (!(T = (BiTNode *)malloc(sizeof (BiTNode))))
return OVERFLOW;
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
void preorder(BiTree &T){
if (T){
printf("%c ",T->data);
preorder(T->lchild);
preorder(T->rchild);
}
}
void inorder(BiTree &T){
if (T){
}
void posorder(BiTree &T){
}
void main ()
{
BiTree T;
} printf("\n后序序列: "); posorder(T); printf("\n中序序列: "); inorder(T); printf("\n先序序列: "); preorder(T); CreateBiTree(T); if (T){ } posorder(T->lchild); posorder(T->rchild); printf("%c ",T->data); } inorder(T->lchild); printf("%c ",T->data); inorder(T->rchild);
【实验心得】
：
在通过这次实验编程后，自己对二叉树的理解更深了一步，但有些地方没有能明白，比如说自己写了一个二叉树，但是输入进去后却不能构成一个二叉树，这个问题到现在还没有解决。
在输入二叉树时，并不是随便乱输的，输入的数据必须组成一个二叉树才行。
实验四：查找与排序
【实验目的】
6. 掌握顺序查找算法的实现。
7.
8. 掌握折半查找算法的实现。
【实验内容】
1. 编写顺序查找程序，对以下数据查找37所在的位置。
5，13，19，21，37，56，64，75，80，88，92
2. 编写折半查找程序，对以下数据查找37所在的位置。
5，13，19，21，37，56，64，75，80，88，92
【实验步骤】
1. 打开VC++。
2. 建立工程：点File->New，选Project 标签，在列表中选Win32 Console Application ，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。
3. 创建源文件或头文件：点File->New，选File 标签，在列表里选C++ Source File 。给文件起好名字，选好路径，点OK 。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
#include "stdio.h"
#include "malloc.h"
#define MAX 100
typedef int Elemtype;
typedef int Status;
typedef struct
{
Elemtype *elem;
int length;
}SSTable;
Status InitSSTable(SSTable &ST )
{
int i,n;
ST.elem = (Elemtype*) malloc (MAX*sizeof (Elemtype));
if (!ST.elem) return 0;
printf("输入元素个数和各元素的值:");
scanf("%d",&n);
for(i=1;i
{
scanf("%d",&ST.elem[i]);
}
ST.length = n;
return 1;
}
int Seq_Search(SSTable ST,Elemtype key)
{
int i;
ST.elem[0]=key;
for(i=ST.length;ST.elem[i]!=key;--i);
return i;
}
int BinarySearch(SSTable ST,Elemtype key)
{
int low,high,mid;
low=1;
high=ST.length;
while(low
{
mid=(low+high)/2;
if(ST.elem[mid]==key)
return mid;
else if(key
high=mid-1;
else
low=mid+1;
}
return 0;
}
void main()
{
SSTable ST;
int key,pos1,pos2;
InitSSTable(ST);
printf("请输入查找的元素:");
scanf("%d",&key);
pos=Seq_Search(ST,key);
pos=BinarySearch(ST,key);
printf("查找的元素位置:%d\n",pos1);
printf("折半查找的元素位置:%d\n",pos2);
}
【实验心得】
实验心得：
1这次实验主要完成了二叉树的查找与排序，在自己的编程中，不断的出错误，不断地修改，并发现自己的不足，以便下次不在犯同样的错误，提高自己的编程能力。
2. 掌握了基本的查找，排序方法。
3. 这次实验并不是很难，只要掌握了书本上的知识，基本上就可以独立完成。我现在越来越发现书本上的只是很重要，只要充分理解书本上的思想，熟练运用所学知识才能真正掌握这门技术。
4. 在程序的编写过程中，遇到很多不明白的地方，在得到同学的大力帮助下，基本掌握了。