数据结构报告.docx

数据结构报告.docx

《数据结构报告.docx》由会员分享，可在线阅读，更多相关《数据结构报告.docx（25页珍藏版）》请在冰点文库上搜索。

数据结构报告

实验一线性表的应用

[实验目的]：

1.把握线性表的逻辑结构概念、线性表的两种存储结构（顺序和链式）；

2.把握顺序表和链表的概念及大体操作，运用其解决一些实际问题。

[实验题目]：

一、请编写26个字母按特定字母值插入或删除的完整程序，可自行选用顺序存储或链表结构。

答：

#include<>/*全局变量及函数提早说明：

*/

#include<>

typedefstructliuyu{chardata;structliuyu*link;}test;

liuyu*p,*q,*r,*head;

intL;/*元素的个数*/

intm=sizeof（test）;

voidbuild（）;/*主函数中会被挪用的函数应当预先说明*/

voiddisplay（）;

intinsert_char（char,char）;/*插入一个字母，在第字母Y之前，假设无字母那么加到末尾*/

intdelet_char（char）;/*删除元素X，注意保留X的前趋元素指针！

*/

/*---------------------------------------------------------*/

voidbuild（）/*字母链表的生成*/

{inti;

head=（test*）malloc（m）;/*m=sizeof（test）;*/

p=head;

for（i=1;i

{p->data=i+'a'-1;/*'a'也可用其ASCII码97来表示*/

p->link=（test*）malloc（m）;/*m=sizeof（test））;*/

p=p->link;}

p->data=i+'a'-1;

p->link=NULL;

}

/*---------------------------------------------------------*/

voiddisplay（）/*字母链表的输出*/

{p=head;

while（p->link!

=NULL）

{printf（"%c",p->data）;

p=p->link;}

printf（"%c\n",p->data）;

}

/*---------------------------------------------------------*/

intinsert_char（charX,charY）/*插入一个字母X在某个字母Y之前，假设找不到Y字母那么加到末尾*/

{p=head;

r=（test*）malloc（m）;

r->data=X;

if（head->data==Y）

{head=r;

r->link=p;}

else{while（（p->data!

=Y）&&（p->link!

=NULL））{q=p;p=p->link;}

if（p->data==Y）{q->link=r;r->link=p;}

else{p->link=r;r->link=NULL;}

}

L++;

return（0）;

}

/*---------------------------------------------------------*/

intdelet_char（charX）/*删除元素X，注意保留X的前趋元素指针！

*/

{p=head;

if（head->data==X）{head=head->link;free（p）;}

else{while（（p->data!

=X）&&（p->link!

=NULL））

{q=p;

p=p->link;}

if（p->data==X）

{q->link=p->link;

free（p）;}

elsereturn（-1）;

}

L--;

return（0）;

}

/*---------------------------------------------------------*/

voidmain（void）/*字母线性表的生成和输出*/

{L=26;

build（）;

display（）;

printf（"insertreturnvalue=%d\n",insert_char（'L','W'））;

display（）;

printf（"deletereturnvalue=%d\n",delet_char（'z'））;

display（）;

}

二、创建一个链表。

.程序源代码：

/*creatalist*/

#include""

#include""

structlist

{intdata;

structlist*next;

};

typedefstructlistnode;

typedefnode*link;

intmain（）

{linkptr,head;

intnum,i;

ptr=（link）malloc（sizeof（node））;

head=ptr;

printf（"pleaseinput5numbers==>\n"）;

for（i=0;i<=4;i++）

{

scanf（"%d",&num）;

ptr->next=（link）malloc（sizeof（node））;

if（i==4）ptr->next=NULL;

elseptr=ptr->next;

}

ptr=head;

while（ptr!

=NULL）

{printf（"Thevalueis==>%d\n",ptr->data）;

ptr=ptr->next;

}

return0;

}

3、反向输出一个链表。

程序源代码：

