数据结构实验报告
专业班级： 指导老师：余腊生 姓
名： 学
号： 实验一 单链表的基本操作的实现
一、实验目的
掌握单链表的基本操作：建立、插入、删除、查找等运算。
二、实验仪器
安装VC++的PC机。
三、实验原理
利用线性表的特性以及其链式存储结构特点对线性表进行相关操作。
四、实验内容
程序中演示了单链表的创建、插入、删除和查找。 程序如下：
#include #include #include #include typedef struct node { int data; struct node *next; } NODE; /******************************************/ NODE *Create() { NODE *p,*head; int x; head=(NODE *)malloc(sizeof(NODE)); head->next=NULL; printf(\"Input data,-1 to End!\\n\");
scanf(\"%d\",&x); while(x!=-1) { p=(NODE *)malloc(sizeof(NODE)); p->data=x; p->next=head->next; head->next=p; scanf(\"%d\",&x); } return(head); } /******************************************/ void Output(NODE *head) { NODE *p; p=head; printf(\"Begin to dump the LinkList...\\n\"); while(p->next!=NULL){ printf(\"->%d\",p->next->data); p=p->next; } printf(\"\\nThe LinkList ended!\\n\"); } /******************************************/ int Listlen(NODE *head){ int i=0; NODE *p=head; while(p->next!=NULL){ i++; p=p->next; } return(i); } /******************************************/ int Get(NODE *head,int i){ int j=0; NODE *p=head; while(p->next&&jnext; } if(!p->next||j>i) return(0); else return(p->data); } /******************************************/ void Del(NODE *head,int i){ NODE *p=head; int j=0; while(p->next&&jnext; } if(!p->next||j>i-1) printf(\"the position is wrong\\n\"); else p->next=p->next->next; } /******************************************/ void Ins(NODE *head,int i,int e) { NODE *p=head,*q; int j=0; while(p->next&&jnext; } if(!p->next&&j>i-1) printf(\"Wrong position\\n\" ); else { q=(NODE *)malloc(sizeof(NODE)); q->data=e; q->next=p->next; p->next=q; } } /******************************************/ main(){ NODE *head; int length; int i,element; system(\"CLS\"); head=Create(); Output(head); length=Listlen(head); printf(\"the length of the link is %d\\n\",length); printf(\"input the order :\\n\"); scanf(\"%d\",&i); element=Get(head,i); printf(\"the element of the order is %d\\n\",element); printf(\"input the del position \\n\"); scanf(\"%d\",&i); Del(head,i); Output(head); printf(\"Input the insert posion and element:\\n\"); scanf(\"%d%d\",&i,&element); Ins(head,i,element); Output(head); getch(); }
五、数据记录及处理
1、运行程序,输入下面一组数据: 93 94 12 13 20 14 链表顺序：14 20 13 12 94 93
2、删除第二个数据结点，在第一个位置插入数据20。
运行结果如下: 插入结果：14 13 12 94 93 删除结果：20 14 13 12 94 93 运行结果截图：
实验二 栈和队列的实现
一、目的和要求
1.理解队列和栈的顺序存储结构和链式存储结构。通过本实验，熟悉队列、栈的结构特点； 2.熟悉队列、栈结构上的操作与算法的实现。
二、实验内容
1.队列的基本操作和应用。 2.栈的基本操作和应用。
三、仪器、设备和材料
1.适合实验要求的计算机系统 。 2.VＣ++编程平台。
四、实验原理
队列与栈是一种操作受限制的线性表，在了解线性表的基本原理的基础上，理解与完成此项实验。
五、实验步骤
1.采用队列的顺序存储结构，。
2.用菜单的形式完成队列的建立，出队，入队等基本操作。 3.采用栈的链式存储结构。
4.用菜单的形式完成栈的出栈、入栈等基本操作。
六、程序算法
#include #include #define OVERFLOW -2 #define ERROR 0 #define OK 1 #define MAX 100 //栈的最大值 typedef int SElemType; typedef int QElemType; typedef struct {SElemType *base;
SElemType *top; }SqStack;
SqStack InitStacka( ) //顺序存储实现栈的初始化 {SqStack S; S.base=(SElemType *)malloc(MAX*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base; return(S); }
void Pusha(SqStack &S,int x) //顺序存储实现栈的入栈操作 {if(S.top-S.base>=MAX) exit(OVERFLOW); *S.top++=x; }
void Popa(SqStack &S) //顺序存储实现栈的出栈操作 {SElemType *p; int x; if(S.top==S.base) return ; else {p=S.top; x=*--S.top; printf(\"\\t删除的栈顶元素是%d\\n\\t出栈操作完成后的栈为:\\n\",x); } } void printa(SqStack S) //输出 {SElemType *p; p=S.base; printf(\"\\t\"); while(p!=S.top) {printf(\"%d \",*(p++));} printf(\"\\n\"); }
typedef struct SqNode {SElemType data; SqNode *Link; }*Sqptr,NODE; typedef struct {Sqptr top; }Stack;
Stack InitStackb() //链式存储实现栈的初始化 {Stack S; S.top=(Sqptr)malloc(sizeof(NODE)); if(!S.top) exit (OVERFLOW); S.top->Link=NULL; return(S); }
void Pushb(Stack &S,int x) //链式存储实现栈的入栈操作 {Sqptr p; p=(Sqptr)malloc(sizeof(NODE)); if(!p) return; p->data=x; p->Link=S.top->Link; S.top->Link=p; }
void Popb(Stack &S) //链式存储实现栈的出栈操作 {int x; Sqptr p; if(S.top->Link==NULL) return; else {p=S.top->Link;
x=p->data;
S.top->Link=p->Link;
printf(\"\\t删除的栈顶元素是%d\\n\",x);
free(p);} }
typedef struct QNode {QElemType data; struct QNode *next; }*QueuePtr,QNode; typedef struct {QueuePtr front; QueuePtr rear; }LinkQueue; LinkQueue InitQueue() //链式存储实现队列的初始化 {LinkQueue Q; Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); Q.front->next=NULL;
return(Q); } void EnQueue(LinkQueue &Q,QElemType x) //链式存储实现队列的入队 {QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=x; p->next=NULL; Q.rear->next=p; Q.rear=p; } void DeQueue(LinkQueue &Q) //链式存储实现队列的出队 {int x; if(Q.front==Q.rear) return; QueuePtr p; p=Q.front->next; x=p->data; printf(\"\\t删除的队头元素是：%d\\n\",x); Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); return; }
typedef struct {SElemType *base; int front,rear; }SqQueue; SqQueue InitQueueb() //顺序存储实现队列的初始化 {SqQueue S; S.base=(SElemType *)malloc(MAX*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.front=S.rear=0; return(S); } void EnQueueb(SqQueue &S,int x)
//顺序存储实现队列的入队 {if((S.rear+1)%MAX==S.front) return; S.base[S.rear]=x; S.rear=(S.rear+1)%MAX; } void DeQueueb(SqQueue &S) //顺序存储实现队列的出队 {int x; if(S.front==S.rear) return; x=S.base[S.front]; S.front=(S.front+1)%MAX; printf(\"\\t删除的队头元素是:%d\\n\",x); } void main() {int choice; int n,x; printf(\"\\n\\n\"); printf(\"\\t1.采用链式存储实现栈的初始化、入栈、出栈操作\\n\"); printf(\"\\t2.采用顺序存储实现栈的初始化、入栈、出栈操作\\n\"); printf(\"\\t3.采用链式存储实现队列的初始化、入队、出队操作\\n\"); printf(\"\\t4.采用顺序存储实现队列的初始化、入队、出队操作\\n\"); printf(\"\\t请选择:\"); scanf(\"%d\",&choice); switch(choice) {case 1:Stack Sa;
printf(\"\\t1.链式存储实现栈的初始化\\n\");
printf(\"\\t2.链式存储实现栈的入栈操作\\n\");
printf(\"\\t3.链式存储实现栈的出栈操作\\n\");
while(1){
printf(\"\\t请选择：\");
scanf(\"%d\",&n);
switch(n)
{case 1:Sa=InitStackb();
printf(\"\\t链式存储栈的初始化完成!\\n\");break;
case 2:printf(\"\\t以\'0\'结束\\n\");printf(\"\\t\");
scanf(\"%d\",&x);
while(x){
Pushb(Sa,x);scanf(\"%d\",&x);}
printf(\"\\t链式存储栈的入栈操作完成!\\n\");break;
case 3:Popb(Sa);break;}}break;
case 2:SqStack S;
printf(\"\\t1.顺序存储实现栈的初始化\\n\");
printf(\"\\t2.顺序存储实现栈的入栈操作\\n\");
printf(\"\\t3.顺序存储实现栈的出栈操作\\n\");
while(1){
printf(\"\\t请选择:\");
scanf(\"%d\",&n);
switch(n)
{ case 1:S=InitStacka();
printf(\"\\t顺序存储栈的初始化完成!\\n\");break;
case 2:printf(\"\\t以\'0\'结束\\n\");
printf(\"\\t\");
scanf(\"%d\",&x);
while(x){
Pusha(S,x);
scanf(\"%d\",&x);}
printf(\"\\t顺序存储栈的入栈操作完成!\\n\");
printa(S);break;
case 3:Popa(S);
printa(S);break;}}break;
case 3:LinkQueue Q;
printf(\"\\t1.链式存储实现队的初始化\\n\");
printf(\"\\t2.链式存储实现队的入栈操作\\n\");
printf(\"\\t3.链式存储实现队的出栈操作\\n\");
while(1){
printf(\"\\t请选择：\");
scanf(\"%d\",&n);
switch(n)
{
case 1:Q=InitQueue();
printf(\"\\t链式存储队的初始化完成!\\n\");break;
case 2:printf(\"\\t以\'0\'结束\\n\");printf(\"\\t\");scanf(\"%d\",&x);
while(x){
EnQueue(Q,x);scanf(\"%d\",&x);}
printf(\"\\t链式存储队的入栈操作完成!\\n\");break;
case 3:DeQueue(Q);break;}}break;
case 4:SqQueue Sv;
printf(\"\\t1.顺序存储实现队的初始化\\n\");
printf(\"\\t2.顺序存储实现队的入栈操作\\n\");
printf(\"\\t3.顺序存储实现队的出栈操作\\n\");
while(1){
printf(\"\\t请选择：\");
scanf(\"%d\",&n);
switch(n)
{case 1:Sv=InitQueueb();
printf(\"\\t链式存储栈的初始化完成!\\n\");break;
case 2:printf(\"\\t以\'0\'结束\\n\");printf(\"\\t\");scanf(\"%d\",&x);
while(x){
EnQueueb(Sv,x);scanf(\"%d\",&x);}
printf(\"\\t链式存储栈的入栈操作完成!\\n\");break;
case 3: DeQueueb(Sv);break;}}break; } } 程序调试截图：
1.采用链式存储实现栈的初始化、入栈、出栈操作
2.采用顺序存储实现栈的初始化、入栈、出栈操作
3.采用链式存储实现队列的初始化、入队、出队操作
4.采用顺序存储实现队列的初始化、入队、出队操作
七、心得体会
实践才能出真知，在通过了上机操作后，才发现了许多在平时上理论课的时候没有想到的方方面面，编写程序时发现很多语法的错误，以及很多英语单词的记不熟，记错，程序函数错用等等，我想需要在以后多多练习，才能逐步解决这些问题。 实验三 二叉树的建立和遍历
一、目的和要求
1、了解二叉树的建立的方法及其遍历的顺序，熟悉二叉树的三种遍历
2、检验输入的数据是否可以构成一颗二叉树
二、实验内容
1.二叉树的建立和遍历
三、仪器、设备和材料
1.适合实验要求的计算机系统 。 2.VＣ++编程平台。
四、实验的描述和算法
1、实验描述
二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为耳熟的每一个左右子树又是一颗二叉树，所以可以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问完并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句实现。
2、算法
#include #include using namespace std; template struct BinTreeNode
//二叉树结点类定义 { T data;
//数据域
BinTreeNode *leftChild,*rightChild;
//左子女、右子女域
BinTreeNode(T x=T(),BinTreeNode* l =NULL,BinTreeNode* r = NULL )
:data(x),leftChild(l),rightChild(r){}
//可选择参数的默认构造函数 }; //----------- template void PreOrder_2(BinTreeNode *p)
//非递归前序遍历 { stack * > S; while(p!=NULL || !S.empty()) {
while(p!=NULL)
{
coutdata;
//访问根结点
S.push(p);
p=p->leftChild;
//遍历指针进到左子女结点
}
if(!S.empty())
//栈不空时退栈
{
p=S.top();
S.pop();
p = p->rightChild;
//遍历指针进到右子女结点
} } } //-- template void InOrder_2(BinTreeNode *p)
//非递归中序遍历 { stack* > S; do {
while(p!=NULL)
//遍历指针未到最左下的结点，不空
{
S.push(p);
p=p->leftChild;
}
if(!S.empty())
//栈不空时退栈
{
p=S.top();
S.pop();
coutdata;
p=p->rightChild;
} } while(p !=NULL || !S.empty()); }
//---- template void PostOrder_2(BinTreeNode *p) //非递归后序遍历 { stack * > S; stack tag;//定义一个新的栈用来保存tag域判别根结点的左右子树是否均遍历过
while(p != NULL || !S.empty())
//左子树经过结点加L进栈
{
while(p!=NULL)
{
S.push(p); //首先将t和tag为入栈，遍历左子树
tag.push(0);//遍历左子树前的现场保护
p=p->leftChild;
}
while( !S.empty() && tag.top()==1)
{
p=S.top();
S.pop();
tag.pop();
coutdata; //最后访问根结点。
}
if( !S.empty())
{
tag.pop();
tag.push(1);//遍历右子树前的现场保护,修改栈顶tag为，遍历右子树
p=S.top();
// 取栈顶保存的指针
p=p->rightChild;
}
else
break;
} } template void InOrder_1(BinTreeNode * subTree) {//递归函数：中序次序遍历以subTree为根的子树。
if(subTree !=NULL)
//NULL是递归终止条件
{
InOrder_1(subTree->leftChild); //中序遍历根的左子树
coutdata;
//访问根结点
InOrder_1(subTree->rightChild); //中序遍历根的右子树
} } template void PreOrder_1(BinTreeNode * subTree) {//递归函数：前序遍历以subTree为根的二叉树。 if(subTree !=NULL)
//递归结束条件
{
coutdata;//访问根结点
PreOrder_1(subTree->leftChild);
//前序遍历根的左子树
PreOrder_1(subTree->rightChild);
//前序遍历根的右子树
} } template void PostOrder_1(BinTreeNode * subTree) {//递归函数：后序次序遍历以subTree为根的子树。
if(subTree !=NULL)
//NULL是递归终止条件
{
PostOrder_1(subTree->leftChild); //后序遍历根的左子树
PostOrder_1(subTree->rightChild); //后序遍历根的右子树
coutdata;
//访问根结点
} } //------------ template void CreateBinTree(BinTreeNode * & subTree) {//递归方式建立二叉树
T item;
cin>>item;
if(item !=-1)
{
subTree = new BinTreeNode();
if(subTree == NULL)
{
cerr
exit(1);
}
subTree->data = item;
CreateBinTree(subTree->leftChild); //递归建立左子树
CreateBinTree(subTree->rightChild); //递归建立右子树
}
else subTree = NULL;
//封闭指向空子树的指针 } int main() {
BinTreeNode * Tree = NULL; cout
cout
PreOrder_1(Tree);
cout
cout
PostOrder_1(Tree); cout
cout
3、实验程序运行截图
实验四 散列法查找和排序
一、目的和要求
1.用散列法实现顺序查找，折半查找 。
二、仪器、设备和材料
1.适合实验要求的计算机系统 。 2.VＣ++编程平台。
三、实验步骤 和程序
1、顺序查找 #include #include #include #define m
100 #define NULLKEY 0 typedef int KeyType;
/* 假设关键字为整型 */ typedef struct { KeyType key; }RecordType; typedef RecordType HashTable[m]; int hash(KeyType k)/*除留余数法构造哈希函数*/ { int h; h = k%m; return h; } int HashSearch( HashTable ht, KeyType K)/*哈希查找*/ { int h0; int i; int hi; h0=hash(K); if (ht[h0].key==NULLKEY)
return (-1); else
if (ht[h0].key==K)
return (h0);
else
/* 用线性探测再散列解决冲突 */
{
for (i=1; i
{
hi=(h0+i) % m;
if (ht[hi].key==NULLKEY)
return (-1);
else
if (ht[hi].key==K)
return (hi);
}
return (-1);
}
} void main() { int i,j; int n; int p; int hj; int k; int result; HashTable ht; for(i=0; i
ht[i].key = NULLKEY; printf(\"请输入哈希表的元素个数:\"); scanf(\"%d\",&n); for(i=1; i
printf(\"请输入第%d个元素:\",i);
fflush(stdin);
scanf(\"%d\",&p);
j = hash(p);
if (ht[j].key == NULLKEY)
ht[j].key = p;
else
{
for (i=1; i
{
hj=(j+i) % m;
if (ht[hj].key==NULLKEY)
{
ht[j].key = p;
}
i = m;
}
}
} } printf(\"请输入要查找的元素:\"); fflush(stdin); scanf(\"%d\",&k); result = HashSearch(ht,k); if(result == -1) printf(\"未找到!\\n\"); else printf(\"元素位置为%d\\n\",result); system(\"pause\"); 运行结果如下：
2、折半查找
#include #define N 21 void main(void) { int a[N]; int i,n,num; int top,bottom,mid; int flag=1; int loc=-1; printf(\"你想在多少个数中进行折半查找，请输入(1--20):\"); scanf(\"%d\",&n); while(n20) {
printf(\"你输入的数不正确，请重新输入:\\n\");
printf(\"你想在多少个数中进行折半查找，请输入(1--20):\");
scanf(\"%d\",&n); } printf(\"请你输入一个整数a[1]:\"); scanf(\"%d\",&a[1]); i=2; while(i
printf(\"请你输入一个整数a[%d]:\",i);
scanf(\"%d\",&a[i]);
i++; } printf(\"\\n输出表列\\n\"); for(i=1;i
bottom=%d,
mid=%d,a[i]=%d\\n\",top,bottom,mid,mid,a[mid]); if((num>a[top])||(num
loc=-1;
flag=0; } else if(a[mid]==num) {
loc=mid;
printf(\"找到数
%6d的位置%2d\\n\",num,loc);
break; } else if(a[mid]>num) {
top=mid-1;
mid=(top+bottom)/2; } else if(a[mid]
bottom=mid+1;
mid=(top+bottom)/2; } } if(loc==-1) { printf(\"%d这个数在表列中没有找到。\\n\",num); } } 运行结果如下：
