#include
#include
#include

typedef int LDataType;
typedef struct Linklist{
LDataType data;
struct Linklist *next;
}Linklist,*pLinklist;

pLinklist BuyNewNode(LDataType data); //动态生成新结点
void InitLinklist(pLinklist *pL); //初始化单链表
void PushBackLinklist(pLinklist *pL,LDataType data); //尾插
void PushFrontLinklist(pLinklist *pL,LDataType data); //头插
void PopBackLinklist(pLinklist* pL); //尾删
void PopFrontLinklist(pLinklist *pL); //头删
void PrintLinklist(Linklist *pL); //打印单链表
pLinklist FindLinklist(pLinklist *pL,LDataType data); //查找指定元素，返回元素位置
//void InsertLinklist(pLinklist *pL,pLinklist p,LDataType data); //指定位置插入
void RemoveLinklist(pLinklist* pL,LDataType data); //删除第一个指定元素
void RemoveAllLinklist(pLinklist *pL,LDataType data); //删除所有指定元素
int IsEmptyLinklist(pLinklist pL); //判断链表是否为空
void DestoryLinklist(pLinklist *pL); //销毁单链表

int main(void){
Linklist *first = NULL;
InitLinklist(&first);
int people_num = 10;
int each = 3;
int return_num = 0;
for (int i=0;i<10;i++){ PushBackLinklist(&first,i+1); } int i = 1; Linklist *another = first; Linklist *pre; PrintLinklist(first); puts(" "); while(1){ if(another->next == first && first->next == another && first == another){
PrintLinklist(first);
break;
}
if(i%3 == 0){
pre = another->next;
RemoveLinklist(&first,another->data);
i++;
another = pre;
PrintLinklist(first);
puts(" ");
}else{
another = another->next;
i++;
}

}

// Linklist *first = NULL;
// InitLinklist(&first);
// for (int i=0;i<10;i++){
// PushBackLinklist(&first,i+1);
// }
// PrintLinklist(first);
// puts(" ");
// RemoveLinklist(&first,7);
// PrintLinklist(first);
}

