数据结构-双链表_slink*p=l,*s

说明

     与单链表相比，在双链表中增加了一个指向其直接前驱的指针，这样形成的链表就有两个不同的方向链，使得可以从已知的结点向前查询。

插入

删除

代码

/*
**	dlink create by yubo.wang 2018.9.12
*/
#include <stdio.h>
#include <stdlib.h>
 
typedef char ElemType;
 
typedef struct node
{
	ElemType data;
	struct node *prior,*next;
}SLink;
 
SLink *MaxNode(SLink *L);
 
void InitList(SLink *&L) /*SLink *&L作为引用型参数或者用二级指针SLink **L*/
{
	L=(SLink *)malloc(sizeof(SLink));
	L->prior=NULL;
	L->next=NULL;
}
 
int GetLength(SLink *L)
{
	int i=0;
	SLink *p=L->next;
	while(p != NULL)
	{
		i++;
		p=p->next;
	}
	return i;
}
 
int GetElem(SLink *L,int i,ElemType &e)
{
	int j=1;
	SLink *p=L->next;
	if(i<1 || i>GetLength(L))
		return 0;
	while(j<i)
	{
		p=p->next;
		j++;
	}
	e=p->data;
	return 1;
}
 
int Locate(SLink *L,ElemType x)
{
	int i=1;
	SLink *p=L->next;
	while(p!=NULL && p->data!=x)
	{
		p=p->next;
		i++;		
	}
	if(NULL == p)
		return 0;
	else
		return i;
}
 
int InsElem(SLink *L,ElemType x,int i)//初始化是尾插，也可中途插入
{
	int j=1;
	SLink *p=L,*s;
	s=(SLink *)malloc(sizeof(SLink));
	s->data=x;
	s->prior=NULL;
	s->next=NULL;
	if(i<1 || i>GetLength(L)+1)//防止i越界
		return 0;
 
	while(j<i)
	{
		p=p->next;
		j++;
	}
	s->next = p->next;
	s->prior = p;
	if(p->next != NULL)//若p不是最后结点，将p之后的结点的prior指向s
		s->next->prior=s;
	p->next = s;
	return 1;
}
 
int DelElem(SLink *L,int i)
{
	int j=1;
	SLink *p=L,*q;
	if(i<1 || i>GetLength(L))
		return 0;
	while(j<i)
	{
		p=p->next;
		j++;
	}
	q=p->next;
	printf("%c\n", q->data);
	p->next=q->next;
	if(q->next != NULL)//若q不是最后结点，将q之后的结点的prior指向p
		q->next->prior=p;
	free(q);
	return 1;
}
 
void DispList(SLink *L)
{
	SLink *p=L->next;
	while(p != NULL)
	{
		printf("%c ", p->data);
		p=p->next;
	}
	printf("\n");
}
 
int main()
{
	int i;
	ElemType e;
	SLink *L=NULL;
	InitList(L);//initial head
 
	InsElem(L,'a',1);
	InsElem(L,'b',2);
	InsElem(L,'c',3);
	InsElem(L,'d',4);
	InsElem(L,'e',5);
	InsElem(L,'f',6);
 
	printf("List:");
	DispList(L);
 
	printf("Length: %d\n", GetLength(L));
 
	i=3;
	GetElem(L,i,e);
	printf("index %d data is:%c\n", i,e);
 
	e='e';
	printf("data %c index is: %d\n", e,Locate(L,e));
 
	i=4;
	printf("delete index %d data ", i);
	DelElem(L,i);
 
	i=2;
	e='w';
	printf("insert index %d data %c\n", i, e);
	InsElem(L,e,2);
 
	printf("List:");
	DispList(L);
 
	printf("MaxNode:%c\n", MaxNode(L)->data);
}
 
/*通过一趟遍历返回单链表元素最大值的结点*/
SLink *MaxNode(SLink *L)
{
	SLink *p=L->next,*q=p;//p用来遍历，q用来记录最大的值结点
	while(p != NULL)
	{
		if(p->data > q->data)
			q=p;
		p=p->next;
	}
	return q;
}
 
/*ScanList算法*/