C语言实现基于链表的回文数判断

mac2024-01-29  35

#include <iostream> #include<stdio.h> #include<stdlib.h> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ int size=0; typedef struct no { int data; struct no *pnext; //定义链表 struct no *ppre; }node; typedef struct { node head; node tail; //链表头尾节点 }lht; void link_init(lht *p) { p->head.pnext=&p->tail; p->head.ppre=NULL; p->tail.pnext=NULL; p->tail.ppre=&p->head; //初始化链表 } int link_add(lht *p,int i) { node *pf=NULL,*pm=NULL,*pl=NULL,*pn=NULL; pn=(node*)malloc(sizeof(node)); if(pn==NULL) return 0; pf=&p->head; pm=pf->pnext; pl=pm->pnext; //在链表偷增加节点 pf->pnext=pn; pn->pnext=pm; pn->ppre=pf; pm->ppre=pn; pn->data=i; size++; return 1; } int link_sub(lht *p,int i) { node *pf=NULL,*pm=NULL,*pl=NULL,*pn=NULL; pf=&p->head; pm=pf->pnext; pl=pm->pnext; pf->pnext=pm->pnext; pl->ppre=pm->ppre; free(pm); pm=NULL; size--; } void link_show(const lht *p) { node *pn=(node*)p->head.pnext; while(pn->pnext!=NULL) { printf("%d ",pn->data); pn=pn->pnext; } printf("\n"); } void link_pdhws(lht *p)//判断回文数 { node *ps=NULL,*pf=NULL; lht check={0}; link_init(&check); ps=(node*)p->head.pnext; pf=ps->pnext; while(pf!=&p->tail) //快指针遍历整个链表 { link_add(&check,ps->data); if(pf->pnext==&p->tail)//偶数时防止越界 { ps=ps->pnext; break; } if(pf->pnext->pnext==&p->tail)//奇数时防止越界 { ps=ps->pnext->pnext; break; } pf=pf->pnext->pnext;//快指针跑两个节点 ps=ps->pnext; //慢指针跑一个节点 } //printf("%d",pf); node *pc=check.head.pnext; link_show(&check); while(ps!=&p->tail) { if(ps->data!=pc->data) { printf("不是回文链表"); return ; } ps=ps->pnext; pc=pc->pnext; } printf("是回文数"); } int main(int argc, char *argv[]) { lht l1={0}; link_init(&l1); link_add(&l1,1); link_add(&l1,2); link_add(&l1,3); link_add(&l1,3); link_add(&l1,1); link_add(&l1,1); link_show(&l1); link_pdhws(&l1); //printf("%d\n",l1.head.pnext->data); return 0; }
最新回复(0)