顺序表基础—C语言版

1.定义

顺序表是指用一组连续的地址存储单元来存储数据元素。

2.优缺点

1. 优点：a.存储密度大；b.可以随机存储元素。
2. 缺点：a.数据元素最大个数需要事先确定; b.删除与插入效率低; c. 不便于扩充空间

3.基础操作

1. 顺序表的插入，我们采用动态分配，以便扩充

#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100     //初始分配容量
#define LIST_INCREMEN 10      //扩增容量
typedef struct
{
    int *data;   //存储地址
    int length;  //表长
    int listsize;//表的存储空间容量
}SqList;
void InitList_Sq(SqList &L); //初始化顺序表
void InsertList_Sq(SqList &L,int i,int e); //顺序表插入操作,i是插入位置，e是插入值
main()
{
    SqList L;
    InitList_Sq(L);
    InsertList_Sq(L,1,3);
    printf("data= %d ",L.data[0]);
}
void InitList_Sq(SqList &L)
{
    L.data=(int *)malloc(LIST_INIT_SIZE*sizeof(int)); //申请空表L
    if(!L.data) //判断是否申请成功
    {
        printf("分配错误\n");
        exit(0);
    }
    L.length=0; //初始时长度为0
    L.listsize=LIST_INIT_SIZE;

}
void InsertList_Sq(SqList &L,int i,int e)
{
    int j;
    if(i<0||i>L.length+1) //判断i值是否合法
    {
        printf("请输入正确的i\n");
        exit(0);
    }
    if(L.length>=L.listsize) //若表满，扩增空间
    {
        int *newbase=(int *)realloc(L.data,(LIST_INIT_SIZE+LIST_INCREMEN)*sizeof(int));
        if(!L.data) //判断是否申请成功
        {
            printf("申请失败\n");
            exit(0);
        }
        L.data=newbase;
        L.listsize+=LIST_INCREMEN;
    }
    for(j=L.length;j>=i;j--)
    {
        L.data[j]=L.data[j-1];
    }
    L.data[i-1]=e;
    L.length++;
}

2.顺序表的删除

void DeleteList_Sq(SqList &L,int i)
{
    int j;
    if(i<0||i>L.length)
    {
        printf("请输入正确的i\n");
        exit(0);
    }
    for(j=i;j<L.length;j++) //将 i右边的元素全部左移
    {
        L.data[j-1]=L.data[j];
    }
    L.length--;

}

3.顺序表定位第一个与e匹配的元素位置

int  LocateData_Sq(SqList &L,int e)
{
    int i;
    for(i=0;i<L.length;i++)
    {
        if(e==L.data[i]) return i+1;
    }
    return 0;
}

4.将不在L中的元素插入到S中

void UnionList_Sq(SqList &L,SqList S)
{
    int i,j;
    for (i=0;i<S.length;i++)
    {
        if(LocateData_Sq(L,S.data[i]))
            InsertList_Sq(L,++L.length,S.data[i]);
    }
}

5.已知L,S 按顺序递增，将其按递增顺序插入到顺序表M

void MergeList_Sq(SqList L,SqList S,SqList &M)
{
    int *pa=L.data,*pb=S.data,*pc=NULL;
    M.listsize=L.listsize+S.listsize;
    M.data=(int *)malloc(M.listsize*sizeof(int));
    pc=M.data;
    if(!M.data)
    {
        printf("申请失败\n");
        exit(0);
    }
    while(*pa<=L.data[L.length-1]&&*pb<=L.data[S.length-1]) //判断是否是最后一个元素
    {
        *pa<=*pb?*pc++=*pa++:*pc++=*pb++;
    }
    while(*pa<=L.data[L.length-1]) *pc++=*pa++; //插入L中剩余元素
    while(*pb<=L.data[L.length-1]) *pc++=*pb++; //插入S中剩余元素
}

4.对于&符号

1. 如下在x.c为后缀的c代码中无法运行,无法引用取地址符&传参

function( &l)
{
    ......
}

2. 只允许如下

function( l)
{
    ......
}
function(*l)
{
    ......
}

3. 在x.cpp后缀的c++代码中，就可以用区地址符&作为参数

function( &l)
{
    ......
}