《 数据结构》实验教案10.docx

《 数据结构》实验教案10.docx

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

《数据结构》实验教案10

教案

2010～2011学年第1学期

《数据结构》实验教案

教学院（部）计算机学院

教研室基础教研室　

授课班级09网络、信管专

授课教师冯珊

职称职务讲师

教材名称《数据结构》朱站立编著

2010年8月30日

实验安排表

周次

日期

实验课题

学时

实验报告次数

4

9.20-9.24

实验一线性表

（一）

2

0

5

9.27-10.1

实验一线性表

（二）

2

0

7

10.8-10.15

实验一线性表（三）

2

1

8

10.18-10.22

实验二栈、队列的实现及应用

2

1

9

10.25-10.29

实验三串及数组的实验

2

1

14

11.29-12.3

实验四二叉树的基本操作

2

1

15

12.6-12.10

实验五查找和排序

（一）

2

0

16

12.13-12.17

实验五查找和排序

（一）

2

1

检查日期

检查人

一式三份:

一份交教务处,一份存教学系部,一份由本人保存.

实验一线性表

（一）

一、实验目的及要求

1、掌握在TC环境下调试顺序表的基本方法

2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现。

二、实验学时

2学时

三、实验任务

1、生成一个顺序表并动态地删除任意元素和在任意位置插入元素。

2、将两个有序表合并成一个有序表。

四、实验重点、难点

1、在顺序表中移动元素。

2、在顺序表中找到正确的插入位置。

五、操作要点

（一）顺序表基本操作的实现

[问题描述]当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。

若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。

[基本要求]要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。

[实现提示]要实现基本操作，可用实现的基本操作，也可设计简单的算法实现。

[程序实现]

#include

#include

typedefintDataType;

#definemaxnum20

typedefstruct

{intdata[maxnum];

intlength;

}SeqList;

/*插入函数*/

intinsert（SeqList*L,inti,DataTypex）

/*将新结点x插入到顺序表L第i个位置*/

{intj;

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

{printf（"\ni值不合法!

"）;

return0;

}

if（（*L）.length>=maxnum-1）

{printf（"\n表满不能插入!

"）;

return0;

}

for（j=（*L）.length;j>=i;j--）（*L）.data[j+1]=（*L）.data[j];

（*L）.data[i]=x;

（*L）.length++;

return1;

}

/*删除函数*/

intdelete（SeqList*L,inti）

/*从顺序L中删除第i个结点*/

{intj;

if（i<0||i>（*L）.length）

{printf（"\n删除位置错误!

"）;

return0;

}

for（j=i+1;j<=（*L）.length;j++）

（*L）.data[j-1]=（*L）.data[j];

（*L）.length--;

return1;

}

/*生成顺序表*/

voidcreatlist（SeqList*L）

{intn,i,j;

printf（"请输入顺序表L的数据个数：

\n"）;

scanf（"%d",&n）;

for（i=0;i

{printf（"data[%d]=",i）;

scanf（"%d",&（（*L）.data[i]））;

}

（*L）.length=n-1;

printf（"\n"）;

}/*creatlist*/

/*输出顺序表L*/

printout（SeqList*L）

{inti;

for（i=0;i<=（*L）.length;i++）

{printf（"data[%d]=",i）;

printf（"%d",（*L）.data[i]）;

}/*printout*/

printf（"\n"）;

}

main（）

{SeqList*L;

charcmd;

inti,t,x;

clrscr（）;

creatlist（L）;

do

{

printf（"\ni,I-----插入\n"）;

printf（"d,D-----删除\n"）;

printf（"q,Q-----退出\n"）;

do

{cmd=getchar（）;

}while（（cmd!

='i'）&&（cmd!

='I'）&&（cmd!

='d'）&&（cmd!

='D'）&&（cmd!

='q'）&&（cmd!

='Q'））;

switch（cmd）

{case'i':

case'I':

printf（"\nPleaseinputtheDATA:

"）;

scanf（"%d",&x）;

printf（"\nWhere?

"）;

scanf（"%d",&i）;

insert（L,i,x）;

printout（L）;

break;

case'd':

case'D':

printf（"\nWheretoDelete?

"）;

scanf（"%d",&i）;

delete（L,i）;

printout（L）;

break;

}

}while（（cmd!

='q'）&&（cmd!

='Q'））;

}

（二）有序顺序表的合并

[问题描述]已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc

[基本要求]lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表

[程序实现]

#include

#definemaxnum20

typedefintDataType;

typedefstruct

{DataTypedata[maxnum];

intlength;

}SeqList;

intMergeQL（SeqListla,SeqListlb,SeqList*lc）

{inti,j,k;

if（la.length+1+lb.length+1>maxnum）

{printf（"\narrayoverflow!

"）;

return0;

}

i=j=k=0;

while（i<=la.length&&j<=lb.length）

{if（la.data[i]<=lb.data[j]）

lc->data[k++]=la.data[i++];

else

lc->data[k++]=lb.data[j++];

}

/*处理剩余部分*/

while（i<=la.length）lc->data[k++]=la.data[i++];

while（j<=lb.length）lc->data[k++]=lb.data[j++];

lc->length=k-1;

return1;

}

