《数据结构》实验报告.doc

姓名： 关宏新
学号： 089074114
班级： 计084班
指导教师： 储岳中

实验一　线性表基本操作的实现
一、 实验目的
1、 掌握使用Turbo C2.0上机调试线性表的基本方法；
2、 掌握线性表的基本操作：插入、删除、查找等运算在顺序存储结构和链式存储结构上的运算。
二、实验要求
1、 链表插入、删除和查找算法的代码；
2、 程序运行结果及分析；
3、 实验总结。
三、实验内容
1、 认真阅读和掌握本实验的参考程序。
2、 上机运行本程序，并完善删除、查找等运算。
3、 保存程序的运行结果，并结合程序进行分析。
4、 按照你对链表操作需要，重新改写算法并运行，实现链表的插入、删除、查找等运算，并保存运行结果。
四、程序流程图、算法及运行结果
1-1
#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 100
struct SeqList
{
int data[MAXSIZE];
int length;
};
typedef struct SeqList *PSeqList;

PSeqList creaeNullList_seq()
{
PSeqList palist=(PSeqList)malloc(sizeof(struct SeqList));
if(palist!=NULL)
{
palist->length=0;
return(palist);
}
printf("Out of space!!\n");
return NULL;
}

int isNullList_seq(PSeqList palist)
{
return (palist->length==0);
}

int insertPre_seq(PSeqList palist,int p,int x)
{
int q;
if(palist->length>=MAXSIZE)
{
printf("overflow!\n");
return(0);
}
if(p<0 || p>palist->length)
{
printf("Not exist!\n");
return(0);
}
if(isNullList_seq(palist))
{
palist->data[0]=x;
palist->length=1;
return(1);
}
for(q=palist->length-1;q>=p;q--)
palist->data[q+1]=palist->data[q] ;
palist->data[p]=x;
palist->length= palist->length+1;
return(1);
}

void main()
{
int i;
PSeqList list;
list=creaeNullList_seq();

printf("插入前的顺序表为：\n ");
for(i=0;i<=9;i++)
{
insertPre_seq(list,i,i*i);
printf(" %d " , list->data[i]);
}
insertPre_seq(list,5,55);

printf("\n插入后的顺序表为：\n ");
for(i=0;i<list->length;i++)
printf(" %d " , list->data[i]);
printf("\n");

getch();
}

1-2
#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 100
struct SeqList
{
int data[MAXSIZE];
int length;
};
typedef struct SeqList *PSeqList;

PSeqList creaeNullList_seq()
{
PSeqList palist=(PSeqList)malloc(sizeof(struct SeqList));
if(palist!=NULL)
{
palist->length=0;
return(palist);
}
printf("Out of space!!\n");
return NULL;
}

int isNullList_seq(PSeqList palist)
{
return (palist->length==0);
}

/* 插入 */
int insertPre_seq(PSeqList palist,int p,int x)
{
int q;
if(palist->length>=MAXSIZE)
{
printf("overflow!\n");
return(0);
}
if(p<0 || p>palist->length)
{
printf("Not exist!\n");
return(0);
}
if(isNullList_seq(palist))
{
palist->data[0]=x;
palist->length=1;
return(1);
}
for(q=palist->length-1;q>=p;q--)
palist->data[q+1]=palist->data[q] ;
palist->data[p]=x;
palist->length= palist->length+1;
return(1);
}

/* 删除 */
int deletePre_seq(PSeqList palist, int i)
{
int j;
if (!palist)
{
printf("表不存在");
return(-1);
}
if(i<1 || i> palist -> length)
{
printf ("删除位置不合法");
return(0);
}
for(j=i;j< palist -> length;j++)
palist ->data[j-1]= palist ->data[j];
palist -> length --;
return (1);
}

/* 检索 ElementType */
int locationPre_seq(PSeqList palist,int x)
{
int i=0;
if (!palist)
{
printf("表不存在");
return(-1);
}
while (i< palist->length && palist->data[i]!= x)
i++;
if (i>=palist-> length) return 0;
else return (i + 1);
}

