单链表的查找、建立操作(C语言)

一、单链表的查找(带头结点)

(一)按位查找

  • GetElem(L,i)按位查找操作。获取表L中第i个位置的元素的值。
//按位查找,返回第i个元素(带头结点)
LNode * GetElem(LinkList L, int i){
	if(i<0)
		return NULL;
	LNode *p;		//指针p指向当前扫描到的结点
	int j=0;		//当前p指向的是第几个结点
	p = L;			//L指向头结点,头结点是第0个结点(不存储数据)
	while(p != NULL && j<i){//循环找到第i个结点
		p =p -> next;
		j++;
	}
	return p;
}
  • 边界情况:
    ①如果 i = 0
    单链表的查找、建立操作(C语言)
  • ②如果 i = 8
    单链表的查找、建立操作(C语言)

(二)按值查找

  • LocateElem(L,e)按值查找操作。在表L中查找具有给定关键字值的元素。
//按值查找,找到数据域==e 的结点
LNode * LocateElem(LinkList L,ElemType e){
	LNode *p = L -> next;
	//从第1个结点开始查找数据域为e的结点
	while(p != NULL && p -> data != e)
		p = p -> next;
	return p;//找到后返回该结点指针,否则返回NULL
}
  • ①、如果e=8:
    单链表的查找、建立操作(C语言)
  • ②、如果e=6:
    单链表的查找、建立操作(C语言)

1. 求表的长度

//求表的长度
int Length(LinkList L){
	int len = 0;//统计表长
	LNode *p = L;
	while(p -> next != NULL){
		p = p -> next;
		len++;
	}
	return len;
}

二、单链表的建立

(一)尾插法

  • 尾插法建立单链表:
    ①、初始化单链表。
    ②、设置变量length记录链表长度
while循环{
	每次取一个数据元素e;
	ListInsert(L,length+1,e)插到尾部;
	length++;
}
  • 尾插法建立单链表
//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
	if(i<1)
		return false;
	LNode *p;		//指针p指向当前扫描到的结点
	int j=0;		//当前p指向的是第几个结点
	p = L;			//L指向头结点,头结点是第0个结点(不存储数据)
	while(p != NULL && j <i-1){//循环找到第i-1个结点
		p = p->next;
		j++;
	}
	if(p == NULL)	//i值不合法
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s -> data = e;
	s -> next = p -> next;
	p -> next = s;	//将结点s连接到p之后
	return true;	//插入成功
}

单链表的查找、建立操作(C语言)

  • 通过设置尾指针减少时间复杂度
    单链表的查找、建立操作(C语言)
LinkList List_TailInsert(LinkList &L){//正向建立单链表
	int x;		//设ElemType为整型
	L = (LinkList)malloc(sizeof(LNode));//建立头结点
	LNode *s,*r = L;		//r为表尾指针
	scanf("%d",&x);			//输入结点的值
	while(x != 9999){
		s = (LNode *)malloc(sizeof(LNode));
		s -> data = x;
		r -> next = s;
		scanf("%d",&x);
	}
	r -> next = NULL;		//尾结点指针置空
	return L;
}

单链表的查找、建立操作(C语言)
单链表的查找、建立操作(C语言)

(二)头插法

  • 重要应用:链表的逆置
LinkList List_HeadInsert(LinkList &L){//逆向建立单链表
	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));//创建头结点
	L -> next = NULL;		//初始为空链表
上一篇:1、求一个链表当中的最大值和最小值


下一篇:查找单链表倒数第k个位置上的结点(高效算法)