写joseph-ring时,循环链表老出错,希望懂这个的帮看一下

xianwei

这个主要是老师的作业，我花了点时间写，没有严格的按照书上的数据结构的那种写法。感觉自己程序问题很大，但就是不知道错在哪里，希望有人看一下。谢谢。

我写了三个文件 第一个是：list_joseph.h

//
// File: joseph_H的链表类型声明
//
#ifndef         LIST_JOSEPH_H
#define                 LIST_JOSEPH_H

typedef struct Node* NodePtr;
struct Node {
        int         locate;
        int         password;
        NodePtr next;       
};

class List_joseph {
public:
        List_joseph();                                // 构造函数
        ~List_joseph();                                // 析够函数
       
        // 对链表结点操作方法
        int         retrieveInfo();
        int         getLocate();
       
        // 对链表本身操作方法
        void         advance();
        void          insert(int);
        void         place(int);
        void         remove();
       
        // 游历链表方法
        void         toFirst();
       
        // 判定测试条件方法
        bool        onlyOne();
        bool        atFirst();
        bool        curIsEmpty();
        bool        listIsEmpty();

private:
        NodePtr head;               
        NodePtr cur;
        NodePtr prev;
        NodePtr allocNode(int);                        // 分配结点内存方法
        void         destroyNode(NodePtr p);        // 释放结点内存方法       
        void         nodeReferenceError();
};
#endif

第二个是list_joseph.cpp

//
// File: List_joeseph.cpp. 链表结点方法定义
//                 和相关动态内存分配.
//
#include                 "List_joseph.h"
#include                 <iostream>
#include                 <cstdlib>
using namespace std;

//
// 默认构造函数;初始化一个链表为空
// 前置条件: 无
// 后置条件: 头结点，当前结点，前结点指针为空
//
List_joseph:ist_joseph()
{
        head        = NULL;
        cur                = NULL;       
        prev        = NULL;
}
//
// 链表析够函数
// 前置条件: 无
// 后置条件: 所有链表结点都被释放
//
List_joseph::~List_joseph()
{
        toFirst();

        while(!listIsEmpty());
                remove();
               
}
//
// 函数将会返回当前结点的值
// 前置条件: 当前结点
// 后置条件: 函数会返回当前结点的信息域.
//                         假如没有这个结点，nodeReferenceError 将被调用
//
int List_joseph::retrieveInfo()
{
        if (curIsEmpty())
                cerr << "retrieveInfo wrong" << endl;
       
        return (cur->password);       
}
//
// 函数会返回当前结点最开始的位置
// 前置条件: 无
// 后置条件: 返回位置
//
int List_joseph::getLocate()
{
        return (cur->locate);
}       

void List_joseph::advance()
{
        cur = cur->next;       
}

//
// 函数将会在当前结点后插入一个新结点或
// 为当前结点分配新的结点(cur == null)
// 前置条件:  当链表为空，或者是一个当前结点时，
//                          password将会是被插入的值
// 后置条件:  这个链表将会有个新的含password值的结点. 假如
//                          链表初始化为空，则这是唯一的结点。假如不是，则
//                          新结点将会被插入当前结点之后。然后新的结点就是
//                          当前结点。
void List_joseph::insert(int password)
{
        NodePtr        target = allocNode(password);
        if (listIsEmpty())
        {
                head = target;
                cur         = target;
                prev = NULL;
                target->next = head;       
        }       
        else
        {
                prev                        = cur;
                target->next         = cur->next;
                cur->next                = target;
                cur                                = target;
        }
}
//
// 函数将会给每个结点一个初始位置值
// 前置条件:  值必须为整数，当前结点布能为空
// 后置条件:  无
//
void List_joseph::place(int locate)
{
        cur->locate = locate;       
}
//
// 函数将会移除当前结点，被释放被占用的空间
// 前置条件:  链表必须为非空， 且当前结点也必须为非空
// 后置条件:  无
//
void List_joseph::remove()
{
        NodePtr tmp;
        if (curIsEmpty())
        {
                cerr << "remove wrong" << endl;
                exit(1);
        }
        else if (onlyOne())
        {
                head = NULL;
                cur  = NULL;
                prev = NULL;
                tmp        = cur;
                destroyNode(tmp);       
        }       
        else
        {
                tmp = cur;
                cur = cur->next;
                prev->next = cur;
                destroyNode(tmp);       
        }
}
//
// 函数设置当前结点为头结点
// 前置条件: 链表被初始化
// 后置条件: 当前结点的值为头结点的值(空或第一个结点的地址)
//
void List_joseph::toFirst()
{
        cur = head;
}

