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

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

因为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[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;
};

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

数组的优缺点:
数组

优点:
1  随机访问快 O(1)
访问第i个元素 &a[i] = 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[10000]
  [ 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

刚学完数据结构谢楼主这么好的东西回去好好看看！！！

账号		自动登录	找回密码
密码			立即注册

[技术交流] 贴下各种结构实例吧-->C++版本

马上注册，结交更多好友，享用更多功能^_^

评分

评分