实验指导.docx

实验指导.docx

《实验指导.docx》由会员分享，可在线阅读，更多相关《实验指导.docx（26页珍藏版）》请在冰点文库上搜索。

实验指导

实验一线性表的顺序表示实现

实验目的：

1、熟悉TC环境的使用以及程序的输入，编辑，调试，运行的全过程；

2、掌握线性表的顺序结构的静态及操作特点；

3、掌握线性表的顺序结构的静态存储和常见操作在C语言环境中的实现方法；

实验要求：

1、认真阅读和掌握本实验相关知识及算法；

2、从实验内容所给题目中任选至少一题编写程序并调试运行通过；

3、保存及打印所编程序及运行结果，并结合所学课堂内容深入分析理解。

实验内容：

1、根据教材所给类C语言算法，结合C语言特点，实现程序完成对于以整型数据为数据元素的线性表的定义、初始化、插入、删除及数据的显示等操作。

2、实现程序利用顺序表完成一个班级的一个学期的所有课程的管理：

能够增加、删除、修改学生的成绩记录。

实验内容示例：

该示例程序基于线性表的顺序存储表示方法，参照教材所述类C语言算法，主要实现了对于以整型数据为数据元素的线性表的定义、初始化、插入、删除及数据的显示等操作，此外，利用C语言函数还实现了对函数执行状态的判断。

程序清单：

#defineLIST_INIT_SIZE100

#defineLISTINCREMENT10

structsqlist

{int*elem;

intlength;

intlistsize;

};

intinitlist（structsqlist*l）/*初始化*/

{（*l）.elem=（int*）malloc（100*sizeof（structsqlist））;

if（!

（*l）.elem）return（-1）;

（*l）.length=0;

（*l）.listsize=100;

return

（1）;

}

voidshow_flag（intfl,char*func_name）/*函数执行状态判断*/

{switch（fl）

{case-2:

printf（"\n%sPARAERROR!

",func_name）;exit（0）;

case-1:

printf（"\n%sOVERFLOW!

",func_name）;exit（0）;

case1:

printf（"\n%sOK!

",func_name）;break;

};

}

intshow_elem（structsqlist*l）/*数据显示*/

{intloopnum,i;

loopnum=（*l）.length;

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

{printf（"\nNO.%delementdata=%d",i,（*l）.elem[i-1]）;

};

return

（1）;

}

intlist_insert（structsqlist*l,inte,inti）/*数据插入*/

{int*p;

int*q;

if（（i>（*l）.length+1）||（i<1））

{return（-2）;}

q=&（（*l）.elem[i-1]）;

for（p=&（（*l）.elem[（*l）.length-1]）;p>=q;--p）*（p+1）=*p;

*q=e;

++（（*l）.length）;

return

（1）;

}

intlist_delete（structsqlist*l,inti）/*数据删除*/

{int*p;

int*q;

int*x;

inty;

if（（i<1）||（i>（*l）.length））return（-2）;

q=（*l）.elem+（*l）.length-1;

p=&（（*l）.elem[i-1]）;

y=（*l）.elem[i-1];

for（++p;p<=q;++p）

{*x=*（p-1）;

*（p-1）=*p;

printf（"\n***********%d<<------%d",*x,*p）;

};

printf（"\nNO.%delemVALUE=%dwasdeleted!

",i,y）;

--（*l）.length;

return1;

}

main（）

{structsqlist*sq;

char*func_namep;

intflag;

clrscr（）;

printf（"\n<<<<>>>>>"）;

flag=initlist（sq）;

func_namep="initlist";

show_flag（flag,func_namep）;

（*sq）.elem[0]=111;

（*sq）.elem[1]=222;

（*sq）.elem[2]=333;

（*sq）.length=3;

flag=show_elem（sq）;

func_namep="show_elem";

show_flag（flag,func_namep）;

flag=list_insert（sq,456,4）;

func_namep="list_insert";

show_flag（flag,func_namep）;

show_elem（sq）;

flag=list_delete（sq,2）;

func_namep="list_delete";

show_flag（flag,func_namep）;

show_elem（sq）;

printf（"\n<<<<<>>>>>"）;

}

实验二线性表的链式表示实现

实验目的：

1、掌握线性表的链式结构的静态及操作特点；

2、掌握线性表的链式结构的存储结构和常见操作在C语言环境中的实现方法；

实验要求：

