【【数据结构】线性表顺序存储结构-数组】
文章目录
- 线性表的顺序存储结构
- 基本操作
- 应用实例
线性表的顺序存储结构
- C/C++中借助数组来实现顺序表
文章图片
//线性表定义
#define MAX_SIZE50
#define FAILED0
#define SUCCESS1
typedef intElemType
typedef structSqList
{
ElemType data[MAX_SIZE];
int length;
}SqList;
//**********************建立顺序表**********************//SqList* CreateList(ElemType a[], int n)
{
int i = 0;
SqList* L = (SqList *)malloc(sizeof(SqList));
while (i < n)
{
L->data[i] = a[i];
i++;
}
L-> length = i;
return L;
}//**********************初始化线性表**********************//SqList* InitList()
{
SqList* L = (SqList*)malloc(sizeof(SqList));
L->length = 0;
return L;
}//**********************销毁线性表**********************//void DestroyList(SqList* L)
{
free(L);
}//**********************判断线性表是否为空**********************//intListEmpty(SqList* L)
{
return (L->length == 0);
}//**********************求表长**********************//
int ListLength(SqList* L)
{
return (L->length );
}//**********************输出信息**********************//voidDispList(SqList* L)
{
for (int i = 0;
i < L->length;
i++)
printf("%d", L->data[i]);
printf("\n");
}//**********************求第i个值**********************//
int LocateElem(SqList* L, ElemType e)
{
int i = 0;
while (i < L->length && L->data[i] != e)
i++;
if (i >= L->length)
return FAILED;
else
return i + 1;
}//**********************返回值为e的索引**********************//int LocateElem(SqList* L, ElemType e)
{
int i = 0;
while (i < L->length && L->data[i] != e)
i++;
if (i >= L->length)
return FAILED;
else
return i + 1;
}//**********************在第i位置插入**********************//intListInsert(SqList* L, int i, ElemType e)
{
if (i<1 || i>L->length)
return FAILED;
i--;
for (int j = L->length;
j > i;
j--)
L->data[j] = L->data[j - 1];
L->data[i] = e;
L->length++;
return SUCCESS;
}//**********************删除第i个值返回给e**********************//intListDelete(SqList* L, int i, ElemType* e)
{
if (i<1 || i>L->length)
return FAILED;
i--;
*e = L->data[i];
for (int j = i;
j < L->length -1;
j++)
L->data[j] = L->data[j + 1];
L->length--;
return SUCCESS;
}
应用实例
//删除所有值为e的元素值 时间复杂度 O(N)
void DelListElem(SqList* L,ElemType e)
{
int k = 0;
for (int i = 0;
i < L->length;
i++)
{
if (L->data[i] != e)
{
L->data[k] = L->data[i];
k++;
}
}
L->length = k;
/*int k = 0;
int i = 0;
while (i < L->length)
{
if (L->data[i] == e)
k++;
else
L->data[i - k] = L->data[i];
i++;
}
L->length -= k;
*/
}//排序，以第一个为哨兵，大的往后放，小的往前放
void Partition(SqList* L)
{
int temp = L->data[0];
int i = 0;
int j = L->length - 1;
while (i < j)
{
while (idata[j]>temp)
j--;
L->data[i] = L->data[j];
while (i < j && L->data[i] <= temp)
i++;
L->data[j] = L->data[i];
}
L->data[i] = temp;
}
//奇偶分开，奇数放前，偶数放后
//类比于上一个例子的排序思想
void OddToEven(SqList* L)
{
int i = 0;
int j = L->length - 1;
int temp = L->data[0];
while (i < j)
{
while (i < j && L->data[j] % 2 == 0)
j--;
L->data[i] = L->data[j];
while (i < j && L->data[i] % 2 == 1)
i++;
L->data[j] = L->data[i];
}
L->data[i] = temp;
}
