例题1：下述算法的功能是什么？

LinkNodeDemo(LinkListL)//L是无头结点的单链表

{

ListNode*P,*Q;

If (L&&L->next)

{

Q=L;L=L->next;P=L;

while ( P->next)P=P->next;

P->next=Q;Q->next=NULL;

}

returnL:

}

解：

该算法的功能为，将单链表L的最后一个结点移动到单链表的第一个元素结点的前面。

例题2：有一个单链表（不同结点的数据域植可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数。

解：本题是遍历通过该链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函数如下：

int count（head，x）

node *head；

ElemType x；

{

node *p；

int n=0；

p=head；

while （p！=NULL）

{

if（p->data==x）n++；

p=p->next；

}

return（n）；

}

例题3：已知一个单链表如图3.1所示，编写一个函数将该单链表复制一个拷贝。

图3.1一个单链表

解：本题的算法思想是依次查找该单链表（其头指针head1）中的每个结点，对每个结点复制一个新结点并链接到新的单链表（其头指针为head2）中。实现本题功能的函数如下：

void copy（head1，head2）

node *head1，*head2；

{

node *p，*q，*s；

head2=（node *）malloc（sizeof（node））；/*建立一个头结点*/

q=head2；p=head1；

while（p！= NULL）

{

s=（node *）malloc（sizeof（node））；/*复制一个新结点*/

s->data=p->data;

q->next=s；/*把s链接到q之后*/

q=s；

p=p->next;

}

q->next=NULL;/*将最后一个结点的next域置为NULL*/

p=head2;/*删除头结点*/

head2=head2->next;

free（p）；

}

例题4：有一个单链表，其结点的元素值以非递减有序排列，编写一个函数删除该单链表中多余的元素值相同的结点。

解：本题采用的算法是：从头到尾扫描该单链表，并作这样的操作：若当前结点的元素值与后续结点的元素值不相等，则指针后移，否则删除该后续结点，直到扫描所有的结点。实现本题功能的函数如下：

node *del（head）

node *head；

{

node *q；

if （head！= NULL）

{

/*当前结点的元素值与后续结点的元素值不相等，则指针后移，否则删除该后续结点*/

while（p->next!=NULL）

if（p->data!=p->next->data）p=p->next;

else

{

q=p->next;

p->next=q->next;

free（q）；

}

return（head）；

}

例题5：假设在长度大于1的循环单链表中，既无头结点也无头指针，p为指针向该链表中某个结点的指针，编写一个函数删除该结点的前驱结点。

解：本题利用循环单链表的特点，通过p指针可循环找到其前驱结点q及q的前驱结点r，然后将其删除。实现本题功能的函数如下：

node *del（p）

node *p；

{

node *q，*r；

q=p；/*查找p结点的前驱结点，用q指针指向*/

while（q->next!=p）q=q->next;

r=q;/*查找q结点的前驱结点，用r指针指向*/

while（r->next!=q）r=r->next;

r->next=p;/*删除q所指的结点*/

free（q）；

return（p）；

}

例题6：假设有一个循环双链表，其结点包含三个域：pre、data和next，其中data为数据域，next为指针域，其值为后续结点的地址，pre也为指针域，其初值为空（NULL），编写一个函数将此循环单链表改为循环双链表。

解：依题意，双链表的结构定义如下：

struct dlist

{

float data；

struct dlist *pre，*next；

}

假设该循环双链表的头指针为head。实现本题功能的函数如下：

struct dlist *trans（head）

struct dlist *head；

{

struct dlist *p，*q；

p=head->next;

q=head;

while（p！=head）/*依次从左向右通过每个结点，对每个结点置pre值*/

{

p->pre=q;

p=p->next;

q=q->next;

}

head->pre=p; /*此时p指向最后一个结点,将第一个结点的pre域指向最后一个结点*/

return（head）；

}