频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
数据结构(一)线性表的顺序存储结构 顺序表的实现
2017-04-19 10:42:19           
收藏   我要投稿

数据结构(一)线性表的顺序存储结构 顺序表的实现:主要实现算法。

    void CreateList(T a[], int n);      //建立顺序表 
    void DispList();                    //显示表元素 
    int ListLength();                   //查看表长度 
    bool GetElem(int i , T &e);         //求某序号的元素值 
    int LocateElem(T e);                //按元素值查找其序号 
    bool ListInsert(int i, T e);        //插入元素 
    bool ListDelete(int i);             //删除元素 

    //友元函数  封闭型
    //表逆置 
    friend void Reverse(SqListClass &L);
    //删除第一个值为X的元素 
    friend bool DeleteElem(SqListClass &L, T x);
    //有序表的二路归并  
    friend void MerGe2(SqListClass &L1, SqListClass &L2, SqListClass &L3);

二路归并

归并操作的工作原理如下:
第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置 第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针超出序列尾 将另一序列剩下的所有元素直接复制到合并序列尾


归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。如
设有数列{6,202,100,301,38,8,1}
初始状态:6,202,100,301,38,8,1
第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;
第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;
第三次归并后:{1,6,8,38,100,202,301},比较次数:4;
总的比较次数为:3+4+4=11,;
逆序数为14;

C++中模板类使用友元模板函数 – – 封闭型

指的是在模板类中盛名友元函数并且实现。如

template 
class SqListClass
{
    friend void Reverse(SqListClass &L)
    {
        …………
    }
}
要点:友元函数定义在模板类之中

简单的实现代码

#include

using namespace std;

#define MaxSize 100

//顺序表类模板 
template 
class SqListClass
{
    T *data;
    int length;

public:
    SqListClass();
    ~SqListClass();
    void CreateList(T a[], int n);      //建立顺序表 
    void DispList();                    //显示表元素 
    int ListLength();                   //查看表长度 
    bool GetElem(int i , T &e);         //求某序号的元素值 
    int LocateElem(T e);                //按元素值查找其序号 
    bool ListInsert(int i, T e);        //插入元素 
    bool ListDelete(int i);             //删除元素 

    //友元函数  封闭型
    //表逆置 
    friend void Reverse(SqListClass &L)
    {
        int i ;
        T temp;
        for(i=0; i < L.lenrgth/2; i++)
        {
            temp = L.data[i];
            L.data[i] = L.data[L.length-i-1];
            L.data[L.length-i-1] = temp;
        }
    }

    //删除第一个值为X的元素 
    friend bool DeleteElem(SqListClass &L, T x)
    {
        int i = 0; 
        int j;
        while(i < L.length && L.data[i] != x) i++;
        if(i>= L.length)
            return false;
        else
        {
            for(j = i; j < L.length; j++)
                L.data[j] = L.data[j+1];
            L.length --;
            return true;
        }
    }

    //有序表的二路归并  
    friend void MerGe2(SqListClass &L1, SqListClass &L2, SqListClass &L3)
    {
        int i = 0, j = 0, k = 0;
        while(i
 SqListClass::SqListClass()
 {
    data = new T[MaxSize];
    length = 0;
  } 

  template
 SqListClass::~SqListClass()
 {
    delete [] data;
 }

 //建立顺序表
 template 
 void SqListClass::CreateList(T a[], int n)
 {
    int i;
    for(i = 0; i < n; i++)
        data[i] = a[i];
    length = i;
  } 

  //求顺序表的长度
   template
 int SqListClass::ListLength()
 {
    return length;
  } 

  //求顺序表中的某个数据元素值
   template
 bool SqListClass::GetElem(int i , T &e)
 {
    if(i <= 1 || i >= length)
        return false;
    e = data[i-1];
    return true;
  } 

  //按元素值查找
   template
int  SqListClass::LocateElem(T e)
{
    int i = 0;
    while(i < length && data[i] != e) 
        i++;
    if(i >= length)
        return 0;
    else
        return i+1;
 } 

 // 插入数据元素 
 template
bool SqListClass::ListInsert(int i, T e)
{
    int j ;
    if(i < 1 || i > length) return false;
    for(j = length; j >= i; j-- )
    {
        data[j] = data[j-1];
    }
    data[i-1] = e;
    length++;
    return true;
}

//删除数据元素
 template
bool SqListClass::ListDelete(int i)
{
    int j;
    if(i<1 || i > length) return false;
    for(j = i ; j < length; j++)
        data[i-1] = data[i];
    length --;
    return true;
 } 

 //输出所有数据元素
  template
 void SqListClass::DispList()
 {

    for(int i = 0; i MyClass;
    SqListClass MyClass1;
    SqListClass MyClass2;
    SqListClass MyClass3;
    MyClass.CreateList(a, 10);
    MyClass1.CreateList(a1, 5);
    MyClass2.CreateList(a2, 5);
    MyClass3.CreateList(a3, 5);

    //Reverse(MyClass);
    DeleteElem(MyClass1, 6);

    MyClass1.DispList();
    return 0;
 }
点击复制链接 与好友分享!回本站首页
上一篇:最详细的Log4j使用教程
下一篇:Log4j属性详解
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站