2、编程序实现单链表的各种基本操作，要求主程序采用菜单形式完成各种功能。
InitList DestoryList ListEmpty ListLenghth DispList GetElem LocteElem ListInsert ListDelete
创建线性表 (1,3,5,2,4,10)
插入元素8, 13; 20,12 求长度 查找元素5
删除元素 2 ; 10 求长度
3、编程序实现顺序栈的各种基本操作，要求主程序采用菜单形式完成各种功能。
InitStack ClearStack StackEmpty StackLenghth DispStack Push Pop GetTop
建栈 (1,3,5,2,4) 求长度
进栈8, 9 ; 显示栈中元素
出栈并显示栈中元素
4、编程序实现链栈的各种基本操作，要求主程序采用菜单形式完成各种功能。
InitStack ClearStack StackEmpty StackLenghth DispStack Push Pop GetTop
建栈 (1,3,5,2,4) 求长度
进栈8, 9 ; 显示栈中元素
出栈并显示栈中元素
5、编程序实现顺序队列的各种基本操作，要求主程序采用菜单形式完成各种功能。
InitQueue ClearQueue QueueEmpty QueueLenghth DispQueue EnQueue DeQueue
建立队列(1,3,5,2,4) 求长度;
入队 6
出队到对为空为止
6、编程序实现链栈队列的各种基本操作，要求主程序采用菜单形式完成各种功能。
InitQueue ClearQueue QueueEmpty QueueLenghth DispQueue EnQueue DeQueue
建立队列(1,3,5,2,4) 求长度;
入队 6
出队到对为空为止
7、编程序实现二叉树的各种基本操作，要求主程序采用菜单形式完成各种功能。
CreatBTNode FindNode LchildNode RchildNode Nodes LeafNodes
创建二叉树:
查找元素C显示其左孩子；
题一：
建立三个文件分别copy进去，按以下的划分。
#include <iostream>
#ifndef LIST
#define LIST
const int CAPACITY = 1024;
typedef int ElementType;
class List
{
public:
List();
bool empty() const;
void insert(ElementType item, int pos);
void erase(int pos);
void display(ostream & out) const;
private:
int mySize; // current size of list stored in myArray
ElementType myArray[CAPACITY]; // array to store list elements
}; //--- end of List class
//------ Prototype of output operator
ostream & operator<< (ostream & out, const List & aList);
#endif
#include <cassert>
using namespace std;
#include "List.h"
//--- Definition of class constructor
List::List()
: mySize(0)
{}
//--- Definition of empty()
bool List::empty() const
{
return mySize == 0;
}
//--- Definition of display()
void List::display(ostream & out) const
{
for (int i = 0; i < mySize; i++)
out << myArray[i] << " ";
}
//--- Definition of output operator
ostream & operator<< (ostream & out, const List & aList)
{
aList.display(out);
return out;
}
//--- Definition of insert()
void List::insert(ElementType item, int pos)
{
if (mySize == CAPACITY)
{
cerr << "*** No space for list element -- terminating "
"execution ***\n";
exit(1);
}
if (pos < 0 || pos > mySize)
{
cerr << "*** Illegal location to insert -- " << pos
<< ". List unchanged. ***\n";
return;
}
// First shift array elements right to make room for item
for(int i = mySize; i > pos; i--)
myArray[i] = myArray[i - 1];
// Now insert item at position pos and increase list size
myArray[pos] = item;
mySize++;
}
//--- Definition of erase()
void List::erase(int pos)
{
if (mySize == 0)
{
cerr << "*** List is empty ***\n";
return;
}
if (pos < 0 || pos >= mySize)
{
cerr << "Illegal location to delete -- " << pos
<< ". List unchanged. ***\n";
return;
}
// Shift array elements left to close the gap
for(int i = pos; i < mySize; i++)
myArray[i] = myArray[i + 1];
// Decrease list size
mySize--;
}
//以下是main函数文件：****/
#include <iostream>
using namespace std;
#include "List.h"
int main()
{
// Test the class constructor
List intList;
cout << "Constructing intList\n";
// Test empty() and output of empty list
if (intList.empty())
cout << "Empty List: \n"
<< intList << endl; // Test output of empty list
// Test insert()
for (int i = 0; i < 9; i++)
{
cout << "Inserting " << i << " at position " << i/2 << endl;
intList.insert(i, i/2); // -- Insert i at position i/2
//Test output
cout << intList << endl;
}
cout << "List empty? " << (intList.empty() ? "Yes" : "No") << endl;
cout << "\nTry to insert at position -1" << endl;
intList.insert(0, -1);
cout << "\nTry to insert at position 10" << endl;
intList.insert(0, 10);
// Test erase()
int index;
cout << endl;
while (!intList.empty())
{
cout << "Give an index of a list element to remove: ";
cin >> index;
intList.erase(index);
cout << intList << endl;
}
cout << "List is empty" << endl;
cout << "\nInserting " << CAPACITY<< " integers\n";
for (int i = 0; i < CAPACITY; i++)
intList.insert(i, i);
cout << "Attempting to insert one more integer:\n";
intList.insert(-1, 0);
}
题2：
#include <iostream>
using namespace std;
#include "Stack.h"
//--- Definition of Stack constructor
Stack::Stack()
: myTop(-1)
{}
//--- Definition of empty()
bool Stack::empty() const
{
return (myTop == -1);
}
//--- Definition of push()
void Stack::push(const StackElement & value)
{
if (myTop < STACK_CAPACITY - 1) //Preserve stack invariant
{
++myTop;
myArray[myTop] = value;
}
else
{
cerr << "*** Stack full -- can't add new value ***\n"
"Must increase value of STACK_CAPACITY in Stack.h\n";
exit(1);
}
}
//--- Definition of display()
void Stack::display(ostream & out) const
{
for (int i = myTop; i >= 0; i--)
out << myArray[i] << endl;
}
//--- Definition of top()
StackElement Stack::top() const
{
if ( !empty() )
return (myArray[myTop]);
else
{
cerr << "*** Stack is empty -- returning garbage value ***\n";
return (myArray[STACK_CAPACITY - 1]);
}
}
//--- Definition of pop()
void Stack::pop()
{
if ( !empty() )
myTop--;
else
cerr << "*** Stack is empty -- can't remove a value ***\n";
}