实验2 单链表应用
实验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);}?
?