实现线性表的链式存储定义,完成单链表的创建(头插法、尾插法)、插入、删除、查找等常用操作,将线性链表逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,以此类推。C语言
时间: 2024-09-24 18:26:35 浏览: 26
在C语言中,线性表的链式存储可以这样定义:
```c
// 定义节点结构体
typedef struct Node {
int data; // 数据域
struct Node* next; // 指针域,指向下一个节点
} Node;
```
以下是实现单链表的一些基本操作:
**1. 创建链表(头插法):**
```c
void insertAtHead(Node** head, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}
```
**2. 创建链表(尾插法):**
```c
void insertAtTail(Node** head, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
if (*head == NULL) {
*head = newNode;
return;
}
Node* lastNode = *head;
while (lastNode->next != NULL)
lastNode = lastNode->next;
lastNode->next = newNode;
}
```
**3. 插入节点:**
```c
void insertNode(Node** head, int index, int value) {
if (index <= 0)
return insertAtHead(head, value);
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
Node* current = *head;
for (int i = 0; i < index - 1 && current != NULL; ++i)
current = current->next;
if (current == NULL)
return;
newNode->next = current->next;
current->next = newNode;
}
```
**4. 删除节点:**
```c
void deleteNode(Node** head, int key) {
Node* temp = *head, *prev = NULL;
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL)
return;
prev->next = temp->next;
free(temp);
}
```
**5. 查找节点:**
```c
Node* searchNode(Node* head, int key) {
Node* current = head;
while (current != NULL && current->data != key)
current = current->next;
return current;
}
```
**6. 线性链表逆置:**
```c
void reverseList(Node** head) {
Node* prev = NULL;
Node* current = *head;
Node* nextTemp = NULL;
while (current != NULL) {
nextTemp = current->next;
current->next = prev;
prev = current;
current = nextTemp;
}
*head = prev;
}
```
以上就是链式存储下单链表的基本操作及逆置实现。注意,在实际应用中,需要处理好内存管理,避免内存泄漏。