创建一个链表并进行初始化,对链表进行插入、删除、查找和更改。算法思路
时间: 2023-12-18 10:05:15 浏览: 49
链表是一种常见的数据结构,它由一系列结点组成,每个结点包含两个部分:数据域和指针域。数据域用来存储数据,指针域用来指向下一个结点。链表有单向链表、双向链表、循环链表等多种形式。
下面是创建一个单向链表并进行初始化,对链表进行插入、删除、查找和更改的算法思路:
1. 定义链表结构体
```c
struct ListNode {
int val;
struct ListNode *next;
};
```
2. 创建链表并初始化
```c
struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->val = 0; // 头结点不存储数据
head->next = NULL;
```
3. 插入结点
```c
void insert(struct ListNode *head, int index, int val) {
struct ListNode *cur = head;
for (int i = 0; i < index && cur != NULL; i++) {
cur = cur->next;
}
if (cur == NULL) {
return;
}
struct ListNode *newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = cur->next;
cur->next = newNode;
}
```
4. 删除结点
```c
void delete(struct ListNode *head, int index) {
struct ListNode *cur = head;
for (int i = 0; i < index && cur != NULL; i++) {
cur = cur->next;
}
if (cur == NULL || cur->next == NULL) {
return;
}
struct ListNode *tmp = cur->next;
cur->next = cur->next->next;
free(tmp);
}
```
5. 查找结点
```c
int search(struct ListNode *head, int val) {
struct ListNode *cur = head->next;
int index = 0;
while (cur != NULL && cur->val != val) {
cur = cur->next;
index++;
}
if (cur == NULL) {
return -1;
} else {
return index;
}
}
```
6. 更改结点
```c
void update(struct ListNode *head, int index, int val) {
struct ListNode *cur = head->next;
for (int i = 0; i < index && cur != NULL; i++) {
cur = cur->next;
}
if (cur == NULL) {
return;
}
cur->val = val;
}
```
以上是单向链表的基本操作,可以根据实际需求进行修改和扩展。