【数据结构】双向链表

一、main函数

#include <stdio.h>
#include "./3.doublelinklist.h"
int main(int argc, const char *argv[])
{
    doublelinklist* head = creatr_doublelinklist();

    insertHead_doublelinklist(head,999);
    insertHead_doublelinklist(head,888);
    insertHead_doublelinklist(head,777);
    insertHead_doublelinklist(head,666);
    insertHead_doublelinklist(head,555);
    insertHead_doublelinklist(head,444);
    showdoublelinklist(head);

    insertEnd_doublelinklist(head,123);
    insertEnd_doublelinklist(head,456);
    insertEnd_doublelinklist(head,789);
    showdoublelinklist(head);

    delHead_doublelinklist(head);
    showdoublelinklist(head);

    delEnd_doublelinklist(head);
    showdoublelinklist(head);

    insertByindex_doublelinklist(head,3,111);
    insertByindex_doublelinklist(head,20,99);
    showdoublelinklist(head);
                                                                                 
    delByindex_doublelinklist(head,2);
    delByindex_doublelinklist(head,20);
    showdoublelinklist(head);
    return 0;
}
                                                                                 

二、功能函数

#include <stdio.h>
#include <stdlib.h>
#include "./3.doublelinklist.h"
doublelinklist* creatr_doublelinklist()
{
    doublelinklist*head = (doublelinklist*)malloc(sizeof(doublelinklist));
    if(NULL == head)
    {
        printf("结点创建失败，双向链表申请失败\n");
        return NULL;
    }
    head->next = NULL;
    head->prev = NULL;
    head->text.len=0;

    return head;
}

//判空
int isEmpty_doublelinklist(doublelinklist*head)
{
    return head->next == NULL?1:0;
}

//遍历
void showdoublelinklist(doublelinklist*head)
{                                                                                                
    doublelinklist*p = head;
    while(p->next != NULL )
    {
        p=p->next;
        printf("%d ",p->text.data);
    }
    printf("\n");
    return ;
}

//头插法
void insertHead_doublelinklist(doublelinklist*head,dataType num)
{
    doublelinklist* temp = (doublelinklist*)malloc(sizeof(doublelinklist));
    if(NULL == temp)                                                                                             
    {
        printf("结点创建失败，头插失败\n");
        return ;
    }
    temp->text.data = num;
    temp->next = NULL;
    temp->prev = NULL;

    if(isEmpty_doublelinklist(head) == 1)
    {
        temp->next = head->next;
        head->next= temp;

        temp->prev = head;

        return ;
    }
    else
    {
        temp->next = head->next;
        head->next = temp;

        temp->next->prev = temp;
        temp->prev = head;
    }
    head->text.len++;
    return ;
}

//尾插法
void insertEnd_doublelinklist(doublelinklist*head,dataType num)
{
    doublelinklist* temp = (doublelinklist*)malloc(sizeof(doublelinklist));
    if(NULL == temp)
    {
        printf("结点创建失败，尾插失败\n");
        return ;
    }
    temp->text.data = num;
    temp->next = NULL;                                                                        
    temp->prev = NULL;

    doublelinklist* p =head;
    while(p->next != NULL)
    {
        p=p->next;
    }
    temp->next = p->next;
    p->next = temp;
    temp->prev = p;

    head->text.len++;
    return ;

}

 //头删法
 void delHead_doublelinklist(doublelinklist*head)
 {
     if(isEmpty_doublelinklist(head))
     {
         printf("双向链表为空，头删失败\n");
         return;
     }
     doublelinklist* temp = head->next;
     if(NULL == temp->next)
     {
         head->next= NULL;
     }
     else
     {
     head->next=temp->next;
     temp->next->prev=head;
     }
     free(temp);
     head->text.len--;
     return;
 }
 
 //尾删法
 void delEnd_doublelinklist(doublelinklist*head)
 {
     if(isEmpty_doublelinklist(head))
     {
         printf("双向链表为空，尾删失败\n");
         return;
     }
     doublelinklist*temp;
     doublelinklist*p=head;
     while(p->next->next != NULL)
     {
         p=p->next;
     }
     temp=p->next;
     p->next=NULL;
     free(temp);
     head->text.len--;
     return;
 }
 
//按位置插入
void insertByindex_doublelinklist(doublelinklist*head,int index,dataType num)
{
    doublelinklist* temp = (doublelinklist*)malloc(sizeof(doublelinklist));
    if(NULL == temp)
    {
        printf("结点创建失败，插入失败\n");
        return ;
    }
    temp->text.data = num;
    temp->next = NULL;
    temp->prev = NULL;

    if(index<1 || index >head->text.len+1)
    {
        printf("插入位置非法\n");
        return ;
    }                                                                                                    
    doublelinklist* p=head;
    int i;
    for(i=1;i<index;i++)
    {
        p=p->next;
    }
    if(p->next != NULL)
    {
        temp->next = p->next;
        p->next = temp;

        temp->next->prev = temp;
        temp->prev = p;
    }
    else
    {
        temp->next = NULL;
        p->next = temp;
        temp->prev = p;
    }
    head->text.len++;
    return ;
}

//按位置删除
void delByindex_doublelinklist(doublelinklist*head,int index)
{
    if(isEmpty_doublelinklist(head))
    {
        printf("双向链表为空，删除失败\n");
        return;
    }

    if(index<1 || index >head->text.len+1)
    {
        printf("选择位置非法\n");
        return ;
    }

    doublelinklist*p=head;
    for(int i=1;i<index;i++)
    {
        p=p->next;
    }
    doublelinklist*temp = p->next;
    p->next = p->next->next;
    temp->next->prev = p;
    free(temp);
    head->text.len--;
    return;

}

三、头文件

#ifndef __doublelink_H__                                   
#define __doublelink_H__

typedef int dataType;

union msg{
    dataType data;
    int len;
};

typedef struct node{
    union msg text;
    struct node* next;
    struct node* prev;
}doublelinklist;

doublelinklist* creatr_doublelinklist();
void showdoublelinklist(doublelinklist*head);
void insertHead_doublelinklist(doublelinklist*head,dataType num);
void insertEnd_doublelinklist(doublelinklist*head,dataType num);
void insertByindex_doublelinklist(doublelinklist*head,int index,dataType num);
void delHead_doublelinklist(doublelinklist*head);
void delEnd_doublelinklist(doublelinklist*head);
void delByindex_doublelinklist(doublelinklist*head,int index);


#endif                                                                                           
                                                                                                 
                                                                                                 
                                                                                                 
                                                                                                 

四、运行结果