数据结构(C语言版)习题及答案第二章(2)

}

case 4:return;

default: printf("输入有误！\n");

}

}

}

6、用循环单链表来实现约瑟夫问题。（作为上机实践题目）

数据结构(C语言版)习题及答案

#include <stdio.h>

#include <malloc.h>

typedef struct Lnode {

int data ;

Lnode *next ;

}*Link;

void CreateList( Link &L , int n )

//建立一个n个结点的循环单链表

{

int i ; Lnode *p,*s;

s= ( Lnode * ) malloc ( sizeof ( Lnode )) ;

s->data = 1 ;

L=p=s;

for ( i=2 ; i<=n ; i++)

{

s= ( Lnode * ) malloc ( sizeof ( Lnode )) ;

s->data = i ;

p->next = s ;

p=s ;

}

p->next=L;

}

void DeleteList( Link &L , Lnode * p, Lnode

{

q->next=p->next ; // 修改结点的指针域

free (p) ; // 释放p结点所占存储空间

}

void josephus(Link &L,int s , int m )

{

Lnode *p,*q;

p=L;

for (int i=1;i<=s-1;i++) p=p->next;

q=p->next;

while(q->next!=p) q=q->next;

while(p->next!=p)

{

for (int j=1;j<m;j++)

{

q=p;p=p->next;

}

printf("%d,",p->data);

DeleteList( L , p , q);

p=q->next;

} *q)//从循环单链表中删除结点p

数据结构(C语言版)习题及答案

printf("%d ",p->data);

printf("\n");

}

void main()

{

Link L=NULL;

int m,n,s;

printf("请输入围圈人数、报数的开始位置和报数的上限\n");

scanf("%d,%d,%d",&n,&s,&m);

if ((m>1000)||(n>1000)) printf("输入值m或n不合法！\n");

else

if (s>n) printf("输入值s和n不合法！\n");

else

{

CreateList( L,n );

printf("\n");

josephus( L, s , m );

}

}

7、某百货公司对仓库中的库存电视进行管理时，按其价格从低到高的次序构成一个循环单链表来保存信息，每个结点包含价格、数量和指针三个域。现新到m台价格为h的电视机，编写修改原信息链表的算法。（作为上机实践题目）

# include < malloc.h >

# include < stdio.h >

struct Elemtype

{

float jiage;

int shuliang;

};

struct Lnode

{

Elemtype data;

struct Lnode * next ;

};

//单链表的后插入创建算法

void Rcreate( Lnode *L , Elemtype A[ ] , int n )

{

int i ;

Lnode *p,*s;

p=L;

for ( i=0 ; i<n ; i++)

{

s= ( Lnode * ) malloc ( sizeof ( Lnode )) ;

s->data = A[i];

数据结构(C语言版)习题及答案

s->next=p->next;

p->next=s ;

p=s ;

}

}

//单链表的输出算法

void printList( Lnode *L )

{ Lnode *p ;

if(L->next==L)

printf("单链表为空！\n");

else

{

p=L->next;

printf("当前仓库中库存的电视相关信息为:\n"); printf("价格\t\t数量\n");

while ( p->next!=L)

{

printf ("%f\t" , p->data.jiage) ;

printf ("%d\n" , p->data.shuliang) ;

p=p->next;

}

printf ("%f\t" , p->data.jiage) ;

printf ("%d\n" , p->data.shuliang) ;

}

}

void Insert( Lnode *L , Elemtype elem) {

Lnode *s;

s=( Lnode * ) malloc (sizeof (Lnode)) ; s->data=elem;

if(L->next==L)

{

}

else

{

Lnode *p=L,*q =L->next;

while ((q!=L)&&q->data.jiage<s->data.jiage) {

p=q;

q=q->next ;

} s->next=L->next; L->next=s;

数据结构(C语言版)习题及答案

s->next=q;

p->next=s;

}

}

//主函数

void main( )

{ Lnode *L;

int n;

Elemtype A[ 50 ],elem;

printf("请输入仓库中库存的电视的台数：\n"); scanf("%d",&n);

printf("按价格从低到高输入电视信息：\n"); for ( int j=0; j<n; j++)

{

scanf("%f,",&A[ j ].jiage) ;

scanf("%d",&A[ j ].shuliang) ;

}

L=( Lnode * ) malloc ( sizeof ( Lnode )) ; L->next=L;

Rcreate( L , A , n ) ;

printList( L ) ;

printf("请输入新到的电视相关信息！\n"); printf("请输入价格:");

scanf("%f",&elem.jiage);

printf("请输入数量:");

scanf("%d",&elem.shuliang);

printf("\n");

Insert(L,elem);

printList( L ) ;

}