数据结构（二）:链表、链队列

上一篇博文中主要总结线性表的顺序存储结构实现，比如顺序表、顺序队列和顺序栈。具体可以参考上篇博文

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

Void InsertAfter(LNode *ptr,Datatypeitem)

{

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;

Void SetLList(LList *L);

Void FreeList(LList *L);

lnt LListSize(LList *L);

lnt LListEmpty(LList *L);

lnt LListLocate(LList *L,DataType item);

。。。。

求线性表的长度

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;

Void LListSetData(LList *L,Datatypeitem,int pos)

{

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;

void SetLQuene( LQueue *Q )

{

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) ;

}

void OutQUEUE (LQueue *Q )

{

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

转载于:https://www.cnblogs.com/huty/p/8519301.html