数据结构-线性表-顺序表

53 阅读 0 评论 35 点赞

我是靠谱客的博主标致小虾米，最近开发中收集的这篇文章主要介绍数据结构-线性表-顺序表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

线性表-顺序表//附有详细注释
完整代码在最后。

常量，用于表示函数返回的状态等

#define OVERFLOW -2
#define OK 1
#define ERROR 0

数据类型说明

//数据类型说明
typedef int ElemType;
//为int类型创建两个新的名字：元素类型和状态
typedef int Status;
#define List_init_size 100
//储存空间最大值
#define Listincrement 10
//线性表存储空间初始分配量
typedef struct {
ElemType *elem;
//存储空间基址
int length;
//当前长度
int listsize;
//当前分配的存储容量
// (以sizeof(ElemType)为单位)
}sqlist;

初始化线性表

//初始化线性表：
Status lnitList(sqlist &L)
//Status即int类型，用以表示函数返回一种状态：OK 或者 ERROR 或者OVERFLOW
{
//构造一个空线性表L
L.elem=(ElemType *) malloc (List_init_size* sizeof (ElemType)); //ElemType，int的别名
// malloc 函数的功能是为一个对象在堆中分配一个sizeof (ElemType)大小的内存空间,并且返回一个指向这块内存的指针
if (!L.elem) exit (OVERFLOW);
L.length=0;
L.listsize= List_init_size;
//储存容量为100
return OK;
}

构建线性表的基本操作

