Question

编写算法判断单链表的数据是否是对称的

Answer 1

这里是从strfile.txt中自动跟读入数据作为链表的节点，如果楼主想自己输入，把createlist里的while循环创建链表的过程修改一下就好。

/*该程序由文件strfile.txt中的字符串读出的字符此生成单链表，后判断单链表的字符串是否中心对称(即判断文件中的字符串是否中心对称)*/
#include<iostream>
#include<fstream.h>
#define ElemType char

typedef struct LNode
{//链表结点结构的定义
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
typedef struct LSNode
{
    char data;//栈结点的数据域
    struct LSNode *prior;//指向前驱的指针
    struct LSNode *next;//指向下一结点的指针
}LSNode,*LStack;
LStack base,top;//定义栈底与栈顶指针，全局变量
//LSNode *base,*top;//和上行等价的另一种定义方式
int InitLinkStack(LStack &LS)
{//栈初始化，完成初始化时栈中没有结点
    LS=(LStack)malloc(sizeof(LSNode));
    LS->data='*';LS->next=LS->prior=NULL;
    base=top=LS;//初始化栈底与栈顶
    return 1;
}
int Push(LStack &LS,ElemType ch)//入栈操作，即插入新结点作为新的栈顶
{
    LStack p=new LSNode;//为要插入栈顶的数据生成结点
    p->data=ch;//给栈结点赋值
    p->prior=top;
    top->next=p;top=top->next;//将新结点链入栈顶，并使top指针指向新栈顶
    top->next=NULL;//别忘了将插入栈顶的新结点的next域置空
    return 1;
}
int Pop(LStack &LS,ElemType &e)//出栈操作，即删除栈顶
{
    if(top == base)
    {
        cout<<"当前链栈已空！"<<endl;return -1;
    }
    e=top->data;
    top=top->prior;//top指针向栈底前进一个位置
    free(top->next);//释放top的下一个元素，即释放当前栈顶以实现出栈操作
    top->next=NULL;
    return 1;
}
int CreateList(LinkList &head)
{//由文件中的字符串生成单链表
    //定义文件输入流，以输入方式打开磁盘文件strfile.txt
    ifstream infile("strfile.txt",ios::in|ios::nocreate);
    if(!infile)
    {
        cerr<<"文件打开失败！"<<endl;exit(1);
    }
    LinkList p=NULL,q=NULL;head=NULL;ElemType ch;
    while(infile.get(ch))
    {//逐个读入文件strfile.txt中的所有字符，并由每个字符生成链表结点
        p=new LNode;
        p->data=ch;
        if(NULL == head)
            head=p;
        else
            q->next=p;
        q=p;//q永远指向尾结点
    }
    infile.close();//关闭输入文件流
    if(NULL != head)
    {//尾结点的next域置空
        q->next=NULL;
    }
    return 1;
}
int DisplayList(LinkList head)
{//顺序遍历链表并输出所有结点的数据域值
    if(NULL == head)
    {
        cout<<"当前链表为空！"<<endl;return -1;
    }
    LinkList p=head;
    while(NULL != p)
    {
        cout<<p->data<<"    ";p=p->next;
    }
    cout<<endl;
    return 1;
}
int IsSymmetry(LinkList head)
{
    LStack LS;
    InitLinkStack(LS);//初始化栈
    LinkList p=head;//p指向第一个字符所在的节点
    ElemType temp_ch;
    while(NULL != p)
    {//将字符串中的全部字符进栈
        Push(LS,p->data);p=p->next;
    }
    p=head;
    while(NULL != p)
    {
        Pop(LS,temp_ch);
        if(p->data != temp_ch)
        {
            cout<<"该字符串不是中心对称的字符串！"<<endl<<endl;return -1;
        }
        else
            p=p->next;
    }
    cout<<"该字符串是中心对称的字符串！"<<endl<<endl;
    return 1;
}
int main()
{
    LinkList head;
    CreateList(head);//生成单链表
    cout<<"顺序遍历链表并输出所有结点的数据域值："<<endl<<endl;
    DisplayList(head);//打印单链表在的所有数据
    IsSymmetry(head);
    return 1;
}