【霍罗维兹数据结构】单链表 | 动态链接的栈和队列 | 多项式 - POLYNOMIALS

前言：

最近在读霍罗维兹的《数据结构基础》（Fundamentals of Data Structures in C），本篇博客为阅读笔记和知识总结。

Ⅰ. 重温一些指针的知识

Sequential representation

将数据对象的连续元素以固定的距离存储起来。

足以满足许多操作。

But difficulties occurs when

但是，当插入和删除一个任意元素时就会出现困难（耗时）。

将几个大小不一的列表存储在最大尺寸的不同数组中（浪费存储）

将列表维持在一个数组中（频繁的数据移动）

Linked representation

链接表示一个节点，与列表中的一个元素相关，包含一个数据成分和一个指向列表中下一个项目的指针，这些指针通常被称为链接。

C提供了对指针的广泛支持，指针类型的实际值是内存的一个地址。

引用操作符 &

解引用操作符 *

int i, *pi;
pi = &i;

为 i 赋值：

i = 10;
*pi = 10;

C允许我们对指针进行算术运算和关系运算。此外，我们还可以将指针明确地转换为整数。

空指针，是不指向任何对象或函数。

通常情况下，空指针由整数0表示。有一个叫做NULL的宏，它被定义为这个常数。

ANSI C，该宏定义在 stddef.h 中；K&R C中，该宏定义在stdio.h中。

// 测试空指针
if (pi == NULL) or if (!pi)

Pointers Can Be Dangerous

通过使用指针，我们可以达到高度的灵活性和效率。

但指针也有危险：访问意外的内存位置当指针实际上没有指向一个对象时，将所有指针设置为NULL。

在指针类型之间转换时，明确地进行类型转换。

pi = malloc(sizeof(int)); /* assign to pi a pointer to int */
pf = (float *) pi; /* casts an int pointer to a float pointer */

为函数定义明确的返回类型。

Using Dynamically Allocated Storage

malloc / free

[Program 4.1]

int i, *pi;
float f, *pf;
pi = (int *) malloc(sizeof(int));
pf = (float *) malloc(sizeof(float));
*pi = 1024;
*pf = 3.14;
printf("an integer = %d, a float = %f\n", *pi, *pf);
free(pi);
free(pf);
inserting pf = (float *) malloc(sizeof(float));

Ⅱ. 单链表

链表中第一个节点的指针的名称就是列表的名称。

值得注意的是：① 节点不在连续的位置上。 ② 节点的位置可能在不同的运行中发生变化。

当我们写一个与链表有关的程序时，除了测试链表的结尾外，我们几乎不会去找一个特定的地址。

要在 cat 和 sat 之间插入 mat 这个词，我们必须：

(1) 获得一个目前未使用的节点；让它的地址为paddr。

(2) 将这个节点的数据字段设置为mat。

(3) 设置paddr的链接字段指向包含cat的节点的链接字段中找到的地址。

(4) 将包含cat的节点的链接字段设置为指向paddr的指针。

要在 cat 和 sat 之间插入mat这个词，我们必须：

(1) 获得一个目前未使用的节点；让它的地址为paddr。

(2) 将这个节点的数据字段设置为mat。

(3) 设置paddr的链接字段指向包含cat的节点的链接字段中找到的地址。

(4) 将包含cat的节点的链接字段设置为指向paddr的指针。

从列表中删除mat：

(1) 找到紧接在mat前面的元素（节点），也就是cat。

(2) 设置cat的链接字段为指向mat的链接字段。

Necessary capabilities to make linked list possible :

(1) 一个定义节点结构的机制，自引用结构。

(2) 一种在我们需要时创建新节点的方法，malloc。

(3) 一种移除我们不再需要的节点的方法，free

Example 4.1 [List of words ending in at]

// Necessary declarations are :
typedef struct list_node *list_pointer;
typedef struct list_node {
    char data[4];
    list_pointer link;
};
list_pointer ptr = NULL; /* creating a new empty list */

用于测试链表是否为空的宏 - A macro to test for an empty list

#define IS_EMPTY(ptr) (!(ptr))

创建新节点 - Creating new nodes

可以用 stdio.h 中的 malloc

ptr = (list_pointer) malloc (sizeof(list_node));

Assigning the values to the fields of the node

e 是一个指向包含字段名的结构的指针，e->name 可以当作是 (*e).name 的简写。

To place the word bat into the list

strcpy (ptr->data, "bat");
ptr->link = NULL;

Example 4.2 [Two-node linked list] :

typedef struct list_node* list_pointer;
typedef struct list_node {
  int data;
  list_pointer link;
};
list_pointer ptr = NULL;

[Program 4.2]

