数据结构、算法与应用(C++描述)(第二版)第五章习题解答

1

1)false
2)4
3) a,c,异常，异常
4)0,2,-1
5）bcd,abd,abc
6)eabcd,abfcd,abcgd,abcdh,异常，异常

3

template
void changeLength2D(T**& a, int oldRows, int oldColumns,
	int newRows, int newColumns)
{
	if (newRows < 0 || newColumns < 0)
		throw illegalParameterValue("new length must be >= 0");
	
	T** temp = new T * [newRows];
	int i;
	for (i = 0; i != newColumns; ++i)
		temp[i] = new T[newColumns];

	int rows = std::min(oldRows, newRows);
	int columns = std::min(oldColumns, newColumns);
	for (i = 0; i != rows; ++i)
		std::copy(a[i], a[i] + columns, temp[i]);

	for (i = 0; i != columns; ++i)
		delete[] a[i];
	delete[] a;
	a = temp;
}
//这里附带官方解答：[https://www.cise.ufl.edu/~sahni/dsaac/public/exer/c5/e3.htm]

4

template
void arrayList::insert(int theIndex, const T& theElement, int spaceSize)
{
	if (theIndex < 0 || theIndex > listSize || spaceSize5

template
void arrayList::trimToSize()
{
	if (listSize == arrayLength)
		return;
	ir(listSize == 0)
	{
		delete[] element;
		element = new T[1];
		arrayLength = 1;
		return;
	}

	changeLength1D(element, listSize, listSize);
	arrayLength = listSize;
}
//复杂度：O(listSize)



6


template
void arrayList::setSize(int newSize)
{
	if (newSize <= listSize)
		return;
	changeLength1D(element, listSize, newSize);
	arrayLength = newSize;
}
//复杂度：O(newSize)



7


template
T& arrayList::operator[](int index)
{
	checkIndex(index);
	return element[index];
}



8


//类内声明
template
	friend bool operator==(const arrayList& lhs, const arrayList& rhs);
//实现
template
bool operator==(const arrayList& lhs, const arrayList& rhs)
{
	if (lhs.listSize != rhs.listSize)
		return false;
	for (int i = 0; i != lhs.listSize; ++i)
		if (lhs.element[i] != rhs.element[i])
			return false;
	return true;
}
//非友元
template
 bool arrayList::operator==(const arrayList& rhs)
{
	if (listSize != rhs.listSize)
		return false;
	for (int i = 0; i != listSize; ++i)
		if (element[i] != rhs.element[i])
			return false;
	return true;
}



9


//友元
template
bool operator!=(const arrayList& lhs, const arrayList& rhs)
{
	return !(lhs == rhs);//需先重载operator==
}
//非友元
template
 bool arrayList::operator!=(const arrayList& rhs)
{
	return !(*this == rhs);
}



10


template
 bool arrayList::operator<(const arrayList& rhs)
{
	bool state = true;
	for (int i = 0; i != listSize && i != rhs.listSize; ++i)
		if (this->element[i] > rhs.element[i])
			state = false;
	return state;
}



11


template
 void arrayList::push_back(const T& theElement)
{
	if (listSize == arrayLength)
	{
		changeLength1D(element, listSize, 2 * arrayLength);
		arrayLength *= 2;
	}
	element[listSize] = theElement;
	++listSize;
}



12


template
 void arrayList::pop_bake()
{
	element[--listSize].~T();
}



13


template
 void arrayList::swap(arrayList& theList)
{
	std::swap(listSize, theList.listSize);
	std::swap(arrayLength, theList.arrayLength);
	std::swap(element,theList.element);
}
//O(1)



14


...
template
 void arrayList::reserve(int theCapacity)
{
	int old = arrayLength;
	arrayLength = std::max(old, theCapacity);
	if (old == arrayLength)
		return;
	else
		changeLength1D(element, arrayLength, theCapacity);
}
...
    
int main()
{
	arrayList a(3);
	std::cout << a.capacity() << std::endl;
	a.reserve(4);
	std::cout << a.capacity() << std::endl;
	a.reserve(5);
	std::cout << a.capacity() << std::endl;
	a.reserve(4);
	std::cout << a.capacity() << std::endl;
	return 0;
}



15


template
 void arrayList::set(int theIndex, const T& theElemenet)
{
	checkIndex(theIndex);
	element[theIndex] = theElemenet;
}



16


template
 void arrayList::clear()
{
	for (int i = 0; i < listSize; ++i)
		element[i].~T();
	listSize = 0;
}



17


template
 void arrayList::removeRange(int start, int end)
{
	if (start<0 || end>listSize)
		throw illegalIndex();
	if (start >= end)
		return;
	std::copy(element + end, element + listSize, element + start);
	int newSize = listSize - end + start;
	for (int i = newSize; i < listSize; ++i)
		element[i].~T();
	std::cout << "element :" << element[newSize] << std::endl;
	listSize  = newSize;
}



18


template
 int arrayList::lastIndexOf(const T& theElement) const
{
	int theIndex, thePos = -1;
	do
	{
		theIndex = thePos;
		thePos =
		(int)(std::find(element + theIndex + 1, 
			element + listSize, theElement) - element);

	} while (thePos != listSize);
	return  (theIndex == listSize) ? -1 : theIndex;
}



19






20


1)
template
 void arrayList::removedSize(int initialCapacity)
{
	if (listSize <= (arrayLength / 4))
		changeLength1D(element, arrayLength, std::max(arrayLength / 2, initialCapacity));
}



21






22


1)
//24题需要有参转置，见24
template
 void arrayList::reverse()
{
	int k = 0;
	while (k < listSize / 2)
	{
		std::swap(element[k], element[listSize - k - 1]);
		++k;
	}
}
4)
template
	friend void reverse(arrayList& theList) { theList.reverse(); }
