本文共 1946 字，大约阅读时间需要 6 分钟。

一、单链表的查找（带头结点）

（一）按位查找

• 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
   
     next;		j++;	}	return p;}
   

• 边界情况：
  ①如果 i = 0
  
• ②如果 i = 8
  

（二）按值查找

• 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：
  
• ②、如果e=6：
  

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 
   
    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;	//插入成功}
   

• 通过设置尾指针减少时间复杂度
  

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;}

（二）头插法

• 重要应用：链表的逆置

LinkList List_HeadInsert(LinkList &L){   //逆向建立单链表	LNode *s;	int x;	L = (LinkList)malloc(sizeof(LNode));//创建头结点	L -> next = NULL;		//初始为空链表👈（必须）	scanf("%d",&x);			//输入结点的值	while(x != 9999){   		//输入9999表示结束		s = (LNode *)malloc(sizeof(LNode));//创建新结点		s -> data = x;		s -> next = L -> next;		L -> next = s;		//将新结点插入表中，L为头指针		scanf("%d",&x);	}	return L;	}