[线性链表的建立与应用实验报告]链表实验报告

来源:培训心得 发布时间:2019-10-14 08:39:06 点击:

实 验 报 告

课程名称 数据结构实验

实验名称 线性链表的建立与应用 2

实验类型 设计型

实验地点 实验日期

指导教师

专 业

班 级

学 号

姓 名

成 绩

辽宁石油化工大学计算机与通信工程学院

实验二

一 实验目的:

了解并掌握线性表在采取链式存储时的逻辑关系与物理存储关系的特点和计算特性,掌握线性链表的各种运算方法。

二 实验内容:

实现单向链表的初始化、查找、删除、添加、排序、查找、合并、逆转、复制等操作。要求程序能够循环执行

三 实验原理:

关于单链表

链表是通过一组任意的存储单元来存储线性表中的数据元素的,为建立起数据元素之间的线性关系,对每个数据元素ai,除了存放数据元素的自身的信息 ai 之外,还需要和ai一

datanext

单链表结点结构

... 链表示意图

起存放其后继 ai+1 所在的存贮单元的地址,这两部分信息组成一个“结点”,存放数据元素信息的称为数据域,存放其后继地址的称为指针域。因此n个元素的线性表通过每个结点的指针域拉成了一个“链子”,称之为链表。因为每个结点中只有一个指向后继的指针,所以称其为单链表。

单链表上基本运算的实现

线性链表的创建:创建过程实际上是链表结点的申请和连接的过程。向系统申请内存单元,输入用户数据,将结点加入到链表中,连接前后件,明确关系后添加下一个结点。

线性链表的删除:选定要删除的结点,将该结点前件的指针域数据修改为后件的物理地址值,释放该节点占用的内存空间。

线性链表的查找:给定查找条件,从链表头开始,顺延向后查找,当找到符合条件的结点时,返回该结点的地址值。

线性链表的编辑:给定查找条件,查找到符合条件的结点后,修改相应的用户数据,但不能改变该结点的指针值。

线性链表的排序:按照指定的用户数据用指定的的排序要求(升序或降序)对链表的逻辑结构进行重组,重组的过程中,只改变逻辑结构,而不是物理结构,也不改变结点的数据。

线性链表的合并:将一个链表的头结点连接到另一个链表的为结点后作为其后件。 线性链表的逆转:将链表按照顺序反转,即尾结点变为头结点,头结点变为尾结点。

四 实验步骤

1 进入Turbo C2.0,新建一个文件。

2 输入程序,程序要求使用子函数进行组织。

3 将源程序保存到指定文件夹“D:\学生姓名”。

4 按F9调试,纠正语法错误。

5按Ctrl+F9运行,调试逻辑错误。

6 按Alt+F5查看结果。

五、实验截图:

六、程序源代码:

#include "stdlib.h"

#include "stdio.h"

struct node

{

int d;

struct node *next;

};

chushicst(head,x) /***********循环链表初始化***************/

int x;struct node *head;

{

struct node *q,*p;

q=(struct node *)malloc(sizeof(struct node));

p=head;

q->d=x;

q->next=head;

while(p->next!=head)

p=p->next;

p->next=q;

return;

}

out(head) /************输出循环链表内元素*****************/

struct node *head;

{

struct node *p;

p=head;

if(p->next==head)

printf("没有元素");

while(p->next!=head)

{

printf("%d ",(p->next)->d);

p=p->next;

}

printf("\n\n");

return;

}

struct node *lookcst(head,x) /*********寻找包含元素x的前一个节点***************/

int x;struct node *head;

{

struct node *p;

p=head;

while((p->next!=head)&&(((p->next)->d)!=x))

p=p->next;

if(p->next==head)

printf("没有找到指定元素!!!\n\n");

return(p);

}

inscst(head,x,b)

int x,b;

struct node *head; /************在指定元素x前插入新元素************/ {

struct node *p,*q;

p=(struct node *)malloc(sizeof(struct node));

p->d=b;

q=lookcst(head,x);

if(q->next==head)

{printf("不能进行插入操作!!!\n\n");return;}

p->next=q->next;q->next=p;

return;

}

delcst(head,x) /***********删除指定元素x ****************/ int x;

struct node *head;

