APS105预习 - 11

Chapter 13 Linked List 链表

链表是一种数组的替代方案！

链表旨在解决数组在需要添加，删除，插入元素的时候不够灵活的问题。

链表的基础结构

链表由**节点(node)**组成，以下是一个节点的数据结构：

typedef struct node{
	int data;
  struct node *next;
} Node;

• data: 该节点中存储的数据
• *next: 下一个节点的内存地址

构建一个基础的链表

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int data;
  struct node *next;
} Node;

int main(void) {
  Node *firstNode = (Node *)malloc(sizeof(Node));
  Node *secondNode = (Node *)malloc(sizeof(Node));

  printf("Enter data for node 1: ");
  scanf("%d", &(firstNode->data));
  firstNode->next = NULL;

  printf("Enter data for node 2: ");
  scanf("%d", &(secondNode->data));
  secondNode->next = NULL;

  // link the list
  firstNode->next = secondNode;

  printf("first data: %d\n", firstNode->data);
  printf("second data: %d\n", firstNode->next->data);
  
  free(firstNode->next);
  free(firstNode);
  return 0;
}

我懒 - 链表的封装

创建节点 (增)

在创建节点的时候，我们需要为每一个节点动态分配堆上内存，所以需要用到malloc函数。

需要注意的是，malloc()并非所有时候都可以成功分配内存，它也会有分配失败的时候（通常是因为程序内存不足）。当分配不成功的时候，malloc()会返回NULL。所以，任何时候在试图使用malloc()分配的内存时候，都应当先检查指针是否有效

Node *createNode(int value) {
  Node *newNode = (Node *)malloc(sizeof(Node));
  if (newNode != NULL) {
    newNode->data = value;
    newNode->next = NULL;
  } else {
    printf("Fail to allocate memory while creating node");
  }
  return newNode;
}

以下是一个使用该函数创建节点的示例代码

int main(void) {
  Node *newNode = NULL;
  newNode = createNode(1);
  newNode->next = createNode(2);
  return 0;
}

在开头插入

bool insertAtFront(Node **headPtr, int value) {
  Node *temp = createNode(value);
  if (temp == NULL) {
    return false;  // something wrong happened while creating node
  }

  temp->next = *headPtr;
  headPtr = temp;
  return true;
}

以上是一种在链表头部插入值的办法，值得思考的是，为什么这里要使用head指针的指针？

此处使用使用的head指针的指针的原因是，我们需要修改main函数当中head的值。如果传入head的指针，然后再对其进行更改，并不能影响到main函数中head指向的值，因为head的指针是按值传递进来的

还有一个更好的解法，便是创建一个全新的数据结构来保存链表(和链表的头指针)

它长这样:

typedef struct list {
  Node *head;
} LinkedList;

bool insertAtFront(LinkedList *list, int value) {
  Node *tmp = (Node *)malloc(sizeof(Node));
  if (tmp == NULL) {
    return false;
  }

  tmp->next = list->head;
  list->head = tmp;
  return true;
}

以下是使用第二种更优办法的样例代码：

int main(void) {
  LinkedList *list = (LinkedList *)malloc(sizeof(LinkedList));
  list->head = createNode(1);
  list->head->next = createNode(2);
  insertAtFront(list, 0);
  printf("%d\n", list->head->data);
  return 0;
}

打印链表

这个函数较容易理解，故不做解释

void printList(LinkedList *list) {
  Node *current = list->head;
  while (current != NULL) {
    printf("%d -> ", current->data);
    current = current->next;
  }
  printf("NULL\n");
}

在结尾插入

bool insertAtBack(LinkedList *list, int value) {
  Node *tmp = createNode(value);
  if (tmp == NULL) {
    return false;
  }
  Node *current = list->head;
  if (current == NULL) {  // This is an empty linkedlist
    list->head = tmp;
    return true;
  }
  while (current->next != NULL) {
    current = current->next;
  }

  current->next = tmp;
  return true;
}

注意⚠️：这里需要额外判断传入的list是否是一个空链表，如果list->head == NULL的话，尝试访问list->head->next将会导致程序崩溃。当链表为空的时候，讲新节点设为头节点即可