void main()
{
int i;
PSeqList list;
list=creaeNullList_seq();

printf("插入前的顺序表为:\n ");
for(i=0;i<=9;i++)
{
insertPre_seq(list,i,i*i);
printf(" %d " , list->data[i]);
}
insertPre_seq(list,5,55);
printf("\n插入后的顺序表为:\n ");
for(i=0;i<list->length;i++)
printf(" %d " , list->data[i]);
printf("\n");

printf("删除前的顺序表为:\n ");
for(i=0;i<=9;i++)
{
insertPre_seq(list,i,i*i);
printf(" %d " , list->data[i]);
}
deletePre_seq(list, 5);
printf("\n删除后的顺序表为:\n ");
for(i=0;i<=8;i++)
printf(" %d " , list->data[i]);
printf("\n");

if(locationPre_seq(list,9)==0)
printf("检索的内容不存在!");
if(locationPre_seq(list,9)!=0&&locationPre_seq(list,9)!=-1)
printf("检索的内容下标为：%d",locationPre_seq(list,9));
printf("\n");

getch();
}

实验二 栈的基本操作
一、 实验目的
掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。
二、实验要求
1． 认真阅读和掌握本实验的算法。
2． 上机将本算法实现。
3． 保存程序的运行结果，并结合程序进行分析。
三、实验内容
利用栈的基本操作实现将任意一个十进制整数转化为R进制整数
算法为：
1、定义栈的顺序存取结构
2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）
3、定义一个函数用来实现上面问题：
(1)十进制整数X和R作为形参
(2)初始化栈
(3)只要X不为0重复做下列动作
将X % R入栈,　 X=X/R
(4)只要栈不为空重复做下列动作
栈顶出栈 , 输出栈顶元素
四、程序流程图、算法及运行结果
2-1
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define stack_init_size 100
#define stackincrement 10

typedef struct sqstack
{
int *base;
int *top;
int stacksize;
} sqstack;

int StackInit(sqstack *s)
{
s->base=(int *)malloc(stack_init_size *sizeof(int));
if(!s->base)
return 0;
s->top=s->base;
s->stacksize=stack_init_size;
return 1;
}

int Push(sqstack *s,int e)
{
if(s->top-s->base>=s->stacksize)
{
s->base=(int *)realloc(s->base,(s->stacksize+stackincrement)*sizeof(int));
if(!s->base)
return 0;
s->top=s->base+s->stacksize;
s->stacksize+=stackincrement;
}
*(s->top++)=e;
return e;
}

int Pop(sqstack *s,int e)
{
if(s->top==s->base)
return 0;
e=*--s->top;
return e;
}

int stackempty(sqstack *s)
{
if(s->top==s->base)
{
return 1;
}
else
{
return 0;
}
}

int conversion(sqstack *s)
{
int n,e=0,flag=0;
printf("输入要转化的十进制数：\n");
scanf("%d",&n);
printf("要转化为多少进制：2进制、8进制、16进制 填数字！\n");
scanf("%d",&flag);
printf("将十进制数%d转化为%d进制是：\n",n,flag);
while(n)
{
Push(s,n%flag);
n=n/flag;
}

while(!stackempty(s))
{
e=Pop(s,e);
switch(e)
{
case 10: printf("A");
break;
case 11: printf("B");
break;
case 12: printf("C");
break;
case 13: printf("D");
break;
case 14: printf("E");
break;
case 15: printf("F");
break;
default: printf("%d",e);
}
}
printf("\n");
return 0;
}

int main()
{
sqstack s;
StackInit(&s);
conversion(&s);
return 0;
}

2-2
#include<stdlib.h>
#define MAXSIZE 100

struct stack
{
int data[MAXSIZE];
int top;
};

void init(struct stack *s)
{
s->top=-1;
}

int empty(struct stack *s)
{
if(s->top==-1) return 1;
else return 0;
}

void push(struct stack *s,int i)
{
if(s->top==MAXSIZE-1){
printf("Stack is full.\n");
return;
}

s->top++;
s->data[s->top]=i;
}

int pop(struct stack *s)
{
if(empty(s)){
printf("Stack is empty.");
return -1;
}
return(s->data[s->top--]);
}

void trans(int num)
{
struct stack s;
int k;
init(&s);

while(num){
k=num%16;
push(&s,k);
num=num/16;
}

while(!empty(&s)){
k=pop(&s);
if(k<10)
printf("%d",k);
else
printf("%c",k+55);
}

printf("\n");
}

main()
{
int num;

clrscr();

printf("Input a num(-1 to quit):\n");
scanf("%d",&num);

while(num!=-1){
trans(num);
scanf("%d",&num);
}

getch();
}

