内容简介： 从这篇博客开始，我针对数据结构与算法整理总结一些代码实践，希望能加深自己对代码的理解，也能帮助到其他小伙伴。 首先，我简单说明一下为什么数据结构在软件开发中如此重要，因为程序本质就是数据结构加算法，只不过现在很多语言对数据处理都有了很好的调用包帮大家封装好了相应数据，所以实际开发的过程中可能用到数据结构的机会并不多，但是常用的数据结构还是蕴含着编程思想的精华。 那么，什么是数据结构呢，按照学术的定义就是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构就是数组，链表，树，还有哈希表。队
从这篇博客开始，我针对数据结构与算法整理总结一些代码实践，希望能加深自己对代码的理解，也能帮助到其他小伙伴。
2.数据结构简介
首先，我简单说明一下为什么数据结构在软件开发中如此重要，因为程序本质就是数据结构加算法，只不过现在很多语言对数据处理都有了很好的调用包帮大家封装好了相应数据，所以实际开发的过程中可能用到数据结构的机会并不多，但是常用的数据结构还是蕴含着编程思想的精华。
那么，什么是数据结构呢，按照学术的定义就是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构就是数组，链表，树，还有哈希表。队列和栈都是可以通过数组和链表做功能实现的，队列就可以通过数组取值实现先进先出的功能就可以称作队列数据结构了，当然链表也可以实现先进先出，这样就是链表队列了，同样的如果对数组和链表实现先进后出实现就成为了栈，在相关数据结构博客后面我会教大家如何利用数组和链表实现队列及栈的。本篇博客，我们先来了解和实现链表数据结构。
其实链表本身设计也可以玩出非常多的花样，像 linux 内核相关数据结构就用了一种让相应链表结构包含数据本身的设计思想，从而实现对各种不同类型数据封装兼容，而不需要使各种数据本身去扩展包含实现链表本身。这样的利用指针指向数据本身再封装成链表的思想简直可以说非常精华了。这也是linux之父，linus的设计巧妙之所在呀！好了我说了这么多，数据结构的好处和妙用，下面我们就开始今天的数据结构之单链表吧。
3.单链表实现及使用
3.1单链表结构
我们设计一个简单的单链表结构，如下：
struct ListNode {
int value;
struct ListNode *next;
};
typedef struct ListNode , * list;
phead为单链表的头指针，它指向表中的第一个节点，头结点的数据可以不存储然后信息，也可以设计成存储线性表长度等附加信息。下面我们学习如何使用链表：
3.2打印单链表
首先，我们可以利用链表打印数据
/*我们开始创建链表并按顺序打印链表的value，开始第一次的链表使用*/
ListNode *creat(int n)
{
int i;
ListNode *phead, *p1, *p2;
/*head用来标记链表，p1总是用来指向新分配的内存空间，
p2总是指向尾结点，并通过p2来链入新分配的结点*/
int a;
phead = NULL;
p2 = NULL;
for (i = 1; i <= n; i++)
{
p1 = (ListNode *)malloc(sizeof(ListNode));
/*动态分配内存空间，并数据转换为(struct LNode)类型*/
printf("请输入链表中的第%d个数：", i);
scanf_s("%d", &a);
p1->data = a;
if (phead == NULL)/*指定链表的头指针*/
{
phead = p1;
p2 = p1;
}
else
{
p2->next = p1;
p2 = p1;
}
p2->next = NULL;/*尾结点的后继指针为NULL(空)*/
}
return phead;/*返回链表的头指针*/
}
void main()
{
int n;
ListNode *q;
printf("请输入链表的长度：/n");
scanf_s("%d", &n);
q = creat(n);/*链表的头指针(head)来标记整个链表*/
printf("/n链表中的数据：/n");
while (q)/*直到结点q为NULL结束循环*/
{
printf("%d ", q->data);/*输出结点中的值*/
q = q->next;/*指向下一个结点*/
}
}
3.2单链表排序
下面实现稍微复杂的一些的链表操作，比如单链表的排序，单独 排序 功能实现常见的就有插入排序，冒泡排序，简单排序，快速排序，这里我们简单实现一些插入排序好了。
void sort(list linklist)
{
/*如果链表没有元素，或者只有一个元素就直接返回*/
if((linklist -> next == NULL) || (linklist -> next -> next == NULL))
{
return;
}
ListNode * phead, * p1, * prep1, * p2, * prep2, * temp;
phead = linklist;
prep1 = phead -> next;
p1 = prep1 -> next;
//prep1和p1是否需要手动后移
bool flag;
while(p1 != NULL)
{
flag = true;
temp = p1;
//由于是单向链表，所以只能从头部开始检索
for(prep2 = head, p2 = prep2 -> next; p2 != p1; prep2 = prep2 -> next, p2 = p2 -> next)
{
//发现第一个较大值
if(p2 -> val > p1 -> val)
{
p1 = p1 -> next;
prep1 -> next = p1;
prep2 -> next = temp;
temp -> next = p2;
flag = false;
break;
}
}
//手动后移prep1和p1
if(flag)
{
prep1 = prep1 -> next;
p1 = p1 -> next;
}
}
}
3.2单链表翻转
然后，我们试一下对链表进行翻转操作：
ListNode reverse(list linklist)//两两节点之间不断交换
{
ListNode *phead；
phead = linklist;
/*如果为空直接返回*/
if(phead == NULL || phead->next == NULL)
return phead;
//定义俩个辅助指针变量
ListNode pre = NULL;
ListNode next = NULL;
//开始进行翻转
while(phead != NULL){
//让辅助指针next指向下一个节点，如果是第一次进入就是指向头指针下一跳
next = phead->next;
//让当前节点指向pre
phead->next = pre;
//进行调换
pre = phead;
//并让头节点指向下一跳
phead = next;
}
//返回pre就是新生成的头结点
return pre;
}
好了，今天单链表讲到这里，我们下篇见！
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- 数据结构 1 线性表详解 链表、 栈 、 队列 结合JAVA 详解
- Runtime数据结构详解
- conntrack中的数据结构详解
- 数据结构之单链表详解二
- 3.10 solidity数据结构详解
- HBase数据结构与基本语法详解
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