list_pointer create2()
{
  /* create a linked list with two nodes */
  list_pointer first, second;
  first = (list_pointer)malloc(sizeof(list_node));
  second = (list_pointer)malloc(sizeof(list_node));
  second->link = NULL;
  second->data = 20;
  first->data = 10;
  first->link = second;
  return first;
}

Example 4.3 [List insertion] :

在某个任意节点之后插入一个数据域为50的节点。注意，我们使用参数声明 list_pointer *ptr。

我们写一个新的宏，IS_FULL，用来判断是否使用了已用的内存。

#define IS_FULL (ptr) (!(ptr))

[Program 4.3]

void insert(list_pointer* ptr, list_pointer node)
{
  /* insert a new node with data=50 into the list ptr after node */
  list_pointer temp;
  temp = (list_pointer)malloc(sizeof(list_node));
  if (IS_FULL(temp)) {
    fprintf(stderr, "The memory is full\n");
    exit(1);
  }
  temp->data = 50;
  if (*ptr) {
    temp->link = node->link;
    node->link = temp;
  }
  else {
    temp->link = NULL;
    *ptr = temp;
  }
}

Example 4.4 [List deletion]

删除取决于要删除的节点的位置。

设有三个指针：

ptr：指向列表的开始。

node：指向我们要删除的节点。

trail：指向要删除的节点之前的那个节点。

[Program 4.4]

void delete(list_pointer* ptr, list_pointer trail, list_pointer node)
{
  /* delete node from the list, trail is the preceding node
  ptr is the head of the list */
  if (trail)
    trail->link = node->link;
  else
    *ptr = (*ptr)->link;
  free(node);
}

Example 4.5 [Printing out a list] :

[Program 4.5]

void print_list(list_pointer ptr)
{
  printf("The list contains: ");
  for (; ptr; ptr = ptr->link)
    printf("%4d", ptr->data);
  printf("\n");
}
list_pointer search(list_pointer ptr, int num)
{
  for (; ptr; ptr = ptr->link)
    if (ptr->data == num) return ptr;
  return ptr;
}
void merge(list_pointer x, list_pointer y, list_pointer* z)
{
  list_pointer last;
  last = (list_pointer)malloc(sizeof(list_node));
  *z = last;
  while (x && y) {
    if (x->data <= y->data) {
      last->link = x;
      last = x;
      x = x->link;
    }
    else {
      last->link = y;
      last = y;
      y = y->link;
    }
  }
  if (x) last->link = x;
  if (y) last->link = y;
  last = *z; *z = last->link; free(last);
}

Ⅲ. 动态链接的栈和队列

如果我们只有一个栈或一个队列，我们可以用顺序表。

但是当几个栈和队列并存时，我们就需要动态链接他们。

注意，栈和队列的链接方向都是便于节点的插入和删除的。

#define MAX_STACKS 10 /* maximum number of stacks */
typedef struct {
  int key;
  /* other fields */
} element;
typedef struct stack* stack_pointer;
typedef struct stack {
  element item;
  stack_pointer link;
};
stack_pointer top[MAX_STACKS];

initialize empty stacks

top[i] = NULL, 0<=i<MAX_STACKS

the boundary conditions

top[i] == NULL iff the i th stack is empty
IS_FULL(temp) iff the memory is full

[Program 4.6]

void add(stack_pointer* top, element item)
{
  /* add an element to the top of the stack */
  stack_pointer temp = (stack_pointer)malloc(sizeof(stack));
  if (IS_FULL(temp)) {
    fprintf(stderr, "The memory is full\n");
    exit(1);
  }
  temp->item = item;
  temp->link = *top;
  *top = temp;
}

call : add(&top[stack_no], item);

[Program 4.7]

element delete(stack_pointer* top)
{
  /* delete an element from the stack */
  stack_pointer temp = *top;
  element item;
  if (IS_EMPTY(temp)) {
    fprintf(stderr, "The stack is empty\n");
    exit(1);
  }
  item = temp->item;
  *top = temp->link;
  free(temp);
  return item;
}

call : item = delete(&top[stack_no]);

#define MAX_QUEUES 10 /* maximum number of queues */
typedef struct {
  int key;
  /* other fields */
} element;
typedef struct queue* queue_pointer;
typedef struct queue {
  element item;
  queue_pointer link;
};
queue_pointer front[MAX_QUEUES], rear[MAX_QUEUES];

initialize empty queues

front[i] = NULL, 0<=i<MAX_QUEUES

the boundary conditions

front[i] == NULL iff the i th queue is empty
IS_FULL(temp) iff the memory is full

[Program 4.8] call : addq(&front[queue_no], &rear[queue_no], item);

void addq(queue_pointer* front, queue_pointer* rear, element item)
{
  /* add an element to the rear of the queue */
  queue_pointer temp = (queue_pointer)malloc(sizeof(queue));
  if (IS_FULL(temp)) {
    fprintf(stderr, "The memory is full\n");
    exit(1);
  }
  temp->item = item;
  temp->link = NULL;
  if (*front) (*rear)->link = temp;
  else *front = temp;
  *rear = temp;
}

