数据结构-线性表的链式存储结构

#include <iostream>
/**
 * 线性表的链式存储实现
 */
using namespace std;
template<class DataType>
struct Node
{
    DataType data;
    Node<DataType> *next;
};

template<class DataType>
class LinkList
{
public:
//无参构造函数 建立只有头结点的空链表
    LinkList();

//含参构造函数,建立有N个元素的单链表
    LinkList(DataType x[], int n);

//析构函数
    ~LinkList();

//求单链表长度
    int Length();

//按位查找 在单链表中查找第i个节点的元素值
    DataType Get(int i);

//按值查找 在单链表中查找值为x的元素序号
    int Locate(DataType x);

//插入操作 在第i个位置插入元素值为x的元素
    void Insert(int i, DataType x);

//删除操作 在单链表中删除第i个节点
    DataType Delete(int i);

//遍历操作 打印链表
    void PrintList();
//求链表最大值
    DataType getMax();
//求链表最小值
    DataType getMin();

private:
//    单链表的头指针
    Node<DataType> *first;
};

template<class DataType>
void LinkList<DataType>::PrintList()
{
    Node<DataType> *p = first->next;
    cout << "遍历单链表:" << endl;
    while (p != NULL)
    {
        cout << p->data << endl;
        p = p->next;
    }
}
template<class DataType>
DataType LinkList<DataType>::getMax()
{
    Node<DataType> *p = first->next;
    int MAX=p->data;
    while(p!=NULL)
    {
        if(p->data >= MAX)
        {
            MAX=p->data;
        }
        p=p->next;
    }
    return MAX;
}
template<class DataType>
DataType LinkList<DataType>::getMin()
{
    Node<DataType> *p = first->next;
    int MIN=p->data;
    while(p!=NULL)
    {
        if(p->data <= MIN)
        {
            MIN=p->data;
        }
        p=p->next;
    }
    return MIN;
}

template<class DataType>
int LinkList<DataType>::Length()
{
    int count;
    Node<DataType> *p = first->next;
    while (p != NULL)
    {
        p = p->next;
        count++;
    }
    return count;
}

template<class DataType>
DataType LinkList<DataType>::Get(int i)
{
    Node<DataType> *p = first->next;
    int count = 1;
    while (p != NULL && count < i)
    {
        p = p->next;
        count++;
    }
    if (p == NULL)
        throw "Error: 位置错误";
    else
        return p->data;
}

template<class DataType>
int LinkList<DataType>::Locate(DataType x)
{
    Node<DataType> *p = first->next;
    int count = 1;
    while (p != NULL)
    {
        if (p->data == x)
            return count;
        p = p->next;
        count++;
    }
    return 0;
}

template<class DataType>
void LinkList<DataType>::Insert(int i, DataType x)
{
    Node<DataType> *p = first;
    int count = 0;
    while (p != NULL && count < i - 1)
    {
        p = p->next;
        count++;
    }
    if (p == NULL)
        throw "Error: 位置错误";
    else
    {
        Node<DataType> *s = new Node<DataType>;
        s->data = x;
        s->next = p->next;
        p->next = s;
    }
}

template<class DataType>
LinkList<DataType>::LinkList()
{
    first = new Node<DataType>;
    first->next = NULL;
}

//头插法
/*template<class DataType>
LinkList<DataType>::LinkList(DataType *x, int n) {
    first = new Node<DataType>;
    first->next = NULL;
    for (int i = 0; i < n; ++i) {
        Node<DataType> *s = new Node<DataType>;
        s.data = x[i];
        s.next = first->next;
        first->next = s;
    }
}*/
//尾插法
template<class DataType>
LinkList<DataType>::LinkList(DataType *x, int n)
{
    first = new Node<DataType>;
    Node<DataType> *end = first;
    for (int i = 0; i < n; ++i)
    {
        Node<DataType> *s = new Node<DataType>;
        s->data = x[i];
        end->next = s;
        end = s;
    }
    end->next = NULL;
}

template<class DataType>
DataType LinkList<DataType>::Delete(int i)
{
    Node<DataType> *p = first;
    int count = 0;
    while (p != NULL && count < i - 1)
    {
        p = p->next;
        count++;
    }
    if (p == NULL || p->next == NULL)
        throw "Error: 位置异常";
    else
    {
        Node<DataType> *temp = p->next;
        DataType dataType = temp->data;
        p->next = temp->next;
        delete temp;
        return dataType;
    }
}

template<class DataType>
LinkList<DataType>::~LinkList()
{
    while (first != NULL)
    {
        Node<DataType> *temp = first;
        first = first->next;
        delete temp;
    }
}

int main()
{
    /*int x[] = {1, 2, 3, 4, 5};
    LinkList<int> linkList(x, 5);
    linkList.Insert(1, 666);
    linkList.PrintList();
    linkList.Delete(2);
    linkList.PrintList();
    cout << "获取: " << linkList.Get(1) << endl;
    cout << "长度: " << linkList.Length() << endl;
    cout << "666的位置: " << linkList.Locate(666) << endl;*/
    LinkList<int> linkList;
    for(int i=0; i<5; i++)
    {
        int x;
        cout<<"请输入元素 "<<i+1<<" :"<<endl;
        cin>>x;
        linkList.Insert(i+1,x);
    }
    linkList.PrintList();
    cout<<"最小值:"<<linkList.getMin()<<endl;
    cout<<"最大值:"<<linkList.getMax();
}

 

全部评论

相关推荐

07-15 14:14
门头沟学院 Java
7.10投递7.15感谢信
投递地平线等公司7个岗位
点赞 评论 收藏
分享
07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务