数据结构之链表篇 单链表 循环链表 双向链表

1.链表

　　链表是线性表的一种，由一系列节点（结点）组成，每个节点包含一个数据域和一个指向下一个节点的指针域。链表结构可以克服数组需要预先知道数据大小的缺点，而且插入和删除元素很方便，但是失去数组随机读取的优点。链表有很多种不同类型：单向链表，双向链表和循环链表。

在链表中第一个节点叫头节点(如果有头节点）头节点不存放有效信息，是为了方便链表的删除和插入操作，第一个有效节点叫首节点，最后一个节点叫尾节点。

2.单链表的操作

　　链表的操作一般有创建链表，插入节点，删除节点，遍历链表。插入节点的方法有头插法和尾插法，头插法是在头部插入，尾插法是在尾部插入。

　　下面以一个带头节点，采用尾插法的链表说明链表的各种操作。

#include<stdio.h>
#include<stdlib.h>
//单链表


//节点结构体
typedef struct node
{
    int value;//数据域
    struct node*next;//指针域
}Node;

Node*createList();//创建链表并且返回头节点指针
void deleteNode(Node*head);//删除节点
void insertNode(Node*head);//插入节点
void travelList(Node*head);//遍历链表

int main()
{
    Node*head=createList();
    travelList(head);
    insertNode(head);
    travelList(head);
    deleteNode(head);
    travelList(head);
    return 0;
}
//创建链表，返回头节点指针
Node*createList()
{
    //采用尾插法
    Node*head;//头节点
    Node*tail;//尾节点
    Node*temp=NULL;
    int i,value,size;
    head=(Node*)malloc(sizeof(Node));//头节点
    head->value=0;
    head->next=NULL;
    tail=head;
    printf("输入节点个数: ");
    scanf("%d",&size);
    printf("输入各个节点的值: ");

    for(i=0;i<size;i++)
    {
        scanf("%d",&value);
        temp=(Node*)malloc(sizeof(Node));
        temp->value=value;
        tail->next=temp;//让尾节点的指针域指向新创建的节点
        tail=temp;//尾节点改为新创建的节点
        tail->next=NULL;//让尾节点的指针域为空
    }
    return head;
}
//遍历链表
void travelList(Node*head)
{
    while(head->next!=NULL)
    {
        printf("%d\n",head->next->value);
        head=head->next;
    }
}
//插入节点
void insertNode(Node*head)
{
    int value;
    int position;
    int pos=0;
    Node*pre=NULL;//用来保存要插入节点的前一个节点
    Node*newNode;
    printf("输入要插入节点的值: ");
    scanf("%d",&value);
    printf("要插入的位置: ");
    scanf("%d",&position);
    while(head!=NULL)
    {
        pos++;
        pre=head;
        head=head->next;
        if(pos==position)
        {
            newNode=(Node*)malloc(sizeof(Node));
            newNode->value=value;
            newNode->next=pre->next;
            pre->next=newNode;
        }
    }
}
//删除节点
void deleteNode(Node*head)
{
    int value;
    Node*pre=head;
    Node*current=head->next;
    printf("输入要删除节点的值: ");
    scanf("%d",&value);
    while(current!=NULL)
    {
        if(current->value==value)
        {
            pre->next=current->next;
            free(current);//释放空间
            break;
        }
        pre=current;
        current=current->next;
    }
}

3.循环链表

　　循环链表就是让尾节点的指针域不再是NULL,而是指向头节点从而形成一个环。循环链表与单链表的操作没有多少差别，只是判断链表是否空应该是

　　tail->next==head。

4.双向链表

　　双向链表的每一个节点都有两个指针域，一个前驱指针，指向前一个节点，头节点的前驱指针为NULL,一个后继指针，指向后一个节点，尾节点的后继指针为NULL。双向链表可以从任一个节点开始访问到前后节点，不像单链表只能向前。代码如下。

#include<stdio.h>
#include<stdlib.h>
//双向链表
typedef struct node
{
    int value;//数据域
    struct node* lNext;//前驱指针
    struct node* rNext;//后继指针
}Node;

Node*createList();//创建链表并且返回头节点指针
void deleteNode(Node*head);//删除节点
void insertNode(Node*head);//插入节点
void travelList(Node*head);//遍历链表

int main()
{

    Node*head=createList();
    travelList(head);
    insertNode(head);
    travelList(head);
    deleteNode(head);
    travelList(head);
    return 0;
}

Node*createList()
{
    Node*head,*tail,*temp;
    int num,value,i;
    head=(Node*)malloc(sizeof(Node));//头节点
    head->value=0;
    head->lNext=NULL;
    head->rNext=NULL;
    tail=head;
    printf("输入节点个数: ");
    scanf("%d",&num);
    printf("输入各个节点的值: ");
    for(i=0;i<num;i++)
    {
        scanf("%d",&value);
        temp=(Node*)malloc(sizeof(Node));
        temp->value=value;
        temp->lNext=tail;
        tail->rNext=temp;
        tail=temp;
        tail->rNext=NULL;
    }
    return head;
}


void deleteNode(Node*head)//删除节点
{

    int value;
    Node*pre;
    Node*current=head->rNext;
    printf("输入要删除节点的值: ");
    scanf("%d",&value);
    pre=head;
    while(current!=NULL)
    {
        if(current->value==value)
        {
            pre->rNext=current->rNext;//上一个节点指向下一个节点
            current->rNext->lNext=pre;//下一个节点的前驱指针指向上一个节点
            free(current);//删除该节点
        }
        pre=current;
        current=current->rNext;
    }
}

void insertNode(Node*head)//插入节点
{
    Node*pre,*temp;
    int value,pos;
    int num=0;
    printf("输入要插入的值: ");
    scanf("%d",&value);
    printf("输入要插入的位置: ");
    scanf("%d",&pos);
    while(head!=NULL)
    {
        num++;
        pre=head;//保存上一个节点
        head=head->rNext;//当前节点
        if(pos==num)
        {
            temp=(Node*)malloc(sizeof(Node));
            temp->value=value;
            temp->lNext=pre;
            temp->rNext=head;
            head->lNext=temp;
            pre->rNext=temp;
        }
    }
}

void travelList(Node*head)//遍历链表
{
    while(head->rNext!=NULL)
    {
        printf("%d\n",head->rNext->value);
        head=head->rNext;
    }
}