数据结构の链表 - Visual Linked List

发表于   |  

SinglyLinkedList

几个月没更新网站, 都快长草了. 上周终于放了寒假, 所以有时间过来发布一个之前写的感觉怪怪的程序刷刷存在感.

科普

「链表」是一种比较有意思的数据结构, 顾名思义, 就是用指针将一个个本没有联系的”节点”链接起来, 其好处在于能够动态分配内存. 如何创建链表呢? 先举个简单的栗子. (单链表静态创建)

定义节点结构

1
2
3
4
5
struct XF_NODE
{
	char szData[1024];		//数据区域
	struct XF_NODE *Next;	//存放下一个节点的地址
};

建立若干个节点

就是定义几个该结构的指针变量并分配内存空间. 

1
2
3
4
struct XF_NODE *Head, *Node2, *Node3;
Head = (struct XF_NODE*)malloc(sizeof(struct XF_NODE));
Node2 = (struct XF_NODE*)malloc(sizeof(struct XF_NODE));
Node3 = (struct XF_NODE*)malloc(sizeof(struct XF_NODE));

填入数据, 搞好关系

1
2
3
4
5
6
strcpy(Head->szData, "I'm the Node 1");
strcpy(Node2->szData, "I'm the Node 2");
strcpy(Node3->szData, "I'm the Node 3");
Head->Next = Node2;
Node2->Next = Node3;
Node3->Next = NULL;

遍历链表

链条建好后便可以操作里面的内容, 比如依次输出等等.. 

1
2
3
4
5
6
struct XF_NODE *Temp = Head;
while (Temp)
{
	puts(Temp->szData);
	Temp = Temp->Next;
}

善后处理

一个优秀的C/C++程序猿, 要养成内存用完后马上释放的好习惯. 

1
2
3
free(Head);
free(Node2);
free(Node3);

结果

I'm the Node 1
I'm the Node 2
I'm the Node 3
Press any key to continue . . .


登场: Visual Linked List

VisualLinkedList

「Visual Linked List」不仅可以实现链表的动态创建, 插入, 删除, 排序, 逆置等操作, 还能通过 Windows GDI 把整个链表绘制出来(快速提高程序的逼格), 也让初学者能够更清晰了解整张表在内存中的结构, 方便学习.


工作原理

创建链表

函数BuildLinkList() 实现链表的动态创建, 返回头结点指针. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
NODE *BuildLinkList(UINT NodeNumber, TCHAR szNodeData[][MAX_NODE_LENGTH])
{
	UINT uCurrentNodeNumber = 1;
	NODE *Head, *BufferA, *BufferB;
	if (NodeNumber <= 0)
		return NULL;
	while (uCurrentNodeNumber <= NodeNumber)
	{
		BufferA = (NODE *)malloc(sizeof(NODE));
		BufferA->szNodeData = szNodeData[uCurrentNodeNumber - 1];
		if (uCurrentNodeNumber == 1)
		{
			Head = BufferB = BufferA;
			uCurrentNodeNumber++;
			continue;
		}
		BufferB->Next = BufferA;
		BufferB = BufferA;
		uCurrentNodeNumber++;
	}
	BufferA->Next = NULL;
	return Head;
}

插入节点

插入节点体现了数学中所谓的分类讨论思想, 有以下两种情况:

  1. 待插入节点位于头结点前: 取代头结点, 把指针指向原头结点
  2. 待插入节点位于头结点后: 前一个节点->Next = 待插入节点, 待插入节点->Next = 前个节点->Next 
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
NODE * InsertNode(NODE *Head, NODE *TobeInserted, UINT uPosition)
{
	NODE *Temp, *Prev;
	UINT uCurrentNode = 1;
	if (uPosition <= 0)
	{
		TobeInserted->Next = Head;
		Head = TobeInserted;
		return Head;
	}
	for (Temp = Head; Temp&&uCurrentNode < uPosition; uCurrentNode++)
	{
		Prev = Temp;
		Temp = Temp->Next;
	}
	if (!Temp)
	{
		TobeInserted->Next = NULL;
		Prev->Next = TobeInserted;
	}
	else
	{
		TobeInserted->Next = Temp->Next;
		Temp->Next = TobeInserted;
	}
	return Head;
}

