线性表顺序存储结构

顺序存储结构有三属性：

1：存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置

2：线性表的最大存储容量：数组长度MaxSize

3：线性表的当前长度：length

#define MAXSIZE 20

typedef int ElemType;

typedef struct

{

    ElemType data[MAXSIZE];

    int length;

}SqList;

线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，它是变化的，但在任意时刻，应该都小于等于数组的长度

优点是无需为了表示表中元素之间的逻辑关系而增加额外存储空间，可以快速存和取表中任一位置的元素；缺点是插入和删除需要移动大量元素，当线性表长度变化较大时，难以确定存储空间的容量，造成存储空间的“碎片”

#include<stdio.h>

#define MaxLen 100

typedef struct
{
    int length ;
    int data[MaxLen] ;
}List ;

int InsertList( List *L, int i, int x )
{
    int k ;
    if( i < 1 || i > L -> length+1 )
    {
        return -1 ;
    }
    if( L -> length >= MaxLen )
    {
        printf( “线性表溢出!” ) ;
        return -1 ;
    }

    for( k = L -> length; k >= i-1; k– )
        L -> data[k+1] = L -> data[k] ;        //结点后移
    L -> data[i-1] = x ;        //插入x
    L -> length ++ ;            //线性表长度增加1

    return 0 ;
}

int DeleteItem( List *L, int n)
{
    int i ;
    if( n < 1 || n > L -> length )
        return -1 ;

    for( i = n-1; i < L -> length; i++ )
        L -> data[i] = L -> data[i+1] ;         //结点前移
    L -> length — ;        //线性表长度减1

    return 0 ;
}

int FindItem( List *L, int x )
{
    int i ;
    for( i = 0; i < L -> length; i++ )
        if( x == L -> data[i] )
            return i+1 ;

    return -1 ;
}

int main()
{
    List L;
    int i;

    //初始化线性表
    for( i = 0; i < 10; i++ )
        L.data[i] = i ;
    L.length = 10 ;
    printf(“First:    “);
    for( i = 0; i < L.length; i++ )
        printf(“%d “, L.data[i] );

    //执行插入操作
    InsertList( &L, 5, 100 ) ;
    printf(“\nInsert:    “);
    for( i = 0; i < L.length; i++ )
        printf(“%d “, L.data[i] );
   
    //执行删除操作
    DeleteItem( &L, 6 ) ;
    printf(“\nDelete:    “);
    for( i = 0; i < L.length; i++ )
        printf(“%d “, L.data[i] );

    //执行查找操作
    printf(“\nSearch:    “);
    printf( “9 is in pos %d “, FindItem( &L, 9 ) ) ;
    printf(“\n”);
    return 0 ;
}

lihui@LastWish $ ./a.out
First:  0 1 2 3 4 5 6 7 8 9
Insert: 0 1 2 3 100 4 5 6 7 8 9
Delete: 0 1 2 3 100 5 6 7 8 9
Search: 9 is in pos 10