| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 377 人关注过本帖
标题:堆栈排序指针问题
只看楼主 加入收藏
丘山君
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:87
专家分:154
注 册:2017-11-15
结帖率:54.55%
  已结贴   问题点数:20  回复次数:6   
堆栈排序指针问题
我写了个代码,编译没错,运行错误,应该是指针问题,但是找不到那错,大神帮忙看看,谢谢。

程序代码:
#include <stdio.h>
#include <stdlib.h>
#define N 7
typedef struct node{
struct node *left;
struct node *right;
int date;
} BTnode;

void Cprintf( int a[])
{
    //创建根结点
    BTnode *root=(BTnode *)malloc(sizeof(BTnode));
    BTnode * *Q;
    //创建队列
    Q=(BTnode * *)malloc((N+2)*sizeof(BTnode *));
    int rear,front;
    rear=front=0;
    BTnode *p;
    //根结点初始化
    root->date=a[0];
    root->left=root->right=NULL;
    Q[rear++]=root;
    BTnode *pa;
    int i;
    pa=root;
    //其他结点
    for(i=1;i<N;i++)
    {
        p=(BTnode *)malloc(sizeof(BTnode));
        p->date=a[i];
        p->left=p->right=NULL;
        if(!pa->left)
            pa->left=p;
        else if(!pa->right)
        {
            pa->right=p;
             pa=Q[front++];
        }
        Q[rear++]=p;
    }//°&acute;&sup2;&atilde;±é&Agrave;ú
    while(front>0)
    {
        int tag;
        int k,t,t1;
        //调整成小根堆
        while(1)
        {
            tag=1;
            for(k=front-1;k>-1;k--)
          {
            BTnode *pmin;
            p=Q[k];
            p=pmin;
            if(pmin->date>p->left->date)
                pmin=p->left;
            if(p->right&&pmin->date>p->right->date)
                pmin=p->right;
            if(p!=pmin)
            {
                t=p->date;
                p->date=pmin->date;
                pmin->date=t;
                tag=0;
            }
            if(tag)
                break;
          }
        }
        //交换根结点和最后一个叶子
        t1=Q[rear-1]->date;
    Q[rear-1]->date=root->date;
    root->date=t1;
    //移除最后一个叶子
    if(Q[front-1]->right)
        Q[front-1]->right=NULL;
    else
    {
         Q[front-1]->left=NULL;
         front--;
    }
    }
}
int main()
{
  int a[N]={3,2,5,6,8,9,10};
  BTnode *root;

  Cprintf(a);
}
附件: 您没有浏览附件的权限,请 登录注册
2017-12-23 19:13
虫眼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:9
帖 子:301
专家分:1101
注 册:2017-11-29
  得分:10 
满版的野指针,这个pmin没在开始定义,野没指向任何东西。到这里就崩溃了。
程序代码:
  for(k=front-1;k>-1;k--)
          {
           

            p=Q[k];
            p=pmin;
            if(pmin->date>p->left->date)

2017-12-23 21:58
九转星河
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:长长久久
等 级:版主
威 望:50
帖 子:4972
专家分:13940
注 册:2016-10-22
  得分:10 
通常还是动态数组实现方便,排序的话用平衡树或者会好一些~好奇网上有类似版本的代码么,感觉可以参考一下~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-12-23 22:36
丘山君
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:87
专家分:154
注 册:2017-11-15
  得分:0 
回复 2楼 虫眼
嗯嗯,谢谢,写反了,应该把pmin指向p的,昨天写的乱,用到变量才临时定义
2017-12-24 13:36
丘山君
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:87
专家分:154
注 册:2017-11-15
  得分:0 

问题还是没解决,现在好像是死循环了,重新排了下版,修改了点
,大佬再帮忙看看,谢谢
程序代码:
#include <stdio.h>
#include <stdlib.h>
#define N 7
typedef struct node{
struct node *left;
struct node *right;
int date;
} BTnode;

void Cprintf( int a[])
{
    //创建根结点
    BTnode *root=NULL;
    BTnode * *Q;
    BTnode *p=NULL;
    BTnode *pa=NULL;
    int i;
    int tag;
    int k,t,t1;
    BTnode *pmin=NULL;
    int j;
    root=(BTnode *)malloc(sizeof(BTnode));
    //创建队列
    Q=(BTnode * *)malloc((N+2)*sizeof(BTnode *));
    int rear,front;
    rear=front=0;
    //根结点初始化
    root->date=a[0];
    root->left=root->right=NULL;
    Q[rear++]=root;
    pa=root;
    //其他结点
    for(i=1;i<N;i++)
    {
        p=(BTnode *)malloc(sizeof(BTnode));
        p->date=a[i];
        p->left=p->right=NULL;
        if(!pa->left)
            pa->left=p;
        else if(!pa->right)
        {
            pa->right=p;
            pa=Q[front++];
        }
        Q[rear++]=p;
    }
   
    while(front>0)
    {

        //调整成小根堆
        while(1)
        {
            tag=1;
            for(k=front-1;k>-1;k--)
                {
                    p=Q[k];
                    pmin=p;
                    if(pmin->date>p->left->date)
                        pmin=p->left;
                    if(p->right&&pmin->date>p->right->date)
                        pmin=p->right;
                    if(p!=pmin)
                        {
                            t=p->date;
                            p->date=pmin->date;
                            pmin->date=t;
                            tag=0;
                        }
                    if(tag)
                        break;
                }
        }
        
        //交换根结点和最后一个叶子
        t1=Q[rear-1]->date;
        Q[rear-1]->date=root->date;
        root->date=t1;
        int j=front-1;
        
        //移除最后一个叶子
        if(Q[front-1]->right)
            Q[front-1]->right=NULL;
        else
            {
                Q[front-1]->left=NULL;
                front--;
            }
    }

    for(j;j>0;j--)
        printf("%d ",Q[j]->date);

}
int main(void)
{
  int a[N]={3,2,5,6,8,9,10};
  BTnode *root;
  Cprintf(a);//°&acute;&sup2;&atilde;±é&Agrave;ú
}
2017-12-28 16:30
九转星河
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:长长久久
等 级:版主
威 望:50
帖 子:4972
专家分:13940
注 册:2016-10-22
  得分:0 
回复 5楼 丘山君
话说,用指针的话平衡树不比堆栈效率更高么,同样可以实现功能~不然的话链表结构的堆应该应用广泛才是,看过网上大都是用数组实现的,这不觉得奇怪么~

PS:刚直接搜过链式结构实现堆,真的还有这种结构的,但感觉在进行堆排序的时候要频繁改变指针,用数组的话感觉效率高很多,当然用链表的话不用考虑数组长度这个因素,试试还是可以的,但这和平衡树实现的功能有什么不同之处么~

[此贴子已经被作者于2017-12-28 17:37编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-12-28 17:26
丘山君
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:87
专家分:154
注 册:2017-11-15
  得分:0 
回复 5楼 丘山君
这个是老师上课教的。要我们自己实现,刚开始学堆,数组实现暂时还不太会。。。
2017-12-28 22:14







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

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