Python实现顺序表

关于顺序表的介绍，请参考：https://blog.csdn.net/weixin_43790276/article/details/103848039

Python 中的列表和元组都属于顺序表，下面根据顺序表的特性，自己来实现顺序表。

一、自定义一个顺序表类

在顺序表中，“表头”部分存储了当前顺序表的容量和已经有多少个数据。初始化一个顺序表时，需要按容量开辟一段内存来作为顺序表的数据存储空间，初始顺序表中的元素个数为0。

定义一个顺序表类 SequenceList ，初始化时可以指定顺序表的长度并开辟对应的存储空间，如默认长度为10，顺序表中的元素个数为0。

# coding=utf-8
class SequenceList(object):

    def __init__(self, max=10):
        self.max = max
        self.data = [None] * self.max
        self.num = 0

这样，就定义了一个顺序表类，实例化一个类对象就可以创建一个顺序表，只是还没有实现相应的功能。

二、实现顺序表的展示功能

    def is_empty(self):
        return self.num is 0

    def is_full(self):
        return self.num is self.max

    def show(self):
        print('<', end='')
        for i in range(0, self.num):
            if i != self.num-1:
                print(self.data[i], end=',')
            else:
                print(self.data[i], end='')
        print('>')

先实现判断顺序表是否为空的方法 is_empty() 和是否已满的方法 is_full()，这两个方法比较简单，如果顺序表中的数据是0个，则为空，如果数据数量已经达到了最大容量，则顺序表已满。

Python中的列表是用中括号，元组是小括号，所以也可以模仿，在展示自定义的顺序表时，使用尖括号，具体见 show() 方法。

if __name__ == '__main__':
    s = SequenceList()
    print("is_empty: ", s.is_empty())
    print("is_full: ", s.is_full())
    s.show()

运行结果：

is_empty:  True
is_full:  False
<>

三、实现顺序表中添加数据的功能

    def add(self, value):
        for j in range(self.num, 0, -1):
            self.data[j] = self.data[j-1]
        self.data[0] = value
        self.num += 1

    def append(self, value):
        self.data[self.num] = value
        self.num += 1

    def insert(self, i, value):
        if not isinstance(i, int):
            raise TypeError
        if i < 0:
            self.add(value)
        if i > self.num:
            self.append(value)
        for j in range(self.num, i, -1):
            self.data[j] = self.data[j-1]
        self.data[i] = value
        self.num += 1

    def count(self):
        return self.num

添加数据到顺序表中，可以从头部添加、从尾部添加或从指定位置添加。

add(value)：从头部添加时，为了保证顺序表的顺序关系，原有的数据需要依次往后移动一个位置，所以从顺序表尾部开始遍历，将每个数据的索引值都加1，然后将添加的数据放在顺序表的第一个位置，添加完成后将顺序表的数量加1。

append(value)：从尾部添加时，直接将数据添加在顺序表最后一个数据的后面，然后将顺序表的数量加1。

insert(i, value)：在指定位置添加数据时，指定位置前面的数据不变，后面的数据都需要往后移动一个位置，所以从顺序表尾部开始遍历，将这些数据的索引值都加1，然后将添加的数据放在指定位置，再将顺序表的数量加1。

如果指定的位置是负数或超过了顺序表最大长度，则需要特殊处理，上面的处理是负数就在头部添加，超过最大长度就在尾部添加。也可以直接抛出 IndexError ，这个按需实现就可以了。

同时实现了查看顺序表长度的方法 count()，返回当前顺序表的数据个数。

    s.add(1)
    s.add(10)
    s.append(2)
    s.append(3)
    s.append(4)
    s.show()
    s.insert(1, 20)
    s.show()
    print("顺序表长度：", s.count())

运行结果：

<10,1,2,3,4>
<10,20,1,2,3,4>
顺序表长度： 6

四、实现顺序表的查询和修改功能

    def is_exist(self, value):
        for j in range(self.num):
            if self.data[j] == value:
                return True
        else:
            return False

    def index(self, value):
        for j in range(self.num):
            if self.data[j] == value:
                return j
        else:
            return -1

    def __getitem__(self, item):
        if not isinstance(item, int):
            raise TypeError
        if 0 <= item < self.num:
            return self.data[item]
        else:
            raise IndexError

    def __setitem__(self, key, value):
        if not isinstance(key, int):
            raise TypeError
        if 0 <= key < self.num:
            self.data[key] = value
        else:
            raise IndexError

在顺序表中添加数据后，就不再是一个空的表了。会有很多关于顺序表中的数据查询需求。

is_exist(value)：判断一个数据是否存在顺序表中，遍历顺序表的每个数据，如果数据值与目标值相等，则说明顺序表中存在目标值。

index(value)：返回一个数据在顺序表中的索引位置，与判断是否存在的实现方式一样，这里返回的是索引的值，如果顺序表中没有这个数据，则返回-1。

