创建一个带头结点的单链表。
要求:此单链表长度为 10;创建完成后,输出显示所创建单链表各结点的
值。
该回答引用chatgpt:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node, *LinkedList;
LinkedList createLinkedList(int n) {
LinkedList head = (LinkedList) malloc(sizeof(Node)); // 创建头结点
head->next = NULL;
LinkedList tail = head; // 指向链表最后一个结点的指针
int i;
for (i = 0; i < n; i++) {
LinkedList node = (LinkedList) malloc(sizeof(Node)); // 创建新结点
node->data = i + 1;
node->next = NULL;
tail->next = node; // 将新结点添加到链表尾部
tail = node; // 将 tail 指向新结点
}
return head;
}
void printLinkedList(LinkedList head) {
LinkedList p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
LinkedList list = createLinkedList(10);
printLinkedList(list);
return 0;
}
有啥困难?
答:①空间的比较:顺序表开辟的是一段连续的空间,然后进行数据的增删改查。而单链表则是一次开辟一个节点的空间,用来存储当前的数据和指向下一个节点的指针。
②时间的比较:访问顺序表中的元素,采用下标进行访问,时间复杂度为O(1),而访问链表中的某一元素,需要遍历整个链表,直到找到元素为止。因此单链表的平均时间复杂度为O(n)。
但是在删除和插入元素时,因为顺序表是连续的,所以需要把被删除或插入的元素后面的元素全部后移或者前移,时间花销很大。而单链表在插入或删除元素时,只需要改变前驱节点的指针就可以了。因此顺序表插入删除元素的平均时间为0(n),而链表的时间复杂度为O(1)。
使用情况:
查询操作使用的比较频繁时,使用顺序表会好一些;在插入、删除操作使用的比较频繁时,使用单链表会好一些。