数据结构-顺序表的结构与代码实现

左手的ㄟ右手 2024-03-16 14:05 58阅读 0赞

**目录**

一、前言

二、什么是顺序表

三、顺序表的实现

1. 顺序表的存储结构

2. 顺序表的基本操作

（1）创建顺序表

（2）插入元素

（3）删除元素

（4）查找元素

四、顺序表的优缺点

1. 优点

2. 缺点

C++实现

Java实现

Python实现

Cobol实现

--------------------

## 一、前言 ##

在计算机科学中，数据结构是一种组织和存储数据的方式，以便于访问和修改。数据结构是计算机科学中的基础，它是算法的基础。数据结构可以分为两种类型：线性结构和非线性结构。顺序表是线性结构中最基本的一种数据结构，它是一种连续的存储结构，可以用数组来实现。本篇博客将详细介绍顺序表的定义、实现、优缺点以及应用场景。

## 二、什么是顺序表 ##

顺序表是一种线性结构，它是一种连续的存储结构，可以用数组来实现。顺序表中的元素在内存中是连续存储的，每个元素都有一个唯一的下标，可以通过下标来访问元素。顺序表中的元素可以是任意类型的数据，如整数、浮点数、字符、字符串等。

顺序表是一种静态的数据结构，它的大小在创建时就已经确定，无法动态地改变大小。如果需要添加或删除元素，需要重新创建一个新的顺序表，并将原来的元素复制到新的顺序表中。

## 三、顺序表的实现 ##

### 1. 顺序表的存储结构 ###

顺序表的存储结构可以用数组来实现。数组是一种连续的存储结构，可以通过下标来访问元素。顺序表中的元素在数组中是按照顺序存储的，每个元素都有一个唯一的下标，可以通过下标来访问元素。

下面是一个简单的顺序表的定义：

#define MAXSIZE 100  // 定义顺序表的最大长度
    
    typedef struct {
        int data[MAXSIZE];  // 存储顺序表中的元素
        int length;         // 顺序表的长度
    } SeqList;

### 2. 顺序表的基本操作 ###

顺序表的基本操作包括创建、插入、删除、查找和遍历等。

#### （1）创建顺序表 ####

创建顺序表需要先定义一个结构体，然后初始化顺序表的长度为0。下面是创建顺序表的代码：

SeqList* createSeqList() {
        SeqList* L = (SeqList*)malloc(sizeof(SeqList));  // 分配内存空间
        L->length = 0;  // 初始化顺序表的长度为0
        return L;
    }

#### （2）插入元素 ####

在顺序表中插入元素需要先判断顺序表是否已满，如果已满则无法插入元素。如果顺序表未满，则需要将插入位置后面的元素依次向后移动一位，然后将新元素插入到指定位置。下面是插入元素的代码：

bool insert(SeqList* L, int index, int value) {
        if (L->length >= MAXSIZE) {  // 判断顺序表是否已满
            return false;
        }
      
        if (index < 1 || index > L->length + 1) {  // 判断插入位置是否合法
            return false;
        }
        for (int i = L->length; i >= index; i--) {  // 将插入位置后面的元素依次向后移动一位
            L->data[i] = L->data[i - 1];
        }
        L->data[index - 1] = value;  // 将新元素插入到指定位置
        L->length++;  // 顺序表长度加1
        return true;
    }

#### （3）删除元素 ####

在顺序表中删除元素需要先判断顺序表是否为空，如果为空则无法删除元素。如果顺序表不为空，则需要将删除位置后面的元素依次向前移动一位，然后将顺序表的长度减1。下面是删除元素的代码：

bool remove(SeqList* L, int index) {
        if (L->length == 0) {  // 判断顺序表是否为空
            return false;
        }
        if (index < 1 || index > L->length) {  // 判断删除位置是否合法
            return false;
        }
        for (int i = index; i < L->length; i++) {  // 将删除位置后面的元素依次向前移动一位
            L->data[i - 1] = L->data[i];
        }
        L->length--;  // 顺序表长度减1
        return true;
    }

#### （4）查找元素 ####

在顺序表中查找元素需要遍历整个顺序表，逐个比较元素的值，直到找到目标元素或者遍历完整个顺序表。下面是查找元素的代码：

