数据结构(c语言版)---- 双向循环链表的创建、插入、删除、遍历等基本操作
程序员文章站
2022-03-22 19:52:33
...
双向循环链表
双向循环链表比单链表要多一个前驱指针。
创建
bool CreatList(Node *l) {
if (l==NULL)
{
return false;
}
printf("输入链表的长度:");
int len;
scanf("%d", &len);
l->data = len;
l->next = l->pre = l;//头节点的前继和后继指向头节点
Node *p = l->next;
Node *q;
srand((int)time(0));
for (int i = 0; i < len; i++)
{//头插法创建
q = (Node *)malloc(sizeof(Node));
q->data = rand() % 100;
q->next = p->next;
p->next->pre = q;
p->next = q;
q->pre = p;//链表的双向指向
}
return true;
}
链表的长度
int LengthList(Node *l) {
if (l==l->next||l==l->pre)
{
return -1;//判断链表是否为空
}
Node *p = l->pre;
int i = 0;
while (p!=l)
{
i++;//依次遍历链表,终止条件为当前节点是否指向头节点
p = p->pre;
}
return i;
}
节点的插入
bool InsertData(Node *l, int i, int data) {
Node *p = l->next;
int j = 0;
while (p != l && j < i - 1) {
j++;
p = p->next;//利用循环找到待插入节点的前驱
}
if (p==l||j>i-1)
{
return false;//判断下标是否合法
}
Node *q = (Node *)malloc(sizeof(Node));
q->data = data;
q->next = p->next;//将带插入节点的后继指向当前节点的后继
p->next->pre = q;//将当前插入节点的后继的前驱指向待插入节点
p->next = q;//当前节点的后继指向待插入节点
q->pre = p;//待插入节点的前继指向当前节点
return true;
}
节点的删除
bool DeleteData(Node *l, int i) {
Node *p = l->next;
int j = 1;
while (p != l && j < i) {
p = p->next;
j++;//通过循环找到待删除节点
}
if (p == l || j > i )
{
return false;//判断下标是否合法
}
p->pre->next = p->next;//待删除节点的前驱的后继指向待删除节点的后继
p->next->pre = p->pre;//待删除节点的后继的前驱指向待删除节点的前驱
free(p);
return true;
}
清空链表
void ClearList(Node *l) {
Node *p, *q;
p = q = l->next;
while (p!=l)
{
p = p->next;
free(q);
q = p;
}
l->next = l->pre = l;//将链表置为空
}
遍历链表
void printfList(Node *l) {
Node *p = l->next;
while (p!=l)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
全部代码
#include<stdio.h>
#include <stdlib.h>
#include<malloc.h>
#include<time.h>
typedef struct node {
int data;
struct node *pre;
struct node *next;//链表的结构
}Node;
bool CreatList(Node *l);//单链表的创建
int LengthList(Node *l);//获取单链表的长度
bool InsertData(Node *l, int i, int data);//在某元素后插入元素
bool DeleteData(Node *l, int i);//删除当前节点
void ClearList(Node *l);//清空链表
void printfList(Node *l);//遍历链表
int main() {
bool flag = true;
int choice;
int i, data;
Node *l = (Node *)malloc(sizeof(Node));
while (flag)
{
printf("\n=====双向循环链表的操作=====\n");
printf("1.创建链表\n");
printf("2.获取链表的长度\n");
printf("3.数值的插入\n");
printf("4.删除节点\n");
printf("5.清空链表\n");
printf("6.遍历链表\n");
printf("====退出程序输入0======\n");
printf("\n输入你的选择:");
scanf("%d", &choice);
switch (choice)
{
case 1:
if (CreatList(l))
{
printf("\n创建成功\n");
}
else {
printf("\n创建失败\n");
}
break;
case 2:
if (LengthList(l)!=-1)
{
printf("\n链表的长度为:%d\n", LengthList(l));
}
else {
printf("\n链表为空\n");
}
break;
case 3:
printf("i,data = ");
scanf("%d %d", &i, &data);
if (InsertData(l, i, data))
{
printf("\n插入成功\n");
}
else {
printf("\n插入失败\n");
}
break;
case 4:
printf("i = ");
scanf("%d", &i);
if (DeleteData(l, i))
{
printf("\n删除成功\n");
}
else {
printf("\n删除失败\n");
}
break;
case 5:
ClearList(l);
break;
case 6:
printfList(l);
break;
default:
flag = false;
break;
}
}
}
bool CreatList(Node *l) {
if (l==NULL)
{
return false;
}
printf("输入链表的长度:");
int len;
scanf("%d", &len);
l->data = len;
l->next = l->pre = l;//头节点的前级和后继指向头节点
Node *p = l->next;
Node *q;
srand((int)time(0));
for (int i = 0; i < len; i++)
{//头插法创建
q = (Node *)malloc(sizeof(Node));
q->data = rand() % 100;
q->next = p->next;
p->next->pre = q;
p->next = q;
q->pre = p;//链表的双向指向
}
return true;
}
int LengthList(Node *l) {
if (l==l->next||l==l->pre)
{
return -1;//判断链表是否为空
}
Node *p = l->pre;
int i = 0;
while (p!=l)
{
i++;//依次遍历链表,终止条件为当前节点是否指向头节点
p = p->pre;
}
return i;
}
bool InsertData(Node *l, int i, int data) {
Node *p = l->next;
int j = 0;
while (p != l && j < i - 1) {
j++;
p = p->next;//利用循环找到待插入节点的前驱
}
if (p==l||j>i-1)
{
return false;//判断下标是否合法
}
Node *q = (Node *)malloc(sizeof(Node));
q->data = data;
q->next = p->next;//将带插入节点的后继指向当前节点的后继
p->next->pre = q;//将当前插入节点的后继的前驱指向待插入节点
p->next = q;//当前节点的后继指向待插入节点
q->pre = p;//待插入节点的前继指向当前节点
return true;
}
bool DeleteData(Node *l, int i) {
Node *p = l->next;
int j = 1;
while (p != l && j < i) {
p = p->next;
j++;//通过循环找到待删除节点
}
if (p == l || j > i )
{
return false;//判断下标是否合法
}
p->pre->next = p->next;//待删除节点的前驱的后继指向待删除节点的后继
p->next->pre = p->pre;//待删除节点的后继的前驱指向待删除节点的前驱
free(p);
return true;
}
void ClearList(Node *l) {
Node *p, *q;
p = q = l->next;
while (p!=l)
{
p = p->next;
free(q);
q = p;
}
l->next = l->pre = l;//将链表置为空
}
void printfList(Node *l) {
Node *p = l->next;
while (p!=l)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}