#小弟刚刚接触C++，还请个位大虾请教。。。 - 编程论坛

#2

flyue2008-03-16 20:31

我自己写的链表：

#include <windows.h>

struct node
{
    int data;
    node *next;
};

node *getone(node *n, int pos)
{
    node *ret = n;
    for(int i = 0; i < pos; i++)
    {
        if(ret == NULL)return NULL;
        ret = ret->next;
    }
    return ret;
}

node *getend(node *n)
{
    node *ret = n;
    while(ret->next != NULL)
        ret = ret->next;

    return ret;
}

//////////////////////////////////////////////////////////////////////////
class CNode
{
private:
    node *m_list;

    void insertnode(node *add, int pos)
    {
        node *n1 = m_list, *n2 = NULL, *n3 = NULL;
        if(pos <= 0)
        {
            m_list = add;
            m_list->next = n1;
        }
        else
        {
            n2 = getone(m_list, pos - 1);
            n3 = getone(m_list, pos);
            n2->next = add;
            add->next = n3;
        }
    }
public:
    CNode()
    {
        m_list = NULL;
    }
    void add(int val, int pos)
    {
        node *addn = new node;
        addn->data = val;
        addn->next = NULL;
        insertnode(addn, pos);
    }

    void del(int pos)
    {
        node *tmp = getone(m_list, pos);
        if(pos <= 0)m_list = tmp->next;
        else
            getone(m_list, pos - 1)->next = tmp->next;
        delete tmp;
    }

    int get(int pos)
    {
        node *tmp;
        tmp = getone(m_list, pos);
        return tmp->data;
    }

    int num()
    {
        if(m_list == NULL)return 0;
        int cnt = 0;
        node *tmp = m_list;
        while(tmp->next != NULL)
        {
            tmp = tmp->next;
            cnt++;
        }
        return cnt + 1;
    }
};

#3

wangxinkai2008-03-16 20:34

谢谢。。。可我要的是，内几种排序方法，链表的。。。。

#4

Ethip2008-03-16 20:52

回复 1# 的帖子

你一定看过数据结构的书了，那书上应该有相应算法的啊，自己去实现一下下，就OK了！

#5

flyue2008-03-16 20:53

CNode n;
n.add(18,0);
n.add(20,0);
输出排列：
20
18

这个add函数就是用来插入的，它会在pos位置插入个值，不会覆盖掉原来的值。
del是用来删除一个节点的。
至于其他的算法，你可以根据我的CNode类自己写呀，还要都给你写好来啊？

#6

wangxinkai2008-03-16 21:42

数上都是数组。。。。。

我合计拿链表写成类。。。。

以后要用的时候也方便么。。。。。

#7

sunkaidong2008-03-16 21:45

自己尝试封装啊..然后如果有问题..可以一起讨论啊..

#8

wangxinkai2008-03-16 21:53

能写出来就不问了。

#9

wangxinkai2008-03-16 21:55

冒泡；
void BubbleSort(int* pData,int Count)
{
  int iTemp;
  for(int i=1;i<Count;i++)
  {
    for(int j=Count-1;j>=i;j--)
    {
      if(pData[j]<pData[j-1])
      {
        iTemp = pData[j-1];
        pData[j-1] = pData[j];
        pData[j] = iTemp;
      }
    }
  }
}

void main()
{
  int data[] = {10,9,8,7,6,5,4};
  BubbleSort(data,7);
  for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
  cout<<"\n";
}
交换；
void ExchangeSort(int* pData,int Count)
{
  int iTemp;
  for(int i=0;i<Count-1;i++)
  {
    for(int j=i+1;j<Count;j++)
    {
      if(pData[j]<pData[i])
      {
        iTemp = pData[i];
        pData[i] = pData[j];
        pData[j] = iTemp;
      }
    }
  }
}

void main()
{
  int data[] = {10,9,8,7,6,5,4};
  ExchangeSort(data,7);
  for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
  cout<<"\n";
}
选择；
void SelectSort(int* pData,int Count)
{
  int iTemp;
  int iPos;
  for(int i=0;i<Count-1;i++)
  {
    iTemp = pData[i];
    iPos = i;
    for(int j=i+1;j<Count;j++)
    {
      if(pData[j]<iTemp)
      {
        iTemp = pData[j];
        iPos = j;
      }
    }
    pData[iPos] = pData[i];
    pData[i] = iTemp;
  }
}

void main()
{
  int data[] = {10,9,8,7,6,5,4};
  SelectSort(data,7);
  for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
  cout<<"\n";
}

插入；
void InsertSort(int* pData,int Count)
{
  int iTemp;
  int iPos;
  for(int i=1;i<Count;i++)
  {
    iTemp = pData[i];
    iPos = i-1;
    while((iPos>=0) && (iTemp<pData[iPos]))
    {
      pData[iPos+1] = pData[iPos];
      iPos--;
    }
    pData[iPos+1] = iTemp;
  }
}

void main()
{
  int data[] = {10,9,8,7,6,5,4};
  InsertSort(data,7);
  for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
  cout<<"\n";
}

拿数组能写，拿链表就蒙了。。。。。

#10

aipb20072008-03-17 00:06

原理一样，某些算法用链表更简单，比如快排
有些又更复杂，比如插入

我也值实现过这两个，其他的自己想，数组会写，那么链表绝对没问题，前提是你理解那个过程

#11

小烟2008-03-18 18:40

讨厌用指针连表