第1关：线性表的链式表示和实现

任务描述

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

相关知识

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

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

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

1. typedef int T;

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

1. typedef struct LN {
2. T data;
3. struct LN* next;
4. }LinkNode;

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

• front： 指向链表的首结点；
• rear： 指向尾结点；
• curr： 指向操作的当前位置（见后文特别说明）的结点；
• pre： 指向当前位置的前一个结点；
• position： 是当前位置的编号（编号从 0 开始）；
• len： 数据元素的个数（即链表的长度）。

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

1. typedef struct {
2. LinkNode* front; // 指向头结点
3. LinkNode* rear; // 指向尾结点
4. LinkNode* pre; // 指向当前位置结点的前一个结点
5. LinkNode* curr; // 指向当前位置结点
6. int position; // 当前位置结点的编号
7. int len; // 线性表的大小（链表结点数）
8. }LinkList;

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

特别说明：

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

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

• 创建空线性表：创建一个链接存储的线性表，初始为空表，返回llist指针。具体操作函数定义如下：

  1. LinkList* LL_Create()
  2. // 创建一个链接存储的线性表，初始为空表，返回llist指针。
  3. {
  4. LinkList* llist=(LinkList*)malloc(sizeof(LinkList));
  5. llist->front=NULL;
  6. llist->rear=NULL;
  7. llist->pre=NULL;
  8. llist->curr=NULL;
  9. llist->position=0;
  10. llist->len=0;
  11. return llist;
  12. }

• 释放线性表结点：释放链表的结点，然后释放llist所指向的结构。具体操作函数定义如下：

  1. void LL_Free(LinkList* llist)
  2. // 释放链表的结点，然后释放llist所指向的结构。
  3. {
  4. LinkNode* node=llist->front;
  5. LinkNode* nextnode;
  6. while(node){
  7. nextnode=node->next;
  8. free(node);
  9. node=nextnode;
  10. }
  11. free(llist);
  12. }

• 置空线性表：释放链表的所有结点，将当前线性表变为一个空表。具体操作函数定义如下：

  1. // 将当前线性表变为一个空表，因此需要释放所有结点。
  2. {
  3. LinkNode* node=llist->front;
  4. LinkNode* nextnode;
  5. while(node){
  6. nextnode=node->next;
  7. free(node);
  8. node=nextnode;
  9. }
  10. llist->front=NULL;
  11. llist->rear=NULL;
  12. llist->pre=NULL;
  13. llist->curr=NULL;
  14. llist->position=0;
  15. llist->len=0;
  16. }

• 获取线性表当前长度： 返回线性表的当前长度。具体操作函数定义如下：

  1. // 返回线性表的当前长度。
  2. {
  3. return llist->len;
  4. }

• 判断线性表是否为空： 若当前线性表是空表，则返回true，否则返回false。具体操作函数定义如下：

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

• 设置线性表当前位置： 设置线性表的当前位置为i号位置。设置成功，则返回true，否则返回false（线性表为空，或i不在有效范围）。假设线性表当前长度为len，那么i的有效范围为[0,len]。具体操作函数定义如下：

  1. bool LL_SetPosition(LinkList* llist, int i)
  2. // 设置线性表的当前位置为i号位置。
  3. // 设置成功，则返回true，否则返回false（线性表为空，或i不在有效的返回）。
  4. // 假设线性表当前长度为len，那么i的有效范围为[0,len]。
  5. {
  6. int k;
  7. /* 若链表为空，则返回*/
  8. if (llist->len==0) return false;
  10. /*若位置越界*/
  11. if( i < 0 || i > llist->len)
  12. { printf("LL_SetPosition(): position error");
  13. return false;
  14. }
  16. /* 寻找对应结点*/
  17. llist->curr = llist->front;
  18. llist->pre = NULL;
  19. llist->position = 0;
  20. for ( k = 0; k < i; k++) {
  21. llist->position++;
  22. llist->pre = llist->curr;
  23. llist->curr = (llist->curr)->next;
  24. }
  26. /* 返回当前结点位置*/
  27. return true;
  28. }

• 获取线性表当前位置结点编号： 获取线性表的当前位置结点的编号。具体操作函数定义如下：

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

• 设置线性表当前位置的下一位置为当前位置： 设置成功，则返回true，否则返回false（线性表为空，或当前位置为表尾）。具体操作函数定义如下：

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