/*reverseoutputalist*/

#include""

#include""

structlist

{intdata;

structlist*next;

};

typedefstructlistnode;

typedefnode*link;

intmain（）

{linkptr,head,tail;

intnum,i;

tail=（link）malloc（sizeof（node））;

tail->next=NULL;

ptr=tail;

printf（"\npleaseinput5data==>\n"）;

for（i=0;i<=4;i++）

{

scanf（"%d",&num）;

ptr->data=num;

head=（link）malloc（sizeof（node））;

head->next=ptr;

ptr=head;

}

ptr=ptr->next;

while（ptr!

=NULL）

{printf（"Thevalueis==>%d\n",ptr->data）;

ptr=ptr->next;

}return0;

}

4.顺序表操作

#include""

#include""

#defineMaxSize50

typedefcharelemtype;

typedefstructnode

{

elemtypedata[MaxSize];

intlen;

}lnode,*List;

voidinit（ListL）

{L->len=0;}

intlength（ListL）

{returnL->len;}

elemtypegetnode（ListL,intpos）

{

if（pos<1||pos>L->len）printf（"error"）;

elsereturnL->data[pos-1];

}

intlocate（ListL,elemtypex）

{inti=0;

while（ilen&&L->data[i]!

=x）i++;

if（i==L->len）return-1;

elsereturn（i+1）;

}

voidinsert（ListL,intpos,elemtypex）

{intj;

if（pos<1||pos>L->len+1）printf（"inserterror\n"）;

else{

L->len++;

for（j=L->len;j>=pos;j--）L->data[j]=L->data[j-1];

L->data[pos-1]=x;};

}

voiddelnode（ListL,intpos）

{intj;

if（pos<1||pos>L->len）printf（"delerror\n"）;

else{

for（j=pos;jlen;j++）

L->data[j-1]=L->data[j];

L->len--;}

}

voidprint（ListL）

{inti;

for（i=1;ilen;i++）

printf（"%c->",L->data[i-1]）;

printf（"%c",L->data[L->len-1]）;

}

intmain（）

{

inti=1,n;

lnodeL;

charch,x;

init（&L）;

printf（"\n\n\n*顺序演出示程序*\n"）;

printf（"请输入你想成立的顺序表的元素，以？

终止:

"）;

ch=getchar（）;

while（ch!

='?

'）

{insert（&L,i,ch）;

i++;

ch=getchar（）;

};

printf（"你成立的顺序表为:

"）;

print（&L）;

printf（"\n顺序表的长度为:

%d",;

printf（"\n输入你想查找的元素：

"）;

fflush（stdin）;

scanf（"%c",&x）;

printf（"你查找的元素为%c序位为%d",x,locate（&L,x））;

printf（"\n输入你想查找的元素序位:

"）;

scanf（"%d",&n）;

printf（"\n你查找的元素为：

%c",getnode（&L,n））;

printf（"\n输入你想插入的元素和序位:

<用逗号隔开>"）;

fflush（stdin）;

scanf（"%c,%d",&x,&n）;

insert（&L,n,x）;

printf（"\n插入后顺序表为：

"）;

print（&L）;

fflush（stdin）;

printf（"\n请输入你想删除的元素序位：

"）;

scanf（"%d",&n）;

delnode（&L,n）;

printf（"\n删除后的顺序表为：

"）;

print（&L）;

fflush（stdin）;

}

实验结果：

实验二栈和队列的应用

[实验目的]：

1.把握栈和队列的结构概念和特性；

2.把握栈和队列的大体操作和栈和队列在程序设计中的应用。

[实验题目]：

进制转换

#include

#defineSTACK_INIT_SIZE100

#defineSTACKINCREMENT10

#defineOK1

#defineERROR0

typedefstruct

握数组的概念和实现，加深对数组的类型明白得。

2.把握数组的存储结构和访问方式。

3.把握特殊矩阵的存储方式。

