线性表及其应用实验报告

数据结构实验报告

实验名称：线性表及其应用 班 级：12级电气本2 学 号：2012081227 姓 名：赵雪磊 指导教师：梁海丽 日 期：2013年9月9日

数学与信息技术学院

一、 实验目的

1、掌握线性表的概念，理解线性表的顺序、链式存储。

2、掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。

二、 实验要求

1、建立顺序存储的线性表，并对之进行插入、删除操作。 2、建立链式存储的线性表，并对之进行插入、删除操作。；

三、 算法描述

#include #include

#include "myList.h"

using namespace std;

template class Link { public: T }

// 【代码2.7】 单链表的类型定义 template

class lnkList : public List { protected:

Link* head, tail; lnkList();

// 单链表的头、尾指针

public:

// 构造函数 // 析构函数 // 判断链表是否为空

~lnkList(); Link }

Link(Link* nextValue = NULL) { }

next = nextValue;

// 具有一个参数的Link 构造函数

data;

// 用于保存结点元素的内容

* next;

// 指向后继结点的指针

Link(const T info, Link* nextValue = NULL) { // 具有两个参数的Link 构造函数

data = info; next = nextValue;

bool isEmpty(); void clear();

// 将链表存储的内容清除，成为空表

// 在表尾添加一个元素value ，表的长度增1

// 在位置p 上插入一个元素value ，表的长度增1 // 删除位置p 上的元素，表的长度减 1

// 查找值为value 的元素，并返回第1次出现的位置

int length(); // 返回此顺序表的当前实际长度 bool insert(int p, T value); bool delete(int p);

int getPos(const T value);

bool append(T value);

}

template

class lnkList:: lnkList() { }

template

class lnkList:: ~lnkList() { }

template

int count = 0; if (i == -1)

return head;

// 若i 为0则定位到第一个结点

// i为-1则定位到" 虚" 头结点

// 假定线性表的元素类型为T

Link lnkList :: setPos(int i) { Link *p;

Link tmp; tmp = head; }

head = head->next; delete tmp;

while (head != NULL) {

head = tail = new Link; p = head->next;

p = p-> next;

while (p != NULL && count

count++; };

return p; }

template Link *p, *q; q = new Link; p = setPos(i-1); if (p == NULL )

{

// p是第i 个结点的前驱

// 假定线性表的元素类型为T

bool lnkList :: insert (int i, T value) {

// 指向第 i 结点，i ＝0,1, …，当链表中结点数小于i 时返回NULL

cout

}

q->next = p->next; q->data = value; p->next = q;

// 插入点在链尾，插入结点成为新的链尾

if (q->next == NULL ) tail = q;

}

// delete a node from singly linked list template Link *p, *q; p = setPos(i-1); if (p == NULL )

{

// p是第i 个结点的前驱

// 假定线性表的元素类型为T

bool lnkList :: delete(int i) {

cout

// q是真正待删结点

// 待删结点为尾结点，则修改尾指针

}

q = p->next;

if (q == tail)

tail = p;

// 删除结点q 并修改链指针

if (q != NULL) {

delete q;

p->next = q->next;

}

return true; }

template

// 假定顺序表的元素类型为T

void lnkList :: print() { while (head != NULL) { }

cout data;

// 从位置p 开始每个元素左移直到curLen, tmp = head;

}

head = head->next;

cout

四、 程序清单

#include

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int ElemType;

#define LIST_INIT_SIZE 10 #define LISTINCREMENT 2 typedef struct shunxubiao{ ElemType *list; int size;

int Maxsize; }SqList;