• 获取线性表当前位置的数据元素的值： 具体操作函数定义如下：

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

• 修改线性表当前位置数据元素的值： 将线性表的当前位置的数据元素的值修改为x。具体操作函数定义如下：

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

• 在线性表当前位置之前插入数据元素： 在线性表的当前位置之前插入数据元素x。空表允许插入，当前位置指针将指向新结点。若插入失败，返回false，否则返回true。具体操作函数定义如下：

  1. bool LL_InsAt(LinkList* llist, T x)
  2. // 在线性表的当前位置之前插入数据元素x。当前位置指针指向新数据元素结点。
  3. // 若插入失败，返回false，否则返回true。
  4. {
  5. LinkNode *newNode=(LinkNode*)malloc(sizeof(LinkNode));
  6. if (newNode==NULL) return false;
  8. newNode->data=x;
  10. if (llist->len==0){
  11. /* 在空表中插入*/
  12. newNode->next=NULL;
  13. llist->front = llist->rear = newNode;
  14. }
  15. //当前位置为表头。
  16. else if (llist->pre==NULL)
  17. {
  18. /* 在表头结点处插入*/
  19. newNode->next = llist->front;
  20. llist->front = newNode;
  21. }
  22. else {
  23. /* 在链表的中间位置或表尾后的位置插入*/
  24. newNode->next = llist->curr;
  25. llist->pre->next=newNode;
  26. }
  27. //插入在表尾后。
  28. if (llist->pre==llist->rear)
  29. llist->rear=newNode;
  30. /* 增加链表的大小*/
  31. llist->len++;
  32. /* 新插入的结点为当前结点*/
  33. llist->curr = newNode;
  34. return true;
  35. }

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

• 删除线性表当前位置数据元素结点： 若删除失败（为空表），则返回false，否则返回true。具体操作函数定义如下：

  1. bool LL_DelAt(LinkList* llist)
  2. // 删除线性表的当前位置的数据元素结点。
  3. // 若删除失败（为空表，或当前位置为尾结点之后），则返回false，否则返回true。
  4. {
  5. LinkNode *oldNode;
  6. /* 若表为空或已到表尾之后，则给出错误提示并返回*/
  7. if (llist->curr==NULL)
  8. {
  9. printf("LL_DelAt(): delete a node that does not exist.\n");
  10. return false;
  11. }
  12. oldNode=llist->curr;
  13. /* 删除的是表头结点*/
  14. if (llist->pre==NULL)
  15. {
  16. llist->front = oldNode->next;
  17. }
  18. /* 删除的是表中或表尾结点*/
  19. else if(llist->curr!=NULL){
  20. llist->pre->next = oldNode->next;
  21. }
  22. if (oldNode == llist->rear) {
  23. /* 删除的是表尾结点，则修改表尾指针和当前结点位置值*/
  24. llist->rear = llist->pre;
  25. }
  27. /* 后继结点作为新的当前结点*/
  28. llist->curr = oldNode->next;
  30. /* 释放原当前结点*/
  31. free(oldNode);
  33. /* 链表大小减*/
  34. llist->len --;
  35. return true;
  36. }

• 删除线性表当前位置后面的那个数据元素结点： 若删除失败（为空表，或当前位置是表尾），则返回false，否则返回true。具体操作函数定义如下：

  1. bool LL_DelAfter(LinkList* llist)
  2. // 删除线性表的当前位置的后面那个数据元素。
  3. // 若删除失败（为空表，或当前位置时表尾），则返回false，否则返回true。
  4. {
  5. LinkNode *oldNode;
  6. /* 若表为空或已到表尾，则给出错误提示并返回*/
  7. if (llist->curr==NULL || llist->curr== llist->rear)
  8. {
  9. printf("LL_DelAfter(): delete a node that does not exist.\n");
  10. return false;
  11. }
  12. /* 保存被删除结点的指针并从链表中删除该结点*/
  13. oldNode = llist->curr->next;
  14. llist->curr->next=oldNode->next;
  16. if (oldNode == llist->rear)
  17. /* 删除的是表尾结点*/
  18. llist->rear = llist->curr;
  19. /* 释放被删除结点*/
  20. free(oldNode);
  21. /* 链表大小减*/
  22. llist->len --;
  23. return true;
  24. }

