外贸高端建站,企业管理软件erp,蛋糕网站模板,个人卖货入驻什么平台双向循环链表是一种较为特殊的链表#xff0c;也是一种常见的数据结构#xff0c;其头尾相连#xff0c;各节点之间可互相访问#xff0c;在单链表中#xff0c;只能依次向后访问#xff0c;无法访问上一个节点#xff0c;而双链表可以依次向下访问也可向上访问。
链表…双向循环链表是一种较为特殊的链表也是一种常见的数据结构其头尾相连各节点之间可互相访问在单链表中只能依次向后访问无法访问上一个节点而双链表可以依次向下访问也可向上访问。
链表形式 双链表有很多节点形象的依次连接在一起每个节点都由一个数据域和两个指针域构成尾指针存放着下一个节点的地址头指针存放着上一个节点的地址故而形象的使各个节点依次相连。
插入一个节点 在1、3节点之间插入节点21节点尾指针原本指向3节点改变其指向使之指向2节点2节点的头指针便指向1节点同理改变3节点的头指针指向使之指向2节点2节点的尾指针指向3节点。
删除一个节点 例如删除2节点只需将原3现2节点节点的地址赋给1节点的尾指针中3节点的头指针指向1再将原2即删除的节点节点的指针域释放掉即可
头插
循环双链表的链表头一般没有数据且一般保持这个位置不动所以访问数据是从第二个节点开始如果在链表头后一直插入数据则第二个节点一直都是新数据所以其实是对双链表进行的是前插操作。
尾插
如果在链表头插入新数据那么出现在链表头前面的都是新数据所以和插在链表尾是一个道理因为双向循环链表是首尾相连的。
具体代码如下
#includestdio.h
#includestdlib.h
#includestring.h typedef struct ListNode
{struct ListNode *front;int data;struct ListNode* next;
}ListNode;typedef struct List
{ListNode *head;
}List;void init(List* plist)//初始化
{//分配空间plist-head (ListNode*)malloc(sizeof(ListNode));//让头指针和尾指针都指向自己plist-head-front plist-head;plist-head-next plist-head;
}int data_num(List* plist)//检查链表节点个数
{ListNode* tem;int i 0;for (tem plist-head-next; tem ! plist-head; tem tem-next){i;}return i;//返回链表节点个数
}void insert_front(ListNode* plist, intdata) //链表头前插
{//分配空间ListNode* cur (ListNode*)malloc(sizeof(ListNode));//记录链表头尾指针的内容,存放的是一个节点的地址即tem临时充当这个节点ListNode* tem plist-next;cur-data data;plist-next cur;
//使链表头的尾指针指向新插进来的节点cur-front plist;//新插进来的节点的头指针指向链表头tem-front cur; //使tem节点的头指针指向新插进来的节点cur-next tem; //新插进来的尾指针指向tem} void forntinsert_list(List* plist, int data) //前插入一个节点
{insert_front(plist-head,data);
}void insert_after(ListNode* plist, intdata) //链表头后插
{ListNode* cur (ListNode*)malloc(sizeof(ListNode));ListNode* tem plist-front; cur-data data;plist-front cur; //使链表头的头指针指向新插进来的节点cur-next plist; //新插进来的节点的尾指针指向链表头tem-next cur; //使tem节点的尾指针指向新插进来的节点cur-front tem; //新插进来的头指针指向tem
}void afterinsert_list(List* plist, int data) //后插入一个节点
{insert_after(plist-head,data);
}void the_insert(List *plist, int pos, int data)
{int i 0;ListNode* cur (ListNode*)malloc(sizeof(ListNode));ListNode* tem plist-head;int num data_num(plist);if (pos num)//所插入数据的位置不能大于节点数因为是循环链表{printf(插入数据失败\n);return;}for (; i pos;i){tem tem-next;//找到插入新节点的位置}cur-data data;cur-next tem-next;//将tem尾指针中存放的内容赋给新节点的尾指针即新节点的尾指针代替tem的尾指针tem-next-front cur;//将原tem节点的下一个节点的头指针指向新节点cur-front tem;//将新节点的头指针指向tem节点tem-next cur;//将tem的尾指针指向新节点
}void print(List* plist) //打印
{ListNode* tem;if (plist-head NULL){printf(\n链表已销毁\n);return;}for (tem plist-head-next; tem ! plist-head; tem tem-next)//双向循环链表的遍历{printf(%d , tem-data);}printf(\n);
}void del(ListNode *the_plist) //删除
{the_plist-front-next the_plist-next;//将该节点尾指针中存放的内容存放到上一个节点的尾指针中the_plist-next-front the_plist-front;//将该节点头指针中存放的内容存放到下一个节点的头指针中free(the_plist);//释放这个节点
}void del_front(List *plist) //头删
{del(plist-head-next);//删除链表头
} void del_after(List *plist) //尾删
{del(plist-head-front);//删除链表尾
}ListNode* list_reach(List* plist, int data) //查找
{ListNode* tem;for (tem plist-head-next; tem ! plist-head; tem tem-next){if (tem-data data)return tem;}return NULL;
}void the_del(List *plist, int data) //删除指定的节点
{ListNode* tmp list_reach(plist, data);if (tmp)del(tmp);
}void destory(List *plist) //销毁链表
{while (plist-head! plist-head-next){del_front(plist);//依次删头}free(plist-head);//释放最后一个头plist-head NULL;
}int main()
{//定义一个“链表头”List* first ;init(first);forntinsert_list(first,2);forntinsert_list(first,8);print(first);afterinsert_list(first,0);print(first);the_insert(first,1, 5);print(first);the_insert(first,1, 6);print(first);the_insert(first,0, 9);print(first);forntinsert_list(first,0);print(first);int k data_num(first);printf(%d个节点\n,k);the_insert(first,8, 7);print(first); del_after(first);print(first);del_front(first);print(first);the_del(first,6);print(first);system(pause);return 0;
}
