文章

6

粉丝

0

获赞

0

访问

2891

头像
单链表(2)
数据结构
发布于2021年4月5日 22:04
阅读数 555

单链表的操作

1.按序号查找

在单链表中取出第 i 个节点,并返回结点的指针。
LNode *GetElem(LinkList L,int i){
	int j = 1;
	LNode *p = L -> next;
	if(i == 0) return L;
	if(i < 0)  return NULL;

	while(p && j < i){
		p = p -> next;
		j++;
	}
	return p;
}
  • if判断语句用来判读 i 是否在正确的使用范围内,( i 不可以小于 0 )。
  • while 循环用来从链表的头部开始遍历,找到第 i 个结点,返回其指针。
  • 此操作时间复杂度 O(n)
p = p -> next 大致是这个样子的,如下图所示:

 

 

2.按值查找

查找某个值所在的结点,返回此结点的指针。
LNode *LocateElem(LinkList L,ElemType e){
	LNode *p = L -> next;
	while(p != NULL && p -> data != e )
		p = p->next;
	return p;
}
  • while循环中的 p != NULL 是用来判断链表是否遍历到最后。

 

  • 此操作时间复杂度 O(n)。

3.插入

将一个新的结点插入到第 i 个位置。

 

 

p = GetElem(L,i-1);
s -> next = p -> next;
p -> next = s;
  • 获取第 i-1 个结点的指针,将新的结点 S 插入到第 i-1 个结点之后(第 i 个位置)。
  • 因为查找第 i-1 个结点的位置时间复杂度为 O(n) 插入操作只需 O(1),所以总体的时间复杂度为 O(n)。

########## 此操作称之为后插操作,与之对应的还有前插操作:

将一个结点插入到某个结点之前。(通常是使用后插的)

前插的代码实现:

p = GetElem(L,i-1);
s -> next = p -> next;
p -> next = s;
temp = p -> data;
p -> data = s ->data;
s -> data = temp;
  • 实际上插入结点的时候是后插操作,但是插入之后,交换新插入节点和其前驱结点的数据域,从而实现前插操作。
  • 此操作时间复杂度 O(n)。


 

4.删除

删除单链表中第 i 个结点

 

 

 

p = GetElem(L,i-1);
q = p -> next;
p -> next = q -> next; //还可以写为 p -> next = p -> next -> next;  
free(q);
  • 要删除某一个结点 ,需要找到其前驱结点,(因为需要修改其前驱结点的指针域)。
  • 如图,将某结点 a2 的前驱结点 a1 的指针域修改为 a2 的后继节点的指针(a3)的地址。
  • 此操作时间复杂度 O(n)。


登录后发布评论

暂无评论,来抢沙发