数据结构验证性实验指导书.docx
- 文档编号:4347817
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:52
- 大小:30.44KB
数据结构验证性实验指导书.docx
《数据结构验证性实验指导书.docx》由会员分享,可在线阅读,更多相关《数据结构验证性实验指导书.docx(52页珍藏版)》请在冰点文库上搜索。
数据结构验证性实验指导书
实验一线性表的顺序存储实验
一、实验目的
1、掌握用VisualC++6.0上机调试顺序表的基本方法
2、掌握顺序表的基本操作,插入、删除、查找、以及有序顺序表的合并等算法的实现
二、实验内容
1、顺序表基本操作的实现
[问题描述]当我们要在顺序表的第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')); } 2、有序顺序表的合并 [问题描述]已知顺序表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、掌握用VisualC++6.0上机调试单链表的基本方法 2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现 3、进一步掌握循环单链表的插入、删除、查找算法的实现 二、实现内容 1、单链表基本操作的实现 [问题描述]要在带头结点的单链表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节点内容: "); } 2、有序单链表的合并 [问题描述]已知单链表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"); } 3.约瑟夫环问题 [问题描述]设有N个人围坐一圈,现从某个人开始报数,数到M的人出列,接着从出列的下一个人开始重新报数,数到M的人以出列,如此下去,直到所有人都出列为此。 试设计确定他们的出列次序序列的程序。 [基本要求]选择单向循环链表作为存储结构模拟整个过程,并依次输出列的各人的编号。 [实现提示]程序运行之后,首先要求用户指定初始报数的下限值,可以n<=30,此题循环链表可不设头节点,而且必须注意空表和非空表的界限。 如n=8,m=4时,若从第一个人,设每个人的编号依次为1,2,3,…开始报数,则得到的出列次序为4,8,5,2,1,3,7,6, 如下图所示,内层数字表示人的编号,每个编号外层的数字代表人出列的序号。 [程序实现] #include #include typedefstructnode {intnum; structnode*next; }linklist; linklist*creat(head,n)/*使n个人围成一圈,并给每个人标识号数*/ linklist*head; intn; {linklist*s,*p; inti; s=(linklist*)malloc(sizeof(linklist)); head=s; s->num=1; p=s; for(i=2;i<=n;i++) {s=(linklist*)malloc(sizeof(linklist)); s->num=i; p->next=s; p=s; } p->next=head; return(head); }/*creat*/ linklist*select(linklist*head,intm) {linklist*p,*q; inti,t; p=head;t=1; q=p;/*q为p的前趋指针*/ p=p->next; do { t=t+1;/*报一次数*/ if(t%m==0) {printf("%4d",p->num); q->next=p->next; free(p); p=q->next; } else{q=p; p=p->next; } }while(q! =p); head=p; printf("%4d",p->num); return(head); }/*select*/ main() {intn,m; linklist*head; printf("\ninputthetotalnumber: n="); scanf("%d",&n); printf("\ninputthenumbertocall: m="); scanf("%d",&m); head=creat(head,n); head=select(head,m); printf("\nthelastoneis: %d",head->num); }/*main*/ 思考题: 编程实现两个循环单链表的合并。 实验三栈、队列的实现及应用 一、实验目的 1、掌握栈和队列的顺序存储结构和链式存储结构,以便在实际背景下灵活运用。 2、掌握栈和队列的特点,即先进后出与先进先出的原
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 验证 实验 指导书