基数排序算法实现

这个是《数据结构与算法C语言实现》的链表内容
radixSort.h

#ifndef RADIX_SORT_H
#define RADIX_SORT_H

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

typedef Node Head;

void insert(const Head head, const Node newNode);
void deleteNode(const Head head, Node delNode);
void displayAll(const Head *);
#endif

radixSort.c

#include "radixSort.h"
#define N 10

// 在链表的最后插入一个节点,这个aNode需要是malloc出来的，因为是传址，不是传值
void insert(Head head, Node aNode)
{
  if (head->next == NULL)
  {
    head->next = aNode;
    aNode->next = NULL;
  }
  else
  {
    //得到链表最后节点
    Node tmpNode = head->next;
    while (tmpNode->next != NULL)
    {
      tmpNode = tmpNode->next;
    }
    printf("末尾插入节点 %d n", aNode->num);
    tmpNode->next = aNode;
    aNode->next = NULL;
  }
}

// 在链表中删除节点delNode
void deleteNode(const Head head, const Node delNode)
{
  // 如果head本身就是空，那么什么也不做
  if (head->next != NULL)
  {
    // 找到和delNode->num相同的节点
    Node tmpNode = head->next;
    Node prevNode = head;
    while (tmpNode->next != NULL && tmpNode->num != delNode->num)
    {
      prevNode = tmpNode;
      tmpNode = tmpNode->next;
    }

    if(tmpNode->next == NULL && tmpNode->num != delNode->num)
    {
      printf("没有找到aNode !!! n");
      fflush(stdout);
    }
    else if (tmpNode->next == NULL && tmpNode->num == delNode->num)
    {
      printf("在链表 《最后》 找到aNode %d,删除之 !!! n", tmpNode->num);
      prevNode->next = tmpNode->next;
      // free(tmpNode);
    }
    else if (tmpNode->num == delNode->num)
    {
      printf("在链表 《中间》 找到aNode %d,删除之 !!! n", tmpNode->num);
      prevNode->next = tmpNode->next;
      // free(tmpNode);
    }

    
    
  }
}

void displayAll(const Head * head)
{  
  printf("n==============================n");
  for(int i = 0; i < N; i++)
  {
    // printf("head %d,%p,%p-", i, *(head + i),(*(head + i))->next);
    printf("head %d : ", i);
    fflush(stdout);
    Node tempNode = (*(head + i))->next;
    if (tempNode != NULL)
    {
      // printf("%d,%p,%p>", tempNode->num, tempNode, tempNode->next);
      printf("%d->", tempNode->num);
      fflush(stdout);
      while(tempNode->next != NULL)
      {
        // printf("%d,%p,%p>", tempNode->num, tempNode, tempNode->next);
        printf("%d->", tempNode->next->num);
        fflush(stdout);
        tempNode = tempNode->next;
      }
    }
    printf("n");
  }
  printf("==============================n");
}

radixSortTest.c

#include 
#include 
#include "radixSort.c"
#include 
#include 

#define M 10
#define P 3 // P是numbers中最大数的N^P的次数

int main()
{
  int numbers[M] = {64, 878, 265, 512, 27, 730, 0, 1, 343, 898};
  Head *head = (Head *)malloc(sizeof(Head *) * N);

  // 建立一个指向Head的指针
  for (int i = 0; i < N; i++)
  {
    Head tmpHead = (Head)malloc(sizeof(Head));
    tmpHead->num = i;
    tmpHead->next = NULL;
    *(head + i) = tmpHead;
    // printf("%d is , next is %x n", (*(head + i))->num, (*(head + i))->next);
  }

  // 把numbers数组中的数字装入链表的节点中，并插入到*(head+i)后
  for (int i = 0; i < N; i++)
  {
    Node tmpNode = (Node)malloc(sizeof(Node)); // 这里Node和struct node 一样？
    tmpNode->num = numbers[i];
    tmpNode->next = NULL;
    // printf("%d - %x n", tmpNode->num, tmpNode->next);
    int geWei = tmpNode->num % 10;
    assert(geWei >= 0);
    assert(geWei < N);
    insert(*(head + geWei), tmpNode);
  }

  displayAll(head);

  // 开始遍历
  for (int j = 1; j < P; j++)
  {
    // 从第一个链表开始遍历，先比较十位（j == 1），后比较百位(j == 2)
    if (j == 1)
    {
      printf("从 十位 开始比较 n");
      getchar();
    }
    else
    {
      printf("从 百位 开始比较 n");
      getchar();
    }

    for (int i = 0; i < N; i++)
    {
      Node aNode = (*(head + i))->next;

      //如果链表不空
      if (aNode != NULL)
      {
        printf("n对节点 %d 进行操作 n", aNode->num);
        int wei = (aNode->num / (int)pow(10, j)) % 10;
        assert(wei >= 0);
        assert(wei < 10);

        if (wei == i)
          aNode = aNode->next;
        else
        {
          // aNode 不是最后一个节点
          while (aNode->next != NULL)
          {
            wei = (aNode->num / (int)pow(10, j)) % 10;
            assert(wei >= 0);
            assert(wei < 10);

            // 在链表 *（head +i) 上删除节点aNode
            printf("head %d:::delete %d  n", i, aNode->num);
            deleteNode(*(head + i), aNode);

            // 在链表 *（head + wei)上插入节点aNode
            printf("head %d:::insert %d  n", wei, aNode->num);

            Node insertNode = (Node)malloc(sizeof(Node));
            insertNode->next = aNode->next;
            insertNode->num = aNode->num;
            insert(*(head + wei), insertNode);

            Node node2free = aNode;
            aNode = aNode->next;
            free(node2free);

            displayAll(head);
          }

          // aNode 是最后一个节点
          if (aNode->next == NULL)
          {
            wei = (aNode->num / (int)pow(10, j)) % 10;
            assert(wei >= 0);
            assert(wei < 10);

            // 在链表 *（head +i) 上删除节点aNode
            printf("head %d:::delete last %d n", i, aNode->num);
            deleteNode(*(head + i), aNode);

            // 在链表 *（head + wei)上插入节点aNode
            printf("head %d:::insert last %d n", wei, aNode->num);

            Node insertNode = (Node)malloc(sizeof(Node));
            insertNode->next = aNode->next;
            insertNode->num = aNode->num;
            insert(*(head + wei), insertNode);
            displayAll(head);
            getchar();

            Node node2free = aNode;
            aNode = aNode->next;
            free(node2free);
            displayAll(head);
            getchar();
          }
        }
      }
    }
  }

  return 0;
}