大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
链表,也称线性表的链式存储结构,其元素在内存空间上不是连续的,通过指针链接来决定元素的次序。
链表的结构多种多样,以下的情况组合起来就有8种链表结构。
1.单向或者双向
虽然有这么多种结构,但是我们最常用的只有两种:
1.无头单向非循环链表:结构简单,一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构,如哈希桶,图的邻接表等。
2.带头双向循环链表:结构最复杂,但实现起来比较简单。
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;
struct SListNode* next;
}SLTNode;
//动态申请一个节点
SLTNode* BuySListNode(SLTDataType x);
//单链表打印
void SLTPrint(SLTNode* phead);
//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//单链表尾删
void SLTPopBack(SLTNode** pphead);
//单链表头插
void SLTPushFount(SLTNode** pphead, SLTDataType x);
//单链表头删
void SLTPopFount(SLTNode** pphead);
//单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//单链表pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//单链表pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//单链表删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
//单链表删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//单链表销毁
void SLTDestroy(SLTNode** pphead);
动态申请一个节点SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{perror("malloc file:");
exit(-1);//退出程序
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
单链表打印void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;
while (cur != NULL)
{printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
单链表尾插void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{*pphead = newnode;
}
else
{SLTNode* tail = *pphead;
while (tail->next)
{ tail = tail->next;
}
tail->next = newnode;
}
}
这里使用二级指针是因为当链表为空时,需要改变一级指针phead为newnode,想要改变一级指针的值要用二级。
单链表尾删void SLTPopBack(SLTNode** pphead)
{assert(*pphead);
if ((*pphead)->next == NULL)
{free(*pphead);
*pphead = NULL;
}
else
{SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next)
{ prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
单链表头插void SLTPushFount(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
单链表头删void SLTPopFount(SLTNode** pphead)
{assert(*pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
单链表查找SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;
while (cur)
{if (cur->data == x)
{ return cur;
}
cur = cur->next;
}
return NULL;
}
单链表pos之后插入xvoid SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);
SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
单链表pos之前插入xvoid SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);
if (*pphead == pos)
{SLTPushFount(pphead, x);
}
else
{SLTNode* prev = *pphead;
while (prev->next != pos)
{ prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
------为什么在pos之后插入x相比在之前插入要简单呢?
因为想要在pos之前插入,必须要找到pos的前一个节点,只能通过遍历链表来找到它。后面的删除指定结点也是相同的道理。
void SLTEraseAfter(SLTNode* pos)
{assert(pos);
if (pos->next == NULL)
{return;
}
else
{SLTNode* nextNode = pos->next;
pos->next = pos->next->next;
free(nextNode);
}
}
单链表删除pos节点void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);
if (*pphead == pos)
{SLTPopFount(pphead);
}
else
{SLTNode* prev = *pphead;
while (prev->next != pos)
{ prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
单链表销毁void SLTDestroy(SLTNode** pphead)
{SLTNode* cur = *pphead;
while (cur)
{SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
通过以上代码可以看出,相比顺序表,链表的头插和头删要简便许多,而尾插和尾删要繁琐一些,这是因为链表不能随机存取,想要找到最后一个结点必须从头开始遍历。
学会了单链表的实现,那么有不少单链表的题就可以有思路了,许多题看似复杂,但实际上就是单链表的插入、删除。
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
val = 5:
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head, *p = head;
while (cur)
{if(cur == head) //当cur为头时
{if (cur->val == val)
{cur = cur->next;
head = cur;
p = cur;
}
else
{cur = cur->next;
}
}
else if (cur->next == NULL) //当cur为尾时
{if (cur->val == val)
{cur = cur->next;
p->next = NULL;
}
else
{cur = cur->next;
}
}
else //当cur在中间
{if (cur->val == val)
{cur = cur->next;
p->next = p->next->next;
}
else
{p = cur;
cur = cur->next;
}
}
}
return head;
}
这是我做这道题时想出的第一个方法,这个方法非常繁琐,要考虑三种情况,就是当cur在头、尾、中间。这个方法很容易想到但难以用代码去实现,在写代码的过程中经常容易乱。
其实这个方法可以优化一下,把“if (cur->val = val)”这个判断拿到外层。代码如下:
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head, *prev = head;
while (cur)
{if (cur->val == val)
{if (cur == head) //当cur为头时
{cur = cur->next;
free(head);
head = cur;
prev = cur;
}
else //当cur不为头
{prev->next = cur->next;
free(cur);
cur = prev->next;
}
}
else
{prev = cur;
cur = cur->next;
}
}
return head;
}
这下看起来是不是简单多了?
回到优化前的代码:在每一个判断cur位置的条件语句中,都包含了对cur->val的判断,于是我想到不妨把里面的这个条件语句拿出来,这样外层就只需要if-else就好了,少了一层判断。再看内部,我也只分了两个条件,一个是cur为头,另一个就是不为头,当cur在中间和尾时的操作其实时相同的,所以把它们合并在一起。并且加上了free函数,把要删除的结点free掉,防止内存泄漏。
其实很多人第一次写都会写出像优化前那样的代码,这很正常,因为初次接触思路可能没有那么清晰,多练练就好了。
与其像方法一那样在原链表上进行操作,我们不妨创建一个新的链表,然后把符合条件的值尾插到新链表中。
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;
struct ListNode* newhead = NULL; //新链表的头
struct ListNode* tail = NULL; //新链表的尾
while (cur)
{if (cur->val != val)
{if (tail == NULL) //判断新链表是否为空
{newhead = tail = cur;
}
else
{tail->next = cur;
tail = tail->next;
}
cur = cur->next;
}
else
{struct ListNode* next = cur->next;
free(cur);
cur = next;
}
}
if (tail) //把新链表的尾结点的next置NULL
{tail->next = NULL;
}
return newhead;
}
这种方法想起来不难,实现起来也不难,写完之后就会发现这不就是单链表的尾插吗,只不过就是加了一个筛选条件而已。
方法三:创建带头链表第三种方法是创建一个带头链表。
我们知道,单链表的尾插相比头插要复杂一些,于是我想到采用带头链表。
采用带头链表可以省去判断新链表是否为空,因为它一定带有头节点不为空,使代码更简洁。
注意:本题要求返回的链表不能带有头节点,所以在最后应该返回头节点的next。
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;
struct ListNode* guard, *tail;
guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode)); //动态开辟一个头结点
guard->next = NULL;
while (cur)
{if (cur->val != val)
{tail->next = cur;
tail = tail->next;
cur = cur->next;
}
else
{struct ListNode* next = cur->next;
free(cur);
cur = next;
}
}
tail->next = NULL;
struct ListNode* newhead = guard->next;
free(guard);
return newhead;
}
这种方法不用考虑多种情况,是我最喜欢的方法。
例题——反转链表给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
这题其实很容易,我们只需要创建一个新链表,然后依次把原链表中的元素头插到新链表中即可。代码如下:
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur = head;
struct ListNode* rhead = NULL;
while (cur)
{struct ListNode* next = cur->next;
cur->next = rhead;
rhead = cur;
cur = next;
}
return rhead;
}
方法二:递归法这道题也可以采用递归的方法,不过有些难以理解。
struct ListNode* reverseList(struct ListNode* head)
{if (head == NULL || head->next == NULL)
{return head;
}
struct ListNode* newhead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
}
三、双向带头循环链表的实现双向带头循环链表虽然结构最复杂,但是实现起来可一点也不复杂,相信你通过前面对单链表的学习,一定能自己写出双向链表。
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
//动态申请一个结点
LTNode* BuyListNode(LTDataType x);
//初始化
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//插入
void LTInsert(LTNode* phead, LTDataType x);
//删除
void LTErase(LTNode* phead);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//返回链表长度
size_t LTSize(LTNode* phead);
//销毁
void LTDestroy(LTNode* phead);
动态申请一个节点LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{perror("malloc fail");
exit(-1);
}
node->data = x;
node->next = NULL;
node->prev = NULL;
return node;
}
初始化LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
打印void LTPrint(LTNode* phead)
{LTNode* cur = phead->next;
while (cur != phead)
{printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
尾插void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
//LTInsert(phead, x);
}
尾删void LTPopBack(LTNode* phead)
{assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
tailPrev->next = phead;
phead->prev = tailPrev;
free(tail);
//LTErase(phead->prev);
}
头插void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);
LTNode* newnode = BuyListNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
//LTInsert(phead->next, x);
}
头删void LTPopFront(LTNode* phead)
{assert(phead);
assert(phead->next != phead);
LTNode* first = phead->next;
LTNode* second = first->next;
free(first);
phead->next = second;
second->prev = phead;
//LTErase(phead->next);
}
查找LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{if (cur->data == x)
{ return cur;
}
cur = cur->next;
}
return NULL;
}
插入void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
删除void LTErase(LTNode* pos)
{assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
free(pos);
prev->next = next;
next->prev = prev;
}
在实现插入、删除后,我们其实可以将其复用到尾插尾删头插头删中。
判断链表是否为空bool LTEmpty(LTNode* phead)
{assert(phead);
return phead->next == phead;
}
返回链表长度size_t LTSize(LTNode* phead)
{assert(phead);
LTNode* cur = phead->next;
size_t size = 0;
while (cur != phead)
{++size;
cur = cur->next;
}
return size;
}
销毁void LTDestroy(LTNode* phead)
{LTNode* cur = phead->next;
while (cur != phead)
{LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
四、总结本文主要讲述了单链表和双向带头循环链表的实现,其中单链表尤为重要,在笔试和面试中经常会考到,建议各位读完本文多去刷一些有关单链表的题,它还有许多奥秘等待大家去探索。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