单向循环链表
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.创建
2种情况:① 第一次开始创建; ②已经创建,往里面新增数据
1. 判断是否第一次创建链表
YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);
NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);
创建方法1
Status CreateList(LinkList *L) {
intvalue =0;
printf("输入节点的值，输入0结束\n");
LinkListtemp =NULL;
LinkListtarget =NULL;
while(1) {
//输入要插入的数据
scanf("%d",&value);
if(value ==0) {
break;
}
//如果输入的链表是空。则创建一个新的节点，使其next指针指向自己 (*head)->next=*head;
if(*L ==NULL) {
*L = (LinkList)malloc(sizeof(Node));
if(!L) {
exit(0);
}else{
//给数据域赋值
(*L)->data= value;
//将指针域指向自己
(*L)->next= *L;
}
}else{
//输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
//找到尾结点
for(target = *L; target->next!= *L; target = target->next) {
//target先指向首元结点
//判断target->next是否指向首元结点（结束的标志）
//target不是尾结点，则target->next指向下一个结点
}
//找到尾结点后
temp = (LinkList)malloc(sizeof(Node));
//
temp->data= value;
//新结点的next指向首元结点
temp->next= *L;
//将target->next 指向新结点
target->next= temp;
}
}
returnOK;
}
创建方法2
Status CreateList2(LinkList *L) {
intvalue =0;
printf("输入节点的值，输入0结束\n");
LinkListtemp =NULL;
//记录尾结点
LinkListr =NULL;
while(1) {
//输入要插入的数据
scanf("%d",&value);
if(value ==0) {
break;
}
//如果输入的链表是空。则创建一个新的节点，使其next指针指向自己 (*head)->next=*head;
if(*L ==NULL) {
*L = (LinkList)malloc(sizeof(Node));
if(!L) {
exit(0);
}else{
//给数据域赋值
(*L)->data= value;
//将指针域指向自己
(*L)->next= *L;
//指向尾结点
r = *L;
}
}else{
//生成新结点
temp = (LinkList)malloc(sizeof(Node));
//
temp->data= value;
//新结点的next指向首元结点
temp->next= *L;
//将target->next 指向新结点
r->next= temp;
//记录尾结节
r = temp;
}
}
returnOK;
}
遍历
单向循环链表的遍历最好用do while,因为头结点就有值
void TraversalList(LinkList L){
//如果是空
if(L ==NULL) {
printf("打印的链表为空!\n");
return;
}else{
inti =1;
LinkListtemp;
temp = L;
do{
printf("链表第%d个值=%d\n",i,temp->data);
temp = temp->next;
i++;
}while(temp != L);//当temp是首元节点时结束循环
printf("链表遍历完成\n");
}
}
循环链表插入数据
StatusListInsert(LinkList*L,intindex,intvalue){
if(*L ==NULL|| index <1) {
returnERROR;
}
//1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
LinkListnewNode = (LinkList)malloc(sizeof(Node));
newNode->data= value;
//
LinkListtarget =NULL;
if(newNode ==NULL) {
returnERROR;
}
if(index ==1) {
//如果是插入首元结点
//找到尾结点
for(target = *L; target->next!= *L; target = target->next) {
}
//新结点作为首元结点
newNode->next= *L;
//尾结点指向新结点
target->next= newNode;
//首地址指向新结点
*L = newNode;
}else{
//找到目标结点的上一个结点
inti=0;
//先指向首元结点
target = *L;
for(i=1; i!= index-1; i++) {
if(target->next== *L) {
//找到尾结点,说明尾结点就是目标结点，结束
break;
}
//下一个结点
target = target->next;
}
//结点的next指向目标结点的next
newNode->next= target->next;
//目标结点的next指向新结点
target->next= newNode;
}
returnOK;
}
循环链表删除元素
StatusLinkListDelete(LinkList*L,intindex){
if(*L ==NULL|| index <=0) {
returnERROR;
}
//指向首元结点
LinkListtemp = *L;
LinkListtarget ;
if(index ==1) {
if((*L)->next== (*L)) {
free(temp);
*L =NULL;
returnOK;
}
//删除首元结点
//找到尾结点
for(target = *L; target->next!= *L; target = target->next) {
}
//首下一个结点改为首元结点
*L = (*L)->next;
//将尾结点指向新的首元结点
target->next= *L;
//释放删除的结点
free(temp);
}else{
//找到目标结点的上一个结点
inti=0;
target = *L;
for(i=1; i!=index-1; i++) {
if(target->next== *L) {
//找到尾结点,说明尾结点就是目标结点，结束
break;
}
target = target->next;
}
//如果找到目标结点是尾结点，则说明越界了
if(target->next== *L) {
printf("越界了\n");
returnERROR;
}
//记录要删除的结点
temp = target->next;
//目标结点指向要删除结点的下一个结点
target->next= temp->next;
free(temp);
}
returnOK;
}
循环链表的查询
ElemType findValue(LinkList L,int index){
if(L ==NULL|| index <=0) {
returnERROR;
}
intvalue =0;
//指向首元结点
LinkListtarget = L;
inti=0;
for(i=1; i != index; i++) {
if(target->next== L) {
//找到尾结点了，越界了
break;
}
target = target ->next;
}
value = target->data;
returnvalue;
}
最后是调用
intmain(intargc,constchar* argv[]) {
printf("单向循环链表\n");
LinkListhead;
intindex,value;
CreateList2(&head);
TraversalList(head);
printf("输入要插入的位置和数据用空格隔开1：");
scanf("%d %d",&index,&value);
ListInsert(&head,index,value);
TraversalList(head);
printf("输入要插入的位置和数据用空格隔开2：");
scanf("%d %d",&index,&value);
ListInsert(&head,index,value);
TraversalList(head);
printf("输入要插入的位置和数据用空格隔开3：");
scanf("%d %d",&index,&value);
ListInsert(&head,index,value);
TraversalList(head);
printf("输入要删除的位置：");
scanf("%d",&index);
LinkListDelete(&head,index);
TraversalList(head);
printf("输入要查找的位置1：");
scanf("%d",&index);
value =findValue(head, index);
printf("查询到的数据 = %d\n",value);
printf("输入要查找的位置2：");
scanf("%d",&index);
value =findValue(head, index);
printf("查询到的数据 = %d\n",value);
printf("输入要查找的位置3：");
scanf("%d",&index);
value =findValue(head, index);
printf("查询到的数据 = %d\n",value);
return0;
}
