北理工数据结构第二章实验报告

第二章作业

1、在什么情况下用顺序表比链表好？

删除，插入操作较少，直接用的时候较多。

2、已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a. 删除P结点的直接后继结点的语句序列是__（11）__（3）__（14）_______。 b. 删除P结点的直接前驱结点的语句序列是（10）（12）（8）（11）（3）（14）。 c. 删除P结点的语句序列是__（10）_（12）_（7）_（3）_（14）______________。 d. 删除首元结点的语句序列是__（12）__（10）__（14）__（13）______。 e. 删除尾元结点的语句序列是__（9）__（11）_（3）_（14）___________。

(1)p = p->next;

(2)p->next = p;

(3)p->next = p->next->next;

(4)p = p->next->next;

(5)while ( p!=NULL ) p=p->next;

(6)while ( q->next!=NULL ) { p=q; q=q->next; }

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

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

(9)while ( p->next->next!=NULL ) p=p->next;

(10)

(11)

(12)

(13)

(14) q=p; q=p->next; p=l; l=l->next; free(q);

3、算法设计。设顺序表va中的数据元素递增有序，请设计一算法，将x插入到顺序表的适当位置，以保持该表的有序性。

i=0; j=length(va);

while(va[i]<x&&i<length(va)) {i++;}

while(j-i!=0) {av[j]=av[j-1];j--;}

av[i]=x;

4、算法设计。请设计一个算法，实现顺序表的原地逆置，即利用原表的存储空间将线性表（a1，a2，……，an）逆置为（an，……，a2，a1）。

for(i=0;i<length(a)/2;i++)

{ p=a[i];

j=length-1-i;

a[i]=a[j];

a[j]=p;}

5、算法设计。请设计一个算法，实现单链表的原地逆置。

p=l;k=l;

while(k->next!=NULL) {k=k->next;}

q=k;

j=p->data;p->data=q->data;q->data=j;

while(p->next!=q)

{ k=p->next; p=p->next;

while(k->next!=q) {k=k->next;}

q=k;

j=p->data;p->data=q->data;q->data=j;}

实验一

1、采用单向环表实现约瑟夫环。

请按以下要求编程实现：

① 从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，……，m。

② 从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。

例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。

#include<stdio.h>

#include<stdlib.h>

typedef struct LNode{

int data; struct LNode *next;

}LNode,*linklist;

void createlist_L(linklist l,int m){

int i; linklist p; l->data=1; l->next=l; for(i=m;i>1;--i) {p=(linklist)malloc(sizeof(LNode)); p->data=i; p->next=l->next;

} l->next=p; }

main()

{

int m,s,n,i,j; linklist l,p,q; scanf("%d %d %d",&m,&s,&n); l=(linklist)malloc(sizeof(LNode));

createlist_L(l,m); p=l; for(i=0;i<m-1;i++) { p=p->next;} for(j=1;j<s;j++) { p=p->next; } for(i=1;i<m+1;i++) {

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

{

p=p->next;

}

q=p->next;

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

free(q);

}

system("pause");

}

2、归并顺序表

请按以下要求编程实现：

① 从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。

② 将链表linka和linkb归并为linkc，linkc仍然为升序排列。归并完成后，linka和linkb为空表。输出linkc。

③ 对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。

例如：linka输入为：10 20 30 40 50 0

linkb输入为：15 20 25 30 35 40 45 50 0

归并后的linkc为：10 15 20 20 25 30 30 35 40 40 45 50 50

删除重复后的linkc为：10 15 20 25 30 35 40 45 50 typedef int status;

typedef int elemtype;

#include "stdio.h"

#include "stdlib.h"

typedef struct node{

elemtype num;

struct node *next;

}node;

typedef struct {

node *l;

int length;

} list;

status create(list *const clist){

int count;

node *c;

clist->l = (node*)malloc(sizeof(node));//head c = clist->l;

c->num = 0;

for(scanf("%d",&count);count!=0;scanf("%d",&count)){

}

return 1;

}

main(void){

list linka, linkb, linkc;

node *p, *q, *r, *t; if( ( c->next = (node*)malloc(sizeof(node)) ) == NULL) return 0; c = c->next; clist->length++; c->num = count; c->next = NULL;

create(&linka);

create(&linkb);

p = linka.l;

q = linkb.l;

linkc.l = (node*)malloc(sizeof(node));//head r = linkc.l;

r->num = 0;

linkc.length = 0;

while(p->next != NULL && q->next != NULL){ if(p->next->num > q->next->num) t=q;

else

t=p;

}

if(p->next != NULL)

r->next=p->next;

else

r->next=q->next;

for(r = linkc.l; r = r->next;)

printf("%d ",r->num);

printf("\n");

r = linkc.l;

while(r->next->next != NULL){ r->next = t->next; t->next = t->next->next; r = r->next;

} if(r->next->next->num == r->next->num){ t = r->next; r->next = t->next; free(t); }else{ } r = r->next;

for(r = linkc.l; r = r->next;) printf("%d ",r->num); system("pause");

}

第二篇：数据结构基础实验6

浙江大学城市学院实验报告

课程名称 数据结构基础

实验项目名称 实验六约瑟夫环的实现

学生姓名 专业班级 学号

实验成绩 指导老师（签名）日期

一. 实验目的和要求

1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。

2、掌握利用线性表的各种操作来进行具体的实际应用。

3、加强程序设计的能力。

二. 实验内容

1、编写程序，模拟约瑟夫环（josephus）问题： n个人（编号为1，2，3，……，n (n>0) ）按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出两个值：一个为首先报数的人的编号i (0<i<=n)，另一个为起始报数上限值m。接着从编号为i的人开始按顺时针方向自1起顺序报数，报到m时停止报数，且报到m的人出列，并将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数，……，如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，给出出列人的编号序列。

基本要求:

（1）人数n、每人的正整数密码、首次报数人编号i、初始报数上限值m均由键盘输入。

（2）参照线性表的抽象数据类型定义，设计本实验的抽象数据类型。

（3）根据你设计的抽象数据类型，分别用顺序存储结构和链式存储结构实现约瑟夫环问题。并请分别将顺序存储结构的程序存放在文件test6_Seq.h（基本操作函数）、test6_Seq.cpp（主函数）中，链式存储结构的程序存放在文件test6_Link.h（基本操作函数）、test6_Link.cpp（主函数）中。

（4）设计测试数据，并调试程序，直到正确运行。

2、填写实验报告，实验报告文件取名为report6.doc。

3、上传实验报告文件report6.doc及源程序文件test6_Seq.h、test6_Seq.cpp、test6_Link.h、test6_Link.cpp到Ftp服务器（ ftp://10.61.14.240:5000 ）自己的文件夹下。同时上交一份书面的实验报告。

三. 抽象数据类型定义

（需说明你设计的每个基本操作的功能）

Test6_seq

1、//清除单链表

void ClearList(LNode *&H)

2、//求单链表长度

int LengthList (LNode*H)

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

bool EmptyList (LNode *H)

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

ElemType GetList (LNode*H, int pos)

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

int FindList (LNode*H, ElemType item)

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

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

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

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

test6_Link

1、//初始化线性表

void InitList(SeqList &L)

2、//判断是否为空

bool EmptyList(SeqList L)

3、//查找给定值元素的位置

int FindList (SeqList L, ElemType item)

4、//在线性表L中求序号为pos的元素，该元素作为函数值返回

ElemType GetList(SeqList L, int pos)

5、//求线性表长度

int LengthList(SeqList L)

6、//按给定条件pos向线性表删除一个元素

bool DeleteList (SeqList &L, ElemType &item , int pos )

7、//按给定条件pos向线性表插入一个元素

bool InsertList(SeqList &L, ElemType item, int pos)

四. 两种类型（顺序和链式）的存储结构定义及算法思路

（包括两种存储结构定义及一些重要函数的算法实现思路）

顺序存储结构：

typedef int ElemType;

typedef struct List{

ElemType *list;

int size;

int MaxSize;

}SeqList;

重要函数的算法实现思路：

void InitList(SeqList &L) //初始化线性表

int LengthList(SeqList L)//求线性表长度

bool EmptyList(SeqList L)//判断是否为空

int FindList (SeqList L, ElemType item) //查找给定值元素的位置

ElemType GetList(SeqList L, int pos)//返回线性表L中序号为pos元素的值

bool DeleteList (SeqList &L, ElemType &item , int pos )

//按给定条件pos向线性表删除一个元素

主函数思路：

1.先求出线性表长度l

2.再利用j=(i+m-1)%l查出要出列的位置

3.如果j=0，则位置在线性表的末尾即j=l;

4.利用m=GetList(josephus1,j)得出密码作为新的m值

5.接着删除出列的人，长度减少1

6.使i=j，意思为从出列人的下一个人开始报数

7.最后利用函数FindList (josephus2,m)输出出列人的编号

链式存储结构：

typedef int ElemType;

struct LNode { // 定义单链表节点类型

ElemType data; // 存放结点中的数据信息

LNode *next; // 指示下一个结点地址的指针

};

重要函数的算法实现思路：

void InitList (LNode*&H)//初始化单链表

