数据结构试验报告

2020-03-03 01:34:26 来源：范文大全收藏下载本文

实验一：ADT的类C描述向C程序的转换实验(2学时)

实验目的：

(1) 复习C语言的基本用法；

(2) 学会用类C的语言对算法进行描述的方法，将类C算法转换成C源程序的方法和过程；

(3) 抽象数据类型的定义和表示、实现；

(4) 加深对数据的逻辑结构和物理结构之间关系的理解； (5) 初步建立起时间复杂度和空间复杂度的概念。实验内容：(类C算法的程序实现) (1) 输入一组数据存入数组中，并将数据元素的个数动态地由输入函数完成。求输入数据的最大值、最小值，并通过函数参数返回所求结果；实验准备：

1) 计算机设备；2) 程序调试环境的准备，如TC环境；3) 实验内容的算法分析与代码设计与分析准备。实验步骤：

1.安装TC并设置好环境，如果已安装好，可以跳过此步； 2.录入程序代码并进行调试和算法分析；

对实验内容(1)的操作步骤：1) 用类C语言描述算法过程；2) 用C语言环境实现该算法。

对实验内容(2)的操作步骤：1) 完成算法的C实现；2) 分析其时间复杂度和空间复杂度。

3.编写实验报告。

实验结果：// 动态分配数组空间 #include #include

int size,i; int *pArray; int *p; void malloc_size() { pArray=(int *)malloc(size*(sizeof(int))); }

