ZBLOG

单链表LinkList类型的定义如下: typedef struct LNode /定 义单链表节点类型 {ElemType data; struct LNode "next; /指向后继节点 } LinkList; (1) 写出算法思路: (4分) (2) 写出算法实现的程序,必要的地方要加上注释; (5 分) (3) 给出算法的时间复杂度。(1 分)

(1) 算法思路:

  • 初始化一个头结点指针head,使其指向NULL。
  • 创建一个新节点,并将数据元素赋值给新节点的data域。
  • 将新节点插入到链表的末尾,即遍历链表直到找到最后一个节点,然后将最后一个节点的next指针指向新节点。
  • 遍历链表,输出每个节点的数据元素。

(2) 算法实现:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef int ElemType;
  4. typedef struct LNode {
  5. ElemType data;
  6. struct LNode* next;
  7. } LinkList;
  8. // 初始化链表
  9. void InitList(LinkList** head) {
  10. *head = NULL; // 初始时头结点指针为空
  11. }
  12. // 在链表末尾插入新节点
  13. void InsertAtEnd(LinkList** head, ElemType data) {
  14. LinkList* newNode = (LinkList*)malloc(sizeof(LinkList)); // 创建新节点
  15. newNode->data = data;
  16. newNode->next = NULL;
  17. if (*head == NULL) { // 若链表为空,则将头结点指针指向新节点
  18. *head = newNode;
  19. return;
  20. }
  21. LinkList* temp = *head;
  22. while (temp->next != NULL) { // 找到最后一个节点
  23. temp = temp->next;
  24. }
  25. temp->next = newNode; // 将最后一个节点的next指针指向新节点
  26. }
  27. // 遍历链表并输出每个数据元素
  28. void TraverseList(LinkList* head) {
  29. if (head == NULL) {
  30. printf("链表为空\n");
  31. return;
  32. }
  33. LinkList* temp = head;
  34. while (temp != NULL) {
  35. printf("%d ", temp->data);
  36. temp = temp->next;
  37. }
  38. }
  39. int main() {
  40. LinkList* list;
  41. InitList(&list); // 初始化链表
  42. // 在链表末尾插入节点
  43. InsertAtEnd(&list, 1);
  44. InsertAtEnd(&list, 2);
  45. InsertAtEnd(&list, 3);
  46. // 遍历链表并输出数据元素
  47. TraverseList(list);
  48. return 0;
  49. }

(3) 算法的时间复杂度:在单链表末尾插入新节点的操作的时间复杂度为O(n),其中n为当前链表中的节点数量。遍历链表输出数据元素的操作的时间复杂度也是O(n)。因此,整体算法的时间复杂度为O(n)。


内容由零声教学AI助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=9210

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?