int LengthList (LNode*H)//求单链表长度

bool EmptyList(LNode*H)//判断是否为空

int FindList (LNode*H, ElemType item)//查找给定值元素的位置

ElemType GetList (LNode*H, int pos)//取单链表第 pos 位置上的元素

bool InsertList ( LNode*&H, ElemType item, int pos)//向单链表插入一个元素

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

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

主函数思路：

1.建立一个具有n个链结点

2.找出第1个报数人的位置

3.利用函数FindList (josephus2,m)输出出列人的编号

4.得出密码作为新的m值

5.接着删除出列的人，长度减少1

6.使i=j，意思为从出列人的下一个人开始报数

五. 实验结果与分析

（包括运行结果截图、结果分析等）

六.心得体会

（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）

通过实验，我发现我对循坏链表不是很清楚，所以用链表作约瑟夫环的时候我没有用循环链表的方法做

【附录----源程序】

Test6_seq.h

void InitList(SeqList &L)

{ //初始化线性表

L.MaxSize =10;

L.list = (ElemType *) malloc(L.MaxSize*sizeof(ElemType)) ;

if (L.list==NULL) {

cout<<"动态存储空间用完，退出运行"<<endl;

exit(1);

}

L.size = 0;

}

//判断是否为空

bool EmptyList(SeqList L)

{

return L.size==0;

}

//查找给定值元素的位置

int FindList (SeqList L, ElemType item)

{

for (int i=0; i<L.size; i++)

if (L.list[i]==item)

return i+1;

}

ElemType GetList(SeqList L, int pos)

{ //在线性表L中求序号为pos的元素，该元素作为函数值返回

if ( pos<1 || pos>L.size )

{

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

exit(1);

}

return L.list[pos-1];

}

int LengthList(SeqList L)

{ //求线性表长度

return L.size;

}

//按给定条件pos向线性表删除一个元素

bool DeleteList (SeqList &L, ElemType &item , int pos )

{ int i;

if ( L.size == 0 ) {

cout<<"顺序表已空无数据可删!"<<endl;

return false;

}

if ( pos < -1 || pos > L.size ) {

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

return false;

}

//找删除位置，赋值给pos

if (pos == 0) {

for ( i=0; i <L.size; i++)

if ( item == L.list[i] ) break;

if (i == L.size) return false;

pos = i+1;

}

else if ( pos == -1 ) pos = L.size;

item = L.list [pos-1]; //返回删除元素值

//删除数据元素

for ( i = pos; i < L.size ; i++)

L.list[i-1] = L.list[i];

L.size--;

// 若线性表空余空间太多，重新分配压缩

if (float (L.size) / L.MaxSize < 0.4 && L.MaxSize > 10 )

{

L.list= (ElemType *) realloc(L.list,

L.MaxSize *sizeof(ElemType) / 2 ) ;

L.MaxSize = L.MaxSize / 2;

}

return true;

}

//按给定条件pos向线性表插入一个元素

bool InsertList(SeqList &L, ElemType item, int pos)

{

if(pos<-1 || pos>L.size+1){

cout<<"pos值无效！"<<endl;return false;

}

int i;

if(pos==0){

for(i=0;i<L.size;i++)

if(item<L.list[i]) break;

pos=i+1;

}

else if(pos==-1) pos=L.size+1;

if(L.size==L.MaxSize){

int k=sizeof(ElemType);

L.list =(ElemType*)realloc(L.list,2*L.MaxSize*k);

if(L.list ==NULL){

cout<<"动态可分配的储存空间用完，退出运行！"<<endl;

exit(1);

}

L.MaxSize=2*L.MaxSize;

}

for(i=L.size-1;i>=pos-1;i--)

L.list[i+1]=L.list[i];

L.list[pos-1]=item;

L.size++;

return true;

}

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))

{

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)

{

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;

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;

}

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

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;

}

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; //删除非表头结点，即cp所指的结点

free(cp);

return true;

}

Test6_Link.cpp

#include <iostream.h>

#include <stdlib.h>

typedef int ElemType;

struct LNode { // 定义单链表节点类型

ElemType data; // 存放结点中的数据信息

LNode *next; // 指示下一个结点地址的指针

};

#include "test6_Link.h"

void main()

{

LNode *p, *newnode;

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

InitList ( p);

InitList (newnode);

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

cin>>n;

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

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

cin>>x;

InsertList (p, x, j);

InsertList (newnode, x,j);

}

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

cin>>i>>m;

while(!EmptyList(p))

{

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

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

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

j=l;

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

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

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

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

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

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

}

相关推荐

北理工数据结构第二章实验报告

第二篇：数据结构基础实验6

专栏推荐