请编写程序实现单链表插入、删除结点等基本算法。给定一个单链表和一系列插入、删除结点的操作序列,输出实施上述操作后的链表。单链表数据域值为整数。\n\n输入格式:\n输入第1行为1个正整数n,表示当前单链表长
时间: 2023-05-31 22:17:54 浏览: 313
### 回答1:
度。接下来n行,每行一个整数,表示单链表中的结点值。接下来若干行,每行为一种操作,格式为"insert x"或"delete x",表示插入值为x的结点或删除值为x的结点。
输出格式:
输出当前单链表中的所有结点值,每个值占一行。
算法实现:
1. 定义单链表结构体Node,包含数据域和指向下一个结点的指针域。
2. 定义单链表类LinkedList,包含头结点指针和链表长度。
3. 实现单链表的插入操作,即在链表中插入一个新结点。插入操作分为两种情况:在链表头部插入结点和在链表中间或尾部插入结点。
4. 实现单链表的删除操作,即删除链表中指定值的结点。删除操作也分为两种情况:删除头结点和删除中间或尾部结点。
5. 根据输入的操作序列,依次执行插入和删除操作,输出最终链表中的所有结点值。
代码实现:
#include <iostream>
using namespace std;
// 定义单链表结构体
struct Node {
int data;
Node* next;
};
// 定义单链表类
class LinkedList {
public:
LinkedList() {
head = new Node;
head->next = NULL;
length = ;
}
~LinkedList() {
Node* p = head;
while (p) {
Node* q = p->next;
delete p;
p = q;
}
}
// 在链表头部插入结点
void insertHead(int x) {
Node* p = new Node;
p->data = x;
p->next = head->next;
head->next = p;
length++;
}
// 在链表中间或尾部插入结点
void insert(int x) {
Node* p = head;
while (p->next && p->next->data < x) {
p = p->next;
}
Node* q = new Node;
q->data = x;
q->next = p->next;
p->next = q;
length++;
}
// 删除头结点
void deleteHead() {
if (head->next) {
Node* p = head->next;
head->next = p->next;
delete p;
length--;
}
}
// 删除中间或尾部结点
void deleteNode(int x) {
Node* p = head;
while (p->next && p->next->data != x) {
p = p->next;
}
if (p->next) {
Node* q = p->next;
p->next = q->next;
delete q;
length--;
}
}
// 输出链表中的所有结点值
void print() {
Node* p = head->next;
while (p) {
cout << p->data << endl;
p = p->next;
}
}
private:
Node* head;
int length;
};
int main() {
int n;
cin >> n;
LinkedList list;
for (int i = ; i < n; i++) {
int x;
cin >> x;
list.insert(x);
}
string op;
int x;
while (cin >> op >> x) {
if (op == "insert") {
list.insert(x);
} else if (op == "delete") {
list.deleteNode(x);
}
}
list.print();
return ;
}
### 回答2:
输入第2行为n个整数,表示单链表各结点数据域值。接下来若干行,每行给出一次操作,格式为“操作类型 数据”,其中操作类型为“I”表示插入操作,“D”表示删除操作,数据为插入的数据域值或删除结点的数据域值。每行操作后须输出执行完操作后的链表。\n\n输出格式:\n将所有操作执行完后的最终链表输出,每个结点输出一行,格式为“数据 连接地址”,其中数据为结点数据域的值,连接地址为下一结点在内存中的地址,连接地址为-1表示链表结束。最后一行输出“-1 -1”。\n\n输入样例:\n5\n1 2 3 4 5\nI 6\nD 3\nI 7\nD 5\nI 9\n\n输出样例:\n1 2\n2 3\n6 1003\n7 1004\n9 -1\n-1 -1\n\n解题思路:\n单链表插入、删除的基本操作涉及到指针的操作,考察的是操作链表的能力。对于插入操作,需要查找插入位置并将前一个节点的指针指向新节点,新节点的指针指向下一个节点。对于删除操作,则需要找到被删除节点的前一个节点,将其指针指向被删除节点的下一个节点,然后将被删除节点释放掉。
### 回答3:
单链表是数据结构中常见的一种线性结构,是由若干个结点组成,每个结点由两个部分组成,一个是存储数据的数据域,一个是指向后继结点的指针域。单链表有头结点和头指针,头结点不存储任何数据,只是为了方便操作而存在。
在实现单链表的操作时,我们需要注意对指针的处理,插入、删除结点需要修改指向前驱结点和后继结点的指针。下面给出单链表的插入、删除结点算法。
插入结点:
1. 创建一个结点p,将要插入的值存放在它的数据域中。
2. 将p的指针域指向原来第i个位置的结点, 也即ListNode[i-1]->next.
3. 将第i-1个结点的指针域指向p,即
ListNode[i-1]->next = p.
4. 链表长度加1,退出。
删除结点:
1. 找到要删除的结点i的前驱结点pre,即 pre = ListNode[i-1].
2. 将pre的指针域指向要删除结点i的后继结点,即
pre->next = ListNode[i]->next.
3. 将i结点从内存中删除,释放空间。
4. 链表长度减1,退出。
下面给出Python语言实现单链表的插入、删除结点算法的示例代码。
```
class Node:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.head = Node(None)
self.length = 0
def insert(self, pos, val):
if pos > self.length + 1 or pos < 1:
return False
p = self.head
for i in range(pos - 1):
p = p.next
node = Node(val)
node.next = p.next
p.next = node
self.length += 1
return True
def delete(self, pos):
if pos > self.length or pos < 1:
return False
p= self.head
for i in range(pos -1):
p = p.next
p.next = p.next.next
self.length -= 1
return True
def printList(self):
p = self.head.next
while(p != None):
print(p.val, end = ' ')
p = p.next
print()
n = int(input())
lst = LinkedList()
for i in range(n):
val = int(input())
lst.insert(i+1, val)
lst.printList()
# 执行若干次插入和删除操作
lst.delete(3)
lst.insert(2, 5)
lst.printList()
```
以上是一个单链表的基本操作,需要注意链表的底层实现。在插入或删除节点时,需要修改前一个节点的指针指向目标节点,同时修改当前节点的指针指向下一节点。此外,出现错误时,需要返回特定的值或信息。
阅读全文