用c语言编写以head为头指针的带头结点的单链表,并且将结点x 插入第一个结点值为key的结点之前。
时间: 2023-06-26 20:07:18 浏览: 88
下面是用C语言实现带头结点的单链表,并且在第一个值为key的结点之前插入结点x的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node, *LinkList;
LinkList initList() {
LinkList head = (LinkList) malloc(sizeof(Node));
head->next = NULL;
return head;
}
void insertNode(LinkList head, int key, int x) {
Node *p = head->next;
Node *pre = head;
while (p != NULL && p->data != key) {
pre = p;
p = p->next;
}
if (p == NULL) {
printf("No node with value %d\n", key);
return;
}
Node *newNode = (Node *) malloc(sizeof(Node));
newNode->data = x;
newNode->next = pre->next;
pre->next = newNode;
}
void printList(LinkList head) {
Node *p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
LinkList head = initList();
for (int i = 1; i <= 5; i++) {
Node *newNode = (Node *) malloc(sizeof(Node));
newNode->data = i;
newNode->next = head->next;
head->next = newNode;
}
printf("Original list: ");
printList(head);
int key = 3, x = 6;
insertNode(head, key, x);
printf("After inserting %d before the first node with value %d: ", x, key);
printList(head);
return 0;
}
```
解释一下代码:
首先定义了一个`Node`结构体,表示链表中的一个结点。其中`data`表示结点的数据,`next`表示指向下一个结点的指针。`LinkList`是指向`Node`结构体的指针,表示整个链表。
```c
typedef struct Node {
int data;
struct Node *next;
} Node, *LinkList;
```
`initList()`函数用来初始化链表,创建一个头结点并返回头指针。
```c
LinkList initList() {
LinkList head = (LinkList) malloc(sizeof(Node));
head->next = NULL;
return head;
}
```
`insertNode()`函数用来插入结点x,它首先遍历链表,找到第一个值为key的结点,并且记录该结点和它的前一个结点。然后创建一个新的结点,并且把它插入到前一个结点和当前结点之间。
```c
void insertNode(LinkList head, int key, int x) {
Node *p = head->next;
Node *pre = head;
while (p != NULL && p->data != key) {
pre = p;
p = p->next;
}
if (p == NULL) {
printf("No node with value %d\n", key);
return;
}
Node *newNode = (Node *) malloc(sizeof(Node));
newNode->data = x;
newNode->next = pre->next;
pre->next = newNode;
}
```
`printList()`函数用来打印整个链表的值。
```c
void printList(LinkList head) {
Node *p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
```
在`main()`函数中,我们首先初始化链表,然后插入一些结点,打印链表,插入新的结点,再打印链表。
```c
int main() {
LinkList head = initList();
for (int i = 1; i <= 5; i++) {
Node *newNode = (Node *) malloc(sizeof(Node));
newNode->data = i;
newNode->next = head->next;
head->next = newNode;
}
printf("Original list: ");
printList(head);
int key = 3, x = 6;
insertNode(head, key, x);
printf("After inserting %d before the first node with value %d: ", x, key);
printList(head);
return 0;
}
```
输出结果为:
```
Original list: 5 4 3 2 1
After inserting 6 before the first node with value 3: 5 4 6 3 2 1
```
阅读全文