2.4.1 线性表的顺序存储表示
//定义顺序表
typedef struct
{
Elempty *elem;//存储空间的基地址
int length;//当前长度
}*SqList,LNode;//顺序表的结构类型
2.4.2 顺序表中基本操作的实现
可以看出， 当线性表以上述定义的顺序表表示时，某些操作很容易实现。 因为表的长度是顺序表的一个 “属性”，所以可以通过返回length的值实现求表长的操作， 通过判断length的值是否为0 判断表是否为空，这些操作算法的时间复杂度都是O(1)。下面讨论顺序表其他几个主要操作的实现。
算法2.1 顺序表的初始化
顺序表的初始化操作就是构造一个空的顺序表。
【算法步骤】
①为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。
②将表的当前长度设为0。
【算法描述】
Status InitList(SqList &L)
{
L = new LNode;//新建一个结点
L->elem= new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
if (! L->elem) return ERROR; //存储分配返回ERROR
L->length=O; //空表长度为0
return OK;
}
算法2.2 顺序表的取值
【算法步骤】
①判断指定的位置序号 i 值是否合理 (1
Status GetElem(SqList L, int i, ElemType& e)
{
if (iL->length)
{
printf("查找位置非法，查找错误\n");
return ERROR;
}
else
{
e = L->elem[i - 1];
printf("%d\n", e);
return OK;
}
}
顺序表基本操作详细代码
#include
#define OK 1
#define ERROR 0
using namespace std;
typedef int ElemType;
typedef int Status;
#define MAXSIZE 100
/*定义顺序表*/
typedef struct {
ElemType *elem;
int length;
}*SqList,LNode;
/*初始化顺序表*/
Status InitList(SqList& L)
{
L = new LNode;
L->elem = new ElemType[MAXSIZE];
if (!L->elem)
{
printf("初始化失败！\n");
return ERROR;
}
L->length = 0;
printf("初始化成功！\n");
return OK;
}
/*建立顺序表*/
Status CreatList(SqList& L, int a[], int n)
{
if (n > MAXSIZE)
{
printf("空间不足，无法建立顺序表！ \n");
return ERROR;
}
for (int i = 0; i < n; i++)
L->elem[i] = a[i];
L->length = n;
return OK;
}
/*遍历操作*/
void PrintList(SqList L)
{
for (int i = 0; i < L->length; i++)
printf("%d ", (L->elem[i]));
}
/*取值（按位查找）*/
Status GetElem(SqList L, int i, ElemType& e)
{
if (iL->length)
{
printf("查找位置非法，查找错误\n");
return ERROR;
}
else
{
e = L->elem[i - 1];
printf("%d\n", e);
return OK;
}
}
/*查找（按值查找）*/
Status LocateElem(SqList L, ElemType e)
{
for (int i = 0; i < L->length; i++)
if (L->elem[i] == e) return i + 1; //查找成功， 返回序号 i + l
return ERROR;//查找失败
}
/*插入*/
Status ListInsert(SqList& L, int i, int e)
{//在顺序表 L 中第 l. 个位置之前插入新的元素 e, i值的合法范围是 1length+l
if ((i < 1) || (i > L->length + 1)) return ERROR;//i值不合法
if (L->length == MAXSIZE) return ERROR;//当前存储空间已满
for (int j = L->length - 1; j >= i - 1; j--)
L->elem[j + 1] = L->elem[j];//插入位置及之后的元素后移
L->elem[i - 1] = e;//将新元素e放入第l个位置
++L->length; //表长加1
return OK;
}
/*删除*/
Status ListDelete(SqList& L, int i)
{//在顺序表L中删除第J.个元素，J.值的合法范围是1length+l
if ((i < 1) || (i > L->length)) return ERROR;//i值不合法
for (int j = i; j length - 1; j++)
L->elem[j - 1] = L->elem[j];//被删除元素之后的元素前移
--L->length;//表长减1
return OK;
}
//测试主程序
int main()
{
int a[5] = { 1,3,2,5,4 };
int* p = new int;
SqList List1;
InitList(List1);//初始化
printf("给顺序表赋值：1 2 3 4 5\n遍历并输出顺序表：\n");
CreatList(List1, a, 5);//建立
PrintList(List1);//遍历输出此顺序表
printf("\n取第三位的值：\n");//按位取值
GetElem(List1, 3, *p);
if (LocateElem(List1, 4) == 0)printf("查无此值！\n");//按值查找
else printf("顺序表中值为4的序号为:\n%d\n", LocateElem(List1, 4));
ListInsert(List1, 2, 8);//在序号2位置上插入8
printf("在序号2位置上插入8:\n");
PrintList(List1);//遍历输出此顺序表
ListDelete(List1, 3);//删除序号5上的元素
printf("\n删除序号3上的元素:\n");
PrintList(List1);//遍历输出此顺序表
}
Original: https://www.cnblogs.com/WMX-0121/p/15871954.html
Author: WMX_0121
Title: 《数据结构》（C语言版）学习笔记——第2章 线性表（顺序表的基本操作）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583949/
转载文章受原作者版权保护。转载请注明原作者出处！