[实验题目]：

1假设稀疏矩阵A和B均以三元组表作为存储结构。

试写出矩阵相加的算法，另设三元组C寄存结果矩阵。

#include""

#include""

#defineMAXSIZE100

typedefstruct

{

introw,col;

inte;

}triple;

typedefstruct

{

tripledata[MAXSIZE+1];

intm,n,len;

}TSMATRIX;

voidinput（TSMATRIX*pa）

{intnrow,ncol,num,elem,i;

printf（"shuru"）;

scanf（"%d%d%d",&nrow,&ncol,&num）;

pa->m=nrow;

pa->n=ncol;

pa->len=num;

for（i=1;i<=num;i++）

{

printf（"zaishuru",i）;

scanf（"%d%d%d",&nrow,&ncol,&elem）;

pa->data[i].row=nrow;

pa->data[i].col=ncol;

pa->data[i].e=elem;

}

}

voidprint（TSMATRIX*pa）

{

inti,j,t;

for（i=1,t=1;i<=pa->m;i++）

{for（j=1,t=1;j<=pa->n;j++）

{

if（pa->data[t].row==i&&pa->data[t].col==j）

{printf（"%4d",pa->data[t].e）;

t++;

}

else

printf（"%4d",0）;

}

printf（"\n"）;

}

}

voidadd（TSMATRIX*pa,TSMATRIX*pb,TSMATRIX*pc）

{

inti,j,t;

if（pa->m!

=pb->m||pa->n!

=pb->n）

{

printf（"buneng\n"）;

return;

}

pc->m=pa->m;

pc->n=pa->n;

i=1;

j=1;

t=0;

while（i<=pa->len&&j<=pb->len）

{

if（（（pa->data[i].row-1）*pa->n+pa->data[i].col-1）<

（（pb->data[j].row-1）*pa->n+pb->data[j].col-1））

{

t++;

pc->data[t].row=pa->data[i].row;

pc->data[t].col=pa->data[i].col;

pc->data[t].e=pa->data[i].e;

i++;

}

else

if（（（pa->data[i].row-1）*pa->n+pa->data[i].col-1）>

（（pb->data[j].row-1）*pa->n+pb->data[j].col-1））

{

t++;

pc->data[t].row=pb->data[i].row;

pc->data[t].col=pb->data[i].col;

pc->data[t].e=pb->data[i].e;

j++;

}

else

if（pb->data[i].e+pb->data[j].e!

=0）

{

t++;

pc->data[t].row=pa->data[i].row;

pc->data[t].col=pa->data[i].col;

pc->data[t].e=pa->data[i].e+pb->data[j].e;

i++;

j++;

}

}

while（i<=pa->len）

{t++;

pc->data[t].row=pa->data[i].row;

pc->data[t].col=pa->data[i].col;

pc->data[t].e=pa->data[i].e;

i++;

}

while（j<=pb->len）

{

t++;

pc->data[t].row=pb->data[i].row;

pc->data[t].col=pb->data[i].col;

pc->data[t].e=pb->data[i].e;

j++;

}

pc->len=t;

}

voidmain（）

{

TSMATRIXa,b,c;

input（&a）;

print（&a）;

input（&b）;

print（&b）;

add（&a,&b,&c）;

print（&c）;}

实验结果：

实验五二叉树的应用

[实验目的]：

把握二叉树的性质和存储结构；把握二叉树的遍历和线索化及其应用；把握哈夫曼树的应用。

[实验题目]：

源程序：

#include<>

#include<>

#defineERROR0;

#defineOK1;

typedefintElemType;

typedefstructBinaryTree

{

ElemTypedata;

structBinaryTree*l;

structBinaryTree*r;

}*BiTree,BiNode;

BiNode*new1（）

{

return（（BiNode*）malloc（sizeof（BiNode）））;

}

CreateSubTree（BiTree*T,ElemType*all,inti）

