c++采用数组来实现链表初始元素的输入、任意位置插入、删除、查找、遍历的功能。自己输入初始元素,通过不同指令输出不同功能
时间: 2023-12-13 21:05:47 浏览: 67
好的,我来给你讲解一下如何使用数组实现链表的基本功能。
首先,我们需要定义一个结构体来表示链表中的每个节点,结构体包括两个成员:数据和下一个节点的位置(即数组中的下标)。
```
struct ListNode {
int val; // 数据
int next; // 下一个节点的位置
};
```
接下来,我们需要定义一个数组来存储链表中的所有节点。同时,我们需要定义一个变量来表示链表中的头节点的位置。
```
const int MAXN = 10010; // 数组的最大长度
ListNode nodes[MAXN]; // 存储链表中的所有节点
int head; // 链表中头节点的位置
```
接下来,我们就可以实现链表的基本功能了。
1. 输入初始元素
我们可以使用一个 for 循环来依次输入每个节点的数据和下一个节点的位置。在输入头节点时,将 head 变量赋值为头节点的位置。
```
int n; // 链表中节点的个数
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> nodes[i].val >> nodes[i].next;
if (i == 1) {
head = nodes[i].next;
}
}
```
2. 任意位置插入
我们需要输入插入位置和要插入的数据,然后依次修改插入节点、前一个节点和后一个节点的 next 指针。
```
int pos, val; // 插入位置和要插入的数据
cin >> pos >> val;
nodes[n+1].val = val; // 新建一个节点存储要插入的数据
nodes[n+1].next = nodes[pos].next; // 修改新节点的 next 指针
nodes[pos].next = n+1; // 修改前一个节点的 next 指针
```
3. 删除节点
我们需要输入要删除的节点的位置,然后依次修改前一个节点和要删除的节点的 next 指针。
```
int pos; // 要删除的节点的位置
cin >> pos;
nodes[pos-1].next = nodes[pos].next; // 修改前一个节点的 next 指针
```
4. 查找节点
我们需要输入要查找的节点的数据,然后遍历整个链表,找到第一个数据匹配的节点。
```
int val; // 要查找的节点的数据
cin >> val;
int p = head;
while (p != -1) {
if (nodes[p].val == val) {
cout << "Found at position " << p << endl;
break;
}
p = nodes[p].next;
}
if (p == -1) {
cout << "Not found" << endl;
}
```
5. 遍历链表
我们可以使用一个 while 循环来依次遍历链表中的所有节点,并输出它们的数据。
```
int p = head;
while (p != -1) {
cout << nodes[p].val << " ";
p = nodes[p].next;
}
cout << endl;
```
以上就是使用数组实现链表的基本功能的方法。需要注意的是,这种方法的效率不如使用指针实现链表,因为每次插入或删除节点时都需要移动数组中的元素。
阅读全文