|
楼主 |
发表于 2012-3-14 13:24:31
|
显示全部楼层
1.
数组
myarray.h内容- #include "student.h"
- #include "mystring.h"
- #include <iostream.h>
- template<typename T>
- class MyArray
- {
- public:
- MyArray()
- {
- Init();
- }
- virtual ~MyArray()
- {
- Clear();
- }
- private:
- //1.InitL ist(&L) //构造空的线性表L
- void Init()
- {
- m_isSorted = false;
- m_lpData = NULL;
- m_nLength = m_nAllocLength = 0;
- }
- public:
- //2.LengthList(L) //求L的长度
-
- //3.GetElem(L,i,&e) //取L中元素ai,由e返回ai
- bool GetElem(int nIndex, T& OutStu)
- {
- if (nIndex < 0 || nIndex >= m_nLength)
- {
- return false;
- }
- OutStu = m_lpData[nIndex];
- return true;
- }
-
- //4.PriorElem(L,ce,&pre_e) //求ce的前驱,由pre_e返回
- bool PriorElem(T& stu,T& OutPreStu)
- {
- for (int i = 0; i < m_nLength; i++)
- {
- if (m_lpData[i] == stu)
- {
- break;
- }
- }
- if (i == m_nLength)
- {
- return false;
- }
- GetElem(i - 1, OutPreStu);
- return true;
- }
-
- //InsertElemPrev 之前
- bool InsertElemPrev(int index, const T& stu)
- {
- if (index < 0 || index > m_nLength)
- {
- return false;
- }
- m_isSorted = false;
- if (m_nLength <= m_nAllocLength)
- {
- int nLengthtemp = m_nLength;
- int nAllocLengthtemp = m_nAllocLength;
- if (m_nAllocLength == 0)
- {
- m_nAllocLength = 1;
- }
- T* newlpdata = new T[nAllocLengthtemp = m_nAllocLength * 2];
- for (int i = 0; i < m_nLength; i++)
- {
- newlpdata[i] = m_lpData[i];
- }
-
- Clear();
- m_lpData = newlpdata;
- m_nAllocLength = nAllocLengthtemp;
- m_nLength = nLengthtemp;
- }
-
- for (int i = m_nLength; i > index; i--)
- {
- m_lpData[i] = m_lpData[i - 1];
- }
- m_lpData[index] = stu;
- m_nLength++;
- return true;
- }
- //InsertElemAfter 之后
- bool InsertElemAfter(int index, const T& stu)
- {
- m_isSorted = false;
- if (index < 0 || index > m_nLength)
- {
- return false;
- }
- if (m_nLength <= m_nAllocLength)
- {
- int nLengthtemp = m_nLength;
- int nAllocLengthtemp = m_nAllocLength;
- if (m_nAllocLength == 0)
- {
- m_nAllocLength = 1;
- }
- T* newlpdata = new T[nAllocLengthtemp = m_nAllocLength * 2];
- for (int i = 0; i < m_nLength; i++)
- {
- newlpdata[i] = m_lpData[i];
- }
-
- Clear();
- m_lpData = newlpdata;
- m_nAllocLength = nAllocLengthtemp;
- m_nLength = nLengthtemp;
- }
-
- for (int i = m_nLength; i > index + 1; i--)
- {
- m_lpData[i] = m_lpData[i - 1];
- }
- m_lpData[index + 1] = stu;
- m_nLength++;
- return true;
- }
- //尾部插入
- void InsertTailElem(const T& InStu)
- {
- m_isSorted = false;
- if (m_nLength <= m_nAllocLength)
- {
- int nLengthtemp = m_nLength;
- int nAllocLengthtemp = m_nAllocLength;
- if (m_nAllocLength == 0)
- {
- m_nAllocLength = 1;
- }
- T* newlpdata = new T[nAllocLengthtemp = m_nAllocLength * 2];
- for (int i = 0; i < m_nLength; i++)
- {
- newlpdata[i] = m_lpData[i];
- }
-
- Clear();
- m_lpData = newlpdata;
- m_nAllocLength = nAllocLengthtemp;
- m_nLength = nLengthtemp;
- }
- m_lpData[m_nLength] = InStu;
- m_nLength++;
- }
- //6.DeleteElem(&L,i) //删除第i个数据元素
- bool DeleteElem(int nIndex)
- {
- if (nIndex < 0 || nIndex >= m_nLength)
- {
- return false;
- }
- for (int i = nIndex; i < m_nLength; i++)
- {
- m_lpData[i] = m_lpData[i + 1];
- }
- m_nLength--;
- return true;
- }
-
- //7.EmptyList(L) //判断L是否为空表
- bool isEmpty() const
- {
- return m_nLength == 0;
- }
-
- //8.ClearList(&L) //置L为空表
- void Clear()
- {
- if (m_lpData != NULL)
- {
- delete []m_lpData;
- m_lpData = NULL;
- }
- m_nAllocLength = m_nLength = 0;
- }
- int GetLength() const
- {
- return m_nLength;
- }
- void PrintAll()
- {
- T temp;
- for (int i = 0; i < m_nLength; i++)
- {
- GetElem(i, temp);
- cout << temp << endl;
- }
- }
- public:
-
- void Sort()
- {
- m_isSorted = true;
- int i = 0;
- int j = 0;
- for (; i < m_nLength; i++)
- {
- for (j = i + 1; j < m_nLength; j++)
- {
- if (m_lpData[i] > m_lpData[j])
- {
- int temp;
- temp = m_lpData[i];
- m_lpData[i] = m_lpData[j];
- m_lpData[j] = temp;
- }
-
- }
- }
- }
-
- void QuickSort(int nMinIndex, int nMaxIndex) //快速排序 O(n*log2^n)
- {
- m_isSorted = true;
- int nTemp1 = nMinIndex;
- int nTemp2 = nMaxIndex;
- T nKey = m_lpData[nMinIndex];
- if (nMinIndex >= nMaxIndex)
- {
- return;
- }
- for (;;)
- {
- while(nMinIndex < nMaxIndex && m_lpData[nMaxIndex] >= nKey)
- {
- nMaxIndex--;
- }
- if (nMinIndex >= nMaxIndex)
- {
- break;
- }
- m_lpData[nMinIndex++] = m_lpData[nMaxIndex];
-
- while (nMinIndex < nMaxIndex && m_lpData[nMinIndex] <= nKey)
- {
- nMinIndex++;
- }
- if (nMinIndex >= nMaxIndex)
- {
- break;
- }
- m_lpData[nMaxIndex--] = m_lpData[nMinIndex];
- }
- m_lpData[nMaxIndex] = nKey;
- int nMiddle = nMaxIndex;
- QuickSort(nTemp1, nMiddle - 1);
- QuickSort(nMiddle + 1, nTemp2);
- }
- int FindItem(const T& obj)
- {
-
- if (isSort())
- {
- return FindItemBy2Half(obj, 0, m_nLength - 1);
- }
- else
- {
- for (int i = 0; i < m_nLength; i++)
- {
- if (m_lpData[i] == obj)
- {
- return 1;
- }
- }
- return -1;
- }
- }
-
- int FindItemBy2Half(const T& obj,int nMinIndex,int nMaxIndex)
- {
- int nMiddel = (nMinIndex + nMaxIndex) / 2;
-
- if (m_lpData[nMiddel] == obj)
- {
- return 1;
- }
- if (nMinIndex >= nMaxIndex)
- {
- return -1;
- }
-
- if (m_lpData[nMiddel] > obj)
- {
- nMaxIndex = nMiddel - 1;
- }
- if (m_lpData[nMiddel] < obj)
- {
- nMinIndex = nMiddel + 1;
- }
- FindItemBy2Half(obj, nMinIndex, nMaxIndex);
- }
-
- void Copy(const MyArray& theObj)
- {
- if (this == &theObj)
- {
- return;
- }
- Clear();
- T* newlpdata = new T[theObj.m_nAllocLength];
- m_lpData = newlpdata;
- m_nLength = theObj.m_nLength;
- m_nAllocLength = theObj.m_nAllocLength;
- for (int i = 0; i < m_nLength; i++)
- {
- m_lpData[i] = theObj.m_lpData[i];
- }
- }
-
- void UnionArray(const MyArray& theObj)
- {
- m_isSorted = false;
- if (m_nAllocLength < m_nLength + theObj.m_nLength)
- {
- int nAllocLengthTemp;
- nAllocLengthTemp = m_nAllocLength;
- T* newlpdata = new T[m_nLength + theObj.m_nLength];
- Clear();
- m_lpData = newlpdata;
- m_nAllocLength = nAllocLengthTemp;
- }
- for (int i = 0; i < theObj.m_nLength; i++)
- {
- InsertTailElem(theObj.m_lpData[i]);
- }
- }
- bool isSort() const
- {
- return m_isSorted;
- }
-
- private:
- T* m_lpData;
- int m_nLength;
- int m_nAllocLength;
- private:
- bool m_isSorted;
- };
复制代码 string.h:- class mystring
- {
- public:
- mystring();
- mystring(char *);
- virtual ~mystring();
- public:
- mystring(const mystring& obj)
- {
- m_lpstring = new char [strlen(obj.m_lpstring) + 1];
- strcpy(m_lpstring, obj.m_lpstring);
- }
- mystring& operator=(const mystring& obj)
- {
- if (this == &obj)
- {
- return *this;
- }
- if (m_lpstring != NULL)
- {
- delete []m_lpstring;
- }
-
- m_lpstring = new char[strlen(obj.m_lpstring) + 1];
- strcpy(m_lpstring, obj.m_lpstring);
- return *this;
- }
- operator char*() const
- {
- return m_lpstring;
- }
- bool operator >= (const mystring& obj)
- {
- return strcmp(m_lpstring, obj.m_lpstring) >= 0;
- }
- bool operator > (const mystring& obj)
- {
- return strcmp(m_lpstring, obj.m_lpstring) > 0;
- }
- bool operator < (const mystring& obj)
- {
- return strcmp(m_lpstring, obj.m_lpstring) < 0;
- }
- bool operator <= (const mystring& obj)
- {
- return strcmp(m_lpstring, obj.m_lpstring) <= 0;
- }
- bool operator == (const mystring& obj)
- {
- return strcmp(m_lpstring, obj.m_lpstring) == 0;
- }
- private:
- char* m_lpstring;
- };
- bool operator<(const mystring& obj1, const mystring& obj2);
- bool operator<=(const mystring& obj1, const mystring& obj2);
- bool operator>(const mystring& obj1, const mystring& obj2);
- bool operator>=(const mystring& obj1, const mystring& obj2);
- bool operator==(const mystring& obj1, const mystring& obj2);
复制代码 string.cpp:- #include "stdafx.h"
- #include "mystring.h"
- //////////////////////////////////////////////////////////////////////
- // Construction/Destruction
- //////////////////////////////////////////////////////////////////////
- mystring::mystring()
- {
- m_lpstring = NULL;
- }
- mystring::mystring(char* lpstring)
- {
- m_lpstring = new char[strlen(lpstring) + 1];
- strcpy(m_lpstring, lpstring);
- }
- mystring::~mystring()
- {
- }
- bool operator<(const mystring& obj1, const mystring& obj2)
- {
- return obj1 < obj2;
- }
- bool operator<=(const mystring& obj1, const mystring& obj2)
- {
- return obj1 <= obj2;
- }
- bool operator>(const mystring& obj1, const mystring& obj2)
- {
- return obj1 > obj2;
- }
- bool operator>=(const mystring& obj1, const mystring& obj2)
- {
- return obj1 >= obj2;
- }
- bool operator==(const mystring& obj1, const mystring& obj2)
- {
- return obj1 == obj2;
- }
复制代码 student.h:- class student
- {
- public:
- student(int ndata = 0)
- {
- m_ndata = ndata;
- }
- student(int ndata);
- ~student();
- public:
- student& operator=(const student& obj)
- {
- if (this == &obj)
- {
- return *this;
- }
- m_ndata = obj.m_ndata;
- return *this;
- }
- operator int() const
- {
- return m_ndata;
- }
- private:
- int m_ndata;
- };
复制代码 |
评分
-
查看全部评分
|