main（）

{SeqListla={{3,4,7,12,15},4};

SeqListlb={{2,5,7,15,18,19},5};

SeqListlc;

inti;

if（MergeQL（la,lb,&lc））

{printf（"\n"）;

for（i=0;i<=lc.length;i++）

printf（"%4d",lc.data[i]）;

}

}

六、注意事项

1、删除元素或插入元素表的长度要变化。

2、在合并表中当某一个表到表尾了就不用比较了，直接将另一个表的元素复制到总表去即可。

实验一线性表

（二）

一、实验目的及要求

1、掌握用在TC环境下上机调试单链表的基本方法

2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现

二、实验学时

2学时

三、实验任务

1、在带头结点的单链表h中第i个数据元素之前插入一个数据元素。

2、将两个有序单链表合并成一个有序单链表。

四、实验重点、难点

1、在单链表中寻找到第i-1个结点并用指针p指示。

2、比较两个单链表的节点数据大小。

五、操作要点

（一）单链表基本操作的实现

[问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。

[基本要求]用链式存储结构实现存储

[实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。

[程序实现]

#include

#include

typedefcharDataType;

typedefstructnode{

DataTypedata;/*结点的数据域*/

structnode*next;/*结点的指针域*/

}ListNode;

voidInit_List（ListNode**L）

{

（*L）=（ListNode*）malloc（sizeof（ListNode））;/*产生头结点*/

（*L）->next=NULL;

}

intList_Length（ListNode*L）

{

intn=0;ListNode*p=L->next;

while（p!

=NULL）

{

n++;

p=p->next;

}

returnn;

}

ListNode*GetNode（ListNode*L,inti）

{

intj;

ListNode*p;

p=L;j=0;/*从头结点开始扫描*/

while（p->next&&j!

=i）/*顺指针向后扫描,直到p->next为NULL或i=j为止*/

{

p=p->next;

j++;

}

if（i==j）

returnp;/*找到了第i个结点*/

else

returnNULL;/*当i<0或i>0时,找不到第i个结点*/

}

voidInsertList（ListNode*L,DataTypex,inti）

{

ListNode*p,*s;

p=GetNode（L,i-1）;/*寻找第i-1个结点*/

if（p==NULL）/*i<1或i>n+1时插入位置i有错*/

{printf（"positionerror"）;

return;

}

s=（ListNode*）malloc（sizeof（ListNode））;

s->data=x;s->next=p->next;p->next=s;

}

voidDeleteList（ListNode*L,inti）

{

ListNode*p,*r;

p=GetNode（L,i-1）;/*找到第i-1个结点*/

if（p==NULL||p->next==NULL）/*i<1或i>n时,删除位置错*/

{printf（"positionerror"）;

return;

}

r=p->next;/*使r指向被删除的结点a*/

p->next=r->next;/*将ai从链上删除*/

free（r）;

}

/*使用头插法建立带头结点链表算法*/

ListNode*CreatListF（void）

{

charch;

ListNode*head=（ListNode*）malloc（sizeof（ListNode））;/*生成头结点*/

ListNode*s;/*工作指针*/

head->next=NULL;

ch=getchar（）;/*读入第1个字符*/

while（ch!

='\n'）

{

s=（ListNode*）malloc（sizeof（ListNode））;/*生成新结点*/

s->data=ch;/*将读入的数据放入新结点的数据域中*/

s->next=head->next;

head->next=s;

ch=getchar（）;/*读入下一字符*/

}

returnhead;

}

/*使用尾插法建立带头结点链表算法*/

ListNode*CreatListR1（void）

{

charch;

ListNode*head=（ListNode*）malloc（sizeof（ListNode））;/*生成头结点*/

ListNode*s,*r;/*工作指针*/

r=head;/*尾指针初值也指向头结点*/

while（（ch=getchar（））!

='\n'）

{

s=（ListNode*）malloc（sizeof（ListNode））;

s->data=ch;

r->next=s;

r=s;

}

r->next=NULL;/*终端结点的指针域置空,或空表的头结点指针域置空*/

returnhead;

}

/*复制链表A中的内容到表B中*/

voidcopy（ListNode*a,ListNode*b）

{

ListNode*pa=a->next;ListNode*u;

ListNode*rb=b;

while（pa!

=NULL）

{

u=（ListNode*）malloc（sizeof（ListNode））;

u->data=pa->data;

rb->next=u;

rb=u;

pa=pa->next;

}

rb->next=NULL;

}

/*输出带头结点的单链表*/

voidDisplaySL（ListNode*la,char*comment）

{ListNode*p;

p=la->next;

if（p）printf（"\n%s\n",comment）;

while（p）

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

p=p->next;

}

printf（"\n"）;

}

/*主函数*/

main（）

{ListNode*la,*lb,*lc,*p;

intn,x,i;

printf（"\n用头插法建立链表la，请输入节点内容:

"）;

la=CreatListF（）;

DisplaySL（la,"新生成链la节点内容:

"）;

printf（"\n链表la的长度:

%2d",List_Length（la））;

printf（"\n请输入要插入的元素:

"）;

scanf（"%c",&x）;

printf（"\n请输入要插入的位置：

"）;

scanf（"%d",&i）;

InsertList（la,x,i）;

DisplaySL（la,"插入后链la节点内容"）;

printf（"\n请输入要删除元素的位置：

"）;

scanf（"%d",&i）;

DeleteList（la,i）;

DisplaySL（la,"删除后链la节点内容"）;

printf（"\n用尾插法建立链表lb，请输入节点内容:

"）;

fflush（stdin）;

lb=CreatListR1（）;

DisplaySL（lb,"新生成链lb节点内容:

"）;

Init_List（&lc）;

copy（la,lc）;

DisplaySL（lc,"复制生成的链lc节点内容:

"）;

}

（二）有序单链表的合并

[问题描述]已知单链表la和lb中的数据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。

[基本要求]不破坏la表和lb表的结构。

[程序实现]

#include

#include

#defineNULL0

typedefintDataType;

typedefstructSLNode

{DataTypedata;

structSLNode*next;

}slnodetype;

intMergeSL（slnodetype*la,slnodetype*lb,slnodetype**lc）;

intCreateSL（slnodetype*la,intn）;

voidDisplaySL（slnodetype*la,char*comment）;

main（）

{slnodetype*la,*lb,*lc,*p;

intn,m;

la=（slnodetype*）malloc（sizeof（slnodetype））;

la->next=NULL;

lb=（slnodetype*）malloc（sizeof（slnodetype））;

lb->next=NULL;

lc=（slnodetype*）malloc（sizeof（slnodetype））;

lc->next=NULL;

printf（"\n输入链la节点数:

"）;

scanf（"%d",&n）;

printf（"\n输入链la节点内容:

"）;

CreateSL（la,n）;

DisplaySL（la,"链la节点内容:

"）;

printf（"\n输入链lb节点数:

"）;

scanf（"%d",&m）;

printf（"\n输入链lb节点内容:

"）;

CreateSL（lb,m）;

DisplaySL（lb,"链lb节点内容:

"）;

if（MergeSL（la,lb,&lc））DisplaySL（lc,"合成后的链lc:

"）;

getchar（）;

}

intMergeSL（slnodetype*la,slnodetype*lb,slnodetype**lc）

{slnodetype*pa,*pb,*pc;

lc=（slnodetype*）malloc（sizeof（slnodetype））;

pa=la->next;

pb=lb->next;

pc=*lc;

while（pa&&pb）

{

pc->next=（slnodetype*）malloc（sizeof（slnodetype））;

pc=pc->next;

if（pa->data<=pb->data）

{pc->data=pa->data;

pa=pa->next;

}

else{pc->data=pb->data;

pb=pb->next;

}

}

while（pa）/*插入la链的剩余段*/

{

pc->next=（slnodetype*）malloc（sizeof（slnodetype））;

pc=pc->next;

pc->data=pa->data;

pa=pa->next;

}

/*插入lb链的剩余段*/

while（pb）

{

pc->next=（slnodetype*）malloc（sizeof（slnodetype））;

pc=pc->next;

pc->data=pb->data;

pb=pb->next;

}

/*生成单链表*/

intCreateSL（slnodetype*la,intn）

{inti;

slnodetype*p,*q;

q=la;

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

{p=（slnodetype*）malloc（sizeof（slnodetype））;

scanf（"%d",&p->data）;

q->next=p;

q=p;

}

q->next=NULL;

return1;

}

/*输出单链表*/

voidDisplaySL（slnodetype*la,char*comment）

{slnodetype*p;

p=la->next;

if（p）printf（"\n%s\n",comment）;

while（p）

{printf（"\n%3d",p->data）;

p=p->next;

}

printf（"\n"）;

}

六、注意事项

1、在第i个节点前删除或插入节点需要用指针来表示第i-1个节点。

2、在合并链表时需要设置多个指针变量。

实验一线性表（三）

一、实验目的及要求

1、掌握用在TC环境下上机调试循环链表的基本方法

2、进一步掌握循环单链表的插入、删除、查找算法的实现

二、实验学时

2学时

三、实验任务

1、生成一个循环单链表。

2、在循环单链表中删除一个节点。

四、实验重点、难点

1、循环单链表中只有一个节点的判断条件。

2、在循环单链表中删除一个节点。

五、操作要点

（一）约瑟夫环问题

[问题描述]设有N个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人以出列，如此下去，直到所有人都出列为此。

试设计确定他们的出列次序序列的程序。

[基本要求]选择单向循环链表作为存储结构模拟整个过程，并依次输出列的各人的编号。

[实现提示]程序运行之后，首先要求用户指定初始报数的下限值，可以n<=30,此题循环链表可不设头节点，而且必须注意空表和非空表的界限。

如n=8,m=4时，若从第一个人，设每个人的编号依次为1，2，3，…开始报数，则得到的出列次序为4，8，5，2，1，3，7，6，

如下图所示，内层数字表示人的编号，每个编号外层的数字代表人出列的序号。

[程序实现]

#include

#include

typedefstruct