删除节点

遍历链表, 删除所有包含参数 szDeleteNodeData 指向的字符串的节点, 跟上面一样需要分类讨论

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
BOOL DeleteNode(NODE *Head, TCHAR *szDeletedNodeData)
{
	BOOL bTag = FALSE;
	NODE *Temp, *Prev, *Deleted;
	if (!Head)
		return FALSE;
	while (Head && !wcscmp(Head->szNodeData, szDeletedNodeData))
	{
		Deleted = Head;
		LinkListHead = Head = Head->Next;
		free(Deleted);
		bTag = TRUE;
	}
	for (Prev = Temp = Head; Temp; )
	{
		if (!wcscmp(Temp->szNodeData, szDeletedNodeData))
		{
			Deleted = Temp;
			Prev->Next = Temp->Next;
			Temp = Temp->Next;
			free(Deleted);
			bTag = TRUE;
			continue;
		}
		Prev = Temp;
		Temp = Temp->Next;
	}
	return bTag;
}

链表排序

简单排序算法 

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
BOOL SortLinkList(NODE *Head, BOOL bType)
{
	// When bType is True, Data: low to high
	// When bType is False, Data: high to low
	NODE *TempA, *TempB;
	TCHAR *szPointer;
	if (!Head || !Head->Next)
		return TRUE;
	for (TempA = Head; TempA->Next; TempA = TempA->Next)
	{
		for (TempB = TempA->Next; TempB; TempB = TempB->Next)
		{
			if (bType)
			{
				if (wcscmp(TempB->szNodeData, TempA->szNodeData) < 0)
				{
					szPointer = TempA->szNodeData;
					TempA->szNodeData = TempB->szNodeData;
					TempB->szNodeData = szPointer;
				}
			}
			else
			{
				if (wcscmp(TempB->szNodeData, TempA->szNodeData) > 0)
				{
					szPointer = TempA->szNodeData;
					TempA->szNodeData = TempB->szNodeData;
					TempB->szNodeData = szPointer;
				}
			}
		}
	}
	return TRUE;
}

链表逆置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
NODE * ReverseLinkList(NODE *Head)
{
	NODE *TempA, *TempB, *Prev;
	if (!Head)
		return NULL;
	if (!Head->Next)
		return Head;
	for (TempA = Head, TempB = NULL; TempA;)
	{
		Prev = TempA;
		TempA = TempA->Next;
		Prev->Next = TempB;
		TempB = Prev;
	}
	Head = Prev;
	return Head;
}

绘制链表

Visual Linked List 每对链表进行一次操作, 都会扔给Windows一个WM_PAINT消息, 然后在消息处理函数MainWindowProc()中重新绘制, 具体实现有兴趣的话请查看完整源码.(第150-163, 496-543行)


悄悄说下这几个月我在干嘛

  1. 首先作为学生当然要做学生该做的事情
  2. 除此之外, 花时间学习了一些有关 C/C++, HTML, Unity等领域的开发技能与一点点调试, 破解 反编译技巧
  3. 学习网络工程方面的知识, 以及实战Linux, WinServer的运维
  4. 二次元: Fate/Zero, Fate/UBW, Sword Art Online, Black Rock Shooter, Puella Magi Madoka Magica..
  5. 着手开发了几个看似并没有什么用的 Win32 项目(包括 Visual Linked List), 其中唯一一个比较实用的炒鸡大型项目已经完成了内测, 目测会在今年过年之前发布. P.s: 说是内测其实就是我自己拿着软件在几台不同的电脑上测试而已_(:3 」∠)_


下载

源码: Download Source Code
成品: Download Executable Binary File

(c) 雪峰 2015