educoder数据结构与算法线性表第2关：实现一个链接存储的线性表-阿里云开发者社区

任务描述

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

特别说明：

“当前位置”：当前位置由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 
#include 
#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
scanf("%d",&x);
LL_InsAfter(llist,x);
}
//设置线性表当前位置为0
LL_SetPosition(llist, 0);
//在线性表表头顺序插入a个元素
scanf("%d", &a);
for(i=0; 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

开始你的任务吧，祝你成功！

题解

// 单链表实现文件
#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之间补充代码，实现结点插入。
    /********** 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;
    }
        else if (llist->curr == llist->rear||llist->curr == NULL)
    {
        /* 在尾结点处插入*/
        newNode->next = llist->curr->next;
        llist->curr->next = newNode;
        llist->pre = llist->curr;
        llist->position++;
    }
    else {  
        /* 在链表的中间位置插入*/
        newNode->next = llist->curr->next;
        llist->curr->next = newNode;
        llist->pre = llist->curr;
        llist->position++;
    }
    /* 增加链表的大小*/
    llist->len++;
    /* 新插入的结点为当前结点*/
    llist->curr = newNode;
    return true;
}
    /********** 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");
}

educoder数据结构与算法线性表第2关：实现一个链接存储的线性表

任务描述

相关知识

特别说明：

编程要求

测试说明

题解

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

educoder数据结构与算法 线性表 第2关：实现一个链接存储的线性表

任务描述

相关知识

特别说明：

编程要求

测试说明

题解

热门文章

最新文章

相关课程

相关电子书

相关实验场景

educoder数据结构与算法线性表第2关：实现一个链接存储的线性表