线性表之顺序表理解


一息若存,希望不灭。

顺序表的分类

1. 静态分配储存空间

#define MAXSIZE 100
typedef  struct
{
    char   Data[MAXSIZE];    //100个字节
    int   curlen;                                //4个字节
    int   totalLen;                                //4个字节
}SeqList,  *PSeqList;   

2. 动态分配储存空间

typedef  struct
{
    char*  pData;    //4个字节
    int   curLen;      //4个字节
    int   totalLen;     //4个字节
}SeqList,  *PSeqList; 

以动态链表为例

基本想法

1.

2.如果想采用一个封装的想法,可以把所有的操作都写入一个类中。

3.这里用C语言实现,使用函数实现。


初始化函数:
InitList()

main : Seqlist plist = NULL;
ret = InitList( &pList );
InitList : int InitList(SeqList `*
`ppList)

二级指针

传 InitList(&pList)

这里为什么传入是二级指针?
第一种:首先plist已经是一个一级指针。再传一个地址进去,就是**的类型了
第二种:首先我要传一个东西出来,一重指针,传出来的数据类型还是一个地址(plist ),因此需要**

二级指针解释关于内存图

因为InitList()函数用完就会消失,所以要让plist指向堆区数组


C语言代码实现

具体代码实现如下

 /*
    适用于标准C
 */

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define OVERFLOW 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

#define Elemtype char

//公共错误码,项目组成员之间的共同约定
#define MALLOC_ERROR  -1  
#define NOTFIND  -2
#define PARAM_ERROR -3
#define REALLOC_ERROR  -4  
//顺序表的结构定义
typedef struct 
{
    Elemtype *pElem;    //动态模式,只定义了一个指针,未分配数据的存储空间。本例假设每个元素都是char型,此处是实际应用中每个元素可能会是结构体变量或者结构体指针
    int iCount;         //当前长度
    int iTotalLength;   //线性表的总长度
}SeqList;               //定义一个新类型,顺序表的类型名称


//初始化函数
//因为本子函数想通过子函数的操作,更改主调函数中某个指针的指向,则需要用到二重指针(要在子函数中修改实参的值,需要加一重指针,而这个实参变量还是个一重指针,所以这里累计是1+1=2重指针了!!)
//本函数假设要修改的实参指针只是一个指针变量(占4个字节,初始指向哪里不重要,为NULL也行),尚未指向任何结构体变量。
 int InitList(SeqList **ppList)
 {
    SeqList *pTemp; //在子函数的栈区定义一个临时指针,以方便本函数中后续的建表过程中的各行代码的书写

    pTemp= (SeqList*)malloc(sizeof(SeqList));  //先申请12个字节,用于存放顺序表的基本结构,iCount,ITotalLength和pElem成员才会存在
    if(pTemp==NULL)
    {
        return MALLOC_ERROR;
    }
    pTemp->iCount=0; //初始时,一个元素都没有
    pTemp->iTotalLength= LIST_INIT_SIZE;  //初始时理论总长就是100个元素(假定值)
    pTemp->pElem= (Elemtype *)malloc( LIST_INIT_SIZE * sizeof(Elemtype));  //因为SeqList的定义中,elem只是一个指针,需要分配空间并让该指针指向这段空间。因为malloc可能迸发异常,所以实际中往往会放在try {} catch() {}结构中
    if (pTemp->pElem==NULL)
    {
        free(pTemp);    //将之前申请的基本表结构所占的空间(12个字节)释放 指的是pTemp指的那个位置被释放
        pTemp = NULL;
        return MALLOC_ERROR;   //  返回一个非0值(通常是一个负数),表示本子函数非正常结束,以供主调函数识别和采取对应措施
    }

    *ppList= pTemp; //做好顺序表的表结构和数据区域之后,将该结构(在堆区)交付给实参(一个指针)来指向,从而完成pTemp指针的使命。
                    //ppList是子函数在栈区中的一个指针变量,它指向主调函数中的一个指针变量,所以*ppList就是主调函数中对应的那个指针(即实参)

     return 0;      //一般情况下,在实际工程开发中,基本上都默认函数返回值为0表示该函数运行期间没有异常情况
 }

