C语言程序设计(王立柱）第八章答案 链表

#pragma once
//node.h
#include<stdlib.h>
typedef struct Node{
  Type data;
  struct Node* prev;
  struct Node* next;
}Node;
Node* GetNode(Type item, Node* p, Node* n);
Type GetData(Node* itr) { return itr->data; }
Node* GetPrev(Node* itr) { return itr->prev; }
Node* GetNext(Node* itr) { return itr->next; }
Node* GetNode(Type item, Node* p, Node* n) {
  Node* re;
  re = (Node*)malloc(sizeof(Node));
  re->data = item;
  re->prev = p;
  re->next = n;
  return re;
}
#pragma once
//list.h
#include"node.h"
typedef struct {
  Node* head;
  Node* tail;
  int size;
}List;
void InitList(List* l);             //准构造函数，建立空表
int Size(List* l) { return l->size; }
int Empty(List* l) { return l->size == 0; }
//读取区间边界
Node* Begin(List* l) { return l->head->next; }  //读取数据首节点指针
Node* End(List* l) { return l->tail; }      //读取链表尾节点指针
Node* Insert(List* l, Node* itr, Type item);  //定点插入到itr前面
void PushFront(List* l, Type item) { Insert(l, Begin(l), item); }//首插
void PushBack(List* l, Type item) { Insert(l, End(l), item); }//尾插
Node* Erase(List* l, Node* itr);        //删除itr指向的结点，返回后继指针
void PopFront(List* l) { Erase(l, Begin(l)); }  //首删
void PuopBack(List* l) { Erase(l, GetPrev(End(l))); }//尾删
void Clear(List* l) { while (!Empty(l))PopFront(l); }//清表
void FreeList(List* l) { Clear(l); free(l->head); free(l->tail); }//准析构函数
void InitList(List* l) {
  l->head = GetNode(0, NULL, NULL);
  l->tail = GetNode(0, 0, 0);
  l->head->next = l->tail;
  l->tail->prev = l->head;
  l->size = 0;
}
Node* Insert(List* l, Node* itr, Type item) {
  //Node* p = itr;
  itr->prev->next = GetNode(item, itr->prev, itr);
  itr->prev = itr->prev->next;
  l->size++;
  return itr->prev;
}
Node* Erase(List* l, Node* itr) {
  //Node* p = itr;
  Node* re = itr->next;
  itr->prev->next = itr->next;
  itr->next->prev = itr->prev;
  free(itr);
  l->size--;
  return re;
}
//Josephus.c
#include<stdio.h>
#include<time.h>
typedef int Type;
#include"list.h"
void OutputList(List* l);
void Josephus(int n);
int main() {
  int n;
  printf("Enter the number of people:\n");
  scanf("%d", &n);
  Josephus(n);
  return 0;
}
void OutputList(List* l) {
  Node* first = Begin(l);
  Node* last = End(l);
  for (; first != last; first = GetNext(first))
    printf("%d\t", GetData(first));
  printf("\n");
}
void Josephus(int n) {
  int counter;          //计数器
  int step;           //随机步长
  Node* first;
  Node* last;
  List Party;           //参与者
  List Loser;           //淘汰者
  List Odd;           //随机步长
  InitList(&Party);
  InitList(&Loser);
  InitList(&Odd);
  for (counter = 1; counter <= n; counter++)
    PushBack(&Party, counter);  //参赛者输入
  printf("Party:\n");       //参赛者输出
  OutputList(&Party);
  srand(time(0));
  first = Begin(&Party);      //数据首结点
  last = End(&Party);       //链表尾结点
  while (Size(&Party) > 1) 
  {
    step = 1 + rand() % 10;
    PushBack(&Odd, step);
    for (counter = 1; counter < step; counter++) {
      first = GetNext(first);     //计算步数一步步把first移到淘汰者处
      if (first == last)        //把链表尾结点转到数据首结点
        first = Begin(&Party);
    }
    PushBack(&Loser,GetData(first));        //淘汰者入Loser
    first = Erase(&Party, first);   //淘汰者淘汰
    if (first == last)        //把链表尾结点转到数据首结点
      first = Begin(&Party);
  }
  printf("Odds:\n");
  OutputList(&Odd);
  printf("Loser:\n");
  OutputList(&Loser);
  printf("Winner:\n");
  printf("%d\n", *Begin(&Party));
//用 printf 语句来打印结构体类型的变量，结果是 undefined behavior！
//什么是未定义行为，就是说发生任何状况都是可能的，这个就要看编译器的实现方式了。
//当然改成GetData(Begin(&Party))就没问题了。
  FreeList(&Party);
  FreeList(&Loser);
  FreeList(&Odd);
}

#include<stdio.h>
typedef int Type;
#include"list.h"
void OutputList(const List* l);
void Selection(List* l);
void Copy(const List* lo, List* lt);
Node* MaxOfNode(Node* n);
int main() {
  int n;
  int i;
  List lo;
  List lt;
  InitList(&lo);
  InitList(&lt);
  int temp = 0;
  printf("输入链表长度n和n个整数：\n");
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &temp);
    PushBack(&lo, temp);
  }
  Selection(&lo);
  Copy(&lo, &lt);
  OutputList(&lo);
  OutputList(&lt);
  FreeList(&lo);
  FreeList(&lt);
  return 0;
}
void OutputList(const List* l) {
  Node* first = Begin(l);
  Node* last = End(l);
  for (; first != last; first = GetNext(first))
    printf("%d\t", GetData(first));
  printf("\n");
}
Node* MaxOfNode(Node* n) {
  int i;
  Node* temp = n;
  Node* max = temp;
  while (temp->next->next != 0) {//temp最多为倒数第二个数据结点
    if (GetData(max) < GetData(temp->next))
      max = temp->next;
    temp = temp->next;
  }
  return max;
}
void Selection(List* l) {
  Node* max;
  Node* temp = Begin(l);//temp是从第一个到倒数第二个数据节点的定位标
  while (temp->next->next != 0) {//temp最多为倒数第二个数据结点
    max = MaxOfNode(temp);
    if (max == temp) {
      temp = temp->next;
      PushFront(l, GetData(temp->prev));
      Erase(l, temp->prev);
    }
    else {
      PushFront(l, GetData(max));
      Erase(l, max);
    }
  }
  PushFront(l, GetData(End(l)->prev));
  Erase(l, End(l)->prev);
}
void Copy(const List* lo, List* lt) {
  Node* one = Begin(lo);
  while (one->next != 0) {
    PushBack(lt, GetData(one));
    one = one->next;
  }
}