//設(shè)計(jì)一個(gè)算法用于判斷帶頭結(jié)點(diǎn)的循環(huán)雙鏈表是否對(duì)稱(chēng)
include <stdio.h>
include <stdlib.h>
typedef struct DNode
{
int data;
struct DNode *prior, *next;
} DNode, *DLinkList;
DLinkList DList_TailInsert(DLinkList L, int n)
{
int i; //設(shè)元素類(lèi)型為整型
L = (DLinkList)malloc(sizeof(DNode));
L->prior = L->next = L;
DNode *p, *q = L;
printf("請(qǐng)輸入表元素：");
for (i = 0; i < n; i++)
{
p = (DNode *)malloc(sizeof(DNode));
scanf("%d", &p->data);
p->next = q->next;
q->next = p;
p->prior = q;
L->prior = p;
q = p;
}
return L;
}
void print(DLinkList L)
{
DLinkList p;
p = L->next;
while (p != L)
{
printf("%d ", p->data);
p = p->next;
}
}
int Symmetry(DLinkList L)
{
DNode *p = L->next, *q = L->prior; //兩頭工作指針
while (p != q && q->next != p) //循環(huán)跳出條件
{
if (p->data == q->data) //所指結(jié)點(diǎn)值相同則繼續(xù)比較
{
p = p->next;
q = q->prior;
}
else
{
return 0;
}
}
return 1;
}
int main()
{
DLinkList L, A;
int n;
A = (DLinkList)malloc(sizeof(DNode));
printf("請(qǐng)輸入要建立的鏈表長(zhǎng)度：");
scanf("%d", &n);
A = DList_TailInsert(L, n);
printf("尾插法建立的雙向循環(huán)鏈表：");
print(A);
printf("\n");
if (Symmetry(A) == 1)
printf("該循環(huán)雙鏈表對(duì)稱(chēng)");
else
printf("該循環(huán)雙鏈表不對(duì)稱(chēng)");
printf("\n");
return 0;
}
