最近补补数据结构，还是从最简单的线性链表开始。下面是线性链表的一些基本算法，留着以后翻案。下面的算法描述都是以字符串为数据元素。链表结构定义如下：
typedef struct node {
char data[100];
struct node *link;
}LNode, *LinkList;
1。建立一个线性链表，这是一个动态生成链结点并依次将它们链接到链表中的过程。设线性链表的第1个链结点的指针为list。当生成第一个链结点时，链表为空，直接将链结点送list即可。每取得一个数据元素，就为该数据元素生成一个链结点，将取得的数据元素的数据信息送给新结点的数据域的同时，将新结点的指针域置为NULL，然后将新结点插入到链表的末尾。下面的算法中是从一个名为 data.txt 的文件中按行读取字符串作为线性链表的数据元素。算法如下：
LinkList creatList() {
LinkList r, p, list = NULL;
char data[ 100 ];
FILE *f = fopen( "data.txt", "rb" );
while( fgets( data, 100, f ) )
{
p = ( LinkList )malloc( sizeof( LNode ) );
if( p != NULL ){
strcpy( p->data, data );
p->link = NULL;
if( list == NULL )
list = p;
else
r->link = p;
r = p;
}
}
fclose( f );
return list;
}
2。求线性链表的长度。线性链表的长度定义为线性链表中包含的结点的个数。因此需要设定一个活动的指针变量来遍历链表和一个计数器。首先让活动指针指向链表的第一个链结点，然后遍历链表，活动指针变量每指向一个链结点，计数器做一次计数，遍历结束后，计数器的内容就是链表的长度。算法如下：
//求线性链表的长度
int length( LinkList list ){
LinkList p = list;
int n = 0;
while( p != NULL ){
n++;
p = p->link; //指针p指向下一个链结点
}
return n; //返回链表长度
}
求线性链表的长度也可以采用递归来实现，算法如下：
int length( LinkList list ){
if( list != NULL ){
return 1 + length( list->link );
}
else
return 0;
}
3。测试线性链表是否为空，若链表为空，返回1，否则返回0。算法如下：
//测试链表是否为空，为空返回1，不为空返回0
int isEmpty( LinkList list ){
return list == NULL;
}
4。确定数据元素item在线性链表中的位置。从链表的第1个链结点开始，从前往后依次比较当前链结点的数据域是否与给定值item匹配，若链表中存在该数据元素，则返回查找结点的地址。否则，返回NULL。算法如下：
//确定元素item在线性链表中的位置
LinkList findItem( LinkList list, char *item ){
LinkList p = list;
while( p != NULL && strcmp( p->data, item ) != 0 ){
p = p->link;
}
return p;
}
5。在非空线性链表的第1个链结点前插入一个数据信息为item的链结点。实现步骤：从存储库中申请一个新的链结点P,将数据元素item置于新结点的数据域内，然后将第1个结点的指针list送到新结点P的指针域内，同时将新结点的地址P赋值给list，至此，新结点已经插入到链表的最前面，成为了新链表的第1个结点。算法如下：
//在非空线性链表的第一个链接点前插入一个数据信息为item的链接点
void insertLink1( LinkList *list, char *item ){
LinkList p = ( LinkList )malloc( sizeof( LNode ) );
if( p != NULL ){
strcpy( p->data, item );
p->link = *list;
*list = p;
}
}
6。在非空线性链表的末尾插入一个数据信息为item的链结点，设置一个指针变量r,先让r指向链表第一个链结点，然后反复执行动作r = r->link，直到r->link == NULL，此时r指向链表的末尾结点，然后将item送入新动态分配的结点的数据域的同时，将新结点的指针域置NULL,最后将新结点的地址送入 r 指向的链结点的指针域，到此完成插入操作。算法如下：
//在非空线性链表的末尾插入一个数据信息为item的链接点
void insertLink2( LinkList list, char *item ){
LinkList r, p;
r = list;
while( r->link != NULL )
r = r->link;
p = ( LinkList )malloc( sizeof( LNode ) );
if( p != NULL ){
strcpy( p->data, item );
p->link = NULL;
r->link = p;
}
}
7。在线性链表中由指针q指出的链结点后面插入一个数据信息为item的链结点，先从存储库中申请一个新的空结点P，将item送入新链结点的数据域，若原线性链表为空表，则新链表结点就是结果链表，此时只需把P的内容送给list即可，若原链表非空，先将q指向的链结点的指针域赋值给新链结点P的指针域，然后再将新链结点的地址P赋值给q结点的指针域即可。算法如下：
//在线性链表中由指针q指出的链接点后面插入一个数据信息为item的链接点
void insertLink3( LinkList *list, LinkList q, char *item ){
LinkList p = ( LinkList )malloc( sizeof( LNode ) );
if( p != NULL ){
strcpy( p->data, item );
if( *list == NULL ){
*list = p;
p->link = NULL;
}
else{
p->link = q->link;
q->link = p;
}
}
}
8。在线性链表中第i个链结点后面插入一个数据信息为item的链结点。这里的i不是结点的地址，只是一个序号。首先应该从第1个结点出发，找到第i个链结点，然后再将新结点插在其后，若插入成功，算法返回1，否则返回-1。算法如下：
int insertLink4( LinkList list, int i, char *item ){
LinkList p, q = list;
int j=1;
while( j < i && q != NULL ){
q = q->link;
j++;
} //寻找第i个结点
if( j != i || q == NULL ){
printf( "there is no i element in the list\n" );
return -1;
} //插入失败，返回-1
p = ( LinkList )malloc( sizeof( LNode ) );
if( p != NULL ){
strcpy( p->data, item );
p->link = q->link;
q->link = p; //将新链结点插在第i个链结点之后
return 1; //插入成功，返回1
}
}
9。在按值有序链接的线性链表中插入一个数据信息为item的链结点。假设有序链表为其链结点是按照数据域值的大小从小到大非递减链接的一个链表，则要求在有序链表中插入一个新的链结点以后仍然保持链表为有序链表。首先为被插入的数据元素申请一个新的链结点，然后从链表的第1个链结点开始顺序查找插入位置，在查找过程中需要保留当前链结点的直接前驱结点的位置，以便在插入新的链结点时使用。算法如下：
/*在按值有序的线性链表中插入一个数据信息为item的链接点并继续保持线性链表有序
在查找过程中需要保持当前结点的直接前驱结点的位置，以便插入新的链结点时使用*/
void insertLink5( LinkList *list, char *item ){
LinkList p, q, r;
p = ( LinkList )malloc( sizeof( LNode ) );
strcpy( p->data, item );
if( *list == NULL || strcmp( item, (*list)->data ) < 0 ){ //若链表为空或者item小于第一个链接点
p->link = *list; //将新的链接点插在链表最前面
*list = p; //list指向被插入的新结点
}
q = *list;
while( q != NULL && strcmp( item, q->data ) >= 0 ){ //寻找新的插入位置
r = q;
q = q->link;
}
p->link = r->link;
r->link = p;
}
10。从非空线性链表中删除q所指的链结点。
这分两种情况：第一情况是，若被删除结点是链表的第一个链结点，这时只需将第二个链结点的地址赋值给list，使得list指向链表的第二个链结点，然后释放被删除结点即可。
第二种情况是，若被删除结点不是链表的第一个链结点，这时需要找到q所指链结点的直接前驱结点r以便达到删除链结点q的目的，只要首先将r指向链表的第1个链结点，然后反复执行r = r->link直到 r->link等于q，算法如下：
/*从非空线性链表中删除q所指的链结点*/
void deleteElement( LinkList *list, LinkList q ){
LinkList r;
if( q == *list ){
*list = ( *list )->link;
free( q );
}
else{
r = *list;
while( r->link != q && r->link != NULL){ //寻找q的直接前驱结点，注意r->link != NULL的条件
r = r->link;
}
if( r->link != NULL ){
r->link = q->link; //删除q所指的链结点
free( q ); //释放被删除结点的空间
}
}
}
11。销毁一个线性链表。
所谓销毁一个线性链表，是指将链表中所有链结点删除，并释放占用的存储空间使其成为一个空表。算法如下：
//删除一个线性链表
void deleteList( LinkList *list ){
LinkList p;
p = *list;
while( p != NULL ){
*list = p->link; //保存下一个链结点的位置
free( p ); //删除并释放当前链结点
p = *list; //下一个链结点成为当前链结点
}
}
12。删除线性链表中数据域值为item的所有链结点。先从链表 第2个链结点开始，从前往后依次判断链表中所有链结点是否满足条件，若某个链结点满足条件，则删除该链结点，否则不做操作。最后再回过头来判断链表中第1个链结点是否满足条件，若满足条件则删除。算法如下：
/*删除线性链表中数据域为item的所有链结点，先从第二个链结点开始判断，遍历整个链表，然后判断
第一个链结点是否满足条件*/
void deleteElements( LinkList *list, char *item ){
LinkList p, q = *list;
p = ( *list )->link;
while( p != NULL ){
if( strcmp( p->data, item ) == 0 ){ //p指向的链结点满足条件
q->link = p->link; //删除p指向的链结点
free( p ); //释放被删除结点的存储空间
p = q->link; //p指向被删除结点的下一结点
}
else{
q = p; //保存p的直接前驱结点信息
p = p->link; //使p指向下一链结点
}
}
if( strcmp(( *list )->data, item) ==0 ){ //判断第一个链结点是否满足条件
q = *list;
*list = ( *list )->link;
free( q );
}
}
13。逆转一个线性链表。
所谓线性链表的逆转操作是指在不增加新的链结点空间的前提下，通过改变链结点指针内地址的方式来依次改变数据元素的逻辑关系，即使得线性表(a1,a2,a3,...,an-1,an)变成(an,an-1,...a3,a2,a1),算法如下：
/*逆转一个线性链表*/
void invert( LinkList *list ){
LinkList p, q, r;
q = NULL;
p = *list;
while( p != NULL ){ //p为遍历链表的指针，始终走在最前端,p!=NULL判断是否到达链表末尾
r = q; //r用来存原始链表的最左边的链结点,即保存待逆转结点的直接前驱结点
q = p; //q用来存当前正在逆向的链结点
p = p->link; //移动活动指针使其指向下一结点
q->link = r; //执行逆转操作
}
*list = q; //将链表末尾该为链表的头部
}
14。将两个非空的线性链表连接成一个线性链表。设两个线性链表的第一个链结点的指针分别为lista和listb。先找到第一个链表末尾结点的位置，然后将第二个链表的第1个链结点的地址送其指针域即可。算法如下：
/*将两个非空线性链表连接成一个线性链表*/
void connect( LinkList lista, LinkList listb ){
LinkList p;
for( p = lista; p->link != NULL; p = p->link ); //寻找第1个链表末尾结点的位置
p->link = listb; //将第二个链表链接到第一个链表的末尾
}
15。将两个按值有序链接的非空线性链表合并为一个按值有序链接的线性链表。设lista和listb分别为两个有序链表的第1个链结点的指针。将这两个有序链表合并为一个有序链表，并设合并后的链表的第1个链结点指针为listc.这里需要设置3个指针p, q, r,其中，p和q分别指向链表lista和链表listb当前待比较插入的链结点，r指向链表listc中当前最后那个链结点。 在初始时，让listc指向lista和listb所指的链结点中值小的那一个链结点。然后不断地比较p与q所指的链结点的数据域值，若p->data
<= q->data，则将p所指的链结点链接到r所指的链结点之后，否则将q所指的链结点链接到r所指的链结点之后。当其中的一个链表为空时，只需将另一个链表中剩余的链结点都依次链接到r所指的链结点之后即可。算法如下：
/*将两个按值有序链接的非空线性链表合并为一个按值有序链接的线性链表*/
LinkList mergeList( LinkList lista, LinkList listb ){
LinkList listc, p = lista, q = listb, r;
if( strcmp( lista->data, listb->data ) <= 0 ){
listc = lista;
r = lista;
p = lista->link;
}
else{
listc = listb;
r = listb;
q = listb->link;
} //listc指向lista和listb中所指结点中值的小者，r指针指向listc中元素，用于生成链表
while( p != NULL && q != NULL ){
if( strcmp( p->data, q->data ) <= 0 ){
r->link = p;
r = p;
p = p->link;
}
else{
r->link = q;
r = q;
q = q->link;
}
}
r->link = ( p == NULL ) ? q : p; //插入剩余链结点
return listc;
}
16。复制一个线性链表。该操作的含义是，已知一个线性链表，要产生一个与已知线性链表完全等价的另外一个线性链表，这里假设已知线性由lista指出，经复制后产生的线性链表由listb指出。可将该操作定义为一个递归算法:
1， 若lista为空，则返回空指针NULL
2, 若lista非空，则复制lista所指的链结点，并将该链结点的指针赋予listb,然后复制该链结点的直接后继结点，并将该直接后继结点的指针赋予listb->link，最后返回新复制的线性链表的第1个链结点指针listb.
算法描述如下：
/*复制一个线性链表*/
LinkList copyList( LinkList lista ){
LinkList listb;
if( lista == NULL ){
return NULL;
}
else{
listb = ( LinkList )malloc( sizeof( LNode ) );
strcpy( listb->data, lista->data );
listb->link = copyList( lista->link );
}
return listb;
}
17。为了调试基本算法的实现，需要打印链表的信息。算法如下：
void printlist(LinkList p) {
LinkList r = p;
if( r == NULL ){
printf("there is no element in the list\n");
}
else{
while( r->link != NULL ){
printf( "%s", r->data );
r = r->link;
}
}
printf( "%s", r->data );
}