数据结构与算法：一、线性表的顺序存储结构SeqList和链式存储结构LinkList_实现线性表的顺序存储结构(seqlist)和链式存储结构(linklist)。

实现了线性表的链式存储结构和线性存储结构，能进行插入元素O(n)，删除元素O(n)，查找元素O(n)和返回线性表长度O(1)的操作。其中链式存储结构使用了C++11的智能指针进行内存管理。
要点：链式存储结构中的clear()要单独删除每一个元素，就像拆链子一样要把中间的每一个环节都拆开，不能简单的把head和tail连起来，不然还是会造成内存泄漏

一、顺序存储结构SeqList

定义了数据类型ElemType，便于修改
使用状态stat，表示操作成功/失败
定义了线性表的长度length和用于存储数据的数组List[]
函数：

• 三个插入函数：

• stat insertElem(int index, ElemType *e);用下标插入
• stat pushBack(ElemType *e);尾部插入
• stat pushFront(ElemType *e);首部插入
  成功返回OK(0)，失败返回ERROR(1)

• 三个删除函数：

• stat deleteElem(int index, ElemType *e);使用下标删除
• stat popBack(ElemType *e);删除尾元素
• stat popFront(ElemType *e);删除首元素
  成功返回OK(0)，并把删除元素存储在e中；失败返回ERROR(1)

• 两个辅助函数：

• stat getElem(int index, ElemType *e);获取下标对应元素，成功返回OK(0)，并赋值e；失败返回ERROR(1)
• int getLength(){ return length; }返回线性表长度

class SeqList
{
public:
    typedef double ElemType;   
     
    enum stat
    {
        OK = 0,
        ERROR
    };

private:
    int length;                 //List length.
    ElemType List[MAXSIZE];

public:
    SeqList():length(0){};
    ~SeqList(){};
    stat insertElem(int index, ElemType *e);
    stat pushBack(ElemType *e);
    stat pushFront(ElemType *e);

    stat deleteElem(int index, ElemType *e);
    stat popBack(ElemType *e);
    stat popFront(ElemType *e);

    stat getElem(int index, ElemType *e);
    
    int getLength(){ return length; }
};
///
///
SeqList::stat SeqList::getElem(int i, SeqList::ElemType *e)
{
    if(i >= length || i < 0)
    {
        return ERROR;
    }
    *e = List[i];
    return OK;
}

SeqList::stat SeqList::insertElem(int index, SeqList::ElemType *e)
{
    if(!(length <= MAXSIZE && index < length && index >=0))
    {
        return ERROR;
    }

    for(int i = length; i != index; --i)
    {
        List[i] = List[i - 1];
    }
    ++length;
    List[index] = *e;
    return OK;
}

SeqList::stat SeqList::pushBack(ElemType *e)
{
    if(length == MAXSIZE)
    {
        return ERROR;
    }
    List[length] = *e;
    ++length;
    return OK;
}

SeqList::stat SeqList::pushFront(ElemType *e)
{
    if(length == MAXSIZE)
    {
        return ERROR;
    }
    for(int i = length; i != 0; ++i)
    {
        List[i] = List[i-1];
    }
    List[0] = *e;
    ++length;
    return OK;
}

