资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

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

[一篇读懂]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. 头插法新建链表实战
  • 一切数据结构 - 增删查改

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

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

画流程图很关键。

使用头插法来新建链表：

#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. 尾插法新建链表实战
  • 尾插法新建链表流程图：
    1
    使用尾插法来新建链表：
#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. 按位置查找及按值查找实战
  • 按位置查找流程图：1
  • 查找位置时需要判断位置是否合法。
#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个位置插入元素流程图：
    1
  • 如果要从函数调用位置，跳转到函数定义位置，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，观察每一个结点是否符合自己的预期。
    1
总结 2
  • 头插法新建链表流程图：
    1
3
  • 尾插法新建链表流程图：
    1
4
  • 按位置查找流程图：1
5
  • 往第i个位置插入元素流程图：
    1
6
  • 链表中每一个结点在内存中是不连续的，通过单步调试，在变量窗口，依次点开头指针L，观察每一个结点是否符合自己的预期。

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


分享名称：[一篇读懂]C语言十讲：单链表的新建、查找-创新互联
URL链接：http://cdkjz.cn/article/pcoci.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
友益建筑机械凿主机租用混凝土搅拌罐车成都网站推广网站运营外贸营销网站建设响应式网站建设簇桥薇薇新娘成都网站推广乐山装修公司

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图