int input_size() { printf(\"please input the size:\\n\"); printf(\"size= \"); scanf(\"%d\",&size); return 0; }

int input_data() { printf(\"please input the value:\\n\"); for(i=0;i

printf(\"pArray[%d]= \",i);

scanf(\"%d\",&pArray[i]); } return *pArray; }

int Compare() { int x,y,i; x=y=p[0]; for(i=0;i

if(x>=p[i]) x=p[i];

if(y

max=%d\\n\",x,y); return 0; }

int Output_data() { p=pArray; printf(\"before ofpaixu :\\n\"); for(i=0;i

printf(\"%d\\t\",*pArray);

pArray++; } printf(\"\\n\"); return *pArray; }

void paixu() { int x=0; int i,j; printf(\"later of paixu:\\n\"); for(i=0;i

for(j=i+1;j

{

if(p[i]>=p[j])

{

x=p[i];p[i]=p[j];p[j]=x;

}

printf(\"%d\\t\",p[i]); } printf(\"\\n\"); }

void main() { clrscr(); input_size(); malloc_size(); input_data(); Output_data(); Compare(); paixu(); }

实验结果：

实验二

线性表及其基本操作实验(2学时) 实验目的：

(1) 熟练掌握线性表ADT和相关算法描述、基本程序实现结构； (2) 以线性表的基本操作为基础实现相应的程序；

(3) 掌握线性表的顺序存储结构和动态存储结构之区分。

实验内容：(类C算法的程序实现，任选其一。具体要求参见教学实验大纲) (1) 一元多项式运算的C语言程序实现(加法必做，其它选做)； (2) 有序表的合并； (3) 集合的并、交、补运算；实验准备：

1) 计算机设备；2) 程序调试环境的准备，如TC环境；3) 实验内容的算法分析与代码设计与分析准备。实验步骤：

1.录入程序代码并进行调试和算法分析； 2.编写实验报告。实验结果：//线性链表

#include #include #define M 6

typedef struct node { int data; struct node *next; }*Sqlist;

void Initlialize(Sqlist &L) { L=(Sqlist)malloc(sizeof(Sqlist)); L->next =NULL; }

int Getlength(Sqlist L) { int i=0; Sqlist p=L->next ; while(p!=NULL) {

i++;

p=p->next; }

return i; }

int Getelem(Sqlist L,int i) {

int j=1,e; Sqlist p=L->next; while(j

p=p->next ;

j++; }

e=p->data ; printf(\"第 %d 个元素是：%d\\n\",i,e); return 1; }

int Locatelem(Sqlist L,int x) {

int i=0; Sqlist p=L->next ; while(p!=NULL&&p->data !=x) {

p=p->next ;

i++; } if(p==NULL)

return 0; else

{

printf(\"%d 是第 %d 个元素\\n\",x,i); return i; } }

void CreatlistF(Sqlist &L,int a[ ],int n) { Sqlist s; int i; L=(Sqlist)malloc(sizeof(Sqlist)); L->next =NULL; for(i=0;i

s=(Sqlist)malloc(sizeof(Sqlist));

} }

void CreatlistR(Sqlist &L,int a[],int n) {

Sqlist s,r; int i; L=(Sqlist)malloc(sizeof(Sqlist)); L->next =NULL; r=L; for(i=0;i

s=(Sqlist)malloc(sizeof(Sqlist));

s->data =a[i];

s->next=NULL;

r->next =s ; r =s; } }

int Inselem(Sqlist &L,int i,int x) { int j=1; Sqlist s,p=L->next ; s=(Sqlist)malloc(sizeof(Sqlist)); s->data =x;s->next =NULL; if(iGetlength(L))

return 0; while(j

p=p->next ; j++; } printf(\"在第 %d 个位置插入数据：%d\\n\",i,x); s->next =p->next ;

p->next =s; return 1; }

int Delelem(Sqlist &L,int i) {

int j=1;

Sqlist p,q;

p=L;

if(iGetlength(L))

return 0; s->data =a[i];

s->next =L->next ; L->next =s;

while(j

{

p=p->next ;

j++;

}

q=p->next ;

p->next =q->next ;

free(q);

return 1; }

void Displist(Sqlist L) { Sqlist p=L->next ;

while(p!=NULL)

{

printf(\"%d\\t\",p->data);

p=p->next ;

}

printf(“\\n”); }

void input(int *pArray,int n) {

printf(\"请输入数组数据(共含 %d 个元):\\n\",n);

for(int i=0;i

Scanf(“%d”,&pArray[i]);

}

int main(int argc, char* argv[]) { Sqlist L;

int Array[M],Select; initlialize(L); do{

printf(\"请输入选择方法（1表示头插法，2表示尾插法,0表示结束）：\\n\");

scanf(\"%d\",&Select);

switch(Select)

{

case 1: printf(\"按头插法建立线性表:\\n\");

input(Array,M);

creatlistF(L,Array,M);

break; case 2: printf(\"按尾插法建立线性表:\\n\");

input(Array,M);

creatlistR(L,Array,M);

break;

}

printf(\"原线性表数据为:\\n\"); Displist(L);

Getelem(L,3);

Locatelem(L,2);

Inselem(L,5,5);

printf(\"修改后的线性表数据为:\\n\");

Delelem(L,4);

Displist(L); }while(Select!=0); return 0; } 运行结果:

实验三

栈和队列实验(6学时) 实验目的：

(1) 熟练掌握栈和队列的抽象数据类型及其结构特点； (2) 实现基本的栈和队列的基本操作算法程序。实验内容：(类C算法的程序实现，任选其一) (1) 设计与实现基本的堆栈和队列结构下的各种操作（如堆栈的PUSH、POP等操作）(必做)；

(2) 以表达式计算为例，完成一个可以进行算术表达式计算功能的算法设计与实现（选做）；实验准备：

1) 计算机设备；2) 程序调试环境的准备，如TC环境；3) 实验内容的算法分析与代码设计与分析准备。实验步骤：

1.录入程序代码并进行调试和算法分析； 2.编写实验报告。实验结果：//队列存储 #include #define QueueSize 10 typedef int status;

typedef struct sqqueue { char data[QueueSize]; int front,rear; }SqQueue;

void InitQueue(SqQueue &qu) { qu.front =qu.rear =0; }

status EnQueue(SqQueue &qu,char x) {

if((qu.rear +1)%QueueSize==qu.front)

return 0; qu.rear =(qu.rear+1)%QueueSize; qu.data[qu.rear]=x; return 1; }

status DeQueue(SqQueue &qu,char &x) { if(qu.rear==qu.front )

return 0; qu.front =(qu.front +1)%QueueSize; x=qu.data[qu.front]; return 1; }

status GetHead(SqQueue qu,char &x) { if(qu.rear ==qu.front)

return 0; x=qu.data[(qu.front+1)%QueueSize]; return 1; }

status QueueEmpty(SqQueue qu) { if(qu.rear==qu.front)

return 1; else

return 0; }

void main() { SqQueue qu; char e; InitQueue(qu); printf(\"Queue %s\\n\",(QueueEmpty(qu)==1?\"Empty\":\"Not Empty\"));

printf(\"inser a\\n\");

EnQueue(qu,\'a\');

printf(\"inser b\\n\");

EnQueue(qu,\'b\');

printf(\"inser c\\n\");

EnQueue(qu,\'c\');

printf(\"inser d\\n\");

EnQueue(qu,\'d\');

printf(\"Queue %s\\n\",(QueueEmpty(qu)==1?\"Empty\":\"Not Empty\"));

GetHead(qu,e);

printf(\"Queue of top elem is: %c\\n\",e);

printf(\"show of Queue:\\n\");

while(!QueueEmpty(qu)) {

DeQueue(qu,e);

printf(\"%c\\t\",e); }

printf(\"\\n\"); } 实验结果：

（2）//用栈实现对表达式的求值运算

#include #include #include

#define TRUE 1 #define FALSE 0 #define OK

1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define STACK_INIT_SIZE

100

#define STACKINCREMENT 10

typedef int Status; typedef char ElemType;

typedef ElemType OperandType;

typedef char OperatorType;

typedef struct {

ElemType *base;

ElemType *top;

int stacksize; }SqStack;

Status InitStack(SqStack &S) {

S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));

if(!S.base) exit (OVERFLOW);

S.top = S.base;

S.stacksize = STACK_INIT_SIZE;

return OK; }

Status GetTop(SqStack S) {

ElemType e;

if (S.top == S.base) return ERROR;

e = *(S.top-1);

return e; }

Status Push (SqStack &S,ElemType e)

{

if (S.top1

merge(r, r1, i, i+length-1, i + 2*length1

merge(r, r1, i, i+length-1, n-1);

else

for(j = i; j

void MergeSort(SortObject * pvector) {

RecordNode record[MAXNUM];

int length = 1;

while (length n) {

mergePa(pvector->record, record, pvector->n, length);

length *= 2;

mergePa(record, pvector->record, pvector->n, length);

length *= 2;

} }

SortObject vector = {8, 49,38,65,97,76,13,27,49};

int main() {

int i; printf(\"排序前序列为：\");

for(i = 0; i

printf(\"%d \", vector.record[i]); printf(\"\\n\");

MergeSort(&vector); printf(\"采用归并排序为：\");

for(i = 0; i

printf(\"%d \", vector.record[i]);

getchar();

return 0; }

实验结果：

实验十

查找实验(2学时)* 实验目的：

(1) 熟练掌握各种静态查找表方法(顺序查找、折半查找、索引顺序表等)； (2) 熟练掌握二叉排序树的构造方法和查找算法；

(3) 了解和掌握其它查找方法。

实验内容：(类C算法的程序实现，除顺序查找算法之外，任选一个) (1) 顺序查找算法的实现(必做)； (2) 折半查找算法的实现(选做)；实验结果：//查找实验

1、顺序查找：

#include #define LENGTH 20

void SequenceSearch(int *fp,int Length) {

int data;

printf(\"开始使用顺序查询.请输入你想要查找的数据: \");

scanf(\"%d\",&data);

for(int i=0;i

if(fp[i]==data)

{

printf(\"数据%d 是第 %d 个数据\\n\",data,i+1);

return ;

}

printf(\"未能查找到数据%d.\\n\",i,data); }

void main() {

int count;

int arr[LENGTH];

printf(\"请输入你的数据的个数:\");

scanf(\"%d\",&count);

printf(\"请输入 %d 个数据:\",count);

for(int i=0;i

scanf(\"%d\",&arr[i]);

SequenceSearch(arr,count); }

实验结果：

2、折半查找：

#include #include #define M 10

typedef struct { char *elem;

int length;

}SStable;

void Create(char **t)

{ int i; static char a[M+1]; *t=a; for(i=1;i

printf(\"A[%d] is:\",i);

scanf(\"%c\",&a[i]);

if (a[i] != \'\\n\') getchar(); } }

int Searth(char *t,char k) { int i; for (i=M;i>=0 && t[i]!=k ;i--);

Return i; }

void output(char *t) { int i; for (i=1;i

printf(\"\\n

A[%d] is %c\",i,t[i]); }

void px(char *t)

{ char s; int i,j; for (i=1;i

for (j=i+1;j

{

if (t[i]>t[j]) {s=t[i];t[i]=t[j];t[j]=s;}

} }

int Search_bin(char *t,char k) { int low=1,high=M,mid; while (low

mid=(low+high)/2;

if (k==t[mid]) return mid;

else if (k

else low=mid+1; } return 0; }

void main() { char *t,k; int s; Create(&t); output(t); printf(\"\\nplease input you search char:\"); k=getchar(); s=Searth(t,k); if (s>=0) printf(\"1: use search find is A[%d]\\n\",s); else printf(\"1:can not find it\\n\"); px(t); output(t); s=Search_bin(t,k); if(s==0) printf(\"\\n1:can not find it \\n\"); else printf(\"\\n2:use Search_bin find is A[%d]\\n\",s); getchar(); }

实验结果：