[一篇讀懂]C語(yǔ)言十講：?jiǎn)捂湵淼男陆?、查?創(chuàng)新互聯(lián)

[一篇讀懂]C語(yǔ)言十講：?jiǎn)捂湵淼男陆?、查?ul>

1. 與408關(guān)聯(lián)解析及本節(jié)內(nèi)容介紹

1 與408關(guān)聯(lián)解析
2 本節(jié)內(nèi)容介紹

2. 頭插法新建鏈表實(shí)戰(zhàn)

3. 尾插法新建鏈表實(shí)戰(zhàn)

4. 按位置查找及按值查找實(shí)戰(zhàn)

5. 往第i個(gè)位置插入元素實(shí)戰(zhàn)

6. 鏈表的調(diào)試方法

總結(jié)

創(chuàng)新互聯(lián)建站主要從事成都網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)陽(yáng)江,10年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):028-86922220

1. 與408關(guān)聯(lián)解析及本節(jié)內(nèi)容介紹 1 與408關(guān)聯(lián)解析

【2019年單鏈表】
41.(13分)設(shè)線性表 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?)采用帶頭結(jié)點(diǎn)的單鏈表保存，鏈表中的結(jié)點(diǎn)定義如下：

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

請(qǐng)?jiān)O(shè)計(jì)一個(gè)空間復(fù)雜度為O(1)且時(shí)間上盡可能高效的算法，重新排列L中的各結(jié)點(diǎn)，得到線性表 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）給出算法的基本設(shè)計(jì)思想。
（2）根據(jù)設(shè)計(jì)思想，采用C或C++語(yǔ)言描述算法，關(guān)鍵之處給出注釋。
（3）說明你所設(shè)計(jì)的算法的時(shí)間復(fù)雜度。

2 本節(jié)內(nèi)容介紹

本節(jié)分為五小節(jié)講解。
第一小節(jié)是針對(duì)頭插法新建鏈表進(jìn)行實(shí)戰(zhàn)
第二小節(jié)是針對(duì)尾插法新建鏈表進(jìn)行實(shí)戰(zhàn)
第三小節(jié)是鏈表按位置查找及按值查找實(shí)戰(zhàn)
第四小節(jié)是往第i個(gè)位置插入元素實(shí)戰(zhàn)
第五小節(jié)是鏈表的調(diào)試方法解析

2. 頭插法新建鏈表實(shí)戰(zhàn)

一切數(shù)據(jù)結(jié)構(gòu) - 增刪查改

上一講介紹了鏈表的新增、刪除、查找的原理。

頭插法新建鏈表流程圖：

畫流程圖很關(guān)鍵。

使用頭插法來新建鏈表：

#include#includetypedef int ElemType; //寫分號(hào)

typedef struct LNode
{ElemType data; //數(shù)據(jù)域
	struct LNode* next;
}LNode,*LinkList;

//輸入3，4，5，6，7，9999
void list_head_insert(LNode*& L)//LNode*是結(jié)構(gòu)體指針 等價(jià)于 LinkList(常用)
{//申請(qǐng)頭結(jié)點(diǎn)空間，頭指針指向頭結(jié)點(diǎn)
	L = (LinkList)malloc(sizeof(LNode));//不能寫LinkList和LNode* - 結(jié)構(gòu)體指針 - 大小8個(gè)字節(jié)
	L->next = NULL;//頭結(jié)點(diǎn)的next為NULL - 第一次讀取時(shí)s->next = L->next =NULL
	//第一個(gè)結(jié)點(diǎn)
	ElemType x;//第一個(gè)結(jié)點(diǎn)的數(shù)據(jù)
	scanf("%d", &x);
	LNode *s;//指針s指向第一個(gè)結(jié)點(diǎn)
	//s = (LinkList)malloc(sizeof(LNode));
	//s->data = x;//x存放到數(shù)據(jù)域中
	//s->next = NULL;//第一個(gè)結(jié)點(diǎn)最后會(huì)成為最后一個(gè)結(jié)點(diǎn) - next指針應(yīng)該為NULL
	//L->next = s;//頭結(jié)點(diǎn)的next，就指向了第一個(gè)結(jié)點(diǎn)

	while (x != 9999)//輸入9999代表輸入結(jié)束 - 不想把9999存入鏈表
	{//scanf("%d", &x);
		s = (LinkList)malloc(sizeof(LNode));
		s->data = x;
		//頭插法，把插入的元素插到第一個(gè)位置
		s->next = L->next;//s的next指向原本鏈表的第一個(gè)結(jié)點(diǎn)
		L->next = s;//頭結(jié)點(diǎn)的next指向新結(jié)點(diǎn)
		scanf("%d", &x);//讀取放在最后，讀到結(jié)束的9999時(shí)就不會(huì)存入鏈表
	}

}

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是鏈表頭指針，是結(jié)構(gòu)體指針類型 - 大小8個(gè)字節(jié)

	list_head_insert(L); //輸入數(shù)據(jù)可以為3 4 5 6 7 9999，頭插法新建鏈表
	print_list(L); //鏈表打印
	return 0;
}

