数据结构——顺序表和链表（下）-阿里云开发者社区

数据结构——顺序表和链表（下）

2022-12-09 84

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 笔记

尾部插入

先建立一个新的节点

分为俩种情况，第一种头节点指向空，第二种头节点指向不为空

第一种情况：头节点为空，建立新的节点后，直接让头节点指向新节点

第二种情况，头节点不为空，创建一个跟节点类型相同的结构体变量，然后让这个变量指向头节点，之后检查后面的每个节点，若有一个节点为的next为空，则在此处插入新节点

tail发现这个节点的next指向为空，然后让这个节点的next指向下一个节点的地址，随着程序的结束tail也会随之消失

void SListpushback(SLTNode** pphead, SLTDataType x)
{
  //pphead不可能为空，pphead是plist的地址，pphead永远不为空
  //1.链表为空
  SLTNode* newnode = BuySLTnode(x);
  if (*pphead == NULL)
  {
  *pphead = newnode;
  }
  //2.不为空
  else
  {
  SLTNode* tail = *pphead;
  while (tail->next != NULL)
  {
    tail =tail->next;
  }
  tail->next = newnode;
  }
}

频繁的malloc会使效率降低

头部节点删除

void SListpopfront(SLTNode** pphead)//头删
{
  SLTNode* del = *pphead;
  *pphead = (*pphead)->next;
  free(del);//删除第一个节点 
  del = NULL;
}

当全部删完后，plist指向NULL，此时就不能再删了。程序会崩溃，此时plsit为空，（*pphead）->next也为空，del也为空，因此加一个检查条件

void SListpopfront(SLTNode** pphead)//头删
{
if（*pphead==NULL）
{
return;
}
  SLTNode* del = *pphead;
  *pphead = (*pphead)->next;
  free(del);//删除第一个节点 
  del = NULL;
}

或

void SListpopfront(SLTNode** pphead)//头删
{
    assert(*pphead！=NULL)；
  SLTNode* del = *pphead;
  *pphead = (*pphead)->next;
  free(del);//删除第一个节点 
  del = NULL;
}

尾部节点删除

要判断尾部有一个节点还是多个节点甚至没有节点

当tail->next为空，删除该节点，然后让前一个节点指向NULL

void SListpopback(SLTNode** pphead)
{
if(*pphead==NULL)
return;
if((*pphead)->next==NULL)
{
free(*pphead);
*pphead=NULL;
}
else
{
  SLTNode* prev = NULL;
  SLTNode* tail = *pphead;
  while (tail->next!= NULL)
  {
  prev = tail;
  tail = tail->next;
  }
  prev->next = NULL;
  free(tail);
  tail = NULL;
}
}

或

void SListpopback(SLTNode** pphead)
{
if(*pphead==NULL)
return;
if((*pphead)->next==NULL)
{
free(*pphead);
*pphead=NULL;
}
else
{
  SLTNode* tail = *pphead;
  while (tail->next->next!= NULL)
  {
  tail = tail->next;
  }
  free(tail->next);
  tail->next = NULL;
}
}

节点的销毁

释放掉cur,cur=next ，不断往下走，最后把头节点置空

void SListDestory(SLTNode** pphead)//用二级指针会更好
{
  SLTNode* cur = *pphead;
  while (cur)
  {
  SLTNode* next = cur->next;
  free(cur);
  cur = next;
  }
  *pphead = NULL;
}

链表查找

SLTNode *SListFind(SLTNode** pphead, SLTDataType x)
{
  SLTNode* cur = *pphead;
  while (cur != NULL)
  {
  if (cur->data == x)
  {
    return cur;
  }
  cur = cur->next;
  }
  return NULL;
}

挨个查找。

随即插入

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pos);
  if (pos == *pphead)
  {
  SListpushfront(pphead, x);
  }
  else
  {
  SLTNode* prve = *pphead;
  while (prve->next != pos)
  {
    prve = prve->next;
    assert(prve);//找不到
  }
  SLTNode* newnode = BuySLTnode(x);
  prve->next = newnode;
  newnode->next = pos;
  }
}

从一个数的前面插入，若果头插则用头插函数

后插

void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  SLTNode* newnode = BuySLTnode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

删除某节点前面的节点

void SlistErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  if (*pphead == pos)
  {
  SListpopfront(pphead);
  }//如果是头删，用头删函数
  else
  {
  SLTNode* prev = *pphead;
  if (prev->next != pos)
  {
    prev = prev->next;
    assert(prev);//判断pos是否属于本链表
  }
  prev->next = pos->next;
  free(pos);
  pos = NULL;
  }
}

删除某节点后面的节点

void SlistEraseAfter(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  if (pos->next == NULL)
  return;
  else
  {
  SLTNode* prev = *pphead;
  prev = pos->next;
  pos->next = prev->next;
  free(prev);
  prev = NULL;
  }
}