[Program 4.9] call : item = deleteq(&front[queue_no]);

element deleteq(queue_pointer* front)
{
  /* delete an element from the queue */
  queue_pointer temp = *front;
  element item;
  if (IS_EMPTY(*front)) {
    fprintf(stderr, "The queue is empty\n");
    exit(1);
  }
  item = temp->item;
  *front = temp->link;
  free(temp);
  return item;
}

Ⅳ. 多项式 - POLYNOMIALS

0x00 Representing Polynomials As Singly Linked Lists

typedef struct poly_node* poly_pointer;
typedef struct poly_node {
  float coef;
  int expon;
  poly_pointer link;
};
poly_pointer a, b, d;

0x01 Adding Polynomials

[Program 4.10]

poly_pointer padd(poly_pointer a, poly_pointer b)
{
  /* return a polynomial which is the sum of a and b */
  poly_pointer front, rear, temp;
  float sum;
  rear = (poly_pointer)malloc(sizeof(poly_node));
  if (IS_FULL(rear)) {
    fprintf(stderr, “The memory is full\n”);
    exit(1);
  }
  front = rear;
  while (a && b)
    switch (COMPARE(a->expon, b->expon)) {
    case –1: /* a->expon < b->expon */
      attach(b->coef, b->expon, &rear);
      b = b->link; break;
    case 0: /* a->expon = b->expon */
      sum = a->coef + b->coef;
      if (sum) attach(sum, a->expon, &rear);
      a = a->link; b = b->link; break;
    case 1: /* a->expon > b->expon */
      attach(a->coef, a->expon, &rear);
      a = a->link;
    }
  /* copy rest of list a then list b */
  for (; a; a = a->link) attach(a->coef, a->expon, &rear);
  for (; b; b = b->link) attach(b->coef, b->expon, &rear);
  rear->link = NULL;
  /* delete extra initial node */
  temp = front; front = front->link; free(temp);
  return front;
}

[Program 4.11]

void attach(float coefficient, int exponent, poly_pointer* ptr)
{
  /* create a new node with coef = coefficient and
  expon = exponent, attach it to the node pointed to
  by ptr. ptr is updated to point to this new node */
  poly_pointer temp;
  temp = (poly_pointer)malloc(sizeof(poly_node));
  if (IS_FULL(temp)) {
    fprintf(stderr, "The memory is full\n");
    exit(1);
  }
  temp->coef = coefficient;
  temp->expon = exponent;
  (*ptr)->link = temp;
  *ptr = temp;
}

分析 padd

和之前说的多项式的padd类似

(1) 添加系数 (2) 指数比较 (3) 为d创建新节点

时间复杂度为

0x02 Erasing Polynomials

假设我们正在编写一个函数集合，用于输入、加法、减法和多项式的乘法，用链表。

注意，我们创建多项式 temp(x) 只是为了保存 d(x) 的部分结果。

通过返回 emp(x) 的节点，我们可以用它们来保存其他多项式。

[Program 4.12]

void erase(poly_pointer* ptr)
{
  /* erase the polynomial pointed by ptr */
  poly_pointer temp;
  while (*ptr) {
    temp = *ptr;
    *ptr = (*ptr)->link;
    free(temp);
  }
}

0x03 Representing Polynomials As Circularly Linked Lists

为了更有效地释放一个多项式的所有节点，我们修改了我们的链表结构，使最后一个节点的链接字段指向列表中的头节点。

我们想释放不再使用的节点，以便我们以后可以重新使用这些节点。我们可以通过维护我们自己的已被 "释放 "的节点的列表（作为一个链），获得一个高效的循环链表 erase 的算法。当我们需要一个新的节点时，我们检查这个列表。如果这个列表不是空的，那么我们可以使用其中的一个节点。只有当列表为空时，才使用 malloc 来创建一个新节点。让 avail 成为一个 poly_pointer 类型的变量，指向已释放节点列表中的第一个节点。

[Program 4.13]

poly_pointer get_node(void) {
  /* provide a node for use */
  poly_pointer node;
  if (avail) {
    node = avail;
    avail = avail->link;
  }
  else {
    node = (poly_pointer)malloc(sizeof(poly_node));
    if (IS_FULL(node)) {
      fprintf(stderr, "The memory is full\n");
      exit(1);
    }
  }
  return node;
}

[Program 4.14]

void ret_node(poly_pointer ptr) {
  /* return a node to the available list */
  ptr->link = avail;
  avail = ptr;
}

[Program 4.15]

