课程名称 数结构 实验名称__线性表操作
实验报告求:1实验目 2实验容 3实验步骤
4运行结果 5流程图 6实验体会
实验目
1 熟悉掌握线性表逻辑结构物理结构
2 熟悉掌握序表存储结构基操作具体函数定义
3 熟悉VC++程序基结构掌握程序中户头文件实现文件文件间相互关系作
4 熟悉VC++操作环境文件输入编辑调试运行全程
二实验求
1 实验前认真准备编写源程序
2 实验中认真调试程序运行结果进行分析注意程序正确性健壮性验证
3 断积累程序调试方法
三实验容
基题
1 元素类型整型序存储线性表进行插入删查找操作
源程序:
#include
#include
#include
const LIST_INIT_SIZE10
const LISTINCREMENT1
typedef struct
{
int *elem
int length
int listsize
}SqList
void InitList_Sq(SqList&L) 构造空线性表L
{
Lelem(int*)malloc(LIST_INIT_SIZE*sizeof(int))
if(Lelem)
exit(0) 存储分配失败
Llength0 空表长度0
LlistsizeLIST_INIT_SIZE 初始存储容量
cout<
void ListInsert_Sq(SqList&Lint iint j) 序线性表L中第i位置前插入新元素j
i合法值1{
if(i<1||i>Llength+1)
cout<
{
int *newbase(int*)realloc(Lelem(Llistsize+LISTINCREMENT)*sizeof(int))
if(newbase)
exit(0) 存储分配失败
Lelemnewbase 新基址
Llistsize+LISTINCREMENT 增加存储容量
}
int *q&(Lelem[i1])
for(int*p&(Lelem[Llength1])p>qp)
*(p+1)*p
*qj
++Llength
cout<
void ListDelete_Sq(SqList&Lint iint&j) 序线性表L中删第i元素j返回值
i合法值1{
if((i<1)||(i>Llength))
cout<
j*p 删元素值赋j
int *qLelem+Llength1 表尾元素位置
for(++pp
*(p1)*p
Llistsize 删元素元素左移
cout<}ListDelete_Sq
bool compare(int mint n)
{
if(mn)
return true
else
return false
}
int LocateElem_Sq(SqList Lint j) 序线性表L中查找第1值j满足compare()元素位序
找返回L中位序否返回0
{
int i1 i初值第1元素位序
int *pLelem p初值第1元素存储位置
while(i{
++i
p++
}
if(ireturn i
else
return 0
}LocateElem_Sq
void disp(SqList&L)
{
int *pLelem
for(int i0i{
cout<<*p<<
p++
}
}
void main()
{
SqList List
InitList_Sq(List)
int *pListelem
int mnjkxy
for(int i0i{
cin>>x
*px
p++
Listlength++
}
cout<<插入请1删请2寻找请3<for(k0k10k++)
{
cin>>y
if(y1)
{
cout<<请输入插入位置元素值<cin>>m>>n
ListInsert_Sq(Listmn)
disp(List)
}
else if(y2)
{
cout<<请输入删第元素<cin>>m
ListDelete_Sq(Listmj)
cout<disp(List)
}
else
{
cout<<请输入查找元素<cin>>m
cout<}
}
cout<}
运行结果:
加强提高题:
2编写求解Josephus问题函数整数序列1 2 3 …… n表示序围坐圆桌周围然n 9 s 1 m 5n 9 s 1 m 0者n 9 s 1 m 10作输入数检查程序正确性健壮性分析完成算法时间复杂度定义JosephusCircle类中含完成初始化报数出圈成员函数输出显示等方法(选做中)
加强题:
1采数组作求解程中数结构
提高题:
2采循环链表作求解程中数结构运行时允许指定意nsm数值直输入 n 0 退出程序
源程序:
(1)加强:
#include
#include
#include
int a[100]
int josephus(int nint sint m)
{
if((n*s*m))
{
cout<<输入错误<exit(0)
}
int x1yn
int is1
int j
while(y)
{
for(i0i{
if(a[i]+1)
a[i]x++
if(a[i]m)
{ a[i]1
cout< x1
y
}
}
for(j0j{
if(a[j]+1)
a[j]x++
if(a[j]m)
{
a[j]1
x1
y
if(y)
break
else
cout<}
}
}
return (j+1)
}
void main()
{
int nsmy0
int x
do{
for(int i0i<100i++)
{a[i]0}
cout<<请输入参加游戏总数<cin>>n
cout<<请输入开始位置报数长度<cin>>s
cin>>m
xjosephus(nsm)
cout<cout<<请选择< cout<<1重新游戏 2退出程序< cin>>y
}while(y1)
getch()
}
运行结果:
(2)提高:
#include
using namespace std
typedef struct LNode
{
struct LNode *next
int a
}LNode*LinkList
class JosephouCircle 定义类包括三元素
{
public
void SetValue()
void PickOut()
private
int n
int s
int m
}
void JosephouCircleSetValue() 设置初值
{
cout<<请输入参加游戏总数<cin>>n
cout<<请输入开始位置<cin>>s
cout<<请输入报数长度<cin>>m
}
void JosephouCirclePickOut()
{
LinkList L
LNode *p*q
int jk
L(LinkList)malloc(sizeof(LNode))
L>nextNULL
LNode*r
rL
for (int i1i{
p(LinkList)malloc(sizeof(LNode))
p>ai
p>nextNULL
r>nextp
rp
}
p>nextL>next
pL>next
j1
while(p&&j{
pp>next++j
}
for(i1i{
for(j1j{
pp>next
}
qp>nextp>nextq>next
pq>next
kq>a
cout<<输出结果<free(q)
}
}
int main(int argcchar* argv[])
{
JosephouCircle Jo1
Jo1SetValue()
Jo1PickOut()
return 0
}
运行结果:
四实验体会总结
1线性链表序表属线性表问题线性链表序表灵活方便
2线性表做元素寻找操作时候必须头结点开始寻找
体会:
编程序时候肯定会遇许问题遇问题:运行程序时候输入元素程序继续做面操作停止运行寻找修改久没发现问题实没办法问学结果终发现条语句编写时出现错误写程序时候定认真仔细点仔细点
教师评价
优
良
中
格
格
教师签名
日期
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
该内容是文档的文本内容,更好的格式请下载文档