// 顺序表.cpp -- 最基本的顺序表(经典顺序表)
// 完整的class.
// List abstract class -- 线性表的C++抽象类声明
template<class Elem> class List()
{
public:
// Reinitialize the list. the client is responsible for
// reclaiming the storange used by the list elements.
virtual void clear() = 0;
// Insert an element at the front of the right partition.
// Return true if successful, false if the list is full.
virtual bool insert(const Elem&) = 0;
// Append an element at the end of the right partition.
// Return true if successful, false if the list is full.
virtual bool append(const Elem&) = 0;
// Remove the first element of right partition. Return
// true if successful, false if the list is empty.
// The element removed is returned in the parameter.
virtual bool remove(Elem&) = 0;
// Place fence at list start, making left partition empty.
virtual void setStart() = 0;
// Place fence at list end, making right partition empty.
virtual void setEnd() = 0;
// Move fence one step left; no change if already at start.
virtual void prev() = 0;
// Move fence one step right; no change if already at end
virtual void next() = 0;
// Return length of left partition
virtual int leftLength() const = 0;
// Return length of right partition
virtual int rightLength() const = 0;
// If pos or more elements are in the list, set the size
// of left partition to pos and return true. Otherwise,
// do nothing and return false.
virtual bool setPos(int pos) = 0;
// Return in first parameter the first element of the
// right partition. Return true if successful, false
// if the right partition is empty.
virtual bool getValue(Elem&) const = 0;
// print the contents of the list
virtual void print() const = 0;
};
// Array-based list implementation -- 线性表的实现
template <class Elem>
class Alist: public List<Elem> //继承
{
private:
int maxSize; // Maximum size of list
int listSize; // Actual number of elements in list
int fence; // Position of fence
Elem* listArray; // Array holding list elementss
public:
AList(int size = DefaultListSize) // constructor
{
maxSize = size;
lastSize = fence = 0;
listArray = new Elem[maxSize];
}
~AList() { delete [] listArray;} // Destructor
void clear()
{
delete [] listArray;
listSize = fence = 0;
listArray = new Elem[maxSize];
}
bool insert(const Elem&);
bool append(const Elem&);
bool remove(Elem&);
void setStart() { fence = 0;}
void setEnd() { fence = listSize;}
void prev() { if (fence != 0) fence--;}
void next() { if (fence <= listSize) fence++;}
int leftLength()const {return fence;}
int rightLength()const {return lastsize - fence;}
bool setPos(int pos)
{
if ((pos >= 0) && (pos <= listSize)) fence = pos;
return (pos >= 0) && (pos <= listSize);
}
bool getValue(Elem& it)const()
{
if (rightLength() == 0) return flase;
else { it = listArray[fence]; reutrn true;}
}
void print()const
{
int temp = 0;
cout << " < ";
while (temp < fence) cout << listArray[temp++] << " ";
cout << " | ";
while (temp < ListSize) cout << listarray[temp++] << " ";
cout << " >\n";
}
};
template <class Elem> // Insert at front of right partition
bool Alist <Elem>::insert(const Elem& item)
{
if (listsize == maxSize) return flase; // List is full
for (int i = listsize; i > fence; i--) // Shift Elem up
listArray[i] = listArray[i-1]; // to make room
listArray[fence] = item;
listSize++; // Increment list size
return true;
}
// Remove and return first Elem in right partition
template <class Elem> bool AList <Elem>::remove(Elem& it)
{
if (rightLength() == 0) return false; // nothing in right
it = listArray[fence]; // copy removed elem
for (int i = fence; i < listSize -1; i++) // Shift them down
listArray[i] = listArray[i + 1];
listSize--; // Decrement Size
return true;
}
// 看完以后就觉得,原来掌握顺序表是很简单的事,只需要掌握几个点;
// 其中最重要的思想是确定位置。
// 知道现在的位置,开始的位置,结束的位置,数组的大小,该位置左右的大小。
分享到:
相关推荐
顺序表基本操作 顺序表实现 顺序表
编写一个程序,实现顺序表的各种基本运算,并在此基础上完成以下功能: 1) 初始化顺序表; 2) 依次采用尾插入法插入a,b,c,d,e元素; 3) 输出顺序表L; 4) 输出顺序表L的长度; 5) 判断顺序表L是否为空; 6) 输出顺序...
使用c++实现顺序表的基本操作: 1、顺序表的初始化 2、顺序表的长度 3、顺序表插入元素 4、删除顺序表元素 5、遍历顺序表 6、查找顺序表元素
顺序表及其应用 顺序表及其应用 顺序表及其应用 顺序表及其应用 顺序表及其应用 顺序表及其应用 顺序表及其应用
(1)初始化顺序表L (2)从标准输入(键盘)逐个数据输入a,b,c,d,e元素 ,建立顺序表 (3)输出顺序表L (4)输出顺序表L的长度 (5)判断顺序表L是否为空 (6)输出顺序表L的第3个元素 (7)输出元素a的位置...
本资源是:线性表中的顺序表的一些操作,包括初始化顺序表、建立顺序表、删除顺序表、在顺序表中插入元素,在顺序表中删除元素、判断空的等一些基本操作。
设计一个包含学生基本信息(学号,姓名,成绩)的顺序表,编程完成如下功能: ⑴ 初始化顺序表 L: 根据用户指定的学生数,逐个输入学生信息; ⑵ 打印表中所有学生信息: 逐个显示表中所有学生的基本信息; ⑶ 判断...
用类实现顺序表基本运算(非结构体 更强大)
顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数据元素...
1.编写程序实现顺序表的下列基本操作: (1)初始化顺序表La。 (2)将La置为空表。 (3)销毁La。 (4)在La中插入一个新的元素。 (5)删除La中的某一元素。 (6)在La中查找某元素,若找到,则返回它在La中第一次出现...
/*构造一张新的顺序表*/ int ListLength_Sq(List l); /*求顺序表L的长度*/ void GetElem_Sq(List *L,int i,ElemType e); /*获取顺序表L的第i个元素*/ int EqualList(ElemType e1,ElemType e2); /*判断数据元素e1,e2...
顺序表头文件顺序表头文件顺序表头文件顺序表头文件
顺序表操作基本代码。帮助顺序表的学习和代码的编写等。
(1) 建立一个顺序表,含有n个数据元素。 (2) 输出顺序表及顺序表的长度。 (3) 在顺序表给定的位置i,插入一个值为x的结点。 (4) 在顺序表中删除值为x的结点或者删除给定位置i的结点。 (5) 将顺序表逆置,...
1,利用顺序表的操作实现以下函数: (1)从顺序表中删除具有最小值的元素,并由函数返回被删除元素的值。空出的位置由最后一个元素填补,若顺序表为空,则显示出错信息,并退出运行。 (2)在顺序表的第i个位置之后...
顺序表的基本操作及实现顺序表的基本操作及实现顺序表的基本操作及实现
编写一个完整的程序,实现顺序表的生成、插入、删除、输出等基本运算。