void cerase(poly_pointer* ptr) {
  /* erase the circular list ptr */
  poly_pointer temp;
  if (*ptr) {
    temp = (*ptr)->link;
    (*ptr)->link = avail;
    avail = temp;
    *ptr = NULL;
  }
}

我们必须把零多项式作为一种特殊情况来处理。我们在每个多项式中引入一个头部节点。

对于有头节点表示的循环链表，我们可以从 cerase 中删除对 (*ptr) 的测试。

我们需要对padd做出的改变是:

(1) Add two variables, starta = a and startb = b.
(2) Prior to the while loop, assign a = a->link and b = b->link.
(3) Change the while loop to while (a != starta && b != startb).
(4) Change the first for loop to for (; a != starta; a = a->link).
(5) Change the second for loop to for (; b != startb; b = b->link).
(6) Delete the lines :
rear -> link = NULL;
/* delete extra initial node */
(7) Change the lines :
temp = front;
front = front -> link;
free(temp);
to
rear -> link = front;
We may further simplify the addition algorithm
if we set the expon field of the head node to -1.

[Program 4.16]

poly_pointer cpadd(poly_pointer a, poly_pointer b)
{
  /* polynomials a and b are singly linked circular lists with a head
  node. Return a polynomial which is the sum of a and b */
  poly_pointer starta, d, lastd;
  int sum, done = FALSE;
  starta = a; /* record start of a */
  a = a->link; /* skip head node for a and b */
  b = b->link;
  d = get_node(); / (get a head node for sum* /
    d->expon = -1; lastd = d;
  do {
    switch (COMPARE(a->expon, b->expon)) {
    case –1: /* a->expon < b->expon */
      attach(b->coef, b->expon, &lastd);
      b = b->link; break;
    case 0: /* a->expon = b->expon */
      if (starta == a) done = TURE;
      else {
        sum = a->coef + b->coef;
        if (sum) attach(sum, a->expon, &lastd);
        a = a->link; b = b->link;
      }
      break;
    case 1: /* a->expon > b->expon */
      attach(a->coef, a->expon, &lastd);
      a = a->link;
    }
  } while (!done)
    lastd->link = d;
  return d;
}

Ⅴ. 其他操作

0x00 Operations For Chains

用于操作单链表的各种函数通常是必要的，也是可取的。我们已经看到了 get_node 和 ret_node。

我们使用如下声明：

typedef struct list_node* list_pointer;
typedef struct list_node {
  char data;
  list_pointer link;
};

0x01 反转链表 - Inverting a chain

如果我们使用三个指针，我们可以 "原地 "进行倒转。

[Program 4.17]

list_pointer invert(list_pointer lead)
{
  /* invert the list pointed to by lead */
  list_pointer middle, trail;
  middle = NULL;
  while (lead) {
    trail = middle;
    middle = lead;
    lead = lead->link;
    middle->link = trail;
  }
  return middle;
}

0x02 链接两个链表 - Concatenating two chains

[Program 4.18]

list_pointer concatenate(list_pointer ptr1, list_pointer ptr2)
{
  /* produce a new list that contains the list ptr1 followed
  by the list ptr2. The list pointed to by ptr1 is changed
  permanently */
  list_pointer temp;
  if (IS_EMPTY(ptr1)) return ptr2;
  else {
    if (!IS_EMPTY(ptr2)) {
      for (temp = ptr1; temp->link; temp = temp->link)
        ;
      temp->link = ptr2;
    }
    return ptr1;
  }
}

Ⅵ. 循环链表的操作

在一个循环链表的前面插入一个新节点。由于我们必须改变最后一个节点的链接字段，我们必须在链表中向后移动，直到找到最后一个节点。如果循环链表的名称指向的是最后一个节点，而不是第一个节点，那就会更方便。

[Program 4.19]

void insert_front(list_pointer* ptr, list_pointer node)
/* insert node at the front of the circular list ptr,
where ptr is the last node in the list. */
{
  if (IS_EMPTY(*ptr)) {
    /* list is empty, change ptr to point to new entry */
    *ptr = node;
    node->link = node;
  }
  else {
    /* list is not empty, add new entry at front */
    node->link = (*ptr)->link;
    (*ptr)->link = node;
  }
}

在循环链表的后部插入一个新的节点：

我们只需要在 insert_front 的 else 子句中添加语句 *ptr = node 即可。

[Program 4.20]

int length(list_pointer ptr)
{
  /* find the length of the circular list ptr */
  list_pointer temp;
  int count = 0;
  if (ptr) {
    temp = ptr;
    do {
      count++;
      temp = temp->link;
    } while (temp != ptr);
  }
  return count;
}

参考资料：

Fundamentals of Data Structures in C

本章完。

【霍罗维兹数据结构】单链表 | 动态链接的栈和队列 | 多项式 - POLYNOMIALS | 一些链表的操作