实验2 单链表应用

实验2 单链表应用

一、实验目的

1．熟悉单链表的存储结构和基本操作；

2．熟悉单循环链表的操作；

3．熟悉单链表的应用。

二、实验内容

1．将一个已知的单循环链表进行逆置运算，如（a₁,a₂,a₃,…,a_n)变为(a_n,a_n-1,…,a₂,a₁)。将算法转换为程序上机实现，并按照要求撰写实验报告。

 

三、实验指导

对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表。

所谓链表的逆置运算（或称为逆转运算）是指在不增加新结点的前提下，依次改变数据元素的逻辑关系，使得线性表（a₁,a₂,a₃,…,a_n)成为(a_n,a_n-1,…,a₂,a₁)。

本题采用的算法是：先建立一个带头结点的单循环链表，从头到尾扫描单链表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);
}