线性表简介：
线性表是一种基本的数据结构，它是由n个相同类型的数据元素组成的有序序列。线性表的每个数据元素称为元素或节点，每个元素可以有一个或多个数据项组成。线性表元素之间的关系是一对一的线性关系，即除了第一个元素和最后一个元素之外，每个元素都有唯一的前驱和后继。
线性表常见的操作包括：初始化表、销毁表、插入元素、删除元素、查找元素、判断表空、遍历表等。
本帖子主要介绍线性表的顺序存储结构，以下称为顺序表。
首先声明一些常用的数据类型的定义：
#define MAXSIZE 50
typedef int ElemType;顺序表的定义：
typedef struct{
ElemType data[MAXSIZE];
int size;
}SqList;顺序表的初始化：
仅需进行内存的分配即可，并将元素数量初始化为0，实现代码：
bool InitList(pSqList *L)
{
(*L) = (SqList *)malloc(sizeof(SqList)); // 为顺序表分配内存
if((*L) == NULL) // 判断是否分配内存成功
{
printf("InitList: Error_malloc\n");
return false;
}
(*L)->size = 0; // 初始化顺序表的长度
return true;
}顺序表的创建：
创建的时候可以传递数组，来实现对于顺序表的创建，遍历传递的数组时，注意不要数组越界，实现代码：
void CreateList(pSqList *L, ElemType arr[])
{
int i = 0;
while(arr[i] != 0xFEFEFEFE) // 判断是否需要结束遍历
{
(*L)->data[i] = arr[i];
++i;
}
(*L)->size = i;
return;
}获取顺序表中元素的数量：
通过顺序表结构中的size成员来获取顺序表中的元素数量，实现代码：
int Size(pSqList *L)
{
return (*L)->size;
}判断顺序表是否为空：
在顺序表结构中，如果size成员的值是0，则说明顺序表中没有成员，则说明顺序表为空，实现代码：
bool Empty(pSqList *L)
{
if((*L)->size == 0)
return true;
return false;
}获取顺序表中的第i个元素的值：
设计时，要注意第i个元素是否存在，不存在就返回false，存在就返回true，如果存在，需要返回数据元素，可以将一个变量作为缓冲，函数设置一个指针作为返回第i个元素的媒介。实现代码如下：
bool GetElem(pSqList *L, ElemType *e, int i)
{
if(i > (*L)->size || i < 1)
{
e = NULL;
return false;
}
*e = (*L)->data[i - 1];
return true;
}查找某个值是否存在：
查找值时，需要遍历顺序表的数据域，不存在就返回0或者是-1等非正值，存在就返回查找的值时第几个数据元素，或者是返回true等具有判断型的标志，根据需求修改即可。设计思路如下（以返回元素的位置为基础）：
int SearchElem(pSqList *L, ElemType *e)
{
int i;
for(i = 0; i < (*L)->size; ++i)
{
if((*L)->data[i] == *e)
{
return (i + 1);
}
}
return -1;
}在一个指定位置插入一个元素
在插入时，需要进行位置的检测，位置不正确返回false，如果位置正确，则先进行是否满元素判断，如果元素已满，则返回false,表示插入失败，如果位置正确且有空位来进行存储，则先进行元素位置的移动，在将元素插入指定位置。实现代码：
bool Insert(pSqList *L, ElemType *e, int pos)
{
if(pos < 1 || pos > MAXSIZE || (*L)->size == MAXSIZE)
return false;
int i;
for(i = (*L)->size; i > pos - 1; --i)
{
(*L)->data[i] = (*L)->data[i - 1];
}
(*L)->data[pos - 1] = *e;
++(*L)->size;
return true;
}删除一个指定位置的元素：
首先对删除的位置进行位置检查，看是否存在越界，不存在越界，假设我们要删除第i个元素（i是一个合法的位置），我们可以直接将第i+1个位置的元素覆盖掉第i个位置的元素，依次将后边的元素前移一个即可。实现代码如下：
bool Delete(pSqList *L, int pos, ElemType *e)
{
if(pos < 1 || pos > (*L)->size)
return false;
int i;
if(e != NULL)
*e = (*L)->data[pos - 1];
for(i = pos - 1; i < (*L)->size; ++i)
{
(*L)->data[i] = (*L)->data[i + 1];
}
--(*L)->size;
return true;
}展示全部元素：
在打印所有元素时需要注意不要数组越界，实现代码如下：
void Display(pSqList *L)
{
int i;
for(i = 0; i < (*L)->size; ++i)
{
printf("%d ", (*L)->data[i]);
}
return;
}总代码如下：
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <malloc.h>
#define MAXSIZE 50
typedef int ElemType;
typedef struct{
ElemType data[MAXSIZE];
int size;
}SqList, *pSqList;
void CreateList(pSqList *L, ElemType arr[])
{
int i = 0;
while(arr[i] != 0xFEFEFEFE) // 判断是否需要结束遍历
{
(*L)->data[i] = arr[i];
++i;
}
(*L)->size = i;
return;
}
bool InitList(pSqList *L)
{
(*L) = (SqList *)malloc(sizeof(SqList)); // 为顺序表分配内存
if((*L) == NULL) // 判断是否分配内存成功
{
printf("InitList: Error_malloc\n");
return false;
}
(*L)->size = 0; // 初始化顺序表的长度
return true;
}
bool Empty(pSqList *L)
{
if((*L)->size == 0)
return true;
return false;
}
int Size(pSqList *L)
{
return (*L)->size;
}
bool GetElem(pSqList *L, ElemType *e, int i)
{
if(i > (*L)->size || i < 1)
{
e = NULL;
return false;
}
*e = (*L)->data[i - 1];
return true;
}
int SearchElem(pSqList *L, ElemType *e)
{
int i;
for(i = 0; i < (*L)->size; ++i)
{
if((*L)->data[i] == *e)
{
return (i + 1);
}
}
return -1;
}
bool Insert(pSqList *L, ElemType *e, int pos)
{
if(pos < 1 || pos > MAXSIZE || (*L)->size == MAXSIZE)
return false;
int i;
for(i = (*L)->size; i > pos - 1; --i)
{
(*L)->data[i] = (*L)->data[i - 1];
}
(*L)->data[pos - 1] = *e;
++(*L)->size;
return true;
}
bool Delete(pSqList *L, int pos, ElemType *e)
{
if(pos < 1 || pos > (*L)->size)
return false;
int i;
if(e != NULL)
*e = (*L)->data[pos - 1];
for(i = pos - 1; i < (*L)->size; ++i)
{
(*L)->data[i] = (*L)->data[i + 1];
}
--(*L)->size;
return true;
}
void Display(pSqList *L)
{
int i;
for(i = 0; i < (*L)->size; ++i)
{
printf("%d ", (*L)->data[i]);
}
return;
}
int main()
{
int arr[10];
memset(arr, -2, sizeof(arr)); // 初始化数组
return 0;
}
没有回复内容