第8章第11题的完整程序

/// 8_11.cpp : 设单链表中存放着n个字符,试编写算法,判断该字符串是否有中心对称关系,

/// 例如xyzzyx, xyzyx 都算是中心对称的字符串。要求用尽可能少的时间完成判断。

 

#include "stdafx.h"

#include <stdlib.h>

 

#define MAXSIZE 8

 

typedef struct node

{

    char data;

    node* pNext;

}node;

 

typedef struct stringList

{

    node* dataHead;

    int number;

}stringList;

 

typedef struct charStack

{

    node* pRear;

}charStack;

 

//取栈顶函数,执行后栈不变

char getHead(charStack* pCS)

{

    if (pCS != NULL && pCS->pRear != NULL)

    {

        return pCS->pRear->data;

    }

    else

    {

        return ”;

    }

}

 

//出栈函数

char pop(charStack* pCS)

{

    //pCS为空,返回空值,pCS不改变

    if (pCS == NULL || pCS->pRear == NULL)

    {

        return ”;

    }

    //pCS仅有一个元素,出栈,pCS置空

    else if(pCS->pRear->pNext == pCS->pRear)

    {

        node* temp = pCS->pRear->pNext;

        int tempdata = temp->data;

 

        pCS->pRear = NULL;

 

        free(temp);

 

        return tempdata;

    }

    else

    {

        node* temp = pCS->pRear->pNext;

        int tempdata = temp->data;

 

        pCS->pRear->pNext = temp->pNext;

 

        free(temp);

 

        return tempdata;

    }

}

 

//入栈函数

char push(charStack* pCS, char& data)

{

    node* s = NULL;

 

    //保证pCS有效

    while (pCS == NULL)

    {

        pCS = (charStack*)malloc(sizeof(charStack));

        pCS->pRear = NULL;

    }

 

    //给s分配空间

    while(s == NULL)

    {

        s = (node*)malloc(sizeof(node));

        s->data = data;

        s->pNext = NULL;

    }

 

    //当pCS为空时,将s作为pCS的唯一元素

    if (pCS->pRear == NULL)

    {

        pCS->pRear = s;

        s->pNext = s;

    }

    else if(pCS->pRear->pNext == pCS->pRear)

    {

        s->pNext = pCS->pRear;

        pCS->pRear->pNext = s;

    }

    else

    {

        s->pNext = pCS->pRear->pNext;

 

        pCS->pRear->pNext = s;

    }

 

    return s->data;

}

 

bool isEmpty(charStack* pCS)

{

    if (pCS == NULL || pCS->pRear == NULL)

    {

        return true;

    }

    else

    {

        return false;

    }

}

 

//输入字符串的函数,用尾插法建链表

stringList* InputList(void)

{

    stringList* head = NULL;

 

    head = (stringList*)malloc(sizeof(stringList));

 

    if (head == NULL)

    {

        printf("内存分配出错!n");

        return NULL;

    }

 

    node* datahead = NULL;

    node* s = NULL;

    node* r = NULL;

    char ch;

    int dnumber = 0;

 

    printf("请输入一个字符串:n");

 

    ch = getchar();

 

    while(ch != ‘n’)

    {

        s = (node*)malloc(sizeof(node));

 

        s->data = ch;

 

        if(datahead == NULL)

        {

            datahead = s;

        }

        else

        {

            r->pNext = s;

        }

 

        r = s;

 

        scanf("%c", &ch);

 

        dnumber ++;

    }

 

    if(r != NULL)

    {

        r->pNext = NULL;

    }

 

    head->dataHead = datahead;

    head->number = dnumber;

 

    return head;

}

 

// 删除链表的函数

void del (stringList* head)

{

    if(head == NULL || head->dataHead == NULL)

    {

        return;

    }

 

    node* temp = head->dataHead;

    node* p = temp;

 

    while(temp != NULL)

    {

        p = temp->pNext;

 

        delete(temp);

 

        temp = p;

    }

 

    delete(head);

 

    return;

}

 

// 显示链表的函数

void PrintList(stringList* head)

{

    if(head == NULL || head->dataHead == NULL)

    {

        printf("这是一个空列表。n");

        return;

    }

 

    node* dhead = head->dataHead;

 

    while(dhead != NULL)

    {

        printf("%c", dhead->data);

 

        dhead = dhead->pNext;

    }

 

    printf("n");

 

    printf("%dn", head->number);

 

    return;

}

 

//判断字符串是否对称

void Proceed(stringList* pHead)

{

    charStack cs;

 

    cs.pRear = NULL;

 

    int number = pHead->number;

 

    node* temp = pHead->dataHead;

 

    //一半元素入栈

    for(int i = 0; i < number / 2; i ++)

    {

        push(&cs, temp->data);

 

        temp = temp->pNext;

    }

 

    //若原字符串长度为奇数,则忽略中间的一个字符

    if( (number & 1) == 1)

    {

        i++;

        temp = temp->pNext;

    }

 

    for(; i < number; i++)

    {

        if(temp->data == pop(&cs))

        {

            temp = temp->pNext;

            continue;

        }

 

        printf("不是对称字符串!n");

 

        return;

    }

 

    printf("是对称字符串!n");

    return;

 

}

 

int _tmain(int argc, _TCHAR* argv[])

{

    stringList* head = NULL;

 

    char ch = ‘y’;

 

    while(ch == ‘y’)

    {

        head = InputList();

 

        PrintList(head);

 

        Proceed(head);

 

        printf("还继续吗?n");

 

        ch = getchar();

        getchar();

 

    }

    return 0;

}

 

 

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: