数据结构实验指导书学生版

LIAOCHENG UNIVERSITY

数据结构 实验指导书

聊城大学计算机学院

2015年9月

《数据结构》课程实验指导书

目 录

实验一 线性表 ........................................... 1

基本信息 ........................................................ 1

实验预习 ........................................................ 1 实验过程 ........................................................ 1 实验数据和实验结果记录 ......................................... 11 实验结果分析 ................................................... 12

实验二 栈和队列 ........................................ 12

基本信息 ....................................................... 12 实验预习 ....................................................... 12 实验过程 ....................................................... 13 实验数据和实验结果记录 ......................................... 16 实验结果分析 ................................................... 17

实验三 二叉树 .......................................... 17

基本信息 ....................................................... 17 实验预习 ....................................................... 18 实验过程 ....................................................... 18 实验数据和实验结果记录 ......................................... 20 实验结果分析 ................................................... 20

实验四 查找 ............................................ 21

基本信息 ....................................................... 21 实验预习 ....................................................... 21 实验过程 ....................................................... 21 实验数据和实验结果记录 ......................................... 22 实验结果分析 ................................................... 23

I

《数据结构》课程实验指导书

实验一 线性表

基本信息

实验课程：数据结构 课程学分：4

设课形式：非独立 实验项目：线性表 项目学时：4

项目类型：设计

实验预习 实验目的和要求： 1、熟悉C语言集成开发环境； 2、会定义线性表的顺序结构和链式结构； 3、熟悉对线性表的基本操作，如插入、删除等。 实验内容和原理或涉及的知识点： 自己编写程序实现线性表的建立、插入、删除等功能。 实验条件： 具有C语言集成开发环境的计算机 实验设计方案： 设计的顺序表算法有： 1、初始化顺序表； 2、顺序表的插入操作； 3、顺序表的删除操作。 设计的链表算法有： 1、建立链表； 2、链表的插入操作； 3、链表的删除操作； 4、链表数据元素的访问。

实验过程

1、根据实验预习阶段的实验设计方案，顺序表算法伪C代码如下。

typedef struct

1

《数据结构》课程实验指导书

{

ElemType *elem; int length; int listsize; }SqList;

status InitList(SqList &L) {

L.elem=(ElemType *) malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (!L.elem) exit(OVERFLOW); L.length=0;

L.listsize=LIST_INIT_SIZE; return OK; }

status ListInsert_Sq(SqList &L, int i, ElemType e) {

if (i<1||i>L.length+1) return ERROR; if (L.length>=L.listsize) {newbase

=

(ElemType

(L.listsize+LISTINCREMENT)*sizeof(ElemType)) ; if (!newbase) exit (OVERFLOW); L.elem = newbase;

L.listsize=L.listsize+LISTINCREMENT; }

q=&(L.elem[i-1]);

for (p=&(L.elem[L.length-1]);p>=q; --p) *(p+1)=*p;

*q=e; L.length++; return OK; }

status ListDelete_Sq(SqList &L, int i, ElemType &e) {

if ((i<1)||i>L.length) return ERROR; p=&L.elem[i-1]; e=*p;

q=L.elem+L.length-1; for (++p; p<=q; ++p)

*(p-1)=*p; --L.length; return OK;

} //ListDelete_Sq

2、将算法细化为程序代码如下。

2

*)realloc(L.elem,

《数据结构》课程实验指导书

#include #include

#define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LISTINCREMENT 10 #define LIST_INIT_SIZE 20 typedef int status; typedef int ElemType; typedef struct {

ElemType *elem; int length; int listsize; } SqList;

status InitList(SqList *L); // 构造一个空的线性表

status ListInsert_Sq(SqList *L, int i, ElemType e); // 在 L 中第 i 个位置之前插入 e ，L 长度加 1

status ListDelete_Sq(SqList *L, int i, ElemType *e); // 删除 L 的第 i 个数据元素，并用 e 返回其值，L 长度减 1 void visit(ElemType e); // 打印 e 的值到显示器

void ListTraverse(SqList L, void visit(ElemType)); // 依次对 L 的每个元素调用函数 visit(ElemType)

int main() {

int i, j; SqList L; InitList(&L);

puts(\ for (i=1; i<=6; i++) {

scanf(\

ListInsert_Sq(&L, i, j); }

puts(\ ListTraverse(L, visit);

puts(\ scanf(\

puts(\ scanf(\

3

本文来源：https://www.bwwdw.com/article/hi6d.html