数据结构与算法：1线性表的顺序存储

线性表表示的是包含相同类型数据元素的一个线性序列，比如咱们常见的数组。

顺序存储表示的是使用一整块连续的内存空间使用静态分配和动态分配都可以。

线性表的顺序存储是整个数据结构中第一个要学习的数据结构，同样也是最简单的数据结构。

线性表的孙处存储的函数有：

（1）初始化线性表。

（2）销毁线性表。

（3）清除线性表的内容。

（4）获取线性表的长度。

（5）判断线性表是否为空。

（6）获取线性表对应索引号的值。

（7）判断线性表是否存在此数据值，如果存在返回在线性表中的索引号。

（8）判断数据是否是线性表的头数据，如果不是返回前驱节点的值。

（9）判断数据是否是线性表的尾数据，如果不是返回后驱节点的值。

（10）在线性表的指定位置添加数据。

（11）在线性表的制定位置删除数据。

（12）输出线性表的所有数据。

这里我们为了简单规定的是整型数据的线性顺序存储结构使用的动态内存分配：

（1）初始化线性表。

List * ListInit(List * list);

返回分配的地址空间，如果分配失败返回null。

（2）销毁线性表。

List * ListDestroy(List *list);

释放分配的空间，如果成功返回null

（3）清除线性表的内容。

int ListClear(List *list);

设置当前线性表的长度的为0

（4）获取线性表的长度。

int ListLength(plist list);

返回线性表的长度。

（5）判断线性表是否为空。

int ListEmpty(plist list);

判断线性表的长度是否为0，对于为空返回-1，不为空返回0

（6）获取线性表对应索引号的值。

int GetElem(plist list,int index);

获取线性表对应位置的数值，对于错误的索引值返回-1.

（7）判断线性表是否存在此数据值，如果存在返回在线性表中的索引号。

int LocateElem(plist list,int data);

判断线性表中是否存在此数值，存在此数值返回在线性表中的索引值。不在线性表中返回-1。

（8）判断数据是否是线性表的头数据，如果不是返回前驱节点的值。

int PreElem(plist list,int data);

判断数值是否是线性表的头节点数据，如果是返回0，反之返回此数值前一个节点的数值，如果此数据不存在于线性表中返回-1.

（9）判断数据是否是线性表的尾数据，如果不是返回后驱节点的值。

判断数值是否是线性表的头节点数据，如果是返回0，反之返回此数值后一个节点的数值，如果此数据不存在于线性表中返回-1.

int SuccElem(plist list,int data);

（10）在线性表的指定位置添加数据。

int ListInsert(plist list,int index,int data);

在线性表中的指定位置插入数据，对于错误的索引值返回-1，反之返回0.

（11）在线性表的制定位置删除数据。

int ListDel(plist list,int index);

删除线性表中执行位置的数值，对于错误的索引值返回-1，反之返回0.

（12）输出线性表的所有数据。

void ListDisplay(plist list);

输出指定线性表中的数据。

源程序：

list.h

#ifndef _LIST_H
#define _LIST_H
#define MAX 256
#define LIST_ERR -1
#define LIST_OK 0
typedef struct{
 int data[MAX];
 int last;
 int size;
}List,*plist;
/**初始化线性表*/
List * ListInit(List * list);
/**销毁线性表*/
List * ListDestroy(List *list);
/**设置线性表为空*/
int ListClear(List *list);
/**获取线性表的长度*/
int ListLength(plist list);
/**判断线性表是否为空*/
int ListEmpty(plist list);
/**获取线性表的对应位置的值*/
int GetElem(plist list,int index);
/**获取此线性表中是否存在此数据，存在返回此数据在线性表中的位置*/
int LocateElem(plist list,int data);
/**判断此数据是线性表中若不是线性表首数据返回前驱值，如果是返回空*/
int PreElem(plist list,int data);
/**判断此数据是线性表中若不是线性表尾数据返回后继值，如果是返回空*/
int SuccElem(plist list,int data);
/**在线性表的指定位置插入数据*/
int ListInsert(plist list,int index,int data);
/**在线性表的制定位置删除数据*/
int ListDel(plist list,int index);
/**输出线性表的数据*/
void ListDisplay(plist list);
#endif

list.c

#include 
#include "list.h"
List * ListInit(List * list)
{
 if(list)
 {
 printf("这个地址已经存在\n");
 }
 else
 {
 printf("开始分配地址\n");
 if(NULL==(list=(List*)malloc(sizeof(List))))
 {
 printf("分配地址空间失败\n");
 }
 printf("List 数据结构的大小%d\n",sizeof(List));
 printf("分配的地址为%u\n",list);
 list->last=0;
 list->size=MAX;
 }
 return list;
}
List * ListDestroy(List * list)
{
 if(list)
 {
 free(list);
 list=NULL;
 
 }
 return list;
 
}
int ListClear(List *list)
{
 if(list)
 {
 list->last=0;
 return LIST_OK;
 }
 else
 {
 return LIST_ERR;
 }
 
}
int ListLength(plist list)
{
 if(list)
 {
 return list->last;
 }
 else
 {
 return LIST_ERR;
 }
 
}
int ListEmpty(plist list)
{
 if(list)
 {
 return list->last;
 }
 else
 {
 return LIST_ERR;
 }
 
}
int GetElem(plist list,int index)
{
 if(list)
 {
 if(index>list->last-1||index<0)
 {
 return LIST_ERR;
 }
 else
 {
 return list->data[index];
 }
 }
 return LIST_ERR;
}
int LocateElem(plist list,int data)
{
 if(list)
 {
 int i=0;
 for(i=0;ilast;i++)
 {
 if(list->data[i]==data)
 {
 break;
 }
 }
 if(i==list->last)
 {
 return LIST_ERR;
 }
 else
 {
 return i;
 }
 }
 else
 {
 return LIST_ERR;
 }
 
}
int PreElem(plist list,int data)
{
 int index=LocateElem(list,data);
 if(index==LIST_ERR)
 {
 return index;
 }
 if(index>0)
 {
 return list->data[index-1];
 }
 else
 {
 return LIST_OK;
 }
 
}
int SuccElem(plist list,int data)
{
 int index=LocateElem(list,data);
 if(index==LIST_ERR)
 {
 return index;
 }
 if((list->last-1)>index)
 {
 return list->data[index+1];
 }
 else
 {
 return LIST_OK;
 }
}
int ListInsert(plist list,int index,int data)
{
 if(list->size>index)
 {
 if(list->last>=index&&index>=0)
 {
 int i;
 for(i=list->last;idata[i+1]=list->data[i];
 }
 list->data[i]=data;
 list->last++;
 return LIST_OK;
 }
 else
 {
 return LIST_ERR;
 }
 }
 else
 {
 return LIST_ERR;
 }
 
 
}
int ListDel(plist list,int index)
{
 if(0==list->last)
 {
 return LIST_ERR;
 }
 else
 {
 if(index>list->last||index<0)
 {
 return LIST_ERR;
 }
 else
 {
 int i=0;
 for(i=index;ilast-1;i++)
 {
 list->data[i]=list->data[i+1];
 }
 list->last--;
 return LIST_OK;
 }
 }
}
void ListDisplay(plist list)
{
 if(list)
 {
 int i;
 for(i=0;ilast;i++)
 {
 printf("The %d is %d\n",i,list->data[i]);
 }
 }
}

main.c

#include 
#include "list.h"
int main(void)
{
 List * list=NULL;
 int status=-1;
 list=ListInit(list);
 if(!list)
 {
 printf("初始化失败\n");
 }
 else
 {
 printf("初始化成功\n");
 printf("list的内存地址为 %u\n",list);
 }
 status=ListInsert(list,0,45);
 status=ListInsert(list,1,55);
 status=ListInsert(list,2,66);
 status=ListInsert(list,3,77);
 status=ListInsert(list,4,88);
 if(!status)
 {
 printf("插入数据成功\n");
 }
 else
 {
 printf("插入数据失败\n");
 }
 ListDisplay(list);
 status=LocateElem(list,77);
 printf("The 77 is at %d\n",status);
 status=LocateElem(list,100);
 printf("The 100 is at %d\n",status);
 status=GetElem(list,2);
 printf("链表的第3个数据为%d\n",status);
 status=GetElem(list,8);
 printf("链表的第9个数据为%d\n",status);
 status=ListDel(list,-1);
 printf("链表的第-1个数据为%d\n",status);
 status=ListDel(list,0);
 if(!status)
 {
 printf("删除数据成功\n");
 }
 else
 {
 printf("删除数据失败\n");
 }
 status=PreElem(list,88);
 printf("数据88的前一个数据是%d\n",status);
 status=PreElem(list,45);
 printf("数据45的前一个数据是%d\n",status);
 status=SuccElem(list,88);
 printf("数据88的后一个数据是%d\n",status);
 status=SuccElem(list,45);
 printf("数据45的后一个数据是%d\n",status);
 status=ListEmpty(list);
 printf("链表是否为空的状态%d\n",status);
 ListDisplay(list);
 status=ListLength(list);
 printf("线性表的长度为%d\n",status);
 ListClear(list);
 status=ListLength(list);
 printf("线性表的长度为%d\n",status);
 list=ListDestroy(list);
 if(list)
 {
 printf("释放失败\n");
 printf("失败状态值为%d\n",status);
 }
 else
 {
 printf("释放成功\n");
 }
 return 0;
}

在程序上存在一些不严谨和通用性上的问题，但是大家应该在观看源程序的基础上看到了线性顺序存储的一些问题：比如删除和添加节点时比较费力可能需要移动整个线性表中的元素。但是他的优点是简单易操作容易实现。下一节我们将实现顺序表的链式存储解决线性表的顺序存储的问题。