03.26 实现一个链接存储的线性表-数据结构与算法课堂项目

任务详情

任务描述

本关任务：完成一个链接存储的线性表的小程序

相关知识

线性表的存储也可以采用链接存储方式来实现。链接存储方式包括单链表、双链表和循环链表等形式。

下面描述了一种基于单链表的线性表实现方案：

为了讨论简单，假设数据元素的类型为整型：

typedef int T;

在链表中，每个数据元素为一个链表结点，结点的具体定义为：

struct LinkNode {

    T data;

    LinkNode* next;

};

如上面的单链表示意图所示，一个链表主要有front、rear、curr、position和len等属性要素组织成一个结构：

front：指向链表的首结点；

rear：指向尾结点；

curr：指向操作的当前位置（见后文特别说明）的结点；

pre：指向当前位置的前一个结点；

position：是当前位置的编号（编号从 0 开始）；

len：数据元素的个数（即链表的长度）。

基于这些属性要素，可以将线性表组织为一个链表结构：

struct LinkList {

    LinkNode* front;  // 指向头结点

    LinkNode* rear;   // 指向尾结点

    LinkNode* pre;    // 指向当前位置结点的前一个结点

    LinkNode* curr;   // 指向当前位置结点

    int position;     // 当前位置结点的编号

    int len;          // 线性表的大小（链表结点数）

};

给定指向该结构的一个指针llist，就可以对链接存储的线性表进行操作。

特别说明：

“当前位置”：当前位置由curr指针给出，当前位置的前一个位置由pre指针给出，当前位置的编号由position给出。后面将定义的若干操作与当前位置有关，例如：在当前位置结点之前插入结点，在当前位置结点之后插入结点，等等。当为空链表时，curr和pre都为空指针，position为0。当前位置在非空链表的最左端时，pre为空指针，curr指向头结点，position=0。当前位置在非空链表的最右端时，pre指向尾结点，curr为空指针，position等于len。

针对链表数据，我们定义如下操作：

创建空线性表：创建一个链接存储的线性表，初始为空表，返回llist指针。具体操作函数定义如下：
- LinkList* LL_Create()
释放线性表结点：释放链表的结点，然后释放llist所指向的结构。具体操作函数定义如下：
- void LL_Free(LinkList* llist)
置空线性表：释放链表的所有结点，将当前线性表变为一个空表。具体操作函数定义如下：
- void LL_MakeEmpty(LinkList* llist)
获取线性表当前长度：返回线性表的当前长度。具体操作函数定义如下：
- int LL_Length(LinkList* llist)
判断线性表是否为空：若当前线性表是空表，则返回true，否则返回false。具体操作函数定义如下：
- bool LL_IsEmpty(LinkList* llist)
设置线性表当前位置：设置线性表的当前位置为i号位置。设置成功，则返回true，否则返回false（线性表为空，或i不在有效范围）。假设线性表当前长度为len，那么i的有效范围为[0,len]。具体操作函数定义如下：
- bool LL_SetPosition(LinkList* llist, int i)
获取线性表当前位置结点编号：获取线性表的当前位置结点的编号。具体操作函数定义如下：
- int LL_GetPosition(LinkList* llist)
设置线性表当前位置的下一位置为当前位置：设置成功，则返回true，否则返回false（线性表为空，或当前位置为表尾）。具体操作函数定义如下：
- bool LL_NextPosition(LinkList* llist)
获取线性表当前位置的数据元素的值：具体操作函数定义如下：
- T LL_GetAt(LinkList* llist)
修改线性表当前位置数据元素的值：将线性表的当前位置的数据元素的值修改为x。具体操作函数定义如下：
- void LL_SetAt(LinkList* llist, T x)
在线性表当前位置之前插入数据元素：在线性表的当前位置之前插入数据元素x。空表允许插入，当前位置指针将指向新结点。若插入失败，返回false，否则返回true。具体操作函数定义如下：
- bool LL_InsAt(LinkList* llist, T x)
在线性表当前位置之后插入数据元素：在线性表的当前位置之后插入数据元素x。空表允许插入，当前位置指针将指向新结点。若插入失败，返回false，否则返回true。具体操作函数定义如下：
- bool LL_InsAfter(LinkList* llist, T x)
删除线性表当前位置数据元素结点：若删除失败（为空表），则返回false，否则返回true。具体操作函数定义如下：
- bool LL_DelAt(LinkList* llist)
删除线性表当前位置后面的那个数据元素结点：若删除失败（为空表，或当前位置是表尾），则返回false，否则返回true。具体操作函数定义如下：
- bool LL_DelAfter(LinkList* llist)
查找线性表中第一个值为x的数据元素的编号：返回值-1表示没有找到，返回值>=0表示编号。具体操作函数定义如下：
- int LL_FindValue(LinkList* llist, T x)
删除线性表中第一个值为x的数据元素：删除第一个值为x的数据元素，返回该数据元素的编号。如果不存在值为x的数据元素，则返回-1。具体操作函数定义如下：
- int LL_DelValue(LinkList* llist, T x)
打印整个线性表：具体操作函数定义如下：
- void LL_Print(LinkList* llist)

