数据结构实验报告

1 《数据结构》实验报告一

实验内容： 线性表链式存储结构下基本操作的实现

学号： 姓名：

一、上机实验的问题和要求（需求分析）：

[ 题目 ] 线性表链式存储结构下基本操作的实现（初始化、赋值、取值、插入、删除、

等）。

二、程序设计的基本思想，原理和算法描述：

首先基于线性链表的存储结构建一个单链表（下面的程序实现的是通过头插法逆序建表），

在此基础上实现对单链表的赋值、取值、插入、删除以及两个表的归并，需要注意的是插入

（删除）过程中指针的修改。

三、调试和运行程序过程中产生的问题及采取的措施：

1、注意scanf的格式；

2、在编写程序过程中注意链表指针的正确修改；

四、源程序及注释

[ 源程序 ] 程序名： 1.cpp

#include

#include #include

#define true 1

#define false 0

#define ok 1

#define error 0 #define overflow -2

#define initsize 100

#define increment 10

#define null 0

typedef int status; typedef int elemtype;

typedef struct lnode

{ elemtype data;

struct lnode *next;

}lnode,*linklist; void listtraverse(linklist l)

{//遍历链式表l

2 linklist p=l->next; while(p!=null)

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

p=p->next;}}

void creatlist(linklist &l,int n)

{//逆位序输入个元素的值，建立带表头节点的单链表l int i;linklist p;

l=(linklist)malloc(sizeof(lnode));

l->next=null;

for(i=n;i>0;--i)

{p=(linklist)malloc(sizeof(lnode)); p->data=i;

p->next = l->next;l->next = p;}}//creatlist

status getelem(linklist l,int i,elemtype &e)

{//取带头节点的单链表l中第i个元素，用e返回

int j;linklist p; p=l->next;j=1;

while(p&&j

p=p->next;++j;}

if(!p||j>i)return error;

e=p->data; return ok;}//getelem

status listinsert(linklist &l,int i,elemtype e){

//在带头节点的单链表l中第i个位置前插入元素e

linklist p,s;

int j=0;p=l->next; while(p&&jnext;++j;}

if(!p||j>i-1)return error;

s=(linklist)malloc(sizeof(lnode));

s->data=e;s->next=p->next;

p->next=s; return ok;

}//listinsert

void main()

{linklist l;int i,e,j,f;int n;

printf("请输入节点个数："); scanf("%d",&n);

creatlist(l, n);

printf("建表成功！");

listtraverse(l);

printf("please input the location i:"); scanf("%d",&i);

getelem(l,i,e);

printf("the i th elem is %d\n",e);

3 printf("please input the inserted elem's num and the value: "); scanf("%d %d",&j,&f);

listinsert(l,j,f);

listtraverse( l); }

五、运行结果

如 输入结点个数 为： 5 运行结果： 1 2 3 4 5

又如 输入要查找的元素为： 3

运行结果：3

输入要插入的位置和元素值：3 8

运行结果：1 2 8 3 4 5 输入要删除元素的位置：3

运行结果：8

4 《数据结构》实验报告一

实验内容： 约瑟夫环

学号： 姓名：

一、上机实验的问题和要求（需求分析）：

[ 题目 ] 设有n个人围坐一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出列，如此下去，直到所有人都出列为止。试设

计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打

印出各人的编号。

二、程序设计的基本思想，原理和算法描述：

本程序是在线性链表的基础上实现对循环链表的操作，重点考察循环链表的删除操作；

三、调试和运行程序过程中产生的问题及采取的措施：

1、注意删除元素时指针的变化；

2、注意要删除元素位置的确定；

四、源程序及注释

[ 源程序 ] 程序名： 2.cpp #include

#include

#include

#define ok 1

#define error -1 #define truth 0

typedef int status;

typedef struct Lnode

{ int data ;

struct Lnode *next; }Lnode,*Linklist;

void creatlist_L(Linklist &L,int n)

{ int i;Lnode *p;

L=(Linklist)malloc(sizeof(Lnode));

L->next=L; L->data=1;

for(i=n;i>1;--i)

{ p=(Linklist)malloc(sizeof(Lnode));

p->data=i;

5 p->next=L->next; L->next=p;

}

}

status printf_L(Linklist L)

{ Linklist p=L;int i; int n=8;

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

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

p=p->next;

} printf("\n");

return ok ;

}

void main ()

{ int i,k,n; Lnode * s;

Lnode *L;

printf("the whole number is: ");

scanf ("%d",&n);

creatlist_L(L,n); printf("the number list is:");

printf_L(L);

printf("请输入要删除元素的位置：");

scanf("%d",&k);

s=L; while(s->next!=s)

{

for(i=1;i

s=s->next;

printf("%d\n",s->next->data); s->next=s->next->next;

s=s->next;

}

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

}

五、运行结果

输入环中元素的个数为： 8

运行结果：1 2 3 4 5 6 7 8

删除元素的位置为：3

运行结果为： 3 6 1 5 2 8 4 7

6 《数据结构》实验报告二

实验内容： 栈的基本操作

学号： 姓名：

一、上机实验的问题和要求（需求分析）：

[ 题目 ] 栈的基本操作的实现（初始化、赋值、取值、插入、删除等），要求分别采用顺序和链式存储结构。

二、程序设计的基本思想，原理和算法描述：

在栈的顺序存储结构的基础上实现栈的初始化（即建栈），自此基础上实现其相关操作，包

括赋值、取栈顶元素、进栈、出栈等，重点考察栈的“先进后出”的特性

三、调试和运行程序过程中产生的问题及采取的措施：

（略）

四、源程序及注释

[ 源程序 ] 程序名： 3.cpp #include

#include #include

#define stack_int_size 8

#define stackincrement 10

#define overflow -2

#define error 0 #define ok 1

typedef int status;

typedef int selemtype;

typedef struct

{ selemtype * base; selemtype * top;

int stacksize;

}sqstack;

status initstack(sqstack &s)

{//构造一个空栈s s.base=(selemtype *)malloc(stack_int_size * sizeof(selemtype));

if(!s.base)exit(overflow);

s.top=s.base;

s.stacksize=stack_int_size;