int LocateElem(SqList L, int e) {
        int i;
        for (i = 0; i < L.length; i++) {
            if (L.data[i] == e) {
                return i; // 返回元素在顺序表中的位置
            }
        }
        return -1; // 如果未找到，返回-1
    }

## 四、顺序表的优缺点 ##

### 1. 优点 ###

1. 随机访问效率高：顺序表中的元素在内存中是连续存储的，因此可以通过下标直接访问任意位置的元素，访问效率非常高。

2. 存储密度高：顺序表中的元素存储在一段连续的存储空间中，因此存储密度非常高，不会出现像链表那样的指针占用额外的存储空间。

3. 空间利用率高：顺序表中的元素存储在一段连续的存储空间中，因此不会出现像链表那样的内存碎片，空间利用率非常高。

4. 适合于大量随机访问的场景：由于顺序表的随机访问效率非常高，因此适合于需要大量随机访问的场景，比如数组、矩阵等。

### 2. 缺点 ###

1. 插入和删除效率低：由于顺序表中的元素存储在一段连续的存储空间中，因此在插入和删除元素时需要移动其他元素，效率比较低。

2. 存储空间需要预先分配：顺序表的存储空间需要预先分配，因此在存储空间不足时需要重新分配更大的空间，并将原有的元素复制到新的空间中，这样会造成一定的时间和空间浪费。

3. 不适合频繁的插入和删除操作：由于顺序表的插入和删除操作效率比较低，因此不适合频繁的插入和删除操作，比如链表等数据结构更适合这种场景。

4. 内存浪费：由于顺序表的存储空间需要预先分配，因此当存储空间没有被充分利用时，会造成一定的内存浪费。

## C++实现 ##

以下是使用C++实现顺序表的完整代码：

#include <iostream>
    using namespace std;
    
    const int MAXSIZE = 100; // 定义顺序表的最大长度
    
    class SeqList {
    private:
        int data[MAXSIZE]; // 存储数据的数组
        int length; // 当前顺序表的长度
    public:
        SeqList() { // 构造函数，初始化顺序表
            length = 0;
        }
        ~SeqList() {} // 析构函数，不需要进行任何操作
        bool isEmpty() { // 判断顺序表是否为空
            return length == 0;
        }
        bool isFull() { // 判断顺序表是否已满
            return length == MAXSIZE;
        }
        int getLength() { // 获取顺序表的长度
            return length;
        }
        int getElem(int i) { // 获取顺序表中第i个元素的值
            if (i < 1 || i > length) { // 判断i是否越界
                cout << "Error: index out of range!" << endl;
                return -1;
            }
            return data[i-1];
        }
        int locateElem(int e) { // 查找元素e在顺序表中的位置
            for (int i = 0; i < length; i++) {
                if (data[i] == e) {
                    return i+1;
                }
            }
            return 0;
        }
        bool insert(int i, int e) { // 在顺序表的第i个位置插入元素e
            if (i < 1 || i > length+1) { // 判断i是否越界
                cout << "Error: index out of range!" << endl;
                return false;
            }
            if (isFull()) { // 判断顺序表是否已满
                cout << "Error: the list is full!" << endl;
                return false;
            }
            for (int j = length; j >= i; j--) { // 将第i个位置及之后的元素后移
                data[j] = data[j-1];
            }
            data[i-1] = e; // 将元素e插入到第i个位置
            length++; // 长度加1
            return true;
        }
        bool remove(int i) { // 删除顺序表中第i个位置的元素
            if (i < 1 || i > length) { // 判断i是否越界
                cout << "Error: index out of range!" << endl;
                return false;
            }
            for (int j = i; j < length; j++) { // 将第i个位置及之后的元素前移
                data[j-1] = data[j];
            }
            length--; // 长度减1
            return true;
        }
        void printList() { // 输出顺序表中所有元素
            if (isEmpty()) { // 判断顺序表是否为空
                cout << "The list is empty." << endl;
                return;
            }
            cout << "The list is: ";
            for (int i = 0; i < length; i++) {
                cout << data[i] << " ";
            }
            cout << endl;
        }
    };
    
    int main() {
        SeqList list;
        list.insert(1, 10);
        list.insert(2, 20);
        list.insert(3, 30);
        list.printList(); // 输出：The list is: 10 20 30
        list.remove(2);
        list.printList(); // 输出：The list is: 10 30
        cout << "The length of the list is: " << list.getLength() << endl; // 输出：The length of the list is: 2
        cout << "The element at position 2 is: " << list.getElem(2) << endl; // 输出：The element at position 2 is: 30
        cout << "The position of element 10 is: " << list.locateElem(10) << endl; // 输出：The position of element 10 is: 1
        return 0;
    }

