数据结构c语言版实验教案Word格式.docx
- 文档编号:8042311
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:62
- 大小:30.89KB
数据结构c语言版实验教案Word格式.docx
《数据结构c语言版实验教案Word格式.docx》由会员分享,可在线阅读,更多相关《数据结构c语言版实验教案Word格式.docx(62页珍藏版)》请在冰点文库上搜索。
13
5.26
实验五查找(验证性)
5.27
数据结构设计性实验项目
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.学生成绩管理查询系统:
每个学生的数据信息有准考证号(主关键字)、姓名、语文、英语、数学、和总分等数据项,所有学生的信息构成一个学生成绩表。
假设准考证号的头两位表示地区编号。
请设计一个管理系统达到如下基本要求:
建立一个学生成绩表,输入准考证号、姓名、语文、英语、数学,然后计算每个学生的总分,存入相应的数据项;
注意:
分析数据对象和它们之间的关系,并以合适的方式进行组织(可选择无序的顺序表、有序的顺序表或索引顺序表来进行存储表示);
(2)查找:
综合应用基本查找算法完成数据的基本查询工作,并输出查询的结果;
(3)输出:
有选择性地输出满足一定条件的数据记录,如输出地区编号为"
01"
,并且总分在550分以上的学生的信息;
(4)计算:
计算在等概率情况下该查找表的平均查找长度。
8.排序:
编制程序让机器随机产生2000个整数,放入一个数组中;
对此2000个随机数序列分别用冒泡排序、快速排序、希尔排序和堆排序方法进行排序,并比较它们的运行时间。
每三、四个同学组成一个小组。
每个实验中的题目,可分别由不同的同学完成。
其它题目可以相互交流,以利于互相提高。
数据结构验证性实验项目
实验一线性表的顺序存储
一、实验目的及要求
1、掌握在TC环境下调试顺序表的基本方法
2、掌握顺序表的基本操作,插入、删除、查找、以及有序顺序表的合并等算法的实现。
二、实验学时
三、实验任务
1、生成一个顺序表并动态地删除任意元素和在任意位置插入元素。
2、将两个有序表合并成一个有序表。
四、实验重点、难点
1、在顺序表中移动元素。
2、在顺序表中找到正确的插入位置。
五、操作要点
(一)顺序表基本操作的实现
[问题描述]当我们要在顺序表的第i个位置上插入一个元素时,必须先将顺序表中第i个元素之后的所有元素依次后移一个位置,以便腾空一个位置,再把新元素插入到该位置。
若是欲删除第i个元素时,也必须把第i个元素之后的所有元素前移一个位置。
[基本要求]要求生成顺序表时,可以键盘上读取元素,用顺序存储结构实现存储。
[实现提示]要实现基本操作,可用实现的基本操作,也可设计简单的算法实现。
[程序实现]
#include<
stdio.h>
conio.h>
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)
\n表满不能插入!
"
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个结点*/
0||i>
(*L).length)
\n删除位置错误!
);
return0;
for(j=i+1;
j<
=(*L).length;
j++)
(*L).data[j-1]=(*L).data[j];
(*L).length--;
/*生成顺序表*/
voidcreatlist(SeqList*L)
{intn,i,j;
printf("
请输入顺序表L的数据个数:
\n"
scanf("
%d"
&
n);
for(i=0;
i<
n;
i++)
data[%d]="
i);
scanf("
&
((*L).data[i]));
(*L).length=n-1;
}/*creatlist*/
/*输出顺序表L*/
printout(SeqList*L)
{inti;
for(i=0;
=(*L).length;
data[%d]="
i);
printf("
(*L).data[i]);
}/*printout*/
main()
{SeqList*L;
charcmd;
inti,t,x;
clrscr();
creatlist(L);
do
{
\ni,I-----插入\n"
d,D-----删除\n"
q,Q-----退出\n"
{cmd=getchar();
}while((cmd!
='
i'
)&
&
(cmd!
I'
d'
D'
q'
Q'
));
switch(cmd)
{case'
:
case'
printf("
\nPleaseinputtheDATA:
scanf("
x);
\nWhere?
i);
insert(L,i,x);
printout(L);
break;
case'
:
\nWheretoDelete?
i);
delete(L,i);
printout(L);
break;
(二)有序顺序表的合并
[问题描述]已知顺序表la和lb中的数据元素按非递减有序排列,将la和lb表中的数据元素,合并成为一个新的顺序表lc
[基本要求]lc中的数据元素仍按非递减有序排列,并且不破坏la和lb表
#include<
stdlib.h>
#defineOK1
#defineERROR0
/*定义ElemType为int或别的自定义类型*/
typedefintElemType;
/*链式存储类型*/
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
/*单链表的建立(头插法)*/
voidCreateList_L(LinkList&
L,intn)//CreateList_L()function
{//ToCreatreaLinkListLwithHeadNode
inti;
LNode*p;
L=(LinkList)malloc(sizeof(LNode));
L->
next=NULL;
PleaseinputthedataforLinkListNodes:
\n"
for(i=n;
i>
0;
--i)
{
p=(LinkList)malloc(sizeof(LNode));
p->
data);
//ReverseorderinputingforCreatingaLinkList
p->
next=L->
next;
L->
next=p;
}//endoffor
if(n)printf("
SuccesstoCreateaLinkList!
elseprintf("
ANULLLinkListhavebeencreated!
}//endofCreateList()function
voidMergeList_L(LinkList&
La,LinkList&
Lb,LinkList&
Lc)
LinkListpa,pb,pc;
pa=La->
pb=Lb->
Lc=pc=La;
while(pa&
pb)
if(pa->
data<
=pb->
data)
{
pc->
next=pa;
pc=pa;
pa=pa->
}
else
next=pb;
pc=pb;
pb=pb->
}
pc->
next=pa?
pa:
pb;
free(Lb);
voidmain()
LinkListLa,Lb,Lc,p;
intn;
请输入La的长度n:
n);
CreateList_L(La,n);
输出La的内容:
p=La->
while(p)
%d->
p->
p=p->
请输入Lb的长度n:
CreateList_L(Lb,n);
输出Lb的内容:
p=Lb->
MergeList_L(La,Lb,Lc);
输出Lc的内容:
p=Lc->
六、注意事项
1、删除元素或插入元素表的长度要变化。
2、在合并表中当某一个表到表尾了就不用比较了,直接将另一个表的元素复制到总表去即可。
实验二单链表
1、掌握用在TC环境下上机调试单链表的基本方法
2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现
3、进一步掌握循环单链表的插入、删除、查找算法的实现
1、在带头结点的单链表h中第i个数据元素之前插入一个数据元素。
2、将两个有序单链表合并成一个有序单链表。
3、生成一个循环单链表。
4、在循环单链表中删除一个节点。
1、在单链表中寻找到第i-1个结点并用指针p指示。
2、比较两个单链表的节点数据大小。
3、循环单链表中只有一个节点的判断条件。
(一)单链表基本操作的实现
1、实现栈的顺序存储和链式存储。
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineMAXQSIZE100
/*定义SElemType为int或别的自定义类型*/
typedefintSElemType;
/*链式栈的存储类型*/
typedefstructSNode
SElemTypedata;
structSNode*next;
}SNode,*LinkStack;
/*取链式栈顶元素*/
intGeTop_L(LinkStacktop,SElemType&
e)
if(!
top->
next)
Error!
It'
sanemptyLinkStack!
return(ERROR);
else
e=top->
next->
data;
return(OK);
/*将元素压入链式栈*/
intPush_(LinkStacktop,SElemType&
SNode*q;
q=(LinkStack)malloc(sizeof(SNode));
q->
data=e;
next=top->
top->
next=q;
return(OK);
/*将元素弹出链式栈*/
intPop_L(LinkStacktop,SElemType&
q=top->
next=q->
free(q);
/*顺序栈的存储类型*/
typedefstruct//definestructureSqStack()
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
/*构造空顺序栈*/
intInitStack(SqStack&
S)//InitStack()sub-function
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!
S.base)
Allocatespacefailure!
return(ERROR);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}//InitStack()end
/*取顺序栈顶元素*/
intGetTop(SqStackS,SElemType&
e)//GetTop()sub-function
if(S.top==S.base)
{
saemptySqStack!
//ifemptySqStack
e=*(S.top-1);
}//GetTop()end
/*将元素压入顺序栈*/
intPush(SqStack&
S,SElemTypee)//Push()sub-function
*S.top++=e;
}//Push()end
/*将元素弹出顺序栈*/
intPop(SqStack&
S,SElemType&
e)//Pop()sub-function
e=*--S.top;
}//Pop()end
inti,j;
SqStacks;
LinkStacks1;
SElemTypee;
InitStack(s);
s1=(LinkStack)malloc(sizeof(SNode));
s1->
next=NULL;
顺序栈的元素:
for(i=1;
i<
=8;
i++)
e);
Push(s,e);
顺序栈出栈:
Pop(s,e);
%d"
e);
链式栈的元素:
for(j=1;
Push_(s1,e);
链式栈出栈:
while(NULL!
=s1->
next)
Pop_L(s1,e);
2、利用顺序栈或链栈实现数制转换。
intStackEmpty(SqStackS)
returnOK;
returnERROR;
/*利用顺序栈实现对于输入的任意一个非负十进制整数,输出
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 语言版 实验 教案