1、认真阅读和掌握本实验相关知识及算法；

2、从实验内容所给题目中任选至少一题编写程序并调试运行通过；

3、保存及打印所编程序及运行结果，并结合所学课堂内容深入分析理解。

实验内容：

1、根据教材所给类C语言算法，结合C语言特点，实现程序完成对于以整型数据为数据元素的线性单链表的定义、初始化、插入、删除及数据的显示等操作。

2、实现程序利用带头结点的单链表完成一个班级的一个学期的所有课程的管理：

能够增加、删除、修改学生的成绩记录。

3、实现程序完成对于以整型数据为数据元素的线性双向循环链表的定义、初始化、插入、删除及数据的显示等操作。

实验内容示例：

该示例程序基于线性表的链式存储表示方法，参照教材所述类C语言算法，主要实现了对于以整型数据为数据元素的线性单链表的定义、初始化、删除及数据的显示等操作。

程序清单：

#defineNULL0

#defineLENsizeof（structlinklist）

structlinklist

{intdata;

structlinklist*next;

};

structlinklist*create_list（intn）/*初始化*/

{inti;

structlinklist*p,*l;

l=（structlinklist*）malloc（LEN）;

l->next=NULL;

for（i=n;i>0;i--）

{p=（structlinklist*）malloc（LEN）;

p->data=100+i;

p->next=l->next;

l->next=p;

};

returnl;

}

voidshow_elem（structlinklist*l）/*数据显示*/

{structlinklist*p;

intj;

p=l->next;

j=1;

while（p）

{printf（"\nNo.%d----%d",j,p->data）;

j=j+1;

p=p->next;

};

printf（"---------"）;

}

intlistdelete_l（structlinklist*l,inti,int*e）/*数据删除*/

{structlinklist*p,*q;

intj=0;

p=l;

while（p->next&&j

{p=p->next;

j=j+1;

};

if（!

（p->next）||（j>i-1））return（-1）;

q=p->next;

p->next=q->next;

*e=q->data;

free（q）;

return

（1）;

}

main（）

{intm=10;

int*de;

structlinklist*sl;

printf（"\n-----------\n"）;

*de=3;

sl=create_list（m）;

show_elem（sl）;

listdelete_l（sl,1,de）;

show_elem（sl）;

printf（"\ndeletedelem=%d",*de）;

}

实验三栈和队列的表示实现

实验目的：

1、掌握栈和队列结构的静态及操作特点；

2、掌握栈和队列的顺序结构的静态存储和常见操作在C语言环境中的实现方法；

3、掌握栈和队列的链式结构的静态存储和常见操作在C语言环境中的实现方法；

实验要求：

1、认真阅读和掌握本实验相关知识及算法；

2、从实验内容所给题目中任选至少一题编写程序并调试运行通过；

3、保存及打印所编程序及运行结果，并结合所学课堂内容深入分析理解。

实验内容：

1、实现程序，基于栈结构的顺序存储表示方法，参照教材所述类C语言算法，主要实现对于以整型数据为数据元素的栈结构的定义、初始化、入栈、出栈等操作。

2、实现程序，基于栈结构的链式存储表示方法，参照教材所述类C语言算法，主要实现对于以整型数据为数据元素的栈结构的定义、初始化、入栈、出栈等操作。

3、实现程序，基于队列结构的顺序存储表示方法，参照教材所述类C语言算法，主要实现对于以整型数据为数据元素的队列结构的定义、初始化、入队、出队等操作。

4、实现程序，基于队列结构的链式存储表示方法，参照教材所述类C语言算法，主要实现对于以整型数据为数据元素的队列结构的定义、初始化、入队、出队等操作。

5、利用栈实现数制转换。

6、利用栈实现单行编辑。

实验内容示例：

该示例程序基于栈结构的顺序存储表示方法，参照教材所述类C语言算法，主要实现了对于以整型数据为数据元素的栈结构的定义、初始化、入栈、出栈等操作。

程序清单：

#defineSTACK_INIT_SIZE100

#defineSTACKINCREMENT10

structsqstack

{int*base;

int*top;

intstacksize;

};

intinitstack（structsqstack*s）/*栈的初始化*/

{s->base=（int*）malloc（100*sizeof（int））;

if（!

s->base）return（-1）;

s->top=s->base;

s->stacksize=100;

return

（1）;

}

intpush（structsqstack*s,inte）/*入栈操作*/

