-
自己实现单向循环链表的功能
-
整理思维导图
-
复习前面顺序表和链表的代码，重写链表逆置函数
1.实现单向循环链表的功能
loop_link_list.h文件
#ifndef __LOOP_LINK_LIST__
#define __LOOP_LINK_LIST__
#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct loop_list
{union{datatype data;int len;};struct loop_list *next;}loop_list,*loop_p;loop_p creat_head();//创建头结点
loop_p creat_node(datatype data);//创建新节点
void insert_head(loop_p H,datatype data);//头插
void out_put(loop_p H);//输出链表(两次循环)
int loop_empty(loop_p H);//判空
void del_tail(loop_p H);//尾删
void insert_pos(loop_p H,int pos,datatype data);//按位置插入
void del_pos(loop_p H,int pos);//按位置删除#endif
loop_link_list.c文件
#include "loop_link_list.h"
loop_p creat_head()
{loop_p L = (loop_p)malloc(sizeof(loop_list));if(L==NULL){printf("空间申请失败\n");return NULL;}L->len = 0;L->next = L;return L;
}loop_p creat_node(datatype data)
{loop_p new = (loop_p)malloc(sizeof(loop_list));if(new==NULL){printf("空间申请失败\n");return NULL;}new->data = data;return new;}
//判空
int loop_empty(loop_p H)
{if(H==NULL){printf("入参失败，请检查\n");return -1;}return H->len==0?1:0;}//头插
void insert_head(loop_p H,datatype data)
{if(H==NULL){printf("入参失败，请检查\n");return;}loop_p new = creat_node(data);new->next = H->next;H->next = new;H->len++;
}//按位置插入
void insert_pos(loop_p H,int pos,datatype data)
{if(H==NULL){printf("入参失败，请检查\n");return;}if(pos>H->len||pos<=0){printf("输入位置不合理\n");return;}loop_p p = H;for(int i=0;i<pos-1;i++){p = p->next;}loop_p new = creat_node(data);new->next = p->next;p->next = new;H->len++;}
//输出（看现象）
void out_put(loop_p H)
{if(H==NULL){printf("入参失败，请检查\n");return;}loop_p p = H->next;for(int i=1;i<=2;i++,p=p->next)//循环两次；{while(p!=H){printf("%d->",p->data);p = p->next; }} putchar(10);}
//尾删
void del_tail(loop_p H)
{if(H==NULL){printf("入参失败，请检查\n");return;}if(loop_empty(H)){printf("列表为空，无法删除\n");}loop_p p = H;while(p->next->next != H){p = p->next;}loop_p del = p->next;p->next = H;free(del);H->len--;
}//按位置删除
void del_pos(loop_p H,int pos)
{if(H==NULL){printf("入参失败，请检查\n");return;}if(pos>H->len||pos<=0){printf("输入位置不合理\n");return;}loop_p p = H;for(int i=0;i<pos-1;i++){p = p->next;}loop_p del = p->next;p->next = p->next->next;free(del);H->len--;}
main.c文件
#include "loop_link_list.h"
int main(int argc, const char *argv[])
{loop_p L = creat_head();insert_head(L,5);insert_head(L,4);insert_head(L,3);insert_head(L,2);del_tail(L);del_tail(L);insert_pos(L,2,30);del_pos(L,3);out_put(L); return 0;
}
2.重写链表逆置函数
//单链表的逆置
void over_turn(link_p H)
{link_p p = H->next->next;//保存第二个结点(从第二个开始头插)link_p q = p->next;//保存要插入结点的下一个结点的地址H->next->next = NULL;while(p!=NULL){p->next = H->next;H->next = p;p = q;if(q!=NULL){q=q->next;}}
}
