一息若存，希望不灭。
顺序表的分类
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);
}
}