数据结构与算法实验指导书
ListNode *s; /*工作指针*/ head->next=NULL;
ch=getchar(); /*读入第1个字符*/ while(ch!='\\n') {
s=(ListNode *)malloc(sizeof(ListNode)); /*生成新结点*/
s->data=ch; /*将读入的数据放入新结点的数据域中*/ s->next=head->next; head->next=s;
ch=getchar(); /*读入下一字符*/ }
return head; }
/*使用尾插法建立带头结点链表算法*/ ListNode * CreatListR1(void) {
char ch;
ListNode *head=(ListNode *)malloc(sizeof(ListNode)); /*生成头结点*/ ListNode *s,*r; /*工作指针*/
r=head; /*尾指针初值也指向头结点*/ while((ch=getchar())!='\\n') {
s=(ListNode *)malloc(sizeof(ListNode)); s->data=ch; r->next=s; r=s; }
r->next=NULL; /*终端结点的指针域置空,或空表的头结点指针域置空*/ return head; }
/*复制链表A中的内容到表B中*/
void copy(ListNode *a, ListNode *b) {
ListNode *pa=a->next; ListNode *u; ListNode *rb=b; while(pa!=NULL) {
u=( ListNode *)malloc(sizeof(ListNode)); u->data=pa->data; rb->next=u; rb=u;
pa=pa->next; }
rb->next=NULL; }
/*输出带头结点的单链表*/
void DisplaySL(ListNode *la, char *comment)
- 6 -
数据结构与算法实验指导书
{ ListNode *p ; p=la->next ;
if(p) printf(\ while(p) { printf(\ p=p->next; }
printf(\}
/*主函数*/ main( )
{ ListNode *la ,*lb,*lc, *p ; int n,x,i;
printf(\用头插法建立链表la，请输入节点内容:\la=CreatListF();
DisplaySL(la,\新生成链la节点内容:\
printf(\链表la的长度: -\printf(\请输入要插入的元素: \scanf(\
printf(\请输入要插入的位置：\scanf(\InsertList(la,x,i);
DisplaySL(la,\插入后链la节点内容\printf(\请输入要删除元素的位置：\scanf(\DeleteList(la,i);
DisplaySL(la, \删除后链la节点内容\
printf(\用尾插法建立链表lb，请输入节点内容:\fflush(stdin); lb=CreatListR1();
DisplaySL(lb,\新生成链lb节点内容:\Init_List(&lc); copy(la,lc);
DisplaySL(lc,\复制生成的链lc节点内容:\}
2、有序单链表的合并
[问题描述] 已知单链表la和lb中的数据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。
[基本要求] 不破坏la表和lb表的结构。 [程序实现]
# include
typedef int DataType; typedef struct SLNode { DataType data;
struct SLNode * next; }slnodetype;
- 7 -
数据结构与算法实验指导书
int MergeSL(slnodetype *la,slnodetype *lb,slnodetype **lc); int CreateSL(slnodetype *la,int n);
void DisplaySL(slnodetype *la , char * comment); main( )
{ slnodetype *la, *lb, *lc ,*p; int n,m;
la=(slnodetype *)malloc(sizeof(slnodetype)); la->next=NULL;
lb=(slnodetype *)malloc(sizeof(slnodetype)); lb->next=NULL;
lc=(slnodetype *)malloc(sizeof(slnodetype)); lc->next=NULL;
printf(\输入链la节点数:\scanf(\
printf(\输入链la 节点内容:\CreateSL(la,n);
DisplaySL(la,\链la 节点内容:\printf(\输入链lb节点数:\scanf(\
printf(\输入链lb节点内容:\CreateSL(lb,m);
DisplaySL(lb,\链lb 节点内容:\
if(MergeSL(la,lb,&lc)) DisplaySL(lc,\合成后的链lc:\getchar(); }
int MergeSL(slnodetype * la , slnodetype *lb,slnodetype * *lc) { slnodetype * pa, * pb, * pc;
lc=(slnodetype *)malloc(sizeof(slnodetype)); pa=la->next; pb=lb->next; pc= *lc;
while(pa&&pb) {
pc->next=(slnodetype*)malloc(sizeof(slnodetype));
pc=pc->next;
if(pa->data<=pb->data) { pc->data=pa->data; pa=pa->next; }
else{ pc->data=pb->data; pb=pb->next; } }
while (pa) /*插入la链的剩余段 */
{
pc->next=(slnodetype*)malloc(sizeof(slnodetype)); pc=pc->next;
pc->data=pa->data; pa=pa->next;
- 8 -
数据结构与算法实验指导书
}
/*插入lb链的剩余段*/ while(pb) {
pc->next=(slnodetype*)malloc(sizeof(slnodetype)); pc=pc->next;
pc->data=pb->data; pb=pb->next;
}
/*生成单链表*/
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(\}
实验三 循环链表实验
一、实验目的
1、掌握用Visual C++6.0上机调试循环链表的基本方法 2、进一步掌握循环单链表的插入、删除、查找算法的实现
二、实现内容
1. 约瑟夫环问题
[问题描述]设有N个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人以出列，如此下去，直到所有人都出列为此。试设计确定他们的出列次序序列的程序。
[基本要求] 选择单向循环链表作为存储结构模拟整个过程，并依次输出列的各人
- 9 -
数据结构与算法实验指导书
的编号。
[实现提示] 程序运行之后，首先要求用户指定初始报数的下限值，可以n<=30,此题循环链表可不设头节点，而且必须注意空表和非空表的界限。
如 n=8, m=4 时，若从第一个人， 设每个人的编号依次为 1，2，3，?开始报数，则得到的出列次序为4，8，5，2，1，3，7，6，
如下图所示，内层数字表示人的编号 ，每个编号外层的数字代表人出列的序号。 [程序实现]
#include
struct node *next; }linklist;
linklist *creat(head,n) /*使n个人围成一圈，并给每个人标识号数*/ linklist *head; int n ;
{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; }
- 10 -
