当前位置：首页 > news >正文

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

news 2025/3/12 12:25:27

目录😋

任务描述

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

相关知识

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

线性表的基本概念
初始化线性表
销毁线性表
判定是否为空表
求线性表的长度
输出线性表
求线性表中某个数据元素值
按元素值查找
插入数据元素
删除数据元素

一、线性表的基本概念

线性表是一种基本的数据结构，它是由 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 100typedef 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;
}