新闻公告

带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)（下）

发布时间：2023-06-27 01:00:15

"申请新节点"函数

新节点都是使用malloc函数动态申请的.函数实现很简单,相信聪明的友友们可以理解,牛牛就不过介绍了.

SLTNode* BuyNode(DateType x)//创建新结点 {  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));  assert(newnode);//防止申请结点失败  newnode->Date = x;  newnode->next = NULL;  return newnode; }

2.3 "删除"元素操作.

因为链表的结点都是动态申请的,所以链表的删除操作需要将目标结点释放,同时为了保护原有的链表结构,需要将受目标结点的其他结点也灵活修改.

单链表的"尾删"

"删除结点"步骤:

处理特殊情况,如果头指针指向NULL,空链表不能执行删除操作.

找倒数第二个结点,方法:tail->next->next != NULL因为最后一个结点的next=NULL;

数据结构记得多画图哦,有助于我们理解.

先释放尾结点(tail->next),再将倒数第二个结点的next置空NULL

处理特殊情况:如果链表就只有一个结点,就不存在倒数第二个结点,此时直接释放头结点,并将头结点置空.

图解:

//尾删 void PopBack(SLTNode** pphead) {  assert(pphead);//二级指针不可能为空,如果为空就一定是传错了  assert(*pphead);//防止空链表的删除操作  SLTNode* tail = *pphead;//创建一个指针代替头指针遍历  if (tail->next == NULL) {  free(tail);  tail= NULL;  }  else {  while (tail->next->next != NULL)  {  tail = tail->next;  }  free(tail->next);  tail->next = NULL;  }  }

单链表的"头删":

同样,单链表的"头删"也是很简单的操作.

步骤:

将头结点记录一下.

将头指针指向第二个结点.

释放头结点.

void PopFront(SLTNode** pphead) {  assert(pphead);//二级指针不可能为空,如果为空就一定是传错了  assert(*pphead);//防止空链表的删除操作  SLTNode* head = *pphead;  *pphead = ( * pphead)->next;  free(head); }

思考:

需不需要单独去考虑,如果链表只有一个结点的特殊情况?

答案:

不需要,因为如果链表只有一个结点,头删将头指针指向第二个结点,刚好是指向NULL,也是符合要求的.

单链表的"删除"指定的目标结点

步骤:

通过查找目标结点函数SListFind(下面牛牛讲了),找到目标结点的地址.

将目标结点的前驱结点指向目标结点的后继结点.

释放目标结点.

特殊情况:如果是头删,需要修改头结点,让其指向第二个结点.

图解:

代码实现:

//告诉位置(建议配合SListFind函数一起使用),删除第一个出现该值的节点 void SlitErase(SLTNode** pphead, SLTNode* pos) {  assert(pphead);//二级指针不可能为空,如果为空就一定是传错了  assert(*pphead);//防止空链表的删除操作  assert(pos);  SLTNode* cur = *pphead;//创建一个指针代替头指针遍历  if (cur == pos) {//如果目标结点是头结点这种特殊情况  SLTNode* next = cur->next;  free(cur);  *pphead = next;  }  else {  while (cur->next != pos && cur->next != NULL)//遍历寻找目标结点  {  cur = cur->next;  }  cur->next = pos->next;//将目标结点的前驱指向目标结点的后继  free(pos);  } }

2.4 "查找"目标结点函数

单链表查找目标结点只需要遍历一遍这个链表即可,如果目标结点有多个,则只返回第一个遇到的目标结点,找不到目标结点则返回NULL.

函数很简单,牛牛不过多介绍了.

SLTNode* SListFind(SLTNode* phead, DateType x) {  SLTNode* cur = phead;//代替头指针遍历链表  while (cur)  {  if (cur->Date == x)  {  return cur;  }  cur = cur ->next;  }  return NULL; }

2.5 单链表的"打印"

单链表的打印很简单,遍历打印就行了.

void Print(SLTNode* phead)//链表的打印 {  //assert(phead);  SLTNode* cur = phead;  while (cur)  {  printf("%d->", cur->Date);  cur = cur->next;  }  printf("NULL\n\n"); }

2.6 单链表的"销毁"

步骤:

创建next指针保存要删除节点的下一个结点.

将要删除的结点释放.

将要删除的结点更新到next

继续执行1

//单链表的销毁 void SLTDestroy(SLTNode* phead)//这个函数不会将头指针置空,要使用该函数的人自己置空 {  SLTNode* del = phead;  SLTNode* next = phead;//用于记录下一个结点  while (next)  {  next = next->next;  free(del);  del = next;   }  //保持习惯置空  next == NULL;  del = NULL; }

总结:"链表"与"顺序表"的区别

顺序表	链表	区别
物理上必定是连续的	逻辑上连续,但是物理上不一定连续	物理存储空间
访问其中的某个结点支持随机访问( O(1) )	不支持随机访问	访问元素

大多数情况下需要移动数据,效率低( O(N) )	只需要改变目标指针的指向,但是需要找到该结点	删除和插入新节点(任意位置)
容量不够时,动态顺序表需要动态扩容,效率不高	没有容量的概念不需要扩容,资源利用率高	插入数据时
元素的存储很高效+频繁访问	频繁的对任意位置的插入和删除	使用场景

由于无物理上连续存在,利用率高

利用率低

缓存利用率

三、总代码

测试区(test.c)

//test.c 主函数区域,用于测试接口 #include "SList.h" void test1() {  SLTNode* plist=NULL;  printf("插入0,1,2,3,4,5,6,7,8,9之后:\n");  PushBack(&plist, 1);  PushBack(&plist, 2);  PushBack(&plist, 3);  PushBack(&plist, 4);  PushBack(&plist, 5);  PushBack(&plist, 6);  PushBack(&plist, 7);  PushBack(&plist, 8);  PushBack(&plist, 9);  //头插  PushFront(&plist, 0);   Print(plist);  printf("尾删一次后:\n");  PopBack(&plist);  Print(plist);  printf("头删一次后:\n");  PopFront(&plist);  Print(plist);  printf("删除第一次出现元素7的结点后:\n");  SlitErase(&plist, SListFind(plist, 7));  Print(plist);  printf("在第一个出现5值的结点后面插入一个值为666的结点\n");  SLTInsertBack(SListFind(plist, 5), 666);  Print(plist);  SLTDestroy(plist);  plist == NULL; } int main() {  test1();  return 0; }

接口实现区(SList.c)

 #include "SList.h"  SLTNode* BuyNode(DateType x)//创建新结点 {  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));  assert(newnode);  newnode->Date = x;  newnode->next = NULL;  return newnode; } void PushBack(SLTNode** pphead, DateType x) {  assert(pphead);  SLTNode*tail = *pphead;//创建一个指针代替头指针遍历  SLTNode* newnode = BuyNode(x);  //cur代表代表头指针,phead表示头指针的地址  //如果cur指向NULL,说明为空链表  if (*pphead == NULL)  {  //这里可以使用tail代替*phead吗?  //不能,因为这里要改变的是,头结点的指针,需要用二级指针(解引用)来改变  *pphead = newnode;//空链表是将头指针指向新节点  }  else  {  //找尾巴,画图解析  //这里可以使用tail,是因为,要改变的是结构体的内容,只需要用结构体指针(解引用)就行  while ( tail->next != NULL)  {  tail = tail->next;  }  tail->next = newnode;  } }   //头插(错误示例) //void PushFront(SLTNode** pphead, DateType x) //{ // assert(pphead); // SLTNode* phead = *pphead; // SLTNode* newnode = BuyNode(x); // //下面两句的顺序不能变,除非再创一个结点保phead // newnode->next = phead; // phead= newnode; //} // 正确写法1 //void PushFront(SLTNode** pphead, DateType x) //{ // assert(pphead); // SLTNode* newnode = BuyNode(x); // //下面两句的顺序不能变,除非再创一个结点保phead // newnode->next = *pphead; // *pphead = newnode; //}  //写法2 void PushFront(SLTNode** pphead, DateType x) {  assert(pphead);  SLTNode* newnode = BuyNode(x);  SLTNode* phead = *pphead;  //顺序随便改  *pphead = newnode;  newnode->next = phead; } //尾删 void PopBack(SLTNode** pphead) {  assert(pphead);//二级指针不可能为空,如果为空就一定是传错了  assert(*pphead);//防止空链表的删除操作  SLTNode* tail = *pphead;//创建一个指针代替头指针遍历  if (tail->next == NULL) {  free(tail);  tail= NULL;   }  else {  while (tail->next->next != NULL)  {  tail = tail->next;  }  free(tail->next);  tail->next = NULL;  }  } void PopFront(SLTNode** pphead) {  assert(pphead);//二级指针不可能为空,如果为空就一定是传错了  assert(*pphead);//防止空链表的删除操作  SLTNode* head = *pphead;  *pphead = ( * pphead)->next;  free(head); }  SLTNode* SListFind(SLTNode* phead, DateType x) {  SLTNode* cur = phead;  while (cur)  {  if (cur->Date == x)  {  return cur;  }  cur = cur ->next;  }  printf("找不到:\n");  return NULL; } void SlitErase(SLTNode** pphead, SLTNode* pos) {  assert(pphead);//二级指针不可能为空,如果为空就一定是传错了  assert(*pphead);//防止空链表的删除操作  assert(pos);  SLTNode* cur = *pphead;//创建一个指针代替头指针遍历  if (cur == pos) {//如果目标结点时头结点  SLTNode* next = cur->next;  free(cur);  *pphead = next;  }  else {  while (cur->next != pos && cur->next != NULL)//遍历寻找目标结点  {  cur = cur->next;  }  cur->next = pos->next;//将目标结点的前驱指向目标结点的后继  free(pos);  } }  void SLTInsertBack( SLTNode* pos, DateType x) {  assert(pos);  SLTNode* newnode = BuyNode(x);  newnode->next = pos->next;  pos->next = newnode;  }  void Print(SLTNode* phead)//链表的打印 {  //assert(phead);  SLTNode* cur = phead;  while (cur)  {  printf("%d->", cur->Date);  cur = cur->next;  }  printf("NULL\n\n"); }   void SLTDestroy(SLTNode* phead)//这个函数不会将头指针置空,要使用该函数的人自己置空 {  SLTNode* del = phead;  SLTNode* next = phead;//用于记录下一个结点  while (next)  {  next = next->next;  free(del);  del = next;   }  //保持习惯置空  next == NULL;  del = NULL; }

函数声明区(SList.h)

#pragma once #include#include#includetypedef int DateType; typedef struct SListN0de {  DateType Date;  struct SListN0de* next; }SLTNode;  //尾插 void PushBack(SLTNode** pphead, DateType x); //尾删 void PopBack(SLTNode** pphead); //头插 void PushFront(SLTNode** pphead, DateType x); //头删 void PopFront(SLTNode** pphead);  //告诉值,返回结点的地址 SLTNode* SListFind(SLTNode* phead, DateType x);  //告诉位置(建议配合SListFind函数一起使用),删除第一个出现该值的节点  void SlitErase(SLTNode** pphead, SLTNode* pos);  //告诉位置,在位置后面插入 void SLTInsertBack( SLTNode* pos, DateType x);  struct SListN0de* BuyNode(DateType x);//创建新节点  void Print(SLTNode* phead);//链表的打印   // 单链表的销毁 void SLTDestroy(SLTNode* phead);

关于我们