第6章17题的完整程序

// 6_17.cpp : 试用顺序存储结构设计一个算法,仅用一个辅助节点,实现将线形表中的节点循环右移k位的运算,

// 并分析算法的时间复杂度。

//

 

#include "stdafx.h"

#include <stdlib.h>

 

typedef int datatype;

 

typedef struct node

{

    datatype data;

    int n;

    node * pNext;

}node;

 

void del (node* head)

// 释放空间的函数

{

    node* p = head;

 

    if(head == NULL)

    {

        return;

    }

 

    while(head != NULL)

    {

        p = head->pNext;

        delete(head);

        head = p;

    }

 

    return;

}

 

datatype FindLast(node* head)

// 寻找链表末尾节点的函数

{

    node* p = head;

 

    if(head == NULL)

    {

        return 0;

    }

 

    while(p->pNext != NULL)

    {

        p = p->pNext;

    }

 

    return p->data;

}

 

node* CreateData(void)

// 建表函数,以-1为结束标志

{

    node* head = NULL;

    node* s = NULL;

    node* r = NULL;

 

    datatype p = 0;

 

    int n = 1;

 

    printf("请输入第一个数:");

    scanf("%d", &p);

 

    while(p != -1)

    {

 

 

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

 

        if(s == NULL)

        {

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

 

            del(head);

 

            return NULL;

        }       

 

        s->data = p;

        s->n = n++;

 

        if(head == NULL)

        {

            head = s;

        }

        else

        {

            r->pNext = s;

        }

 

        r = s;

 

        printf("请输入下一个数(输入-1结束):");

        scanf("%d", &p);

    }

 

    if(r != NULL)

    {

        r->pNext = NULL;

    }

 

    return head;

}

 

void Rotate(node* head)

// 循环右移一位的函数

{

    node* p = head;

 

    if(p == NULL || p->pNext == NULL)

    {

        return;

    }

 

    datatype tempdata = head->data;

 

    while(p->pNext != NULL)

    {

        /*

        p->pNext->data = p->data;

        p = p->pNext;

        */

 

        tempdata = p->pNext->data;

        p->pNext->data = head->data;

        p = p->pNext;

 

        head->data = tempdata;

    }

 

    head->data = tempdata;

 

}

 

void RotateX(node* head, int k)

// 循环右移k位的函数

{

    if (k <= 0)

    {

        printf("nk值小于0,将返回。n");

        return;

    }

 

    printf("n循环右移%d位:n", k);

 

    for(int i = 0; i < k; i++)

    {

        Rotate(head);

    }

 

    return;

}

 

void printnode(node* head)

// 显示链表的函数

{

    node* p = head;

 

    if(p == NULL)

    {

        printf("当前线性表为空表n");

    }

 

    printf("当前线性表为:n");

 

    while(p != NULL)

    {

        printf("%dt", p->data);

        p = p->pNext;

    }

    printf("n");

}

 

int main(int argc, char* argv[])

{

    node* head = CreateData();

    int k = 0;

 

    printnode(head);

 

    printf("请输入k:");

    scanf("%d", &k);

 

    RotateX(head, k);

 

    printnode(head);

 

    del(head);

 

    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 博主赞过: