单链表(线性表的链式存储)的基本运算

  • 内容
  • 相关

链式存储是最常用的动态存储方法。通常将采用链式存储结构的线性表称为线性链表。从链接方式的角度链表可分为单链表、循环链表和双链表。从实现角度看,可分为动态链表和静态链表。单链表的节点结构包括一个数据域和一个指针域。基本算法如下:

/*单链表的存储结构*/
typedef struct Node  /*结点类型定义*/
{
	ElemType data;
	struct Node*  next;
}Node,*LinkList;  /*LinkList为结构指针类型*/
/*初始化单链表*/
InitList(LinkList *L)
{
	*L=(LinkList)malloc(sizeof(Node));  /*建立头结点*/
	(*L)->next=NULL;  /*建立空的单链表L*/
}
/*用头插法创建单链表*/
void CreateFromHead(LinkList L)
{ /*L是带头结点的空链表头指针,通过键盘输入表中元素值,利用头插法建立单链表L*/
	Node *s;
	char c;
	int flag=1;
	while(flag) /*flag初值为1,当输入'$'时,置flag为0,建表结束*/
	{
		c=getchar();
		if(C!='$')
		{
			s=(Node *)malloc(sizeof(Node));  /*创建新结点*/
			s->data=c;
			s->next=L->next; /*将s结点插入表头*/
			L->next=s;
		}
		else
			flag=0;
	}
}
/*利用尾插法建立单链表L*/
void CreataFromTail(LinkList L)
{ /*L是带头结点的空链表头指针,通过键盘输入表中元素值,利用尾插法建立单链表L*/
	Node *s,*r;
	int flag=1; /*设置一个标志,初值为1,当输入'$'时,置flag为0,建表结束*/
	r=L; /*r指针动态指向链表的当前表尾,以便做尾插入,其初值指向头结点*/
	while(flag)  /*循环输入表中元素值,将建立新结点s插入表尾*/
	{
		c=getchar();
		if(C!='$')
		{
			s=(Node *)malloc(sizeof(Node));
			s->data=c;
			r->next=s;
			r=s;
		}
		else
		{
			flag=0;
			r->next=NULL; /*将最后一个节点的next指针域置空,表示链表的结束*/
		}
	}
}
/*******************查找******************/
/*(按序号查找)在单链表中查找第i个结点*/
Node *Get(LinkList L,int i)
{ /*在带头结点的单链表L中查找第i个结点,若找到(1<=i<=n),则返回该结点的存储位置,否则返回NULL*/
	int j;
	Node *p;
	if(i<=0)
		return NULL;
	p=L;j=0;  /*从头结点扫描*/
	while((p->next!=NULL)&&(j<i))
	{
		p=p->next;  /*扫描下一个结点*/
		j++;  /*已扫描结点计数器*/
	}
	if(i==j)
		return p;  /*找到第i个结点*/
	else
		return NULL;  /*找不到,i<=0或i>n*/
}
/*(按值查找)在单链表L中查找值为key的结点*/
Node *Locate(LinkList L,ElemType key)
{ /*在带头结点的单链表L中查找其结点值为key的第一个结点,若找到则返回该结点的位置p,否则返回NULL*/
	Node *p;
	p=L->next; /*从表中第一个结点开始*/
	while(p!=NULL)  /*当前表未查完*/
		if(p->data!=key)
			p=p->next;
		else
			break;  /*找到结点值=key时退出循环*/
		return p;
}
/*求单链表的长度*/
int ListLength(LinkList L)
{  /*求带头结点的单链表L的长度*/
	Node *p;
	p=L->next;
	j=0;   /*用来存放单链表的长度*/
	while(p!=NULL)
	{
		p=p->next;
		j++;
	}
	return j;  /*j为求得的单链表长度*/
}
/*单链表的插入操作*/
void InsList(LinkList L,int i,ElemType e)
{  /*在带头结点的单链表L中第i个位置插入值为e的新结点*/
	Node *pre,*s;
	int k;
	if(i<=0)
		return ERROR;
	pre=L;	k=0;  /*从"头"开始,查找第i-1个结点*/
	while(pre!=NULL&&k<i-1) /*表未查完且未查到第i-1个时重复,找到pre指向第i-1个*/
	{
		pre=pre->next;
		k=k+1;
	}  /*查找第i-1个结点*/
	if(pre==NULL) /*如当前位置pre为空则表示已找完,但还未数到第i个,说明插入位置不合理*/
	{
		printf("插入位置不合理!");
		return ERROR;
	}
	s=(Node *)malloc(sizeof(Node)); /*申请一个新结点*/
	s->data=e;  /*值e置入s的数据域*/
	s->next=pre->next;  /*修改指针,完成插入操作*/
	pre->next=s;
	return OK;
}
/*单链表删除操作*/
void DelList(LinkList L,int i,ElemType e)
{  /*在带头结点的单链表L中删除第i个元素,并将删除的元素保存到变量*e中*/
	Node *pre,*r;
	int k;
	pre=L;	k=0;
	while(pre->next!=NULL&&k<i-1) /*寻找被删除结点i的前驱结点i-1使p指向他*/
	{
		pre=pre->next;
		k=k+1;
	}  /*查找第i-1个结点*/
	if(pre->next==NULL) /*while循环是因为p->next==NULL或i<1而跳出的,因为pre->next为空,没有
						找到合法的前驱位置,说明删除位置i不合法*/
	{
		printf("删除位置不合法");
		return ERROR;
	}
	r=pre->next;
	pre->next=r->next;  /*修改指针,删除结点r*/
	*e=r->data;
	free(r);  /*释放被删除的结点所占的内存空间*/
	return OK;
}

本文标签:

版权声明:若无特殊注明,本文皆为《尤尤》原创,转载请保留文章出处。

本文链接:单链表(线性表的链式存储)的基本运算 - https://www.yxfseo.cn/post-60.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注