[一篇读懂]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语言十讲:单链表的新建、查找-创新互联
当前路径:http://scyanting.com/article/pcoci.html