头插法建立循环双链表
时间: 2024-09-28 11:09:39 浏览: 0
头插法(也称为头追法)是在创建循环双链表时常用的一种技巧,它的基本思想是先创建一个空的链表头部节点,然后依次将新元素添加到链表头部,同时更新每个新元素的前驱指针指向当前节点,以及当前节点的后继指针指向下一个新元素。这个过程会形成一个首尾相连的环形结构。
以下是步骤说明:
1. **初始化**:首先,创建一个`head`节点作为链表的头,其`next`和`prev`均设为`null`,表示链表初始为空。
2. **添加元素**:对于每一个新的元素`e`,设置其`next`指针指向当前的`head`,`prev`指针设为`null`,然后将`head`的`prev`指针指向新元素`e`,这样就形成了一个闭环。
```python
new_node = Node(e) # 新节点
new_node.prev = None
new_node.next = head
if head is not None:
head.prev = new_node
head = new_node
```
通过这种方式,每次添加新元素都能无缝地增加到链表头部,形成循环链表。
相关问题
c++头插法建立循环双链表
在 C++ 中,头插法(push_front)用于在链表头部添加元素,创建循环双链表(circular doubly linked list)通常涉及到以下几个步骤:
1. 定义节点结构:首先,需要定义一个包含数据域和指针域的节点结构,包括一个指向当前节点的指针、前驱节点的指针和后继节点的指针。
```cpp
struct Node {
int data;
Node* prev;
Node* next;
};
```
2. 创建头结点:创建一个特殊的头结点,它的 `prev` 和 `next` 都指向它自身,表示循环链表的开始和结束。
```cpp
Node* head = new Node();
head->data = 0; // 或者设置初始值
head->prev = head;
head->next = head;
```
3. 插入新节点:每次想在链表头部插入新的节点,你可以创建一个新的节点,然后将其 `prev` 指向当前头结点,`next` 指向前一个节点,并更新头结点的 `next` 指针。
```cpp
void pushFront(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->prev = head;
newNode->next = head->prev;
head->prev->next = newNode;
head->prev = newNode;
}
```
4. 示例完整代码:
```cpp
#include <iostream>
// 定义节点
struct Node {
int data;
Node* prev;
Node* next;
};
// 插入节点到头部
void pushFront(Node*& head, int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->prev = head;
newNode->next = head->prev;
head->prev->next = newNode;
head->prev = newNode;
}
// 打印循环链表
void printCircularList(Node* node) {
while (node != nullptr) {
std::cout << node->data << " ";
node = node->next;
}
std::cout << std::endl;
}
int main() {
Node* head = new Node();
head->data = 0; // 初始化头结点
pushFront(head, 5);
pushFront(head, 4);
pushFront(head, 3);
std::cout << "循环链表内容: ";
printCircularList(head);
return 0;
}
```
写实验报告:关于根据线性表的抽象数据类型的定义,选择下面任意一种链式结构实现线性表,并完成线性 表的基本功能。 线性表存储结构(五选一): ①带头结点的单链表; ②不带头结点的单链表; ③循环链表; ④双链表; ⑤静态链表。 线性表的基本功能: ①构造(使用头插法、尾插法两种方法); ②插人(要求建立的链表按照关键字从小到大有序); ③删除; ④查找; ⑤获取链表长度; ⑥销毁; ⑦其他(可自行定义)。编写main函数测试线性表的正确性
以下是一个使用带头结点的单链表实现线性表的示例代码:
```c++
#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 定义线性表类
class List {
private:
ListNode* head; // 头节点指针
public:
// 构造函数
List() {
head = new ListNode(0); // 创建头节点
}
// 析构函数
~List() {
ListNode* p = head;
while (p) {
ListNode* q = p->next;
delete p;
p = q;
}
}
// 头插法构造链表
void createHeadList(int n) {
for (int i = 0; i < n; i++) {
int x;
cin >> x;
ListNode* p = new ListNode(x);
p->next = head->next;
head->next = p;
}
}
// 尾插法构造链表
void createTailList(int n) {
ListNode* tail = head;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
ListNode* p = new ListNode(x);
tail->next = p;
tail = p;
}
}
// 按关键字从小到大插入节点
void insert(int x) {
ListNode* p = head;
while (p->next && p->next->val < x) {
p = p->next;
}
ListNode* q = new ListNode(x);
q->next = p->next;
p->next = q;
}
// 删除节点
void remove(int x) {
ListNode* p = head;
while (p->next && p->next->val != x) {
p = p->next;
}
if (p->next) {
ListNode* q = p->next;
p->next = q->next;
delete q;
}
}
// 查找节点
ListNode* find(int x) {
ListNode* p = head->next;
while (p && p->val != x) {
p = p->next;
}
return p;
}
// 获取链表长度
int length() {
int len = 0;
ListNode* p = head->next;
while (p) {
len++;
p = p->next;
}
return len;
}
// 销毁链表
void destroy() {
ListNode* p = head;
while (p) {
ListNode* q = p->next;
delete p;
p = q;
}
head = NULL;
}
// 输出链表
void print() {
ListNode* p = head->next;
while (p) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
}
};
int main() {
List list;
int n;
cin >> n;
list.createHeadList(n); // 使用头插法构造链表
list.print(); // 输出链表
list.insert(5); // 插入节点
list.print(); // 输出链表
list.remove(3); // 删除节点
list.print(); // 输出链表
ListNode* p = list.find(4); // 查找节点
if (p) {
cout << "Found: " << p->val << endl;
} else {
cout << "Not found" << endl;
}
cout << "Length: " << list.length() << endl; // 获取链表长度
list.destroy(); // 销毁链表
return 0;
}
```
注意:以上代码仅为示例,实际实验报告中应该根据具体要求进行修改和完善。