#include <stdio.h>
#include <stdlib.h>
typedef int dataType;
typedef struct linkNode
{
dataType data;
struct linkNode *next;
}node,*linkList;
// 1.初始化不带头结点的循环单链表
void init(linkList *head)
{
*head = NULL;
}
// 2.获取循环单链表的尾结点
node *rear(linkList head)
{
node *p = head;
while (p)
{
if(p->next == head)
break;
p = p->next;
}
return p;
}
// 3.输出循环单链表各结点的值
void display(linkList head)
{
node *p = head;
if(!p)
{
printf("循环单链表为空!\n");
return;
}
while (p->next != head)
{
printf("%d ",p->data);
p = p->next;
}
printf("%d\n",p->data);
}
// 4.查找值为x的结点
node* findX(linkList head, dataType x)
{
node *p = head;
if(!p)
{
printf("循环单链表为空!\n");
return head;
}
while (p->next != head)
{
if(p->data == x)
return p;
p = p->next;
}
if(p->data == x)
return p;
else return NULL;
}
// 5.查找第i个结点
node *find(linkList head, int i)
{
node *p = head;
if(i < 1)
{
printf("索引非法!\n");
return NULL;
}
if(!p)
{
printf("循环单链表为空!\n");
return head;
}
int j = 1;
while (p->next != head && i != j)
{
p = p->next;
j++;
}
if(i == j)
return p;
return NULL;
}
// 6.循环单链表的尾部插入结点
void rearInsert(linkList *head, dataType x)
{
node *p = *head,*q;
q = (node*) malloc(sizeof(node));
q->data = x;
if(!p)
{
q->next = q;
*head = q;
return;
}
p = rear(*head);
p->next = q;
q->next = *head;
}
// 7.在循环单链表的第i个位置后插入元素x
void insert(linkList *head, int i, dataType x)
{
if(i < 0)
{
printf("非法的插入位置,无法插入!\n");
return;
}
node *p = *head,*q,*r;
q = (node*) malloc(sizeof(node));
q->data = x;
if(i == 0) // 当要在链表最前方插入时
{
if(!p) // 链表为空时
{
*head = q;
(*head)->next = *head;
return;
} // 链表非空时
r = rear(*head); // 找到尾结点
q->next = *head;
r->next = q;
*head = q;
return;
}
p = find(*head,i); // 其他位置插入则需要找到插入位置
if(!p)
printf("非法的位置,无法插入!\n");
else
{
if(p->next == (*head)) // 如果在尾结点后插入
{
p->next = q;
q->next = *head;
return;
}
q->next = p->next; // 中间的位置插入
p->next = q;
}
}
// 6.删除循环单链表中值为x的元素
void del(linkList *head, dataType x)
{
node *p = *head,*q;
if(!p)
{
printf("链表为空,无法删除!\n");
return;
}
p = findX(p,x);
if(!p)
{
printf("未找到这样的结点,无法删除!\n");
return;
}
if((*head)->next == *head) // 只有一个结点时
{
free(p);
*head = NULL;
return;
}
if(p->next == *head) // 如果是删除最后一个结点
{
if(p == (*head)->next) // 只有两个结点时
{
(*head)->next = *head;
free(p);
} else // 多于两个结点时
{
p->data = p->next->data;
q = p->next;
p->next = p->next->next;
*head = p;
free(q);
return;
}
} else
{
p->data = p->next->data; // 中间结点的删除
q = p->next;
p->next = p->next->next;
free(q);
}
}
int main()
{
linkList list; // 声明循环单链表
init(&list); // 初始化空的不带头结点的循环单链表
display(list); // 输出单链表
for (int i = 1; i <= 5; i++)
rearInsert(&list,i);
display(list);
int i = 5;
node *n = find(list,i); // 查找第i个元素
if(n)
printf("链表的第%d个元素是%d\n",i,n->data);
else
printf("链表访问越界!\n");
dataType x = 6;
printf("在第%d个位置后面插入元素%d\n",i,x);
insert(&list,i,x);
display(list);
printf("删除一个值为%d的元素\n",x);
del(&list,x);
display(list);
return 0;
}
版权属于:
lixiangrong
作品采用:
《
署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)
》许可协议授权
评论 (0)