{

*（s->top）=e;

/*printf（"\ninpush...e=%d",*（s->top））;

*/s->top=s->top+1;

return

（1）;

}

intpop（structsqstack*s,int*e）/*出栈操作*/

{if（s->top==s->base）return（-1）;

s->top=s->top-1;

*e=*（s->top）;

return

（1）;

}

main（）

{structsqstack*ss;

inti,j=5;

int*m;

intflag;

clrscr（）;

initstack（ss）;

for（i=5;i>0;i--）push（ss,100+i）;

for（i=5;i>0;i--）

{flag=pop（ss,m）;

printf（"\nNO.%delem=%d",flag,i,*m）;

};

}

实验四串的表示实现

实验目的：

1、掌握串结构的静态及操作特点；

2、掌握串结构的静态存储和常见操作在C语言环境中的实现方法；

实验要求：

1、认真阅读和掌握本实验相关知识及算法；

2、从实验内容所给题目中任选至少一题编写程序并调试运行通过；

3、保存及打印所编程序及运行结果，并结合所学课堂内容深入分析理解。

实验内容：

1、实现程序，基于串的定长顺序存储表示方法，参照教材所述类C语言算法，主要实现对于以字符型数据为数据元素的串结构的定义、初始化、赋值、联接等操作。

2、实现程序，基于串的堆分配存储表示方法，参照教材所述类C语言算法，主要实现对于以字符型数据为数据元素的串结构的定义、初始化、赋值、求子串等操作。

实验内容示例（略）

实验五特殊矩阵、稀疏矩阵的表示实现

实验目的：

1、掌握特殊矩阵的压缩存储思路和方法以及操作特点；

2、掌握特殊矩阵的存储方法以及常见操作在C语言环境中的实现方法；

3、掌握稀疏矩阵的压缩存储思路和方法以及操作特点；

4、掌握稀疏矩阵的存储方法以及常见操作在C语言环境中的实现方法；

实验要求：

1、认真阅读和掌握本实验相关知识及算法；

2、从实验内容所给题目中任选至少一题编写程序并调试运行通过；

3、保存及打印所编程序及运行结果，并结合所学课堂内容深入分析理解。

实验内容：

1、实现程序，基于对称矩阵的压缩存储表示方法，实现对于以整数数据为数据元素的对称矩阵的压缩存储及按行、列下标查询特定元素等操作。

2、实现程序，基于稀疏矩阵三元组表存储表示方法，参照教材所述类C语言算法，实现对于以整数数据为数据元素的稀疏矩阵的存储、求转置阵等操作。

实验内容示例（略）

实验六二叉树的表示实现

实验目的：

1、掌握二叉树的静态及操作特点；

2、掌握二叉树的各种遍历方法；

3、掌握二叉树的存储、遍历、线索化等在C语言环境中的实现方法；

实验要求：

1、认真阅读和掌握本实验相关知识及算法；

2、从实验内容所给题目中任选至少一题编写程序并调试运行通过；

3、保存及打印所编程序及运行结果，并结合所学课堂内容深入分析理解。

实验内容：

1、实现程序，构造二叉树并按先序（中序、后序）遍历操作。

2、实现程序，构造二叉树并对其进行线索化操作。

实验内容示例

该示例程序完成了按满二叉树给元素编号并输入的方式构造二叉树，并在其上进行先序遍历操作。

程序清单：

#include

#defineERROR0;

#defineOK1;

typedefintElemType;

typedefstructBinaryTree

{ElemTypedata;

structBinaryTree*l;

structBinaryTree*r;

}*BiTree,BiNode;

BiNode*new（）

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

}

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

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

{

*T=NULL;

returnOK;

}

*T=new（）;

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）;

}

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;

}

main（）

{

BiTreeroot;

CreateBiTree（&root）;

PreOrderTraverse（root,printelem）;

}

实验七图的表示实现

实验目的：

1、掌握图结构的静态及操作特点；

2、掌握图结构的静态存储和常见操作在C语言环境中的实现方法；

3、掌握图结构的遍历算法在C语言环境中的实现方法。

实验要求：

1、认真阅读和掌握本实验相关知识及算法；

2、从实验内容所给题目中任选至少一题编写程序并调试运行通过；

3、保存及打印所编程序及运行结果，并结合所学课堂内容深入分析理解。

实验内容：

1、实现程序，完成有向有权图结构的邻接矩阵的构造。