编程要求

本关任务是实现 step2/LinkList.cpp中的LL_InsAfter操作函数，以实现线性表数据插入功能。具体要求如下：

在线性表的当前位置之后插入数据元素x。空表允许插入，当前位置指针将指向新结点。若插入失败，返回false，否则返回true；

输入输出格式请参见后续测试样例。

注意：本关必读中提及的其他操作函数已经由平台实现，你在实现操作函数LL_InsAfter时，在函数体内可调用其他操作函数。

本关涉及的 LinkList.cpp 中的LL_InsAfter操作函数的代码框架如下：

bool LL_InsAfter(LinkList* llist, T x)
// 在线性表的当前位置之后插入数据元素x。空表允许插入。当前位置指针将指向新结点。若插入失败，返回false，否则返回true。

{

    // 请在这里补充代码，完成本关任务

    /********** Begin *********/

    /********** End **********/

}

测试说明

本关的测试文件是 step2/Main.cpp ，负责对你实现的代码进行测试。具体代码如下：

#include <stdio.h>

#include <stdlib.h>

#include "LinkList.h"

#pragma warning(disable:4996)

int main()

{

    //创建一个线性表

    LinkList* llist=LL_Create();

    //向线性表中插入a个数据元素

    int i;

    int x;

    int a;

    scanf("%d", &a);

    for(i=0; i<a; i++) {

        scanf("%d",&x);

        LL_InsAfter(llist,x);

    }

    //设置线性表当前位置为0

    LL_SetPosition(llist, 0);

    //在线性表表头顺序插入a个元素

    scanf("%d", &a);

    for(i=0; i<a; i++) {

        scanf("%d", &x);

        LL_SetPosition(llist,0);

        LL_InsAfter(llist,x);

    }

    //删除线性表中第一个值为x的元素节点

    scanf("%d", &x);

    LL_DelValue(llist, x);

    //设置当前位置为i，并删除该位置的元素节点

    scanf("%d", &i);

    LL_SetPosition(llist, i);

    LL_DelAt(llist);

    //打印整个线性表然后释放线性表空间

    LL_Print(llist);

    system("PAUSE");

    LL_Free(llist);

}

注意： step2/Main.cpp 的代码不能被修改。

以下是平台对 step2/Main.cpp 的测试样例：

样例输入

3 //输入一个数a，后面将输入a个数据元素

8 9 3  //a个数据元素，依次插入尾结点后。形成单链表结点序列：8,9,3

3  //输入一个数b，后面将再输入b个数据元素

10 89 22  //b个数据元素，依次插入0号结点后。形成单链表结点序列：8,22,89,10,9,3

89  //删除一个值为89的结点

1  //删除1号结点

样例输出

8 10 9 3

代码示例

/*************************************************************
    date: April 2017
    copyright: Zhu En
    DO NOT distribute this code without my permission.
**************************************************************/
// 单链表实现文件

#include <stdio.h>

#include <stdlib.h>

#include "LinkList.h"

// 1）
LinkList * LL_Create()
// 创建一个链接存储的线性表，初始为空表，返回llist指针。
{
  LinkList * llist = (LinkList * ) malloc(sizeof(LinkList));
  llist - > front = NULL;
  llist - > rear = NULL;
  llist - > pre = NULL;
  llist - > curr = NULL;
  llist - > position = 0;
  llist - > len = 0;
  return llist;
}

