数据结构の链表 - 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