if(p!=NULL)return(j); else return(-1); } /* locat_L */
3.约瑟夫问题的一种描述：编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数。
方法1．报m的人出列（将其删除），从他在顺时针方向上的下一个人开始重新从一报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。 方法2. 报m的人出列（将其删除），将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从一报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。 [方法1的程序清单] #include
#include
typedef struct node /* 结点的结构定义 */ { int num; /* 编号子域 */ int sm; /* 密码子域 */ struct node *next; /* 指针域 */ }JOS;
/* 函数声明 */ JOS *creat();
void outs(JOS *h, int m); /* 主函数 */ main()
{ int m; JOS *h; h=creat();
printf(“\\n enter the begin secret code, m=（m>1）”); scanf(“%d”,&m); outs(h, m); } /* main */
/* 生成约瑟夫环 */ JOS *creat()
h { int i=0, mi;
JOS *new, *pre, *h;
h=(JOS *)malloc(sizeof(JOS)); /* 为头结点申请空间 */ h->link=h; /* 头结点h形成环 */ pre=h;
printf(“\\n 个人密码 =?”); scanf(“%d”,&mi);
21
while( mi != -111) /* 密码为-111，结束循环 */ { new=(JOS *)malloc(sizeof(JOS)); /* 申请数据元素结点空间 */ i++; new->num=i; new->sm=mi; /* 结点送值 */
new->link=h; pre->link=new;
pre=new; /* 形成循环链表 */ printf(“\\n 个人密码 =?”); scanf(“%d”,&mi); /* 读入下一个密码 */
} /* while */
pre->link= h->link; free(h); /* 删除头结点h */ h=pre->link; return(h); /* 头指针指向第一个数据元素结点 */ } /* JOS *creat , 该约瑟夫环无附加头结点 */ /* 按m被叫出列的顺序，输出结点信息 */ void outs(JOS *h, int m) { int i; JOS *q=h, p;
printf(“\\n “); while (q->link!=q)
{ for(i=1;i
printf(“m m ”,q->num,q->sm); /* 输出第m个人的编号和密码 */ p->link=q->link; free(q); /* 第m个人出列 */ q=p->link;
}
printf(“m m \\n”,q->num,q->sm); /* 输出最后一个结点的编号值 */ free(q); } /* outs */
本程序用了不带头结点的循环链表，也可以加上头结点，对于本题有头结点会使操作麻烦，（同学们可以试一试，加进头结点如何实现？）并不是任何时候有头结点都能使程序操作简化，要根据实际情况，决定用是否使用头结点。
感兴趣的同学可以设计一个程序实现约瑟夫环的方法2。
在一般情况下默认使用头结点。不论是单向链表还是循环链表，头指针不能丢。
三、实习题(以下题目选做1题)
1. 用顺序存储表示（数组）实现约瑟夫环问题。
2. 一个线性表有n个元素（n 3. 从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： （1）指定的值x由键盘输入；（2）程序能处理空链表的情况。 4.用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。 22 要求：（1）通讯录是按姓名项的字母顺序排列的； （2）能查找通讯录中某人的信息； [提示] 可用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的第一个数据元素结点作为链中的首结点，也是末结点。从第二个数据开始逐一作为‘工作结点’，需从链表的首结点开始比较，如果‘工作结点’的数据比链中的‘当前结点’的数据小，就插在其前面。否则，再看后面是否还有结点，若没有结点了就插在其后面成为末结点；若后面还有结点，再与后面的结点逐一比较处理。 5. 超长正整数的加法，设计一个程序实现两个任意长的整数求和运算 [提示] 可采用一个带有头结点的循环链表来表示一个非负的超大整数。从低位 开始每四位组成的数字，依次放在链表的第一个、第二个、……结点中，不足四位的最高位存放在链表的最后一个结点中，表头结点值规定位-1。 例如：大整数“567890987654321”可用如下的头结点的链表表示： head -1 4321 8765 8909 567 按照此数据结构，可以从两个表头结点开始，顺序依次对应相加，求出所需要的进位后，将其代入下一个结点进行运算。 23 实习三 栈和队列 一、实习目的 1. 掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。 2. 掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。 3. 了解和掌握递归程序设计的基本原理和方法。 二、实例 在各种教科书中关于栈和队列叙述十分清晰。但是，它们在计算机内的实现介绍不够详细。为了减轻学生上机实验的困难，在此给出几个例题供参考。 1. 栈的顺序存储结构及实现。 #include #define MAXSIZE 20 /* 数组最大界限 */ typedef int ElemType; /* 数据元素类型 */ typedef struct { ElemType a[MAXSIZE]; /* 一维数组子域 */ int top; /* 栈顶指针子域 */ }SqStack; /* 栈的顺序结构体类型 */ SqStack s1; /* 函数声明 */ void init_s(SqStack *s); void out_s(SqStack s); void push(SqStack *s,ElemType e); ElemType pop(SqStack *s); /* 主函数 */ main() { int k; ElemType e,x; char ch; init_s( &s1); /* 初始化一个空栈 */ do { printf(\ printf(\数据元素e进栈 \ printf(\出栈一个元素，返回其值\； printf(\结束程序运行\ printf(\ printf(\请输入您的选择 (1,2,3)\ scanf(\ switch(k) { case 1:{ printf(\进栈 e=?\ push( &s1,e); out_s( s1 ); 24 } break; case 2:{ x= pop( &s1); out_s( s1 ); } break; printf(\出栈元素 : %d\ case 3: exit(0); } /* switch */ printf(\ }while(k>=1 && k<3); printf(\再见！\ printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */ /* 初始化空栈 * / void init_s(SqStack *s) { s->top=-1; } /* init_s */ /* 输出栈的内容 */ void out_s(SqStack s) { char ch; int i; /* 千万不能修改栈顶指针top */ if (s->top==-1) printf(“\\n Stack is NULL. “); else{ i=s->top; while( i!=-1){ printf(“\\n data=%d”, s->a[i]); i--; } } printf(“\\n 打回车键，继续。“); ch=getch(); } /* out_c */ /* 进栈函数 */ void push(SqStack *s,ElemType e) { if(s->top==MAXSIZE-1)printf(“\\n Sstack is Overflow!”); else{ s->top++ ; s->a[s->top]=e; } }/* push */ /* 出栈函数 */ ElemType pop(SqStack *s) { ElemType x; if(s->top==-1){ printf(“\\n Stack is Underflow!”); x=-1; } else { x=s->a[s->top]; 25