【数据结构】顺序表和链表2(下)

简介: 【数据结构】顺序表和链表2(下)

5.打印链表

定义cur指针遍历链表,逐个访问数据,这里为了更加形象,在每个数据之后加上了->符号。

void SListPrint(SListNode* plist)
{
  SListNode* cur = plist;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}


6.查找数据

遍历链表,逐个与需要查找到数据对比,如果与我们需要查找到数据相同,就返回该节点地址,否则返回NULL

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
  SListNode* cur = plist;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}


(2)带头双向循环链表的接口实现

1.存储结构

双向链表和单列表的区别就是双向链表多一个指向前一个节点的指针prev,结构如下图:

12d50f487e8345b5a921833a4397721f.png

typedef struct ListNode
{
  LTDataType _data;
  struct ListNode* _next;
  struct ListNode* _prev;
}ListNode;

2.初始化与销毁

  • 初始化

带头链表的初始化就是新建一个哨兵位头节点,后面对链表进行操作的时候直接传头节点即可,此时链表内没有元素,所有哨兵位的prev指向自己,next也指向自己。

ListNode* ListCreate()
{
  ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
  if (guard == NULL)
  {
    perror("BuyListNode");
    exit(-1);
  }
  guard->_next = guard;
  guard->_prev = guard;
  return guard;
}


  • 销毁

由于增加节点的时候是一个一个的malloc的所有销毁的时候也是一个一个的释放,那么定义一个cur指针,遍历链表,依次free,最后free掉哨兵位。

void ListDestory(ListNode* pHead)
{
  assert(pHead);
  ListNode* cur = pHead->_next;
  ListNode* next = NULL;
  while (cur != pHead)
  {
    next = cur->_next;
    free(cur);
    cur = next;
  }
  free(pHead);
    pHead = NULL;
}


3.插入数据

每一次插入数据都需要创建新节点,因此封装一个BuyListNode函数,用于创建新节点

ListNode* BuyListNode(LTDataType x)
{
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  if (newnode == NULL)
  {
    perror("BuyListNode");
    exit(-1);
  }
  newnode->_next = NULL;
  newnode->_prev = NULL;
  newnode->_data = x;
  return newnode;
}


  • 头插

创建新节点,链接在guard的下一个节点位置。将nownode的prev指向guard。

void ListPushFront(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListNode* newnode = BuyListNode(x);
  newnode->_next = pHead->_next;
  pHead->_next->_prev = newnode;
  pHead->_next = newnode;
  newnode->_prev = pHead;
}


  • 尾插

在单链表里,进行尾插的时候,需要先找到尾,但是对于双向链表,他的guard节点指向的prev就是尾节点,就可以省略了找尾节点的过程,然后将newnode节点链接上即可

void ListPushBack(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListNode* newnode = BuyListNode(x);
  ListNode* tail = pHead->_prev;
  tail->_next = newnode;
  newnode->_prev = tail;
  pHead->_prev = newnode;
  newnode->_next = pHead;
}


  • pos位置之前插入

在pos位置之前插入就需要在用用prev记录pos的前一个节点,然后创建一个新节点,并链接在链表上即可。

void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);
  ListNode* prev = pos->_prev;
  ListNode* newnode = BuyListNode(x);
  prev->_next = newnode;
  newnode->_prev = prev;
  newnode->_next = pos;
  pos->_prev = newnode;
}


4.删除数据

在删除节点的时候,要保证删除的不能是哨兵位节点,所以这里封装一个判空函数判断链表里是否只有一个头节点,返回bool值。

bool ListEmpty(ListNode* pHead)
{
  assert(pHead);
  return pHead->_next == pHead;
}


  • 头删

首先要判断传入的指针是否有效,链表是否为空,头删删除的是哨兵位的下一节点,那么我们定义一个del保存guard的next节点,然后将del节点取下来,将其他guard与del的下一节点链接起来,然后释放del节点。

void ListPopFront(ListNode* pHead)
{
  assert(pHead);
  assert(!ListEmpty(pHead));
  ListNode* del = pHead->_next;
  pHead->_next = del->_next;
  del->_next = pHead;
  free(del);
  del = NULL;
}


  • 尾删

首先判断指针有效性,然后判空。尾删本质上删除的是guard的前一个节点,所以我们先定义一个tail保存尾节点,然后取下来tail节点,将其他的节点链接起来,然后释放tail节点。

void ListPopBack(ListNode* pHead)
{
  assert(pHead);
  assert(!ListEmpty(pHead));
  ListNode* tail = pHead->_prev;
  tail->_prev->_next = pHead;
  pHead->_prev = tail->_prev;
  free(tail);
  tail = NULL;
}


  • 删除pos位置的节点

删除该节点,直接将pos位置的节点的前一个节点和后一个节点链接起来,然后释放pos位置即可。

void ListErase(ListNode* pos)
{
  assert(pos);
  pos->_prev->_next = pos->_next;
  pos->_next->_prev = pos->_prev;
  free(pos);
  pos = NULL;
}


5.查找数据

遍历链表,并与需要查找的数据对比,匹配之后返回该节点地址,否则返回空指针。

ListNode* ListFind(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListNode* cur = pHead->_next;
  while (cur != pHead)
  {
    if (cur->_data == x)
      return cur;
    cur = cur->_next;
  }
  return NULL;
}


6.打印数据

遍历链表,依次打印数据,这里为了更加形象,在每个数据后面加上'<=>'符号。

void ListPrint(ListNode* pHead)
{
  assert(pHead);
  ListNode* cur = pHead->_next;
  printf("guard<=>");
  while (cur != pHead)
  {
    printf("%d<=>", cur->_data);
    cur = cur->_next;
  }
  printf("\n");
}


相关文章
|
1天前
数据结构 链表(第7、8天)
数据结构 链表(第7、8天)
|
1天前
|
存储
数据结构——带头双向循环链表
数据结构——带头双向循环链表
|
4天前
|
存储 索引
顺序表和链表
通过以上示例,我们可以看到顺序表和链表在实际应用中如何操作。顺序表适合于需要频繁读取数据的场景,而链表则更适用于频繁修改数据的情况。在选择使用哪种数据结构时,应考虑到实际应用的需求和上下文环境。
9 2
|
4天前
|
存储
初阶数据结构 带头双链表
初阶数据结构 带头双链表
7 0
|
4天前
数据结构初阶 链表的补充
数据结构初阶 链表的补充
7 0
|
4天前
|
存储
数据结构初阶 链表详解
数据结构初阶 链表详解
5 0
|
4天前
数据结构初阶 顺序表的补充
数据结构初阶 顺序表的补充
5 0
|
4天前
|
存储
数据结构初阶 顺序表的讲解
数据结构初阶 顺序表的讲解
7 0
|
9天前
|
存储 算法
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
9 0
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
|
6天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表