__getitem__(item)：根据索引查询某个索引的数据，给定一个索引值，直接返回顺序表中该位置的数据即可，如果给的索引值超出了索引范围，应该直接抛出 IndexError 。这个方法之所以重写 Python 中的 __getitem__() 魔法方法，是因为 __getitem__() 实现了列表下标的方式来操作数据，支持 s[1] 这种类型的语法。这样写之后，既可以使用 s[1] 来获取顺序表中索引1的数据，也可以使用 s.__getitem__(1) ，结果相同。

__setitem__(key, value)：修改指定位置的数据，先根据给定的索引值，找到顺序表中该索引的数据，然后修改。重写 __setitem__() 方法的原因与 __getitem__() 相同。

    s.show()
    print(s.is_exist(200))
    print(s.index(20))
    print(s.__getitem__(1))
    print(s[1])
    s[2] = 30
    s.__setitem__(3, 40)
    s.show()

运行结果：

<10,20,1,2,3,4>
False
1
20
20
<10,20,30,40,3,4>

五、实现顺序表的删除功能

    def remove(self, i):
        if not isinstance(i, int):
            raise TypeError
        if i < 0 or i >= self.num:
            raise IndexError
        for j in range(i, self.num):
            if j == self.num-1:
                self.data[j] = None
            else:
                self.data[j] = self.data[j+1]
        self.num -= 1

    def delete(self, value):
        for i in range(self.num):
            if self.data[i] == value:
                self.remove(i)
                return

    def delete_all(self, value):
        for i in range(self.num):
            if self.data[i] == value:
                self.remove(i)
                self.delete_all(value)

对顺序表执行删除操作之后，依然要保证顺序表中的数据顺序关系。

remove(i)：删除指定索引的数据，删除指定索引位置的数据之后，该索引后面的数据都要依次往前移动。所以从指定索引的位置开始，依次将后一个位置的数据赋值给前一个位置，就实现了数据的删除。如果到了最后一个位置，则直接将它赋值为空就可以了。删除之后，顺序表的数量减1。

delete(value)：删除指定值的数据，先遍历顺序表，找到对应值的索引，然后调用上面按索引删除的方法，即可删除指定的数据。使用这个方法，如果顺序表中有多个满足条件的数据，只会删除最前面的一个数据。

delete_all(value)：删除所有相等的值，如果顺序表中有多个数据与指定值相等，删除第一个数据后，顺序表中数据的数量 self.num 会减1，继续遍历顺序表，会出现删除不完全甚至程序出错的情况。所以在删除第一个数据之后，递归调用自身，这样重新遍历时使用的是减1之后的 self.num ，不会出现漏删或错误。（也可以自己使用其他方式实现）

    s.show()
    s.remove(5)
    s.show()
    s.append(4)
    s.append(4)
    s.append(4)
    s.append(4)
    s.append(4)
    print("is_full: ", s.is_full())
    s.show()
    print("s的长度：", s.count())
    s.delete(4)
    s.show()
    s.delete_all(4)
    s.show()

运行结果：

<10,20,30,40,3,4>
<10,20,30,40,3>
is_full:  True
<10,20,30,40,3,4,4,4,4,4>
s的长度： 10
<10,20,30,40,3,4,4,4,4>
<10,20,30,40,3>

以上就是 Python 中顺序表及一些简单方法的实现。

上面的顺序表容量默认设置是10，如果超过10(可以改大)会报 IndexError ，使用时要注意。因为这个顺序表类中没有实现动态扩容的方法，不像 Python 中的列表有自动扩容的机制，如果需要的话可以继续实现扩容的方法。

顺序栈的基本操作实现---入栈、出栈、判断是否为空

栈本身就比较简单，栈的基本概念推荐文章：http://blog.csdn.net/hguisu/article/details/7674195

实现代码如下：

stack.h 栈的头文件：

#pragma once 
#include <iostream>

#define MAX 10  // 注意没有分号
class stack
{
private:
	int arr[MAX];
	int top;

public:
	stack()   //构造函数
	{
	    top = -1;
	}

	void pop(int val); //入栈
	int push();//出栈
	bool isFull(); //判断是否栈满
	bool isEmpty();//判断是否为空栈


};//有分号

#include "stack.h"
using namespace std;

bool stack::isEmpty()
{
	if(top == -1)
	{
		cout <<"is empty" << endl;
		return true;
	}
	else 
		return false;
}

bool stack::isFull()
{
	if(top == MAX)
	{
		cout <<"is full " << endl;
		return true;
	}
	else 
		return false;
}

// 入栈，先判断是否满
void stack::pop(int val)
{
	if(isFull() == 1)
		cout << "have full" << endl;
	else 
	{
		top++;
		arr[top] = val;
		
	}
}

// 出栈，判断是否为空
int stack::push()
{
	if(isEmpty() == 1)
		cout <<"have empty" <<endl;
	else 
	{
		int data = arr[top];
		arr[top] = NULL;
		top--;
		return data;
	}
}

#include "stack.h"
using namespace std;

int main ()
{
	stack test;
	test.isEmpty();

	test.pop(1);
	test.pop(2);
	test.pop(3);
	test.isFull();

	int data1 = test.push ();
	cout <<"出栈数字为" << data1 << endl;

	int data2 = test.push ();
	cout <<"出栈数字为" << data2 << endl;

	system ("pause");
	return 0;

}