/* 以下循环单链表操作纯本人原创，转载请注明来源 */
/***********************************************************************************************************************
File Name : 双向链表.c
Date Created : 2019-10-22
Author : 大竹竿
Description : 实现双向链表各类操作
***********************************************************************************************************************/
/*带头节点的循环双向链表 */
/*
头节点；首节点前的节点(头节点永远指向首节点，头节点不存在左指针)
头指针：指向头节点的指针
首节点：链表第一个节点
尾节点：链表最后一个节点
*/
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
#define num 3
typedef int datatype;
typedef int bool;
/* 定义节点结构体 */
typedef struct list {
datatype data; // 数据域
struct list *Lnext; // 左指针
struct list *Rnext; // 右指针
}List, *pList;
/* 函数声明 */
pList init(); // 初始化
void build(pList h); // 创建
int isEmpty(pList h); // 判空
int length(pList h); // 测长
void print(pList h); // 打印
/* 增 */
void head_Insert(pList h); // 头插
void tail_Insert(pList h); // 尾插
void first_head_Value_Insert(pList h); // 指定值头插(只插第一个)
void all_head_Value_Insert(pList h); // 指定值头插(所有的)
void first_tail_Value_Insert(pList h); // 指定值尾插(只插第一个)
void all_tail_Value_Insert(pList h); // 指定值尾插(所有的)
void head_Order_Insert(pList h); // 指定序号头插
void tail_Order_Insert(pList h); // 指定序号尾插
/* 删 */
void head_Delete(pList h); // 头删
void tail_Delete(pList h); // 尾删
void first_Value_Delete(pList h); // 指定值删除(只删除第一个)
void all_Value_Delete(pList h); // 指定值删除(删除所有的)
void order_Delete(pList h); // 指定序号删除
/* 改 */
void first_Value_Revise(pList h); // 指定值修改(只修改第一个)
void all_Value_Revise(pList h); // 指定值修改(修改所有的)
void order_Revise(pList h); // 指定序号修改
/* 查 */
void first_Value_Query(pList h); // 指定值查询(只查询第一个)
void all_Value_Query(pList h); // 指定值查询(查找所有的)
void order_Query(pList h); // 指定序号查询
void Destroy(pList h); // 销毁
/* 函数定义 */
/* 初始化 */
pList init()
{
pList h = (pList)malloc((sizeof(List))); // 创建头结点
h->Rnext = NULL; // 初始化时，头节点右指针为空
return h;
}
/* 创建 */
void build(pList h)
{
pList p = h; // 声明一个移动指针
int i, arr[num];
printf("请输入%d个数：", num);
for (i = 0; i < num; i++) {
scanf("%d", &arr[i]);
}
for (i = 0; i < num; i++) {
pList node = (pList)malloc(sizeof(List)); // 创建节点
node->data = arr[i]; // 节点数据域
node->Lnext = p; // 新节点左指针指向上一个节点
node->Rnext = NULL; // 新节点右指针为空
p->Rnext = node; // 上一个节点指向下一个节点（对于首节点而言，为头结点指向首节点）
p = p->Rnext; // 指针后移
}
return;
}
/* 判空 */
bool isEmpty(pList h)
{
if (h->Rnext == NULL) {
return true;
}
return false;
}
/* 测长 */
int length(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return 0;
}
int len = 0;
pList p = h;
while (p->Rnext != NULL) {
len++;
p = p->Rnext;
}
printf("当前链表长度为：%d\n", len);
return len;
}
/* 打印 */
void print(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("当前链表为：");
pList p = h->Rnext;
while (p != NULL) {
printf("%d ", p->data);
p = p->Rnext;
}
printf("\n\n");
return;
}
/* 头插 */
void head_Insert(pList h)
{
printf("请输入头插的值：");
datatype ele;
scanf("%d", &ele);
pList node = (pList)malloc(sizeof(List));
node->data = ele;
node->Lnext = h;
node->Rnext = h->Rnext;
h->Rnext = node;
return;
}
/* 尾插 */
void tail_Insert(pList h)
{
printf("请输入尾插的值：");
datatype ele;
scanf("%d", &ele);
pList p = h; // 移动指针
while (p->Rnext != NULL) { // 找到尾节点
p = p->Rnext;
}
pList node = (pList)malloc(sizeof(List));
node->data = ele;
node->Lnext = p;
node->Rnext = NULL;
p->Rnext = node;
return;
}
/* 指定值头插(只插第一个) */
void first_head_Value_Insert(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入需要在哪个数值前插入(只插第一个)：");
datatype ele;
scanf("%d", &ele);
printf("请输入需要插入的值；");
datatype val;
scanf("%d", &val);
pList p = h; // 移动指针
while (p->Rnext != NULL){
if (p->Rnext->data == ele) { // 找到指定值的前驱
break;
}
p = p->Rnext;
}
if (p->Rnext == NULL) {
printf("输入的值%d不存在!\n", ele);
return;
}
pList node = (pList)malloc(sizeof(List));
node->data = val;
node->Lnext = p;
node->Rnext = p->Rnext;
p->Rnext->Lnext = node;
p->Rnext = node;
return;
}
/* 指定值头插(所有的) */
void all_head_Value_Insert(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入需要在哪个数值前插入(所有的)：");
datatype ele;
scanf("%d", &ele);
printf("请输入需要插入的值；");
datatype val;
scanf("%d", &val);
pList p = h;
bool flag = true;
while (p->Rnext != NULL) { // 找到指定值的前驱
if (p->Rnext->data == ele) {
flag = false;
pList node = (pList)malloc(sizeof(List));
node->data = val;
node->Lnext = p;
node->Rnext = p->Rnext;
p->Rnext->Lnext = node;
p->Rnext = node;
p = p->Rnext->Rnext;
continue;
}
p = p->Rnext;
}
if (flag) {
printf("输入的值%d不存在!\n", ele);
return;
}
return;
}
/* 指定值尾插(只插第一个) */
void first_tail_Value_Insert(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入需要在哪个值后插入(只插第一个)：");
datatype ele;
scanf("%d", &ele);
printf("请输入需要插入的值：");
datatype val;
scanf("%d", &val);
pList p = h->Rnext; // 移动指针
while (p != NULL) { // 找到指定值节点
if (p->data == ele) {
break;
}
p = p->Rnext;
}
if (p == NULL) {
printf("输入的值%d不存在!\n", ele);
return;
}
pList node = (pList)malloc(sizeof(List));
node->data = val;
node->Lnext = p;
node->Rnext = p->Rnext;
p->Rnext->Lnext = node;
p->Rnext = node;
return;
}
/* 指定值尾插(所有的) */
void all_tail_Value_Insert(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入需要在哪个值后插入(所有的)：");
datatype ele;
scanf("%d", &ele);
printf("请输入需要插入的值：");
datatype val;
scanf("%d", &val);
pList p = h->Rnext;
bool flag = true;
while (p != NULL) { // 找到指定值节点
if (p->data == ele) {
flag = false;
pList node = (pList)malloc(sizeof(List));
node->data = val;
node->Lnext = p;
node->Rnext = p->Rnext;
p->Rnext->Lnext = node;
p->Rnext = node;
p = p->Rnext->Rnext;
continue;
}
p = p->Rnext;
}
if (flag) {
printf("输入的值%d不存在!\n", ele);
return;
}
return;
}
/* 指定序号头插 */
void head_Order_Insert(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入在第几个元素前插入：");
int n;
scanf("%d", &n);
if ((n < 1) || (n > length(h))) {
printf("输入的序号非法!\n");
return;
}
printf("请输入需要插入的值：");
datatype ele;
scanf("%d", &ele);
pList p = h;
int i = 1;
while (i != n) { // 找到序号节点的前驱节点
p = p->Rnext;
i++;
}
pList node = (pList)malloc(sizeof(List));
node->data = ele;
node->Lnext = p;
node->Rnext = p->Rnext;
p->Rnext->Lnext = node;
p->Rnext = node;
return;
}
/* 指定序号尾插 */
void tail_Order_Insert(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入在第几个元素后插入：");
int n;
scanf("%d", &n);
if ((n < 1) || (n > length(h))) {
printf("输入的序号非法!\n");
return;
}
printf("请输入需要插入的值：");
datatype ele;
scanf("%d", &ele);
pList p = h;
int i = 0;
while (i != n) { // 找到序号节点
p = p->Rnext;
i++;
}
pList node = (pList)malloc(sizeof(List));
node->data = ele;
node->Lnext = p;
node->Rnext = p->Rnext;
p->Rnext->Lnext = node;
p->Rnext = node;
return;
}
/* 头删 */
void head_Delete(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("头删...\n");
pList p = h->Rnext;
p->Rnext->Lnext = h;
h->Rnext = p->Rnext;
free(p);
return;
}
/* 尾删 */
void tail_Delete(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("尾删...\n");
pList p = h;
while (p->Rnext->Rnext != NULL) { // 找到尾节点的前驱
p = p->Rnext;
}
free(p->Rnext);
p->Rnext = NULL;
return;
}
/* 指定值删除（删除第一个） */
void first_Value_Delete(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入需要删除的值(只删第一个)：");
datatype ele;
scanf("%d", &ele);
pList p = h, p1;
while (p->Rnext != NULL) { // 找到指定值的前驱
if (p->Rnext->data == ele) {
break;
}
p = p->Rnext;
}
if (p->Rnext == NULL) {
printf("输入的值%d不存在!\n", ele);
return;
}
p1 = p->Rnext;
p1->Rnext->Lnext = p;
p->Rnext = p1->Rnext;
free(p1);
return;
}
/* 指定值删除（删除所有的） */
void all_Value_Delete(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入需要删除的值(删除所有)：");
datatype ele;
scanf("%d", &ele);
pList p = h, p1;
bool flag = true;
while (p->Rnext != NULL) { // 找到指定值的前驱
if (p->Rnext->data == ele) {
flag = false;
p1 = p->Rnext;
p1->Rnext->Lnext = p;
p->Rnext = p1->Rnext;
free(p1);
continue;
}
p = p->Rnext;
}
if (flag) {
printf("输入的值%d不存在!\n", ele);
return;
}
return;
}
/* 指定序号删除 */
void order_Delete(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入需要删除第几个元素：");
int n;
scanf("%d", &n);
if ((n < 1) || (n > length(h))) {
printf("输入的序号非法!\n");
return;
}
pList p = h, p1;
int i = 1;
while (i != n) { // 找到序号节点的前驱
p = p->Rnext;
i++;
}
p1 = p->Rnext;
p1->Rnext->Lnext = p;
p->Rnext = p1->Rnext;
free(p1);
return;
}
/* 指定值修改（只改第一个） */
void first_Value_Revise(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入需要修改的值(修改第一个)：");
datatype ele;
scanf("%d", &ele);
printf("请输入改为哪个值：");
datatype val;
scanf("%d", &val);
pList p = h;
while (p->Rnext != NULL) { // 找到指定值的前驱
if (p->Rnext->data == ele) {
p->Rnext->data = val;
return;
}
p = p->Rnext;
}
if (p->Rnext == NULL) {
printf("输入的值%d不存在!\n", ele);
return;
}
return;
}
/* 指定值修改(修改所有) */
void all_Value_Revise(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入需要修改的值(修改所有的)：");
datatype ele;
scanf("%d", &ele);
printf("请输入改为哪个值：");
datatype val;
scanf("%d", &val);
pList p = h;
bool flag = true;
while (p->Rnext != NULL) { // 找到指定值的前驱
if (p->Rnext->data == ele) {
flag =false;
p->Rnext->data = val;
}
p = p->Rnext;
}
if (flag) {
printf("输入的值%d不存在!\n", ele);
return;
}
return;
}
/* 指定序号修改 */
void order_Revise(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入需要修改第几个元素：");
int n;
scanf("%d", &n);
if ((n < 1) || (n > length(h))) {
printf("输入的序号非法!\n");
return;
}
printf("请输入改为哪个值：");
datatype val;
scanf("%d", &val);
pList p = h;
int i = 0;
while (i != n) { // 找到序号节点
p = p->Rnext;
i++;
}
p->data = val;
return;
}
/* 指定值查找（查找第一个） */
void first_Value_Query(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入需要查找的值(只查第一个)：");
datatype ele;
scanf("%d", &ele);
pList p = h;
int n = 0;
while (p->Rnext != NULL) { // 找到指定值的前驱
n++;
if (p->Rnext->data == ele) {
printf("元素%d在第%d号位置上!\n", ele, n);
return;
}
p = p->Rnext;
}
if (p->Rnext == NULL) {
printf("输入的值%d不存在!\n", ele);
return;
}
return;
}
/* 指定值查找（查找所有） */
void all_Value_Query(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入需要查询的值(查找所有的)：");
datatype ele;
scanf("%d", &ele);
printf("%d所处的位置分别为：", ele);
pList p = h;
int i = 0;
bool flag = true;
while (p->Rnext != NULL) { // 找到指定值的前驱
i++;
if (p->Rnext->data == ele) {
printf("%d ", i);
flag = false;
}
p = p->Rnext;
}
if (flag) {
printf("输入的值%d不存在!\n", ele);
return;
}
else {
printf("\n");
}
return;
}
/* 指定序号查询 */
void order_Query(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("请输入需要查询第几个位置的元素：");
int n;
scanf("%d", &n);
if ((n < 1) || (n > length(h))) {
printf("输入的序号非法!\n");
return;
}
pList p = h;
int i = 0;
while (i != n) { // 找到序号节点
p = p->Rnext;
i++;
}
printf("第%d号位置的元素为：%d\n", n, p->data);
return;
}
/* 销毁 */
void Destroy(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
return;
}
printf("销毁链表...\n");
pList p = h, p1;
while (!(isEmpty(h))) {
p1 = p->Rnext;
p->Rnext = p->Rnext->Rnext;
free(p1);
}
return;
}
int main()
{
/* 初始化 */
pList head = init(); // 创建头结点
/* 创建 */
build(head);
length(head);
print(head);
/* 头插 */
head_Insert(head);
length(head);
print(head);
/* 尾插 */
tail_Insert(head);
length(head);
print(head);
/* 指定值头插(只插第一个) */
first_head_Value_Insert(head);
length(head);
print(head);
/* 指定值头插(所有的) */
all_head_Value_Insert(head);
length(head);
print(head);
/* 指定值尾插(只插第一个) */
first_tail_Value_Insert(head);
length(head);
print(head);
/* 指定值尾插(所有的) */
all_tail_Value_Insert(head);
length(head);
print(head);
/* 指定序号头插 */
head_Order_Insert(head);
length(head);
print(head);
/* 指定序号尾插 */
tail_Order_Insert(head);
length(head);
print(head);
/* 头删 */
head_Delete(head);
length(head);
print(head);
/* 尾删 */
tail_Delete(head);
length(head);
print(head);
/* 指定值删除(删除第一个) */
first_Value_Delete(head);
length(head);
print(head);
/* 指定值删除(删除所有的) */
all_Value_Delete(head);
length(head);
print(head);
/* 指定序号删除 */
order_Delete(head);
length(head);
print(head);
/* 指定值修改(只修改第一个) */
first_Value_Revise(head);
length(head);
print(head);
/* 指定值修改(修改所有) */
all_Value_Revise(head);
length(head);
print(head);
/* 指定序号修改 */
order_Revise(head);
length(head);
print(head);
/* 指定值查询(只查第一个) */
first_Value_Query(head);
length(head);
print(head);
/* 指定值查询(查找所有的) */
all_Value_Query(head);
length(head);
print(head);
/* 指定序号查询 */
order_Query(head);
length(head);
print(head);
/* 销毁 */
Destroy(head);
length(head);
print(head);
return 0;
}