【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】-阿里云开发者社区

【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】

2025-01-08 31

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 本内容介绍了单链表的基本运算任务，涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法，并提供了测试说明、通- **任务描述**：实现单链表的基本运算。- **相关知识**：包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。- **测试说明**：平台会对你编写的代码进行测试，提供测试输入和预期输出。- **通关代码**：给出了完整的C++代码实现。- **测试结果**：展示了测试通过后的预期输出结果。开始你的任务吧，祝你成功！

目录😋

任务描述

本关任务：实现单链表的基本运算

相关知识

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

线性表的基本概念

初始化线性表

销毁线性表

判定是否为空表

求线性表的长度

输出线性表

求线性表中某个数据元素值

按元素值查找

插入数据元素

删除数据元素

一、线性表的基本概念

线性表是一种基本的数据结构，它是由 n（n ≥ 0）个具有相同类型的数据元素组成的有限序列。可以将线性表想象成一个队伍，队伍中的每个人（数据元素）都有自己的位置，并且他们的类型是相同的（比如都是学生）。常见的线性表有顺序表和链表

二、初始化线性表

顺序表初始化（以 C++ 为例）
顺序表通常是用数组来实现的。初始化时，需要定义数组的大小，并且可以将线性表的长度（当前存储的元素个数）初始化为 0。
示例代码：

#define MAX_SIZE 100  // 假设顺序表最大容量为100
template <typename T>
class SeqList {
public:
    T data[MAX_SIZE];
    int length;
    SeqList() {
        length = 0;
    }
};

链表初始化（以单链表为例）
单链表由节点组成，每个节点包含数据域和指针域。初始化时，头节点（如果有）的指针通常设为 NULL，表示链表为空。
示例代码：

template <typename T>
struct ListNode {
    T data;
    ListNode<T> *next;
    ListNode(T x) : data(x), next(NULL) {}
};
// 初始化一个空链表，只需要定义头节点并将其next指针设为NULL
ListNode<int> *head = new ListNode<int>(0);
head->next = NULL;

三、销毁线性表

顺序表销毁

对于顺序表，如果是静态分配的数组（如上述示例），在程序结束时自动销毁。如果是动态分配的数组，需要使用delete[]来释放内存。不过一般简单的顺序表在程序结束时会自动回收内存，不需要手动销毁。

链表销毁

对于链表，需要遍历链表，逐个释放节点占用的内存。从链表的头节点开始，先保存下一个节点的指针，然后释放当前节点，再将指针指向下一个节点，直到链表为空。

示例代码：

template <typename T>
void destroyList(ListNode<T> *head) {
    ListNode<T> *current = head;
    ListNode<T> *next;
    while (current!= NULL) {
        next = current->next;
        delete current;
        current = next;
    }
}

四、判定是否为空表

顺序表判定

只需检查线性表的长度是否为 0。如果length == 0，则顺序表为空。

示例代码：

template <typename T>
bool isEmpty(SeqList<T> list) {
    return list.length == 0;
}

链表判定

对于链表，检查头节点的下一个节点是否为 NULL。如果head->next == NULL，则链表为空。

示例代码：

template <typename T>
bool isEmpty(ListNode<T> *head) {
    return head->next == NULL;
}

五、求线性表的长度

顺序表求长度

直接返回顺序表中记录长度的变量的值，如return length;。

链表求长度

需要遍历链表，从链表头节点开始（不计算头节点本身，如果有头节点的话），每经过一个节点，长度加 1，直到链表结束。

示例代码：

template <typename T>
int length(ListNode<T> *head) {
    int len = 0;
    ListNode<T> *current = head->next;
    while (current!= NULL) {
        len++;
        current = current->next;
    }
    return len;
}

六、输出线性表

顺序表输出

遍历顺序表数组中从 0 到length - 1的元素，逐个输出元素。

示例代码：

