数据结构---线性表---链表比较与应用

单链表的结构

单链表是一种最简单的链表，结点只包含存储元素本身信息的数据域和存储直接后续结点存储位置的指针域。结构如下图：

循环链表的结构

 表中最后一个元素的指针与不为空，二是指向表头，整个链表形成一个环。与一般链表相比只要给定循环链表中的任一结点地址，就可以完成对表中所有所有元素的遍历。

双向链表的结构

表中的每个结点都有两个指针域，一个指向直接后继，一个指向直接前驱。故而可以从任意结点完成向前或向后查找，并且在插入和删除操作时需要完成对两个方向信息的完善。

应用：一元多项式加法

      设指针ha、hb分别为多项式链表A(x)、B(x)的头指针，指针p、q的初始位置分别指向A(x)、B(x)中的第一项。过程为：比较p、q所指结点中的指数项。

       若：p->exp<q->exp，那么p所指的结点为C(x)中的一项，令p指针后移一个结点；

       若：p->exp>q->exp，则q所指的结点为C(x)中的一项，将q结点插入p结点之前，并令q指针后移一个结点；

       若p->exp==q->exp，则将两个结点中的系数相加，当和不为零时，修改p结点中的系数，释放q结点；否则，删去p结点，同时释放p、q结点。

       这种方法实际上是将B(x)加到A(x)中，最后形成C(x)，因此C(x)中的结点不需要重新生成。

EXPNODE  *AddPoly(EXPNODE *ha,EXPNODE *hb)
{
  p=ha->next; q=hb->next;//两多项式首个元素
  pre=ha; hc=ha;                //多项式头指针
  while (p!=NULL && q!=NULL)
  {	if (p->exp<q->exp){ pre=p; p=p->next; }//a<b
	if (p->exp>q->exp)                                  //a>b
	{ u=q->next; q->next=p->next;p->next=q;
          pre->next=q;
	  pre=q; q=u;//这里有点问题---------------------
	}
	if (p->exp==q->exp)
	{ int x=p->coef+q->coef;
	  if (x!=0){ p->coef=x; pre=p; }
	  else{ pre->next=p->next; free(p);	}
	  p=pre->next; u=q; q=q->next; free(u);
	}
  }
  if (q!=NULL) pre->next=q;
  free(hb);   return(hc);
}

　　顺序表和链表的比较：

顺序表

       – 插入、删除运算时间代价O(n)

       – 预先申请固定长度的数组

       – 如果整个数组元素很满，则没有结构性存储开销

链表

       – 插入、删除运算时间代价O(1)

          但找到第i个删除元素运算时间代价O(n)

       – 存储利用指针，动态地按照需要为表中新的元素分配存储

          空间

       – 每个元素都有结构性存储开销