SeqList::stat SeqList::deleteElem(int index, ElemType *e)
{
    if(index >= length)
    {
        return ERROR;
    }
    for(int i = index + 1; i != length; ++i)
    {
        List[i - 1] = List[i];
    }
    --length;
    return OK;
}
SeqList::stat SeqList::popBack(ElemType *e)
{
    if(!length)
    {
        return ERROR;
    }
    --length;
    return OK;
}
SeqList::stat SeqList::popFront(ElemType *e)
{
    if(!length)
    {
        return ERROR;
    }
    for(int i = 1; i != length; ++i)
    {
        List[i - 1] = List[i];
    }
    --length;
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

二、链式存储结构LinkList

• 双向链表
• 使用头节点和为节点标记

定义了数据点的基本单元Node

class Node
{
public:
    typedef double NodeType;
    typedef std::shared_ptr<Node> pNode;  //定义数据类型
    NodeType data;	//节点数据
    pNode next;		//上一个节点
    pNode pre;		//下一个节点
    Node(NodeType d):data(d), next(nullptr), pre(nullptr){}
    Node():Node(0){}
    ~Node(){}
};
1
2
3
4
5
6
7
8
9
10
11
12

函数定义：

插入函数：

定义了八个插入函数：

• stat insertElem(int index, Node::pNode e); //插入在index指定的序号的前边
• stat insertElem(Node::pNode index, Node::pNode e); //插入在智能指针指定的序号前边
• stat pushBack(Node::pNode e); //在尾部插入
• stat pushFront(Node::pNode e); //在头部插入

上边四个函数插入的元素都是智能指针，也可以直接用节点存储的元素类型进行插入：

• stat insertElem(int index, Node::NodeType e); //front insert
• stat insertElem(Node::pNode index, Node::NodeType e); //front insert
• stat pushBack(Node::NodeType e);
• stat pushFront(Node::NodeType e);

删除函数：

定义了五个删除相关的函数：

• Node::pNode deleteElem(int index); //删除下标指向的元素，返回值为指向删除元素下一位的智能指针
• Node::pNode deleteElem(Node::pNode index); //删除指针指向的元素，返回值为指向删除元素下一位的智能指针
• Node::pNode popBack(); //删除尾元素，返回值同上
• Node::pNode popFront(); //删除首元素，返回值同上
• void clear(); //删除所有元素

辅助函数：

定义了四个辅助函数：

• Node::pNode getElem(int index); //返回下标代表的元素指针
• int getLength(){ return length; } //获取线性表长度
• Node::pNode getHead() { return head; } //获取首部指针
• Node::pNode getTail() { return tail; } //获取尾部指针

class LinkList
{
public:
    typedef Node ElemType; 
    enum stat
    {
        OK = 0,
        ERROR
    };
private:
    int length;
    Node::pNode head;
    Node::pNode tail;
public:
    LinkList();
    ~LinkList(){};
    stat insertElem(int index, Node::pNode e);              //front insert
    stat insertElem(Node::pNode index, Node::pNode e);      //front inseet
    stat pushBack(Node::pNode e);
    stat pushFront(Node::pNode e);

    stat insertElem(int index, Node::NodeType e);           //front insert
    stat insertElem(Node::pNode index, Node::NodeType e);   //front insert
    stat pushBack(Node::NodeType e);
    stat pushFront(Node::NodeType e);


    Node::pNode deleteElem(int index);
    Node::pNode deleteElem(Node::pNode index);
    Node::pNode popBack();
    Node::pNode popFront();

    Node::pNode getElem(int index);
    
    void clear();
    int getLength(){ return length; }
    Node::pNode getHead() { return head; }
    Node::pNode getTail() { return tail; }

};

/
///
LinkList::LinkList()
{
    head = std::make_shared<Node>();
    tail = std::make_shared<Node>();
    head->next = tail;
    tail->pre = head;
    length = 0;
}

Node::pNode LinkList::getElem(int index)
{
    if(!(index <= length && index >= 0))
    {
        return nullptr;
    }
    Node::pNode p = this->head->next;
    for(int i = 0; i != index; ++i)
    {
        p = p->next;
    }
    return p;
}

LinkList::stat LinkList::insertElem(int index, Node::pNode e)
{
    Node::pNode p = getElem(index);
    if(!p)
    {
        return ERROR;
    }
    
    e->next = p;
    e->pre = p->pre;
    p->pre->next = e;
    p->pre = e;
    
    ++length;
    return OK;
}

LinkList::stat LinkList::insertElem(Node::pNode index, Node::pNode e)
{
    if(index == nullptr || index->pre == nullptr)
    {
        return ERROR;
    }
    
    
    e->next = index;
    e->pre = index->pre;
    index->pre->next = e;
    index->pre = e;

    ++length;
    return OK;
}

LinkList::stat LinkList::pushBack(Node::pNode e)
{
    return insertElem(this->tail, e); 
}

LinkList::stat LinkList::pushFront(Node::pNode e)
{
    return insertElem(this->head->next, e); 
}

LinkList::stat LinkList::insertElem(int index, Node::NodeType e)
{
    Node::pNode p = std::make_shared<Node>(e);
    return insertElem(index, p);
}
LinkList::stat LinkList::insertElem(Node::pNode index, Node::NodeType e)
{
    Node::pNode p = std::make_shared<Node>(e);
    return insertElem(index, p);
}

LinkList::stat LinkList::pushBack(Node::NodeType e)
{
    Node::pNode p = std::make_shared<Node>(e);
    return pushBack(p); 
}

LinkList::stat LinkList::pushFront(Node::NodeType e)
{
    Node::pNode p = std::make_shared<Node>(e);
    return pushFront(p); 
}

Node::pNode LinkList::deleteElem(int index)
{
    Node::pNode p = getElem(index);
    if(!p)
    {
        return nullptr;
    }
    Node::pNode temp = p->next;

    p->pre->next = p->next;
    p->next->pre = p->pre;
    p->pre = nullptr;
    p->next = nullptr;
    
    --length;
    return temp;
}
Node::pNode LinkList::deleteElem(Node::pNode index)
{
    
    if(index == nullptr || index->pre == nullptr || index -> next == nullptr)
        return nullptr;
    Node::pNode temp = index->next;
    index->pre->next = index->next;
    index->next->pre = index->pre;
    index->pre = nullptr;
    index->next = nullptr;
    
    --length;
    return temp;
}
Node::pNode LinkList::popBack()
{
    return deleteElem(tail->pre);
}
Node::pNode LinkList::popFront()
{
    return deleteElem(head->next);
}
void LinkList::clear()
{
    length = 0; 
    Node::pNode p = head->next;
    while(p != tail)
    {
        p=deleteElem(p);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182