{

struct node *p,*q;

q=lookcst(head,x);

if(q->next==head)

{printf("不能进行删除操作!!\n\n");return;}

p=q->next;q->next=p->next;

free(p);

delcst(head,x);

return;

}

mgcst2(head1,head2) /*************合并两个循环链表*************/ struct node *head1,*head2;

{

struct node *p,*q;

p=head1;

q=head2;

while(p->next!=head1)

p=p->next;

while(q->next!=head2)

q=q->next;

p->next=head2->next;

q->next=head1;

head2->next=head2;

return;

}

fencst(head1,head2,x) /*****************分解一个循环链表******/ int x;struct node *head1,*head2;

{

struct node *p,*q;

int i=0;

p=head1;

q=head1;

while(q->next!=head1)

q=q->next;

while((i!=x)&&p->next!=head1)

{p=p->next;i++;}

if(x

head2->next=p->next;

q->next=head2;

p->next=head1;

return;

}

invcst(head) /******************逆转循环链表********************/ struct node *head;

{

struct node *p,*q,*r;

if(head->next==head) return;

p=head->next;q=p->next;

p->next=head;

while (q!=head)

{

r=q->next;q->next=p;

p=q;q=r;

}

head->next=p;

return;

}

copycst(head1,head2) /** **********复制循环链表***************/

struct node *head1,*head2;

{ int x;

struct node *p;

head2->next=head2;

p=head1;

while(p->next!=head1)

{

p=p->next;

x=p->d;

chushicst(head2,x);

}

return;

}

sortcst(head) /*************循环链表的排序***************/

struct node *head;

{

struct node *p,*q;

int k,i=0;

p=head;

q=p->next;

while(p->next!=head)

{ if(p->d>q->d)

{ k=p->d;

p->d=q->d;

q->d=k;

i++;

}

p=p->next;

q=q->next;

}

p=head;

q=p->next;

while(i!=0)

{ i=0;

while(p->next!=head)

{

if(p->d>q->d)

{ k=p->d;

p->d=q->d;

q->d=k;

i++;

}

p=p->next;

q=q->next;

}

p=head;

q=p->next;

}

return;

}

chacst(head,ss) /**************循环链表的定值查找*****************/ int ss;struct node *head;

{ int i=0;

struct node *p;

p=head;

printf("输出查找元素的位置: ");

while((p->next!=head)&&(((p->next)->d)!=ss))

{ p=p->next;i++;}

if((p->next)->d!=ss) {printf("该循环链表中没有此元素!!\n\n");return;} else printf("%d ",i+1);

printf("\n\n");

return;

}

chacst1(head,x) /************循环链表的定次查找****************/ int x;struct node *head;

{

struct node *p;

int i=0;

p=head;

while((p->next!=head)&&(i!=x))

{ p=p->next; i++; }

if(i

{printf("该循环链表中没有此位置!!!\n\n");return;}

printf("输出查找位置的元素: ");

printf("%d",p->d);

printf("\n\n");

return;

}

main()

{

int i,j,x,b,xx,y,yy,m,n;

struct node *head1,*head2,*head3,*q;

head1=(struct node *)malloc(sizeof(struct node));

head1->next=head1;

head2=(struct node *)malloc(sizeof(struct node));

head2->next=head2;

printf("\n");

printf("输入0, 退出\n");

printf("输入1, 链表1赋初值\n");

printf("输入2, 链表2赋初值\n");

printf("输入3, 在指定元素x前插入元素b\n");

printf("输入4, 删除指定元素\n");

printf("输入5, 合并 \n");

printf("输入6, 分解 \n");

printf("输入7, 逆转 \n");

printf("输入8, 复制\n");

printf("输入9, 排序 \n");

printf("输入10, 按位查找\n");

printf("输入0-10: ");

scanf("%d",&y);

printf("\n");

for(;y!=0;)

{

switch(y)

{

case 1:

{

printf("输入初始元素个数: ");

scanf("%d",&i);

for(j=1;j

{

printf("输入第%d个元素 ",j);

scanf("%d",&x);

chushicst(head1,x);

}

printf("输出循环链表1内元素: ");

out(head1);

printf("输出循环链表2内元素: ");

out(head2);

break;

}

case 2: {

printf("输入初始元素个数: ");

scanf("%d",&i);

for(j=1;j

{

printf("输入第%d个元素 ",j);

scanf("%d",&x);

chushicst(head2,x);

}

printf("输出循环链表1内元素: ");

out(head1);

printf("输出循环链表2内元素: ");

out(head2);

break; } case 3: {printf("请输入指定元素x: "); scanf("%d",&x); printf("请输入插入元素b: ");

scanf("%d",&b);

printf("\n");

inscst(head1,x,b);

printf("输出循环链表1内元素: ");

out(head1);

printf("输出循环链表2内元素: ");

out(head2);

break;

}

case 4:

{

printf("请输入要删除的指定元素xx: ");

scanf("%d",&xx);

printf("\n\n");

delcst(head1,xx);

printf("输出循环链表1内元素: ");

out(head1);

printf("输出循环链表2内元素: ");

out(head2);

break;

}

case 5:

{ if(head2->next!=head2)

mgcst2(head1,head2);

else

printf("循环链表2为空\n\n");

printf("输出循环链表1内元素: ");

out(head1);

printf("输出循环链表2内元素: ");

out(head2);

break;

}

case 6:

{

printf("请输入要拆分的位置: ");

scanf("%d",&x);

printf("\n"); fencst(head1,head2,x); printf("输出循环链表1内元素: "); out(head1); printf("输出循环链表2内元素: ");

out(head2);

break;

}

case 7:

{

invcst(head1);

printf("输出循环链表1内元素: ");

out(head1);

break;

}

case 8:

{

copycst(head1,head2);

printf("输出循环链表1内元素: ");

out(head1);

printf("输出循环链表2内元素: ");

out(head2);

break;

}

case 9:

{

sortcst(head1);

printf("输出循环链表1内元素: ");

out(head1);

break;

}

case 10:

{

printf("输入0,不执行操作!\n");

printf("输入1,循环链表的定次查找\n");

printf("输入2,循环链表的定值查找\n");

printf("请输入0-2: ");

scanf("%d",&n);

for(;n!=0;)

{ switch(n)

{ case 1:

{

printf("请输入要查找的位置: ");

scanf("%d",&yy);

printf("\n");

printf("输出循环链表1内元素: ");

out(head1);

chacst1(head1,yy);

break;

}

case 2:

{

printf("请输入要查找的元素: ");

scanf("%d",&m);

printf("输出循环链表1内元素: ");

out(head1);

chacst(head1,m);

break;

}

default:break;

}

printf("输入"0",退出查找!\n");

printf("输入"1",循环链表的定次查找\n");

printf("输入"2",循环链表的定值查找\n");

printf("请输入"0"-"2": ");

scanf("%d",&n);

}

printf("\n");

}

default:break;

}

printf("输入0, 退出\n");

printf("输入1, 链表1赋初值\n");

printf("输入2, 链表2赋初值\n");

printf("输入3, 在指定元素x前插入元素b\n");

printf("输入4, 删除指定元素\n");

printf("输入5, 合并 \n");

printf("输入6, 分解 \n");

printf("输入7, 逆转 \n");

printf("输入8, 复制\n");

printf("输入9, 排序 \n");

printf("输入10, 按位查找\n");

printf("输入0-10: ");

scanf("%d",&y);

}

printf("\n"); } free(head1); free(head2);

七、实验中应注意的问题与思考题:

1 在处理过程中保证数据结构的逻辑完整性。链表的实现最好采用带头结点的单链表,可以简化链表的处理过程,采用单链表会涉及“指向指针的指针”容易造成逻辑上的混乱,技术上比较难以实现。

2 在对结点进行查找时,可能会出现多个查询结果,应该如何处理?

答:查找时多加一层循环,循环条件为控制变量的next为head为止。

3 为什么删除结点的时候要释放内存空间?

答:防止内存泄漏。

4 对各个功能模块采用独立编制子函数,增强程序的可执行性、可移植性和可读性。增加情报信息量,对实际应用中可能发生的情况考虑周全,对非法情形要提出适当的处理方案

推荐访问:线性 链表 建立 实验 报告 图书管理链表实现实验报告 c语言线性链表实验小结
上一篇:超声波测距器的设计|超声波测距原理与实现
下一篇:最后一页

Copyright @ 2013 - 2018 三十范文网_讲话发言_党团范文_规章制度 All Rights Reserved

三十范文网_讲话发言_党团范文_规章制度 版权所有 湘ICP备11019447号-75