SJTU OJ部分题目 2015级数据结构作业

#include 
using namespace std;

class noSpace {};
class outOfBound {};

template 
class seqList {
    private:
        elemType *elem;     // 顺序表存储数组，存放实际的数据结点。
	   	int len;            // 顺序表中的结点个数，亦称表的长度。
        int maxSize;	    // 顺序表的的最大可能的长度。
    public:
	 	seqList （ int initSize ）;	// 构造函数
	   	~seqList （ ）;			    // 析构函数
 		bool isEmpty （ ） const { return （ len == 0 ）; }
            //表为空返回TRUE否则返回FALSE。
        bool isFull （ ） const { return （len == maxSize）; }
            // 表是否已经满，满则返回TRUE，否则FALSE。
        int length （ ） const;  // 表的长度
        elemType get （ int i ） const; 	 // 返回第i个结点的值
        int find （const elemType &e ）;  // 返回值等于e的结点的序号，无则返回0
        int	insert （int i const elemType & e ）;
            // 在第i个位置上插入新的结点（值为e），并
            // 使原来的第i个结点至最后一个结点的序号依次加1。
            // 插入成功返回1，否则为0
        int  remove （ int i elemType & e ）;
            // 若第i个结点存在，删除并将其值放入e
			// 若i 非法，则删除失败，返回0。
        void clear（ ）;    		    // 清空顺序表
   	};


int main（）
{
   	seqList chlist（21）;
     //定义一个SeqList类的对象，其中ElemType定义为char，
     //空间大小为21，即除下标为0的数组元素外，最多可以
     //放20个结点。

	char ctemp;
	int i n result;
	         // 输入一个正整数，并输入 Enter 作为结束标志。

    cout << “number of the elements:“<< endl;
    cin >> n;
    cin.get（ctemp）;	//  将 Enter 抛弃。
	cout << “input the elements:\n“ << endl;

    try {
	// 将字符逐个输入到表chlist中，并依次插入到表尾。
		for （ i=1; i<=n; i++）
		{ cin.get （ ctemp）;  chlist.insert（ i ctemp）; }

        result=chlist.remove（1ctemp）; //删除并获得首结点.
        result=chlist.insert（chlist.length（ ）/2+1 ctemp）;
        // 将删除的首结点插入到中间。

        cout << “output the elements:\n“ << endl;

     	for （ i=1; i<=chlist.length（ ）; i++）
		cout.put（chlist.get（i））;
		// 读取第i个结点的值并输出。
     cout << ‘\n‘;
    } catch （noSpace） {cout<<“no space in the memory“<      catch （outOfBound） {cout<<“index is out of the bounds“<
	return 0;
}

template 
seqList::seqList （ int initSize ）
{	// 构造函数
    if （ initSize > 0 ）
    {
        elem = new elemType[ initSize];			// 申请连续空间，返回空间首地址。
        if （!elem） throw noSpace（）;  // 若申请空间失败，则程序中断。
        len=0;
        maxSize = initSize-1;
    }
}

template 
seqList::~seqList （ ）
{	// 析构函数
    delete [ ] elem; //释放占用的连续空间
}

template 
int seqList::length （ ） const
{	// 返回表的长度。
  	return len;
}

template 
elemType seqList::get （ int i ） const
{	// 读出第i个结点的值并返回。
    if（ （ i < 1） || （ i > len ） ） throw outOfBound（）; // 越界、非法。
  	return elem[i];
}

template 
int seqList::find （ const elemType &e ）
{
    // 按照下标从大到小顺序查找值为e的数组结点的下标并将其返回。
    // elem[0]做哨兵用保证即使查找失败，也可以在哨兵位上能找到值e。
    elem[0]= e; int i = len;   // 初始位置为尾结点所在下标
    while （elem[i] != e ） i--;	// 不等时继续向前比较，找到返回结点下标，否则返回0。
    return i;
}

template 
int seqList