//根据元素的值x,在顺序表pList中,查找其第一次出现的位置下标,并返回(注意,下标可以为0)。如果没找到,则返回NOTFIND,即-2
int SearchByValue(SeqList *pList, Elemtype Value)
{
    int pos=0;
    //重要的步骤,参数校验!一定别忘了!如果Value有一定的现实含义,则还需要对其做参数有效性校验
    if (pList==NULL)
    {
        return PARAM_ERROR;
    }

    while ( pos<=pList->iCount-1 && pList->pElem[pos]!= Value) //一边比较,一边往后移pos的值,直到找到或者到达有效数据的末尾
                                                               //操作总长范围
        pos++;

    if ( pos <= pList->iCount-1 ) //如果是以“找到”的姿态跳出while循环
        return pos;
    else  
        return NOTFIND;    //如果是以“到末尾”的姿态跳出while循环

}

//功能:根据给定的逻辑位置值pos(假设从1开始),在pList指向的顺序表中提取其元素值,存放到pValue指针指向的空间中并返回给主调函数使用
//备注:pValue的写法,展示了C语言如何通过参数传递,将子函数内的数据传出来,给主调函数使用,注意形参写法和调用时的实参写法!
//      pValue指针,假定其已经指向某个存储空间,本函数不再校验它。问题是:这个空间,应该在主调函数中申请,还是在子函数中申请?一般做法是在主调函数中申请!
int GetValue(SeqList *pList, int pos, Elemtype *pValue) //    ret= GetValue(&List1, 2, pmyValue); 
{
    //重要的步骤,参数校验!一定别忘了!如果Value有一定的现实含义,则还需要对其做参数有效性校验
    if (pList==NULL || pList->pElem==NULL || pos<1 || pos >pList->iCount || pValue==NULL)
    {
        return PARAM_ERROR;
    }

    *pValue= pList->pElem[pos];                    //获得元素值
    return 0;
}

//功能:根据指定的逻辑位置pos值(假设从0开始),在pList指向的顺序表中,第pos个元素后面插入值为Value的元素
//备注:pos的值应>=0,当pos=0时,全体所有数据都需要后移一格;当pos>=iCount时,全体数据都不需要后移
//SeqListInsert(pList1, i, (Elemtype)('H'-i));
int SeqListInsert(SeqList *pList, int pos, Elemtype Value) // 传一个表的地址,直接传一个表,不稳
                                                           //这里排序有两种,第一种是直接传要插入的地址,就是直接知道自己要插入的地址
                                                           //第二种,用数组,结合下标的方式插入
                                                           //要插入的值就是value
{
    Elemtype *pNewBase, *p, *q;

    if (pList==NULL || pList->pElem==NULL || pos <0 )
    {
        return PARAM_ERROR;
    }
    if ( pos > pList->iCount )//pos太大了,大过了icount
        pos = pList->iCount ;

    //如果当前已经装满,则需要扩展存储空间
    if (pList->iCount == pList->iTotalLength)
    {
        pNewBase= (Elemtype *)realloc(pList->pElem, (pList->iTotalLength + LISTINCREMENT)*sizeof(Elemtype));  //请同学们进一步了解realloc的工作原理,当空间字节数较多时,该函数开销较大!
        if (pNewBase== NULL)
        {
            return REALLOC_ERROR;
        }

        pList->pElem= pNewBase;
        pList->iTotalLength= pList->iTotalLength + LISTINCREMENT;
    }

    //主逻辑
    q= &(pList->pElem[pos]); //q 指向的这个元素及其后面所有元素都需要后移一格
    for(p= &(pList->pElem[pList->iCount-1]) ; p>=q; p--)  //从后面往前,循环,每个元素后移一格,直到腾出要插入的内存空间。当pos=0时,全体所有数据都需要后移一格;
                                                          //当pos>=iCount时,全体数据都不需要后移
                                                          //第一个iCOunt=1 表示的是0
        *(p+1)= *p;

    *q= Value;  //实现插入操作
    pList->iCount++;  //元素增加,别忘了让有效长度值iCount加1——随时维护iCount值的准确性,以方便程序员即时读取,而不是在需要的时候才去数个数
    return 0;
}

