牛骨文教育服务平台(让学习变的简单)

问题描述

试写一算法来判断单链表的前n个字符是否中心对称。
例如xyx,xyyx都是中心对称

算法思想

第1章第2节练习题19 判断循环双链表对称中已经初次涉及到了判断链表中心对称的问题,但是因为单链表只能从前往后遍历,因此不能使用与其相同算法进行解决,那么借助栈来判断单链表中的数据是否中心对称。

将单链表的前一半元素依次入栈,遍历到单链表的后一半元素的第一个元素时,便从栈中弹出一个元素,对它们俩开始比较。

  • 若相等,则将链表中的下一个元素与栈中再次弹出的元素进行比较,直至单链表到末尾,而且如果此时栈也为空栈,则可得出此单链表是中心对称的结论;
  • 若不相等,则单链表不是中心对称。

算法描述

int JudgeSym(LNode* head,int n)
{
    LNode *p=head->next;
    char s[n/2];
    int i;
    for(i=0;i<n/2;i++){
        s[i]=p->data;
        p=p->next;
    }
    i--;
    if(n%2){
        p=p->next;  
    }
    while(p&&p->data==s[i]){
        p=p->next;
        i--;
    }
    if(i==-1){
        return 0;
    }else{
        return -1;
    }
}

具体代码见附件。

附件

typedef char ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

LinkList CreatList(LNode*);
int JudgeSym(LNode*,int);
void Print(LNode*);

int main(int argc,char* argv[])
{
    LNode *head;
    head=(LNode*)malloc(sizeof(LNode));
    head=CreatList(head);
    Print(head);

    int flag;
    int n=5;
    flag=JudgeSym(head,n);
    if(flag){
        printf("The link is not symmetery before %d charactor!
",n);
    }else{
        printf("The link is symmetery before %d charachtor!
",n);
    }
    return 0;
}
//尾插法建立单链表
LinkList CreatList(LNode* head)
{
    LNode *L;
    LNode *r=head;
    ElemType x;
    scanf("%c",&x);
    while(x!="
"){
        L=(LNode*)malloc(sizeof(LNode));
        L->data=x;
        r->next=L;
        r=L;
        scanf("%c",&x);
    }
    return head;
}
//判断中心对称
int JudgeSym(LNode* head,int n)
{
    LNode *p=head->next;
    char s[n/2];
    int i;
    for(i=0;i<n/2;i++){
        s[i]=p->data;
        p=p->next;
    }
    i--;
    if(n%2){
        p=p->next;  
    }
    while(p&&p->data==s[i]){
        p=p->next;
        i--;
    }
    if(i==-1){
        return 0;
    }else{
        return -1;
    }
}
//打印全部结点
void Print(LNode *head)
{
    LNode *p=head->next;
    while(p){
        printf("%4c",p->data);
        p=p->next;
    }
    printf("
");
}