数据结构基础篇(4)

十六.循环链表

• 概念
  • 循环链表是一种头尾相接的链表（最后一个结点的指针域指向头结点，整个链表形成一个环）
• 优点
  • 从表任一结点出发均可找到表中其他结点
• 判断终止
  • 由于循环链表中没有NULL指针，所以涉及遍历操作时，终止条件不像非循环链表那样判断p或p->next是否为空，而是是否等于头指针
  • 循环条件从p！=NULL到p！=L，p->next！=NULL到p->next！=L（单循环链表）
• 时间复杂度
  • 头指针表示单循环链表
    • 找a~1的时间复杂度：O（1）
    • 找a~n的时间复杂度：O（n）
      • 注意
        • 表的操作常常在表的首尾位置上进行
  • 尾指针表示单循环链表
    • a~1的存储位置是：R->next->next
    • a~n的存储位置是：R
    • 时间复杂度均为O（1）

• LinkList Connect(LinkList Ta,LinkList Tb)    //假设Ta.Tb都是非空的单循环链表
  {vp=Ta->next;    //p存表头结点Ta->next=Tb->next->next;    //Tb表头连接Ta表尾delete Tb->next;    //释放Tb表头结点Tb->next=p;    //修改指针return Tb;
  }  

十七.双向链表

• 双向链表的由来
  • 查找某结点的后续结点的执行时间=O(1)
    • 单链表结点->有指示后继的指针域->后继结点
  • 查找某结点的前驱结点的执行时间=O（n）
    • - ->无指示前驱的指针域->依次寻找前驱结点
• 双向链表的概念
  • 在单链表的每个结点里再增加一个指向其直接前驱的指针域prior，这样链表就形成了有两个方向不同的链。
• 双向链表的特点
  • 双向链表也有循环表
    • 让头结点的前驱指针指向链表的最后一个节点
    • 让最后一个节点的后继指针指向头结点
• 双向链表结构的对称性
  • p->prior->next=p=p->next->prior
• 在双向链表中有些操作（如：ListLength、GetElem等），因仅涉及一个方向的指针，所以它们的算法与线性链表的相同。
• 在插入、删除时，则需同事修改两个方向上的指针，两个的操作的时间复杂度都为O（n）。

双向链表的插入

void ListInsert_DuL(DuLinkList &L,Init i,ElemType e)    //在带头结点的双向循环链表L中第i个位置之前插入元素e
{if(!(p=GetElemP_DuL(L,i)))return ERROR;s=new DuLNOde;s->date=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;return OK;
}//ListInsert_Dul

双向链表的删除

void ListDelete_DuL(DuLinkList &L,Init i,ElemType &e)    //删除带头节点的双向循环链表L的第i个元素，并返回e
{if(!(p=GetElemP_DuL(L,i)))return ERROR;e=p->data;p->prior->next=p->next;p->next->prio=p->prior;free(p)return OK;
}//ListDelete_Dul

十八.单链表，循环链表和双向链表的时间效率比较

时间效率的比较	查找表头结点（首元结点）	查找表尾结点	查找结点*P的前驱结点
带头结点的单链表L	L->next 时间复杂度O(1)	从L->next依次向后遍历时间复杂度O(n)	通过p->next无法找到其前驱
带头结点仅设头指针L的循环单链表	L->next 时间复杂度O(1)	从L->next依次向后遍历时间复杂度O(n)	通过p->next可以找到其前驱 时间复杂度O(n)
带头结点仅设尾指针R的循环单链表	R->next| 时间复杂度O(1)	R 时间复杂度O(1)	通过p->next可以找到其前驱 时间复杂度O(n)
带头结点的双向循环链表L	L->next 时间复杂度O(1)	L->prior 时间复杂度O(1)	p->prior 时间复杂度O(1)

十九.顺序表和链表的比较

• 链式存储结构的优点
  • 节点空间可以动态申请和释放
  • 数据元素的逻辑次序靠节点的指针来指示，插入和删除时不需要移动数据元素
• 链式存储结构的缺点
  • 存储密度小，每个结点的指针域需额外占用存储空间。当每个节点的数据域所占字节不多时，指针域所占存储空间的比重闲得很大。
    • 存储密度
      • 概念
        • 结点数据本身所占的存储量和整个节点结构所占的存储量之比
      • 公式
        • 存储密度=结点数据本身占用的空间/结点占用的空间总量
      • 比较
        • 顺序表存储密度1，链式小于1。
  • 链式存储结构是非随机存储结构。对任一结点的操作都要从头指针依指针链查找到该结点，增加了算法的复杂度。