在上面的代码中，我们定义了一个SeqList类，其中包含了顺序表的基本操作，如插入、删除、查找等。在主函数中，我们创建了一个SeqList对象list，并对其进行了一些操作，最后输出了一些结果。

## Java实现 ##

public class SeqList<T> {
        private Object[] elementData; // 存储元素的数组
        private int size; // 元素个数
    
        // 默认容量为10
        public SeqList() {
            this(10);
        }
    
        // 指定初始容量
        public SeqList(int initialCapacity) {
            if (initialCapacity < 0) {
                throw new IllegalArgumentException("容量不能为负数：" + initialCapacity);
            }
            this.elementData = new Object[initialCapacity];
            this.size = 0;
        }
    
        // 获取元素个数
        public int size() {
            return this.size;
        }
    
        // 判断是否为空
        public boolean isEmpty() {
            return this.size == 0;
        }
    
        // 获取指定位置的元素
        public T get(int index) {
            checkIndex(index);
            return (T) this.elementData[index];
        }
    
        // 修改指定位置的元素
        public void set(int index, T element) {
            checkIndex(index);
            this.elementData[index] = element;
        }
    
        // 在指定位置插入元素
        public void add(int index, T element) {
            if (index < 0 || index > this.size) {
                throw new IndexOutOfBoundsException("索引越界：" + index);
            }
            ensureCapacity(this.size + 1);
            System.arraycopy(this.elementData, index, this.elementData, index + 1, this.size - index);
            this.elementData[index] = element;
            this.size++;
        }
    
        // 在末尾添加元素
        public void add(T element) {
            add(this.size, element);
        }
    
        // 删除指定位置的元素
        public T remove(int index) {
            checkIndex(index);
            T oldValue = (T) this.elementData[index];
            int numMoved = this.size - index - 1;
            if (numMoved > 0) {
                System.arraycopy(this.elementData, index + 1, this.elementData, index, numMoved);
            }
            this.elementData[--this.size] = null;
            return oldValue;
        }
    
        // 清空顺序表
        public void clear() {
            for (int i = 0; i < this.size; i++) {
                this.elementData[i] = null;
            }
            this.size = 0;
        }
    
        // 检查索引是否越界
        private void checkIndex(int index) {
            if (index < 0 || index >= this.size) {
                throw new IndexOutOfBoundsException("索引越界：" + index);
            }
        }
    
        // 扩容
        private void ensureCapacity(int minCapacity) {
            if (minCapacity > this.elementData.length) {
                int newCapacity = this.elementData.length * 2;
                if (newCapacity < minCapacity) {
                    newCapacity = minCapacity;
                }
                this.elementData = Arrays.copyOf(this.elementData, newCapacity);
            }
        }
    }
    ```
    
    使用示例：
    
    ```java
    SeqList<String> list = new SeqList<>();
    list.add("A");
    list.add("B");
    list.add("C");
    System.out.println(list.get(1)); // 输出 B
    list.set(1, "D");
    System.out.println(list.get(1)); // 输出 D
    list.add(1, "E");
    System.out.println(list.get(1)); // 输出 E
    System.out.println(list.remove(2)); // 输出 D
    list.clear();
    System.out.println(list.isEmpty()); // 输出 true

## Python实现 ##

