单链表运算

一、初始化

void Link::Initiate() {
  DeleteAll();
  head = NULL;
}

二、建立单链表

(一)从表尾到表头建立单链表(不带有空白头结点)

链表与顺序表不同,它是一种动态管理的存储结构,链表中的每个结点占用的存储空间不是预先分配的,而是在运行时系统根据需求动态生成的,因此建立单链表应该从空表开始。

可以在每读入一个数据元素后申请一个结点,然后插在链表的头部(从表尾到表头建立单链表)。

下图体现了线性表(20,50,10,80,40)的链式存储结构的建立过程。因为是在链表的头部插入,读入数据的顺序和线性表中的逻辑顺序是相反的。

从表尾到表头建立单链表
从表位到表头建立单链表

算法实现如下:

void Link::HeadCreate(int n) {
  DeleteAll();

  Item *s, *p;
  int i;

  p = NULL;

  for(i = 1; i <= n; i++) {
    s = new Item();

    cin >> s->data;
    s->next = p;
    
    p = s;
  }

  head = p;
}

(二)从表头到表尾建立单链表(不带有空白结点)

从表尾到表头插入结点建立单链表比较简单,但读入的数据元素的顺序与生成的单链表中元素的顺序是相反的。若希望次序一致,则用从表头到表尾建立单链表的方法。因为每次是将新结点插入链表的尾部,所以需加入一个指针 r 用来始终指向链表中的尾结点,以便能够将新结点插入链表的尾部。

初始状态:头指针 P=NULL,尾指针 r=NULL。按线性表中元素的顺序依次读入数据元素,只要不是结束标志,即申请结点,并将新结点插入 r 所指结点的后面,然后 r 指向新结点(但第一个结点有所不同,注意下面算法中的有关部分)。

从表头到表尾建立单链表
从头到尾建立单链表

算法实现如下:

void Link::TailCreate(int n) {
  DeleteAll();

  Item *s,*r,*p;
  int i;

  p = NULL;

  for (i = 1; i <= n; i++) {
    s = new Item();

    cin >> s->data;

    s->next = NULL;

    if (p == NULL) p = r = s;
    else {
      r->next = s;
      r = s;
    }
  }

  head = p;
}

在上面的算法中,第一个结点的处理和其他结点是不同的,原因是第一个结点加入前链表为空,它没有直接前驱结点,它的地址就是整个链表的指针,需要放在链表的头指针变量中;而其他结点有直接前驱结点,其地址放入直接前驱结点的指针域。

「第一个结点」的问题在很多操作中都会遇到。在链表中插入结点时,将结点插在第一个位置和其他位置是不同的;在链表中删除结点时,删除第一个结点和删除其他结点的处理也是不同的;为了方便操作,有时在链表的头部加入一个空白的「头结点」,头结点的类型与数据结点一致,数据域为空,在标识链表的头指针变量 H 中存放该结点的地址。这样即使是空表,头指针变量 H 也不再为空了。头结点的加入使得「第一个结点」的问题不再存在,也使得「空表」和「非空表」的处理成为一致。

带空白头结点的单链表为空表和非空表
带空头结点的单链表

(三)从表尾到表头建立单链表(带有空白头结点)

void Link::HeadCreateWithHead(int n) {
  DeleteAll();

  Item *s,*p;
  int i;

  p = new Item();

  p->next = NULL;

  for(i = 1; i <= n; i++) {
    s = new Item();

    cin >> s->data;

    s->next = p->next;

    p->next = s;
  }

  head= p;
}

(四)从表头到表尾建立单链表(带有空白头结点)

void Link::TailCreateWithHead(int n) {
  DeleteAll();

  Item *s,*r,*p;
  int i;

  p = new Item();

  p->next = NULL;

  r = p;

  for(i = 1; i <= n; i++) {
    s = new Item();

    cin >> s->data;

    r->next = s;

    r = s;
  }

  r->next = NULL;

  head = p;
}

从上面 4 个算法可以看出,对于不带空白头结点的单链表,空表情况下需要单独处理,而带上空白头结点之后则不用了,算法的时间复杂度均为 O(n)。在以后的单链表算法中,如不加说明则认为单链表是带空白头结点的。

三、求表长

顺序表的表长可以方便获得。相比而言,求单链表的表长稍微复杂些。设有一个移动指针 p 和计数器 j,初始化后,p 所指结点后面若还有结点,p 向后移动,计数器加 1。

算法实现如下:

int Link::Length() {
  int j;
  Item *p;

  j = 1;

  p = head->next;

  while(p != NULL) {
    j++;
    p = p->next;
  }

  return --j;
}

上述算法的时间复杂度为O(n)。

四、查找操作

(一)按序号查找

从单链表的第一个元素结点起,判断当前结点是否是第 i 个,若是,则返回该结点的指针;否则继续下一个结点的查找,直到表结束为止。若没有第 i 个结点,则返回空;如果 i=0;则返回头指针。

