编写一个程序,实现单链表的各种基本运算,并在此基础上完成如下功能: 1.创建单链表 2.采用头插或尾插法依次插入节点元素的值 3.输出单链表 4.输出单链表的长度 5.判断单链表是否为空 6.输出单链表第i个位置上的元素 7.删除单链表第i个位置上的元素 8.数据结构类型定义
时间: 2024-09-19 19:17:13 浏览: 62
首先,我们需要定义单链表的数据结构类型,包含一个指向下一个节点的指针和存储数据的域。这里我们将创建一个名为`ListNode`的结构体:
```c
// 定义单链表节点
typedef struct ListNode {
int data; // 存储整数值
struct ListNode* next; // 指向下一个节点的指针
} ListNode;
```
接下来,我们可以实现单链表的基本操作:
1. 创建单链表(初始化为NULL):
```c
ListNode* createList() {
return (ListNode*)malloc(sizeof(ListNode)); // 分配内存
}
```
2. 首部插入元素(假设链表已存在且非空):
```c
void insertAtHead(ListNode** head, int value) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}
```
3. 尾部插入元素(假设链表已存在且非空):
```c
void insertAtTail(ListNode** head, int value) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = value;
if (*head == NULL) {
*head = newNode;
return;
}
ListNode* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
```
4. 输出链表:
```c
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
```
5. 判断链表是否为空:
```c
int isEmpty(ListNode* head) {
return head == NULL;
}
```
6. 获取链表长度(使用迭代或递归,这里用迭代):
```c
int getLength(ListNode* head) {
int count = 0;
ListNode* temp = head;
while (temp != NULL) {
count++;
temp = temp->next;
}
return count;
}
```
7. 删除第i个位置的元素(假设链表长度大于等于i):
```c
void deleteElement(ListNode** head, int i) {
if (isEmpty(*head)) return;
if (i == 0) { // 如果要删除的是头结点
ListNode* temp = *head;
*head = (*head)->next;
free(temp);
} else {
ListNode* current = *head;
for (int j = 0; j < i - 1 && current != NULL; j++) {
current = current->next;
}
if (current == NULL || current->next == NULL) {
printf("Invalid index.\n");
return;
}
ListNode* toDelete = current->next;
current->next = current->next->next;
free(toDelete);
}
}
```
8. 删除单链表(释放所有节点内存):
```c
void deleteList(ListNode** head) {
ListNode* temp = *head;
while (temp != NULL) {
ListNode* nextTemp = temp->next;
free(temp);
temp = nextTemp;
}
*head = NULL;
}
```
以上就是单链表的各种基本运算及其相关功能的实现。你可以根据这些函数进行组合使用。
阅读全文