//合并无序的顺序表  MergeOption:0 不允许重复  1允许重复
int DisorderSeqListMerge(SeqList *pListA, SeqList *pListB, int MergeOption, SeqList **pListC)
{
    int i, ret;

    if (pListA==NULL || pListA->pElem==NULL || pListB==NULL || pListB->pElem==NULL || MergeOption < 0 || MergeOption > 1 )
    {
        return PARAM_ERROR;
    }

    *pListC= (SeqList *)malloc( sizeof(SeqList));
    if (*pListC==NULL)
    {
        return MALLOC_ERROR;
    }

    (*pListC)->iTotalLength= pListA->iTotalLength + pListB->iTotalLength;
    (*pListC)->pElem= (Elemtype *)malloc( (*pListC)->iTotalLength * sizeof(Elemtype));  
    if ((*pListC)->pElem==NULL)
    {
        if ((*pListC) != NULL)
            free(*pListC);
        *pListC= NULL;
        return MALLOC_ERROR;
    }

    //将A表的数据依次复制到C表数据区
    for(i= 0; i<pListA->iCount; i++)
        (*pListC)->pElem[i]= pListA->pElem[i];
    (*pListC)->iCount= pListA->iCount;

    for (i=0; i<pListB->iCount; i++)
    {
        ret = SearchByValue(pListA, pListB->pElem[i]);
        if ( ret >= 0 && MergeOption==0) //现有重复的元素,且不允许重复
        {
            //什么都不做,不执行插入操作
        }
        else  //没找到,没有重复的元素
        {
            SeqListInsert(*pListC, (*pListC)->iCount, pListB->pElem[i]);  //将LB[i]插入到新表LC的末尾
        }
    }

    return 0;
}
 //测试代码,或者主程序代码,在测试InitList函数时,由你自己随意编写;在提交老板后,由项目经理或高级程序员负责编写
int main(void)
{
    int ret, i;
    SeqList List2;              //内存中为List2这个结构体变量分配4+4+4=12个字节
    Elemtype myValue;
    Elemtype *pmyValue= &myValue;
    SeqList *pList1= NULL;    //内存中为pList1这个结构体指针变量分配4个字节         
    SeqList *pList2= NULL;
    //创建演示
    ret= InitList( &pList1 );  //注意,InitList需要的是一个结构体变量的地址,故传&pList1
    if (ret==0)
        printf("创建空的顺序表成功!表的理论总长为%d,每次如果不够,自动增长值为%d", LIST_INIT_SIZE, LISTINCREMENT);
    else
    {
        printf("未能成功分配顺序表的数据存储空间,创建顺序表失败!");
        return 0;
    }

    ret= InitList( &pList2 );  //注意,InitList需要的是一个结构体变量的地址,故传&List2
    if (ret==0)
        printf("创建空的顺序表成功!表的理论总长为%d,每次如果不够,自动增长值为%d", LIST_INIT_SIZE, LISTINCREMENT);
    else
    {
        printf("未能成功分配顺序表的数据存储空间,创建顺序表失败!");
        return 0;
    }


    for (i= 0; i<5; i++)
    {
        SeqListInsert(pList1, i, (Elemtype)('H'-i));
    }
    for (i= 0; i<5; i++)
    {
        SeqListInsert(pList2, i, (Elemtype)('A'+i));//???
    }

    //访问演示
    ret= GetValue(pList1, 2, pmyValue);  //注意在Debug状态下看看*pmyValue的变化,理解数据传递的方向(从子函数给主调函数)
    if (ret==0)
        printf("你要读取表中第%d个元素,其值是%c", 2, *pmyValue); //主调函数使用子函数传出来的数据
    else
        printf("你要读取表中第%d个元素,本表不存在这个元素!", 2);

    //无序表的合并
    DisorderSeqListMerge(pList1, pList2, 1, &pList2);
    return 0;
}

Java代码实现

/*
适用于Java
 */

//定义Person类
class Person
{
    public int id;
    public String name;


    public  Person(int id,String name)
    {
        this.id=id;
        this.name=name;
    }

    public void show()
    {
        System.out.println("学号: "+id+" --- "+"姓名: "+name);
    }

}

//顺序表操作

class SeqList
{                        
    private int currlen;// 线性表现在的长度
    static final int maxsize = 100;//理论最大为100个元素
    private int totalLen;// 线性表的总长度
    Person[] data=new Person[maxsize+1];

    //初始化表
    public void InitList(SeqList arr)
    {
           arr.currlen=0;
    }

    //表的现有长度
    public int ListLen(SeqList arr)
    {
        return (arr.currlen);
    //    System.out.println(arr.currlen);

    }

   //判断表是不是空
   public boolean isEmpty()
    {
       return (currlen==0)?true:false;
    }

