对称循环双链表的判定（C语言实现）_数据结构c语言判断链表对称

设计一个算法用于判断带头结点的循环双向链表是否对称。

（1） 首先创建一个循环双向链表，输入到“-1”时，退出循环，链表创建完成。

（2） 设计一个符合上述要求的函数：让p从左向右扫描，q从右向左扫描，直到它们指向同一结点（结点为奇数个）或相邻（结点为偶数个）为止。若它们所指结点值相同，则继续进行下去，否则返回0。若比较全部相等，则返回1。

（3） 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。

#include <stdio.h>
#include <stdlib.h>
 
typedef struct DNode {
	int data;
	struct DNode *next, *prior;
} DNode, *DinkList;
 
/*  
 TODO：创建循环双向链表
 功能：创建循环双向链表，从键盘录入链表元素，输入-1 回车停止输入
 比如录入1 2 3 4 5 6 -1，链表值为：1 2 3 4 5 6 
 
 参数：DinkList L是需要操作的链表
 返回值： 返回值为创建成功的链表
 */
DinkList Createlist(DinkList L) {
DinkList e=NULL;
DinkList p=NULL;
DinkList q=NULL;
p=(DinkList) malloc(sizeof(DNode));
L->data=-1;
L->next=NULL;
L->prior=NULL;
L->next=p;
p->prior=L;
q=p;
scanf("%d",&p->data);
while(p->data!=-1)
{
    p=(DinkList) malloc(sizeof(DNode));
    scanf("%d",&p->data);
    q->next=p;
    p->prior=q;
    q=p;
}
e=(DinkList) malloc(sizeof(DNode));
q->next=e;
e->data=-1;
e->prior=q;
e->next=L;
L->prior=e;
return L;
 
}
 
/*  
 TODO：输出循环双向链表
 功能：输出循环双向链表，每个元素之间用" ->" 隔开，
 比如，链表元素：1 2 3 4 5 6 
 则输出为：1 ->2 ->3 ->4 ->5 ->6 
 
 参数：DinkList L是需要操作的链表
 返回值： 无
 */
void ViewLinklist(DinkList L) {
    DinkList h=NULL;
    h=L->next;
    printf("%d",h->data);
    h=h->next;
    while(h->data!=-1)
    {
        printf(" ->%d",h->data);
        h=h->next;
    }
 
 
 
}
 
/*  
 TODO：查看是否对称
 
 功能：让p从左向右扫描，q从右向左扫描，直到它们指向同一结点（结点为奇数个）或相邻（结点为偶数个）为止。
 若它们所指结点值相同，则继续进行下去，否则返回0。若比较全部相等，则返回1。
 如：链表元素：1 2 3 4 5 4 3 2 1，则对称
 链表元素：1 2 3 4 5 5 4 3 2 1，则对称
 链表元素：1 2 3 4 5 1 2 3 4 5，则不对称
 
 参数：DinkList L是需要操作的链表
 返回值： 返回1 双向链表对称，返回0双向链表不对称
 */
int Symmetry(DinkList L) {
    DinkList p=NULL,q=NULL,h=NULL,e=NULL;
    p=q=L->next;
    while(q->data!=-1)
    {
        q=q->next;
    }
    q=q->prior;
    while(p->data==q->data&(p->data!=-1||q->data!=-1))
{
    p=p->next;
    q=q->prior;
}
if(p->data==-1&&q->data==-1)
{
    return 1;
}
return 0;
}
 
int menu_select() //菜单驱动程序
{
	int sn;
	printf("实验一运行系统\n");    //显示菜单
	printf("==============================\n");
	printf("1、建立循环双向链表\n");
	printf("2、循环双向链表元素输出\n");
	printf("3、判断是否对称\n");
	printf("0、退出实验\n");
	printf("==============================\n");
	printf("请选择0--3:");
 
	for (;;)   //菜单功能选择
			{
		scanf("%d", &sn);
		getchar();
		if (sn < 0 || sn > 3)
			printf("\n输入选择错误，请重新选择 0--3:");
		else
			break;
	}
	return sn;
}
 
void main() {
	DinkList L = (DinkList) malloc(sizeof(DNode));
	for (;;)  // 无限循环,选择0 退出
			{
		switch (menu_select())  // 调用菜单函数，按返回值选择功能函数
		{
		case 1:
			printf("请输入链表数据,录入-1停止:\n");
			Createlist(L);
			break;
		case 2:
			printf("循环双链表为：\n");
			ViewLinklist(L);
			break;
		case 3:
			if (Symmetry(L) == 1)
				printf("该循环单链表对称");
			else
				printf("该循环单链表不对称");
			break;
		case 0:
			printf("再见!\n");        //退出系统
			exit(0);
		} // switch语句结束 
	} // for循环结束 
} // main()函数结束