需要设计一个单链表结构,该链表结构数据域存储整数, 编写函数实现基本运算方法。基本运算方法应包括创建链表、销毁链表、求链表长度、求链表某一位置节点的值、查找值为x的节点所在位置、新增节点、插入节点,删除节点。 节点各数据域与指针请自行定义。
时间: 2024-09-13 21:11:02 浏览: 66
单链表是一种常见的数据结构,它由一系列节点组成,每个节点包含数据域和指向下一个节点的指针。在设计单链表存储整数时,我们通常定义节点结构如下:
```c
typedef struct ListNode {
int data; // 数据域,存储整数
struct ListNode *next; // 指针域,指向下一个节点
} ListNode;
```
基于这个结构,我们可以实现所需的基本运算方法:
1. 创建链表:
```c
ListNode* createList() {
ListNode *head = (ListNode*)malloc(sizeof(ListNode)); // 创建头节点,初始化为NULL
head->next = NULL;
return head;
}
```
2. 销毁链表:
```c
void destroyList(ListNode **head) {
ListNode *current = *head, *next;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
*head = NULL;
}
```
3. 求链表长度:
```c
int getLength(ListNode *head) {
int length = 0;
ListNode *current = head->next;
while (current != NULL) {
length++;
current = current->next;
}
return length;
}
```
4. 求链表某一位置节点的值:
```c
int getNodeValue(ListNode *head, int position) {
int index = 0;
ListNode *current = head->next;
while (current != NULL && index < position) {
current = current->next;
index++;
}
if (current != NULL) {
return current->data;
} else {
// 位置超出链表长度
return -1;
}
}
```
5. 查找值为x的节点所在位置:
```c
int findNode(ListNode *head, int x) {
int index = 0;
ListNode *current = head->next;
while (current != NULL) {
if (current->data == x) {
return index;
}
current = current->next;
index++;
}
// 未找到
return -1;
}
```
6. 新增节点:
```c
void addNode(ListNode *head, int value) {
ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = value;
newNode->next = head->next;
head->next = newNode;
}
```
7. 插入节点:
```c
void insertNode(ListNode *head, int position, int value) {
ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = value;
ListNode *current = head;
int index = 0;
while (current != NULL && index < position) {
current = current->next;
index++;
}
if (current != NULL) {
newNode->next = current->next;
current->next = newNode;
} else {
// 位置超出链表长度,只在末尾添加
addNode(head, value);
}
}
```
8. 删除节点:
```c
void deleteNode(ListNode *head, int position) {
ListNode *current = head;
int index = 0;
while (current != NULL && index < position - 1) {
current = current->next;
index++;
}
if (current != NULL && current->next != NULL) {
ListNode *temp = current->next;
current->next = temp->next;
free(temp);
}
// 位置超出链表长度,不进行删除
}
```
阅读全文