上一篇博文中主要总结线性表的顺序存储结构实现，比如顺序表、顺序队列和顺序栈。具体可以参考上篇博文
http://blog.csdn.net/lg1259156776/article/details/46993591
下面要进行学习和总结的是线性表的链式存储结构实现，比如链表和链队列。
顺序存储结构的优缺点
优点是逻辑相邻，物理相邻，可随机存取任一元素，存储空间使用紧凑；缺点是插入、删除操作需要移动大量的元素，平均移动n/2，预先分配空间需按照最大空间分配，利用不充分（C++ STL模板库中实现的vector的存储空间是由类自动分配，无需用户管理，伴随着插入和删除，其容量也总是会调整的，这个内存维护总是需要花费心思的），表容量难以扩充。链表
单向链表
每个元素(表项)由结点(Node)构成typedef struct LNode
{
Datatype data;
struct LNode *next;
}
单向链表的存贮映像
对应的指针操作
LNode *p,*q; p->data;p->next; q=new LNode; q=p; q=p->next; (q指向后继) p=p->next; (指针移动) p->next=q; (链指针改接) p->next= q->next; 链表结点的基本运算Void SetNode(LNode *front);//构造函数,结点的next置NULL Node*NextNode(LNode *ptr);//返回后继指针 Void InsertAfter(LNode *ptr,Datatype item);//在结点*ptr插入 Void DeleteAfter(LNode *ptr);//删除结点后的一个结点. 在结点后插入数据指针的变化：
newnode->next= current->next;
current->next = newnode
{
LNode *q;
q=new LNode;
If (q==NULL){错误信息}
q->data=item;
q->next=ptr->next;
ptr->next=q;
} 在结点后删除数据指针的变化q=p->next;
If(q!=NULL){p.next=q.next;Deleteq;}
单链表的定义
多个类表达一个概念(单链表)：链表结点(ListNode)、链表(List)
Typedef struct
{
LNode *front;
int Size;//并非必要的成员
} LList;
求线性表的长度
int LListSize(LList *L)
{
Lnode *p=L;
int k=0;
while(p){k++,p=p->next;}
return k;
}//时间复杂度O(n)
关于插入的讨论已知结点之后插入,时间复杂度O(1)已知结点之前插入?
需要查找前驱,时间复杂度为O(n),如果指向第一个结点,要修改头指针
Void LListInsertB(LList *L,LNode *p,LNode *s)
{
LNode *q;
if(p==L){s->next=L;L=s;}
else { q=L;
while(q->next!=p)q=q->next;
q->next=s;s->next=p;
}
}
带表头结点的单链表
表头结点位于表的最前端，本身不带数据，仅标志表头 设置表头结点的目的是统一空表与非空表的操作,简化链表操作的实现 头结点:表中的第一个结点，数据域为空 最后一个结点的指针为 NULL 开始结点：第一个数据元素的结点 头指针：指向头结点的指针
设置表头结点的目的是统一空表与非空表的操作,简化链表操作的实现
带表头结点的单链表插入在带表头结点的单链表第一个结点前插入新结点
Newnode->next=p->next ; p->next=newnode
从带表头结点的单链表中删除第一个结点
q= p->link;p->link = q->link;delete q;
{
int i;LNode *ptr;
如果pos不合法，退出
否则
ptr=NextNode(L->front);
for(i=0;i<pos;i++)
ptr=NextNode(ptr);
ptr->data=item
}
循环链表
循环链表是单链表的变形。 循环链表最后一个结点的link指针不为NULL,而是指向了表的前端 为简化操作，在循环链表中往往加入表头结点。 循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。
特殊链表
链表队列
Typedefstruct
{
LNode *front;
LNode *rear;
}LQuene;
{
Q->front=new LNode;
if(Q->front==NULL){err;}
SetNode(Q->front);
Q->rear=Q->front;
}
void EnQueue (LQueue *Q, DataType item){
InsertAfter(Q->rear,item);
Q->rear =NextNode(Q->rear) ;
}
{
if (EMPTY( Q ) ){error;}
else{
temp = Q->front->next ;
Q->front->next =temp->next ;
delete temp ;
if ( Q->front->next == NULL )
Q->rear = Q->front ;
}
}
多项式的存储表示
非常简单的可以想到一下两种表示存储表示：静态数组
int degree;
float coef[maxDegree+1];动态数组
typedef struct
{
int degree;
float *coef;
}Polynomial;
构造函数:
VoidSetPoly ( Polynomial *poly,int sz ) {
Poly->degree= sz;
Poly->coef= new float [degree + 1];
}
以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式不经济
多项式的链表表示
在多项式的链表表示中每个结点三个数据成员
Polynomial( ); //构造函数 int IfZeroPoly ( ); //判是否零多项式 float Coef ( int e); // 返回某次数的系数 int MaxExp ( ); //返回最大指数 PolynomialAdd (); // 加法 PolynomialMinus(); // 减法 PolynomialMult (); // 乘法 float Eval ( float x); //求值
*************************************************************************************************************************************
2015-7-23