2.3.2 单链表上基本操作的实现.md

↩返回主页

⬅上一节 / 下一节➡

---

2.3.2 单链表上基本操作的实现

• 头插法建立

  

  LinkList List_HeadInsert(LinkList &L) {
      LNode *s; int x;
      L = (LinkList)malloc(sizeof(LNode));
      L->next = NULL;
      scanf("%d", &x);
      while(x != 9999) {
          s = (LNode*)malloc(sizeof(LNode));
          s->data = x;
          s->next = L->next;
          L->next = s;
          scanf("%d", &x);
      }
      return L;
  }

  • 时间复杂度：插入 n 个结点需要 n 次，故 T(n) = O(n)

    注：后续分析时间复杂度均为 最坏时间复杂度

• 尾插法建立

  

  LinkList List_TailInsert(LinkList &L) {
      int x;
      L = (LinkList)malloc(sizeof(LNode));
      LNode *s, *r=L;
      scanf("%d", &x);
      while(x != 9999) {
          s = (LNode*)malloc(sizeof(LNode));
          s->data = x;
          r->next = s;
          r = s;  // r 为尾结点
          scanf("%d", &x);
      }
      return L;
  }

  • 时间复杂度：插入 n 个结点需要 n 次，故 T(n) = O(n)

• 按序号查找

  LNode *GetElem(LinkList L, int i) {
      int j=1;
      LNode *p = L->next;
      if(i == 0)
          return L;
      if(i < 1)
          return NULL;
      while(p && j<i) {
          p = p->next;
          j++;
      }
      return p;
  }

  • 时间复杂度：O(n)

• 按值查找

  LNode *LocateElem(LinkList L, ElemType e) {
      LNode *p = L->next;
      while(p!=NULL && p->data!=e)
          p = p->next;
      return p;
  }

  • 时间复杂度：O(n)

• 插入节点

  

  p = GetElem(L, i-1);
  s->next = p->next;
  p->next = s;

• 删除节点

  

  p = GetElem(L, i-1);
  q = p->next;
  p->next = q->next;
  free(q);

• 求表长

  

  int count=0;
  p = head;
  while(p->next != NULL) {
      count++;
      p = p->next;
  }

💡 题型

  xxx

单项选择题

1. xxxx（ ）

   A. xxx
   B. XX
   C. Xx
   D. xX
   
   

   查看解析

   答案：x

---

返回顶部⤴

-- 完 --