@rg070836rg 2016-06-25T01:57:06.000000Z 字数 8778 阅读 1853

数据结构——链表报告

`data_structure`

一、设计方式

结点结构：
包含数据域以及指针域，数据域通过模板可以实现不同类型的数据类型。

template <class T>
struct Node
{
    T data;
    Node<T> *next;
};

链表结构：
包含头结点，用于数据的存储，包含一系列函数，用于数据的访问及管理。

template <class T>
class LinkList
{ 
    /*
    略去一系列成员函数
    */
private:
    Node<T> *pHead;     //节点，包含数据域和指针域
};

文件结构：

LinkList.cpp

LinkList.h

test.cpp

LinkList.cpp与LinkList.h用于实现链表模板
test.cpp用于测试模板的正确性

二、具体实现

2.1 LinkList类设计

template <class T>
class LinkList
{ 
//**********
//基本函数
//**********
public:
    LinkList();                 //无参构造函数
    ~LinkList();               //析构函数，作垃圾回收
    LinkList(T a[], int n,string flag);     //构造函数
//**********
//功能函数
//**********
public:
    int ListLength();               //返回链表长度
    T& Get(int pos);                //按位返回元素引用
    int Locate(T item);             //按值找位
    void PrintListLink();           //遍历打印
    void Insert(int pos, T item);   //按位插值
    void Delete(int i);             //按位删值
    void Invert();                  //逆序链表
    void Merge(LinkList<T> &L);     //归并链表
    void SelectSort();              //选择排序
    LinkList<T>& operator=(LinkList<T>* L);//重载赋值，便于合并
    friend LinkList<T>* Merge(LinkList<T> &LA, LinkList<T>&LB);
    friend void Merge_1(LinkList<T> &LA, LinkList<T>&LB);
//**********
//成员变量
//**********
private:
    Node<T> *pHead;     //节点，包含数据域和指针域
};

2.1.1 单链表的初始化

单链表可以有两种初始化，无参初始化，只生成头结点的空链表，有参初始化，可以实现带元素节点的链表。

单链表的无参构造函数：

/**
* 无参数构造函数
* 作用:生成头结点
* @param[in] 无
* @param[out] 无
*/
template <class T>
LinkList<T>::LinkList()
{
    pHead = new Node<T>;
    pHead->next = NULL;
}

单链表的有参构造函数：

本函数提供三种插入方法：

头插法（head）

顺序插法（sorted）

尾插法（tail）

根据所给标志不同，选择不同构造方法。

template <class T>
LinkList<T>::LinkList(T a[],int n,string flag)

1、头插法（head）

if (flag=="head")
    {
        pHead = new Node<T>;
        pHead->next = NULL;
        for (int i = 0; i < n; i++)
        {
            Node<T> *p = new Node<T>;
            p->data = a[i];
            p->next = pHead->next;
            pHead->next = p;
        }       
    }

头插法每次生成的节点插在头结点的后面，操作简单。

2、顺序插法（sorted）

else if (flag == "sorted")
    {
        pHead = new Node<T>;    pHead->next = NULL;
        Node<T> *p, *front, *current;
        for (int i = 0; i < n; i++)
        {
            front = pHead;
            p = new Node<T>;
            p->data = a[i];
            current = pHead->next;
            while ((current != NULL) && (current->data < p->data))
            {
                front = current;
                current = current->next;
            }
            p->next = current;
            front->next = p;
        }
    }

顺序插法，在构造的时候，考虑顺序，使得构造函数完成的同时链表有序，时间复杂度为 $O(n^2)$ ，p是新建节点，front以及current确定插入位置。

3、尾插法（tail）

else if (flag == "tail")
    {
        pHead = new Node<T>;
        Node<T> * rear = pHead;
        for (int i = 0; i < n; i++)
        {
            Node<T> *p = new Node<T>;
            p->data = a[i];
            rear->next = p;
            rear = p;
        }
        rear->next = NULL;
    }

尾插法，每次生成的节点放在链表尾部，rear指针指向最后一个节点，无须重新遍历。便于插入操作。

其他情况程序提示错误

else
    {
        cerr << "error at flag choosing!" << endl;
    }

2.1.2求链表长度

遍历链表，通过计数器计数，并返回。

/**
* int ListLength()
* 作用:返回链表节点数
* @param[in] 无
* @param[out] int
*/
template <class T>
int LinkList<T>::ListLength()
{
    int num = 0;
    Node<T> *p = pHead->next;
    while (p!=NULL)
    {
        p = p->next;
        num++;
    }
    return num;
}

2.1.3按位找值

从第一个元素点开始，计数器i初始化为1，找到位序pos后，返回该位置元素的引用，注意此返回值的修改，会对链表值进行改动。同时，需要考虑异常情况，保证程序安全。

