2009级数据结构实验指导书(4)

数据结构实验指导书

}

}

/*生成单链表*/

int CreateSL(slnodetype *la ,int n) { int i ;

slnodetype *p , *q ; q=la ;

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

{ p=(slnodetype *)malloc(sizeof(slnodetype)); scanf(\q->next=p; q=p; }

q->next=NULL ; return 1 ; }

/*输出单链表*/

void DisplaySL(slnodetype *la, char *comment) { slnodetype *p ; p=la->next ;

if(p) printf(\while(p)

{ printf(\p=p->next ; }

printf(\}

5、约瑟夫环问题

[问题描述]设有N个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人以出列，如此下去，直到所有人都出列为此。试设计确定他们的出列次序序列的程序。

[基本要求] 选择单向循环链表作为存储结构模拟整个过程，并依次输出列的各人的编号。

[实现提示] 程序运行之后，首先要求用户指定初始报数的下限值，可以n<=30,此题循环链表可不设头节点，而且必须注意空表和非空表的界限。

如 n=8, m=4 时，若从第一个人， 设每个人的编号依次为 1，2，3，?开始报数，则得到的出列次序为4，8，5，2，1，3，7，6，

如下图所示，内层数字表示人的编号 ，每个编号外层的数字代表人出列的序号。 [程序实现]

#include #include typedef struct node { int num;

struct node *next; }linklist;

linklist *creat(head,n) /*使n个人围成一圈，并给每个人标识号数*/ linklist *head; int n ;

- 11 -

数据结构实验指导书

{linklist *s,*p; int i;

s=(linklist * )malloc(sizeof(linklist)); head=s; s->num=1; p=s;

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

{ s=(linklist *) malloc(sizeof(linklist)); s->num=i; p->next=s; p=s; }

p->next=head; return(head); }/* creat */

linklist * select(linklist *head, int m) { linklist *p, *q; int i, t; p=head; t=1;

q=p; /* q为p的前趋指针*/ p=p->next; do {

t=t+1 ; /*报一次数*/ if(t%m==0) { printf(\ q->next=p->next; free(p); p=q->next; }

else { q=p; p=p->next; } }while(q!=p); head=p;

printf(\ return (head); }/* select */

main( ) { int n,m;

linklist *head;

printf(\ scanf(\

printf(\ scanf(\ head=creat(head,n); head=select(head,m);

printf(\

- 12 -

数据结构实验指导书

}/* main */

三、注意事项

1、 删除元素或插入元素表的长度要变化。

2、 在合并表中当某一个表到表尾了就不用比较了，直接将另一个表的

元素复制到总表去即可。

3、 链表中在第i个节点前删除或插入节点需要用指针来表示第i-1个

节点。

4、 在合并链表时需要设置多个指针变量。

5、 循环链表如果不是要删除的节点则指针后移，否则删除该节点。

思考题：编程实现两个循环单链表的合并。

实验二 栈、队列的实现及应用

一、实验目的

1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。

二、实验内容

1、实现栈的顺序存储

# define MAXSIZE 100 typedef int ElemType; typedef struct

{ ElemType data[MAXSIZE]; int top; }SeqStack;

void InitStack(SeqStack *s) {s->top=0; return 1; }

int StackEmpty(SeqStack *s) { if(s->top==0) return 1; else return 0; }

int StackFull(SeqStack *s)

{ if(s->top==MAXSIZE-1) return 1; else return 0; }

void Push(SeqStack *s,int x)

{ if (StackFull(s)){ printf(\ return 0; }

- 13 -

数据结构实验指导书

else { s->data[s->top]=x;

s->top++; }

}

void Display(SeqStack *s) {if(s->top==0)

printf(\ else{ while(s->top!=0)

{ printf(\ s->top=s->top-1;

}

} }

ElemType Pop(SeqStack *s)

{ if(StackEmpty(s)) return 0; else return s->data[--s->top]; }

ElemType StackTop(SeqStack *s) { int i;

if(StackEmpty(s)) return 0; else { i=s->top-1;

return s->data[i];} /*返回栈顶元素的值，但不改变栈顶指针*/

}

main(SeqStack *p)

{int n,i,k,h,x1,x2,select;

printf(\ InitStack(p);

printf(\ scanf(\ for(i=0;i

{ printf(\ scanf(\ Push(p,k); }

printf(\ printf(\ printf(\

printf(\

printf(\ scanf(\ switch(select)

{case 1:{ display(p); break;}

case 2:{ printf(\ scanf(\ Push(p,h);

- 14 -

数据结构实验指导书

case 3:{ display(p); break;} x1=Pop(p);

printf(\ display(p); break;

} case 4:{ x2=StackTop(p);

printf(\

break;

}

}

2、利用栈实现数制转换

# define MAXSIZE 100

typedef int ElemType； /*将顺序栈的元素定义为整型*/ typedef struct

{ ElemType data[MAXSIZE]; int top; }SeqStack;

void InitStack(SeqStack *s) {s->top=0; return 1; }

int StackEmpty(SeqStack *s) { if(s->top==0) return 1; else return 0; }

int StackFull(SeqStack *s) { if(s->top==m-1) return 1; else return 0; }

void Push(SeqStack *s,int x)

{ if (StackFull(s)){ printf(\ return 0; }

else { s->data[s->top]=x;

s->top++; }

}

ElemType Pop(SeqStack *s) { ElemType y;

if(StackEmpty(s)){ printf(\ return 0;

- 15 -

}