《数据结构》 实验报告1

xxx 实验报告

课程 名称 系部 实验 时间 评语 指导教师： 数据结构 班级 实验实验一 线性表操作 名称 姓名 学号 地点 机位 成绩 2012 年10 月15 日21 时30 分～ 时 分 一、实验目的

1.熟悉上机环境，进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。

3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容

1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤

1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。

2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。

3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用

1) 程序1的主要代码(附简要注释)

#include using namespace std; #define MAXSIZE 1024 //#define OVERFLOW 0 //#define NULL 0 #define OK 1

#define MAXSIZE 1024

typedef int elemtype; /* 线性表中存放整型元素 */ typedef struct //结构定义头文件sqlist.h { elemtype vec[MAXSIZE];

int len; /* 顺序表的长度 */ }sqlist;

int initlist(sqlist *L,int k) { int i;

printf(\ for( i=0;i

scanf(\同效,注意输入时地址\ return OK; }

// 以下是整个源程序：#include\int main() { int i,n;

sqlist *L,a; //定义表的变量

printf(\ scanf(\

L=&a; //指针引用,如果去掉L=&a语句，会出现什么结果？ L->len=n; //将长度传给len initlist(L,n);

printf(\ for(i=0;i

printf(\

printf(\ system(\ return 0; }

2) 程序2的主要代码(附简要注释)

/*顺序表的插入

利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31} 然后在第i个位置插入元素68。

注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序

本程序实现的是在第i个元素之前插入新的元素(顺序表中元素的次序）的区别。*/ #include using namespace std; //#include\

#define MAXSIZE 1024 //#define OVERFLOW 0 #define ERROR 0 #define OK 1

#define MAXSIZE 1024

typedef int elemtype; /* 线性表中存放整型元素 */ typedef struct //结构定义头文件initlist.h { elemtype vec[MAXSIZE];

int len; /* 顺序表的长度 */ }sqlist;

int initlist(sqlist *L,int k) { int i;

printf(\ for( i=0;i

scanf(\同效,注意输入时地址\ return OK; }

/*----------------------------------------------*/ int insert(sqlist *L,int i,int x)

//插入运算，将值为x的元素插入到第i个元素之前 { int j;

if((*L).len>=MAXSIZE)

{ printf(\ return ERROR; }

else if((i<1)||(i>(*L).len+1))

{ printf(\ return ERROR; }

else{ for(j=(*L).len-1;j>=i-1;j--) //L->len (*L).vec[j+1]=(*L).vec[j]; //元素后移 (*L).vec[i]=x; //插入元素区别：i-1 (*L). len++; //表长度增加1

return OK; } }

int main() { int n,i,x; sqlist *L,a;

printf(\ scanf(\输入表长度 L=&a; L->len=n; initlist(L,n);

printf(\ scanf(\

printf(\ scanf(\ if(insert(L,i,x))

{ printf(\ printf(\ for(i=0;ilen;i++) printf(\ } else

printf(\ system(\ return 0; }

3) 程序3的主要代码(附简要注释)

#include #include #include typedef struct tagNODE{ int value;

struct tagNODE *next; }NODE, *LPNODE;

void Input(LPNODE pHead) {

LPNODE pNext, pTmp; char ch;

if(!pHead) { return; } pNext = pHead;

while(pNext && pNext->next){ pNext = pNext->next; }

while(1){

printf(\

pTmp = (LPNODE)malloc(sizeof(NODE)); memset(pTmp, 0, sizeof(NODE)); pNext->next = pTmp;

scanf(\ fflush(stdin);

printf(\ ch = getchar();

if(ch != 'y' && ch !='Y'){ break; }

pNext = pNext->next;