//在一个线性表中输入N个数据：
Status sqlistinput(sqlist &L, int n)
{
if (n>L.listsize) return ERROR;
for (int i=0; i<n; i++)
scanf("%d", &L.elem[i]);
L.length=n;
return OK;
}
//判线性表是否为空
Status ListEmpty(sqlist L)
{
if (!L.length) return ERROR;
else return OK;
}
//求线性表的长度
Status ListLength(sqlist L)
{
return L.length;
}
//将线性表L的数据输出：
Status sqlistoutput(sqlist L)
{
for (int i=0; i<ListLength(L); i++) printf ("%d
", L.elem[i]);
printf ("n");
return OK;
}
//取线性表的第i个元素，将结果保存在e中
Status GetElem(sqlist l, int i, ElemType &e)
{
if (i<1 || i>l.length+1)
return ERROR;
e=l.elem[i-1];
//数组元素下表从0开始，第i个元素在数组中的下标为i-1
return OK;
}

顺序表实验中拓展的线性表操作

//两个数据元素是否相等的比较函数
Status equal(ElemType e1, ElemType e2)
{
if (e1==e2)
return OK;
else
return ERROR;
}
//根据compare函数在线性表中定位元素e的位置
int LocateElem_sq(sqlist L, ElemType e, Status (*compare)(ElemType,ElemType))	//成功返回位序,否则返回0
{
int i=1;
ElemType *p;
//定义指针用以遍历线性表
p=L.elem;
//线性表储存空间基址
while (i<=L.length && !(*compare) (*p++, e))
++i;
//找到e或者遍历完线性表停止循环，i记录位置
if (i<=L.length)
return i;
else
return 0;
}

在线性表中求某个元素的前一个元素和后一个元素

//在线性表中求某元素的前趋结点，如存在则返回其前趋结点pre_e的值，否则返回出错信息
Status PriorElem(sqlist L, ElemType cur_e, ElemType &pre_e)
{
int pos;
pos=LocateElem_sq(L, cur_e, equal);
//pos表示某元素的位置
if (pos==0)
return ERROR;
else if (pos==1)
return OVERFLOW; //overflow 表示位于第一个
else
{
GetElem(L,pos-1,pre_e);
//pos-1表示前驱结点的位置
return OK;
}
}
//在线性表中求某元素的后继结点
Status NextElem(sqlist L, ElemType cur_e, ElemType &next_e)
{
int pos;
pos=LocateElem_sq(L, cur_e, equal);
if (pos==0)
return ERROR;
else if (pos==L.length)
return OVERFLOW;
//overflow 表示最后一个
else
{
GetElem(L,pos+1,next_e);
return OK;
}
}

线性表的插入和删除操作

//在线性表中插入一个元素
Status Listinsert_sq(sqlist &L, int i, ElemType e)
{
ElemType *p,*q,*newbase;
if (i<1 || i>L.length+1)
return ERROR;
if (L.length>=L.listsize)
{
newbase=(ElemType *) realloc (L.elem, (L.listsize+Listincrement) * sizeof (ElemType));
//realloc更改已经配置的内存空间，即更改由malloc()函数分配的内存空间的大小。
if (!newbase) exit (OVERFLOW);
L.elem=newbase;
L.listsize+=Listincrement;
}
q=&(L.elem[i-1]);
//此时的&为取地址运算符，当前指针q指向线性表的第i个元素
for (p=&(L.elem[L.length-1]); p>=q; --p)
//p指向最后一个元素
{
*(p+1)=*p;
//此时*为取值运算符，元素后移一位
}
*q=e;
//将e赋值给第i个元素
++L.length;
//插入一个元素后线性表长度加一
return OK;
}
//在线性表中删除第i个元素，其结果保留在e中
Status Listdelete_sq(sqlist &l, int i, ElemType &e)
//删除和插入原理基本相同
{
ElemType *p,*q;
if (i<1 || i>l.length)
return ERROR;
p=&(l.elem[i-1]);
e=*p;
q=&(l.elem[l.length-1]);
for (++p; p<=q; ++p)
{
*(p-1)=*p;
}
--l.length;
return OK;
}

主函数用于测试线性表顺序表

int main()
{
sqlist la;
//生成对象即线性表la
int m,n,i,e,k,cur_e,pre_e,next_e;
//建立线性表，并输入线性表的数据
lnitList(la);
printf ("请输入线性表 la 的元素个数 n n");
scanf ("%d", &n);
if(n>0 && n<=List_init_size)
{
printf ("请输入线性表 la 的 n 个元素n");
sqlistinput(la,n);
sqlistoutput(la);
printf ("n");
}
else
{
printf ("建立线性表失败，线性表长度最大为%d n",List_init_size);
system("pause");
system("cls");
return 0;
}

测试插入删除操作（测试应放在主函数中，下面不在赘述）

//调用插入函数，对线性表进行插入操作
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入插入的元素的位置和插入的值 n");
scanf ("%d%d", &i, &e);
//i代表位置，e代表数值
m=Listinsert_sq(la, i, e);
if(m!=1) printf ("插入失败n");
else sqlistoutput(la);
system("pause");
system("cls");
//调用删除函数，对线性表进除删操作
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入要删除的元素的位置n");
scanf ("%d", &i);
m=Listdelete_sq(la, i, e);
if(m!=1) printf ("删除失败n");
else
{
printf ("删除的数据是%d n", e);
sqlistoutput(la);
}
system("pause");
system("cls");

测试元素的位置

//调用GetElem()函数，取第i个位置的元素的值。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入要获得哪个位置的元素n");
scanf ("%d", &i);
m=GetElem(la, i, e);
if(m!=1) printf ("查找失败n");
else printf ("线性表中第 %d 位查找到的数据是 %d n", i, e);
system("pause");
system("cls");
//调用LocateElem_sq函数，求元素cur_e的位置。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入要获得哪个元素的位置n");
scanf ("%d", &cur_e);
k=LocateElem_sq(la, cur_e, equal);
if(k==0) printf ("查找失败n");
else printf (" %d 在线性表中的位置是 %d n", cur_e, k);
system("pause");
system("cls");

求元素的前驱和后继


//调用PriorElemQ函数 求元素cur_e的前驱。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("求元素的前驱，请输入数据n");
scanf ("%d", &cur_e);
m=PriorElem(la, cur_e, pre_e);
if(m!=1) printf ("查找失败n");
else printf (" %d 元素的前驱是 %d n", cur_e, pre_e);
system("pause");
system("cls");
//调用NextElem()函数，求元素cur_e的后继。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("求元素的后继，请输入数据n");
scanf ("%d", &cur_e);
m=NextElem(la, cur_e, next_e);
if(m!=1) printf ("查找失败n");
else printf (" %d 元素的后继是 %d n",cur_e, next_e);
}

最后，如果觉得这篇博客能帮助到你，请点个小小的赞支持一下我（收藏也行呀，嘻嘻），这是我继续更新的动力呀，关注我可以得到第一时间的更新，更加快人一步哦。
如果有问题请在评论区留言，一起交流进步。
附完整代码：

#include "stdio.h"
#include "stdlib.h"
#define OVERFLOW -2
#define OK 1
#define ERROR 0
//数据类型说明
typedef int ElemType;
//为int类型创建两个新的名字：元素类型和状态
typedef int Status;
#define List_init_size 100
//储存空间最大值
#define Listincrement 10
//线性表存储空间初始分配量
typedef struct {
ElemType *elem;
//存储空间基址
int length;
//当前长度
int listsize;
//当前分配的存储容量
// (以sizeof(ElemType)为单位)
}sqlist;
//直接定义结构体变量sqlist
//初始化线性表：
Status lnitList(sqlist &L)
//Status即int类型，用以表示函数返回一种状态：OK 或者 ERROR 或者OVERFLOW
{
//构造一个空线性表L
L.elem=(ElemType *) malloc (List_init_size* sizeof (ElemType)); //ElemType，int的别名
// malloc 函数的功能是为一个对象在堆中分配一个sizeof (ElemType)大小的内存空间,并且返回一个指向这块内存的指针
if (!L.elem) exit (OVERFLOW);
L.length=0;
L.listsize= List_init_size;
//储存容量为100
return OK;
}
//在一个线性表中输入N个数据：
Status sqlistinput(sqlist &L, int n)
{
if (n>L.listsize) return ERROR;
for (int i=0; i<n; i++)
scanf("%d", &L.elem[i]);
L.length=n;
return OK;
}
//判线性表是否为空
Status ListEmpty(sqlist L)
{
if (!L.length) return ERROR;
else return OK;
}
//求线性表的长度
Status ListLength(sqlist L)
{
return L.length;
}
//将线性表L的数据输出：
Status sqlistoutput(sqlist L)
{
for (int i=0; i<ListLength(L); i++) printf ("%d
", L.elem[i]);
printf ("n");
return OK;
}
//取线性表的第i个元素，将结果保存在e中
Status GetElem(sqlist l, int i, ElemType &e)
{
if (i<1 || i>l.length+1)
return ERROR;
e=l.elem[i-1];
//数组元素下表从0开始，第i个元素在数组中的下标为i-1
return OK;
}
//两个数据元素是否相等的比较函数
Status equal(ElemType e1, ElemType e2)
{
if (e1==e2)
return OK;
else
return ERROR;
}
//根据compare函数在线性表中定位元素e的位置
int LocateElem_sq(sqlist L, ElemType e, Status (*compare)(ElemType,ElemType))	//成功返回位序,否则返回0
{
int i=1;
ElemType *p;
//定义指针用以遍历线性表
p=L.elem;
//线性表储存空间基址
while (i<=L.length && !(*compare) (*p++, e))
++i;
//找到e或者遍历完线性表停止循环，i记录位置
if (i<=L.length)
return i;
else
return 0;
}
//在线性表中求某元素的前趋结点，如存在则返回其前趋结点pre_e的值，否则返回出错信息
Status PriorElem(sqlist L, ElemType cur_e, ElemType &pre_e)
{
int pos;
pos=LocateElem_sq(L, cur_e, equal);
//pos表示某元素的位置
if (pos==0)
return ERROR;
else if (pos==1)
return OVERFLOW; //overflow 表示位于第一个
else
{
GetElem(L,pos-1,pre_e);
//pos-1表示前驱结点的位置
return OK;
}
}
//在线性表中求某元素的后继结点
Status NextElem(sqlist L, ElemType cur_e, ElemType &next_e)
{
int pos;
pos=LocateElem_sq(L, cur_e, equal);
if (pos==0)
return ERROR;
else if (pos==L.length)
return OVERFLOW;
//overflow 表示最后一个
else
{
GetElem(L,pos+1,next_e);
return OK;
}
}
//在线性表中插入一个元素
Status Listinsert_sq(sqlist &L, int i, ElemType e)
{
ElemType *p,*q,*newbase;
if (i<1 || i>L.length+1)
return ERROR;
if (L.length>=L.listsize)
{
newbase=(ElemType *) realloc (L.elem, (L.listsize+Listincrement) * sizeof (ElemType));
//realloc更改已经配置的内存空间，即更改由malloc()函数分配的内存空间的大小。
if (!newbase) exit (OVERFLOW);
L.elem=newbase;
L.listsize+=Listincrement;
}
q=&(L.elem[i-1]);
//此时的&为取地址运算符，当前指针q指向线性表的第i个元素
for (p=&(L.elem[L.length-1]); p>=q; --p)
//p指向最后一个元素
{
*(p+1)=*p;
//此时*为取值运算符，元素后移一位
}
*q=e;
//将e赋值给第i个元素
++L.length;
//插入一个元素后线性表长度加一
return OK;
}
//在线性表中删除第i个元素，其结果保留在e中
Status Listdelete_sq(sqlist &l, int i, ElemType &e)
//删除和插入原理基本相同
{
ElemType *p,*q;
if (i<1 || i>l.length)
return ERROR;
p=&(l.elem[i-1]);
e=*p;
q=&(l.elem[l.length-1]);
for (++p; p<=q; ++p)
{
*(p-1)=*p;
}
--l.length;
return OK;
}
int main()
{
sqlist la;
//生成对象即线性表la
int m,n,i,e,k,cur_e,pre_e,next_e;
//建立线性表，并输入线性表的数据
lnitList(la);
printf ("请输入线性表 la 的元素个数 n n");
scanf ("%d", &n);
if(n>0 && n<=List_init_size)
{
printf ("请输入线性表 la 的 n 个元素n");
sqlistinput(la,n);
sqlistoutput(la);
printf ("n");
}
else
{
printf ("建立线性表失败，线性表长度最大为%d n",List_init_size);
return 0;
}
system("pause");
system("cls");
//调用插入函数，对线性表进行插入操作
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入插入的元素的位置和插入的值 n");
scanf ("%d%d", &i, &e);
//i代表位置，e代表数值
m=Listinsert_sq(la, i, e);
if(m!=1) printf ("插入失败n");
else sqlistoutput(la);
system("pause");
system("cls");
//调用删除函数，对线性表进除删操作
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入要删除的元素的位置n");
scanf ("%d", &i);
m=Listdelete_sq(la, i, e);
if(m!=1) printf ("删除失败n");
else
{
printf ("删除的数据是%d n", e);
sqlistoutput(la);
}
system("pause");
system("cls");
//调用GetElem()函数，取第i个位置的元素的值。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入要获得哪个位置的元素n");
scanf ("%d", &i);
m=GetElem(la, i, e);
if(m!=1) printf ("查找失败n");
else printf ("线性表中第 %d 位查找到的数据是 %d n", i, e);
system("pause");
system("cls");
//调用LocateElem_sq函数，求元素cur_e的位置。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入要获得哪个元素的位置n");
scanf ("%d", &cur_e);
k=LocateElem_sq(la, cur_e, equal);
if(k==0) printf ("查找失败n");
else printf (" %d 在线性表中的位置是 %d n", cur_e, k);
system("pause");
system("cls");
//调用PriorElemQ函数 求元素cur_e的前驱。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("求元素的前驱，请输入数据n");
scanf ("%d", &cur_e);
m=PriorElem(la, cur_e, pre_e);
if(m!=1) printf ("查找失败n");
else printf (" %d 元素的前驱是 %d n", cur_e, pre_e);
system("pause");
system("cls");
//调用NextElem()函数，求元素cur_e的后继。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("求元素的后继，请输入数据n");
scanf ("%d", &cur_e);
m=NextElem(la, cur_e, next_e);
if(m!=1) printf ("查找失败n");
else printf (" %d 元素的后继是 %d n",cur_e, next_e);
return 0;
}