双向链表的操作(C语言)

main函数部分:

#include <stdio.h>
#include "./23_doubleLinkList.h"
int main(int argc, const char *argv[])
{   
    doubleLinkList* head = create_doubleLinkList();
    insertHead_doubleLinkList(head,12);
    insertHead_doubleLinkList(head,21);
    insertHead_doubleLinkList(head,14);
    insertHead_doubleLinkList(head,16);
    
    insertTail_doubleLinkList(head,13);
    show_doubleLinkList(head);
    insertBypos_doubleLinkList(head,33,6);
    show_doubleLinkList(head);
    deleteHead_doubleLinkList(head);
    show_doubleLinkList(head);
    deleteTail_doubleLinkList(head);
    show_doubleLinkList(head);
    deleteBypos_doubleLinkList(head,2);
    show_doubleLinkList(head);                                 
    return 0;
}
                                                               
                                                               

功能函数:

#include<stdio.h>                                                                                                                                                                                                                            
#include <stdlib.h>                                                                                                                                                                                                                          
#include "./23_doubleLinkList.h"                                                                                                                                                                                                             
doubleLinkList* create_doubleLinkList()                                                                                                                                                                                                      
{                                                                                                                                                                                                                                            
    doubleLinkList* head = (doubleLinkList*)malloc(sizeof(doubleLinkList));                                                                                                                                                                  
    if(NULL==head)                                                                                                                                                                                                                           
    {                                                                                                                                                                                                                                        
        printf("头结点创建失败!n");                                                                                                                                                                                                        
        return NULL;                                                                                                                                                                                                                         
    }                                                                                                                                                                                                                                        
    head->text.len=0;                                                                                                                                                                                                                        
    head->next=head->prev=NULL;                                                                                                                                                                                                              
    return head;                                                                                                                                                                                                                             
}                                                                                                                                                                                                                                            
//判断链表是否为空                                                                                                                                                                                                                           
int isEmpty(doubleLinkList* head)                                                                                                                                                                                                            
{                                                                                                                                                                                                                                            
    return head->next==NULL?1:0;                                                                                                                                                                                                             
}                                                                                                                                                                                                                                            
//头插                                                                                                                                                                                                                                       
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=temp->prev=NULL;                                                                                                                                                                                                              
    //插入操作                                                                                                                                                                                                                               
    //需分情况考虑该链表是否有元素,以免出现段错误                                                                                                                                                                                           
        if(head->next!=NULL)                                                                                                                                                                                                                 
    {                                                                                                                                                                                                                                        
        temp->next = head->next;                                                                                                                                                                                                             
        head->next=temp;                                                                                                                                                                                                                     
        temp->prev=head;                                                                                                                                                                                                                     
        temp->next->prev=temp;                                                                                                                                                                                                               
    }else                                                                                                                                                                                                                                    
    {                                                                                                                                                                                                                                        
        temp->next = head->next;                                                                                                                                                                                                             
        head->next=temp;                                                                                                                                                                                                                     
        temp->prev=head;                                                                                                                                                                                                                     
    }                                                                                                                                                                                                                                        
    head->text.len++;                                                                                                                                                                                                                        
    return;                                                                                                                                                                                                                                  
                                                                                                                                                                                                                                             
}                                                                                                                                                                                                                                            
//尾插                                                                                                                                                                                                                                       
void insertTail_doubleLinkList(doubleLinkList* head,datatype num)                                                                                                                                                                            
{                                                                                                                                                                                                                                            
    //定义一个新的结点                                                                                                                                                                                                                       
    doubleLinkList* temp=(doubleLinkList*)malloc(sizeof(doubleLinkList));                                                                                                                                                                    
    if(NULL == temp)                                                                                                                                                                                                                         
    {                                                                                                                                                                                                                                        
        printf("头结点创建失败!n");                                                                                                                                                                                                        
        return;                                                                                                                                                                                                                              
                                                                                                                                                                                                                                             
    }                                                                                                                                                                                                                                        
    temp->text.data=num;                                                                                                                                                                                                                     
    temp->next=temp->prev=NULL;                                                                                                                                                                                                              
    //找到尾部的结点,p就是原双向链表的尾部结点                                                                                                                                                                                              
    doubleLinkList* p=head;                                                                                                                                                                                                                  
    while(p->next!=NULL)                                                                                                                                                                                                                     
    {                                                                                                                                                                                                                                        
        p=p->next;                                                                                                                                                                                                                           
    }                                                                                                                                                                                                                                        
    p->next=temp;                                                                                                                                                                                                                            
    temp->next=NULL;                                                                                                                                                                                                                         
    temp->prev=p;                                                                                                                                                                                                                            
    head->text.len++;                                                                                                                                                                                                                        
    return;                                                                                                                                                                                                                                  
}                                                                                                                                                                                                                                            
//按位置插入                                                                                                                                                                                                                                 
void insertBypos_doubleLinkList(doubleLinkList* head,datatype num,int pos)                                                                                                                                                                   
{                                                                                                                                                                                                                                            
    if(pos<1 || pos>head->text.len+1)                                                                                                                                                                                                        
    {                                                                                                                                                                                                                                        
        printf("输入的位置%d不合法!n",pos);                                                                                                                                                                                                
    }                                                                                                                                                                                                                                        
    //定义一个新的结点                                                                                                                                                                                                                       
    doubleLinkList* temp=(doubleLinkList*)malloc(sizeof(doubleLinkList));                                                                                                                                                                    
    if(NULL == temp)                                                                                                                                                                                                                         
    {                                                                                                                                                                                                                                        
        printf("头结点创建失败!n");                                                                                                                                                                                                        
        return;                                                                                                                                                                                                                              
                                                                                                                                                                                                                                             
    }                                                                                                                                                                                                                                        
    temp->text.data=num;                                                                                                                                                                                                                     
    temp->next=temp->prev=NULL;                                                                                                                                                                                                              
    //找到要插入位置的前一个`结点                                                                                                                                                                                                            
    doubleLinkList* p=head;                                                                                                                                                                                                                  
    int i;                                                                                                                                                                                                                                   
    for(i=0;i<pos-1;i++)                                                                                                                                                                                                                     
    {                                                                                                                                                                                                                                        
        p=p->next;                                                                                                                                                                                                                           
    }                                                                                                                                                                                                                                        
    temp->next=p->next;                                                                                                                                                                                                                      
    p->next=temp;                                                                                                                                                                                                                            
    temp->prev=p;                                                                                                                                                                                                                            
    if(temp->next!=NULL)                                                                                                                                                                                                                     
    temp->next->prev=temp;                                                                                                                                                                                                                   
    head->text.len++;                                                                                                                                                                                                                        
    return;                                                                                                                                                                                                                                  
}                                                                                                                                                                                                                                            
//头删                                                                                                                                                                                                                                       
void deleteHead_doubleLinkList(doubleLinkList* head)                                                                                                                                                                                         
{                                                                                                                                                                                                                                            
    if(head->next==NULL)                                                                                                                                                                                                                     
    {                                                                                                                                                                                                                                        
        printf("链表为空!n");                                                                                                                                                                                                              
        return;                                                                                                                                                                                                                              
    }                                                                                                                                                                                                                                        
    //定义一个指针指向要删除的结点方便后续释放                                                                                                                                                                                               
    doubleLinkList* temp;                                                                                                                                                                                                                    
    temp=head->next;                                                                                                                                                                                                                         
                                                                                                                                                                                                                                             
                                                                                                                                                                                                                                             
    head->next=temp->next;                                                                                                                                                                                                                   
    //需分情况考虑该结点是否为链表最后一个结点,以免出现段错误                                                                                                                                                                               
    if(temp->next!=NULL)                                                                                                                                                                                                                     
    {                                                                                                                                                                                                                                        
        temp->next->prev=head;                                                                                                                                                                                                               
    }                                                                                                                                                                                                                                        
    free(temp);                                                                                                                                                                                                                              
    head->text.len--;                                                                                                                                                                                                                        
    return;                                                                                                                                                                                                                                  
}                                                                                                                                                                                                                                            
//尾删                                                                                                                                                                                                                                       
void deleteTail_doubleLinkList(doubleLinkList* head)                                                                                                                                                                                         
{                                                                                                                                                                                                                                            
    if(head->next==NULL)                                                                                                                                                                                                                     
    {                                                                                                                                                                                                                                        
        printf("链表为空!n");                                                                                                                                                                                                              
        return;                                                                                                                                                                                                                              
    }                                                                                                                                                                                                                                        
    //定义一个指针指向要删除的结点方便后续释放                                                                                                                                                                                               
    doubleLinkList* p=head;                                                                                                                                                                                                                  
    while(p->next!=NULL)                                                                                                                                                                                                                     
    {                                                                                                                                                                                                                                        
        p=p->next;                                                                                                                                                                                                                           
    }                                                                                                                                                                                                                                        
    p->prev->next=NULL;                                                                                                                                                                                                                      
    free(p);                                                                                                                                                                                                                                 
    head->text.len--;                                                                                                                                                                                                                        
    return;                                                                                                                                                                                                                                  
                                                                                                                                                                                                                                             
}                                                                                                                                                                                                                                            
//按位置删除                                                                                                                                                                                                                                 
void deleteBypos_doubleLinkList(doubleLinkList* head,int pos)                                                                                                                                                                                
{                                                                                                                                                                                                                                            
    if(head->next==NULL)                                                                                                                                                                                                                     
    {                                                                                                                                                                                                                                        
        printf("链表为空!n");                                                                                                                                                                                                              
        return;                                                                                                                                                                                                                              
    }                                                                                                                                                                                                                                        
    //判断位置是否合法                                                                                                                                                                                                                       
    if(pos<1 || pos>head->text.len)                                                                                                                                                                                                          
    {                                                                                                                                                                                                                                        
        printf("输入的位置%d不合法!n",pos);                                                                                                                                                                                                
    }                                                                                                                                                                                                                                        
    //定义一个指针指向要删除的结点方便后续释放                                                                                                                                                                                               
    doubleLinkList* p=head;                                                                                                                                                                                                                  
    int i;                                                                                                                                                                                                                                   
    for(i=0;i<pos;i++)                                                                                                                                                                                                                       
    {                                                                                                                                                                                                                                        
        p=p->next;                                                                                                                                                                                                                           
    }                                                                                                                                                                                                                                        
    //p就是要删除的结点                                                                                                                                                                                                                      
    p->prev->next=p->next;                                                                                                                                                                                                                   
    //当结点不为最后一个节点时,需要将该结点的后一位的前驱指针指向上一个结点                                                                                                                                                                 
    //当结点为最后一个节点则不需要,若不分情况考虑则会出现段错误;                                                                                                                                                                           
    if(p->next!=NULL)                                                                                                                                                                                                                        
    {                                                                                                                                                                                                                                        
    p->next->prev=p->prev;                                                                                                                                                                                                                   
    }                                                                                                                                                                                                                                        
    free(p);                                                                                                                                                                                                                                 
    head->text.len--;                                                                                                                                                                                                                        
}                                                                                                                                                                                                                                            
//遍历                                                                                                                                                                                                                                       
void show_doubleLinkList(doubleLinkList* head)                                                                                                                                                                                               
{                                                                                                                                                                                                                                            
    doubleLinkList* p=head;                                                                                                                                                                                                                  
    if(isEmpty(head))                                                                                                                                                                                                                        
    {                                                                                                                                                                                                                                        
        printf("链表为空!n");                                                                                                                                                                                                              
    }                                                                                                                                                                                                                                        
    while(p->next!=NULL)                                                                                                                                                                                                                     
    {                                                                                                                                                                                                                                        
            p=p->next;                                                                                                                                                                                                                       
                                                                                                                                                                                                                                             
        printf("%d ",p->text.data);                                                                                                                                                                                                          
    }                                                                                                                                                                                                                                        
    printf("n");                                                                                                                                                                                                                            
    return;                                                                                                                                                                                                                                  
}                                                                                                                                                                                                                                            
                                                                                                                                                                                                                                             
                                                                                                                                                                                                                                             
                                                                                                                                                                                                                                             

头文件:

                                                                                 
#ifndef __doubleLinkList_H__
#define __doubleLinkList_H__
typedef int datatype;
union msg{    //若数据的类型也为int,则不需要这个联合体
datatype data;
int len;       //放头结点,记录链表长度
};
typedef struct node{
    union msg text;
    struct node* next; //指针,由于指针指向这一整个节点,所以类型为struct node*
    struct node* prev; 
}doubleLinkList; 

doubleLinkList* create_doubleLinkList();

void insertHead_doubleLinkList(doubleLinkList* head,datatype num);

void insertTail_doubleLinkList(doubleLinkList* head,datatype num);

void deleteBypos_doubleLinkList(doubleLinkList* head,int pos);
void deleteTail_doubleLinkList(doubleLinkList* head);
void deleteHead_doubleLinkList(doubleLinkList* head);
void insertBypos_doubleLinkList(doubleLinkList* head,datatype num,int pos);
void show_doubleLinkList(doubleLinkList* head); 
#endif                                                                                       
                                                                                             

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>