级本数据结构实验教案.docx

级本数据结构实验教案.docx

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

级本数据结构实验教案

数据结构

实验

数据结构设计性实验项目

1.线性表的合并：

已知线性表La和Lb的元素按值非递减排列。

归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。

分别采用顺序存储结构和链式结构来实现。

2.线性表的逆置：

设有一个线性表（e0,e1,…,en-2,en-1），请编写一个函数将这个线性表原地逆置，即将线性表内容置换为（en-1,en-2,…,e1,e0）。

线性表中的数据可以为整数、字符或字符串，试分别采用顺序存储结构和链式结构来实现。

3.约瑟夫环的实现：

设有n个人围坐一圈，用整数序列1,2,3,……,n表示顺序围坐在圆桌周围的人，现从某个位置s上的人开始报数，数到m的人出列，接着从出列的下一个人又从1开始重新报数，数到m的人出列，如此下去，直到所有人都出列为此。

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

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

检查程序的正确性和健壮性。

（1）采用数组表示作为求解过程中使用的数据结构。

（2）采用单向循环链表作为存储结构模拟整个过程，循环链表可不设头节点,必须注意空表和非空表的界限。

4.数制转换：

利用顺序栈和链栈实现数制转换

5.二叉树的遍历：

分别以顺序存储结构和二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。

6.赫夫曼树与赫夫曼编码：

已知某系统在通信联络中只可能出现8种字符a,b,c,d,e,f,g,h，其概率分别为{0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11}，试设计Huffman编码，并计算其平均码长。

（1）初始化：

从键盘读入8个字符，以及它们的权值，建立Huffman树。

（2）编码：

根据建立的Huffman树，求每个字符的Huffman编码。

对给定的待编码字符序列进行编码。

（3）译码：

利用已经建立好的Huffman树，对上面的编码结果译码。

译码的过程是分解电文中的字符串，从根结点出发，按字符’0’和’1’确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。

（4）打印 Huffman树。

7.学生成绩管理查询系统：

每个学生的数据信息有准考证号（主关键字）、姓名、语文、英语、数学、和总分等数据项，所有学生的信息构成一个学生成绩表。

假设准考证号的头两位表示地区编号。

请设计一个管理系统达到如下基本要求：

（1）初始化：

建立一个学生成绩表，输入准考证号、姓名、语文、英语、数学，然后计算每个学生的总分，存入相应的数据项；注意：

分析数据对象和它们之间的关系，并以合适的方式进行组织（可选择无序的顺序表、有序的顺序表或索引顺序表来进行存储表示）；

（2）查找：

综合应用基本查找算法完成数据的基本查询工作，并输出查询的结果；

（3）输出：

有选择性地输出满足一定条件的数据记录，如输出地区编号为"01"，并且总分在550分以上的学生的信息；

（4）计算：

计算在等概率情况下该查找表的平均查找长度。

8.排序：

编制程序让机器随机产生2000个整数，放入一个数组中；对此2000个随机数序列分别用冒泡排序、快速排序、希尔排序和堆排序方法进行排序，并比较它们的运行时间。

注意：

每三、四个同学组成一个小组。

每个实验中的题目，可分别由不同的同学完成。

其它题目可以相互交流，以利于互相提高。

数据结构验证性实验项目

实验一线性表的顺序存储实验

一、实验目的及要求

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、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现

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

二、实验学时

4学时

三、实验任务

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

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

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

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

四、实验重点、难点

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

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

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

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

五、操作要点

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

[问题描述]要在带头结点的单链表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;

}slno;

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

intCreateSL（slno*la,intn）;

voidDisplaySL（slno*la,char*comment）;

voidmain（）

{slno*la,*lb,*lc;

intn,m;

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

la->next=NULL;

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

lb->next=NULL;

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

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（slno*la,slno*lb,slno**lc）

{slno*pa,*pb,*pc;

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

pa=la->next;

pb=lb->next;

pc=*lc;

while（pa&&pb）

{

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

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=（slno*）malloc（sizeof（slno））;

pc=pc->next;

pc->data=pa->data;

pa=pa->next;

}

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

while（pb）

{

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

pc=pc->next;

pc->data=pb->data;

pb=pb->next;

}

pc->next=NULL;

return1;

}

/*生成单链表*/

intCreateSL（slno*la,intn）

{inti;

slno*p,*q;

q=la;

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

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

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

q->next=p;

q=p;

}

q->next=NULL;

return