//main() -> reverse(a);



23


template
 void arrayList::leftShift(int i)
{
	std::copy(element + i, element + listSize, element);
	for (int index = listSize - i; index != listSize; ++index)
		element[index].~T();
	listSize = listSize - i;
}

//main()
int main()
{
	arrayList a(3);
	a.insert(0, 1);
	a.insert(1, 2);
	a.insert(2, 3);
	a.push_back(2);
	a.push_back(5);
	a.output(std::cout);
	a.leftShift(2);
	a.output(std::cout);
	return 0;
}



24


template
 void arrayList::reverse(int first, int end)
{//注意reverse[frist,end)
	while (first < (first + end) / 2)
	{
		--end;
		std::swap(element[first], element[end]);
		++first;
	}
}

template
 void arrayList::circularShift(int i)
{//把element拆解成两个以i为界限序列
	//注意reverse[frist,end)
	reverse(0, i);
	reverse(i, listSize );
	reverse(0, listSize );
}



25


template
 void arrayList::half()
{
	for (int i = 0; i < listSize; i += 2)
		element[i / 2] = element[i];
	int newSize = (listSize + 1) / 2;
	for (int i = newSize; i < listSize; ++i)
		element[i].~T();
	listSize = newSize;
}



26






27


template
class arrayList : public linearList
{
public:
    ...
	class iterator;
	iterator begin() { return iterator(element); }
	iterator end() { return iterator(element + listSize); }
    
	class iterator
    {
      ...  
    };
    ...
};


//main
int main()
{
	arrayList a(3);
	a.insert(0, 1);
	a.insert(1, 2);
	a.insert(2, 3);
	a.push_back(4);
	a.push_back(5);
	for (arrayList::iterator it = a.begin();
		it != a.end(); ++it)
		cout << *it << " ";
	cout << endl;
	return 0;
}



28


template
void arrayList::meld(arrayList& a, arrayList& b)
{
	delete[] element;
	listSize = a.size() + b.size();
	arrayLength = listSize;
	element = new T[listSize];

	int minIndex = std::min(a.size(), b.size());
	int index = 0;
	for (int i = 0; i < minIndex; ++i)
	{
		element[index++] = a.get(i);
		element[index++] = b.get(i);
	}

	arrayList::iterator beg, end;
	if (a.size() < b.size())
	{
		beg = b.begin() + minIndex; //注意 需重载iterator+  而不是++
		end = b.end();
	}
	else if (a.size() > b.size())
	{
		beg = a.begin() + minIndex;
		end = a.end();
	}
	arrayList::iterator to = begin() + 2 * minIndex;
	std::copy(beg, end, to);

	/*listSize = a.listSize + b.listSize;
	if (a.listSize > b.listSize)
	{
		int i = b.listSize;
		int j;
		for (j = 0; j != i * 2; ++j) 
		{
			if (j % 2 == 0) 
				element[j] = a[j / 2];
			element[j] = b[j / 2];
		}
		copy(a.element + i, a.element + a.listSize, element + j);
	}
	else
	{
		int i = a.listSize;
		int j;
		for (j = 0; j != i * 2; ++j) 
		{
			if (j % 2 == 0) 
				element[j] = a[j / 2];
			else 
				element[j] = b[j / 2];
		}
		copy(b.element + i, b.element + b.listSize, element + j);
	}*/
}
//重载
iterator& operator+(int index) { position+=index; return *this; }



29


template
void arrayList::merge(arrayList& a, arrayList& b)
{
	delete[] element;
	listSize = a.size() + b.size();
	arrayLength = listSize;
	element = new T[listSize];

	int ca = 0;                       
	int cb = 0;                       
	int ct = 0;                       

	while ((ca < a.listSize) && (cb < b.listSize))
		if (a.element[ca] <= b.element[cb])
			element[ct++] = a.element[ca++];
		else
			element[ct++] = b.element[cb++];

	std::copy(a.element + ca, a.element + a.listSize, element + ct);
	ct += a.listSize - ca;
	std::copy(b.element + cb, b.element + b.listSize, element + ct);
	ct += b.listSize - cb;
}



30


template
void arrayList::split(arrayList& a, arrayList& b)
{
	a.clear();
	b.clear();
	for (int i = 0; i < listSize; ++i)
		if (element[i] & 1)
			a.push_back(element[i]);
		else
			b.push_back(element[i]);
}



31


官方：【https://www.cise.ufl.edu/~sahni/dsaac/public/exer/c5/e31.htm】
Data Structures, Algorithms, & Applications in C++
Chapter 5, Exercise 31

The code is given below and in the file arrayCircularList.h. Test code is included in arrayCircularList.cpp.
template
class circularArrayList : public linearList 
{
   public:
      // constructor, copy constructor and destructor
      circularArrayList(int initialCapacity = 10);
      circularArrayList(const circularArrayList&);
      ~circularArrayList() {delete [] element;}

      // ADT methods
      bool empty() const {return first == -1;}
      int size() const
         {if (first == -1)
             return 0;
          else
             return (arrayLength + last - first) % arrayLength + 1;
         }
      T& get(int theIndex) const;
      int indexOf(const T& theElement) const;
      void erase(int theIndex);
      void insert(int theIndex, const T& theElement);
      void output(ostream& out) const;

      // additional method
      int capacity() const {return arrayLength;}

   protected:
      void checkIndex(int theIndex) const;
            // throw illegalIndex if theIndex invalid
      T* element;            // 1D array to hold list elements
      int arrayLength;       // capacity of the 1D array
      int first;             // location of first element
      int last;              // location of last element
};

template
circularArrayList::circularArrayList(int initialCapacity)
{// Constructor.
   if (initialCapacity < 1)
   {ostringstream s;
    s << "Initial capacity = " << initialCapacity << " Must be > 0";
    throw illegalParameterValue(s.str());
   }
   arrayLength = initialCapacity;
   element = new T[arrayLength];
   first = -1;   // list is empty
}

template
circularArrayList::circularArrayList(const circularArrayList& theList)
{// Copy constructor.
   arrayLength = theList.arrayLength;
   element = new T[arrayLength];
   first = theList.first;
   if (first == -1)
      return;   // theList is empty
  
   // non-empty list
   last = theList.last;
   int current = first;
   while (current != last)
   {
      element[current] = theList.element[current];
      current = (current + 1) % arrayLength;
   }
   element[current] = theList.element[current];
}

template
void circularArrayList::checkIndex(int theIndex) const
{// Verify that theIndex is between 0 and size() - 1.
   int listSize = size();
   if (theIndex < 0 || theIndex >= listSize)
   {ostringstream s;
    s << "index = " << theIndex << " size = " << listSize;
    throw illegalIndex(s.str());
   }
}

