链表的浅析 - Githubissues

bosthhe1 commented 2 years ago

一，链表和顺序表的区别和优劣势 1，链表和顺序表在存贮的方式上有很大差异，链表是逻辑连续，但是在物理空间上是不连续的，而顺序表是连续的。 2，链表和顺序表在空间的使用方式上有很大差异，链表是需要一个空间开一个空间，然后将空间通过指针连接上，而顺序表是给定的空间，可以直接在空间内部进行操作(这里就涉及到顺序表的增容问题)。 3，链表的优势和劣势 ①，链表在空间上是不连续的，所以插入和删除都非常方便，不用挪动其他数据，只需要控制指针指向的位置，时间复杂度为O(1)。 ②，由于链表在空间上不连续，所以不能随机访问，要想访问一个元素，需要遍历链表，时间复杂度为O(N)。 ③，由于链表在空间上是不连续开辟空间，空间和空间之间容易产生空间碎片，造成空间浪费。 4，顺序表的优势和劣势 ①，顺序表在空间是连续的，所以顺序表可以进行随机访问，想要访问一个元素，只需要找到对应的下标，时间复杂度为O(1)。 ②，由于顺序表在空间上是连续的，所以顺序表的开辟不容易控制，开少了，容易造成内存不够，开打了容易造成空间浪费(不考虑动态开辟空间) ③，由于顺序表在空间上是连续的，所以顺序表的插入和删除不方便，都需要遍历顺序表，时间复杂度为O(N)。

bosthhe1 commented 2 years ago

二，无头单向不循环链表和带头双向循环链表的区别链表带头和不带头链表单向和双向链表的循环和不循环由于以上的特性，将链表分为8类(222) 其中最具有代表性的链表为；无头单向不循环链表和带头双向循环链表因为这两个链表的形式刚好为对立；无头单向不循环链表结构简单，但是在操作中却很麻烦，而带头双向循环链表结构复杂，但是在操作中却简单。以下为无头单向不循环链表和带头双向循环链表具体操作步骤。

bosthhe1 commented 2 years ago

无头单向不循环链表链表的尾插，则是将新节点插入到最后一个节点，将新节点的next指向空。 $CM5)XE$0Z$W%{ _@ ZTY)42$

void SListPushBack(SListNode** pplist, SLTDateType x)
{
SListNode* plist = *pplist;
SListNode* newTail = (SListNode*)malloc(sizeof(SListNode));
newTail->data = x;
newTail->next = NULL;
while (plist->next != NULL)
{
plist = plist->next;
}
plist->next = newTail;
}

单链表的头插是将新的节点指向原链表的头，再将原链表的表头头给新的链表头

void SListPushFront(SListNode** pplist, SLTDateType x)
{
SListNode* plist = *pplist;
SListNode* newFront = (SListNode*)malloc(sizeof(SListNode));
newFront->data = x;
newFront->next = plist;
*pplist = newFront;
}

链表在pos位置后面插入是将新的节点，插入到链表中，需要注意的是，不能先将前一个节点指向新节点，不然前一个节点无法访问下一个节点，所以要先将新节点和下一个节点链接，然后再将前一个节点链接新节点

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
newNode->data = x;
newNode->next = NULL;
SListNode* next = pos->next;
newNode->next = next;
pos->next = newNode;
}

链表的头删将现有表头删除，下一个节点作为新的头

void SListPopFront(SListNode** pplist)
{
assert(*pplist);
SListNode* NewHead = *pplist;
SListNode* FreeNode = *pplist;
NewHead = NewHead->next;//保存下一个节点的地址
free(FreeNode);//删除头节点
*pplist = NewHead;//将下一个节点作为新的头
}

链表的尾删将现有尾节点删除，上一个节点作为新的尾

