Creat函数为什么会错呢?

循环链表ADT模板简单应用算法设计:约瑟夫环

作者: 冯向阳时间限制: 1S章节: DS:线性表

问题描述 :

目的:使用C++模板设计循环链表的抽象数据类型(ADT)。并在此基础上,使用循环链表ADT的基本操作,设计并实现单链表的简单算法设计。

内容:(1)请使用模板设计循环链表的抽象数据类型。(由于该环境目前仅支持单文件的编译,故将所有内容都集中在一个源文件内。在实际的设计中,推荐将抽象类及对应的派生类分别放在单独的头文件中。参考网盘中的单链表ADT原型文件,自行设计循环链表的ADT。)

(2)ADT的简单应用:使用该ADT设计并实现循环链表应用场合的一些简单算法设计。

应用2:编号为1,2,...,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。现在给定一个随机数m>0,从编号为1的人开始,按顺时针方向1开始顺序报数,报到m时停止。报m的人出圈,同时留下他的密码作为新的m值,从他在顺时针方向上的下一个人开始,重新从1开始报数,如此下去,直至所有的人全部出列为止。请在使用循环链表ADT的基础上,设计一个算法求出圈的顺序(以编号表示)。限定人数至少为1.

参考函数原型:

template

void Joseph(CirLinkList &A, int m);

//约瑟夫环专用结点类型

struct node{

int number;

int code;

};

输入说明 :

第一行:人数n

第二行:第一个人所持的密码

第三行:第二个人所持的密码

...

第n+1行:第n个人所持的密码

第n+2行:给定的随机数m

输出说明 :

第一行至第n行:建立的循环链表的遍历结果(一个结点占据1行)

第n+1行:空行

第n+2行:出圈的顺序(编号与编号之间以“->”分隔)

#include
#include
#include
using namespace std;

/* 循环单链表的结点定义 */
template
struct LinkNode
{
ElemType data;
int node;
LinkNode *next;
//构造函数1,用于构造头结点
LinkNode(LinkNode *ptr = NULL)
{
next = ptr;
}
//构造函数2,用于构造其他结点
//函数参数表中的形参允许有默认值,但是带默认值的参数需要放后面
LinkNode(const ElemType &item,const ElemType &itam, LinkNode *ptr = NULL)
{
next = ptr;
data = item;
node=itam;
}
//取得结点的数据域的值
ElemType getData(){ return data; }
//修改结点的next域
void SetLink( LinkNode *link ){ next = link; }
//修改结点的data域
void SetLink( ElemType value ){ data = value; }
};

//带头结点的循环单链表
template
class CirLinkList
{
private:
LinkNodehead; // 头结点
LinkNode *tail; // 尾结点
public:
//无参数的构造函数
CirLinkList(){head = new LinkNode; tail = head; head->next = head;}
//带参数的构造函数
CirLinkList(const ElemType &item){head = new LinkNode(item); tail = head; head->next = head;}
//拷贝构造函数
CirLinkList(CirLinkList &List);
//析构函数
//~CirLinkList(){ListDestroy();}
//销毁链表
void ListDestroy();
//清空链表
void ListClear();
//返回链表的长度
int ListLength()
{
if(head->next==head)
return 0;
else
{LinkNode *p;
int i=1;
p=head->next;
while(p->next!=head->next)
{
p=p->next;
i++;
}
return i;}
}
//判断链表是否为空表
bool ListEmpty()
{
if(head->next==head)
return true;
else return false;
}
//获取循环链表头结点
LinkNode
GetHead() { return head;}
//获取循环链表尾结点
LinkNode* GetTail() { return tail;}
//设置链表头结点
void SetHead(LinkNodep){ head = p;}
//在链表的第pos个位置之后插入e元素
void ListInsert_next(int pos,ElemType e)
{
int j;
LinkNode *p,*s,*r;
s=(LinkNode
)malloc(sizeof(ElemType));
p=head->next;
j=1;
while(j {
p=p->next;
j++;
}
r=p;
s->data=e;
p->next=s;
s->next=r->next;
}
//表头插入法动态生成链表
void CreateList_Head(int n)
{
ElemType w;
LinkNode h;
LinkNode *o;
h=head;
for(int i=n;i>0;i--)
{
o=(LinkNode
)malloc(sizeof(ElemType));
cin>>w;
o->data=w;
o->node=n-i+1;
h->next=o;
tail=o;
tail->next=head->next;
h=tail;
}
}
//表尾插入法动态生成链表
//void CreateList_Tail(int n, ElemType *A);
//遍历链表
void ListTraverse()
{
LinkNode *p=head->next;
while(p->next!=head->next)
{

          cout<<p->node<<" "<<p->data<<endl;
          p=p->next;
      }
      cout<<p->node<<" "<<p->data<<endl;

      cout<<endl;
      return ;
  }

void Joseph(int m,int cd)
{
int j=1,i;
LinkNode *p,*s;
p=head->next;
s=p;
for(i=1;i {
while(j!=m)
{
s=p;
p=p->next;
j++;}
s->next=p->next;
m=p->data;
cout<node<<"->";
p=s->next;
j=1;
}
cout<node;
cout<<endl;
}
};

int main()
{
CirLinkList d;
int cd;
cin>>cd;
d.CreateList_Head(cd);
int m;
cin>>m;
d.ListTraverse();
d.Joseph(m,cd);
return 0;
}

所设链表为带头指针的循环链表
即头指针指向第一个元素,尾指针也指向第一个元素
但在初始化时 头指针和尾指针相等。

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!