数据结构实验报告
实验一 顺序表的插入和删除
实验目的
1、掌握使用Turbo C上机调试线性表的基本方法；
2、掌握线性表的基本操作：插入、删除在顺序存储结构上的运算。
实验要求
1、认真阅读和掌握本实验的给定的程序；
2、按照你的操作需要，编制程序、上机调试运行程序；
3、保存程序的运行结果，并结合程序进行分析。
实验内容
利用顺序表完成线性表信息的管理。要求首先建立并初始化线性表，并实现增加、删除等功能。
（1） 对给定字母A C D E建立顺序表
（2） 在给定位置插入字母B，形成顺序表A B C D E
（3） 删除字母D，形成表A B C D
实验代码
/* JList.h */
#define _JLLIST_H_
#ifndef BUFFER
#define BUFFER 256
#endif
class JList
{
public:
typedef char* Position;
JList();
bool isEmpty(void);
int length(void);
void insertElementById(int, char);
void append(char);
void rmElementById(int);
// char getElementById(int);
char* toString(void);
~JList();
private:
int LENGTH;
int cap; // Capacity
int maxLength;
Position HEAD;
char *cell;
void reload(void);
};
/* JList.cpp */
#include "JList.h"
#ifndef NULL
#define NULL 0
#endif
#ifndef BUFFER
#define BUFFER 256
#endif
JList::JList()
{
cell = new char[BUFFER];
LENGTH = 0;
HEAD = cell;
cap = 1;
maxLength = cap * BUFFER;
}
int JList::length(void)
{
return LENGTH;
}
void JList::append(char input)
{
if (LENGTH < maxLength)
{
cell[LENGTH] = input;
}
else
{
reload();
cell[LENGTH] = input;
}
++LENGTH;
}
void JList::reload(void)
{
char *newCell;
char *temp;
int ctrlLoop;
++cap;
maxLength = cap * BUFFER;
newCell = new char[maxLength];
for (ctrlLoop = 0; ctrlLoop < LENGTH; ++ctrlLoop)
{
newCell[ctrlLoop] = cell[ctrlLoop];
}
temp = cell;
cell = newCell;
newCell = NULL;
delete(temp);
}
char* JList::toString(void)
{
int ctrlLoop;
char* newStr;
newStr = new char[LENGTH + 1];
for (ctrlLoop = 0; ctrlLoop < LENGTH; ++ctrlLoop)
{
newStr[ctrlLoop] = cell[ctrlLoop];
}
newStr[LENGTH] = '\0';
return newStr;
}
void JList::insertElementById(int position, char input)
{
int newLength;
int cellPos;
int ctrlLoop;
newLength = LENGTH + 1;
if (newLength > maxLength)
{
reload();
}
for (ctrlLoop = LENGTH - 1; ctrlLoop >= position; --ctrlLoop)
{
cell[ctrlLoop + 1] = cell[ctrlLoop];
}
++LENGTH;
cell[position] = input;
}
void JList::rmElementById(int position)
{
int ctrlLoop;
int newLength;
char cache;
newLength = LENGTH - 1;
for (ctrlLoop = position; ctrlLoop < LENGTH; ++ctrlLoop)
{
cell[ctrlLoop] = cell[ctrlLoop + 1];
cache = cell[position];
}
cell[LENGTH - 1] = NULL;
--LENGTH;
}
JList::~JList()
{
delete(cell);
}
/* example.cpp – this is the main document of the App */
#include <iostream>
#ifndef _JLIST_H_
#include "JList.h"
#endif
void output(JList *);
void genAxis(int);
void drawLine(int);
void splash(void);
int main(void)
{
JList L;
char cInput;
int elementId;
splash();
std::cout << " Give me a string to init the list." << std::endl;
std::cout << " String goes here: ";
cInput = getchar();
while (cInput != '\n')
{
L.append(cInput);
cInput = getchar();
}
output(&L);
std::cout << " What do U want to insert?" << std::endl;
std::cout << " Give me a character: ";
std::cin >> cInput;
putchar('\n');
std::cout << " Where do U want to insert?\nGive me the place where U want to insert after." << std::endl;
std::cout << " Give me the element ID: ";
std::cin >> elementId;
L.insertElementById(elementId - 1, cInput);
output(&L);
std::cout << " Which element do you want to remove from the list?" << std::endl;
std::cout << " Give me the element ID: ";
std::cin >> elementId;
L.rmElementById(elementId - 1);
output(&L);
system("pause");
return 0;
}
void output(JList* list)
{
int length;
char *str;
char *axis;
length = list->length();
str = list->toString();
drawLine(length);
genAxis(length);
drawLine(length);
std::cout << ' ' << str << std::endl;
drawLine(41);
putchar('\n');
}
void genAxis(int length)
{
int ctrl_loop;
putchar(' ');
for (ctrl_loop = 0; ctrl_loop < length; ++ctrl_loop)
{
std::cout << ctrl_loop + 1;
}
putchar('\n');
}
void drawLine(int length)
{
int ctrl_loop;
putchar(' ');
for (ctrl_loop = 0; ctrl_loop < length; ++ctrl_loop)
putchar('-');
putchar('\n');
}
void splash(void)
{
std::cout << " Copyright (C) 20## Spinel Studio" << std::endl;
std::cout << " By Andrew Junzki" << std::endl;
putchar('\n');
}
实验二 链表的插入和删除
实验目的
1、掌握使用Turbo C上机调试线性表的基本方法；
2、掌握链表的基本操作：插入、删除和游历的操作。
实验要求
1、认真阅读和掌握本实验的给定的程序；
2、按照你的操作需要，编制程序、上机调试运行程序；
3、保存程序的运行结果，并结合程序进行分析。
实验内容
利用顺序表完成线性表信息的管理。要求首先建立并初始化线性表，并实现增加、删除和游历等功能。
（1） 对给定字母A C D E建立顺序表
（2） 在给定位置插入字母B，形成顺序表A B C D E
（3） 删除字母D，形成表A B C E
实验代码
/* JList.h */
#define _JLIST_H_
class JList
{
private:
class Node
{
public:
char data;
Node* next;
Node* previous;
};
typedef Node* pNode;
typedef pNode List;
typedef pNode Position;
public:
JList();
// Check if the list is empty.
bool isEmpty(void);
// Add an element to the list
void append(char);
// Insert a element ahead of or behind the element got by id.
void insertAfterById(int, char);
// Remove the element got by id.
void rmElementById(int);
// Get a element by id.
Position getElementById(int);
// Get the length of the list.
int length(void);
char* toString(void);
~JList();
private:
int LENGTH;
List HEAD;
Position tail;
// Check if the pointer is at the head or tail of the list.
bool isHead(Position);
bool isTail(Position);
};
/* JList.cpp */
#include "JList.h"
#include <iostream>
JList::JList()
{
HEAD = new Node;
LENGTH = 0;
HEAD->next = NULL;
HEAD->previous = NULL;
tail = HEAD;
}
bool JList::isEmpty(void)
{
if (HEAD->next == NULL || HEAD->previous == NULL)
return true;
else
return false;
}
bool JList::isHead(Position P)
{
if (P->previous == NULL)
return true;
else
return false;
}
bool JList::isTail(Position P)
{
if (P->next == NULL)
return true;
else
return false;
}
void JList::append(char input)
{
Position new_item;
new_item = new Node;
new_item->data = input;
new_item->next = NULL;
new_item->previous = tail;
tail->next = new_item;
tail = tail->next;
++LENGTH;
}
JList::Position JList::getElementById(int id)
{
int ctrl_loop;
Position P;
P = HEAD;
if (id > LENGTH)
return NULL;
for (ctrl_loop = 0; ctrl_loop < id; ++ctrl_loop)
{
P = P->next;
}
return P;
}
void JList::insertAfterById(int id, char insert)
{
Position new_node;
Position TARGET;
TARGET = getElementById(id);
if (TARGET == NULL)
exit(1);
if (isTail(TARGET))
{
append(insert);
return;
}
new_node = new Node;
new_node->data = insert;
new_node->next = TARGET->next;
new_node->previous = TARGET;
TARGET->next = new_node;
++LENGTH;
}
void JList::rmElementById(int id)
{
Position TARGET;
Position prev;
Position next;
TARGET = getElementById(id);
prev = TARGET->previous;
next = TARGET->next;
prev->next = next;
next->previous = prev;
delete(TARGET);
}
char* JList::toString(void)
{
Position ptr;
char *str;
int ctrl_loop;
ctrl_loop = 0;
ptr = HEAD->next;
str = new char[LENGTH + 1];
while (ptr != NULL)
{
str[ctrl_loop] = ptr->data;
ptr = ptr->next;
++ctrl_loop;
}
str[ctrl_loop] = '\0';
return str;
}
int JList::length(void)
{
return LENGTH;
}
JList::~JList()
{
while (tail->previous != NULL)
{
Position cache;
cache = tail;
tail = tail->previous;
delete(cache);
}
delete(tail);
tail = NULL;
}
/* example.cpp – this is the main document of the App */
#include <iostream>
#ifndef _JLIST_H_
#include "JList.h"
#endif
void output(JList *);
void genAxis(int);
void drawLine(int);
void splash(void);
int main(void)
{
JList L;
char cInput;
int elementId;
splash();
std::cout << " Give me a string to init the list." << std::endl;
std::cout << " String goes here: ";
cInput = getchar();
while (cInput != '\n')
{
L.append(cInput);
cInput = getchar();
}
output(&L);
std::cout << " What do U want to insert?" << std::endl;
std::cout << " Give me a character: ";
std::cin >> cInput;
putchar('\n');
std::cout << " Where do U want to insert?\nGive me the place where U want to insert after." << std::endl;
std::cout << " Give me the element ID: ";
std::cin >> elementId;
L.insertAfterById(elementId, cInput);
output(&L);
std::cout << " Which element do you want to remove from the list?" << std::endl;
std::cout << " Give me the element ID: ";
std::cin >> elementId;
L.rmElementById(elementId);
output(&L);
system("pause");
return 0;
}
void output(JList* list)
{
int length;
char *str;
char *axis;
length = list->length();
str = list->toString();
drawLine(length);
genAxis(length);
drawLine(length);
std::cout << ' ' << str << std::endl;
drawLine(41);
putchar('\n');
}
void genAxis(int length)
{
int ctrl_loop;
putchar(' ');
for (ctrl_loop = 0; ctrl_loop < length; ++ctrl_loop)
{
std::cout << ctrl_loop + 1;
}
putchar('\n');
}
void drawLine(int length)
{
int ctrl_loop;
putchar(' ');
for (ctrl_loop = 0; ctrl_loop < length; ++ctrl_loop)
putchar('-');
putchar('\n');
}
void splash(void)
{
std::cout << " Copyright (C) 20## Spinel Studio" << std::endl;
std::cout << " By Andrew Junzki" << std::endl;
putchar('\n');
}
实验三 二叉树的建立
实验目的
1. 掌握二叉树的原理；
2. 掌握二叉树的构造方法。
实验要求
1．认真思考，编制本实验的程序。
2．上机调试、运行本程序。
3．保存程序的运行结果，并结合程序进行分析。
实验内容
实现用字符A,B,C,D,E,F构成的如下二叉树。
实验四 二叉树的遍历
实验目的
1、掌握二叉树的各种遍历算法的原理；
2、掌握中历算法的编程。
实验要求
1、按照你的操作需要，编制程序、上机调试运行程序；
2、保存程序的运行结果，并结合程序进行分析。
实验内容
对实验三给出的二叉树，编程中历的方法把每个元素显示出来
实验代码
/* JBinTree.h */
#pragma once
#define _JBINTREE_H
typedef char DATA;
class JBinTree
{
private:
class Node {
public:
Node* left;
Node* right;
Node* up;
DATA data;
};
typedef Node* pNode;
typedef pNode Position;
public:
JBinTree(char);
Position getNodeByKey(Position, DATA);
bool appendToNode(char, DATA);
bool isTail(Position);
bool getNextNode(char);
void resetPtr(void);
char* toString(void);
void output();
~JBinTree();
private:
Position HEAD;
Position ptr;
int nodeNum;
void lookup(Position);
};
typedef JBinTree* pTree;
/* JBinList.cpp */
#include "JBinTree.h"
#include <iostream>
JBinTree::JBinTree(char data)
{
HEAD = new Node;
HEAD->data = data;
HEAD->up = NULL;
HEAD->left = NULL;
HEAD->right = NULL;
ptr = HEAD;
nodeNum = 0;
}
bool JBinTree::appendToNode(char turn, DATA data)
{
Position newNode;
if (turn == 'L')
{
if (ptr->left == NULL)
{
newNode = new Node;
ptr->left = newNode;
}
else
return false;
}
else if (turn == 'R')
{
if (ptr->right == NULL)
{
newNode = new Node;
ptr->right = newNode;
}
else
return false;
}
else
return false;
newNode->up = ptr;
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
++nodeNum;
return true;
}
JBinTree::Position JBinTree::getNodeByKey(Position P, DATA key)
{
if (P->data == key)
return P;
if (isTail(P))
return NULL;
if (P->left != NULL)
{
Position pos;
pos = getNodeByKey(P->left, key);
if (pos != NULL)
return pos;
}
if (P->right != NULL)
{
Position pos;
pos = getNodeByKey(P->right, key);
if (pos != NULL)
return pos;
}
return NULL;
}
bool JBinTree::getNextNode(char turn)
{
if (turn == 'L')
ptr = ptr->left;
else if (turn == 'R')
ptr = ptr->right;
else
return false;
return true;
}
bool JBinTree::isTail(Position P)
{
if (P->left == NULL && P->right == NULL)
return true;
else
return false;
}
void JBinTree::resetPtr(void)
{
ptr = HEAD;
}
void JBinTree::output(void)
{
Position P;
P = HEAD;
lookup(P);
}
void JBinTree::lookup(Position P)
{
std::cout << P->data << ' ';
if (isTail(P))
return;
if (P->left != NULL)
{
lookup(P->left);
}
if (P->right != NULL)
{
lookup(P->right);
}
}
JBinTree::~JBinTree()
{
}
/* example.h */
#include <iostream>
#ifndef _JBINLIST_H
#include "JBinTree.h"
#endif
int main(void)
{
pTree Tree;
Tree = new JBinTree('A');
Tree->appendToNode('L', 'B');
Tree->appendToNode('R', 'C');
Tree->getNextNode('L');
Tree->appendToNode('L', 'D');
Tree->appendToNode('R', 'E');
Tree->resetPtr();
Tree->getNextNode('R');
Tree->appendToNode('L', 'F');
Tree->output();
system("pause");
return 0;
}
-
数据结构实验报告
实验报告实验课程：数据结构实验项目：实验专业：计算机科学与技术姓名：**学号：***指导教师：**实验时间：20**-12-7重庆…
-
数据结构实验报告(C语言)(强力推荐)
数据结构实验实验内容和目的掌握几种基本的数据结构集合线性结构树形结构等在求解实际问题中的应用以及培养书写规范文档的技巧学习基本的查…
-
数据结构实验———图实验报告
数据结构实验报告目的要求掌握图的存储思想及其存储实现掌握图的深度广度优先遍历算法思想及其程序实现掌握图的常见应用算法的思想及其程序…
-
数据结构实验报告格式
数据结构实验报告格式实验11顺序表的基本操作一实验目的1掌握使用VC上机调试线性表的基本方法2掌握线性表的基本操作插入删除查找等运…
-
数据结构实验报告全集
数据结构实验报告全集实验一线性表基本操作和简单程序1实验目的1掌握使用VisualC60上机调试程序的基本方法2掌握线性表的基本操…
-
数据结构实验报告 线性表的顺序表示和实现
数学与计算科学学院实验报告实验项目名称线性表的顺序表示和实现所属课程名称数据结构A实验类型验证性实验日期20xx年4月5号班级信管…
-
数据结构实验报告
数据结构随堂实验实验报告指导教师姓名学号班级专业计算机科学与技术目录C语言结构体与指针1线性顺序表的实现及操作3串的匹配与替换6线…
-
数据结构顺序表操作实验报告
实验1顺序表的操作一12345678实验要求输入一组整型元素序列建立顺序表实现该顺序表的遍历在该顺序表中进行顺序查找某一元素查找成…
-
数据结构实验一_顺序表的基本操作实验报告
实验一顺序表的基本操作一实验目的掌握线性表的顺序表基本操作建立插入删除查找合并打印等运算二实验要求包含有头文件和main函数1格式…
-
数据结构顺序表实验报告
一、设计人员相关信息1.设计者姓名、学号和班号：12地信2.设计日期：2014.3.上机环境：VC++6.0二、程序设计相关信息1…
-
华中科技大学·计算机13级·数据结构实验报告
课程设计报告课程名称专业班级CS1308学号姓名陈劲龙指导教师报告日期计算机科学与技术目录实验一基于顺序结构的线性表实现11问题描…