使用c语言建立带头结点的单链表,试编写算法,在第i个位置前插入一个新元素,在第j个位置删除一个元素
时间: 2024-09-09 19:11:58 浏览: 20
在C语言中,建立一个带头结点的单链表,首先需要定义链表的节点结构体,包含数据域和指向下一个节点的指针。然后实现插入和删除操作的函数。
以下是一个简单的示例:
首先,定义链表节点结构体:
```c
typedef struct Node {
int data; // 数据域
struct Node *next; // 指向下一个节点的指针
} Node;
typedef struct {
Node *head; // 指向头结点的指针,头结点通常不存储数据
} LinkedList;
```
接着,创建一个带头结点的单链表,并实现插入和删除操作:
```c
// 初始化链表
void InitLinkedList(LinkedList *list) {
list->head = (Node *)malloc(sizeof(Node)); // 分配头结点空间
if (list->head == NULL) {
exit(1); // 内存分配失败,退出程序
}
list->head->next = NULL; // 头结点的next指针设为NULL
}
// 在第i个位置前插入元素
void InsertBefore(LinkedList *list, int i, int data) {
if (i <= 0) return; // 插入位置不合法
Node *p = list->head; // 从头结点开始
int j = 0;
while (p != NULL && j < i - 1) { // 移动到第i-1个位置的节点
p = p->next;
j++;
}
if (p == NULL) return; // 没有找到第i-1个位置
Node *newNode = (Node *)malloc(sizeof(Node)); // 创建新节点
if (newNode == NULL) {
exit(1); // 内存分配失败,退出程序
}
newNode->data = data; // 设置新节点数据
newNode->next = p->next; // 新节点指向第i个位置的节点
p->next = newNode; // 第i-1个位置的节点指向新节点
}
// 在第j个位置删除一个元素
void DeleteAt(LinkedList *list, int j) {
if (j <= 0) return; // 删除位置不合法
Node *p = list->head; // 从头结点开始
int k = 0;
while (p->next != NULL && k < j - 1) { // 移动到第j-1个位置的节点
p = p->next;
k++;
}
if (p->next == NULL) return; // 没有找到第j个位置
Node *temp = p->next; // 临时保存第j个位置的节点
p->next = temp->next; // 第j-1个位置的节点指向第j+1个节点
free(temp); // 释放第j个位置的节点内存
}
```
注意:在实际使用中,应当对函数进行相应的错误检查,并且在删除节点后,需要考虑是否需要释放被删除节点的内存以避免内存泄漏。