循环双链表教程(个人笔记)
前言
作为一个C语言初学者的我,用博客来存放我的笔记
循环双链表教程
一、定义结构体
代码入下:
typedef struct Node//定义结构体
{
char date[10]; //数据域
struct Node *prior;//指针域
struct Node *next;
}Node;
typedef struct Node *PNode;//用来记录首尾的指针
typedef struct List
{
PNode first;//记录表头(头指针)
PNode last;//记录最后一个结点(尾指针)
int size;//记录结点个数
}List;
二、创建空表
代码如下:
void Creat(List *list)//创造空表
{
Node *s = (Node*)malloc(sizeof(Node));
list->first = list->last = s;//分别记录头结点的位置
//创造循环双向空链表
list->last->next = list->first;//s->next指向s
list->first->prior = list->last;//s->prior指向s
list->size = 0;//记录结点个数
}
三、插入方法
1.尾插法
代码如下:
void Add(List *list)//尾插法
{
Node *newNode = (Node*)malloc(sizeof(Node));
printf("请输入你要插入的数据:");
scanf("%s",newNode->date);
newNode->next = list->first;//新结点尾和表头相接
list->first->prior = newNode;//表头指向新结点
list->last->next = newNode;//表尾指向新结点
newNode->prior = list->last;//新结点的头指向表尾
list->last = newNode;//尾指针指向新结点(更新表尾为新节点)
list->size++;//结点个数增加1
}
用下图帮助我更好的理解
2.选插法
void Insert(List *list)//选插
{
Node *newNode = (Node*)malloc(sizeof(Node));
int i = 0,j = 0;
printf("请输入你要插入的数据:");
scanf("%s",newNode->date);//给新结点数据域赋值
printf("请输入%s的插入位置:",newNode->date);
scanf("%d",&i);
if(i < 1||i > list->size)
{
printf("该位置不在链表范围内!\n");
return;
}
else
{
Node *p = (Node*)malloc(sizeof(Node));
p = list->first->next;
for(j = 1;j < i - 1;j++)
p = p->next;
newNode->next = p->next;
p->next->prior = newNode;
newNode->prior = p;
p->next = newNode;
list->size++;
}
}
四、查找方法
1.按位置查找
void Get(List *list)//查找第i个元素
{
int i = 0,j = 0;
printf("请输入你要查找元素的位置:");
scanf("%d",&i);
if(i < 1 ||i > list->size)
{
printf("该链表没有第%d个元素\n",i);
return;
}
else
{
Node *p = (Node*)malloc(sizeof(Node));
p = list->first->next;
for(j = 1;j < i;j++)
p = p->next;
printf("第%d个元素是%s\n",i,p->date);
}
}
2.按内容查找
void Locate(List *list)//查找元素e
{
int i = 1;
char date[10];
Node *p = (Node*)malloc(sizeof(Node));
printf("请输入你要查找的数据:");
scanf("%s",date);
p = list->first->next;
for(i = 1;i < list->size;i++)
{
if(strcmp(p->date,date) == 0)
break;
p = p->next;
}
if(i > list->size)
{
printf("该链表中没有%s这个元素\n",p->date);
return;
}
printf("%s是链表的第%d个元素\n",p->date,i);
}
五、输出链表
void Print(List *list)//输出
{
if(list->size == 0)
{
printf("该表为空表\n");
return;
}
else
{
int i;
Node *p = (Node*)malloc(sizeof(Node));
p = list->first->next;
printf("该链表中的元素元素有:\n");
for(i = 1;i <= list->size;i++)
{
printf("%s ",p->date);
p = p->next;
}
printf("\n");
}
}
六、删除方法
1.按位置删除
void Delete(List *list)//选删
{
int i = 0,j = 0;
Node *p = (Node*)malloc(sizeof(Node));
p = list->first->next;
printf("请输入你要删除数据的位置:");
scanf("%d",&i);
if(i < 1 || i >list->size)
{
printf("该链表没有第%d个数据,无法删除!\n",i);
return;
}
else
{
for(j = 1;j < i;j++)
p = p->next;
p->next->prior = p->prior;
p->prior->next = p->next;
free(p);
list->size--;
}
}
2.全部删除
void Destroy(List *list)//全删
{
Node *p = (Node*)malloc(sizeof(Node));
Node *q = (Node*)malloc(sizeof(Node));
p = q = list->first->next;
for(;list->size > 0;list->size--)
{
p = p->next;
free(q);
q = p;
}
}
总结
链表的核心其实就是对指针的运用,作为初学者的我,只有把基础打牢了,才能更好的掌握。