单向循环链表
单向循环链表是可循环的单链表，它与单链表的区别在于单向链表的最后一个元素的指针域为空，而单向循环链表的最后一个结点指针域 ，指向链表头结点，不再是为空。
单向循环链表的日常操作
1.代码习惯，先定义一下宏
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
//定义结点
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;
2.单向循环链表的初始化
区别： 与单链表初始化相比较，多了一步将首节点的next指向头结点也就是它本身。
3.单向循环链表的插入
两种情况:
判断是否第一次创建链表
YES->创建一个新结点,并使得新结点的next 指向自身; (L)->next = (L);
NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);
初始化方式一
Status CreateList(LinkList *L){
int item;
scanf("%d",&item);
LinkList temp = NULL;
LinkList target = NULL;
//如果输入的链表是空。则创建一个新的节点，使其next指针指向自己 (*head)->next=*head;
if(*L==NULL)
{
*L = (LinkList)malloc(sizeof(Node));
if(!L)exit(0);
(*L)->data=item;
(*L)->next=*L;
}
else
{
//输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
for (target = *L; target->next != *L; target = target->next);
temp=(LinkList)malloc(sizeof(Node));
if(!temp) return ERROR;
temp->data=item;
temp->next=*L; //新节点指向头节点
target->next=temp;//尾节点指向新节点
}
return OK;
}
初始化方式二设置一个指针，指向最后一个插入的结点
Status CreateList2(LinkList *L,int item){
LinkList temp = NULL;
LinkList target = NULL;
LinkList r = NULL;
//第一次创建
if(*L == NULL){
*L = (LinkList)malloc(sizeof(Node));
if(!*L) return ERROR;
(*L)->data = item;
(*L)->next = *L;
r = *L;//这一步是灵魂
}else{
temp = (LinkList)malloc(sizeof(Node));
if(!temp) return ERROR;
temp->data = item;
temp->next = *L;
r->next = temp;
r = temp;//这一步是灵魂
}
return OK;
}
4.单向循环链表的插入
如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
- 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
- 找到链表最后的结点_尾结点,
- 让新结点的next 执行头结点.
- 尾结点的next 指向新的头结点;
- 让头指针指向temp(临时的新结点)
LinkList temp ,target;
int i;
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
for (target = *L; target->next != *L; target = target->next);
temp->next = *L;
target->next = temp;
*L = temp;
如果插入的位置不是1
- 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
- 先找到插入的位置,如果超过链表长度,则自动插入队尾;
- 通过target找到要插入位置的前一个结点, 让target->next = temp;
- 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ;
LinkList temp ,target;
int i;
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
for ( i = 1,target = *L; target->next != *L && i != place - 1; target = target->next,i++) ;
temp->next = target->next;
target->next = temp;
5.循环链表删除元素
如果删除的是第一个位置
- 1.如果删除的只剩下首元结点了，那么直接将链表置空
- 2.如果链表的数据很多，但删除的是首元结点，先找到尾结点，使得尾结点next指向头结点的下一个结点，新节点作为头结点，释放原来的头结点。
- 3.如果删除的是其他结点，先找到删除结点target，使得target->next 指向下一个结点，释放需要删除的结点temp。
Status LinkListDelete1(LinkList *L,int place){
LinkList temp,target;
int i;
//temp 指向链表首元结点
temp = *L;
if (temp ==NULL) {
return ERROR;
}
if (place==1) {
//只剩下首元节点了
if (temp->next == *L) {
(*L) = NULL;
return OK;
}
for (target = *L; target->next != *L; target->next = target) ;
temp = *L;
(*L) = (*L)->next;
//尾结点重新指向新的头结点
target->next = *L;
free(temp);
}else{
//找到删除结点的结点
for(i=1,target = *L;target->next != *L && i != place -1;target = target->next,i++) ;
temp = target->next;
temp->next = temp->next;
free(temp);
}
}
6.单向循环链表的遍历
void show(LinkList p)
{
//如果链表是空
if(p == NULL){
printf("打印的链表为空!\n");
return;
}else{
LinkList temp;
temp = p;
do{
printf("%5d",temp->data);
temp = temp->next;
}while (temp != p);
printf("\n");
}
7.循环链表查找值注意：当尾结点指向头结点就要直接跳出循环
int findValue(LinkList L,int value){
int i = 1;
LinkList p;
p = L;
//寻找链表中的结点 data == value
while (p->data != value && p->next != L) {
i++;
p = p->next;
}
//当尾结点指向头结点就会直接跳出循环,所以要额外增加一次判断尾结点的data == value;
if (p->next == L && p->data != value) {
return -1;
}
return i;
}
网友评论