单链表上的基本操作

1.头插法建立单链表

  • T(n) = O(n)
  • 如果没有设立头结点，则每次插入新节点后，将结点的地址赋值给L。
  • 生成单链表中数据元素的顺序与插入顺序相反。
LinkList list_HeadInsert(LinkList &L, int n)
{
	LNode *p; int x;
	L = (LinkList)malloc(sizeof(LNode));	//创建头结点
	L -> next = NULL;	
	for (int i = 0; i < n; i ++)
	{
		p = (LNode *)malloc(sizeof(LNode));	//生成新节点
		scanf("%d", &x);
		p -> data = x;
		p -> next = L -> next;
		L -> next = p;
	}
	return L;
}

2.尾插法建立单链表

  • T(n) = O(n)
  • 增加一个 尾指针r。
LinkList list_TailInsert(LinkList &L, int n)
{
	LNode *p, *r; int x;
	L = (LinkList)malloc(sizeof(LNode));
	L -> next = NULL;
	r = L;
	for (int i =  0; i < n; i ++ )
	{
		p = (LNode *)malloc(sizeof(LNode));
		scanf("%d", &x);
		p -> data = x;
		r -> next = p;
		r = p;
	}
	r -> next = NULL;	//尾结点指针置空
	return L;
}

3.按序号查找结点值

  • 查找第i个结点的值,如果找到，将其保存到e中。
  • T(n) = O(n)
bool GetElem(LinkList L, int i, ElemType &e);
{
	int j = 1;
	LNode *p = L -> next;	//p指向首元结点
	while(p && j < i)
	{
		p = p -> next;
		j ++;
	}
	if (!p || j > i)	//p为空即i > n 或 i <= 0
		return false;
	e = p -> data;
	return true;
}

4.按值查找结点

  • T(n) = O(n)
LNode *LocateElem(LinkList L, ElemType e)
{
	LNode *p = L -> next;	//p指向首元结点
	while (p && p -> data != e)
	{
	    p = p -> next;
	}
	return p;	//查找成功返回结点e的地址p，查找失败返回NULL
}

5.插入

bool LisTInsert(LinKList &L, int i, int e)
{
	LNode *p = L, *s; int j = 0;
	while (p && j < i - 1)
	{
	    p = p -> next;
	    j ++;
	}
	if (!p || j > i - 1)	//p为空即 i > n + 1 或 i < 1;
	s = (LNode *)malloc(sizeof(LNode));
	s -> data = e;
	s -> next = p -> next;
	p -> next = s;
    return true;
}

6.删除

  • 图示
    单链表上的基本操作 算法 第2张
bool ListDelete(LinKList &L, int i)
{	
	LNode *p, *q; int j= 0;
	while(!(p -> next) && (j < i - 1))	//p -> next：p的后继结点可能不存在
	{	
		p = p -> next;
		j ++;
	}
	q = p -> next;	//临时存储被删除结点的地址
	p -> next = q -> next;
	free(q);	//释放删除结点的空间
	return true;
}

7.求表长

int ListLenth(LinkList L)
{	
	LNode *p = L;
	int length = 0;
	while (!p)
	{
		p = p -> next;
		length ++;
	}
	return length;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