单向循环链表的尾结点的指针域必须指向链表的首结点的地址，初始化时头节点指向头节点本身，链表为空时也是。
1.节点结构体
typedef int DataType_t;
typedef struct Node{DataType_t data;struct Node* next;
}Node_t;
2.创建单循环链表
- 新建一个头节点用于管理链表
Node_t* CreateCrcList()
{Node_t* head = (Node_t*)malloc(sizeof(Node_t));if(head == NULL){printf("内存分配失败\n");exit(-1);}head->next = head; // 环形链表，头节点的next指向自己return head;
}
- 新建一个节点
Node_t* CreateNode(DataType_t value)
{Node_t* newNode = (Node_t*)malloc(sizeof(Node_t));if(newNode == NULL){printf("内存分配失败\n");exit(-1);}newNode->data = value;newNode->next = NULL;return newNode;
}
3.向链表插入新节点
- 头插
bool AddNodeAtHead(Node_t* head, DataType_t value)
{Node_t* newNode = CreateNode(value);if(newNode == NULL){return false;}if(head->next == head){ // 链表为空head->next = newNode;newNode->next = newNode;return true;}Node_t* tail = head->next; //需找到尾节点while(tail->next != head->next){tail = tail->next;}newNode->next = head->next;head->next = newNode;tail->next = newNode; //尾节点指向新的节点return true;
}
- 尾插
bool AddNodeAtTail(Node_t* head, DataType_t value)
{Node_t* newNode = CreateNode(value);if(newNode == NULL){return false;}if(head->next == head){ // 链表为空head->next = newNode;newNode->next = newNode;return true;}Node_t* tail = head->next; //遍历找到尾节点while(tail->next != head->next){ tail = tail->next;}tail->next = newNode;newNode->next = head->next;return true;
}
- 指定位置插入
bool InsertNodeAtPosition(Node_t* head, int position, DataType_t value)
{if(position < 1){ //首结点开始算1printf("position should be greater than 1");return false;}Node_t* newNode = CreateNode(value);if(newNode == NULL){return false;}if(position == 1){if(head->next == head){ //链表为空head->next = newNode;newNode->next = newNode;return true;}else{Node_t* tail = head->next;while(tail->next != head->next) tail = tail->next;newNode->next = head->next;head->next = newNode;tail->next = newNode;return true;}}Node_t* current = head; //找第position节点的前驱for(int i=1;i<position;i++){ current = current->next; //链表为空的情况也考虑上if((current==head->next && i!=1) || current == head){printf("插入位置超出链表长度\n");free(newNode);return false;} }newNode->next = current->next;current->next = newNode;return true;
}
4.删除链表节点
- 头删
bool DeleteHeadNode(Node_t* head)
{if(head->next == head){ // 链表为空printf("链表为空，无法删除节点\n");return false;}Node_t* temp = head->next;if(head->next->next == temp){ // 链表只有一个节点head->next = head;free(temp);return true;}Node_t* tail = head->next; // 遍历找到尾节点while(tail->next != head->next){ tail = tail->next;}head->next = temp->next;tail->next = head->next;free(temp);return true;
}
- 尾删
bool DeleteTailNode(Node_t* head)
{if(head->next == head){ // 链表为空printf("链表为空，无法删除节点\n");return false;}Node_t* tail = head; //找到倒数第二个节点while(tail->next->next != head->next){ tail = tail->next;}Node_t* temp = tail->next;if(temp == head->next){ // 链表只有一个节点head->next = head;free(temp);return true;}tail->next = head->next;free(temp);return true;
}
- 删除指定值的节点
bool DeleteNodeByValue(Node_t* head, DataType_t value)
{if(head->next == head){ //链表为空printf("链表为空，无法删除节点\n");return false;}if(head->next->data == value){ //首节点即为要删除的节点且包含只有一个节点的情况DeleteHeadNode(head); return true;}Node_t* current = head->next; //遍历到current->next值为valuewhile(current->next != head->next && current->next->data != value){current = current->next;}if(current->next == head->next){ //尾节点为value的情况循环里已遍历 printf("未找到值为%d的节点\n", value);return false;}Node_t* temp = current->next;current->next = temp->next;free(temp);return true;
}
5.遍历输出链表
bool PrintCrcList(Node_t* head)
{if(head->next == head){ // 链表为空printf("链表为空\n");return false;}Node_t* current = head;do{current = current->next; printf("%d -> ", current->data); }while(current->next != head->next);printf("NULL\n");return true;
}