算法实现如下,其时间复杂度为O(n):

Item * Link::Locatei(int i) {
  int j = 1;

  Item *p; 

  if (i == 0) return head;

  p = head->next;

  while((p != NULL) && (j < i)) {
    p = p->next;
    j++;
  }

  if (j == i) 
    return p;
  else {
    cout << "position is not correct!" << endl;
    return NULL;
  }
}

(二)按值查找(定位)

从链表的第一个元素结点起,判断当前结点值是否等于 x,若是,返回该结点的指针,否则继续下一个结点的查找,直到表结束为止。若找不到,则返回空。
算法实现如下,其时间复杂度为O(n):

Item * Link::Locatex(DataType x) {

  Item *p;

  p = head->next;

  while ((p != NULL) && (p->data != x))
    p = p->next;

  if (p)
    return p;
  else {
    cout << x << " is not exist!" << endl;
    return NULL;
  }
}

(三)读取第 i 个位置上的元素值

算法实现如下,其时间复杂度为O(n):

DataType Link::Get(int i) { 
  int j;
  Item *p;

  j = 1;
  p = head->next;

  while((j < i) && (p != NULL)) {
    j++;

    p = p->next;
  }

  if ((p == NULL) || (j > i)) {
    cout << "position is not correct!" << endl;

    return NULL;
  } else 
    return p->data;
}

五、插入

单链表插入操作

(一)后插结点

设 p 指向单链表中某结点,s 指向待插入的值为 x 的新结点,将*s插入*p的后面,插入示意图如上图(a)所示:

代码操作顺序为:

  1. s->next = p->next;
  2. p->next = s;

(二)前插结点

设 p 指向链表中某结点,s 指向待插入的值为 x 的新结点,将*s插入*p的前面,插入示意图如上图(b)所示。

与后插不同的是,首先要找到*p的前驱*q,再完成在*q之后插入*s。设单链表头指针为 L,操作如下:

q=L;

while(q->next != p)
  q = q->next;    //找*p 的直接前驱

s->next = q->next;

q->next = s;

后插操作的时间复杂度为 O(1),前插操作因为要找*p的前驱,时间复杂度为 O(n)。其实,我们关心的是数据元素之间的逻辑关系,所以仍然可以将*s插入*p的后面,然后将 p->data 与 s->data 交换即可。这样既满足了逻辑关系,也能使得时间复杂度为 O(1)。

(三)插入算法

  1. 找到第 i-1 个结点;若存在,继续步骤2,否则结束。

  2. 申请新结点,将数据填入新结点的数据域。

  3. 将新结点插入。

前插结点算法如下:

bool Link::Insert(DataType x, int i) {
  Item *p, *s;

  p = Locatei(i-1);

  if(p == NULL) {
    cout << "position is not correct!" << endl;

    return false;
  }

  s = new Item();
  s->data = x;
  s->next = p->next;
  p->next = s;

  return true;
}

六、删除

单列表删除结点示意图:
单链表删除结点

(一)删除结点

设p指向单链表中某结点,删除*p。操作示意图如上所示。通过示意图可见,要实现对结点*p的删除,首先要找到*p的前驱结点*q,然后完成指针的删除操作即可。指针的操作,由下列语句实现。

q->next = p->next;

delete p;

显然,找*p前驱的时间复杂度为 O(n)。
若要删除*p的后继结点(假设存在),则可以直接完成:

s = p->next;

p->next = s->next;

delete s;

该操作的时间复杂度为 O(1)。

(二)删除运算

  1. 找到第 i-1 个结点,若存在,继续步骤 2,否则结束。

  2. 若存在第 i 个结点,则继续步骤 3,否则结束。

  3. 删除第 i 个结点,结束。

算法实现如下,其时间复杂度为O(n):

bool Link::Deleted(int i) { 
  Item *p = Locatei(i-1);
  Item *q;

  if (p == NULL) {
    cout << "position is not correct!" << endl;
    return false;
  }

  q = p->next;

  if (q != NULL) {
    p->next = q->next;
    delete q;
    return true;
  } else {
    cout << "position is not correct!" << endl;
    return false;
  }
}

七、打印

void Link::Print() {
  Item *p;

  p = head->next;

  while (p! = NULL) {
    cout << p->data << " ";
    p = p->next;
  }

  cout << endl;
}

八、删除所有结点

void Link::DeleteAll() {
  Item *p = head, *q;

  while (p != NULL) {
    q = p->next;
    delete p;
    p = q;
  }

  head = NULL;
}

通过上面的基本操作可知:

  1. 在单链表上插入、删除一个结点,必须知道其前驱结点的指针;
  2. 单链表不具有按序号随机访问的特点,只能从头指针开始一个个顺次进行。
用户头像
登录后发表评论