2、整数单链表的建立、查找、插入、删除、输出程序(线性表的链式存储实现),表中不允许有重复数据,保存为LinkList文件。
时间: 2023-10-19 07:04:13 浏览: 92
这里提供一个基于C语言的整数单链表的实现代码。
首先定义一个链表节点的结构体:
```c
typedef struct ListNode {
int val; // 节点存储的整数值
struct ListNode* next; // 指向下一个节点的指针
} ListNode;
```
然后定义一些基本的操作函数:
1. 创建一个空链表
```c
ListNode* createList() {
return NULL;
}
```
2. 查找链表中是否存在某个整数值
```c
bool contains(ListNode* head, int val) {
ListNode* p = head;
while (p != NULL) {
if (p->val == val) {
return true;
}
p = p->next;
}
return false;
}
```
3. 在链表头插入一个节点
```c
ListNode* insertAtHead(ListNode* head, int val) {
ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
new_node->val = val;
new_node->next = head;
return new_node;
}
```
4. 在链表尾插入一个节点
```c
ListNode* insertAtTail(ListNode* head, int val) {
ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
new_node->val = val;
new_node->next = NULL;
if (head == NULL) {
return new_node;
}
ListNode* p = head;
while (p->next != NULL) {
p = p->next;
}
p->next = new_node;
return head;
}
```
5. 在链表中删除一个节点
```c
ListNode* deleteNode(ListNode* head, int val) {
if (head == NULL) {
return NULL;
}
if (head->val == val) {
ListNode* new_head = head->next;
free(head);
return new_head;
}
ListNode* p = head;
while (p->next != NULL && p->next->val != val) {
p = p->next;
}
if (p->next != NULL) {
ListNode* del_node = p->next;
p->next = del_node->next;
free(del_node);
}
return head;
}
```
6. 输出链表中所有节点的值
```c
void printList(ListNode* head) {
ListNode* p = head;
while (p != NULL) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");
}
```
最后在主函数中调用这些操作函数即可:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct ListNode {
int val; // 节点存储的整数值
struct ListNode* next; // 指向下一个节点的指针
} ListNode;
ListNode* createList() {
return NULL;
}
bool contains(ListNode* head, int val) {
ListNode* p = head;
while (p != NULL) {
if (p->val == val) {
return true;
}
p = p->next;
}
return false;
}
ListNode* insertAtHead(ListNode* head, int val) {
ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
new_node->val = val;
new_node->next = head;
return new_node;
}
ListNode* insertAtTail(ListNode* head, int val) {
ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
new_node->val = val;
new_node->next = NULL;
if (head == NULL) {
return new_node;
}
ListNode* p = head;
while (p->next != NULL) {
p = p->next;
}
p->next = new_node;
return head;
}
ListNode* deleteNode(ListNode* head, int val) {
if (head == NULL) {
return NULL;
}
if (head->val == val) {
ListNode* new_head = head->next;
free(head);
return new_head;
}
ListNode* p = head;
while (p->next != NULL && p->next->val != val) {
p = p->next;
}
if (p->next != NULL) {
ListNode* del_node = p->next;
p->next = del_node->next;
free(del_node);
}
return head;
}
void printList(ListNode* head) {
ListNode* p = head;
while (p != NULL) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");
}
int main() {
ListNode* head = createList();
head = insertAtHead(head, 1);
head = insertAtHead(head, 2);
head = insertAtTail(head, 3);
head = insertAtTail(head, 4);
printList(head);
head = deleteNode(head, 2);
head = deleteNode(head, 4);
printList(head);
return 0;
}
```
这里的实现使用了头插法和尾插法,可以根据具体需求选择使用哪种插入方式。注意,在使用完链表后,需要手动释放链表中每个节点的内存,避免内存泄漏。
阅读全文