/**
* T& Get(int pos)
* 作用:获得指定pos位的元素的引用
* @param[in] pos
* @param[out] T
*/
template <class T>
T& LinkList<T>::Get(int pos)
{
    Node<T> *p = pHead->next;
    int i = 1;
    while (p!=NULL && i!=pos)
    {
        p = p->next;
        i++;
    }
    if (p == NULL||i>pos)
    {
        cerr << "数据非法，异常退出。";
        system("pause");
        exit(1);
    }
    else
        return p->data;
}

2.1.4遍历单链表

遍历单链表，并输出各节点元素数据域值。

/**
* PrintListLink()
* 作用:遍历并打印链表数据
* @param[in] 
* @param[out] 
*/
template<class T>
void LinkList<T>::PrintListLink()
{
    Node<T> *p = pHead->next;
    while (p!=NULL)
    {
        cout << p->data<<"\t";
        p = p->next;
    }
}

2.1.5单链表的按位插值

遍历查找到第pos-1个节点，插入元素item

/**
* Insert(int pos,T item)
* 作用:在pos位置插入元素item
* @param[in]  位置pos 元素item
* @param[out]
*/
template<class T>
void LinkList<T>::Insert(int pos,T item)
{
    Node<T> *p = pHead;
    int j = 0;
    while (p!=NULL && j<pos-1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
    {
        cout << "已至链表尾，放弃插入位置，自动插入尾部";
        Node<T> *tmp = new Node<T>;
        tmp->data = item;
        tmp->next = NULL;
        p->next = tmp;
    }
    else
    {
        Node<T> *tmp = new Node<T>;
        tmp->data = item;
        tmp->next = p->next;
        p->next = tmp;
    }
}

2.1.7按位删除

删除第i个元素值，必找到第i-1个节点，并使之链接到i+1个节点上，同时销毁第i个元素的空间，同时置为NULL。

/**
* Delete(int i)
* 作用:按照位序i删除节点
* @param[in]  位置i
* @param[out]
*/
template<class T>
void LinkList<T>::Delete(int i)
{
    Node<T> *p = pHead;
    int j = 0;
    while (p!=NULL && j<i-1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL || p->next == NULL || j > i-1 )
    {
        cerr << "删除位置不在表内，异常退出";
        exit(1);
    }
    else
    {
        Node<T> *tmp = p->next;
        p->next = tmp->next;
        delete tmp;
        tmp=NULL;
    }
}

2.1.8 单链表的逆置

实际就是使用头插法，重新组织链表。

/**
* Invert()
* 作用:逆序该链表
* @param[in]  
* @param[out]
*/
template<class T>
void LinkList<T>::Invert()
{
    Node<T> *p =  pHead->next;
    pHead->next = NULL;
    while (p != NULL)
    {
        Node<T> *q = p;
        p = p->next;
        q->next = pHead->next;
        pHead->next= q;;
    }
}

2.1.9 合并单链表

这块采用了三种方式合并链表：

成员函数调用

友元无返回值合并

友元有返回值合并

下面来一一介绍。

首先，合并单链表的前提是有序，所以假定传进来的表都是有序的。这边不做有序的判断。

成员函数调用

作为链表的成员函数调用，把传入的链表，归并到调用链表中。由于是成员函数，所以在其中访问私有成员没有问题。

/**
* Merge(LinkList<T> &L)
* 作用:将L链表数据合并到调用表 
* @param[in]    
* @param[out]
*/
template <class T>
void LinkList<T>::Merge(LinkList<T> &L)
{
    Node<T> *p3 = pHead;
    Node<T> *p1 = pHead->next;
    Node<T> *p2 = L.pHead->next;
    while ((p1 != NULL) && (p2 != NULL))
    {
        if ((p1->data) < (p2->data))
        {
            p3->next = p1;
            p1 = p1->next;
            p3 = p3->next;
        }
        else
        {
            p3->next = p2;
            p2=p2->next;
            p3 = p3->next;
        }
    }
    if (p1 != NULL) p3->next = p1;
    if (p2 != NULL) p3->next = p2;
    delete L.pHead;
    L.pHead = NULL;
}

友元无返回值合并

这是通过友元的方式，无须调用者，函数目的是把两个链表的值，归并到第一个链表中，友元的声明，使其能够方便的使用私有成员。

/**
    * LinkList<T>* Merge(LinkList<T> &, LinkList<T>&)
    * 作用:通过友元方式，把LB元素合并到LA中
    * 注意：LA,LB需有序
    * @param[in] LA,LB
    * @param[out] 
    */
    friend void Merge_1(LinkList<T> &LA, LinkList<T>&LB){
        Node<T> *p1 = LA.pHead->next;
        Node<T> *p2 = LB.pHead->next;
        Node<T> *p3 = LA.pHead;
        while (p1 != NULL && p2 != NULL)
        {
            if (p1->data<p2->data)
            {
                p3->next = p1;
                p1 = p1->next;
                p3 = p3->next;
            }
            else{
                p3->next = p2;
                p2 = p2->next;
                p3 = p3->next;
            }
        }
        if (p1 != NULL) p3 = p1->next;
        if (p2 != NULL) p3 = p2->next;
        delete LB.pHead;
        LB.pHead = NULL;
    }

友元有返回值合并

这个函数与上个函数的区别在于，这个函数，合并两个链表，并返回这个合并的链表。为了接受这个返回的链表，在类中，重载了赋值运算符“=”。

    /**
    * LinkList<T>* Merge(LinkList<T> &, LinkList<T>&)
    * 作用:通过友元方式，合并链表LA,LB元素，并返回合并后链表
    * 注意：LA,LB需有序
    * @param[in] LA,LB
    * @param[out] 合并后链表LC
    */
    friend LinkList<T>* Merge(LinkList<T> &LA, LinkList<T>&LB)
    {
        LinkList<T> *LC = new LinkList<T>;
        Node<T> *p1 = LA.pHead->next;
        Node<T> *p2 = LB.pHead->next;
        Node<T> *p3 = LC->pHead;
        while (p1 != NULL && p2 != NULL)
        {
            if (p1->data < p2->data)
            {
                p3->next = p1;
                p1 = p1->next;
                p3 = p3->next;
            }
            else
            {
                p3->next = p2;
                p2 = p2->next;
                p3 = p3->next;
            }
        }
        if (p1 != NULL)
            p3->next = p1;
        else
            p3->next = p2;
        delete LA.pHead; LA.pHead = NULL;
        delete LB.pHead; LB.pHead = NULL;
        return LC;
    }

重载赋值运算符：
若链表本身为空，使用插值的方法生成链表。若本身不空，可以再次调用归并，是两者进行归并。

template<class T>
LinkList<T>& LinkList<T>::operator = (LinkList<T> *L)
{
    if (this->pHead->next==NULL)
    {
        Node<T> *p = L->pHead->next;
        while (p != NULL)
        {
            this->Insert(this->ListLength()+1,p->data);
            p = p->next;
        }
        L->~LinkList();
        //因为尝试的是值复制，所以显示调用析构函数删除空间
    }
    else{
        this->Merge(*L);
    }
     return *this;
}

2.1.10链表的排序

这里选用插入排序法，将链表按照升序排列。

/**
* SelectSort()
* 作用:将L链表按升序排列
* @param[in]
* @param[out]
*/
template <class T>
void LinkList<T>::SelectSort()
{
    //选择排序,每次选择未排序部分的最小值交换到前面 
    if (pHead->next == NULL) return; //链表为空  
    if (pHead->next->next == NULL) return; //只有一个节点  
    Node<T> *Pre_Sorting = pHead->next; //记录正在排序的点  
    while (Pre_Sorting != NULL)
    {
        Node<T> *pTemp = Pre_Sorting->next; //从pSorting开始往后遍历  
        Node<T> *pMin = Pre_Sorting; //暂存从pSorting开始的最小的点  
        while (pTemp != NULL)
        {
            if (pTemp->data < pMin->data)
                pMin = pTemp;
            pTemp = pTemp->next;
        }
        //进行交换  
        T temp = Pre_Sorting->data;
        Pre_Sorting->data = pMin->data;
        pMin->data = temp;
        //排序下一个点  
        Pre_Sorting = Pre_Sorting->next;
    }
}

至此，链表功能基本说明完毕。下面进入测试阶段。

三、测试

3.1有参构造函数测试

部分代码：

int main()
{
    int a[10] = {8,6,2,4,5,1,3,9,7,10};
    LinkList<int> L1(a, 10, "head");
    LinkList<int> L2(a, 10, "sorted");
    LinkList<int> L3(a, 10, "tail");
    cout << endl << "链表L1(头插)为：" << endl;
    L1.PrintListLink();
    cout << endl << "链表L2（顺序插）为：" << endl;
    L2.PrintListLink();
    cout << endl << "链表L3（尾插）为：" << endl;
    L3.PrintListLink();
    ………………
}

测试截图：

3.2返回链表长度测试

部分代码：

    int a[10] = { 8, 6, 2, 4, 5, 1, 3, 9, 7, 10 };
    LinkList<int> L(a, 10, "head");
    cout << endl << "链表L为：" << endl;
    L.PrintListLink();
    cout << "返回链表长度：" << endl 
        << L.ListLength()<<endl;

测试截图：
此处输入图片的描述

3.3按位返回元素引用测试

部分代码：

    int a[10] = { 8, 6, 2, 4, 5, 1, 3, 9, 7, 10 };
    LinkList<int> L(a, 10, "head");
    cout << endl << "链表L为：" << endl;
    L.PrintListLink();
    cout << "返回位序5的元素值：" << endl 
        << L.Get(5)<< endl;

测试截图：
此处输入图片的描述

3.4 按值找位测试

部分代码：

    int a[10] = { 8, 6, 2, 4, 5, 1, 3, 9, 7, 10 };
    LinkList<int> L(a, 10, "head");
    cout << endl << "链表L为：" << endl;
    L.PrintListLink();
    int A = 7;
    cout << "返回元素A(7)的位序值：" << endl
        << L.Locate(A) << endl;

测试截图：
此处输入图片的描述

3.5按位插值测试

部分代码：

    int a[10] = { 8, 6, 2, 4, 5, 1, 3, 9, 7, 10 };
    LinkList<int> L(a, 10, "head");
    cout << endl << "链表L为：" << endl;
    L.PrintListLink();
    cout<< "按位(4)插值(11)：" << endl;
    L.Insert(4, 11);    
    L.PrintListLink();
    cout << endl;

测试截图：
此处输入图片的描述

3.6按位删值测试

部分代码：

    int a[10] = { 8, 6, 2, 4, 5, 1, 3, 9, 7, 10 };
    LinkList<int> L(a, 10, "head");
    cout << endl << "链表L为：" << endl;
    L.PrintListLink();
    cout << "按位(1)删值：" << endl;
    L.Delete(1);
    L.PrintListLink();

测试截图：
此处输入图片的描述

3.7逆序链表测试

部分代码：

    int a[10] = { 8, 6, 2, 4, 5, 1, 3, 9, 7, 10 };
    LinkList<int> L(a, 10, "head");
    cout << endl << "链表L为：" << endl;
    L.PrintListLink();
    cout<< "逆序链表：" << endl;
    L.Invert();
    L.PrintListLink();

测试截图：
此处输入图片的描述

3.8 归并测试

部分代码：

    cout <<  "归并链表(成员函数)：" << endl;
    int b[6] = { 1, 3, 5, 7, 9, 11 };
    int c[6] = {2,4,6,8,10,12};
    LinkList<int> LB(b, 6, "tail");
    LinkList<int> LC(c, 6, "tail");
    cout << endl << "链表LB为：" << endl;
    LB.PrintListLink();
    cout << endl << "链表LC为：" << endl;
    LC.PrintListLink();
    LB.Merge(LC);
    cout << endl << "归并后的链表LB为：" << endl;
    LB.PrintListLink(); 
    cout << endl;

测试截图：
此处输入图片的描述

3.9有返回值归并友元函数测试

部分代码：

    cout <<  "归并链表(有返回值函数)：" << endl;
    int b[6] = { 1, 3, 5, 7, 9, 11 };
    int c[6] = {2,4,6,8,10,12};
    LinkList<int> LB(b, 6, "tail");
    LinkList<int> LC(c, 6, "tail");
    cout << endl << "链表LB为：" << endl;
    LB.PrintListLink();
    cout << endl << "链表LC为：" << endl;
    LC.PrintListLink();
    LinkList<int> L;
    cout << endl;
    cout << endl << "合并后的L链表：" << endl;
    L = Merge(LB, LC);
    L.PrintListLink();
    cout << endl;

测试截图：
此处输入图片的描述

3.10 无返回值归并链表测试

部分代码：

    cout <<  "归并链表(无返回值函数)：" << endl;
    int b[6] = { 1, 3, 5, 7, 9, 11 };
    int c[6] = {2,4,6,8,10,12};
    LinkList<int> LB(b, 6, "tail");
    LinkList<int> LC(c, 6, "tail");
    cout << endl << "链表LB为：" << endl;
    LB.PrintListLink();
    cout << endl << "链表LC为：" << endl;
    LC.PrintListLink();
    cout << endl;
    cout << endl << "合并后的LB链表：" << endl;
    Merge_1(LB, LC);
    LB.PrintListLink();

测试截图：
此处输入图片的描述

                                        陈实
                                        2015年3月29日

数据结构——链表报告

data_structure

一、设计方式

二、具体实现

2.1 LinkList类设计

2.1.1 单链表的初始化

2.1.2求链表长度

2.1.3按位找值

2.1.4遍历单链表

2.1.5单链表的按位插值

2.1.7按位删除

2.1.8 单链表的逆置

2.1.9 合并单链表

2.1.10链表的排序

三、测试

3.1有参构造函数测试

3.2返回链表长度测试

3.3按位返回元素引用测试

3.4 按值找位测试

3.5按位插值测试

3.6按位删值测试

3.7逆序链表测试

3.8 归并测试

3.9有返回值归并友元函数测试

3.10 无返回值归并链表测试

内容目录

`data_structure`