[一篇读懂]C语言十讲：单链表的新建、查找

• 1. 与408关联解析及本节内容介绍
• • 1 与408关联解析
  • 2 本节内容介绍
• 2. 头插法新建链表实战
• 3. 尾插法新建链表实战
• 4. 按位置查找及按值查找实战
• 5. 往第i个位置插入元素实战
• 6. 链表的调试方法
• 总结
• • 2
  • 3
  • 4
  • 5
  • 6

创新互联建站主要从事成都网站制作、成都网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务阳江,10年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:028-86922220

---

1. 与408关联解析及本节内容介绍 1 与408关联解析

【2019年单链表】
41.(13分)设线性表 L = ( a 1 , a 2 , a 3 , … , a n − 2 , a n − 1 , a n ) L=(a_1,a_2 ,a_3,…,a_{n-2},a_{n-1},a_n) L=(a1​,a2​,a3​,…,an−2​,an−1​,an​)采用带头结点的单链表保存，链表中的结点定义如下：

typedef struct node {int data;
	struct node* next;
}NODE;

请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表 L = ( a 1 , a n , a 3 , a n − 1 , a 3 , a n − 2 , … ) L=(a_1,a_n ,a_3,a_{n-1},a_3,a_{n-2},…) L=(a1​,an​,a3​,an−1​,a3​,an−2​,…)。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计的算法的时间复杂度。

2 本节内容介绍

本节分为五小节讲解。
第一小节是针对头插法新建链表进行实战
第二小节是针对尾插法新建链表进行实战
第三小节是链表按位置查找及按值查找实战
第四小节是往第i个位置插入元素实战
第五小节是链表的调试方法解析

---

2. 头插法新建链表实战

• 一切数据结构 - 增删查改

上一讲介绍了链表的新增、删除、查找的原理。

• 头插法新建链表流程图：
  

画流程图很关键。

使用头插法来新建链表：

#include#includetypedef int ElemType; //写分号

typedef struct LNode
{ElemType data; //数据域
	struct LNode* next;
}LNode,*LinkList;

//输入3，4，5，6，7，9999
void list_head_insert(LNode*& L)//LNode*是结构体指针 等价于 LinkList(常用)
{//申请头结点空间，头指针指向头结点
	L = (LinkList)malloc(sizeof(LNode));//不能写LinkList和LNode* - 结构体指针 - 大小8个字节
	L->next = NULL;//头结点的next为NULL - 第一次读取时s->next = L->next =NULL
	//第一个结点
	ElemType x;//第一个结点的数据
	scanf("%d", &x);
	LNode *s;//指针s指向第一个结点
	//s = (LinkList)malloc(sizeof(LNode));
	//s->data = x;//x存放到数据域中
	//s->next = NULL;//第一个结点最后会成为最后一个结点 - next指针应该为NULL
	//L->next = s;//头结点的next，就指向了第一个结点

	while (x != 9999)//输入9999代表输入结束 - 不想把9999存入链表
	{//scanf("%d", &x);
		s = (LinkList)malloc(sizeof(LNode));
		s->data = x;
		//头插法，把插入的元素插到第一个位置
		s->next = L->next;//s的next指向原本链表的第一个结点
		L->next = s;//头结点的next指向新结点
		scanf("%d", &x);//读取放在最后，读到结束的9999时就不会存入链表
	}

}

void print_list(LinkList L)
{L = L->next;
	while (L != NULL)
	{printf("%3d", L->data);
		L = L->next;
	}
	printf("\n");
}

//头插法新建链表
int main()
{LinkList L; //L是链表头指针，是结构体指针类型 - 大小8个字节

	list_head_insert(L); //输入数据可以为3 4 5 6 7 9999，头插法新建链表
	print_list(L); //链表打印
	return 0;
}

---

3. 尾插法新建链表实战

• 尾插法新建链表流程图：
  
  使用尾插法来新建链表：

#include#includetypedef int ElemType; //写分号

typedef struct LNode
{ElemType data; //数据域
	struct LNode* next;
}LNode, * LinkList;

