| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1316 人关注过本帖
标题:关于单链表的一个问题
只看楼主 加入收藏
DJ小胖
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2017-5-8
结帖率:0
收藏
已结贴  问题点数:20 回复次数:4 
关于单链表的一个问题
下面是一个单链表归并排序算法,编译环境是VC6.0,数据规模在一万时可以正常编译运行,但规模提升后就无法运行了,求好心人帮帮忙啊,马上就要用了,帮忙调试一下!!!
#include <stdio.h>  
#include <stdlib.h>  
#include<time.h>
/*Link list node*/  
struct node  
{  
    int data;  
    struct node* next;  
};  
  
/*function prototype */  
struct node* SortedMerge(struct node* a, struct node* b);  
void FrontBackSplit(struct node* source, struct node** frontRef, struct node** backRef);  
  
/*sorts the linked list by changing next pointers(not data) */  
void MergeSort(struct node** headRef)  
{  
    struct node* head = *headRef;  
    struct node* a;  
    struct node* b;  
  
    /*base case-- length 0 or 1 */  
    if((head == NULL) || (head->next == NULL))  
    {  
        return;  
    }  
      
    /*Split head into 'a' and 'b' sublists */  
    FrontBackSplit(head, &a, &b);  
  
    /*Recursively sort the sublists */  
    MergeSort(&a);  
    MergeSort(&b);  
  
    /* answer = merge the two sorted lists together */  
    *headRef = SortedMerge(a, b);  
}  
  
struct node* SortedMerge(struct node* a, struct node* b)  
{  
    struct node* result = NULL;  
  
    /* Base cases */  
    if(a == NULL)  
        return (b);  
    else if(b == NULL)  
        return (a);  
  
    /* Pick either a or b recur */  
    if(a->data <= b->data)  
    {  
        result = a;  
        result->next = SortedMerge(a->next, b);  
    }  
    else  
    {  
        result = b;  
        result->next = SortedMerge(a, b->next);     
    }  
    return (result);  
}  
  
/* UTILITY FUNCTIONS */  
/* Split the nodes of the given list into front and back halves,
    and return the two lists using the references parameters.
    If the length is odd, the extra node shold go in the front list.
    Uses the fast/slow pointer strategy. */  
void FrontBackSplit(struct node* source, struct node** frontRef, struct node** backRef)  
{  
    struct node* fast;  
    struct node* slow;  
  
    if(source == NULL || source->next == NULL)  
    {  
        *frontRef = source;  
        *backRef = NULL;  
    }  
    else  
    {  
        slow = source;  
        fast = source->next;  
  
        /* Advance 'fast' two nodes, and advance 'slow' one node */   
        while(fast != NULL)  
        {  
            fast = fast->next;  
            if( fast != NULL )  
            {  
                slow = slow->next;  
                fast = fast->next;  
            }  
        }  
  
        *frontRef = source;  
        *backRef = slow->next;  
        slow->next = NULL;  
    }  
}  
      
/*Function to print nodes in a given linked list*/  
void printList(struct node* node)  
{
    int i=10;
    while( i )  
    {  
        printf("%d  ", node->data);  
        node = node->next;  
        i--;
    }  
    printf("\n");
}  
  
/* Function to insert a node at the begining of the linked list*/  
void push(struct node** head_ref, int new_data)  
{  
    /*allocate node*/  
    struct node* new_node = (struct node*)malloc(sizeof(struct node));  
      
    /*put in the data*/  
    new_node->data = new_data;  
      
    /*link the old list off the new node*/  
    new_node->next = (*head_ref);  
      
    /*move the head to point to the new node*/  
    (*head_ref) = new_node;  
}  
      
/* Drier program to test above functions*/  
int main()  
{  
   clock_t start,finish;
    double duration;
    srand((unsigned)time(NULL));
    /* Start with the empty list */  
    //struct node* res = NULL;  
    struct node* a = NULL;  
  int n=100000;
    /* Let us create a unsorted linked lists to test the functions
       Created lists shall be a: 2->3->20->5->10->15 */  
    while(n){
        push(&a, rand()%100000+1);
        n--;
    }
  printList(a);
  start=clock();
    /* Sort the above created Linked List */  
    MergeSort(&a);  
  finish=clock();
    printf("\n Sorted Linked List is: \n");  
    printList(a);            
  duration=(double)(finish-start)/CLOCKS_PER_SEC;
    printf("%f s\n",duration);
    return 0;  
}  
搜索更多相关主题的帖子: function include source 规模 
2017-05-08 21:32
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:20 
递归的深度。
递归是有巨大开销的。

用迭代实现,可破。

09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-05-08 21:36
DJ小胖
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2017-5-8
收藏
得分:0 
回复 2楼 renkejun1942
那就是说明我的内存无法支撑程序的运行了吗?
2017-05-08 21:40
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
对于递归的深度,理论上是无限的,但是操作系统会限制最大深度。
提供给程序的系统栈是有大小的,具体跟系统有关还是跟编译器有关,就不的而已了。
我很少用递归,递归也学的很烂。

[此贴子已经被作者于2017-5-8 21:49编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-05-08 21:44
DJ小胖
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2017-5-8
收藏
得分:0 
回复 4楼 renkejun1942
好的,谢谢啦!
2017-05-08 21:51
快速回复:关于单链表的一个问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.038963 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved