数据结构与算法·其四

链表

链式存储结构

每个元素在存储器上的位置是任意的，逻辑相邻并不一定物理相邻。

每个节点存储的数据有两个部分。数据域和指针域。

访问时只能通过头节点依次向后查找，这种方法称为顺序存储法

如何判断链表是否为空

• 有头节点，头节点的指针为空时；
• 无头节点，头指针为空时；

链表种类

• 单链表：指针域只存储下一个元素的位置
• 双链表：指针域存储上一个和下一个的位置
• 循环链表：链表结点首尾相接

具体算法

• 初始化
  1. L=new LNode
  2. L->next=Null
• 销毁
  1. while(L){p=L;L=L->next;delete p;}
• 清空
  1. p=L->next;while(p){q=p->next;delete p;p=q;}L->next=NULL;
  2. 相比较于删除操作，仅仅保留了头节点
• 获取表长
  1. p=L->next;i=0;while(p){i++;p=p->next;}return i;
• 获取第i个元素
  1. p=L->next;j=1;while(p&&j<i){p=p->next;++j}if(!p||j>i)return ERROR;e=p->data;return OK;
• 按值查找
  1. p=L->next;while(p&&p->data!=e){p=p->next}return p;
• 插入节点（在第i个元素之前插入数据e）
  1. p=L;j=0;
  2. while(p&&j<i-1){p=p->next;++j;}
  3. if(!p||j>i-1)return ERROR
  4. s=new LNode;
  5. s->next=p->next;p->next=s;return OK;
• 删除节点（删除第i个元素）
  1. p=L;j=0;
  2. while(p&&j<i-1){p=p->next;++j;}
  3. if(!(p->next)||j>i-1)return ERROR;
  4. q=p->next;p->next=q->next;
  5. delete q;return OK;