void list_tail_insert(LNode*& L)
{L = (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点
	L->next = NULL;//头结点的next为NULL
	ElemType x;
	scanf("%d", &x);
	LNode* s, * r = L;//s用来指向申请的新节点，r始终指向列表尾部
	while (x != 9999)
	{s = (LinkList)malloc(sizeof(LNode));//为新节点申请空间
		s->data = x;
		r->next = s;//新节点给尾节点的next指针
		r = s;//r要指向新的尾部
		scanf("%d", &x);
	}
	r->next = NULL;//让尾节点的next为NULL
}

void print_list(LinkList L)
{L = L->next;
	while (L != NULL)
	{printf("%3d", L->data);
		L = L->next;
	}
	printf("\n");
}

//尾插法新建链表
int main()
{LinkList L; //L是链表头指针，是结构体指针类型 - 大小8个字节
	list_tail_insert(L);
	print_list(L); //链表打印
	return 0;
}

---

4. 按位置查找及按值查找实战

• 按位置查找流程图：
• 查找位置时需要判断位置是否合法。

#include#includetypedef int ElemType; //写分号

typedef struct LNode
{ElemType data; //数据域
	struct LNode* next;
}LNode, * LinkList;


void list_tail_insert(LNode*& L)
{L = (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点
	L->next = NULL;//头结点的next为NULL
	ElemType x;
	scanf("%d", &x);
	LNode* s, * r = L;//s用来指向申请的新节点，r始终指向列表尾部
	while (x != 9999)
	{s = (LinkList)malloc(sizeof(LNode));//为新节点申请空间
		s->data = x;
		r->next = s;//新节点给尾节点的next指针
		r = s;//r要指向新的尾部
		scanf("%d", &x);
	}
	r->next = NULL;//让尾节点的next为NULL
}

void print_list(LinkList L)
{L = L->next;
	while (L != NULL)
	{printf("%3d", L->data);
		L = L->next;
	}
	printf("\n");
}

//按位置查找
LinkList GetElem(LinkList L, int SearchPos)
{int j = 0;
	while (L && j< SearchPos)//L!=NULL，地址不为NULL
	{L = L->next;
		j++;
	}
	return L;
}

//按值查找
LinkList LocateElem(LinkList L, ElemType SearchVal)
{while (L)
	{if (L->data == SearchVal)//如果找到对应的值，返回那个节点的地址
		{	return L;
		}
		L = L->next;
	}
	return NULL;
}

//尾插法新建链表
int main()
{LinkList L; //L是链表头指针，是结构体指针类型 - 大小8个字节

	list_tail_insert(L);
	print_list(L); //链表打印

	LinkList search;//用来存储拿到的某一个节点
	//按位置查找
	search = GetElem(L, 2);
	if (search != NULL)
	{printf("Secceeded in searching by serial number\n");
		printf("%d\n", search->data);
	}

	//按值查找
	search = LocateElem(L, 6);
	if (search != NULL)
	{printf("Secceeded in searching by serial number\n");
		printf("%d\n", search->data);

	}
	return 0;
}

---

5. 往第i个位置插入元素实战

• 往第i个位置插入元素流程图：
  
• 如果要从函数调用位置，跳转到函数定义位置，ctrl+鼠标左键点击。

#include#includetypedef int ElemType; //写分号

typedef struct LNode
{ElemType data; //数据域
	struct LNode* next;
}LNode, * LinkList;


void list_tail_insert(LNode*& L)
{L = (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点
	L->next = NULL;//头结点的next为NULL
	ElemType x;
	scanf("%d", &x);
	LNode* s, * r = L;//s用来指向申请的新节点，r始终指向列表尾部
	while (x != 9999)
	{s = (LinkList)malloc(sizeof(LNode));//为新节点申请空间
		s->data = x;
		r->next = s;//新节点给尾节点的next指针
		r = s;//r要指向新的尾部
		scanf("%d", &x);
	}
	r->next = NULL;//让尾节点的next为NULL
}

void print_list(LinkList L)
{L = L->next;
	while (L != NULL)
	{printf("%3d", L->data);
		L = L->next;
	}
	printf("\n");
}

//按位置查找
LinkList GetElem(LinkList L, int SearchPos)
{int j = 0;
	if (SearchPos< 0)
	{return NULL;
	}
	while (L && j< SearchPos)//L!=NULL，地址不为NULL
	{L = L->next;
		j++;
	}
	return L;
}

//按值查找
LinkList LocateElem(LinkList L, ElemType SearchVal)
{while (L)
	{if (L->data == SearchVal)//如果找到对应的值，返回那个节点的地址
		{	return L;
		}
		L = L->next;
	}
	return NULL;
}

//i代表插入到第几个位置
bool ListFrontInsert(LinkList L, int i, ElemType InsertVal)
{LinkList p = GetElem(L, i - 1);
	if (NULL == p)
	{return false;
	}
	LinkList q;
	q = (LinkList)malloc(sizeof(LNode));//为新节点申请空间
	q->data = InsertVal;
	q->next = p->next;
	p->next = q;
	return true;
}

//尾插法新建链表
int main()
{LinkList L; //L是链表头指针，是结构体指针类型 - 大小8个字节

	list_tail_insert(L);
	print_list(L); //链表打印

	LinkList search;//用来存储拿到的某一个节点
	bool ret;
	ret = ListFrontInsert(L, 2, 99);//新节点插入第i个位置
	print_list(L); 
	return 0;
}

---

6. 链表的调试方法

• 链表中每一个结点在内存中是不连续的，通过单步调试，在变量窗口，依次点开头指针L，观察每一个结点是否符合自己的预期。
  

---

总结 2

• 头插法新建链表流程图：
  

3

• 尾插法新建链表流程图：
  

4

• 按位置查找流程图：

5

• 往第i个位置插入元素流程图：
  

6

• 链表中每一个结点在内存中是不连续的，通过单步调试，在变量窗口，依次点开头指针L，观察每一个结点是否符合自己的预期。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网页名称：[一篇读懂]C语言十讲：单链表的新建、查找-创新互联
标题来源：http://myzitong.com/article/pcoci.html