2、实现程序，完成有向有权图结构的邻接表的构造。

3、实现程序，完成构造无向无权图的邻接表（矩阵）并在其上进行深度优先遍历。

4、实现程序，完成构造无向无权图的邻接表（矩阵）并在其上进行广度优先遍历。

实验内容示例：

邻接表表示的图的深度优先搜索和广度优先搜索程序：

#include

#definemaxvertexnum100

#definequeuesize100

#definenull0

typedefstruct{

　　intfront,rear,count,data[queuesize];

　}cirqueue;//循环队列结构定义

typedefintvertextype;//为了简单，设图中结点的数据为整型

typedefstructnode{

　　intadjvex;//存放邻接点序号

　　structnode*next;//指向下一个边结点

　}edgenode;//图的邻接表的边结点定义

typedefstructvnode{

　　vertextypevertex;//顶点数据域

　　edgenode*firstedge;//指向第一个边结点

　}vertexnode;//图的邻接表表示的顶点结点定义

typedefvertexnodeadjlist[maxvertexnum];//用向量定义图的邻接表表示的顶点表

typedefstruct{

　　adjlistadjlist;

　　intn;//图的顶点数

　　inte;//图的边数

　}algraph;//定义图的邻接表

typedefenum{FALSE,TRUE}boolean;

booleanvisited[maxvertexnum];//保存访问信息的布尔向量

main（）//主函数

　{//建立图g，并进行深度优先搜索和广度优先搜索

　　algraph*g;

　　g=（algraph*）malloc（sizeof（algraph））;//申请图g的邻接表空间

　　createalgraph（g）;//建立图g的邻接表表示

　　printf（"thedfsis:

"）;/

　　dfstraverse（g）;//对图g进行深度优先搜索，并打印搜索序列

　　printf（"thebfsis:

"）;

　　bfstraverse（g）;//对图g进行广度优先搜索，并打印搜索序列　

　}

createalgraph（algraph*g）

　{//建立图g的邻接表表示

　　inti,j,k;

　　intflag;

　　edgenode*s;

　　printf（"\ncreat:

\n"）//选择建立有向图或无向图

　　printf（"digraph--0\n"）;

　　printf（"undigraph--1\n"）;

　　scanf（"%d",&flag）;

　　printf（"inputn,e\n"）;

　　scanf（"%d%d",&g->n,&g->e）;//输入图g的顶点数和边数

　　printf（"inputnodes:

\n"）;

　　for（i=0;in;i++）{//构造一个只含n个顶点，边数为0的图

　　　　scanf（"%d",&（g->adjlist[i].vertex））;

　　　　　//输入顶点的数据域（为了简单起见，输入为整数）

　　g->adjlist[i].firstedge=null;//将顶点结点的firstedge域置为空

　　　}//endfor

　　for（k=0;ke;k++）{

　　　　printf（"inputi,j（0~n-1）:

\n"）;

　scanf（"%d%d",&i,&j）;

/*输入对应于一条边的顶点序号序偶对，要求顶点序号为0~n-1*/

　　　　s=（edgenode*）malloc（sizeof（edgenode））;//申请一个边结点*s

　　　　s->adjvex=j;//将序号j放入边结点*s的adjvex域

　　　　s->next=g->adjlist[i].firstedge;

　　　　//将边结点*s作为第一个邻接点插入到序号为i的顶点的边表中

　　　　g->adjlist[i].firstedge=s;

　　　　if（flag）{//若要建立无向图

　　　　　s=（edgenode*）malloc（sizeof（edgenode））;申请一个边结点*s

　　　　　　s->adjvex=i;//将序号i放入边结点*s的adjvex域

　　　　　　s->next=g->adjlist[j].firstedge;

　　　　//将边结点*s作为第一个邻接点插入到序号为j的顶点的边表中

　　　　　　g->adjlist[j].firstedge=s;

　　　　　}//endofif

　　　}//endoffor

　}//endofcreatalgraph

dfs（algraph*g,inti）

　{//对图g进行以序号为i的顶点作为出发点深度优先搜索

　　edgenode*p;

　　printf（"visitvertex:

%d",g->adjlist[i].vertex）;

/*打印序号为i的顶点信息*/

　　visited[i]=TRUE;//将序号为i的顶点设置已访问过标记

　　p=g->adjlist[i].firstedge;

/*设置寻找序号为i的第一个未访问过邻接点的扫描