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

//seqlist.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
typedef struct SeqList
{
  Type* data;
  int max;
  int size;
}List;
void InitSeqList(List* l, int n);
//构造函数，建立空顺序表
void FreeSeqList(List* l) { free(l->data); }
//析构函数
void Reserve(List* l, int newmax);
//扩大数组长度
void Insert(List* l, int id, Type item);
//定点插入
void PushFront(List* l, Type item) { Insert(l, 0, item); }
//首插
void PushBack(List* l, Type item) { Insert(l, l->size, item); }
//尾插
void Erase(List* l, int id);
//定点删除
void PopBack(List* l) { Erase(l, l->size - 1); }
//尾删
void PopFront(List* l) { Erase(l, 0); }
//首删
void Clear(List* l) { l->size = 0; }
//清表
int GetSize(const List* l) { return l->size; }
//读取数据个数
Type GetData(const List* l, int id) { return l->data[id]; }
//读取索引为id的数据
void InitSeqList(List* l, int n)
{
  l->data = (Type*)malloc(n * sizeof(Type));
  if (l->data == 0)
  {
    printf("allocation failure!\n");
    exit(1);
  }
  l->max = n;
  l->size = 0;
}
void Reserve(List* l, int newmax)
{
  int i;
  Type* old;
  if (newmax < l->max)
    return;
  old = l->data;
  l->max = newmax;
  l->data = (Type*)malloc(newmax * sizeof(Type));
  for (i = 0; i < l->max; i++)
    l->data[i] = old[i];
  free(old);
}
void Insert(List* l, int id, Type item)
{
  int i;
  if (id<0 || id>l->size)
  {
    printf("Insert:id is illegal!");
    exit(1);
  }
  if (l->size == l->max)
    Reserve(l, 2 * l->max);
  for (i = l->size; i > id; i--)
    l->data[i] = l->data[i - 1];
  l->data[id] = item;
  l->size++;
}
void Erase(List* l, int id)
{
  int i;
  if (id<0 || id>l->size - 1)
  {
    printf("Erase:id is illegal!");
    exit(1);
  }
  for (i = id + 1; i < l->size; i++)
    l->data[i - 1] = l->data[i];
  l->size--;
}
//main.c
#include<stdio.h> 
typedef int Type;
#include"seqlist.h"
void OutputArray_list(const List* l);
void Selection_list(List* l);
void Invert_list(List* l);
int main() {
  int n_size;
  int i;
  List seqlist;
  printf("Enter the size of array:\n");
  scanf_s("%d", &n_size);
  InitSeqList(&seqlist, n_size);
  printf("Enter %d integers:\n", n_size);
  for (i = 0; i < n_size; i++)
  {
    int temp;
    scanf_s("%d", &temp);
    Insert(&seqlist, i, temp);
  }
  printf("选择排序结果：\n");
  Selection_list(&seqlist);
  OutputArray_list(&seqlist);
  printf("逆置结果：\n");
  Invert_list(&seqlist);
  OutputArray_list(&seqlist);
  return 0;
}
void OutputArray_list(const List* l)
{
  int n = GetSize(l);
  int i;
  for (int i = 0; i < n; i++)
    printf("%d\t", GetData(l, i));
  printf("\n");
}
void Selection_list(List* l)
{
  int n = GetSize(l);
  while (n > 1)
  {
    int max = 0;//选择排序最大值的索引
    for (int i = 1; i < n; i++)
    {
      if (GetData(l, max) < GetData(l, i))
        max = i;
    }
    int item = GetData(l, max);//要删除再重新插入的最大值
    Erase(l, max);//定点删除
    Insert(l, n - 1, item);//定点插入到无序顺序表的最后一个
    n--;
  }
}
void Invert_list(List* l)
{
  int n = GetSize(l);
  int left = 0;
  int right = n - 1;
  int temp;
  for (; left < right; left++, right--)
  {
    temp = GetData(l, left);
    Erase(l, left);
    //删除后数据前移一位，size-1
    Insert(l, left, GetData(l, right - 1));
    //第一次换位，虽然数据前移了但是right和right-1的值相等，结果是正确的
    //但是第一次换位后，第二次的删除操作使right前移一位
    //如果没有减一就会导致实际上的right（第二次操作移到left的值）是right+1
    //去掉减一运行观察一下就懂了
    Erase(l, right);
    Insert(l, right, temp);
  }
}