• 查找线性表中第一个值为x的数据元素的编号： 返回值-1表示没有找到，返回值>=0表示编号。具体操作函数定义如下：

  1. int LL_FindValue(LinkList* llist, T x)
  2. // 找到线性表中第一个值为x的数据元素的编号。
  3. // 返回值-1表示没有找到，返回值>=0表示编号。
  4. {
  5. LinkNode* p=llist->front;
  6. int idx=0;
  7. while(p!=NULL && p->data!=x) {
  8. idx++;
  9. p = p->next;
  10. }
  11. if (idx>=llist->len) return -1;
  12. else return idx;
  13. }

• 删除线性表中第一个值为x的数据元素： 删除第一个值为x的数据元素，返回该数据元素的编号。如果不存在值为x的数据元素，则返回-1。具体操作函数定义如下：

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

• 打印整个线性表： 具体操作函数定义如下：

  1. void LL_Print(LinkList* llist)
  2. // 打印整个线性表。
  3. {
  4. LinkNode* node=llist->front;
  5. while (node) {
  6. printf("%d ", node->data);
  7. node=node->next;
  8. }
  9. printf("\n");
  10. }

编程要求

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

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

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

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

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

1. bool LL_InsAfter(LinkList* llist, T x)
2. // 在线性表的当前位置之后插入数据元素x。空表允许插入。当前位置指针将指向新结点。若插入失败，返回false，否则返回true。
3. {
4. // 请在这里补充代码，完成本关任务
5. /********** Begin *********/
8. /********** End **********/
9. }

测试说明

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

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include "LinkList.h"
4. #pragma warning(disable:4996)
6. int main()
7. {
8. //创建一个线性表
9. LinkList* llist=LL_Create();
11. //向线性表中插入a个数据元素
12. int i;
13. int x;
14. int a;
15. scanf("%d", &a);
16. for(i=0; i<a; i++) {
17. scanf("%d",&x);
18. LL_InsAfter(llist,x);
19. }
21. //设置线性表当前位置为0
22. LL_SetPosition(llist, 0);
24. //在线性表表头顺序插入a个元素
25. scanf("%d", &a);
26. for(i=0; i<a; i++) {
27. scanf("%d", &x);
28. LL_SetPosition(llist,0);
29. LL_InsAfter(llist,x);
30. }
32. //删除线性表中第一个值为x的元素节点
33. scanf("%d", &x);
34. LL_DelValue(llist, x);
36. //设置当前位置为i，并删除该位置的元素节点
37. scanf("%d", &i);
38. LL_SetPosition(llist, i);
39. LL_DelAt(llist);
41. //打印整个线性表然后释放线性表空间
42. LL_Print(llist);
43. system("PAUSE");
44. LL_Free(llist);
46. }

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

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

1. 3 //输入一个数a，后面将输入a个数据元素
2. 8 9 3 //a个数据元素，依次插入尾结点后。形成单链表结点序列：8,9,3
3. 3 //输入一个数b，后面将再输入b个数据元素
4. 10 89 22 //b个数据元素，依次插入0号结点后。形成单链表结点序列：8,22,89,10,9,3
5. 89 //删除一个值为89的结点
6. 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，否则返回TRUE。

{

    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)

    {

        //在尾结点插入

        newNode->next=NULL;

        llist->rear->next=newNode;

        llist->pre=llist->rear;

        llist->rear=newNode;

        llist->position=llist->len;

    }

    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");

}

第2关：线性链表

任务描述

本关任务：根据所学线性链表的基础知识，完成线性链表插入数据功能的程序编写并通过所有测试用例。

相关知识

为了完成本关任务，你需要掌握：

1、线性链表的基础知识；

2、线性链表的实现。

线性链表简介

线性表的链式存储结构称为线性链表，如图1所示，线性链表将存储空间划分成若干的小块，每块占用若干个字节，这些小块称为存储结点。将其中的存储结点分为两个部分，一部分用于存储数据元素的值，称为数据域；另一部分用于存储元素之间的前后件关系，即存放下一个元素在存储序号（存储地址），指向后件结点。在线性链表中用一个专门的指针 HEAD 指向线性链表中第一个数据元素的结点（即存放第一个元素的地址）。线性表中最后一个元素没有后件，因此，线性链表中的最后一个结点的指针域为空（用 NULL 或0表示），表示链终结。

图 1 线性链表

