设计一个算法用于判断带头结点的循环双链表是否对称
问题描述:
设计一个算法用于判断带头结点的循环双链表是否对称。问题解答:
算法思想:让p从左向右扫描,q从右向左扫描,直到它们指向同一结点(p==q,当循环双链表中结点个数为奇数时)或相邻(p->next=q或q->prior=p,当循环双链表中结点个数为偶数时)为止,若它们所指结点值相同,则继续进行下去,否则返回0。若比较全部相等,则返回1。int Symmetry(DLinkList L){ //本算法从两头扫描循环双链表,以判断链表是否对称 DNode *p=L->next, *q=L->prior; //两头工作指针 while (p! =q&&q->next! =p) //循环跳出条件 if (p->data==q->data) { //所指结点值相同则继续比较 p=p->next; q=q->prior; }else //否则,返回0 return 0; return 1; //比较结束后返回1 }