{

if（（all[i]==0）||i>16）

{

*T=NULL;

returnOK;

}

*T=new1（）;

if（*T==NULL）

returnERROR;

（*T）->data=all[i];

CreateSubTree（&（（*T）->l）,all,2*i）;

CreateSubTree（&（（*T）->r）,all,2*i+1）;

}

CreateBiTree（BiTree*T）

{

ElemTypeall[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};

CreateSubTree（T,all,1）;

return1;

}

printelem（ElemTyped）

{

printf（"%d\n",d）;

}

PreOrderTraverse（BiTreeT,int（*Visit）（ElemTyped））

{

if（T）

{

if（Visit（T->data））

if（PreOrderTraverse（T->l,Visit））

if（PreOrderTraverse（T->r,Visit））returnOK;

returnERROR;

}elsereturnOK;

}

InOrderTraverse（BiTreeT,int（*Visit）（ElemTyped））

{

if（T!

=NULL）

{

if（InOrderTraverse（T->l,Visit））

if（Visit（T->data））

if（InOrderTraverse（T->r,Visit））returnOK;

returnERROR;

}elsereturnOK;

}

PostOrderTraverse（BiTreeT,int（*Visit）（ElemTyped））

{

if（T）

{

if（PostOrderTraverse（T->l,Visit））

if（PostOrderTraverse（T->r,Visit））

if（Visit（T->data））returnOK;

}elsereturnOK;

}

voidmain（）

{

BiTreeroot;

CreateBiTree（&root）;

printf（"这棵树的前序遍历结果为:

"）;

PreOrderTraverse（root,printelem）;

printf（"\n"）;

printf（"这棵树的中序遍历结果为:

"）;

InOrderTraverse（root,printelem）;

printf（"\n"）;

printf（"这棵树的后序遍历结果为:

"）;

PostOrderTraverse（root,printelem）;

printf（"\n"）;

}

2编写递归算法，计算二叉树中叶子结点的数量。

#include<>

#include<>

typedefstructliuyu{intdata;structliuyu*lchild,*rchild;}test;

liuyu*root;

intsum=0;intm=sizeof（test）;

voidinsert_data（intx）/*如何生成二叉排序树？

参见教材P43C程序*/

{liuyu*p,*q,*s;

s=（test*）malloc（m）;

s->data=x;

s->lchild=NULL;

s->rchild=NULL;

if（!

root）{root=s;return;}

p=root;

while（p）/*如何接入二叉排序树的适当位置*/

{q=p;

if（p->data==x）{printf（"dataalreadyexist!

\n"）;return;}

elseif（xdata）p=p->lchild;elsep=p->rchild;

}

if（xdata）q->lchild=s;

elseq->rchild=s;

}

DLR（liuyu*root）/*中序遍历递归函数*/

{if（root!

=NULL）

{if（（root->lchild==NULL）&&（root->rchild==NULL））{sum++;printf（"%d\n",root->data）;}

DLR（root->lchild）;

DLR（root->rchild）;}

return（0）;

}

main（）/*先生成二叉排序树，再挪用中序遍历递归函数进行排序输出*/

{inti,x;

i=1;

root=NULL;/*万万别忘了赋初值给root!

*/

do{printf（"pleaseinputdata%d:

",i）;

i++;

scanf（"%d",&x）;/*从键盘搜集数据，以-9999表示输入终止*/

if（x==-9999）{

DLR（root）;

printf（"\nNowoutputcountvalue:

%d\n",sum）;

return（0）;}

elseinsert_data（x）;}/*挪用插入数据元素的函数*/

while（x!

=-9999）;

return（0）;}

执行结果：

假设一开始运行就输入-9999，那么无叶子输出，sum=0。

实验七查找

[实验目的]：

1.把握顺序表和有序表的查找方式；

2.把握二叉排序树的构造和查找方式；

[实验题目]：