(1) 算法思路:
- 初始化一个头结点指针head,使其指向NULL。
- 创建一个新节点,并将数据元素赋值给新节点的data域。
- 将新节点插入到链表的末尾,即遍历链表直到找到最后一个节点,然后将最后一个节点的next指针指向新节点。
- 遍历链表,输出每个节点的数据元素。
(2) 算法实现:
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode* next;
} LinkList;
// 初始化链表
void InitList(LinkList** head) {
*head = NULL; // 初始时头结点指针为空
}
// 在链表末尾插入新节点
void InsertAtEnd(LinkList** head, ElemType data) {
LinkList* newNode = (LinkList*)malloc(sizeof(LinkList)); // 创建新节点
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) { // 若链表为空,则将头结点指针指向新节点
*head = newNode;
return;
}
LinkList* temp = *head;
while (temp->next != NULL) { // 找到最后一个节点
temp = temp->next;
}
temp->next = newNode; // 将最后一个节点的next指针指向新节点
}
// 遍历链表并输出每个数据元素
void TraverseList(LinkList* head) {
if (head == NULL) {
printf("链表为空\n");
return;
}
LinkList* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
int main() {
LinkList* list;
InitList(&list); // 初始化链表
// 在链表末尾插入节点
InsertAtEnd(&list, 1);
InsertAtEnd(&list, 2);
InsertAtEnd(&list, 3);
// 遍历链表并输出数据元素
TraverseList(list);
return 0;
}
(3) 算法的时间复杂度:在单链表末尾插入新节点的操作的时间复杂度为O(n),其中n为当前链表中的节点数量。遍历链表输出数据元素的操作的时间复杂度也是O(n)。因此,整体算法的时间复杂度为O(n)。
内容由零声教学AI助手提供,问题来源于学员提问