## 問題描述 > 設計一算法用于判斷帶頭結點的循環雙鏈表是否對稱 ## 算法思想 > 考慮到題目要求的是循環雙鏈表，因此設置兩個指針p和q，讓p從頭節點開始，從前往后遍歷；指針q從頭節點的prior域指示的尾結點開始，從后往前遍歷，直到它們指向同一結點（`循環雙鏈表的結點數為奇數`）或相鄰結點時`循環雙鏈表的結點數為偶數`為止。 在遍歷期間，如果兩個指針指向的結點的數據域的值一直保持相等，則它們沿著各自的方向繼續遍歷；如果不想等，則終止遍歷。 ## 算法描述 ~~~ int JudgeSym(DNode *head) { DNode *p=head->next; DNode *q=head->prior; while(p!=q&&q->next!=p){ if(p->data==q->data){ p=p->next; q=q->prior; }else{ break; } } if(p==q){ return 0; }else{ return -1; } } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct DNode{ ElemType data; struct DNode *prior,*next; }DNode, *DLinkList; DLinkList CreatList(DNode*); int JudgeSym(DNode*); void BackPrint(DNode*); void ForwardPrint(DNode*); int main(int argc,char* argv[]) { DNode *head; head=(DNode*)malloc(sizeof(DNode)); head->next=head; head->prior=head; head=CreatList(head); BackPrint(head); ForwardPrint(head); int flag=JudgeSym(head); if(flag==0){ printf("It is symmery!\n"); }else{ printf("It isn't symmery!\n"); } return 0; } //尾插法建立循環雙鏈表 DLinkList CreatList(DNode* head) { DNode *r=head; DNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(DNode*)malloc(sizeof(DNode)); L->data=x; L->next=head; head->prior=L; r->next=L; L->prior=r; r=L; scanf("%d",&x); } return head; } //判斷是否對稱，若對稱，返回0；否則返回-1。 int JudgeSym(DNode *head) { DNode *p=head->next; DNode *q=head->prior; while(p!=q&&q->next!=p){ if(p->data==q->data){ p=p->next; q=q->prior; }else{ break; } } if(p==q){ return 0; }else{ return -1; } } //向后遍歷輸出所有結點 void BackPrint(DNode *head) { DNode *p=head->next; while(p!=head){ printf("%4d",p->data); p=p->next; } printf("\n"); } //向前遍歷輸出所有結點 void ForwardPrint(DNode* head) { DNode *p=head->prior; while(p!=head){ printf("%4d",p->data); p=p->prior; } printf("\n"); } ~~~