प्रौद्योगिकी साझेदारी

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

हाय~! एषः संघर्षशीलः लघु मेषः अस्ति यत् भवान् मम लेखं पठितुं शक्नोति तथा च किञ्चित् सल्लाहं ददातु
💥💥个人主页：संघर्षशीलः मेषः
💥💥所属专栏：ग भाषा

🚀本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

---

प्रस्तावना

एकललिङ्क् कृता सूची केवलं कस्यचित् नोड् इत्यस्य पताद्वारा एकस्मिन् दिशि दत्तांशं प्राप्तुं शक्नोति, यदा तु द्विगुणितसूची नोडस्य पताद्वारा उभयदिशि दत्तांशं प्राप्तुं शक्नोति योजनस्य, विलोपनस्य, जाँचस्य, परिवर्तनस्य च कार्यक्षमता अधिका भवति, परन्तु एकललिङ्कितसूचिकायाः ​​अपेक्षया कोडस्य कार्यान्वयनम् सरलतरं भवति , द्विगुणलिङ्कितसूचीनां लाभाः अधिकं स्पष्टाः भवन्ति ।

---

1. लिङ्क् कृतसूचीनां वर्गीकरणं

लिङ्क्ड् सूचीः अष्टप्रकारेषु विभक्ताः सन्ति : शिरः, अशिरः, एकदिशा, द्विपक्षीयः, चक्रीयः, अचक्रीयः च वयं केवलं सामान्यानि एव शिक्षेम ।एकदिशा अचक्रीयलिङ्किता सूची विना नेतातथाद्विपक्षीयवृत्तीयलिङ्कितसूचीं प्रमुखं कृतवान्, अर्थात्एकलसूचीतथाद्विगुणितसूची。
द्विगुणितसूची : १.

वस्तुतः अन्तिमे लेखे वयं एकललिङ्कितसूचिकायाः ​​प्रथमं नोडं हेड नोड् इति आह्वयन्तः, यत् अशुद्धम् अस्ति तस्य कारणं सुलभतया अवगन्तुं भवति, यतः एकललिङ्क् कृतस्य सूचीयाः शिरः नास्ति, तथा च केवलं द्विगुणितसूचिकायां शिरः नोड् इति आह्वयतिसेंटिनल स्थिति。

• द्विगुणसम्बद्धसूचिकायाः ​​हेड नोड् मध्ये वैधदत्तांशः संगृहीतः नास्ति, परन्तु अमान्यदत्तांशः ।
• प्रहरणस्थानं परिवर्तयितुं न शक्यते, केवलं तस्य दिशां परिवर्तयितुं शक्यते।

---

2. द्विगुणलिङ्कितसूचिकायाः ​​कार्यान्वयनम्

२.१ द्विगुणितसूचीनोड्स्

द्विगुणलिङ्कितसूचिकायाः ​​नोड्स् दत्तांशसञ्चयस्य आवश्यकतां अनुभवन्ति, तथैव पूर्वस्य अग्रिमस्य च नोड्सस्य पताः अतः द्विगुणलिङ्कितसूचिकायाः ​​नोड्सः सन्ति :

typedef int dlist_data_type;

//双向链表节点
typedef struct dlist
{
	dlist_data_type data;
	struct dlist* next
	struct dlist* prev;
}dlist;
1
2
3
4
5
6
7
8
9

---

२.२ नोड् कृते आवेदनं कुर्वन्तु

एकललिङ्कितसूचिकायाः ​​विपरीतम्, द्विगुणलिङ्कितसूचौ न्यूनातिन्यूनम् एकः नोड् भवितुमर्हति, यः हेड नोड् अस्ति, यः सेन्टिनेल् बिट् इति अपि उच्यते ।
योजयितुं, विलोपयितुं, परीक्षितुं, परिवर्तनं वा कर्तुं पूर्वं,द्विगुणलिङ्कितसूचिका एकं सेन्टिनेल् बिट् आरभणीयम्, तथा च सेन्टिनेल् बिट् अमान्यदत्तांशं संगृह्णाति ।

