数据布局-2.单向链表的实现

节点布局体计划

1. struct LinkNode
2. {
3.         // 数据域
4.         void* data;
5.         // 指针域
6.         struct LinkNode * next;
7. };

复制代码

• data：一个 void* 类型的指针，指向节点存储的数据。利用 void* 是为了链表可以或许存储不同类型的数据。
  
• next：一个指向下一个 LinkNode 布局体的指针，形成链表的链接。
  

链表布局体计划

1. struct LList
2. {
3.         //头节点
4.         struct LinkNode pHeader;
5.         //链表长度
6.         int m_size;
7. };

复制代码

• pHeader：链表的头节点。固然 pHeader 本身也是 LinkNode 类型，但它可以作为链表的起始节点，其 next 指针指向第一个实际的数据节点。
  
• m_size：一个整数，表现链表中节点的数量。
  

初始化链表

1. LinkList init_LinkList()
2. {
3.         struct LList* myList = malloc(sizeof(struct LList));
4.        
5.         if (myList == NULL)
6.         {
7.                 return NULL;
8.         }
10.         myList->pHeader.data = NULL;
11.         myList->pHeader.next = NULL;
12.         myList->m_size = 0;
14.         return myList;
15. }

复制代码

• 利用 malloc 分配 struct LList 的内存。
  
• 初始化头节点的 data 指针为 NULL，next 指针也为 NULL。
  
• 设置链表长度 m_size 为 0。
  

插入链表

1. void insert_LinkList(LinkList list, int pos, void* data)
2. {
3.         if (list == NULL)
4.         {
5.                 return;
6.         }
7.         if (data == NULL)
8.         {
9.                 return;
10.         }
11.         // 将list还原成struct LList数据类型
12.         struct LList * myList = list;
14.         if (pos <0 || pos > myList->m_size)
15.         {
16.                 //位置无效 强制尾插
17.                 pos = myList->m_size;
18.         }
19.         //找到插入节点的前驱
20.         struct LinkNode * pCurrent = &myList->pHeader;
21.         for (int i = 0; i < pos; i++)
22.         {
23.                 pCurrent = pCurrent->next;
24.         }
25.         //创建新节点
26.         struct LinkNode* newNode = malloc(sizeof(struct LinkNode));
27.         newNode->data = data;
28.         newNode->next = NULL;
30.         //建立节点关系
32.         newNode->next = pCurrent->next;
33.         pCurrent->next = newNode;
35.         //更新链表长度
36.         myList->m_size++;
37. }

复制代码

• 查抄 list 和 data 是否为空，若为空则返回。
  
• 如果位置 pos 无效（负数或超出链表当前巨细），将位置设置为链表末尾。
  
• 通过遍历找到插入位置的前驱节点 pCurrent。
  
• 创建新节点并插入链表中。
  
• 更新链表长度 m_size。
  

遍历链表

1. void foreach_linkList(LinkList list,void(*myForeach)(void *))
2. {
3.         if (list == NULL)
4.         {
5.                 return;
6.         }
8.         struct LList* mylist = list;
10.         struct LinkNode* pCurrent = mylist->pHeader.next;
11.         for (int i = 0; i < mylist->m_size; i++)
12.         {
13.                 myForeach(pCurrent->data);
14.                 pCurrent = pCurrent->next;
15.         }
16. }

复制代码

• 查抄 list 是否为空，若为空则返回。
  
• 利用 pCurrent 遍历链表，重新节点的下一个节点开始。
  
• 对每个节点的数据调用 myForeach，然后移动到下一个节点。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。