class SeqList:
        def __init__(self, maxsize=None):
            self.maxsize = maxsize
            self._items = [None] * maxsize
            self.length = 0
    
        def __getitem__(self, index):
            if index < self.length:
                return self._items[index]
            else:
                raise IndexError('Index out of range')
    
        def __setitem__(self, index, value):
            if index < self.length:
                self._items[index] = value
            else:
                raise IndexError('Index out of range')
    
        def __len__(self):
            return self.length
    
        def __repr__(self):
            return str(self._items[:self.length])
    
        def insert(self, index, value):
            if self.length >= self.maxsize:
                raise Exception('SeqList is full')
            if index < 0 or index > self.length:
                raise IndexError('Index out of range')
            for i in range(self.length, index, -1):
                self._items[i] = self._items[i-1]
            self._items[index] = value
            self.length += 1
    
        def delete(self, index):
            if index < 0 or index >= self.length:
                raise IndexError('Index out of range')
            for i in range(index, self.length-1):
                self._items[i] = self._items[i+1]
            self._items[self.length-1] = None
            self.length -= 1
    ```
    
    使用方法：
    
    ```python
    # 创建一个长度为5的顺序表
    lst = SeqList(5)
    
    # 插入元素
    lst.insert(0, 1)
    lst.insert(1, 2)
    lst.insert(2, 3)
    
    # 输出顺序表
    print(lst)  # [1, 2, 3]
    
    # 删除元素
    lst.delete(1)
    
    # 输出顺序表
    print(lst)  # [1, 3]

## Cobol实现 ##

以下是使用COBOL语言实现顺序表的示例代码：

IDENTIFICATION DIVISION.
    PROGRAM-ID. SEQUENTIAL-LIST.
    
    DATA DIVISION.
    WORKING-STORAGE SECTION.
    01 LIST-SIZE PIC 9(4) VALUE 100.
    01 LIST OCCURS 0 TO 99 TIMES DEPENDING ON LIST-SIZE.
       05 LIST-ITEM PIC X(20).
    01 LIST-COUNT PIC 9(4) VALUE 0.
    
    PROCEDURE DIVISION.
    MAIN-LOGIC.
        DISPLAY "SEQUENTIAL LIST PROGRAM".
        PERFORM DISPLAY-MENU UNTIL LIST-COUNT = 100.
        STOP RUN.
    
    DISPLAY-MENU.
        DISPLAY "1. ADD ITEM TO LIST".
        DISPLAY "2. DELETE ITEM FROM LIST".
        DISPLAY "3. DISPLAY LIST".
        DISPLAY "4. EXIT".
        DISPLAY "ENTER YOUR CHOICE: ".
        ACCEPT CHOICE.
        EVALUATE CHOICE
            WHEN 1
                PERFORM ADD-ITEM
            WHEN 2
                PERFORM DELETE-ITEM
            WHEN 3
                PERFORM DISPLAY-LIST
            WHEN 4
                EXIT PROGRAM
            WHEN OTHER
                DISPLAY "INVALID CHOICE".
        END-EVALUATE.
    
    ADD-ITEM.
        IF LIST-COUNT = 100
            DISPLAY "LIST IS FULL"
            GO TO MAIN-LOGIC
        END-IF
        DISPLAY "ENTER ITEM TO ADD: ".
        ACCEPT LIST-ITEM(LIST-COUNT)
        ADD 1 TO LIST-COUNT.
    
    DELETE-ITEM.
        IF LIST-COUNT = 0
            DISPLAY "LIST IS EMPTY"
            GO TO MAIN-LOGIC
        END-IF
        DISPLAY "ENTER ITEM TO DELETE: ".
        ACCEPT DELETE-ITEM
        SEARCH LIST
            AT END
                DISPLAY "ITEM NOT FOUND"
            WHEN LIST-ITEM(LIST-COUNT) = DELETE-ITEM
                SUBTRACT 1 FROM LIST-COUNT
                DISPLAY "ITEM DELETED"
            WHEN OTHER
                CONTINUE
        END-SEARCH.
    
    DISPLAY-LIST.
        IF LIST-COUNT = 0
            DISPLAY "LIST IS EMPTY"
            GO TO MAIN-LOGIC
        END-IF
        DISPLAY "LIST CONTENTS: "
        PERFORM VARYING I FROM 1 BY 1 UNTIL I > LIST-COUNT
            DISPLAY LIST-ITEM(I)
        END-PERFORM.

这个程序定义了一个大小为100的顺序表，使用LIST-COUNT变量来跟踪列表中的元素数量。主逻辑部分包括一个菜单，允许用户添加、删除和显示列表中的元素。ADD-ITEM和DELETE-ITEM子程序分别用于添加和删除元素，DISPLAY-LIST子程序用于显示列表中的元素。