链表
链表基础
定义：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
特点：
结点地址不连续
结点：
定义：组成链表的基本单元
组成：用户需要用的实际数据和下一个结点的地址
图示：
解析：
1.每个正方形代表一个结点、其上方的数字代表其在内存中的地址值。正方形的两层分别代表其数据内容以及用于指向下一个结点的指针。
2.如图，每个结点都存储着下个结点的地址，以此形成逻辑上的链状。
3.第一个正方形head代表头指针变量，用于存放链表中第一个结点的地址。
实现方式：链表用含指针的结构体实现。
例：
struct Node//声明结构体，用于模拟结点
{
char data;//用于存储数据，可以声明多个
struct Node *next;//用于存储下一个结点的地址
};
代码示例：
#include <stdio.h>
#include <stdlib.h>
/*这个程序用来测试简单单向链表的创建及使用*/
struct Student//使用结构体来模拟结点的结构
{
int num;
float score;
struct Student *next;//用于存储下一结点的地址
};
int main()
{
struct Student a,b,c,*head,*p;//a,b,c作为结点，head作为头指针变量，p用于链接各结点
/*为各结点赋值*/
a.num=31001,a.score=89.5;
b.num=31003,b.score=90;
c.num=31007,c.score=85;
/*将结点链接为链表*/
head=&a;//这一步十分重要！链表必须要有头指针变量
a.next=&b,b.next=&c;//中间的每个结点都存储着下一个结点的地址
c.next=NULL;//c作为最后一个结点，为其next指针赋值为NULL以表示链表已到尽头
/*使用链表（输出链表中的值）*/
p=head;//使p指向链表的头一个结点
do
{
printf("%d %.1f\n",p->num,p->score);
p=p->next;//核心代码，使p指向链表的下一个结点。这样下一次循环将直接读取到新结点的数据。
}
while(p!=NULL);//当p==NULL即链表已到尽头。则不需要继续循环
return 0;
}
结果：
解析：链表的长度可变，结点可自行设计、增加、删除。使用十分灵活。
注：大部分演示以单向链表为例，方便理解。
链表操作
基础
核心：
1.通过指针访问链表
2.利用动态分配空间建立动态链表
代码示例：
#include <stdio.h>
#include <stdlib.h>
/*这个程序用于演示结点控制基础*/
struct Student//结构体Student用于模拟链表结点
{
int num;
float score;
struct Student *next;
};
int main()
{
struct Student *p;//定义指针p用于操作链表结点
p=malloc(sizeof(struct Student));//利用malloc为结点动态分配空间
p->num=31001;//为链表结点添加数据
p->score=89.5;
printf("%d %.1f\n",p->num,p->score);//输出测试
free(p);//对于失去利用价值的结点，直接释放其内存空间
return 0;
}
结果：
解析：
1.对于链表的所有节点，定义指针并分配空间而非直接定义变量。避免因结点过多造成的代码繁杂和空间浪费
2.使用malloc动态分配空间和使用free释放无用结点是链表操作的关键，能保证对链表成员的高控制度。
创建及遍历链表：
代码示例：
#include <stdio.h>
#include <stdlib.h>
/*这个程序用来测试对链表的创建和遍历操作*/
typedef struct NODE//因为结构中需要定义结构体指针，所以即使使用了自定义类型，结构体的名称仍不能省略
{
int data;
struct NODE *next;//此处指针时指向结构体NODE的，切勿写成自定义类型Node
}Node;
Node *createLinkList(int);//用于创建链表
void traverse(Node*);//用于遍历并输出链表中的值的函数
int main()
{
Node *head;
int n=0;
printf("输入链表的结点数：");
scanf("%d",&n);
head=createLinkList(n);
printf("开始输出链表：\n");
traverse(head);
return 0;
}
Node *createLinkList(int n)//n代表链表的结点数
{
Node *h=NULL,*p,*last;//h表示链表头结点，last表示链表末结点
int d,i;
for(i=0;i<n;i++)
{
scanf("%d",&d);
p=(Node *)malloc(sizeof(Node));//创建一个结点
p->data=d;//为结点赋值
p->next=NULL;//初始化next
if(h==NULL)//如果链表无头结点
h=p;//使本次创建的结点成为链表头结点
else
last->next=p;//否则，使本次创建的结点和之前的末结点链接
last=p;//使本次创建的结点成为末结点
}
return h;//返回头结点的地址
}
void traverse(Node *h)
{
Node *p;
p=h;//p首先指向头结点
while(p!=NULL)
{
printf("%-5d",p->data);
p=p->next;//p指向下一个结点
}
printf("\n");
return;
}
结果：
解析：
1.createLinkList函数用于创建链表，实质是一个循环创建并链接结点的过程。其中h作为链表头指针变量其值一旦确定就不再改变，而last始终指向链表末结点。
2.traverse函数用于遍历链表，原理与基础部分的测试代码相同。需要注意的是，h作为链表头指针变量。是不应该改变其值的，否则容易造成链表结构混乱或结点丢失。
向链表中插入结点：
原理演示：
p指向r，要将q插入p和r之间
q->next=p->next;
p->next=q;
执行完毕，则链表变为p指向q指向r
代码示例：
#include <stdio.h>
#include <stdlib.h>
/*这个程序用于测试向链表中插入结点*/
/*通过逐个插入结点建立有序链表*/
typedef struct NODE
{
int data;
struct NODE *next;
} Node;
Node *insertNode(Node*,int);//用于插入结点
void traverse(Node*);//用于遍历并输出链表中的值的函数
int main()
{
int i,b[]={67,25,78,99,87};
Node *head=NULL;
for(i=0;i<5;i++)
head=insertNode(head,b[i]);
traverse(head);
return 0;
}
void traverse(Node *h)
{
Node *p;
p=h;//p首先指向头结点
while(p!=NULL)
{
printf("%-5d",p->data);
p=p->next;//p指向下一个结点
}
printf("\n");
return;
}
Node *insertNode(Node *h,int b)
{
Node *q1=h,*q2,*p;
p=(Node*)malloc(sizeof(Node));//生成新结点
p->data=b;
if(h==NULL)//如果当前链表为空，则p作为首结点
{
h=p;
p->next=NULL;
}
else if(p->data<h->data)//如果当前结点数值小于首结点数值,则p作为首结点
{
h=p;
p->next=q1;
}
else//否则，逐个比对，找到p结点应在位置，将其插入
{
/*循环改变q1指向的结点，直到找到p的位置或到达链表末尾*/
while(q1!=NULL&&p->data>=q1->data)
{
q2=q1;
q1=q1->next;
}
/*此时q2正好应当是p的前一结点，因此执行插入*/
p->next=q2->next;
q2->next=p;
}
return h;
}
结果：
解析：
1.通过逐个插入结点，建立有序单向链表。
2.通过操作q1而非直接操作h，保证链表头结点不混乱。
3.对于单向链表的插入，保存上一个结点的地址是很重要的（单向链表和数组不同，无法通过当前结点反推前一结点），因此上述代码中的q2必不可少。
在链表中删除结点：
原理演示：
p指向q指向r，要将q删除
p->next=q->next;
free(q);
执行完毕，则链表变为p指向r,且q不复存在
代码示例：
#include <stdio.h>
#include <stdlib.h>
/*这个程序用于测试向链表中插入结点*/
/*通过逐个插入结点建立有序链表*/
typedef struct NODE
{
int data;
struct NODE *next;
} Node;
Node *insertNode(Node*,int);//用于向链表中有序的插入结点
Node *deleteNode(Node*,int);//用于从有序链表中删除指定结点
void traverse(Node*);//用于遍历并输出链表中的值的函数
int main()
{
int i,b[]={67,25,78,99,87};
Node *head=NULL;
for(i=0;i<5;i++)
head=insertNode(head,b[i]);
traverse(head);
int num;
do
{
printf("please enter a num,enter 0000 to exit:");
scanf("%d",&num);
if(num==0000)
return 0;
head=deleteNode(head,num);
traverse(head);
}while(1);
return 0;
}
void traverse(Node *h)
{
Node *p;
p=h;//p首先指向头结点
while(p!=NULL)
{
printf("%-5d",p->data);
p=p->next;//p指向下一个结点
}
printf("\n");
return;
}
Node *insertNode(Node *h,int b)
{
Node *q1=h,*q2,*p;
p=(Node*)malloc(sizeof(Node));//生成新结点
p->data=b;
if(h==NULL)//如果当前链表为空，则p作为首结点
{
h=p;
p->next=NULL;
}
else if(p->data<h->data)//如果当前结点数值小于首结点数值,则p作为首结点
{
h=p;
p->next=q1;
}
else//否则，逐个比对，找到p结点应在位置，将其插入
{
/*循环改变q1指向的结点，直到找到p的位置或到达链表末尾*/
while(q1!=NULL&&p->data>=q1->data)
{
q2=q1;
q1=q1->next;
}
/*此时q2正好应当是p的前一结点，因此执行插入*/
p->next=q2->next;
q2->next=p;
}
return h;
}
Node *deleteNode(Node *h,int b)
{
Node *p,*q;
p=h;
if(h==NULL)//如果链表是空的
printf("List is null,delete fail.\n");
else
{
/*循环比对结点值，直到比对成功或链表遍历*/
while(b!=p->data&&p->next!=NULL)
{
q=p;
p=p->next;
}
if(b==p->data)//如果比对成功
{
if(p==h)//如果该结点是头结点
h=p->next;//使下一个结点成为头结点
else
q->next=p->next;//否则，删除p结点
free(p);//释放无用结点的内存空间，以避免空间的浪费。
}
else//如果比对失败，即链表遍历
printf("%d not found,delete fail.\n",b);
}
return h;
}
结果：
解析：删除节点所需要循序的原则和插入结点类似，确保头结点不随意改变以及保存当前结点的上一结点的地址。
链表应用
代码示例：
/*
猴子选大王
m个猴子围成一圈，
编号为1,2,3,.....,m
从第一个开始数数（1。。2。。。3。。4。。），
每数到第n个，该猴子就要离开此圈，
然后下一个猴子重新从1开始数.
这样依次下来，直到圈中只剩最后一只猴子，
则该猴子成为猴子大王。
*/
/*此问题实际上是“约瑟夫问题”的一种，*/
/*
此处用链表（循环单链表）来解决这个问题。
但应认识到这并不是此种问题的最优解
*/
#include <stdio.h>
#include <stdlib.h>
struct Monkey//定义结点
{
int num;
struct Monkey *next;
};
struct Monkey* create_circle(int,int);//创建循环单链表（猴子圈）
int vote(struct Monkey*,int,int);//选举猴王
int main()
{
int m,n,king;
struct Monkey *head;
printf("请输入猴子的总数m和猴子选举时数的最大数n，两数中间用空格隔开:\t");
scanf("%d %d",&m,&n);
if(n==1)//如果只有一只猴子，直接使他成为猴王。
king=m;
else
{
head=create_circle(m,n);
king=vote(head,m,n);
}
printf("猴王是%d\n",king);
return 0;
}
struct Monkey* create_circle(int m,int n)
{
int i;
struct Monkey *h,*p1,*p2;
p1=p2=(struct Monkey*)malloc(sizeof(struct Monkey));
h=p1;//第一个创建的结点作为首结点
h->num=1;
for(i=1;i<m;i++)
{
p1=(struct Monkey*)malloc(sizeof(struct Monkey));
p1->num=i+1;
p2->next=p1;//p2此时代表的是上一次创建的结点，而p1代表这一次创建的结点。
p2=p1;//使p2等于p1，这样下次循环时，p2又将刚好是p1的上一个结点。
}
p2->next=h;//此时，p2代表末结点。使得p2的下一个结点是首结点，就完成了一个环状的链表
return h;
}
int vote(struct Monkey* h,int m,int n)
{
int i,j,k;
struct Monkey *p1,*p2;
p1=h;
for(i=1;i<m;i++)//因为要把m猴子淘汰到只剩一只，所以每次循环淘汰一只猴子，需要m-1次循环
{
for(j=1;j<n-1;j++)//模拟从1数到n-1
p1=p1->next;//循环结束时，p1正好是数n-1的那只猴子。
p2=p1->next;//使p2指向p1的下一个结点，这样p2就成为了应该出圈的猴子
p1->next=p2->next;//使p2出圈
free(p2);//释放p2的内存空间，避免浪费
}
k=p1->num;//循环结束，最后剩下的p1就是猴王
free(p1);//既然选出了猴王，那么p1也就没用了，所以释放其内存空间
return k;
}
结果：
解析：
1.用循环单链表来表示一群猴子。模拟结点的结构体有两个成员，一个保存猴子的编号，一个作为指向下一个猴子的指针。
2.此处使用的是循环单链表，即末结点的指针并不为NULL，而是指向首结点。以此构成环形的链。
3.仍要强调：建立链表和操作链表的核心是：利用好上一个操作的结点的地址值。
链表拓展
树型链表的存储：
图示：
解析：
以上即树形链表，对于如1、2、3、5这样其下链接着其他结点的结点称为根结点。而另一些没有链接更多结点的结点称为叶结点。
原理：
建立结点数组，使得数组的每个元素都代表链表中的一个结点。
如果此结点为根节点，则使该结点的指针指向其下的一个结点（如果有多个结点，则一一指向）。
如果此结点为叶结点，则不连接到其他结点。
图示：
结点结构体：
struct Node
{
int index;
Node *next;
};
Node *header[11];
.....
二叉排序树
图例:
解析：
对于数列45、24、53、12、28、90。。首先将45作为首结点，
然后将24和45对比，24小于45，因此置于45左下。
然后将53和45对比，53大于45，因此置于45右下。
然后将12和45对比，12小于45，因45左下已有值，
所以将12和24对比，12小于24，因此置于24左下。
然后将28和45对比，28小于45，因45左下已有值，
所以将28和24对比，28大于24，因此置于24右下。
然后将90和45对比，90大于45，因45右下已有值，
所以将90和53对比，90大于53，因此置于53右下。
特性：
1.二叉树中每个结点左下的所有的数，必定小于它。而右下所有的数，必定大于它。
2.当在此二叉树中查找某数时，只要与一个数比对，便可缩减一半的数据规模（类比二分法）
结点结构体：
struct node
{
struct node *lchild;
type data;//type可为任何类型的数据，此处只是基本结构示例。
struct node *rchild;
};
搜索函数示例：
int search(node *p,type k)//type可为任何类型的数据，此处只是基本结构示例。
{
if(p==NULL)
return -1;
else if(k==p->data)
return k;//查找成功
else if(k<p->data)
return search(p->lchild,k);//使用递归实现向左下查找
else if(k<p->data)
return search(p->rchild,k)
}
倒排表（搜索引擎常用数据结构）
图示：
解析：
对于三个句子：
text1: I am you. text2: He is she. text3: She is he.
其中出现过的所有单词为：i,am,you,he,is,she
将之存放于数组中，并以指针指向其对应的结点。
每个结点代表该词某次出现的信息。
如am的第一个结点，text1;2;^;代表的就是am这次出现在text1中，在字符串的第二个位置，以及下一次出现的位置为空。
而he的第一个结点，text2;0;指向;代表的就是he这次出现在text2中，在字符串的第零个位置，以及指向下一次出现的位置的指针。
注：对于以上图例中的数组，可以看出其中的单词排列是有序的。因此在查找时可用二分查找等算法进一步加快检索速率。
结点结构体：
struct appear
{
string filename;
int start;
struct appear *next;
};
图例：
解析：
对于现实中的搜索引擎，常如上图所示，将单词使用哈希算法换算成一个哈希值，并以哈希值作为数组下标。
这样可以更进一步的提高检索速率。
图例：
解析：
对于现实中的搜索引擎，常如上图所示，将单词使用哈希算法换算成一个哈希值，并以哈希值作为数组下标。
这样可以更进一步的提高检索速率。