南昌大学，数据结构，实验报告

实 实验课程：学生姓名：学 号：专业班级：

验 报 告

数 据 结 构 某同学 6100410235

计科103班

2012年 6月 1日

1

目 录

实验一 线性表及其应用??????????????3 实验二 栈和队列?????????????????12 实验三 二叉树及其应用??????????????19 实验四 实验五

图的运用?????????????????24 查找 排序???????????????? 29 2

南昌大学实验报告

---（1）线性表及其应用

学生姓名： 某同学 学 号： 6100410235 专业班级： 计科103班 实验类型：□ 验证 □ 综合 ■ 设计 □ 创新 实验日期： 2012-3-8 实验成绩：

一．实验目的

帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。

二．问题描述

1． 构造一个空的线性表L；

2． 在线性表L的第i个元素之前插入新的元素e； 3． 在线性表L中删除第i个元素，并用e返回其值。

三．实验要求

1．分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。

2．在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。

四．实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境

五．实验步骤

1．用学生选择的语言，设计出线性表的顺序和链表存储结构； 1． 设计出这两种存储结构下的线性表的插入、删除算法； 2． 用所选择的语言实现算法；

3． 测试程序,并对不同存储结构下的算法分析。

六．测试数据和分析

1．插入操作：

输入数据：L = ( ) ListInsert (L, 1, 'k'), 正确结果：L = (k)

输入数据：L = (EHIKMOP) ListInsert (L, 9, 't'), 正确结果：return ERROR; L = (EHIKMOP)

3

输入数据：L = (ABCEHKNPQTU) ListInsert(L, 4, 'u'), 正确结果： L = (ABCuEHKNPQTU) 2．删除操作：

输入数据：L = () ListDelete (L, 1, e) 正确结果：ERROR, L = ()

输入数据：L = (DEFILMNORU) ListDelete_Sq(L, 5, e) 正确结果： L = (DEFIMNORU), e='L' 输入数据：L = (CD) ListDelete_Sq(L, 1, e) 正确结果： L = (D), e = 'C'

3．如线性表有n个结点，对两种存储结构下插入和删除的时间复杂度进行分析。

七．实验结果

顺序存储C程序： #include #include typedef int elemtype; typedef int status; #define ERROR -1 #define OK 1

#define OVERFLOW 2008 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ elemtype *elem; int length; int listsize; }sqlist;

status InitList_Sq(sqlist *L){ //构造一个空的线性表L elemtype *a=0; a=(elemtype *)malloc(LIST_INIT_SIZE*sizeof(elemtype)); L->elem=a; if(!(*L).elem)return OVERFLOW; (*L).listsize=LIST_INIT_SIZE; (*L).length=0; return OK; }

status List_Insert(sqlist *L,int i,elemtype e){ //在第i个元素之前插入元素e

elemtype * p=0; elemtype *q=0;elemtype * newbase=0;

4