欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

链表的基本操作

程序员文章站 2024-02-19 22:24:40
...

链表

本文中主要分析以下几个链表:

不带头节点的单链表、带头节点的双向循环链表

链表:一种链式存储的线性表,用一组地址任意的存储单元存放线性表的数据元素,称存储单元为一个节点

链表分类

1.单/双链表

2.带/不带头节点

3.循环/不循环链表

链表的基本操作

单链表

基本操作:初始化、销毁、插、删、查

在删除和插入中分:头删/插、尾删/插、正常删/插

  •  定义结构体
typedef int DataType;

typedef struct ListNode
{
    DataType data;
    struct ListNode* next;
} ListNode;
  •  初始化
void ListInit(ListNode **ppfirst)
{
    assert(*ppfirst!=NULL);
    *ppfirst = NULL;
}
  •  销毁
void DestroyList(ListNode **ppfirst)
{
    ListNode *next = *ppfirst;
    for(ListNode *cur = *ppfirst;cur!=NULL;cur = next)
    {
        next = cur->next;
        free(cur);
    }
    *ppfirst = NULL;
}

链表的基本操作 

  •  创建节点
ListNode* CreatNode(DateType data)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    assert(newnode);
    node->data = data;
    node->next = NULL;
    
    return newnode;
}
  •  插入

分析

正常情况:从堆上申请空间,更改ppfirst的值

特殊情况:*ppfirst == NULL

  • 头插

链表的基本操作

void ListPushFront(ListNode **ppfirst, DataType data)
{
    assert(ppfirst != NULL);
    ListNode* node = CreatNode(data);
    node->next = *ppfirst;
    
    *ppfirst = node;
}

链表的基本操作 

  • 尾插(遍历链表)
void ListPushBack(ListNode **ppfirst, DataType data)
{
    ListNode* node = CreatNode(data);
    //特殊情况 链表为空
    if(*ppfirst == NULL)
    {
        *ppfirst = node;
        return;
    }
    //正常情况
    ListNode *cur = *ppfirst;
    while(cur != NULL)
    {
        cur = cur->next;
    }
    cur->next = node;
}
  • 正常插入(中插)

分析

  1. 如果要插入的位置是第一个节点--->调用头插
  2. 找到要插入的位置的前一个节点,插入

链表的基本操作

void ListInsert(ListNode **ppfirst, ListNode *pos, DataType data)
{
    //pos是第一个节点
    if(*ppfirst == pos)
    {
        ListPushFront(ppfirst,data);
        return;
    }
    //找到pos前一个节点
    ListNode *cur = *ppfirst;
    while(cur->next != pos)
    {
        cur = cur->next;
    }
    ListNode *node = CreatNode(data);
    node->next = cur->next;
    cur->next = node;
}
  •  删除

  • 头删

分析

  1. 变量地址不为空
  2. 不能为空链表

链表的基本操作

void ListPopFront(ListNode **ppfirst)
{
    assert(ppfirst != NULL);
    assert(*ppfirst != NULL);
    ListNode *del = *ppfirst;
    *ppfirst = del->next;
    free(del);
}
  • 尾删

分析

  1. cur->next->next == NULL
  2. 特殊:只有一个节点

链表的基本操作 

void ListPopBack(ListNode **ppfirst)
{
    assert(ppfirst != NULL);
    assert(*ppfirst != NULL);
    //只有一个节点
    if((*ppfirst)->next == NULL)
    {
        free(*ppfirst);
        *ppfirst = NULL;
        return;
    }
    ListNode *cur = *ppfirst;
    ListNode *del;
    while(cur->next->next != NULL);
    {
        cur = cur->next;
    }
    del = cur->next;
    cur->next = NULL;
    free(del);
}
  •  正常删除(中删)

分析

  1. 当要删除的是第一个节点时--->头删
  2. 先找到要删除的节点的前一个节点,然后删除

链表的基本操作 

void ListEarse(ListNode **ppfirst, ListNode *pos)
{
    assert(ppfirst != NULL);
    assert(*ppfirst != NULL);
    if((*ppfirst)->next == pos)
    {
        ListPopFront(ppfirst);
        return;
    }
    ListNode *cur = *ppfirst;
    while(cur->next != pos)
    {
        cur = cur->next;
    }
    cur->next = pos->next;
    free(pos);
}
  •  查找

分析

  1. 遍历链表
  2. 传值
ListNode* ListFind(ListNode* first, DataType data)
{
    assert(first);
    for(ListNode *cur = first; cur != NULL; cur = cur->next)
    {
        if(cur->data == data)
        {
            return cur;
        }
    }
    return NULL;
}

双向带头循环链表

基本操作:初始化、销毁(删除带头节点)、清空(保留带头节点)、插、删

在删除和插入中分:头删/插、尾删/插、正常删/插

  •  定义结构体
typedef struct DListNode
{
	int data;
	struct DListNode *prev;
	struct DListNode *next;
} DListNode;

链表的基本操作 

  •  初始化
void DListInit(DListNode **ppHead)
{
    assert(ppHead != NULL);
    DListNode *pHead = (DListNOde*)malloc(sizeof(DListNode));
    pHead->prev = pHead;
    pHead->next = pHead;
    
    *ppHead = pHead;
}
  •  清空链表
void DListClear(DListNode *pHead)
{
    DListNode *cur = pHead->next;
    DListNode *next;
    while(cur != pHead)
    {
        next = cur->next;
        free(cur);
    }
    pHead->next = pHead;
	pHead->prev = pHead;
}
  •  销毁
void DListDestroy(DListNode **ppHead)
{
    assert(ppHead != NULL);
    DListClear(*ppHead);
    free(*ppHead);
    *ppHead = NULL;
}
  •  插入

  • 正常插入 

链表的基本操作 

void DListInsert(DListNode *pHead, DListNode *pos, int data)
{
    (void)pHead;//仅仅是为了防止编译警告
    DListNode *node = (DListNOde*)malloc(sizeof(DListNode));
    node->data = data;
    
    node->prev = pos->prev;
	node->next = pos;
	pos->prev->next = node;
	pos->prev = node;
}
  • 头插
void DListPushFront(DListNode *pHead, int data)
{
    DListInsert(pHead, pHead->next, data);
}
  • 尾插
void DListPushBack(DListNode *pHead, int data)
{
    DListInsert(pHead,pHead,data);
}

链表的基本操作 

  •  删除 

  • 正常删除

void DListErase(DListNode *pHead, DListNode *pos)
{
    (void)pHead;
    assert(pHead != NULL);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    
    free(pos);
}
  • 头删
void DListPopFront(DListNode *pHead)
{
	DListErase(pHead,pHead->next);
}
  • 尾删
void DListPopBack(DListNode *pHead)
{
	DListErase(pHead, pHead->prev);
}