• 顺序表和链表比较图

比较项目\存储结构	顺序表	链表
空间-存储空间	预先分配，导致空间闲置或溢出现象	动态分配，不会出现存储空间闲置或溢出现象
空间-存储密度	不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1	需要借助指针来体现元素间的逻辑关系，存储密度小于1.
时间-存取元素	随机存储，按位置访问元素的时间复杂度O(1)	顺序存储，按位置访问元素时间复杂度O(n)
时间-插入、删除	平均移动约表中一半元素，时间复杂度O(n)	不需要移动元素，确定插入，删除位置后，时间复杂度O
适用情况	表长变化不大，能事先确定变化的范围。 很少进行插入或删除操作，经常按元素位置序号访问数据元素。	长度变化较大 频繁进行插入或删除操作

二十.线性表的应用

• 线性表的合并
  • 问题
    • 假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A=AUB
  • 解决

void union(List &La,List Lb)
{La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e))ListInsert(&La,++La_len,e);    }
}    //算法的时间复杂度是：O(ListLength(La)*ListLength(Lb))

• 有序表的合并
  • 问题
    • 已知线性表La和Lb中的数据元素按值非递减有序排列，现要求LA和Lb归并为一个新的线性表Lc，Lc中的数据元素扔按值非递减有序排列。
  • 解决
    • 创建一个空表Lc
    • 依次从La或Lb中“摘取”元素值较小的节点插入到Lc表的最后，直到其中一个表边空为止
    • 继续将La或Lb其中一个表的剩余节点插入在Lc表的最后

用顺序表来实现

void MergeList_Sq(SqList LA,SqList Lb,SqList &LC)
{pa=LA.elem;pb=LB.elem;    //指针pa和pb的初值分别指向两个表的第一个元素LC.length=LA.length+LB.length;    //新表长度为待合并量表的长度之和LC.elem=new ElemType[LC.length];    //为合并后的新表分配一个数组空间pc=LC.elem;    //指针pc指向新表的第一个元素pa_last=LA.elem+LA.length-1;    //指针pa_last指向LA表的最后一个元素pb_last=LB.elem+LB.length-1;     //指针pa_last指向LB表的最后一个元素while(pa<=pa_last && pb<=pb_last)    //两个表都非空{if(*pa<=*pb)*pc++=*pa++;    //依次“摘取”两表中的最小值else *pc++=*pb++;                                                          }while(pa<=pa_last)*pc++=*pa++;     //LB表已到达表尾，将LA中剩余元素加入LCwhile(pb<=pb_last)*pc=++=*pb++;    //LA表已到达表尾，将LB中剩余元素加入LC
}    //MergeList_Sq//算法的时间复杂度是：O(ListLength(La)*ListLength(Lb))

用链表来实现

void MergeList_L(SqList &La,SqList &Lb,SqList &Lc)
{pa=La->next;pb=Lb->next;pc=Lc=La;    //用La的头结点作为Lc的头结点while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;        }               else{pc->next=pb;pc=pb;pb=pb->next;        }     }pc->next=pa?pa:pb；  //插入剩余段delete Lb;    //释放Lb的头结点
}    //算法的时间复杂度是：O(ListLength(La)*ListLength(Lb))

• 一元多项式的运算
  • 多项式创建
  • 创建一个只有头结点的空链表
  • 根据多项式的项的个数n，循环n次执行以下操作
    • 生成一个新结点*s
    • 输入多项式当前项的系数和指数赋给新节点*s的数据域
    • 设置一前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱，pre初值指向头结点。
    • 指针q初始化，指向首元结点
    • 循链向下逐个比较链表中当前结点与输入项指数，找到第一个大与输入项指数的节点*q
    • 将输入项结点*s插入到结点*q之前

void CreatePolyn(Polynomial &P,int n)    //输入m项的系数和指数，建立表示多项式的有序链表P
{P=new PNode;p->next=NULL;    //先建立一个带头结点的单链表for(i=1;i<=n;i++)    //依次输入n个非零项{s=new PNode;    //生成新节点cin>>s->coef>>s->expn;    //输入系数和指数pre=P;    //pre用于保存q的前驱，初值为头结点q=P->next;    //q初始化，指向首元结点while(q&&q->expn<s->expn)    //找到第一个大于输入项指数的项*q{pre=q;q=q->next;        }    s->next=q;    //将输入项s插入到q和其前驱结点pre之间pre->next=s;}
}