判断单链表的前n个元素是否对称
问题描述:
设单链表的表头指针为h,结点结构由data和next两个域构成,其中data域为字符型。试设计算法判断该链表的前n个字符是否中心对称。例如xyx、xyyx都是中心对称。问题解答:
算法思想:使用栈来判断链表中的数据是否中心对称。将链表的前一半元素依次进栈。在处理链表的后一半元素时,当访问到链表的一个元素后,就从栈中弹出一个元素,两个元素比较,若相等,则将链表中下一个元素与栈中再弹出的元素比较,直至链表到尾。这时若栈是空栈,则得出链表中心对称的结论;否则,当链表中的一个元素与栈中弹出元素不等时,结论为链表非中心对称,结束算法的执行。int dc(LinkList L, int n){ //h是带头结点的n个元素单链表,本算法判断链表是否是中心对称 char s[n/2];int i=1; //i记结点个数,s字符栈 P=L->next; //p是链表的工作指针,指向待处理的当前元素 for{i=0;i<n/2;i++) { //链表前一半元素进栈 s[i]=p->data; p=p->next; } i--; //恢复最后的i值 if(n%2==1) //若n是奇数,后移过中心结点 p=p->next; while(p!=NULL && s[i] ==p->data) { //检测是否中心对称 i--; //i充当找顶指针 p=p->next; } if (i==-1) //桟为空找 return 1; //链表中心对称 else return 0; //链表不中心对称 }算法先将“链表的前一半”元素(字符)进栈。当n为偶数时,前一半和后一半的个数相同;当n为奇数时,链表中心结点字符不必比较,移动链表指针到下一字符开始比较。比较过程中遇到不相等时,立即退出while循环,不再进行比较。
本题也可以先将单链表中的元素全部入栈,然后再次扫描单链表L并比较,直到比较到单链表L尾为止,但是算法需要两次扫描单链表L,效率不及上述算法高。