3. 尾插法新建鏈表實(shí)戰(zhàn)

尾插法新建鏈表流程圖：

使用尾插法來新建鏈表：

#include#includetypedef int ElemType; //寫分號(hào)

typedef struct LNode
{ElemType data; //數(shù)據(jù)域
	struct LNode* next;
}LNode, * LinkList;

void list_tail_insert(LNode*& L)
{L = (LinkList)malloc(sizeof(LNode));//申請(qǐng)頭結(jié)點(diǎn)空間，頭指針指向頭結(jié)點(diǎn)
	L->next = NULL;//頭結(jié)點(diǎn)的next為NULL
	ElemType x;
	scanf("%d", &x);
	LNode* s, * r = L;//s用來指向申請(qǐng)的新節(jié)點(diǎn)，r始終指向列表尾部
	while (x != 9999)
	{s = (LinkList)malloc(sizeof(LNode));//為新節(jié)點(diǎn)申請(qǐng)空間
		s->data = x;
		r->next = s;//新節(jié)點(diǎn)給尾節(jié)點(diǎn)的next指針
		r = s;//r要指向新的尾部
		scanf("%d", &x);
	}
	r->next = NULL;//讓尾節(jié)點(diǎn)的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是鏈表頭指針，是結(jié)構(gòu)體指針類型 - 大小8個(gè)字節(jié)
	list_tail_insert(L);
	print_list(L); //鏈表打印
	return 0;
}

4. 按位置查找及按值查找實(shí)戰(zhàn)

按位置查找流程圖：
查找位置時(shí)需要判斷位置是否合法。

#include#includetypedef int ElemType; //寫分號(hào)

typedef struct LNode
{ElemType data; //數(shù)據(jù)域
	struct LNode* next;
}LNode, * LinkList;


void list_tail_insert(LNode*& L)
{L = (LinkList)malloc(sizeof(LNode));//申請(qǐng)頭結(jié)點(diǎn)空間，頭指針指向頭結(jié)點(diǎn)
	L->next = NULL;//頭結(jié)點(diǎn)的next為NULL
	ElemType x;
	scanf("%d", &x);
	LNode* s, * r = L;//s用來指向申請(qǐng)的新節(jié)點(diǎn)，r始終指向列表尾部
	while (x != 9999)
	{s = (LinkList)malloc(sizeof(LNode));//為新節(jié)點(diǎn)申請(qǐng)空間
		s->data = x;
		r->next = s;//新節(jié)點(diǎn)給尾節(jié)點(diǎn)的next指針
		r = s;//r要指向新的尾部
		scanf("%d", &x);
	}
	r->next = NULL;//讓尾節(jié)點(diǎn)的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)//如果找到對(duì)應(yīng)的值，返回那個(gè)節(jié)點(diǎn)的地址
		{	return L;
		}
		L = L->next;
	}
	return NULL;
}