प्रयुक्ते नोड् प्रारम्भे स्वयमेव सूचयन्तः द्वौ सूचकौ भवतः ।。

//申请节点
dlist* dlist_buy(dlist_data_type x)
{
	dlist* newdlist = (dlist*)malloc(sizeof(dlist));
	if (newdlist == NULL)
	{
		perror("malloc fail!");
		return 1;
	}
	newdlist->data = x;
	newdlist->next = newdlist;
	newdlist->prev = newdlist;
	return newdlist;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

सेन्टिनेल् बिट् इत्यस्य आरम्भस्य द्वौ उपायौ स्तः ।
मापदण्डरूपेण प्रत्यागतम्:

void dlist_init(dlist** pphead)
{
	assert(pphead);
	*pphead = dlist_buy(-1);
}
1
2
3
4
5

अस्मिन् पद्धत्या गौणसूचकानाम् उपयोगः आवश्यकः भवति ।
रिटर्न् वैल्यू इति रूपेण प्रत्यागतम्:

dlist* dlist_init()
{
	dlist* phead = dlist_buy(-1);
	return phead;
}
1
2
3
4
5

एषा पद्धतिः सरलतरः, सुलभतया च अवगन्तुं शक्नोति ।

---

२.३ दत्तांशस्य मुद्रणं अन्वेषणं च

दत्तांशस्य मुद्रणं अन्वेषणं च एकलङ्कितसूचिकायाः ​​अपेक्षया बहु भिन्नं नास्ति, अतः अहं विस्तरेण न गमिष्यामि ।
केवलं यत् ध्यानं आवश्यकं तत् लूपस्य समाप्त्यर्थं शर्तः यदा सूचकः सेन्टिनेल् बिट् प्रति सूचयति तदा लूप् समाप्तं भवति, न तु यदा सूचकः सेन्टिनेल् बिट् प्रति सूचयति ।NULL。

//打印数据
void dlist_print(dlist* phead)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULLn");
}
//查找
dlist* dlist_find(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

---

२.४ शिरःप्लग्, पुच्छप्लग् च

एकललिङ्क् कृतसूचिकायाः ​​विपरीतम्, द्विगुणलिङ्कितसूचिकायाः ​​योजनं, विलोपनं, प्रश्नं, परिवर्तनं च कार्याणि सेन्टिनेल् बिट् न परिवर्तयिष्यन्ति, अतः केवलंमूल्येन आह्वानं कुर्वन्तुतत् ।
द्विगुणितसूचिकायाः ​​सम्मिलनसञ्चालने त्रयः नोड्स् परिवर्तनस्य आवश्यकता भवति परिवर्तनप्रक्रियायाः समये, ध्यानं ददातुप्रथमं नूतनं नोड् परिवर्तयन्तु, ततः अग्रिमं नोड् परिवर्तयन्तु, अन्ते पूर्वस्य नोड् परिवर्तयन्तु ।

//插入操作不改变哨兵位，因此传一级指针即可
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* newdlist = dlist_buy(x);

	//新尾节点
	newdlist->prev = phead->prev;
	newdlist->next = phead;

	//旧尾节点
	phead->prev->next = newdlist;

	//头节点（哨兵位）
	phead->prev = newdlist;
}
//头插
void dlist_push_front(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* newdlist = dlist_buy(x);

	//新节点
	newdlist->prev = phead;
	newdlist->next = phead->next;

	//旧节点
	phead->next->prev = newdlist;

	//哨兵位
	phead->next = newdlist;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

---

२.५ शिरः लोपः पुच्छलोपः च

लोपक्रियायाः पूर्वापेक्षा अस्ति यत् नोड्स् न भवितुम् अर्हन्ति (सेंटिनलस्थानं न गण्यते), विलोपनात् पूर्वं, अद्यापि नोड्-सङ्केतं रक्षन्तु, द्विगुणलिङ्कितसूचौ पुनः सम्मिलितं कुर्वन्तु, ततः नोड्-विमोचयन्तु ।

//尾删
void dlist_pop_back(dlist* phead)
{
	assert(phead);
	assert(phead->next != phead);//双向链表不能为空
	dlist* del = phead->prev;
	//新尾节点
	del->prev->next = phead;
	//哨兵位
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

//头删
void dlist_pop_front(dlist* phead)
{
	assert(phead);
	assert(phead->next != phead);
	dlist* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

२.६ निर्दिष्टस्थाने दत्तांशं सम्मिलितं विलोपनं च

//在指定位置之后插入数据
void dlist_insert_back(dlist* pos, dlist_data_type x)
{
	assert(pos);
	dlist* newdlist = dlist_buy(x);
	newdlist->prev = pos;
	newdlist->next = pos->next;

	pos->next->prev = newdlist;
	pos->next = newdlist;
}
//删除指定位置的节点
void dlist_erase(dlist* pos)
{
	assert(pos);
	dlist* del = pos;
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

निर्दिष्टस्थाने दत्तांशं विलोपयित्वा ।यतः एतत् फंक्शन् मूल्येन आह्वयति, निर्दिष्टस्थाने नोड् मुक्तं कृत्वा, वयं केवलं औपचारिकं पैरामीटर् सूचकं सेट् कुर्मःNULL, तथा च वास्तविकः पैरामीटर् सूचकः अद्यापि एतत् स्थानं सूचयति, अतः फंक्शन् आह्वानस्य समाप्तेः अनन्तरं वास्तविकं पैरामीटर् सूचकं सेट् कर्तव्यम्NULL。

---

२.७ द्विगुणलिङ्कितसूचीं नाशयन्तु

द्विगुणसम्बद्धसूचिकायाः ​​विनाशस्य अन्त्यशर्तः यदा ट्रैवर्सल् सूचकः शिरः नोड् प्रति सूचयति तदा लूप् तः बहिः भग्नः भवति ।अन्ते सेंटिनलस्थानं पृथक् मुक्तं कर्तव्यम्, द्विगुणलिङ्कितसूचिकायाः ​​विनाशकार्यकॉलस्य समाप्तेः अनन्तरं, सेन्टिनेलबिट् प्रति सूचयति सूचकः अपि सेट् कर्तव्यः ।NULL。

//销毁
void dlist_destroy(dlist* phead)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		dlist* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(pcur);
	pcur = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

3. द्विगुणलिङ्कितसूचिकायाः ​​सम्पूर्णसङ्केतः

dlist.h:

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int dlist_data_type;

//双向链表节点
typedef struct dlist
{
	dlist_data_type data;
	struct dlist* next;
	struct dlist* prev;
}dlist;

//初始化
//插入数据之前，双向链表必须初始化到只有一个头节点（哨兵位）
//void dlist_init(dlist** pphead);//以参数的形式返回
dlist* dlist_init();//以返回值的形式返回

//打印数据
void dlist_print(dlist* phead);
//查找
dlist* dlist_find(dlist* phead, dlist_data_type x);
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x);
//头插
void dlist_push_front(dlist* phead, dlist_data_type x);
//尾删
void dlist_pop_back(dlist* phead);
//头删
void dlist_pop_front(dlist* phead);
//在指定位置之后插入数据
void dlist_insert_back(dlist* pos, dlist_data_type x);
//删除指定位置的节点
void dlist_erase(dlist* pos);
//销毁
void dlist_destroy(dlist* phead);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

dlist.c:

#define  _CRT_SECURE_NO_WARNINGS

#include "dlist.h"

//申请节点
dlist* dlist_buy(dlist_data_type x)
{
	dlist* newdlist = (dlist*)malloc(sizeof(dlist));
	if (newdlist == NULL)
	{
		perror("malloc fail!");
		return 1;
	}
	newdlist->data = x;
	newdlist->next = newdlist;
	newdlist->prev = newdlist;
	return newdlist;
}

//初始化
//void dlist_init(dlist** pphead)
//{
//	assert(pphead);
//	*pphead = dlist_buy(-1);
//}

dlist* dlist_init()
{
	dlist* phead = dlist_buy(-1);
	return phead;
}

//打印数据
void dlist_print(dlist* phead)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULLn");
}

//查找
dlist* dlist_find(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//插入操作不改变哨兵位，因此传一级指针即可
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* newdlist = dlist_buy(x);

	//新尾节点
	newdlist->prev = phead->prev;
	newdlist->next = phead;

	//旧尾节点
	phead->prev->next = newdlist;

	//头节点（哨兵位）
	phead->prev = newdlist;
}

//头插
void dlist_push_front(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* newdlist = dlist_buy(x);

	//新节点
	newdlist->prev = phead;
	newdlist->next = phead->next;

	//旧节点
	phead->next->prev = newdlist;

	//哨兵位
	phead->next = newdlist;
}

//尾删
void dlist_pop_back(dlist* phead)
{
	assert(phead);
	assert(phead->next != phead);//双向链表不能为空
	dlist* del = phead->prev;
	//新尾节点
	del->prev->next = phead;
	//哨兵位
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

//头删
void dlist_pop_front(dlist* phead)
{
	assert(phead);
	assert(phead->next != phead);
	dlist* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}

//在指定位置之后插入数据
void dlist_insert_back(dlist* pos, dlist_data_type x)
{
	assert(pos);
	dlist* newdlist = dlist_buy(x);
	newdlist->prev = pos;
	newdlist->next = pos->next;

	pos->next->prev = newdlist;
	pos->next = newdlist;
}

//删除指定位置的节点
void dlist_erase(dlist* pos)
{
	assert(pos);
	dlist* del = pos;
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

//销毁
void dlist_destroy(dlist* phead)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		dlist* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(pcur);
	pcur = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

test.c:

#define  _CRT_SECURE_NO_WARNINGS

#include "dlist.h"

void test()
{
	//dlist* plist = NULL;
	//dlist_init(&plist);

	dlist* plist = dlist_init();

	//尾插
	dlist_push_back(plist, 1);
	dlist_push_back(plist, 2);
	dlist_push_back(plist, 3);
	dlist_print(plist);
	
	//头插
	//dlist_push_front(plist, 1);
	//dlist_push_front(plist, 2);
	//dlist_push_front(plist, 3);
	//dlist_print(plist);

	//尾删
	//dlist_pop_back(plist);
	//dlist_pop_back(plist);
	//dlist_pop_back(plist);
	//dlist_print(plist);

	//头删
	//dlist_pop_front(plist);
	//dlist_print(plist);
	//dlist_pop_front(plist);
	//dlist_print(plist);
	//dlist_pop_front(plist);
	//dlist_print(plist);

	//dlist* find = dlist_find(plist, 2);
	//dlist_insert_back(find, 4);
	//dlist_print(plist);

	//dlist* find = dlist_find(plist, 2);
	//dlist_erase(find);
	//find = NULL;
	//dlist_print(plist);

	dlist_destroy(plist);
	plist = NULL;//手动置空
}

int main()
{
	test();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

---

4. अनुक्रमसूचिकायाः ​​लिङ्क्ड् सूचीयाः च तुलना

अनुक्रमसूचीनां तथा लिङ्क्ड् सूचीनां पूरकलाभाः सन्ति तथा च भिन्न-भिन्न-अनुप्रयोग-परिदृश्येषु स्व-स्व-लाभान् प्रयोक्तुं शक्नुवन्ति ।

---

सारांशं कुरुत

• यदि अनुप्रयोगपरिदृश्ये नित्यं अन्वेषण-विलोपन-क्रियाणां आवश्यकता भवति तथा च अधिकं स्मृति-उपभोगं स्वीकुर्वितुं शक्नोति तर्हि द्विगुणित-सूची अधिका उपयुक्ता भवितुम् अर्हति ।
• यदि स्मृतिः सीमितः अस्ति अथवा अन्वेषण-विलोपन-क्रियाणां कार्यक्षमता अधिका नास्ति तर्हि एकैकं लिङ्क् कृता सूची अधिका उपयुक्ता भवितुम् अर्हति ।