数据结构学习心得——顺序表

梦里梦外; 2022-06-10 10:27 881阅读 0赞

## 一、线性表的定义 ##

线性表是具有相同特性数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n（n>0）表示。

## 二、线性表的存储结构 ##

线性表的存储结构有顺序存储和链式存储两种。前者称为顺序表，后者称为链表（链表见下篇博客，这里介绍下顺序表）。

1.  顺序表  
    顺序表就是把线性表中的所有元素按照其逻辑顺序，一次存储到从指定的春初位置开始的一块连续的存储空间中。
2.  顺序表的操作  
    顺序表的基本操作有初始化，求指定位置元素，查找，插入，删除，输出等操作。以下用C++语言来实现这些操作。

#include <iostream>
    
    using namespace std;
    
    //顺序表结构体的定义
    typedef struct Sqlist
    {
        int data[20];
        int length;
    }Sqlist;
    
    //顺序表的初始化
    void initSqlist(int a[],int n,Sqlist &L)
    {
        int i;
        for(i=0;i<n;i++)
        {
            L.data[i]=a[i];
            L.length=n;
        }
    }
    
    //求指定第p位元素
    int getElem(Sqlist L,int p)
    {
        return L.data[p-1];
    }
    
    //顺序表中查找第一个值等于e的元素
    int findElem(Sqlist L,int e)
    {
        int i;
        for(i=0;i<L.length;i++)
        {
            if(L.data[i]==e)
            {
                return i+1;
            }
        }
        return -1;
    }
    
    //顺序表中插入元素(第p位插入e元素)
    void insertElem(Sqlist &L,int p,int e)
    {
        int i;
        for(i=L.length-1;i>=p-1;i--)
        {
            L.data[i+1]=L.data[i];
        }
        L.data[p-1]=e;
        L.length++;
    }
    
    //顺序表的删除第p位元素
    void deleElem(Sqlist &L,int p)
    {
        int i;
        for(i=p-1;i<=L.length-1;i++)
        {
            L.data[i]=L.data[i+1];
        }
        L.length--;
    }
    
    //输出顺序表中的所有元素
    void printList(Sqlist L)
    {
        int i;
        cout<<"顺序表中有"<<L.length<<"个元素"<<endl;
        cout<<"分别为：";
        for(i=0;i<=L.length-1;i++)
        {
            cout<<L.data[i]<<" ";
        }
        cout<<endl;
    }
    int main()
    {
        Sqlist L;
        int a[7]={
       7,2,3,6,8,2,1};
    
        initSqlist(a,7,L);
    
        printList(L);
        cout<<"第二位元素为："<<getElem(L,2)<<endl;
    
        cout<<"8元素的位置为："<<findElem(L,8)<<endl;
    
        insertElem(L,3,0);
        cout<<"插入后";
        printList(L);
    
        deleElem(L,3);
        cout<<"删除后";
        printList(L);
    
        return 0;
    }

运行结果如下图所示：  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20220610/2264ba3bc9704e69b693d57736a45d66.png