实验2 单链表应用
一、实验目的
1.熟悉单链表的存储结构和基本操作;
2.熟悉单循环链表的操作;
3.熟悉单链表的应用。
二、实验内容
1.将一个已知的单循环链表进行逆置运算,如(a1,a2,a3,…,an)变为(an,an-1,…,a2,a1)。将算法转换为程序上机实现,并按照要求撰写实验报告。
三、实验指导
对于单链表而言,最后一个结点的指针域是空指针,如果将该链表头指针置入该指针域,则使得链表头尾结点相连,就构成了单循环链表。对于单链表只能从头结点开始遍历整个链表,而对于单循环链表则可以从表中任意结点开始遍历整个链表。
所谓链表的逆置运算(或称为逆转运算)是指在不增加新结点的前提下,依次改变数据元素的逻辑关系,使得线性表(a1,a2,a3,…,an)成为(an,an-1,…,a2,a1)。
本题采用的算法是:先建立一个带头结点的单循环链表,从头到尾扫描单链表L,把p作为活动指针,沿着链表向前移动,每遇到一个新结点,就将此结点插入到头结点之后,直到p==L时,单循环链表倒置实现。q指向p前趋结点,r指向q的前趋结点。其中,q的next值为r,r的初值置为head。
四、实验要求
1.每个同学必须独立完成;
2.代码编写规范要求:程序中的开头部分必须对本程序的总体功能进行注释;程序中每个函数段必须要有注释说明该函数的功能或作用;
3.实验设计和源码撰写应在每次上机之前完成,上机时进行调试和修改、记录实验数据和结果;
4.实验报告的总结部分,应描述如下内容:
(1)单链表与顺序表区别的体会。
(2)本次实验过程的体会,是否自己独立完成?最大的困难是什么?自己准备如何解决这个困难?
5.提交实验报告。
参考实验代码:
#define NULL 0
#include<stdio.h>
#include<malloc.h>
typedef struct node
{
int num;
struct node *next;
}linklist;
void output(linklist *head) /*输出循环链表的信息*/
{
linklist *p;
p=head->next;
while(p!=head)
{
printf("%d ",p->num);
p=p->next;
}
printf("\n");
}
linklist *creat(int n) /*建立单循环链表*/
{
int k;
linklist *head, *r, *p;
p=(linklist *)malloc(sizeof(linklist));
head=p;
r=p;
p->next=p;
for(k=1;k<=n;k++)
{
p=(linklist *)malloc(sizeof(linklist));
p->num=k;
r->next=p;
r=p;
}
p->next=head;
return(head);
}
linklist *invert(linklist *head) /*逆置函数*/
{
linklist *p,*q,*r;
p=head->next;
q=head;
while(p!=head)
{
r=q;
q=p;
p=p->next;
q->next=r;
}
head->next=q;
return(head);
}
void main()
{
int n;
linklist *head;
printf("输入所建立的循环链表的结点个数:\n");
scanf("%d",&n);
head=creat(n);
printf("输出建立的单循环链表:\n");
output(head);
printf("现在进行逆置!\n");
head=invert(head);
printf("输出进行逆置运算后的单循环链表的结点信息!\n");
output(head);
}
分享到:
相关推荐
数据结构实验 单链表的应用 利用类实现单链表的应用
数据结构试验 单链表的基本操作及应用 源代码 下载
2.再从键盘输入顺序任意的5个整数,按有序插入的要求生成第二个有序单链表,将该链表输出显示。 3.将这两个有序单链表合并成一个有序单链表,要求使用两个单链表的原有空间进行合并,将生成的有序单链表输出显示。
实验报告有流程图,代码带注释及运行结果和应用算法实现,报告很全
数据结构实验报告:单链表的建立 1.实验目的 (1)了解数据的逻辑结构和数据的存储结构之间的区别与联系; (2)掌握线性表的链式表示和实现方法,特别是插入、删除操作。 (3)掌握运用C语言上机调试线性表的...
单链表操作 和 栈、队列的应用 基本要求:1)用前插法建立带表头结点的单链表; 2)在该链表中统计数据值为x的结点个数。 3)在该链表中值为k的结点前插入y结点,并删除k结点,如果没有值为k的结点则把y结点插在...
利用单链表实现电话本的模拟程序:定义单链表的数据类型,将头插法和尾插法、插入、删除、查找、修改、计数、逆置、输出等操作都定义成子函数的形式,最后在主函数中调用它,并将每一种操作前后的结果输出,以查看每...
科大版的数据结构代码 用于上机实验和单链表的应用 适用于初学者
洛阳理工学院实验报告 "系别 "计算机系 "班级 " "学号 " "姓名 " " "课程名称 "数据结构 "实验日期 "11.7 " "实验名称 "链表的基本操作 "成绩 " " "实验目的: " "熟悉掌握线性表链式存储结构,掌握与应用查找、插入...
1.编写算法,根据用户输入的字符数据...2.编写算法,实现在带有头结点的单链表中按序号查找的函数。 假设单链表中包含6个数据元素,测试数据: 1. 查找第0个. 2. 查找第1个. 3. 查找第2个. 4. 查找第6个. 5. 查找第7个.
大二实验作业 顺序表,单链表,顺序表应用,冒泡排序,折半查找 写在一个form窗口
针对单链表的建立以及赋予相关功能,实现信息的增删改查等,实验报告内容稍微欠缺,请自行修改
数据结构-基本算法-单链表(学生时代源码,调试可运行)
用单链表解决约瑟夫环问题,数据结构实验报告。约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人...
(2)设计实验:其主要内容是针对具体问题,应用某一个知识点,自己设计方案,并上机实现,目的是培养学生对数据结构的简单应用能力; (3)综合实验:其主要内容是针对具体问题,应用某几个知识点,自己设计方案,并...
数据结构实验报告 吴宗翰09013221 缪宇坤 实验题目1: 实验一单链表应用 编写算法,完成: 1、用单链表存储有理数N/M(N)的小数形式,若为无限循环小数,则用环链表表示; 2、判断N/M的小数形式中是否存在无限循环...
实验一 线性表的顺序存储实验 实验二 单链表实验 实验三 循环链表实验 实验四 栈、队列的实现及应用 实验五 串及数组的实验 实验六 查找 实验七 排序
实验一 单链表的定义和应用 实验要求: 1.用单链表存储结构定义线性表 2.实现单链表基本操作(5个基本操作:构造,销毁,插入,删除, 取指定数据元素) 3.用单链表实现两个集合的合并或者一元多项式的 实验二 栈...
创建单链表 输出单链表 单链表的查询 单链表的插入 删除
用C++编的用的是用单链表结构做的通讯录管理 课程设计,内附课程设计的实验报告!