    //添加数据
    public int  add(SeqList arr,Person data)
    {
         if(arr.currlen>maxsize){
            System.out.println("顺序表已满,不能插入节点");
            return 0;
        }
        arr.data[arr.currlen++]=data;
        return 1;
    }

   //查找元素的值(根据下标)
   public void SearchByIndex(SeqList arr,int n)
    {
         if( n<0 || n>arr.currlen)
        {
             System.out.println("呀!出错啦!检查一下!");
        }

       else
        {
           System.out.println(arr.data[n-1].id+"---"+arr.data[n-1].name);
        }

    }

    //查找元素的下标(根据元素的值)
    public int SearchByValue(SeqList arr,Person data) 
    {
         int pos=0;


        while (pos<=arr.currlen-1 && arr.data[pos]!=data)
        {
            pos++;
        }

        if(pos <= arr.currlen-1)
        {
            return pos;
        }
        else 
        {
            System.out.println("没有找到这个下标呀!");
        }
        return 1;
    }

    //插入数据
    public int insert(SeqList arr,int pos, Person d)
    {
        int i;
        if(pos<0)
        {
            return -1;
        }

        if(pos > arr.currlen)
            pos = arr.currlen;

        //装满的情况
        if(arr.currlen >= maxsize)
        {
            System.out.println("顺序表装满了,不能插入啦!");
        }

        //将顺序表数据往后移
        for (i = arr.currlen;i>=pos ;i-- )
        {
            arr.data[i+1] = arr.data[i];
        }

        arr.data[pos]=d;
        arr.currlen++;// 元素增加!!!
        return 1;


    }

    //删除数据

    public int delete(SeqList arr,int n)
    {
        int i;
        if(n<=0 || n>=arr.currlen)
        {
            System.out.println("输入出错啦,不能删除!");
            return 0;
        }

        for (i=n;i<arr.currlen ;i++ )
        {
            arr.data[i]=arr.data[i+1];
        }
        arr.currlen--;
        return 1;

    }
    //显示所有数据
    public int showData(SeqList arr)
    {
         int i;
         for (i=0;i<=arr.currlen-1; i++)
         {
             System.out.println(arr.data[i].id+"---"+arr.data[i].name);
         }
         return 0;
       }
 }

class  SeqlistTest
{
      public static void main(String[] args) 
    {

        //开始测试
        System.out.println("-----------------");
        System.out.println("以下是测试");

        SeqList arr= new SeqList();

        //初始化
        System.out.println("---------初始化测试--------");
        arr.InitList(arr);
        System.out.println("初始化完成");
        System.out.println();


        //查看初始化是否完成
        System.out.println("---------确认初始化是否完成--------");
       int i =  arr.ListLen(arr);


     // 添加数据
     System.out.println();
     System.out.println("--------添加数据:张三和李四等5人---------");
        Person data1=new Person(1,"张三");
        Person data2=new Person(2,"李四");
        Person data3=new Person(3,"王五");
        Person data4=new Person(4,"唐僧");
        Person data5=new Person(5,"孙悟空");
        Person data6=new Person(6,"李倩");

        arr.add(arr,data1);
        arr.add(arr,data2);
        arr.add(arr,data3);
        arr.add(arr,data4);
        arr.add(arr,data5);


        //显示数据
        System.out.println();
        System.out.println("--------测试显示数据---------");
        arr.showData(arr);


        //判断表是不是空
        System.out.println();
        System.out.println("--------判断表是否为空---------");
        boolean m = arr.isEmpty();
        System.out.println(m);


         //查找元素的值(根据下标)
         System.out.println();
         System.out.println("--------查找元素的值(根据下标),查找1---------");
         arr.SearchByIndex(arr,1);



        //查找元素的下标(根据元素的值)
        System.out.println();
        System.out.println("---------查找元素的下标(根据值):查找李四--------");
        int index = arr.SearchByValue(arr,data2) ; //m是接收哪个下标
        arr.SearchByIndex(arr,index+1);



        //插入数据
        System.out.println();
        System.out.println("-------测试插入数据,在arr[1]那里插入李倩----------");
    int res1 = arr.insert(arr,1, data6);
    arr.showData(arr);//看一下现在表什么样子


        //删除数据
        System.out.println();
      System.out.println("-------测试删除数据:删除李倩----------");
        arr.delete(arr,1);
        arr.showData(arr);

        //表的现有长度
        System.out.println();
    System.out.println("--------测试表现在有的长度---------");
    int len = arr.ListLen(arr);
    System.out.println(len);
    }
}