bool List_joseph:nlyOne()
{
        return (cur == cur->next);       
}

//
// 布尔函数：当当前结点的值与头结点的值一致时，返回真
// 前置条件: 无
// 后置条件: 当cur与头结点有一样的值为真(null 或是第一个结点的地址)
//
bool List_joseph::atFirst()
{
        return (cur == head);       
}
//
// 当前位置为空则返回真
// 前置条件: 链表被初始化过
// 后置条件: 为空则返回真
bool List_joseph::curIsEmpty()
{
        return (cur == NULL);       
}
//
// 布尔函数: 为空返回真
// 前置条件: 链表必须被初始化
// 后置条件: 为空返回真，否则返回假
//
bool List_joseph::listIsEmpty()
{
        return (head == NULL);       
}
       
//
// 为结点分配空间
// 前置条件:  为int型元素分配空间
// 后置条件:  为分配的空间返回一个指向该内存的指针，
//                          如失败则结束程序.
//
NodePtr List_joseph::allocNode(int password)
{
        NodePtr p = new Node;
        if (!p)
        {
                cerr << "Error making node" << endl;
                exit(1);       
        }
        else
        {
                p->password        = password;
                p->next                = NULL;       
        }
       
        return p;
}
//
// 释放一个链表结点
// 前置条件:  P为指向要释放的结点
// 后置条件:  结点被释放
//
void List_joseph::destroyNode(NodePtr p)
{
        delete p;       
}
//
// 函数处理结点出错情况
// 前置条件: 当前结点出错
// 后置条件: 出错信息将被打印
//
void List_joseph::nodeReferenceError()
{
        cerr << "ERROR: No current node" << endl;       
        exit(1);
}

第三个是joseph_ring.cpp
//
// Function to test the list_joseph.cpp & list_joseph.h.
//
#include         "List_joseph.h"
#include         <iostream>
using namespace std;


int m = 20;

int main()
{
        List_joseph joseph_ring;
        int i, tmp;
        i = 1;
        cout << "please type in everyone's passowrd: " << endl;
        cin  >> tmp;
        while (tmp != -1)
        {
                joseph_ring.insert(tmp);
                joseph_ring.place(i);
                i++;
                cin >> tmp;
        }
       
        i = 0;
        while (joseph_ring.listIsEmpty() != true)
        {
               
                i++;
                while (i == m)
                {
                        cout << joseph_ring.getLocate() << endl;
                        m = joseph_ring.getLocate();
                        joseph_ring.remove();
                        i = 0;
                }       
                joseph_ring.advance();
        }
       
       
        joseph_ring.~List_joseph();
       
       
        return 0;                // ANSI C99 standard        
}

xianwei

题目一                约瑟夫环

【问题描述】
     约瑟夫（Joseph）问题的一种描述是：编号为1，2，…, n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

【基本要求】
       利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。

【测试数据】
          m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。
【实现提示】
          程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。
【选作内容】
       向上述程序中添加在顺序结构上实现的部分。

这个是老师的题目。

假如有人对我问题中一些乱七八糟的东西，看不懂，可以问一下，我会最快回答，因为我的代码写的很混乱。而且加了太多的东西。还有几个函数我没有加注释。

xianwei

自己解决了， 循环链表的空判定出了超级严重的问题。另外就是这个函数不好改（水平不行），我改到最后用goto语句写好了。

千里马肝

   某人在屋檐下躲雨，看见观音正撑伞走过。这人说：“观音菩萨，普度一下众生吧，带我一段如何？”

　 观音说：“我在雨里，你在檐下，而檐下无雨，你不需要我度。”这人立刻跳出檐下，站在雨中：“现在我也在雨中了，该度我了吧？”观音说：“你在雨中，我也在雨中，我不被淋，因为有伞；你被雨淋，因为无伞。所以不是我度自己，而是伞度我。你要想度，不必找我，请自找伞去！”说完便走了。

　 第二天，这人遇到了难事，便去寺庙里求观音。走进庙里，才发现观音的像前也有一个人在拜，那个人长得和观音一模一样，丝毫不差。

　 这人问：“你是观音吗？”

　 那人答道：“我正是观音。”

　 这人又问：“那你为何还拜自己？”

　 观音笑道：“我也遇到了难事，但我知道，求人不如求己。”

shaoxiaoning

斑竹 回答真有哲理。