[数据结构与算法]链表的 取值 查找 插入 删除

目录

一.单链表的取值

?二.单链表的查找

一.单链表的取值

取第i个位置上的元素，用e返回

1. 从第一个结点（L->next）开始顺链扫描，用指针p指向当前结点，p的初值：p=L->next
2. j作计数器，累计扫过的结点数，j的初始值为1
3. p指向下一结点时，j+1? p=p->next; j++;
4. 当j == i时，取值成功

   Status GetElem_L(LinkList L, int i, ElemType &e){
   	p = p->next; j = 1;
   	
   	while(p && j<i){           //向后扫描，直到p指向i，或第i个元素不存在 
   		p = p->next;
   		j++;
   	}
   	
   	if(!p || j>i) return ERROR; //非法，第i个元素不存在 
   	
   	return OK; 
   } 

?二.单链表的查找

查找链表中值为e的元素，并用j返回其 位置 或 地址

p = L->next;

p = p->next;

p->data !=e;

?跳出条件：p == NULL；循环条件：p ！= NULL;?

1. 从第一个结点开始，依次和e比较
2. 若找到与e相同大小的元素，返回其在链表中的位置或地址
3. 若未找到，返回0或NULL

返回地址?

Lnode *LocateElem_L(LinkList L, ElemType e){
	p = L->next;
	
	while(p && p->date != e){
		p = p->next;
	}
	return p;
}

返回位置

int LocateElem_L(LinkList L, Elemtype e){
	p = L->next; 
	j = 1;
	
	while( p && p->data != e){
		p =p->next;
		j++;
	}
	if(p != NULL) return j;
	else return 0; 
}

时间效率：只能从顺序存取，从头遍历

T(n)=O(n)