实验三 串的模式匹配
一、 实验目的
1． 利用顺序结构存储串，并实现串的匹配算法。
2． 掌握简单模式匹配思想，熟悉KMP算法。
二、 实验要求
1．认真理解简单模式匹配思想，高效实现简单模式匹配；
2．结合参考程序调试KMP算法，努力算法思想；
3．保存程序的运行结果，并结合程序进行分析。
三、 实验内容
1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置；
2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并与简单模式匹配算法进行比较。
四、程序流程图、算法及运行结果
3-1
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100

int StrIndex_BF(char s[MAXSIZE],char t[MAXSIZE])
{
int i=1,j=1;
while (i<=s[0] && j<=t[0] )
{
if (s[i]==t[j]){
i++;
j++;
}
else {
i=i-j+2;
j=1;
}
}

if (j>t[0])
return (i-t[0]);
else
return -1;

}
int main()
{
char s[MAXSIZE];
char t[MAXSIZE];
int answer, i;

printf("S String -->\n ");
gets(s);

printf("T String -->\n ");
gets(t);

printf("%d",StrIndex_BF(s,t)); /*验证*/

if((answer=StrIndex_BF(s,t))>=0)
{
printf("\n");
printf("%s\n", s);
for (i = 0; i < answer; i++)
printf(" ");
printf("%s", t);
printf("\n\nPattern Found at location:%d\n", answer);
}

else
printf("\nPattern NOT FOUND.\n");

getch();
return 0;

}

3-2
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100

void get_nextval(unsigned char pat[],int nextval[])
{
int length = strlen(pat);
int i=1;
int j=0;
nextval[1]=0;

while(i<length)
{
if(j==0||pat[i-1]==pat[j-1])
{
++i;
++j;
if(pat[i-1]!=pat[j-1]) nextval[i]=j;
else nextval[i]=nextval[j];
}
else j=nextval[j];
}

}

int Index_KMP(unsigned char text[], unsigned char pat[],int nextval[])
{
int i=1;
int j=1;
int t_len = strlen(text);
int p_len = strlen(pat);

while(i<=t_len&&j<=p_len)
{
if(j==0||text[i-1]==pat[j-1]){++i;++j;}
else j=nextval[j];
}

if(j>p_len) return i-1-p_len;
else return -1;

}

int main()
{
unsigned char text[MAXSIZE];
unsigned char pat[MAXSIZE];
int nextval[MAXSIZE];
int answer, i;
printf("\nBoyer-Moore String Searching Program");
printf("\n====================================");

printf("\n\nText String --> ");
gets(text);

printf( "\nPattern String --> ");
gets(pat);
get_nextval(pat,nextval);

if((answer=Index_KMP(text, pat,nextval))>=0)
{
printf("\n");
printf("%s\n", text);
for (i = 0; i < answer; i++)
printf(" ");
printf("%s", pat);
printf("\n\nPattern Found at location %d\n", answer);
}

else
printf("\nPattern NOT FOUND.\n");

getch();
return 0;

}

3-3
#include "stdio.h"

void GetNext1(char *t,int next[])
{
int i=1,j=0;
next[1]=0;
while(i<=9)
{
if(j==0||t[i]==t[j])
{++i; ++j; next[i]=j; }
else
j=next[j];
}
}

void GetNext2(char *t , int next[])
{
int i=1, j = 0;
next[1]= 0;
while (i<=9)
{
while (j>=1 && t[i] != t[j] )
j = next[j];
i++; j++;
if(t[i]==t[j]) next[i] = next[j];
else next[i] = j;
}
}

void main()
{
char *p="abcaababc";
int i,str[10];
GetNext1(p,str);
printf("Put out:\n");
for(i=1;i<10;i++)
printf("%d",str[i]);

GetNext2(p,str);
printf("\n");
for(i=1;i<10;i++)
printf("%d",str[i]);
printf("\n");

getch();
}

实验四 二叉树操作
一、 实验目的
1． 进一步掌握指针变量的含义。
2． 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。
3． 掌握用指针类型描述、访问和处理二叉树的运算。
二、 实验要求
1． 认真阅读和掌握本实验的参考程序。
2． 按照对二叉树的操作需要，在创建好二叉树后再通过遍历算法验证创建结果。
3． 保存程序的运行结果，并结合程序进行分析。
三、 实验内容
以下参考程序是按完全二叉树思想将输入的字符串生成二叉树，并通过遍历来验证二叉树创建正确与否，但不能创建非完全二叉树，请认真研究该程序，然后模仿教材例6.4初始化方式创建二叉树:所有的空指针均用#表示，如教材图6-13对应的二叉树，建立时的初始序列为：AB#D##CE##F##。
四、程序流程图、算法及运行结果