线性链表中各元素的存储序号是不连续的，元素间的前后件关系与位置关系同时也是不一致的，前后件的关系依靠各结点的指针来指示，指向表的第一个元素的指针 HEAD 称为头指针，当HEAD=NULL时，表示该链表为空。对于线性链表，可以从头指针开始，沿着各结点的指针扫描到链表中的所有结点。这种线性链表称为线性单链表，即可以从表头开始向后扫描链表中的所有结点，而不能从中间或表尾结点向前扫描位于该结点之前的元素。

线性链表的实现

1、插入结点

当需要向链表中插入结点时，根据插入位置的不同，可分为3种情形：插入到链表的首部，也就是头结点和首元结点中间；插入到链表中间的某个位置；插入到链表最末端。虽然插入位置有区别，但使用的插入方法是一样的，如图2所示，首先，需要将新结点的 next 指针指向所插入位置后的结点；再插入位置前的结点的 next 指针指向插入结点，即可完成插入操作。

图 2 插入结点

代码示例：

1. link * insertElem(link * p,int elem,int add){
2. link * temp=p; //创建临时结点temp
3. //首先找到要插入位置的上一个结点
4. for (int i=1; i<add; i++) {
5. if (temp==NULL) {
6. printf("插入位置无效\n");
7. return p;
8. }
9. temp=temp->next;
10. }
11. //创建插入结点c
12. link * c=(link*)malloc(sizeof(link));
13. c->elem=elem;
14. //向链表中插入结点
15. c->next=temp->next;
16. temp->next=c;
17. return p;
18. }

2、查找与更新

当需要查找线性链表的某个数据时，一般情况下，链表只能通过头结点或者头指针进行访问，所以实现查找某结点最常用的方法就是对链表中的结点进行逐个遍历。代码示例如下：

1. int selectElem(link * p,int elem){
2. link * t=p;
3. int i=1;
4. while (t->next) {
5. t=t->next;
6. if (t->elem==elem) {
7. return i;
8. }
9. i++;
10. }
11. return -1;
12. }

若需要对链表中的某个结点数据进行修改与更新，首先我们需要通过遍历的方式找到对应的结点，再对其数据域进行更新即可。代码示例如下：

1. //更新函数，其中，add 表示更改结点在链表中的位置，newElem 为新的数据域的值
2. link *amendElem(link * p,int add,int newElem){
3. link * temp=p;
4. temp=temp->next;//在遍历之前，temp指向首元结点
5. //遍历到被删除结点
6. for (int i=1; i<add; i++) {
7. temp=temp->next;
8. }
9. temp->elem=newElem;
10. return p;
11. }

编程要求

在右侧编辑器中的 Begin-End 之间补充 C 语言代码，完成对线性链表插入功能的实现，其数据内容通过 scanf 从后台获取。

测试说明

平台将使用测试集运行你编写的程序代码，若全部的运行结果正确，则通关。

测试输入：

1. 张三
2. 李四
3. 王五

预期输出：

1. 线性链表创建成功！
2. 张三
3. 李四
4. 王五

---

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

截止后通关代码:

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

struct stu{

    char  name[32];

    struct stu  *next;

};

/*创建链表，参数n是初始化链表时建立的数据个数

prev：指向当前结点的前一个结点

cur：指向当前结点

head：保存表头结点的指针*/

struct stu* CreatList(int n){

    int i;

    struct stu *prev,*cur,*head;

    head=(struct stu*)malloc(sizeof(struct stu));

    if(head==NULL){

        printf("Can't alloc memory\n");

        return NULL;

    }

    prev=head;

    head->name[0]='\0';

    head->next=NULL;

    for(i=1;i<=n;i++){

        cur=(struct stu*)malloc(sizeof(struct stu));

        if(cur==NULL){

            printf("Can't alloc memory\n");

            return NULL;                

        }

    scanf("%s",cur->name);

    // 请在下面的Begin-End之间补充代码，插入结点。

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

prev->next=cur;

prev=cur;

 

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

    }

    printf("线性链表创建成功！\n");

    return head;

}

/*遍历链表，打印链表数据*/

void Print(struct stu *head){

    struct stu *cur;

    cur=head->next;

    while(cur!=NULL){

        printf("%s\n",cur->name);

        cur=cur->next;

    }

}

int main(){

    int number=3;

    struct stu *head;

    head=CreatList(number);

    if(head==NULL)

        return -1;

    Print(head);

    return 0;  

}