// 2）	
void LL_Free(LinkList * llist)
// 释放链表的结点，然后释放llist所指向的结构。
{
  LinkNode * node = llist - > front;
  LinkNode * nextnode;
  while (node) {
    nextnode = node - > next;
    free(node);
    node = nextnode;
  }
  free(llist);
}

// 3）	
void LL_MakeEmpty(LinkList * llist)
// 将当前线性表变为一个空表，因此需要释放所有结点。
{
  LinkNode * node = llist - > front;
  LinkNode * nextnode;
  while (node) {
    nextnode = node - > next;
    free(node);
    node = nextnode;
  }
  llist - > front = NULL;
  llist - > rear = NULL;
  llist - > pre = NULL;
  llist - > curr = NULL;
  llist - > position = 0;
  llist - > len = 0;
}

// 4）	
int LL_Length(LinkList * llist)
// 返回线性表的当前长度。
{
  return llist - > len;
}

// 5）	
bool LL_IsEmpty(LinkList * llist)
// 若当前线性表是空表，则返回true，否则返回 False。
{
  return llist - > len == 0;
}

// 6）  
bool LL_SetPosition(LinkList * llist, int i)
// 设置线性表的当前位置为i号位置。
// 设置成功，则返回true，否则返回false（线性表为空，或i不在有效的返回）。
// 假设线性表当前长度为len，那么i的有效范围为[0,len]。
{
  int k;
  /* 若链表为空，则返回*/
  if (llist - > len == 0) return false;

  /*若位置越界*/
  if (i < 0 || i > llist - > len) {
    printf("LL_SetPosition(): position error");
    return false;
  }

  /* 寻找对应结点*/
  llist - > curr = llist - > front;
  llist - > pre = NULL;
  llist - > position = 0;
  for (k = 0; k < i; k++) {
    llist - > position++;
    llist - > pre = llist - > curr;
    llist - > curr = (llist - > curr) - > next;
  }

  /* 返回当前结点位置*/
  return true;
}

// 7)	
int LL_GetPosition(LinkList * llist)
// 获取线性表的当前位置结点的编号。
{
  return llist - > position;
}

// 8）	
bool LL_NextPosition(LinkList * llist)
// 设置线性表的当前位置的下一个位置为当前位置。
// 设置成功，则返回true，否则返回false（线性表为空，或当前位置为表尾）。
{
  if (llist - > position >= 0 && llist - > position < llist - > len)
  /* 若当前结点存在，则将其后继结点设置为当前结点*/
  {
    llist - > position++;
    llist - > pre = llist - > curr;
    llist - > curr = llist - > curr - > next;
    return true;
  } else
    return false;
}

// 9）	
T LL_GetAt(LinkList * llist)
// 返回线性表的当前位置的数据元素的值。
{
  if (llist - > curr == NULL) {
    printf("LL_GetAt(): Empty list, or End of the List.\n");
    LL_Free(llist);
    exit(1);
  }
  return llist - > curr - > data;
}

// 10）	
void LL_SetAt(LinkList * llist, T x)
// 将线性表的当前位置的数据元素的值修改为x。
{
  if (llist - > curr == NULL) {
    printf("LL_SetAt(): Empty list, or End of the List.\n");
    LL_Free(llist);
    exit(1);
  }
  llist - > curr - > data = x;
}

// 11）	
bool LL_InsAt(LinkList * llist, T x)
// 在线性表的当前位置之前插入数据元素x。当前位置指针指向新数据元素结点。
// 若插入失败，返回false，否则返回true。
{
  LinkNode * newNode = (LinkNode * ) malloc(sizeof(LinkNode));
  if (newNode == NULL) return false;

  newNode - > data = x;

  if (llist - > len == 0) {
    /* 在空表中插入*/
    newNode - > next = NULL;
    llist - > front = llist - > rear = newNode;
  }
  //当前位置为表头。
  else if (llist - > pre == NULL) {
    /* 在表头结点处插入*/
    newNode - > next = llist - > front;
    llist - > front = newNode;
  } else {
    /* 在链表的中间位置或表尾后的位置插入*/
    newNode - > next = llist - > curr;
    llist - > pre - > next = newNode;
  }
  //插入在表尾后。
  if (llist - > pre == llist - > rear)
    llist - > rear = newNode;
  /* 增加链表的大小*/
  llist - > len++;
  /* 新插入的结点为当前结点*/
  llist - > curr = newNode;
  return true;
}

