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

一、线性表的定义

线性表是具有相同特性数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用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;
}

运行结果如下图所示：