数据结构-线性表的链式存储结构

除单链表外，链式存储结构还有循环链表、双链表...

1、循环链表

结构：尾结点的指针域指向头结点或表的首元结点。

特点：表中所有节点都链接在一个环上。

（1）循环单链表的合并算法：将两个循环单链表合并成一个单链表。

思路：先遍历两个链表找到表尾，再将第一个表的表尾链接第二个表的表头，第二表尾链接到第一表头。

//方式一
LinkList merge_1(LinkList LA,LinkList LB)
{
    Node *p,*q;
    p=LA;
    q=LB;
    //找到LA表尾
    while(p->next!=LA)
        p=p->next;
    //找到LB表尾
    while(q->next!=LB)
        q=q->next;
    q->next=LA;//修改LB表尾指针，使之指向LA头结点
    p->next=LB->next;//修改LA尾指针，使之指向LB中第一个结点
    free(LB);//删除LB头结点
    return(LA);
}


//方式二
LinkList merge_2(LinkList LA,LinkList LB)
{
    Node *p;
    p=LA->next;//保存LA头结点地址
    LA->next=LB->next->next;//LB的开始结点连接LA的终端结点
    free(LB->next);//释放LB头结点
    LB->next=p;//LA头结点链接到LB终端结点之后
    return LB;
}

2、双向链表

C语言结构定义

typedef struct DNode
{
    ElemType data;
    struct DNode *prior,*next;
}DNode.*DoubleList;

双向链表特点：任一结点均可沿前驱和后继两个方向操作。

（1）尾插法建立双链表

void createDlist(DNode *L,int a[],int n)
{
	DNode *s,*r;
	int i;
	L=(DNode*)malloc(sizof(DNode));
	L->prior=Null;
	L->next=Null;
	r=L;//r始终指向终端结点，开始头结点也是尾结点
	for(i=0;i<n;++i)
	{
		s=(DNode*)malloc(sizof(DNode));
		s->data=a[i];
		r->next=s;
		s->prior=r;
		r=s;
	}
	r->next=Null;
}

（2）查找结点

在双链表中差按照第一个值为x的结点，从第一个结点开始，边扫描比较，若找到这样的结点，则返回结点指针，否则返回Null。

DNode* findNode(DNode *L,ElemType x)
{
	DNode *p=L->next;
	while(p!=Null)
	{
		if(p->data==x)
			break;
		p=p->next;
	}
	return p;
}

（3）双向链表的插入操作

假设在双链表中p所指的结点之后插入一个结点s，其操作语句：

s->next=p->next;
s->prior=p;
p->next=s;
s->next->prior=s;

note：上述插入不可改变顺序，先将要插入的结点的两边链接好，这样就可以保证不会发生链接之后找不到结点的情况。

（4）删除操作

设要删除双链表中p结点的后继结点，其操作语句：

q=p->next;
p->next=q->next;
q->next->prior=p;
free(q);

3、静态链表

采用数组模拟实现链表。

结点结构定义，

typedef struct{
    ElemType data;
    int cursor;
}component,Stacticlist[Maxsize]

（1）初始化操作

void initial(Stacticlist space,int *av)
{
    int k;
    space[0]->cursor=-1;
    for(k=1;k<Maxsize-1;k++)
    {
        space[k]->cursor=k+1;
    }
    space[Maxsize-1]=-1;
    *av=1;
}

（2）分配结点操作

int getNode(Stacticlist space,int *av)
{
    int i;
    i=av;
    av=space[av].cursor;    //av指针为头指针的下一个
    return i;        //返回可用新结点
}

（3）结点回收操作

void freeNodes(Stacticlist space,int *av,int k)
{
    space[k].cursor=av;
    av=k;
}