void SListPopBack(SListNode** pplist)
{
assert(*pplist);
SListNode* Tail = *pplist;
SListNode* prior = *pplist;
while (Tail->next != NULL)//首先需要找到尾节点
{
prior = Tail;//用于保存尾节点的上一个节点，作为新的尾
Tail = Tail->next;
}
free(Tail);
Tail=NULL;
prior->next = NULL;
}

链表的中间删将指定的节点位置的后面节点删除。

void SListEraseAfter(SListNode* pos)
{
assert(pos);
assert(pos->next);
SListNode* next =pos->next;
pos ->next  =next->next;
free(next)
}
链表的查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
assert(plist);
SListNode* Slist = plist;
while (Slist != NULL&&Slist->data != x)//需要遍历链表，查找到对应指针位置
{
Slist = Slist->next;
}
if (Slist != NULL)
{
printf("找到了 :%d\n ", Slist->data);
return Slist;//查找到了，返回指针位置
}
else
{
printf("无该元素\n");
return NULL;//没有查找到返回空
}
}
free掉链表
退出前，销毁链表
void SListDestroy(SListNode* plist)
{
assert(plist);
while(plist)
{
pplist = plist;
plist= plist->next;
free(pplist)
}
free(plist);
plist = NULL;
}

bosthhe1 commented 2 years ago

双向带头循环链表双向带头循环链表虽然看起来结构复杂，但是在实际的操作中却比单向无头不循环链表操作简单链表的创建

ListNode* ListCreate()
{
    ListNode* Head = (ListNode*)malloc(sizeof(ListNode));
    Head->_next = Head;//自己指向自己
    Head->_prev = Head;
    return Head;
}

链表的头增// 需要改变next和prev

void ListPushFront(ListNode* pHead, LTDataType x)
{
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    p->_data = x;
    p->_next = pHead->_next;
    pHead->_next->_prev = p;
    p->_prev = pHead;
    pHead->_next = p;
}
链表的尾增//和头增道理差不多
void ListPushBack(ListNode* pHead, LTDataType x)
{
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    ListNode* Tail = pHead->_prev;
    p->_data = x;
    Tail->_next = p;
    p->_prev = Tail;
    p->_next = pHead;
    pHead->_prev = p;
}
链表的中间增//和链表头增差不多，换汤不换药
void ListInsert(ListNode* pos, LTDataType x)
{
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    p->_data = x;
    p->_next = pos;
    p->_prev = pos->_prev;
    pos->_prev->_next = p;
    pos->_prev = p;
}
链表的尾删//不需要遍历链表，头节点的prve为链表的尾节点
void ListPopBack(ListNode* pHead)
{
    assert(pHead);
    ListNode* Tail = pHead->_prev;
    ListNode* newTail = pHead->_prev->_prev;
    newTail->_next = pHead;
    pHead->_prev = newTail;
    free(Tail);
}
链表的头删，需要注意删除时候链接的顺序
void ListPopFront(ListNode* pHead)
{
    assert(pHead);
    ListNode* ps = pHead->_next;
    pHead->_next = ps->_next;
    ps->_next->_prev = pHead;
    free(ps);
}
链表的中间删除
void ListErase(ListNode* pos)
{
    ListNode* Front = pos->_prev;
    ListNode* Back = pos->_next;
    Front->_next = Back;
    Back->_prev = Front;
    free(pos);
}
链表的查找，需要遍历链表，当链表来到哨兵位的时候，说明没有找到该元素
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
    assert(pHead);
    ListNode* Find = pHead->_next;
    while (Find->_data != x&&Find!=pHead)
    {
        Find = Find->_next;
    }
    if (Find != pHead)
    {
        printf("找到了");
        return Find;
    }
    else
        printf("找不到");
        return NULL;
}
退出前摧毁链表
void ListDestory(ListNode* pHead)
{
    if (pHead->_next != pHead)
    {
        ListNode* p = pHead->_next;
        pHead->_next = pHead->_next->_next;
        pHead->_next->_prev = pHead;
        free(p);
    }
    free(pHead);
}

bosthhe1 / -

链表的浅析 #19