目录
一、概述
二、线性表介绍
三、单链表的操作实现
📌3.1 C语言定义链表结点
📌3.2 单链表初始化
📌3.3 单链表插入数据
📌3.4 单链表删除数据
📌3.5 单链表查找数据
📌3.6 单链表的销毁
四、单链表完整代码
线性表是最基础的一种数据结构，从定义来看，线性表除了第一个元素和最后一个元素之外，其他元素都有唯一的前驱和唯一的后继；在计算机实现线性表有
顺序存储结构、链式存储结构2种，在C语言中，这两种线性表的存储结构分别对应到数组和链表。本文将介绍线性表的定义、一些基础概念(头结点、头指针、单链表、循环链表、双向链表等)、最后实现一个单链表。
线性表：零个或多个数据元素的有序排列。
解释：线性表的元素可以是零个，也可以多个，若存在多个元素，则第一个无前驱、最后一个无后继，其他元素有且只有一个前驱、后继；
举例：
①军训时排列好的队伍属于线性表；
②将十二生肖排列起来也属于线性表：鼠、牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪。
线性表的抽象数据类型
抽象数据类型可以理解为：有哪些数据以及哪些操作。
线性表的抽象数据类型如下：Dara(数据及关系) 有零个或多个数据元素，每个数据元素类型为ElemType; 数据元素之间是一对一的关系； Operate(操作) InitList(*L); // 初始化操作，建立一个空的线性表； ListEmpty(L); // 判断线性表是否为空； ClearList(L); // 将线性表清空； GetElem(L,i,*e);// 获取第i个元素，并通过e将值返回； LocateElem(L); // 查询值为e的元素，并返回序号 ListInsert(*L,i, e); // 插入元素 ListInDelete(*L,i,*e); // 删除元素； ListInLength(L); // 线性表长度； endADT对于不同的应用，线性表的操作是不同的，上述操作是最基本的，有些线性表可能会有更复杂的操作。
线性表的顺序存储结构：用一段地址连续的存储单元，依次存储线性表的数据元素。
在C语言中，可以用一维数组来实现线性表顺序存储结构，#define MAXSIZE 20 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int length; }优点：可以快速查询元素；不需增加额外存储空间。
缺点：插入、删除元素需要移动大量元素；长度变化大，不好确定存储空间容量。
线性表的链式存储结构：用一组任意的存储单元来存储线性表的数据元素，这组存储单元可以是不连续的。
特点：每个存储单元不仅要存储数据(数据域)，还需要存储后继元素的地址(指针域)。
头指针：指向链表第一个结点的指针，保存了第一个结点的地址。若有头结点，则指向头结点。头指针是链表的必需元素。
头结点：为了方便操作链表，在第一个结点前增加的一个结点，其数据域可以不存储任何信息，指针域存储第一个结点地址。有了头结点，第一个元素的插入和删除操作就和其他元素一样了。头结点不是必须的。
在C语言中，可以用结构体指针来实现线性表链式存储结构，typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; // 指向结点的指针 }Node; // 定义链表结点：包含数据域，指针域 typedef struct Node *LinkList;// 定义链表，是指向结点的指针
上一小节，了解到线性表的一些基础知识，也知道了线性表的 顺序存储结构 可以用C语言的 数组 实现，而 链式存储结构 可以用 结构体指针 来实现，关于数组的一些操作如：初始化、插入元素、删除元素、清空数组，都比较简单，本文不作阐述；但是关于使用结构体指针来实现 链式存储结构 的“初始化、插入元素、删除元素、清空”等操作使，常常会使初学者感到迷惑。
这一小节，带你理解C语言使用结构体指针实现单链表的基础操作。
单链表是由一个个结点连接而成的，结点的结构体一般都有一个指向结点的指针，如下面代码的struct Node *next;，前一个结点就是依靠这个指针(地址)找到下一个结点的；结点的结构体除了这个指针之外的其他字段都可以认为是用来保存数据的数据域，如下面代码的ElemType data;，这里定义类型只是一个int型，实际使用中，往往是比较复杂的结构体。
typedef struct Node *LinkList;定义了一个指向结点的指针类型为LinkList，其实这个可以理解为头指针，头指针是链表必需的，但也可以不定义成List，直接使用struct Node*去初始化链表也可以，定义成LinkList是为了写代码时方便理解。
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node *next; // 指向结点的指针
}Node; // 定义链表结点：包含数据域，指针域
typedef struct Node *LinkList;// 定义链表，是指向结点的指针
本文介绍的单链表带有头结点，这样的好处是第一个结点的插入和删除不需要特殊处理。因为是带有头结点的链表，所以初始化链表的算法思路如下：
1、分配一个结点的存储空间作为头结点，并将头指针指向头结点；
2、让头结点的next指针指向NULL，头结点的数据填一个无效值；
3、将头指针返回给函数调用者。
C语言实现代码如下：
LinkList ListInit()
{
LinkList list = (LinkList)malloc(sizeof(ListNode));
list->next = NULL;
list->data = -1;
return list;
}
单链表插入数据时，一定要记住顺序：先连接、后断开。
先连接：是指先新节点连接当前节点的下个节点，new->next = cur->next;
后断开：将当前节点的的指针域指向新节点，与旧节点断开，cur->next = new;
如果这两个顺序反了，先执行cur->next = new;，会导致cur后面的数据全部都丢了，因为cur->next原本是保存着后继元素的地址的，现在直接被覆盖后，就无法继续查找后继元素了。
单链表在第n个位置插入数据的算法思路：
1、定义一个结点指针cur指向头结点，用来遍历链表；
2、定义一个变量i，用来表示下个结点的序号，初始化为1(头结点下个结点就是第一结点)；
3、将cur指针不断往后移动，直到下个位置就是插入位置n，即当i==n跳出循环;
4、若结束循环后，cur为无效结点，说明循环到最后一个结点时，链表长度不够；
5、否则，说明当前结点cur的下个位置就是插入位置n，分配存储空间给新结点new；
6、把值填进新节点的数据域，用新结点指向当前节点的下个节点；
7、将当前节点指向新节点，完成插入操作。
C语言实现代码如下：
int ListInsert(LinkList list, int data, int n)// 将node插入到第n位,n从1开始
{
ListNode* cur = list;// cur指向当前结点，初始化指向头结点
int i=1; // i表示下个结点的序号
while(cur && i<n) // 当前结点有效，且下个位置不是插入位置，就往后移动一个
{
cur = cur->next;
i++;
}
if(!cur) // 当前结点无效，说明已经移动到最后
{
printf("[%s %d]error din't have No.%d\n", __FUNCTION__,__LINE__, n);
return -1; // 链表没有 n 那么长
}
ListNode* new = (ListNode*)malloc(sizeof(ListNode));
new->data = data;
new->next = cur->next;
cur->next = new;
return 0;
}
单链表要删除下一个结点的话，就是“把当前结点的指针指向下一个结点的下一个结点”，这样就删除了下一个结点。如果可以理解这句话的话，删除结点就是一句代码cur->next = cur->next->next;。如下图，删除结点p，只需要把结点p的指针指向p->next->next。如果不好理解，也可以先找到要删除的结点delete，再它的下个结点delete->next给cur的指针。
单链表删除第n个数据的算法思路：
1、定义一个结点指针cur指向头结点，用来遍历链表；
2、定义一个变量i，用来表示下个结点的序号，初始化为1(头结点下个结点就是第一结点)；
3、当下个结点(cur->next)有效，且下个位置不是删除位置n，就继续后移，直到无效或i==n跳出循环;
4、若结束循环后，下个结点(cur->next)为无效结点，说明循环到最后一个结点了，链表长度不够；
5、否则，说明下个结点(cur->next)就是删除位置n的结点delete，赋值delete = cur->next；
6、将当前结点的指针域指向delete的下个结点，cur->next=delete->next;
7、最后释放delete结点的内存，完成删除操作。
C语言实现代码如下，删除结点更关注的是下个结点(cur->next)的有效性：
// 删除第n个结点，且将删除的值通过data传出
int ListDelete(LinkList list, int *data, int n)
{
ListNode* cur = list;// cur指向当前结点，初始化指向头结点
int i=1; // i表示下个结点的序号
while(cur->next && i<n)// 下个结点有效，且下个位置不是删除位置，就往后移动一个
{
cur = cur->next;
i++;
}
if(!cur->next) // 下个结点无效，说明已经移动到最后
{
printf("[%s %d]error din't have No.%d\n", __FUNCTION__,__LINE__, n);
return -1; // 链表没有 n 那么长
}
ListNode *delete = cur->next;
cur->next = delete->next;
free(delete);
return 0;
}
单链表查找第n个数据的算法思路：
1、定义一个结点指针cur指向第一个结点，用来遍历链表；
2、定义一个变量cur_i，用来表示当前结点的序号，初始化为1(第一步指向的就是第一个结点)；
3、当前个结点(cur)有效，且当前位置不是查找位置n，就继续后移，直到无效或i==n跳出循环;
4、若结束循环后，当前结点(cur)为无效结点，说明循环到最后一个结点了，链表长度不够；
5、否则，说明当前结点(cur)就是查找位置n的结点；返回结点数据*data = cur->data。
C语言实现代码如下：
int ListFind(LinkList list, int *data, int n)
{
ListNode* cur = list->next;// 指向第一个节点
int cur_i=1; // i表示当前结点的序号
while(cur && cur_i<n) // 当前结点有效，且当前位置不是查找位置n，就往后移动一个
{
cur = cur->next;
cur_i++;
}
if(!cur) // 当前结点无效，说明已经移动到最后
{
printf("[%s %d]error din't have No.%d\n", __FUNCTION__,__LINE__, n);
return -1; // 链表没有 n 那么长
}
*data = cur->data;
printf("[%s %d]find No.%d = %d\n", __FUNCTION__,__LINE__, n,*data);
return 0;
}
单链表销毁的算法思路：
1、定义一个结点指针cur指向第一个结点，用来遍历链表；
2、定义一个结点指针next，保存下个结点地址，所以先保存在next；
3、当前个结点(cur)有效，进入循环：
3.1、先保存下个结点地址，因为下个结点本来保存在cur->next，直接free(cur)会丢掉下个结点；
3.2、删除当前结点，释放内存
3.3、将当前指针指向前面保存好的下个结点。
4、结束循环后，已经删除完所有节点，此时需要将头指针指向NULL，表示空链表。
C语言实现代码如下：
void ListDestroy(LinkList list)
{
ListNode* cur = list->next; // 指向第一个节点
ListNode* next = NULL; // 用于保存下个结点地址
while(cur) // 当前结点有效，就往后移动
{
next = cur->next; // 保存下个结点地址
//printf("[%s %d]delete %d\n", __FUNCTION__,__LINE__, cur->data);
free(cur); // 删除当前结点、并释放内存
cur = next; // 将当前结点指针指向下个结点
}
list->next = NULL;
}
下面是带有头结点的单链表完整代码，已经在Ubuntu下编译通过，并使用了，复制代码保存为LinkList.c，然后再Ubuntu命令行执行gcc LinkList.c -o LinkList去编译。
// LinkList.c
#include <stdio.h>
#include <stdlib.h>
typedef struct _ListNode
{
int data;
struct _ListNode *next;
}ListNode;
typedef ListNode* LinkList;
LinkList ListInit()
{
LinkList list = (LinkList)malloc(sizeof(ListNode));
list->next = NULL;
list->data = -1;
return list;
}
int ListInsert(LinkList list, int data, int n)// 将node插入到第n位,n从1开始
{
ListNode* cur = list;// cur指向当前结点，初始化指向头结点
int i=1; // i表示下个结点的序号
while(cur && i<n) // 当前结点有效，且下个位置不是插入位置，就往后移动一个
{
cur = cur->next;
i++;
}
if(!cur) // 当前结点无效，说明已经移动到最后
{
printf("[%s %d]error din't have No.%d\n", __FUNCTION__,__LINE__, n);
return -1; // 链表没有 n 那么长
}
ListNode* new = (ListNode*)malloc(sizeof(ListNode));
new->data = data;
new->next = cur->next;
cur->next = new;
return 0;
}
// 删除第n个结点，且将删除的值通过data传出
int ListDelete(LinkList list, int *data, int n)
{
ListNode* cur = list;// cur指向当前结点，初始化指向头结点
int i=1; // i表示下个结点的序号
while(cur->next && i<n)// 下个结点有效，且下个位置不是删除位置，就往后移动一个
{
cur = cur->next;
i++;
}
if(!cur->next) // 下个结点无效，说明已经移动到最后
{
printf("[%s %d]error din't have No.%d\n", __FUNCTION__,__LINE__, n);
return -1; // 链表没有 n 那么长
}
ListNode *delete = cur->next;
cur->next = delete->next;
free(delete);
return 0;
}
int ListFind(LinkList list, int *data, int n)
{
ListNode* cur = list->next;// 指向第一个节点
int cur_i=1; // i表示当前结点的序号
while(cur && cur_i<n) // 当前结点有效，且当前位置不是查找位置n，就往后移动一个
{
cur = cur->next;
cur_i++;
}
if(!cur) // 当前结点无效，说明已经移动到最后
{
printf("[%s %d]error din't have No.%d\n", __FUNCTION__,__LINE__, n);
return -1; // 链表没有 n 那么长
}
*data = cur->data;
printf("[%s %d]find No.%d = %d\n", __FUNCTION__,__LINE__, n,*data);
return 0;
}
void ListDestroy(LinkList list)
{
ListNode* cur = list->next; // 指向第一个节点
ListNode* next = NULL; // 用于保存下个结点地址
while(cur) // 当前结点有效，就往后移动
{
next = cur->next; // 保存下个结点地址
//printf("[%s %d]delete %d\n", __FUNCTION__,__LINE__, cur->data);
free(cur); // 删除当前结点、并释放内存
cur = next; // 将当前结点指针指向下个结点
}
list->next = NULL;
}
void ListPrintf(LinkList list)
{
ListNode* cur = list->next;// 指向第一个节点
printf("list:[");
while(cur)
{
printf("%d,",cur->data);
cur = cur->next;
}
printf("]\n");
}
int main()
{
LinkList list=ListInit();
int data=0;
printf("Linklist is empty !!! \n");
ListInsert(list, 2, 2); // 空链表时，验证插入
ListDelete(list, &data, 1); // 空链表时，验证删除
ListFind(list, &data, 1); // 空链表时，验证查询
ListDestroy(list); // 空链表时，验证销毁
printf("\ninsert 3 data\n");
// 正常插入3个数据
ListInsert(list, 1, 1);
ListInsert(list, 2, 2);
ListInsert(list, 3, 3);
ListPrintf(list);
printf("\n验证错误值\n");
ListInsert(list, 5, 5); // 验证插入
ListDelete(list, &data, 4); // 验证删除
ListFind(list, &data, 4); // 验证查询
printf("\n正常操作\n");
// 正常操作
ListFind(list, &data, 2);
printf("delete 2,now\n");
ListDelete(list, &data, 2);
ListPrintf(list);
printf("Insert 4 to 2,now\n");
ListInsert(list, 4, 2);
ListPrintf(list);
printf("Destroy ,now\n");
ListDestroy(list);
ListPrintf(list);
return 0;
}
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案 查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has
我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden
我的主要目标是能够完全理解我正在使用的库/gem。我尝试在Github上从头到尾阅读源代码，但这真的很难。我认为更有趣、更温和的踏脚石就是在使用时阅读每个库/gem方法的源代码。例如，我想知道RubyonRails中的redirect_to方法是如何工作的:如何查找redirect_to方法的源代码？我知道在pry中我可以执行类似show-methodmethod的操作，但我如何才能对Rails框架中的方法执行此操作？您对我如何更好地理解Gem及其API有什么建议吗？仅仅阅读源代码似乎真的很难，尤其是对于框架。谢谢! 最佳答案 Ru
有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳
我的假设是moduleAmoduleBendend和moduleA::Bend是一样的。我能够从thisblog找到解决方案,thisSOthread和andthisSOthread.为什么以及什么时候应该更喜欢紧凑语法A::B而不是另一个，因为它显然有一个缺点？我有一种直觉，它可能与性能有关，因为在更多命名空间中查找常量需要更多计算。但是我无法通过对普通类进行基准测试来验证这一点。 最佳答案 这两种写作方法经常被混淆。首先要说的是，据我所知，没有可衡量的性能差异。(在下面的书面示例中不断查找)最明显的区别，可能也是最著名的，是你的
几个月前，我读了一篇关于rubygem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：
我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。 最佳答案 在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur