ccqiji 发表于 2012-3-14 13:21:20

贴下各种结构实例吧-->C++版本

因为C的复杂度和难以描述性 果断放弃C实现
C++的比较好理解 就是一个封装类很少用到继承 多态更没见过
现贴出各种结构实现

ccqiji 发表于 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;
      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 == 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;
            for (int i = 0; i < m_nLength; i++)
            {
                newlpdata = m_lpData;
            }
            
            Clear();
            m_lpData = newlpdata;
            m_nAllocLength = nAllocLengthtemp;
            m_nLength = nLengthtemp;
      }
      
      for (int i = m_nLength; i > index; i--)
      {
            m_lpData = m_lpData;
      }
      m_lpData = 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;
            for (int i = 0; i < m_nLength; i++)
            {
                newlpdata = m_lpData;
            }
            
            Clear();
            m_lpData = newlpdata;
            m_nAllocLength = nAllocLengthtemp;
            m_nLength = nLengthtemp;
      }
      
      for (int i = m_nLength; i > index + 1; i--)
      {
            m_lpData = m_lpData;
      }
      m_lpData = 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;
            for (int i = 0; i < m_nLength; i++)
            {
                newlpdata = m_lpData;
            }
            
            Clear();
            m_lpData = newlpdata;
            m_nAllocLength = nAllocLengthtemp;
            m_nLength = nLengthtemp;
      }
      m_lpData = 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 = m_lpData;
      }
      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
    {
      returnm_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 > m_lpData)
                {
                  int temp;
                  temp = m_lpData;
                  m_lpData = m_lpData;
                  m_lpData = temp;
                }
               
            }
      }
    }

    void QuickSort(int nMinIndex, int nMaxIndex)   //快速排序O(n*log2^n)
    {
      m_isSorted = true;
      int nTemp1 = nMinIndex;
      int nTemp2 = nMaxIndex;
      T nKey = m_lpData;
      if (nMinIndex >= nMaxIndex)
      {
            return;
      }
      for (;;)
      {
            while(nMinIndex < nMaxIndex && m_lpData >= nKey)
            {
                nMaxIndex--;
            }
            if (nMinIndex >= nMaxIndex)
            {
                break;
            }
            m_lpData = m_lpData;
            
            while (nMinIndex < nMaxIndex && m_lpData <= nKey)
            {
                nMinIndex++;
            }
            if (nMinIndex >= nMaxIndex)
            {
                break;
            }
            m_lpData = m_lpData;
      }
      m_lpData = 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 == obj)
                {
                  return 1;
                }
            }
            return -1;
      }
    }
   
    int FindItemBy2Half(const T& obj,int nMinIndex,int nMaxIndex)
    {
      int nMiddel = (nMinIndex + nMaxIndex) / 2;
      
      if (m_lpData == obj)
      {
            return 1;
      }
      if (nMinIndex >= nMaxIndex)
      {
            return -1;
      }
      
      if (m_lpData > obj)
      {
            nMaxIndex = nMiddel - 1;
      }
      if (m_lpData < obj)
      {
            nMinIndex = nMiddel + 1;
      }
      FindItemBy2Half(obj, nMinIndex, nMaxIndex);
    }

   
    void Copy(const MyArray& theObj)
    {
      if (this == &theObj)
      {
            return;
      }
      Clear();
      T* newlpdata = new T;
      m_lpData = newlpdata;
      m_nLength = theObj.m_nLength;
      m_nAllocLength = theObj.m_nAllocLength;
      for (int i = 0; i < m_nLength; i++)
      {
            m_lpData = theObj.m_lpData;
      }
    }
   
    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;
            Clear();
            m_lpData = newlpdata;
            m_nAllocLength = nAllocLengthTemp;
      }
      for (int i = 0; i < theObj.m_nLength; i++)
      {
            InsertTailElem(theObj.m_lpData);
      }
    }
    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 ;
      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;
      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;
    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;
};

ccqiji 发表于 2012-3-14 13:24:55

数组的优缺点:
数组

优点:
1随机访问快 O(1)
   访问第i个元素 &a = base+(i-1)*sizeof(item)

缺点:

2增加 删除 速度慢 O(n/2)

3查询元素
   有序数组 速度快 log2^n
   无序数组 慢   O(n)

4. 当空间不够时候,
   (申请空间,复制原内容,释放原元素)O(2n)

适用场合:
   1.数据操作(增加 删除) 频率少
   2.有序 ,频率高 查找快
   3.可以预先判断估计元素个数情况下[汉字表 8000]

ccqiji 发表于 2012-3-14 13:28:10

算了传文件算了贴代码太长了
2.链表:
优点:

1当在指定的元素后增加 或删除 速度快 O(1)

2. 空间无限制


缺点:

1随机访问慢 O(n)

   访问第i个元素 一个个找

2查询元素慢O(n)
   无序 慢   O(n)
   有序 慢   因为随机访问慢
   
适用场合:

   1.无法事先估计元素个数

   2.尾部增加 尾部删除 频繁的时候

ccqiji 发表于 2012-3-14 13:30:37

3.栈和队列
因为栈和队列也是线性结构所以可以继承数组类或链表类
这里用双链表实现
栈有蛮多应用 二叉树的遍历非递归时要用到
二叉树的层次遍历要用到队列

ccqiji 发表于 2012-3-14 13:33:44

数据结构中有个迭代器的概念
线性表->(数组,链表)

不同的线性表的实现中,用户可以使用统一的遍历方法.

1. iterator 迭代器(位置指示器)
   
   MyArray<T>::iterator it = list1.begin();

   for(; it != list1.end(); it++)
   {
   T& obj = *it;
   }


2.
(位置)
POSITION pos = list1.begin();

while( pos != list1.end() )
{
   //T& obj = list1.GetNext(pos);

   T& obj = list1.GetData(pos);

   pos++;
}

这里自己做得时候有个小BUG 没有解决 最后多输出个0..

ccqiji 发表于 2012-3-14 13:34:38

哈希表:
也是线性结构 散列

小甲鱼 发表于 2012-3-14 13:42:48

非常不错,谢谢朋友分享!

ccqiji 发表于 2012-3-14 13:49:09

最大堆:
最大堆排序算法我认为是最实用的
比如有一题
n个无序元素 得到最小的m个元素
/*   100000000            m
[ 5 63 59 45 12 36 98 97 ...... ]
1亿个数据得到前10000最小的数据
这里用到最大堆来完成算法复杂度直接成了
(m/2)(lg2^m) + (n-m)(lg2^m)
具体思路就是前10000个构成个最大堆 从10001 到 100000000
如果小于根节点 循环与根节点交换 维护最大堆性质就行了
       = lg2^m- (m/2)(lg2^m)

ccqiji 发表于 2012-3-14 13:53:41

还有个桶排序感觉实用性并不到 是个线性阶 有点浪费空间
可以用哈希表实现解决空间浪费问题
具体思路
比如
10 2 3 4 5 7 0
这些数据
定义个数组 数组长度为要排序数据的最大长度 为10
数组元素为 0 0 2 3 4 5 0 7 0 0 10
0为标记 表示没有数据
当你写完数组 数据默认就自动排好序了
很少用

ccqiji 发表于 2012-3-14 14:01:07

当然具体数据分布情况
选择不同的算法
代码中基本上有冒泡 快排
最大堆 二叉树排序
晚上我贴下二叉树
前中后遍及 以及层次遍及
还有二叉树排序 查找
这些代码都是上课时记的
有什么错误大家一起交流

ccqiji 发表于 2012-3-14 15:31:27

void MyTree::PreorderTraverse(TreeNode* lpNode) //前序递归
{
    if (lpNode != NULL)
    {
      cout << lpNode->m_Data << endl;
      PreorderTraverse(lpNode->m_lpLeft);
      PreorderTraverse(lpNode->m_lpRight);
    }

}

void MyTree::MidorderTraverse(TreeNode* lpNode) //中序递归
{
    if (lpNode != NULL)
    {
      MidorderTraverse(lpNode->m_lpLeft);
      cout << lpNode->m_Data << endl;
      MidorderTraverse(lpNode->m_lpRight);
    }
}

void MyTree::LastorderTraverse(TreeNode* lpNode) //后序递归
{
    if (lpNode != NULL)
    {
      LastorderTraverse(lpNode->m_lpLeft);
      LastorderTraverse(lpNode->m_lpRight);
      cout << lpNode->m_Data << endl;
    }
}二叉树的遍历:

递归真的蛮简单的
调整下输出位置就行了 符合人的思想
如果是反前序 反中序 反后续 调整下递归函数调用的左右节点顺序即可
非递归有点抽象

能用递归的就能用栈结构来表示 但是一个函数两个递归函数调用就有点难理解的

首先看递归 都是压入左节点递归
当左节点最后一个问题执行完成才又递归传右节点void MyTree::PreorderTraverseByStack(TreeNode* lpNode) //前序非递归
{
    MyStack<TreeNode*> theStack;

   
    while (lpNode != NULL || !theStack.isEmpty())
    {

      while (lpNode != NULL)
      {
            cout << lpNode->m_Data << endl;
            theStack.push(lpNode);
            lpNode = lpNode->m_lpLeft;
      }

      if (!theStack.isEmpty())
      {
            theStack.pop(lpNode);
            lpNode = lpNode->m_lpRight;
      }
    }


   
}这需要多思考 多跟程序才能慢慢理解

中序的话 就是输出位置不同 把输出放到pop后就可以实现

而后序换输出位置已经不行
因为是最后输出根节点
先左后右最后根

所以肯定会有判断条件
先遍历到左子树叶子节点 弹出输出
然后跳到父节点 查找右节点 如果右节点非空 继续查找
然后输出右叶子
跳到父节点 输出父节点

这里父节点如果直接pop出来 则会出错 要么保存两次父节点 要么
写个取栈顶的函数 非改变栈大小 只是取元素

我写的第二种void MyTree::LastorderTraverseByStack(TreeNode* lpRoot)
{
    MyStack<TreeNode*> theStack;
    TreeNode* preNode = NULL;
    while ( lpRoot != NULL || !theStack.isEmpty())
    {
      if (lpRoot != NULL)
      {
            theStack.push(lpRoot);
            lpRoot = lpRoot->m_lpLeft;
      }
      else
      {
            theStack.GetTail(lpRoot);
            if ( lpRoot->m_lpRight != NULL && preNode != lpRoot->m_lpRight)
            {
                lpRoot = lpRoot->m_lpRight;
            }
            else
            {
                theStack.GetTail(preNode);
                lpRoot = preNode;
                cout << lpRoot->m_Data << endl;
                theStack.pop(lpRoot);
                lpRoot = NULL;
            }
      }
    }




}最后一个层次遍历

意思就是从根节点 第一层开始
从左到右或从右到左一层层的输出

这里用不了递归(因为递归输出位置3种情况已经用完 测试下都不是层次遍历) 所以栈也实现不了
只能用队列 不用队列也很难写void MyTree::LayerorderTraverse(TreeNode* lpNode) //层次遍历
{
    if(lpNode == NULL)
    {
      return;
    }
      
    MyQueue<TreeNode*> theQueue;
    theQueue.EnQueue(lpNode);
    TreeNode* lpCurNode = NULL;
    while (theQueue.DeQueue(lpCurNode))
    {
      cout << lpCurNode->m_Data << endl;
      if (lpCurNode->m_lpLeft != NULL)
      {
            theQueue.EnQueue(lpCurNode->m_lpLeft);
      }
      if (lpCurNode->m_lpRight != NULL)
      {
            theQueue.EnQueue(lpCurNode->m_lpRight);
      }
      
    }

}说下应用
前序遍历是波兰表达式
后续遍历是逆波兰表达式
中序是我们最习惯的表达式

所以写个让用户输入表达式的程序 可以用二叉树来写
遍历用后续 加个栈结构就可以实现

还有个析构函数怎么写 把后序遍历输出部分换成delete就行了

至于什么赫夫曼树什么的 也跟这有关系 感觉有点晕。。

ccqiji 发表于 2012-3-15 19:18:58

没人来啊。。
也许C++语法有点难懂 不过貌似就是用到个类 构造和析构
连C++3个特性都没用到

ccqiji 发表于 2012-3-15 22:24:56

二叉有序数的添加 删除
当删除的节点有左右子树时 一种方法时交换其数据值
一种方法时交换指针值 因为当数据特别大时交换时拷贝数据会浪费很大内存
这里我做的是交换指针

所以析构时 有序树不用后序遍历删除了
析构代码也改了

ccqiji 发表于 2012-3-16 14:27:03

今天讲到avl树 平衡树
其中平衡因子 就是左子树-右子树高度差 是个公式算出来的
而有些书 直接给-1 0 1

还有些书根本不讲avl树的实现。。 貌似觉得退化到链表对当今计算机没什么影响。。
自己先做一遍 唉 已经昏了 以前感觉链表交换排序够复杂的跟avl树根本不是一个层次的难

╬══→飞扬 发表于 2012-3-16 16:20:20

好文章,我也打算开始把数据结构上的知识重新学一遍{:1_1:}

ccqiji 发表于 2012-3-16 19:19:21


AVL树
    1.每个结点的左右子树abs(高度差值)<=1

TreeNode
{
   int m_nSubHeight;左右子树高度差值左高度-右高度
}

旋转: K1 K2相邻
         K1               K2
   K2      C    ===>   A       K1
   A    B                      B    C


好处: 合适的旋转 可以使得高度减少

右单旋转
                    20(K1)                  10(K2)
       10(K2)         30   ===>   7          20(K1)
    7       15               5          15       30
5

左单旋转

         K1                        K2
   A       K2       ===>   K1       C
         B    C         A   B


右双旋转
               K1                  k3
      K2         D   ===>       k2      K1
      A   K3               A   B    C    D
          B    C   
         
   1. K2,K3 左单旋          2. K1,K3 右单旋
            
                   K1                  K3
            K3      D         K2         K1
          K2   C             A   B    C   D
      A    B


左双旋转

                    K1
        D                k2
                k3            C   
       
          A           B

   1. k3, k2 右单旋
       
                k3
        A                k2
                B                C

    2.k3, k1左单旋
       
                k3
        k1                k2
D          A          B           C



--------------------------------------------------------------
时间复杂度:

查找 logn

增加 找logn + c1 + 高度差调整logn + 旋转时间

   2logn + c1 + c2

旋转时间 c2 + 高度差调整logn

删除 找logn + c1 + 高度差调整logn+ 旋转时间

   2logn + c1 + c2




ccqiji 发表于 2012-3-17 17:21:27

今天学到图 彻底崩溃 看到实现有点恶心的感觉

Klaus 发表于 2012-3-30 22:27:52

牛啊,学习了

小青年 发表于 2012-4-4 11:33:02

刚学完数据结构   谢楼主这么好的东西   回去好好看看!!!
页: [1] 2
查看完整版本: 贴下各种结构实例吧-->C++版本