题目
十一、假设有一个循环链表的长度大于1，结点中数据的数据类型为DataType，且表中既无头结点也无头指针。已知s为指向链表中某结点的指针，要求写出：
（1）循环链表的类型定义；
struct Node{
DataType data;
struct Node * link;
};
（2）在该循环链表中，删除所有DataType值为X结点的算法。 （15分）
算法思路
算法思路：指针r指向s指针的下一个，检查r指向的结点的数据是否等于x。若等于删除，不等于指向下一个结点，直到指向s指针指向的结点。这时检查s指针指向的结点的数据是否等于x,若等于且有多个结点，则直接删除，若只有一个结点，删除后return NULL。
代码
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
struct Node{
int data;
struct Node * link;
};
struct Node * func(struct Node * s,int x)
{
struct Node * l;
struct Node * r=s->link;
while(r!=s)
{
if(r->data==x)//值为x的结点删除
{
l=r->link;
r->data=r->link->data;
r->link=r->link->link;
if(l==s)
{
s=s->link;//若删除的是s指向的结点，则需要让s指向下一个结点
}
free(l);
}
else
r=r->link;
}
if(r->data==x&&r->link!=r)
{
l=r->link;
r->data=r->link->data;
r->link=r->link->link;
free(l);
}
if(r->data==x&&r->link==r)
{
free(r);
return NULL;
}
return r;
}
void PutNode(struct Node * s)
{
struct Node * l=s->link;
if(s==NULL)
cout<<"s为空"<<endl;
else
while(l!=s)
{
cout<<l->data<<" ";
l=l->link;
}
cout<<l->data;
}
int main(int argc, char** argv) {
struct Node * s=(struct Node *)malloc(sizeof(struct Node));
s->data=3;
s->link=(struct Node *)malloc(sizeof(struct Node));
s->link->data=5;
s->link->link=(struct Node *)malloc(sizeof(struct Node));
s->link->link->data=7;
s->link->link->link=(struct Node *)malloc(sizeof(struct Node));
s->link->link->link->data=5;
s->link->link->link->link=s;
PutNode(s);
s=func(s,5);
cout<<endl;
PutNode(s);
return 0;
}
运行结果
实验用的链表，删除值为5的结点
第一行打印的是链表中的数值
第二行打印的是删除后的链表中的数值
