Site Overlay

(snippet) 整数链表

使用空头节点设计。

llist.h 如下:

#if !defined(__LLIST_H__)
#define __LLIST_H__

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 链表定义
typedef struct _node {
  int32_t data;
  struct _node *next;
} node, *pnode;

// 创建链表并返回一个结点
pnode llist_create();

// 将数据追加到链表的末尾
pnode llist_append(pnode head, int32_t data);

// 带走链表的第一个实际元素
pnode llist_shift(pnode head);

// 计算链表实际元素的数量
int32_t llist_count(pnode head);

// 获取指定位置的实际元素
pnode llist_get_at(pnode head, int32_t where);

// 取出链表最后的实际元素
pnode llist_last(pnode head);

// 释放内存
void llist_free(pnode head);

#endif  // __LLIST_H__

llist.c 如下:

#include "llist.h"

// create a linked list, returning the head, and the head will be ignored when
// using. 创建链表并返回一个结点
pnode llist_create() {
  pnode new_node = (pnode)malloc(sizeof(node));
  new_node->next = NULL;
  memset(new_node, 0, sizeof(node));
  return new_node;
}

// 将数据追加到链表的末尾
pnode llist_append(pnode head, int32_t data) {
  pnode current = head;
  while (current->next != NULL) {
    current = (pnode)current->next;
  }
  pnode new_node = llist_create();
  new_node->data = data;
  new_node->next = NULL;
  current->next = (pnode)new_node;
  return new_node;
}

// 带走链表的第一个实际元素
pnode llist_shift(pnode head) {
  pnode out = llist_create();
  out->next = NULL;
  out->data = head->next->data;
  head->next = head->next->next;
  return out;
}

// 计算链表实际元素的数量
int32_t llist_count(pnode head) {
  int32_t length = 0;
  pnode current = head;
  while ((current = current->next) != NULL) {
    length++;
  }
  return length;
}

// 获取指定位置的实际元素
pnode llist_get_at(pnode head, int32_t where) {
  if (where == 0) return head;
  int32_t index = 0;
  pnode current = head;
  while ((current = current->next) != NULL) {
    index++;
    if (index == where) {
      return current;
    }
  }
  return NULL;
}

// 取出链表最后的实际元素
pnode llist_last(pnode head) {
  pnode current = head;
  while (current->next != NULL) {
    current = current->next;
  }
  return current;
}
// 释放内存
void llist_free(pnode head) {
  pnode prev = NULL;
  pnode current = head;
  while (current->next != NULL) {
    prev = current;
    current = current->next;
    free(prev);
  }
  free(current);
  free(head);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注