//尾插法新建鏈表
int main()
{LinkList L; //L是鏈表頭指針，是結(jié)構(gòu)體指針類型 - 大小8個(gè)字節(jié)

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

	LinkList search;//用來存儲(chǔ)拿到的某一個(gè)節(jié)點(diǎn)
	//按位置查找
	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個(gè)位置插入元素實(shí)戰(zhàn)

往第i個(gè)位置插入元素流程圖：
如果要從函數(shù)調(diào)用位置，跳轉(zhuǎn)到函數(shù)定義位置，ctrl+鼠標(biāo)左鍵點(diǎn)擊。

#include#includetypedef int ElemType; //寫分號(hào)

typedef struct LNode
{ElemType data; //數(shù)據(jù)域
	struct LNode* next;
}LNode, * LinkList;


void list_tail_insert(LNode*& L)
{L = (LinkList)malloc(sizeof(LNode));//申請(qǐng)頭結(jié)點(diǎn)空間，頭指針指向頭結(jié)點(diǎn)
	L->next = NULL;//頭結(jié)點(diǎn)的next為NULL
	ElemType x;
	scanf("%d", &x);
	LNode* s, * r = L;//s用來指向申請(qǐng)的新節(jié)點(diǎn)，r始終指向列表尾部
	while (x != 9999)
	{s = (LinkList)malloc(sizeof(LNode));//為新節(jié)點(diǎn)申請(qǐng)空間
		s->data = x;
		r->next = s;//新節(jié)點(diǎn)給尾節(jié)點(diǎn)的next指針
		r = s;//r要指向新的尾部
		scanf("%d", &x);
	}
	r->next = NULL;//讓尾節(jié)點(diǎn)的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)//如果找到對(duì)應(yīng)的值，返回那個(gè)節(jié)點(diǎn)的地址
		{	return L;
		}
		L = L->next;
	}
	return NULL;
}

//i代表插入到第幾個(gè)位置
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));//為新節(jié)點(diǎn)申請(qǐng)空間
	q->data = InsertVal;
	q->next = p->next;
	p->next = q;
	return true;
}

//尾插法新建鏈表
int main()
{LinkList L; //L是鏈表頭指針，是結(jié)構(gòu)體指針類型 - 大小8個(gè)字節(jié)

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

	LinkList search;//用來存儲(chǔ)拿到的某一個(gè)節(jié)點(diǎn)
	bool ret;
	ret = ListFrontInsert(L, 2, 99);//新節(jié)點(diǎn)插入第i個(gè)位置
	print_list(L); 
	return 0;
}

6. 鏈表的調(diào)試方法

鏈表中每一個(gè)結(jié)點(diǎn)在內(nèi)存中是不連續(xù)的，通過單步調(diào)試，在變量窗口，依次點(diǎn)開頭指針L，觀察每一個(gè)結(jié)點(diǎn)是否符合自己的預(yù)期。

總結(jié) 2

頭插法新建鏈表流程圖：

尾插法新建鏈表流程圖：

按位置查找流程圖：

往第i個(gè)位置插入元素流程圖：

鏈表中每一個(gè)結(jié)點(diǎn)在內(nèi)存中是不連續(xù)的，通過單步調(diào)試，在變量窗口，依次點(diǎn)開頭指針L，觀察每一個(gè)結(jié)點(diǎn)是否符合自己的預(yù)期。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

名稱欄目：[一篇讀懂]C語(yǔ)言十講：?jiǎn)捂湵淼男陆ā⒉檎?創(chuàng)新互聯(lián)
當(dāng)前地址：http://weahome.cn/article/pcoci.html

真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

[一篇讀懂]C語(yǔ)言十講：?jiǎn)捂湵淼男陆?、查?創(chuàng)新互聯(lián)

其他資訊

網(wǎng)站制作

企業(yè)服務(wù)

網(wǎng)站建設(shè)

服務(wù)器托管

真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

[一篇讀懂]C語(yǔ)言十講：?jiǎn)捂湵淼男陆?、查?創(chuàng)新互聯(lián)

其他資訊

網(wǎng)站制作

企業(yè)服務(wù)

網(wǎng)站建設(shè)

服務(wù)器托管

[一篇讀懂]C語(yǔ)言十講：?jiǎn)捂湵淼男陆?、查?創(chuàng)新互聯(lián)