数据结构基础实验6(2)

Test6_seq.cpp

#include <iostream.h>

#include <stdlib.h>

typedef int ElemType;

typedef struct List{

ElemType *list;

int size;

int MaxSize;

}SeqList;

#include "test6_Seq.h"

void main()

{

SeqList josephus1;

SeqList josephus2;

int i,j,m,n,l,x;

InitList(josephus1);

InitList(josephus2);

cout<<"请输入人数n："<<endl;

cin>>n;

cout<<"请输入每人的正整数密码："<<endl;

for(j=1;j<=n;j++){

cin>>x;

InsertList(josephus1,x,j);

InsertList(josephus2,x,j);

}

cout<<"\n请输入首次报数人编号i及初始报数上限值m"<<endl;

cin>>i>>m;

while(!EmptyList(josephus1))

{

浙大城院 数据结构基础实验6

l=LengthList(josephus1); //线性表长度

j=(i+m-1)%l; //查出要出列的位置

if(j==0) //如果j=0，则位置在线性表的末尾

j=l;

m=GetList(josephus1,j); //得出下一个上限值

DeleteList(josephus1,m,j); //删除出列的人

i=j; //从删除人的下一个人开始报数

cout<<"出列人的编号是:";

cout<<FindList (josephus2,m)<<endl;

// FindList (josephus2,m)查找给定值元素的位置

}

}

Test6_Link.h

//不带表头附加结点的单链表

//初始化单链表

void InitList (LNode*&H)

{

H = NULL;

}

//清除单链表

void ClearList(LNode *&H)

{ //释放动态申请的内存空间

LNode *cp, *np; //当前结点指针与后继结点指针

cp=H;

while(cp!=NULL) //按顺序遍历单链表，释放每个结点

{

np=cp->next; // 保存下一个结点

free(cp);

cp=np; //使下一个结点成为当前结点

}

H=NULL; //置单链表为空

}

//求单链表长度

int LengthList (LNode*H)

{

LNode*p=H; //用来遍历链表结点

int i=0; //用来统计结点个数

while(p!=NULL)

浙大城院 数据结构基础实验6

{

i++;

p=p->next;

}

return i;

}

//判断单链表是否为空表

bool EmptyList (LNode *H)

{

return H == NULL;

}

//取单链表第 pos 位置上的元素

ElemType GetList (LNode*H, int pos)

{

LNode*p=H; //用来遍历链表结点

int i=0; //用来统计已查找的结点个数

if (pos<1) {

cerr<< " pos is out range!"<<endl;

exit(1);

}

while (p!=NULL) { //遍历到第pos个结点或最后一个结点为止

i++;

if (i==pos) break;

p=p->next;

}

if (p!=NULL) return p->data;

else //pos值大于表长

{ cerr<<" pos is out range!"<<endl;

exit(1);

}

}

//从单链表中查找是否存在给定值的元素

int FindList (LNode*H, ElemType item)

{

int i=0;

LNode*p=H; //用来遍历链表结点

while(p!=NULL)

{

i++;

if (p->data==item)

return i;

浙大城院 数据结构基础实验6

else

p=p->next;

}

}

//向单链表插入一个元素

bool InsertList ( LNode*&H, ElemType item, int pos)

{

LNode*newptr, *cp, *ap;

if (pos<-1) {

cout<<" 参数不合法"<<endl;

return false;

}

//寻找新结点的插入位置，使得在ap和cp间插入

cp=H; ap=NULL;

if (pos == 0) { //按值有序插入情况

while ( cp != NULL) {

if ( item < cp->data )

break;

else {

ap=cp; cp=cp->next;

}

}

}

else if ( pos == -1 ) //在表尾插入情况

while ( cp != NULL) {

ap=cp; cp=cp->next;

}

else { //按指定位置插入情况

int i=0;

while ( cp != NULL) {

i++;

if (i==pos) break;

else { ap=cp; cp=cp->next;

}

}

if ( cp==NULL && i+1<pos ) {

cout<<"参数不合法"<<endl;

return false;

}

}

//完成新结点的动态分配, 赋值与插入

浙大城院 数据结构基础实验6

newptr = (LNode*)malloc(sizeof(LNode));

newptr ->data = item;

if (ap==NULL) { //插入到表头

newptr->next=H;

H=newptr;

}

else //插入到ap和cp结点之间

{

newptr->next=cp;

ap->next=newptr;

}

return true;

}

//从单链表中删除一个元素

bool DeleteList ( LNode*&H, ElemType &item, int pos)

{

LNode*cp, *ap;

if (H==NULL)

{

cerr<< "空表，不能删除! "<<endl;

return false;

}

if (pos<-1) {

cout<<"参数不合法! "<<endl;

return false;

}

//寻找删除位置，使得cp指向待删除结点，ap指向cp的前一个结点

cp=H;

ap=NULL;

if (pos == 0) { //按值删除情况

while ( cp != NULL) {

if ( item == cp->data )

break;

else {

ap=cp; cp=cp->next;

}

}

if (cp==NULL) {

cout<< "没有相应结点可删除!"<<endl;

return false;

}

浙大城院 数据结构基础实验6

}

else if ( pos == -1 ) //删除表尾结点情况

while ( cp->next != NULL) {

ap=cp; cp=cp->next;

}

else { //删除指定位置结点情况

int i=0;

while ( cp != NULL) {

i++;

if (i==pos) break;

else { ap=cp; cp=cp->next; }

}

if ( cp==NULL) {

cout<<"参数不合法!"<<endl;

return false;

}

}

item = cp->data;

if (ap==NULL) H=H->next; //删除表头结点

else ap->next=cp->next; //删除非 …… 此处隐藏：2092字，全部文档内容请下载后查看。喜欢就下载吧 ……