24李后浪实验一Word文件下载.docx
- 文档编号:7566274
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:18
- 大小:70.58KB
24李后浪实验一Word文件下载.docx
《24李后浪实验一Word文件下载.docx》由会员分享,可在线阅读,更多相关《24李后浪实验一Word文件下载.docx(18页珍藏版)》请在冰点文库上搜索。
intlength;
intlistsize;
}SqList;
/*构造一个空线性表算法*/
intInitList_Sq(SqList&
L)//InitList_Sq()function
{//InititialaSq_List
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!
L.elem)return(0);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return
(1);
}//endofInitList_Sq()function
/*从顺序表中查找与给定元素值相同的元素在顺序表中的位置*/
intLocateElem_Sq(SqListL,ElemTypee)//LocateElem_Sq()sub-function
{inti=1;
int*p=L.elem;
while(i<
=L.length&
&
*p++!
=e)
++i;
if(i<
=L.length)
return(i);
else
return(ERROR);
}//LocateElem_Sq()end
/*向顺序表中插入元素*/
intListInsert_sq(SqList&
L,inti,inte)//ListInsert_sq()
{if(i<
1||i>
L.length+1)//i(location)isillegal
{printf("
Initialfailure!
\n"
);
}
if(L.length>
=L.listsize)//insertintotheendoftheSqlist
{ElemType*Newbase;
Newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!
Newbase)
Overflow!
return(ERROR);
L.elem=Newbase;
L.listsize+=LISTINCREMENT;
int*p,*q;
q=&
(L.elem[i-1]);
//qpointattheelementbeforetheinsertedone
for(p=&
(L.elem[L.length-1]);
p>
=q;
--p)//movetheelement
*(p+1)=*p;
*q=e;
++L.length;
return(OK);
}//ListInser_sq()end
voidmain()
{
SqListL;
intn,i;
ElemTypee;
printf("
构建空顺序表。
InitList_Sq(L);
请输入顺序表元素个数:
scanf("
%d"
&
n);
for(i=1;
i<
=n;
i++)
请输入顺序表第%d的元素:
"
i);
scanf("
e);
ListInsert_sq(L,i,e);
}
顺序表的元素为:
%d\t"
L.elem[i-1]);
(2)运行结果:
(alt+printscreen)
(3)运行结果分析:
生成一个顺序表,可以键盘上读取元素,用顺序存储结构实现存储。
2、已知顺序表la和lb中的数据元素按非递减有序排列,将la和lb表中的数据元素,合并成为一个新的顺序表lc,lc中的数据元素仍按非递减有序排列,并且不破坏la和lb表。
#defineERROR0
/*有序顺序表的合并*/
intMerge_Sq(SqList&
A,SqList&
B,SqList&
C)//Merge_Sq()function
{//MergetheSqListAandBtoC
C.listsize=C.length=A.length+B.length;
C.elem=(ElemType*)malloc(C.listsize*sizeof(ElemType));
C.elem)
{printf("
OverFlow!
//failuretoallocateroominRAM
return(0);
};
inti=0,j=0;
//iandjistheSubscriptofA.elem[]andB.elem[]
intk=0;
//kistheSubscriptofC.elem[]
while((i<
A.length)&
(j<
B.length))//Tomergewheni<
=A.lengthandj>
=B.length
if(A.elem[i]<
=B.elem[j])
{C.elem[k]=A.elem[i];
i++;
k++;
}//endofif
{C.elem[k]=B.elem[j];
j++;
}//endofelse
A.length)//inserttherestofSqListA
{C.elem[k]=A.elem[i];
i++;
}//endofwhile
while(j<
B.length)//inserttherestofSqListB
{C.elem[k]=B.elem[j];
j++;
}
printf("
SuccesstoMergeAandB!
return
(1);
}//endofMerge_Sq()function
SqListLa,Lb,Lc;
InitList_Sq(La);
ListInsert_sq(La,i,e);
La.elem[i-1]);
InitList_Sq(Lb);
ListInsert_sq(Lb,i,e);
Lb.elem[i-1]);
Merge_Sq(La,Lb,Lc);
=Lc.length;
Lc.elem[i-1]);
将la和lb表中的数据元素,合并成为一个新的顺序表lc,lc中的数据元素仍按非递减有序排列,并且不破坏la和lb表。
3.单链表基本操作的实现。
要求生成单链表时,可以键盘上读取元素,用链式存储结构实现存储。
#include<
/*链式存储类型*/
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));
scanf("
p->
data);
//ReverseorderinputingforCreatingaLinkList
p->
next=L->
next;
next=p;
}//endoffor
if(n)printf("
SuccesstoCreateaLinkList!
elseprintf("
ANULLLinkListhavebeencreated!
}//endofCreateList()function
LinkListL,p;
intn;
输入单链表的长度\n"
CreateList_L(L,n);
p=L->
while(p)
{printf("
%d->
p->
p=p->
生成单链表,可以键盘上读取元素,用链式存储结构实现存储。
4、已知单链表la和lb中的数据元素按非递减有序排列,将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。
要求①不破坏la表和lb表的结构。
②破坏la表和lb表的结构。
voidMergeList(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{pc->
next=pb;
pc=pb;
pb=pb->
pc->
next=(pa?
pa:
pb);
free(Lb);
pc=Lc->
next;
while(pc)
pc->
pc=pc->
}//MergeList
LinkListLa,Lb,Lc;
CreateList_L(La,n);
CreateList_L(Lb,n);
MergeList(La,Lb,Lc);
将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。
5、约瑟夫环的实现:
设有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)采用单向循环链表作为存储结构模拟整个过程,循环链表可不设头节点,必须注意空表和非空表的界限。
#include<
#include<
#defineOK1
#defineERROR0
#defineLIST_INIT_SIZE10
#defineLISTINCREMENT10
/*定义ElemType为int或别的自定义类型*/
typedefintElemType;
/*链式存储类型*/
typedefstructLNode
{ElemTypenum;
structLNode*next;
}LNode,*LinkList;
LinkListcreate(LinkList&
head,intn){
LinkLists,p;
inti;
s=(LinkList)malloc(sizeof(LNode));
head=s;
s->
num=1;
p=s;
for(i=2;
i++){
s=(LinkList)malloc(sizeof(LNode));
s->
num=i;
p->
next=s;
p=s;
p->
next=head;
returnhead;
LinkListselect(LinkList&
head,intm){
LinkListp,q;
intt;
p=head;
t=1;
q=p;
p=p->
do{
t=t+1;
if(t%m==0){
printf("
num);
q->
next=p->
free(p);
p=q->
}
else{
q=p;
p=p->
while(q!
=p);
head=p;
printf("
voidmain(){
intn,m;
LinkListhead;
请输入n值:
请输入m值:
m);
head=create(head,n);
head=select(head,m);
数组表示作为求解过程中使用的数据结构。
采用单向循环链表作为存储结构模拟整个过程。
三、结论(写本次实验的收获)
通过这次实验,我掌握了以下内容:
1、掌握了用VisualC++6.0上机调试顺序表的基本方法。
2、掌握了顺序表的基本操作,插入、删除、查找、以及有序顺序表的合并等算法的实现。
3、掌握了用VisualC++6.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 24 后浪 实验