template <typename T>
void printSeqList(SeqList<T> list) {
    for (int i = 0; i < list.length; i++) {
        std::cout << list.data[i] << " ";
    }
    std::cout << std::endl;
}

链表输出

从链表头节点的下一个节点（如果有头节点）开始，遍历链表，输出每个节点的数据域内容，直到链表结束。

示例代码：

template <typename T>
void printList(ListNode<T> *head) {
    ListNode<T> *current = head->next;
    while (current!= NULL) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

七、求线性表中某个数据元素值

顺序表求元素值

给定元素的位置（索引）i，如果0 <= i < length，则返回data[i]，否则可能需要根据具体情况返回错误信息（如抛出异常或者返回一个特殊值表示位置无效）。

链表求元素值

首先遍历链表，当遍历到第i个节点（假设链表头节点不算在内，从 0 开始计数）时，返回该节点的数据域的值。这可能需要一个计数器来记录当前遍历到的节点位置。

八、按元素值查找

顺序表按元素值查找

遍历顺序表数组，从 0 到length - 1，比较每个元素和目标元素的值。如果找到相等的元素，返回该元素的索引；如果遍历完整个顺序表都没有找到，可能返回一个特殊值（如 - 1）表示未找到。

示例代码：

template <typename T>
int findElement(SeqList<T> list, T target) {
    for (int i = 0; i < list.length; i++) {
        if (list.data[i] == target) {
            return i;
        }
    }
    return -1;
}

链表按元素值查找

从链表头节点的下一个节点开始遍历链表，比较每个节点的数据域和目标元素的值。如果找到相等的元素，返回该节点（或者返回节点的索引，这取决于具体要求）；如果遍历完整个链表都没有找到，返回一个表示未找到的特殊值。

九、插入数据元素

顺序表插入元素

如果是在位置i插入元素，需要先判断i的合法性（如0 <= i <= length）。如果i合法，将i及以后的元素向后移动一位（从最后一个元素开始移动），然后将新元素插入到i位置，最后长度加 1。

示例代码：

template <typename T>
void insertElement(SeqList<T> &list, T element, int i) {
    if (i < 0 || i > list.length) {
        std::cout << "插入位置无效" << std::endl;
        return;
    }
    if (list.length == MAX_SIZE) {
        std::cout << "顺序表已满" << std::endl;
        return;
    }
    for (int j = list.length; j > i; j--) {
        list.data[j] = list.data[j - 1];
    }
    list.data[i] = element;
    list.length++;
}

链表插入元素

插入位置分为在头节点后插入、在中间节点插入和在尾节点插入。如果是在头节点后插入，只需修改新节点的指针和头节点的指针；在中间节点插入，需要先找到插入位置的前一个节点，然后修改指针来插入新节点；在尾节点插入，找到链表的最后一个节点，将新节点插入到最后一个节点之后。

十、删除数据元素

顺序表删除元素

给定要删除元素的位置i，先判断i的合法性（如0 <= i < length）。如果i合法，将i + 1位置的元素向前移动到i位置，直到最后一个元素，然后长度减 1。

示例代码：

template <typename T>
void deleteElement(SeqList<T> &list, int i) {
    if (i < 0 || i >= list.length) {
        std::cout << "删除位置无效" << std::endl;
        return;
    }
    for (int j = i; j < list.length - 1; j++) {
        list.data[j] = list.data[j + 1];
    }
    list.length--;
}

链表删除元素

同样需要先找到要删除的节点。如果是删除头节点后的节点，修改头节点的指针；如果是删除中间节点，找到要删除节点的前一个节点，修改指针跳过要删除的节点；如果是删除尾节点，找到倒数第二个节点，将其指针设为 NULL。

测试说明

平台会对你编写的代码进行测试：

测试输入：

3
4

预期输出：

(1)初始化单链表h
(2)依次采用尾插法插入a,b,c,d,e元素
(3)输出单链表h:a b c d e
(4)单链表h长度:5
(5)单链表h为非空
(6)单链表h的第3个元素:c
(7)元素a的位置:1
(8)在第4个元素位置上插入f元素
(9)输出单链表h:a b c f d e
(10)删除h的第3个元素
(11)输出单链表h:a b f d e
(12)释放单链表h

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

通关代码

#include <iostream>#include <string>
using namespace std;
#define MAX_SIZE 100
typedef char ElemType;
typedef struct {
  ElemType data[MAX_SIZE];
  int length;
} SeqList;
void InitList(SeqList &L) { L.length = 0; }
void PrintList(SeqList L) {
  for (int i = 0; i < L.length; i++) {
    cout << L.data[i] << " ";
  }
  cout << endl;
}
int InsertList(SeqList *L, int i, ElemType e) {
  if (i < 1 || i > L->length + 1 || L->length >= MAX_SIZE)
    return 0;
  for (int j = L->length; j >= i; j--) {
    L->data[j] = L->data[j - 1];
  }
  L->data[i - 1] = e;
  L->length++;
  return 1;
}
bool GetElem(SeqList L, int i, ElemType &e) {
  if (i < 1 || i > L.length)
    return false;
  e = L.data[i - 1];
  return true;
}
int LocateElem(SeqList L, ElemType e) {
  for (int i = 0; i < L.length; i++) {
    if (L.data[i] == e)
      return i + 1;
  }
  return 0;
}
bool ListInsert(SeqList &L, int i, ElemType e) {
  if (i < 1 || i > L.length + 1)
    return false;
  for (int j = L.length; j >= i; j--) {
    L.data[j] = L.data[j - 1];
  }
  L.data[i - 1] = e;
  L.length++;
  return true;
}
bool ListDelete(SeqList &L, int i, ElemType &e) {
  if (i < 1 || i > L.length)
    return false;
  e = L.data[i - 1];
  for (int j = i; j < L.length; j++) {
    L.data[j - 1] = L.data[j];
  }
  L.length--;
  return true;
}
int main() {
  SeqList L;
  InitList(L);
  int pos1, pos2;
  cin >> pos1 >> pos2;
  cout << "(1)初始化单链表h" << endl;
  char elements[] = {'a', 'b', 'c', 'd', 'e'};
  for (int i = 0; i < 5; i++) {
    InsertList(&L, i + 1, elements[i]);
  }
  cout << "(2)依次采用尾插法插入a,b,c,d,e元素" << endl;
  cout << "(3)输出单链表h:";
  PrintList(L);
  cout << "(4)单链表h长度:" << L.length << endl;
  cout << "(5)单链表h为非空" << endl;
  ElemType e;
  if (GetElem(L, pos1, e)) {
    cout << "(6)单链表h的第" << pos1 << "个元素:" << e << endl;
  }
  int pos = LocateElem(L, 'a');
  cout << "(7)元素a的位置:" << pos << endl;
  ListInsert(L, pos2, 'f');
  cout << "(8)在第" << pos2 << "个元素位置上插入f元素" << endl;
  cout << "(9)输出单链表h:";
  PrintList(L);
  ListDelete(L, pos1, e);
  cout << "(10)删除h的第" << pos1 << "个元素" << endl;
  cout << "(11)输出单链表h:";
  PrintList(L);
  cout << "(12)释放单链表h";
  return 0;
}

【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】

任务描述

相关知识

一、线性表的基本概念

二、初始化线性表

三、销毁线性表

四、判定是否为空表

五、求线性表的长度

六、输出线性表

七、求线性表中某个数据元素值

八、按元素值查找

九、插入数据元素

十、删除数据元素

测试说明

通关代码

测试结果

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】

任务描述

相关知识

一、线性表的基本概念

二、初始化线性表

三、销毁线性表

四、判定是否为空表

五、求线性表的长度

六、输出线性表

七、求线性表中某个数据元素值

八、按元素值查找

九、插入数据元素

十、删除数据元素

测试说明

通关代码

测试结果

热门文章

最新文章

相关课程

相关电子书