int InitList_Sq(SqList &L) { // 构造一个空的线性表L 。

L.list = new ElemType[LIST_INIT_SIZE];

if (!L.list) return OVERFLOW; // 存储分配失败 L.size = 0; // 长度

为0

L.Maxsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq int InsertList_Sq(SqList &L, int i, ElemType e) { ElemType *p,*q;

if (i L.Maxsize+1) return ERROR; q = &(L.list[i-1]); // q指示插入位置 for (p=&(L.list[L.Maxsize-1]); p >= q; --p) *(p+1) = *p;

// 插入位置及之后的元素右移

*q = e; // 插入e ++L.size; // 表长增1 return OK; } // ListInsert_Sq

int LocateElem_Sq(SqList L, ElemType e) {

// 在顺序表中查询数据元素e ，若存在，则返回它的位序，否则返回 0 int i = 1; // i 的初值为第 1 元素的位序 ElemType *p = L.list; // p 的初值为第 1 元素的存储位置 while (i

if (i

Status InsertList_Sq(SqList &L,ElemType e,ElemType f,ElemType g) { int i=LocateElem_Sq(L,e); int j=LocateElem_Sq(L,f); if(i==j-1) { InsertList_Sq(L,j,g); return OK; }

else return ERROR; }

int GetList_Sq(SqList L,int i) { if(i>0 && i

Status ListDelete_Sq(SqList &L, int i, ElemType &e) { ElemType *p,*q;

if ((i L.Maxsize)) return ERROR; p = &(L.list[i-1]); // p为被删除元素的位置 e = *p; // 被删除元素的值赋给e q = L.list+L.size-1; // 表尾元素的位置 for (++p; p

*(p-1) = *p; // 被删除元素之后的元素左移 --L.size; // 表长减1 return OK; } // ListDelete_Sq

void Create_Sq(SqList &L) { cout>count;

for(int i=0;i>L.list[i]; ++L.size; } }

void Print_Sq(SqList &L) { cout

void main() { SqList myList;

ElemType e,f,g,sc; InitList_Sq(myList); Create_Sq(myList); cout>g;

cout>e>>f; if(!InsertList_Sq(myList,e,f,g)) cout

cout>wx;

if(!ListDelete_Sq(myList,wx,sc)) cout

五、 实验结果与分析

六、 实验心得

此次上机实验，不仅对此次编译程序的算法思想有了新的认识，还让我深刻的体会到了线性表的重要性以及其应用的方便，并且对指针加深了映象，应用了书本中的算法思想，对我以后的编译以及完成新的程序有很大的帮助。

数据结构实验报告

实验名称：线性表及其应用 班 级：12级电气本2 学 号：2012081227 姓 名：赵雪磊 指导教师：梁海丽 日 期：2013年9月9日

数学与信息技术学院

一、 实验目的

1、掌握线性表的概念，理解线性表的顺序、链式存储。

2、掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。

二、 实验要求

1、建立顺序存储的线性表，并对之进行插入、删除操作。 2、建立链式存储的线性表，并对之进行插入、删除操作。；

三、 算法描述

#include #include

#include "myList.h"

using namespace std;

template class Link { public: T }

// 【代码2.7】 单链表的类型定义 template

class lnkList : public List { protected:

Link* head, tail; lnkList();

// 单链表的头、尾指针

public:

// 构造函数 // 析构函数 // 判断链表是否为空

~lnkList(); Link }

Link(Link* nextValue = NULL) { }

next = nextValue;

// 具有一个参数的Link 构造函数

data;

// 用于保存结点元素的内容

* next;

// 指向后继结点的指针

Link(const T info, Link* nextValue = NULL) { // 具有两个参数的Link 构造函数

data = info; next = nextValue;

bool isEmpty(); void clear();

// 将链表存储的内容清除，成为空表

// 在表尾添加一个元素value ，表的长度增1

// 在位置p 上插入一个元素value ，表的长度增1 // 删除位置p 上的元素，表的长度减 1

// 查找值为value 的元素，并返回第1次出现的位置

int length(); // 返回此顺序表的当前实际长度 bool insert(int p, T value); bool delete(int p);

int getPos(const T value);

bool append(T value);

}

template

class lnkList:: lnkList() { }

template

class lnkList:: ~lnkList() { }

template

int count = 0; if (i == -1)

return head;

// 若i 为0则定位到第一个结点

// i为-1则定位到" 虚" 头结点

// 假定线性表的元素类型为T

Link lnkList :: setPos(int i) { Link *p;

Link tmp; tmp = head; }

head = head->next; delete tmp;

while (head != NULL) {

head = tail = new Link; p = head->next;

p = p-> next;

while (p != NULL && count

count++; };

return p; }

template Link *p, *q; q = new Link; p = setPos(i-1); if (p == NULL )

{

// p是第i 个结点的前驱

// 假定线性表的元素类型为T

bool lnkList :: insert (int i, T value) {

// 指向第 i 结点，i ＝0,1, …，当链表中结点数小于i 时返回NULL

cout

}

q->next = p->next; q->data = value; p->next = q;

// 插入点在链尾，插入结点成为新的链尾

if (q->next == NULL ) tail = q;

}

// delete a node from singly linked list template Link *p, *q; p = setPos(i-1); if (p == NULL )

{

// p是第i 个结点的前驱

// 假定线性表的元素类型为T

bool lnkList :: delete(int i) {

cout

// q是真正待删结点

// 待删结点为尾结点，则修改尾指针

}

q = p->next;

if (q == tail)

tail = p;

// 删除结点q 并修改链指针

if (q != NULL) {

delete q;

p->next = q->next;

}

return true; }

template

// 假定顺序表的元素类型为T

void lnkList :: print() { while (head != NULL) { }

cout data;

// 从位置p 开始每个元素左移直到curLen, tmp = head;

}

head = head->next;

cout

四、 程序清单

#include

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int ElemType;

#define LIST_INIT_SIZE 10 #define LISTINCREMENT 2 typedef struct shunxubiao{ ElemType *list; int size;

int Maxsize; }SqList;

int InitList_Sq(SqList &L) { // 构造一个空的线性表L 。

L.list = new ElemType[LIST_INIT_SIZE];

if (!L.list) return OVERFLOW; // 存储分配失败 L.size = 0; // 长度

为0

L.Maxsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq int InsertList_Sq(SqList &L, int i, ElemType e) { ElemType *p,*q;

if (i L.Maxsize+1) return ERROR; q = &(L.list[i-1]); // q指示插入位置 for (p=&(L.list[L.Maxsize-1]); p >= q; --p) *(p+1) = *p;

// 插入位置及之后的元素右移

*q = e; // 插入e ++L.size; // 表长增1 return OK; } // ListInsert_Sq

int LocateElem_Sq(SqList L, ElemType e) {

// 在顺序表中查询数据元素e ，若存在，则返回它的位序，否则返回 0 int i = 1; // i 的初值为第 1 元素的位序 ElemType *p = L.list; // p 的初值为第 1 元素的存储位置 while (i

if (i

Status InsertList_Sq(SqList &L,ElemType e,ElemType f,ElemType g) { int i=LocateElem_Sq(L,e); int j=LocateElem_Sq(L,f); if(i==j-1) { InsertList_Sq(L,j,g); return OK; }

else return ERROR; }

int GetList_Sq(SqList L,int i) { if(i>0 && i

Status ListDelete_Sq(SqList &L, int i, ElemType &e) { ElemType *p,*q;

if ((i L.Maxsize)) return ERROR; p = &(L.list[i-1]); // p为被删除元素的位置 e = *p; // 被删除元素的值赋给e q = L.list+L.size-1; // 表尾元素的位置 for (++p; p

*(p-1) = *p; // 被删除元素之后的元素左移 --L.size; // 表长减1 return OK; } // ListDelete_Sq

void Create_Sq(SqList &L) { cout>count;

for(int i=0;i>L.list[i]; ++L.size; } }

void Print_Sq(SqList &L) { cout

void main() { SqList myList;

ElemType e,f,g,sc; InitList_Sq(myList); Create_Sq(myList); cout>g;

cout>e>>f; if(!InsertList_Sq(myList,e,f,g)) cout

cout>wx;

if(!ListDelete_Sq(myList,wx,sc)) cout

五、 实验结果与分析

六、 实验心得

此次上机实验，不仅对此次编译程序的算法思想有了新的认识，还让我深刻的体会到了线性表的重要性以及其应用的方便，并且对指针加深了映象，应用了书本中的算法思想，对我以后的编译以及完成新的程序有很大的帮助。


相关文章

  • 教师资格证考试目录

    • 高一上学期学必修1.3,下学期学必修2.4,高二上半学期(期中考试前)学必修5,再学选修,其中理科期中考试后期末考试前学选修2-1,文科是选修1-1,到年后第二学期理科在期中考试前学选修2-2,文科是1-2,期中考试后到期末考试理科学选修2 ...查看


  • 试剂分析性能评估模板

    • 胆固醇测定试剂盒 分析性能评估资料 山东高密彩虹分析仪器有限公司 目 录 1 概述 2 胆固醇测定试剂盒及相关信息 3 性能评估资料 3.1 检测限评估资料 3.2 线性范围评估资料 3.3 可报告范围评估资料 3.4 准确性(回收实验)评 ...查看


  • 教育统计学大纲

    • 高纲1428 江苏省高等教育自学考试大纲 28063 教育统计学 南京师范大学编 江苏省高等教育自学考试委员会办公室 Ⅰ 课程的性质与设置目的 <教育统计学>是研究如何整理.分析在包括教育实验.教育调查等教育研究中所获取的数字资 ...查看


  • 自评报告-辽宁石油化工大学理学院

    • 自评报告 辽宁石油化工大学大学理学院 数学系线性代数教研组 二零零九年三月八日 一.教学队伍 1-1课程负责人与主讲教师 课程负责人情况简介 课程负责人 宋岱才,男,1954年1月生,教授. 1982年1月毕业于石油大学(华东)计算数学专业 ...查看


  • 本科生毕业设计手册

    • 中国石油大学胜利学院 本科生毕业设计(论文)手册 题目学生姓名学号专业班级指导教师 2016年3月4日 目录 本科生毕业设计(论文)任务书................................................... ...查看


  • 数据结构A教学大纲

    • 数据结构A 教学大纲 (Data Structures A) 课程编号: 06311360 学 分: 5.0 学 时: 75 (其中:讲课学时:60 实验学时:0 上机学时:15) 先修课程:离散数学.程序设计基础.面向对象程序设计 适用专 ...查看


  • 计量经济学实验报告

    • 大连海事大学 实 验 报 告 实验名称: 计量经济学软件应用 姓 名: 宋 杨 指导教师: 赵冰茹 交通运输管理学院 二○一四 年 十二 月 一. 实验目标 学会常用经济计量软件的基本功能,并将其应用在一元线性回归模型的分析中.具体包括:E ...查看


  • 哈工大无线电定位原理与应用实验报告

    • Harbin Institute of Technology 无线电定位原理实验报告 课程名称: 无线电定位原理与应用 班级: 姓名: 学号: 同组人: 学号: 指导教师: 张云 实验时间: 实验成绩: 哈尔滨工业大学 1. 实验一 调频法 ...查看


  • 奇妙的非牛顿流体[1]

    • 72力 学 与 实 践1998年第20卷 ・身边力学的趣话・ 奇妙的非牛顿流体 王振东 (天津大学力学系, 天津 300072摘要 形形色色的非牛顿流体, 性能及应用. 关键词 , , 无管虹吸, 湍流减阻 牛顿1687年发表了以水为工作介 ...查看


热门内容