template
T& circularArrayList::get(int theIndex) const
{// Return element whose index is theIndex.
 // Throw illegalIndex exception if no such element.
   checkIndex(theIndex);
   return element[(first + theIndex) % arrayLength];
}

template
int circularArrayList::indexOf(const T& theElement) const
{// Return index of first occurrence of theElement.
 // Return -1 if theElement not in list.

   int listSize = size();
   for (int i = 0; i < listSize; i++)
      if (element[(first + i) % arrayLength] == theElement)
         return i;

   return -1;
}

template
void circularArrayList::erase(int theIndex)
{// Delete the element whose index is theIndex.
 // Throw illegalIndex exception if no such element.
   checkIndex(theIndex);

   // no exception thrown, valid index, remove element
   if (size() == 1)
   {// list becomes empty
      element[first].~T();   // delete element
      first = -1;
      return;
   }

   // determine which side has fewer elements
   // and shift the smaller number of elements
   int listSize = size();
   if (theIndex <= (listSize - 1) / 2)
   {// shift elements theIndex - 1 ... 0
      for (int i = theIndex - 1; i >= 0; i--)
          element[(first + i + 1) % arrayLength]
             = element[(first + i) % arrayLength];
      element[first].~T();    // delete
      first = (first + 1) % arrayLength;
   }
   else
   {// shift elements theIndex + 1 ... size() - 1
      for (int i = theIndex + 1; i < listSize; i++)
          element[(first + i - 1) % arrayLength]
             = element[(first + i) % arrayLength];
      element[last].~T();   // delete
      last = (arrayLength + last - 1) % arrayLength;
   }
}

template
void circularArrayList::insert(int theIndex, const T& theElement)
{// Insert theElement so that its index is theIndex.
   int listSize = size();
   if (theIndex < 0 || theIndex > listSize)
   {// invalid index
      ostringstream s;
      s << "index = " << theIndex << " size = " << listSize;
      throw illegalIndex(s.str());
   }

   // valid index, handle empty list as special case
   if (first == -1)
   {// insert into empty list
      first = last = 0;
      element[0] = theElement;
      return;
   }

   // insert into a nonempty list, make sure we have space
   if (listSize == arrayLength)
   {// no space, double capacity
      T* newArray = new T [2 * arrayLength];

      // copy elements into new array beginning at position  0
      int j = 0;   // position in newArray to copy to
      for (int i = first;
               i != last; i = (i + 1) % arrayLength)
         newArray[j++] = element[i];
      newArray[j] = element[last];  // copy last element

      // switch to newArray and set first and last
      delete [] element;
      element = newArray;
      arrayLength *= 2;
      first = 0;
      last = j;
   }

   // create space for new element
   if (theIndex <= listSize / 2)
   {// shift elements 0 through theIndex - 1
      for (int i = 0; i < theIndex; i++)
         element[(arrayLength + first + i - 1) % arrayLength]
             = element[(first + i) % arrayLength];
      first = (arrayLength + first - 1) % arrayLength;
   }
   else
   {// shift elements listSize - 1  ... theIndex
      for (int i = listSize - 1; i >= theIndex; i--)
         element[(first + i + 1) % arrayLength]
              = element[(first + i) % arrayLength];
      last = (last + 1) % arrayLength;
   }
       
   // insert new element
   element[(first + theIndex) % arrayLength] = theElement;
}

template
void circularArrayList::output(ostream& out) const
{// Put the list into the stream out.
   if (first == -1)
      return;   // list is empty
   
   // non-empty list
   int current = first;
   while (current != last)
   {
      cout << element[current]  << "  ";
      current = (current + 1) % arrayLength;
   }
   cout << element[current]  << "  ";
}

// overload <<
template 
ostream& operator<<(ostream& out, const circularArrayList& x)
   {x.output(out); return out;}
The complexity of each method is the same as that of the corresponding method of arrayList.
数据结构与算法C++

相关

年功序列c++游戏

C++ ：string 用法详解

C++11 并发指南五(std::condition_variable 详解)

顺序存储的循环队列（c++实现）

C++中的各种定义

解析一下C++的异常处理

C++typename的由来和用法

C++多元组tuple使用方法？你熟悉吗？快来看看吧

使用vs2019用c++创建dll库

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

数据结构与算法之PHP排序算法（冒泡排序）

标签