数据结构实验报告实验5

目的与要求

简述题目要解决的问题是什么，并说明输入和输出数据的形式。

简述存储结构和算法的基本思想。

使用的计算机：硬件配置、软件环境

列出调试通过的源程序。

习题1：

/*********************************************************************

*    1．设计一个用链表表示的直接选择排序算法，并用程序实现。         *

* 算法说明：已知待排序初始序列用单链表存贮，头指针head指向第一个结点 *

* ，从这个待排序列中找出最小结点，插入head之后，用r来指示。r以前为已 *

* 排序序列，r以后为未排序序列。再从未排序序列中找出最小结点插入r的后 *

* 面，让r指向这个结点。反复执行这个过程，直到排好序。                *

*********************************************************************/

#include

#include

//结点

typedef struct no

{

    int x;

    struct no *next;

}Node, *Node_;

//函数声明

Node_ Structure();//构建序列链表

void Show(Node_ head);//打印链表

void Sort(Node_ head);//排序算法

void Myfree(Node_ head);//空间释放算法

void main()

{

    Node head;

    head.next = Structure();

    if(head.next == NULL) 

    {

        printf("构建序列表失败!\\n");

        return ;

    }

    Show(head.next);

    Sort(&head);

    Show(head.next);

    Myfree(head.next);

}

//用于构造一个序列链表，返回其第一个元素的指针

Node_ Structure()

{

    int x;

    scanf("%d", &x);

    if(x!=0)

    {

        Node_ q=(Node_)malloc(sizeof(Node));

        q->x = x;

        q->next = Structure();

        return q;

    }

    return NULL;

}

//释放申请的空间

void Myfree(Node_ head)

{

    Node_ p;

    while(head != NULL)

    {

        p = head;

        head = head->next;

        free(p);

    }

}

//打印序列链表中的数据

void Show(Node_ head)

{

    while(head != NULL)

    {

        printf("%4d", head->x);

        head = head->next;

    }

    printf("\\n");

}

//排序算法

void Sort(Node_ head)

{

    Node_ r=head, p;

    Node_ ident;//用来记录中间量

    Node_ identl;//用来记录中间量的前一个结点

while(r->next != NULL)

    {

        ident = r->next;

        identl = r;

        for(p=ident; p->next!=NULL; p=p->next)

        {

            if((p->next->x) < (ident->x))

            {

                identl = p;

                ident  = p->next;

            }

        }

        identl->next = ident->next;

        ident->next = r->next;

        r->next = ident;

        r = r->next;

    }

}

习题2：

/**********************************************************************

*2．对N个关键字取整数的记录进行整序，以使所有关键字为非负数的记录排在 *

* 关键字为负数的记录之前，要求使用最少的附加空间，且算法的时间复杂度  *

* 为O(N)。                                                            *

**********************************************************************/

#include

#define MAX 100

void main()

{

    int a[MAX];

    int i, j, n;

    printf("请输入记录的总个数。\\n");

    scanf("%d", &n);

    printf("请输入各记录（仅输入关键字）\\n");

for(i=1; i <= n; i++)

    {

        scanf("%d", &a[i]);

    }

    a[0] = a[1];

    i=1; j=n;

    while(i    {

        while(i=0) --j;

        a[i] = a[j];

        while(i        a[j] = a[i];

    }

    a[i] = a[0];

    for(i=1; i<=n; i++)//打印输出

    {

        printf("%4d", a[i]);

    }

    printf("\\n");

}

列出上面程序对应的运行结果。

分析程序的优缺点、时空性能

     改进思想，写出心得体会