// 12）	
bool LL_InsAfter(LinkList * llist, T x)
// 在线性表的当前位置之后插入数据元素x。空表允许插入。当前位置指针将指向新结点。
// 若插入失败，返回false，否则返回true。
{
  // 请在Begin-End之间补充代码，实现结点插入。
  /**********编辑区1 Begin *********/
  LinkNode * newNode = (LinkNode * ) malloc(sizeof(LinkNode));
  if (newNode == NULL) return false;

  newNode - > data = x;

  if (llist - > len == 0) {
    newNode - > next = NULL;
    llist - > front = llist - > rear = newNode;
    llist - > pre = NULL;
  } else {
    if (llist - > curr == NULL) {
      free(newNode);
      return false;
    }

    newNode - > next = llist - > curr - > next;
    llist - > curr - > next = newNode;

    if (llist - > curr == llist - > rear) {
      llist - > rear = newNode;
    }

    llist - > pre = llist - > curr;

  }

  llist - > curr = newNode;
  llist - > len++;
  /**********编辑区1 End **********/
}

// 13）	
bool LL_DelAt(LinkList * llist)
// 删除线性表的当前位置的数据元素结点。
// 若删除失败（为空表，或当前位置为尾结点之后），则返回false，否则返回true。
{
  LinkNode * oldNode;
  /* 若表为空或已到表尾之后，则给出错误提示并返回*/
  if (llist - > curr == NULL) {
    printf("LL_DelAt(): delete a node that does not exist.\n");
    return false;
  }
  oldNode = llist - > curr;
  /* 删除的是表头结点*/
  if (llist - > pre == NULL) {
    llist - > front = oldNode - > next;
  }
  /* 删除的是表中或表尾结点*/
  else if (llist - > curr != NULL) {
    llist - > pre - > next = oldNode - > next;
  }
  if (oldNode == llist - > rear) {
    /* 删除的是表尾结点，则修改表尾指针和当前结点位置值*/
    llist - > rear = llist - > pre;
  }

  /* 后继结点作为新的当前结点*/
  llist - > curr = oldNode - > next;

  /* 释放原当前结点*/
  free(oldNode);

  /* 链表大小减*/
  llist - > len--;
  return true;
}

// 14）	
bool LL_DelAfter(LinkList * llist)
// 删除线性表的当前位置的后面那个数据元素。
// 若删除失败（为空表，或当前位置时表尾），则返回false，否则返回true。
{
  LinkNode * oldNode;
  /* 若表为空或已到表尾，则给出错误提示并返回*/
  if (llist - > curr == NULL || llist - > curr == llist - > rear) {
    printf("LL_DelAfter():  delete a node that does not exist.\n");
    return false;
  }
  /* 保存被删除结点的指针并从链表中删除该结点*/
  oldNode = llist - > curr - > next;
  llist - > curr - > next = oldNode - > next;

  if (oldNode == llist - > rear)
    /* 删除的是表尾结点*/
    llist - > rear = llist - > curr;
  /* 释放被删除结点*/
  free(oldNode);
  /* 链表大小减*/
  llist - > len--;
  return true;
}

// 15）	
int LL_FindValue(LinkList * llist, T x)
// 找到线性表中第一个值为x的数据元素的编号。
// 返回值-1表示没有找到，返回值>=0表示编号。
{
  LinkNode * p = llist - > front;
  int idx = 0;
  while (p != NULL && p - > data != x) {
    idx++;
    p = p - > next;
  }
  if (idx >= llist - > len) return -1;
  else return idx;
}

// 16）	
int LL_DelValue(LinkList * llist, T x)
// 删除第一个值为x的数据元素，返回该数据元素的编号。如果不存在值为x的数据元素，则返回-1。
{
  int idx = LL_FindValue(llist, x);
  if (idx < 0) return -1;
  LL_SetPosition(llist, idx);
  LL_DelAt(llist);
  return idx;
}

// 17）	
void LL_Print(LinkList * llist)
// 打印整个线性表。
{
  LinkNode * node = llist - > front;
  while (node) {
    printf("%d ", node - > data);
    node = node - > next;
  }
  printf("\n");
}