双向链表的定义,初始化,插入和删除的具体实现c代码
时间: 2023-09-03 09:26:14 浏览: 46
### 回答1:
双向链表是一种链式数据结构,其中每个节点都包含指向前一个节点和后一个节点的指针。下面是双向链表的定义、初始化、插入和删除的C代码实现:
#### 双向链表的定义
```c
typedef struct node {
int data;
struct node* prev;
struct node* next;
} Node;
typedef struct {
int size;
Node* head;
Node* tail;
} DoublyLinkedList;
```
#### 双向链表的初始化
```c
DoublyLinkedList* init() {
DoublyLinkedList* list = (DoublyLinkedList*) malloc(sizeof(DoublyLinkedList));
list->size = 0;
list->head = NULL;
list->tail = NULL;
return list;
}
```
#### 双向链表的插入
```c
void insert(DoublyLinkedList* list, int data, int index) {
if (index < 0 || index > list->size) {
printf("Invalid index!\n");
return;
}
Node* node = (Node*) malloc(sizeof(Node));
node->data = data;
node->prev = NULL;
node->next = NULL;
if (list->size == 0) {
list->head = node;
list->tail = node;
} else if (index == 0) {
node->next = list->head;
list->head->prev = node;
list->head = node;
} else if (index == list->size) {
node->prev = list->tail;
list->tail->next = node;
list->tail = node;
} else {
Node* curr = list->head;
for (int i = 0; i < index - 1; i++) {
curr = curr->next;
}
node->prev = curr;
node->next = curr->next;
curr->next->prev = node;
curr->next = node;
}
list->size++;
}
```
#### 双向链表的删除
```c
void delete(DoublyLinkedList* list, int index) {
if (index < 0 || index >= list->size) {
printf("Invalid index!\n");
return;
}
Node* temp;
if (list->size == 1) {
temp = list->head;
list->head = NULL;
list->tail = NULL;
} else if (index == 0) {
temp = list->head;
list->head = list->head->next;
list->head->prev = NULL;
} else if (index == list->size - 1) {
temp = list->tail;
list->tail = list->tail->prev;
list->tail->next = NULL;
} else {
Node* curr = list->head;
for (int i = 0; i < index; i++) {
curr = curr->next;
}
temp = curr;
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
}
free(temp);
list->size--;
}
```
### 回答2:
双向链表是一种常见的数据结构,它每个节点包含数据和两个指针,分别指向前一个节点和后一个节点。下面是双向链表的定义、初始化、插入和删除操作的具体实现。
1. 双向链表的定义:
```c
typedef struct Node{
int data;
struct Node* prev;
struct Node* next;
} Node;
```
2. 双向链表的初始化:
```c
Node* createNode(int data){
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
```
3. 双向链表的插入操作:
```c
// 在头节点之前插入新节点
void insertAtBeginning(Node** head, int data){
Node* newNode = createNode(data);
newNode->next = *head;
if (*head != NULL){
(*head)->prev = newNode;
}
*head = newNode;
}
// 在尾节点之后插入新节点
void insertAtEnd(Node** head, int data){
Node* newNode = createNode(data);
if (*head == NULL){
*head = newNode;
return;
}
Node* temp = *head;
while(temp->next != NULL){
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
// 在指定位置pos插入新节点
void insertAtPosition(Node** head, int data, int pos){
if (pos <= 0){
insertAtBeginning(head, data);
} else{
Node* newNode = createNode(data);
Node* temp = *head;
for(int i = 1; i < pos && temp != NULL; i++){
temp = temp->next;
}
if (temp == NULL){ // 若超出链表长度,则插入到尾部
insertAtEnd(head, data);
} else{
newNode->next = temp;
newNode->prev = temp->prev;
temp->prev->next = newNode;
temp->prev = newNode;
}
}
}
```
4. 双向链表的删除操作:
```c
// 删除头节点
void deleteFromBeginning(Node** head){
if (*head == NULL){
return;
}
Node* temp = *head;
*head = (*head)->next;
if (*head != NULL){
(*head)->prev = NULL;
}
free(temp);
}
// 删除尾节点
void deleteFromEnd(Node** head){
if (*head == NULL){
return;
}
Node* temp = *head;
while(temp->next != NULL){
temp = temp->next;
}
if (temp == *head){
*head = NULL;
} else{
temp->prev->next = NULL;
}
free(temp);
}
// 删除指定位置pos的节点
void deleteFromPosition(Node** head, int pos){
if (pos <= 0){
deleteFromBeginning(head);
} else{
Node* temp = *head;
for(int i = 1; i < pos && temp != NULL; i++){
temp = temp->next;
}
if (temp == NULL){
return;
} else{
temp->prev->next = temp->next;
if (temp->next != NULL){
temp->next->prev = temp->prev;
}
free(temp);
}
}
}
```
以上是双向链表的定义、初始化、插入和删除操作的具体实现。
### 回答3:
双向链表(Doubly Linked List)是一种数据结构,由结点构成,每个结点包含一个数据元素和两个指针,分别指向前一个结点和后一个结点。
1. 定义:
```c
typedef struct Node {
int data; // 数据元素
struct Node* prev; // 前一个结点指针
struct Node* next; // 后一个结点指针
} Node;
typedef struct DoublyLinkedList {
Node* head; // 头结点指针
} DoublyLinkedList;
```
2. 初始化:
```c
void initDoublyLinkedList(DoublyLinkedList* list) {
list->head = NULL;
}
```
3. 插入:
```c
void insertNode(DoublyLinkedList* list, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
if(list->head == NULL) { // 若链表为空
newNode->prev = NULL;
newNode->next = NULL;
list->head = newNode;
} else {
newNode->prev = NULL;
newNode->next = list->head;
list->head->prev = newNode;
list->head = newNode;
}
}
```
4. 删除:
```c
void deleteNode(DoublyLinkedList* list, int data) {
Node* currentNode = list->head;
while(currentNode != NULL) {
if(currentNode->data == data) {
if(currentNode->prev == NULL) { // 若为头结点
list->head = currentNode->next;
if(list->head != NULL) {
list->head->prev = NULL;
}
} else if(currentNode->next == NULL) { // 若为尾结点
currentNode->prev->next = NULL;
} else {
currentNode->prev->next = currentNode->next;
currentNode->next->prev = currentNode->prev;
}
free(currentNode);
return;
}
currentNode = currentNode->next;
}
}
```
以上是双向链表的定义、初始化、插入和删除的具体实现的C代码。注意,在插入和删除操作中,需要处理头结点和非头结点的情况,并且要释放节点内存空间。