2链表拓展思路

循环链表

定义：单链表的末尾指向头结点

//初始化时next—>自己

头结点的数据域可以用来存储某些整个链表的属性来节省空间

双向链表

定义：有两个指针域和一个数据域，指针域指向上一个prior和下一个next

//插入函数思路
/*
先使新结点指向next，再使last的上一个指向这个，新节点的上一个指向prior，最后使next的上一个指向这个。
*/

//可以类似头结点设置尾结点，新增一个空间来节省时间

双向循环链表

定义：双向链表的末尾指向头结点

#include<stdio.h>
#include<stdlib.h>
//双向循环链表
typedef struct DoubleLink{
    struct DoubleLink * front;//前指针
    struct DoubleLink * next;//后指针
    int element;//数据
}List;

List *head;//头指针
List *end;//尾指针


//初始化
void InitList()
{
    head=(List*)malloc(sizeof(List));
    end=(List*)malloc(sizeof(List));
    
    head->next=end;
    end->front=head;
    head->front=NULL;
    end->next=NULL;
}

//头插法
void head_insert(int key)
{
    List* temp=(List*)malloc(sizeof(List));
    temp->element=key;
    temp->next=head->next;
    temp->front=head;
    head->next=temp;
    temp->next->front=temp;
}

//尾插法
void end_insert(int key)
{
    List* temp=(List*)malloc(sizeof(List));
    temp->element=key;
    temp->next=end;
    temp->front=end->front;
    end->front=temp;
    temp->front->next=temp;
}

//在某个数据后插入数据（头插带入部分代码）
void index_insert(int date,int key)
{
	int index=find(data);
    List* temp=head;
    if(index==-1)
    {
        head_insert(key);
        return;
    }
    for(int i=0;i<index;i++)
    {
		temp=temp->next;
    }
    List* new=(List*)malloc(sizeof(List));
    new->element=key;
    new->next=temp->next;
    new->front=temp;
    temp->next=new;
    new->next->front=new;
}

//删除代码
void delete(int key)
{
    int index=find(key);
    if(index==-1)
    {
        return;
	}
    List* temp=head;
    for(int i=0;i<index;i++)
    {
        temp=temp->next;
	}
    temp->front->next=temp->next;
    temp->next->front=temp->front;
    free(temp);
}

int find(int data)
{
    List*temp=head;
    int i=-1;
    while(temp!=end)
    {
        if(temp->element==data)
            break;
        temp=temp->next;
        i++;
    }
    return i;
}

发布于 2024-11-10