4-1
#include"stdio.h"
#define max 30
#define NULL 0

typedef struct BNode
{
char data; /* 数据域 */
struct BNode *lchild,*rchild; /* 指向左右子女 */
}BinTree;

void preorder(BinTree *t); /* 声明先根遍历函数 */
void inorder(BinTree *t); /* 声明中根遍历函数 */
void postorder(BinTree *t);/* 声明后根遍历函数 */
int leafs(BinTree *b); /* 声明求叶子数函数 */
int treedeep(BinTree *p); /* 声明求树的深度函数 */
BinTree *swap(BinTree *p); /* 声明交换二叉树的所有结点的左右子树的函数 */

/* 将字符串中的第i个字符开始的m个字符作为数据生成对应的二叉树 */
BinTree *cre_tree(char *str,int i,int m)
{
BinTree *p;
if(i>=m) /* 无效结点 */
return NULL;
p=(BinTree *)malloc(sizeof(BinTree));/* 生成新结点 */
p->data=str[i];
p->lchild=cre_tree(str,2*i+1,m);/* 创建新结点的左子树 */
p->rchild=cre_tree(str,2*i+2,m);/* 创建新结点的右子树 */
return p;
}

void main()
{
int i,n;
char str[max];
BinTree *root;/* 根结点 */
printf("请输入二叉树的结点数:");
scanf("%d",&n);
getchar();/* 输入数字 */
printf("请输入长度为 %d 的字符串 :",n);
for(i=0;i<n;i++)
scanf("%c",&str[i]);
printf("\n");
root=cre_tree(str,0,n);
printf("二叉树已成功创建! 结点序列为：");
for(i=0;i<n;i++)
printf(" %c ",str[i]);
printf("\n");
/* 先根遍历 */
printf("\n先根遍历结果:");
preorder(root);
printf("\n");
/* 中根遍历 */
printf("\n中根遍历结果:");
inorder(root);
printf("\n");
/* 后根遍历 */
printf("\n后根遍历结果:");
postorder(root);
printf("\n");
printf("\n叶子数为：%d\n",leafs(root));
printf("\n树的深度为：%d\n",treedeep(root));
printf("\n交换左右子树后先序遍历序列为：");
preorder(swap(root));
printf("\n\n");
}

void preorder(BinTree *t)
{
if(t!=NULL)
{
printf(" %c ",t->data);
if(t->lchild)
{
printf("->");
preorder(t->lchild);
}
if(t->rchild)
{
printf("->");
preorder(t->rchild);
}
}
}

void inorder(BinTree *t)
{
if(t!=NULL)
{
inorder(t->lchild);
printf(" %c ",t->data);
inorder(t->rchild);
}
}

void postorder(BinTree *t)
{
if(t!=NULL)
{
postorder(t->lchild);
postorder(t->rchild);
printf(" %c ",t->data);
}
}

int leafs(BinTree *b)/* 求叶子数 */
{
int num1,num2;
if(b==NULL) return (0);
else if(b->lchild==NULL && b->rchild==NULL) return (1);
else
{
num1=leafs(b->lchild);
num2=leafs(b->rchild);
return(num1+num2);
}
}

int treedeep(BinTree *p)/* 求树的深度 */
{
int ldeep,rdeep,deep;
if(p==NULL) deep=0;
else
{
ldeep=treedeep(p->lchild);
rdeep=treedeep(p->rchild);
deep=(ldeep>rdeep?ldeep:rdeep)+1;
}
return deep;
}

BinTree *swap(BinTree *p)/* 交换二叉树的所有结点的左右子树 */
{
BinTree *stack[max];
int k=0;
stack[k]=NULL;
if(p!=NULL)
{
stack[++k]=p->lchild;
p->lchild=p->rchild;
p->rchild=stack[k];
p->lchild=swap(p->lchild);
p->rchild=swap(p->rchild);
}
return p;
}

实验五 图的创建与遍历.
一、 实验目的
1．掌握图的含义；
2． 掌握用邻接矩阵和邻接表的方法描述图的存储结构；
3． 理解并掌握深度优先遍历和广度优先遍历的存储结构。
二、 实验要求
1． 认真阅读和掌握本实验的参考程序。
2． 按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。
3． 保存程序的运行结果，并结合程序进行分析。
三、 实验内容
以下参考程序是按邻接表的方法