//循环链表与开辟内存区域无关
pLinklist BuyNewNode(LDataType data){
pLinklist NewNode = (pLinklist)malloc(sizeof(Linklist));
if (NewNode == NULL){
printf("动态开辟内存空间失败\n");
return NULL;
}
NewNode->data = data;
NewNode->next = NULL;
return NewNode;
}
void InitLinklist(pLinklist *pL){
assert(pL != NULL); //初始化操作
(*pL) = NULL;
}
void PushBackLinklist(pLinklist *pL,LDataType data){
//主要就是从尾部插入的元素应该要指向头指针
assert(pL != NULL); //尾插一个数据域为data的结点
pLinklist NewNode = BuyNewNode(data);
if(*pL == NULL){
*pL = NewNode;
NewNode->next = *pL;
return ;
}
pLinklist cur = *pL;
while(cur->next != *pL){
cur = cur->next;
}
NewNode->next = cur->next;
cur->next = NewNode;
}
void PushFrontLinklist(pLinklist *pL,LDataType data){
assert(pL != NULL); //头插一个数据域为data的结点
pLinklist NewNode = BuyNewNode(data);
if(*pL == NULL){
*pL = NewNode;
NewNode->next = *pL;
return ;
}
NewNode->next = *pL;
*pL = NewNode;
pLinklist pre = NewNode->next;
while(pre->next != NewNode->next){
pre = pre->next;
}
pre->next = *pL;
}
int IsEmptyLinklist(pLinklist pL){
return (pL == NULL); //判断无头单链表是否为空
}
void PopBackLinklist(pLinklist *pL){
assert(pL != NULL); //尾删
if(IsEmptyLinklist(*pL)){
puts("链表为空，删除失败");
return ;
}
pLinklist cur = *pL;
pLinklist pre;
if(cur->next == *pL){
//只有一个结点
*pL = NULL;
free(cur);
cur = NULL;
return ;
}
while(cur->next != *pL){
pre = cur;
cur = cur->next;
}
pre->next = *pL;
free(cur);
cur = NULL;
}
void PopFrontLinklist(pLinklist *pL){
assert(pL != NULL); //头删，既是删除第一个结点
if(*pL == NULL){
printf(" 链表为空，删除失败");
return ;
}
pLinklist cur = *pL;
if(cur->next == *pL){
*pL = NULL;
free(cur);
cur = NULL;
return ;
}
*pL = cur->next;
free(cur);
cur = NULL;
}
pLinklist FindLinklist(pLinklist *pL,LDataType data){
assert( pL != NULL); //找到第一个数据为data的结点
pLinklist cur = *pL;

while(cur->next != \*pL){  
    if (cur->data == data){  
        return cur;  
    }  
    cur = cur->next;  
}  
if(cur->data == data){  
    return cur;  
}

return NULL;  

}
//void InsertLinklist(pLinklist *pL,pLinklist p,LDataType data){
// assert(pL != NULL); //xiangp结点之前插入一个数据为data的元素
// pLinklist NewNode = BuyNewNode(data);
// pLinklist cur = *pL;
// while(cur->next != p){
// cur = cur->next;
// }
// NewNode->next = p;
// cur->next = NewNode;
//}
void RemoveLinklist(pLinklist *pL,LDataType data){
assert(pL != NULL); //删除第一个数据域为data的结点
pLinklist cur = NULL;
pLinklist p = *pL;
pLinklist pre = NULL;
cur = FindLinklist(pL,data);
if (cur == NULL){
printf("未找到要删除的元素");
return ;
}
if (*pL == cur){
//位于第一个结点
// *pL = cur->next;
// free(cur);
// cur = NULL;
// return ;
pLinklist each_node = *pL;
while(each_node->next != *pL){
each_node = each_node->next;
}
each_node->next = (*pL)->next;
*pL = (*pL)->next;
free(cur);
cur = NULL;
return ;
}
while(p != cur){
pre = p;
p = p->next;
}
pre->next = cur->next;
free(cur);
cur = NULL;
}
void RemoveAllLinklist(pLinklist *pL,LDataType data){
assert(pL != NULL); //删除每一个数据域都是data的结点
pLinklist cur = NULL;
pLinklist p = *pL;
pLinklist pre = *pL;
while(p->next != *pL){
if (p->data == data && (*pL) == p){
//第一个结点是
pLinklist each_node = *pL;
while(each_node->next != *pL){
each_node = each_node->next;
}
each_node->next = (*pL)->next;
pre = p;
p = p->next;
*pL = p;
free(pre);
pre = NULL;

    }  
    else if(p->data == data){  
        //后续结点是  
        cur = p;  
        p = p->next;  
        pre->next = p;  
        free(cur);  
        cur = NULL;  
    }  
    else{  
        //此结点不是  
        pre = p;  
        p = p->next;  
    }  
}  

}
void PrintLinklist(Linklist *pL){
pLinklist cur = pL; //打印链表
if(cur->next == pL){
printf("%d--->",cur->data);
}else{
while(cur->next != pL){
printf("%d--->",cur->data);
cur = cur->next;
}
printf("%d--->",cur->data);
}
printf("头");

}
void DestoryLinklist(pLinklist *pL){
assert(pL != NULL); //摧毁链表
pLinklist cur = *pL;
pLinklist pre = NULL;
if (*pL == NULL){
printf("链表为空");
return ;
}
if (cur->next = *pL){
*pL = NULL;
free(cur);
cur = NULL;
return ;
}
while(cur->next != *pL){
pre = cur;
cur = cur->next;
free(pre);
pre = NULL;
}
}

这个代码是我在单链表的基础上改的，顺便实现了一下一个Josephus算法。其他的值是可以输入的。

在写这个代码的时候唯一难一点的就是头插，头删这两个操作。

头插：首先要判断是否为空，如果为空的话直接插入，然后再指向自己或者指向*pL就行了；但是如果有元素的话，头插就不是那么简单了，我们可以看一下下面的图，很明显，我们需要将新的结点的link域指向*pL，然后将*pL指向新的结点，这还没有完！！ 然后现在的链表并不是我们想要的一个循环链表，所以我们要找到最后一个结点再让他指向新的结点。

头删：我感觉这个和上面头删是一样的，上面的只要掌握了，自然也就会头部删除了。先判断是否为空……