数据结构(C语言描述)——顺序表-创新互联

上一篇文章里面我们创建了一个封装预处理命令和宏定义的头文件"StdFile.h"，现在我们再次引用此头文件，进行后续操作。

成都创新互联公司专注于金城江网站建设服务及定制，我们拥有丰富的企业做网站经验。热诚为您提供金城江营销型网站建设，金城江网站制作、金城江网页设计、金城江网站官网定制、微信小程序定制开发服务，打造金城江网络公司原创品牌,更为您提供金城江网站排名全网营销落地服务。

线性表的顺序存储结构，存储空间是连续的，空间大小是提前设定好的(静态存储)，当然现在C99和C11允许使用变长数组，这里不讨论此新增内容。

优点:便于查找和索引，存储空间利用率较高。

缺点;若内存空间分配过小会造成数据溢出，过大会造成空间浪费。中间插入和排序要移动大量元素，算法复杂度过大。

以下是关于顺序表的基本定义:

#define MAX_SIZE 100

typedef struct
{
	ElemType elem[MAX_SIZE];
	Index last;
}SeqList;

其中MAZ_SIZE为大结点数，数值可修改，last为顺序表最后一个元素的数组下标(注意不是序号)。当表满时，last=MAX_SIZE-1，当表空时，last=-1，注意last=0，说明有一个元素。

接下来我们创建一个包括顺序表的定义和方法的头文件"SeqList.h“。

里面包括的内容如下:

#include "StdFile.h"
#define MAX_SIZE 100

typedef struct
{
	ElemType elem[MAX_SIZE];
	Index last;
}SeqList;

//初始化顺序表
void InitList(SeqList* L)
{
	memset(L, 0, sizeof(ElemType) * MAX_SIZE);
	L->last = -1;
}

//创建顺序表
SeqList CreateList(Num Len = 20, ElemType Max = 100)
{
	SeqList L;
	Index i;
	InitList(&L);
	L.last = Len - 1;
	for (i = 0; i<= L.last; i++)
	{
		srand((unsigned)time(NULL) + (unsigned)rand());
		L.elem[i] = rand() % Max + 1;
	}
	return L;
}

//创建有序顺序表
SeqList CreateOrdList(ElemType a = 0, ElemType b = MAX_SIZE, Step s = 1)
{
	SeqList L;
	InitList(&L);
	ElemType e;
	Index i = 0;
	if (s >0 && a<= b)
		for (e = a, i = 0; e<= b; e += s, i++)
			L.elem[i] = e;
	else
		for (e = a, i = 0; e >= b; e += s, i++)
			L.elem[i] = e;
	L.last = i - 1;
	return L;
}

//输入顺序表
SeqList InputList()
{
	SeqList L;
	InitList(&L);
	Index i = 0;
	char c;
	do
	{
		scanf_s("%lld", &L.elem[i]);
		c = getchar();
		i++;
	} while (c != '\n');
	L.last = i - 1;
	return L;
}

//打印元素
void PrintList(SeqList L)
{
	Index i;
	for (i = 0; i<= L.last; i++)
		printf("%lld ", L.elem[i]);
	putchar('\n');
}

//元素个数
Num ListLength(SeqList L)
{
	return L.last + 1;
}

//判断元素存在
int IsInList(SeqList L, ElemType e)
{
	Index i;
	for (i = 0; i<= L.last; i++)
		if (L.elem[i] == e)
			return TRUE;
	return FALSE;
}

//获取元素
ElemType GetDataList(SeqList L, Index i)
{
	if (i >= 1 && i<= L.last + 1)
		return L.elem[i - 1];
	return ERROR;
}

//查找元素
Index LocateList(SeqList L, ElemType e)
{
	Index i;
	for (i = 0; i<= L.last; i++)
		if (L.elem[i] == e)
			return i + 1;
	return -1;
}

//插入单个元素
int InsList(SeqList* L, Index i, ElemType e)
{
	Index j;
	if (1<= i && i<= L->last + 2 && L->last + 2<= MAX_SIZE)
	{
		for (j = L->last; j >= i - 1; j--)
		{
			L->elem[j + 1] = L->elem[j];
		}
		L->elem[i - 1] = e;
		L->last++;
		return OK;
	}
	else
		return ERROR;
}

//删除单个元素
int DelList(SeqList* L, Index i)
{
	Index j;
	if (1<= i && i<= L->last + 1)
	{
		for (j = i - 1; j< L->last; j++)
			L->elem[j] = L->elem[j + 1];
		L->last--;
		return OK;
	}
	else
		return ERROR;
}

//判断空表
int EmptyList(SeqList L)
{
	if (L.last = -1)
		return TRUE;
	else
		return FALSE;
}

//清空元素
void ClearList(SeqList* L)
{
	memset(L, 0, sizeof(ElemType) * MAX_SIZE);
	L->last = -1;
}

//销毁顺序表
void DestroyList(SeqList* L)
{
	free(L);
}

//顺序表转置
void ReverseList(SeqList* L)
{
	Index i;
	ElemType t;
	for (i = L->last; i >= L->last / 2; i--)
	{
		t = L->elem[L->last - i];
		L->elem[L->last - i] = L->elem[i];
		L->elem[i] = t;
	}
}

//顺序表排序
void SortList(SeqList* L, int reverse = FALSE)
{
	Index i, j;
	ElemType t;
	if (reverse == FALSE)
	{
		for (i = 0; i<= L->last - 1; i++)
		{
			for (j = i + 1; j<= L->last; j++)
			{
				if (L->elem[j]< L->elem[i])
				{
					t = L->elem[i];
					L->elem[i] = L->elem[j];
					L->elem[j] = t;
				}
			}
		}
	}
	else
	{
		for (i = 0; i<= L->last - 1; i++)
		{
			for (j = i + 1; j<= L->last; j++)
			{
				if (L->elem[j] >L->elem[i])
				{
					t = L->elem[i];
					L->elem[i] = L->elem[j];
					L->elem[j] = t;
				}
			}
		}
	}
}

//末尾追加元素
int AppendList(SeqList* L, ElemType e)
{
	if (L->last + 2 >MAX_SIZE)
		return ERROR;
	else
	{
		L->elem[L->last + 1] = e;
		L->last++;
		return OK;
	}
}

//顺序拼接
SeqList MergeList(SeqList L1, SeqList L2)
{
	SeqList L3;
	InitList(&L3);
	Index i, j, k = 0;
	for (i = 0, j = 0; i<= L1.last && j<= L2.last;)
	{
		if (L1.elem[i]<= L2.elem[j])
		{
			L3.elem[k] = L1.elem[i];
			i++;
			k++;
		}
		else
		{
			L3.elem[k] = L2.elem[j];
			j++;
			k++;
		}
	}
	while (i<= L1.last)
	{
		L3.elem[k] = L1.elem[i];
		i++;
		k++;
	}
	while (j<= L2.last)
	{
		L3.elem[k] = L2.elem[j];
		j++;
		k++;
	}
	L3.last = L1.last + L2.last + 1;
	return L3;
}

//升序插入元素
int InsOrdList(SeqList* L, ElemType e)
{
	Index i, j;
	if (L->last + 2 >MAX_SIZE)
		return ERROR;
	else
	{
		for (i = 0, j = L->last + 1; i<= L->last; i++)
			if (L->elem[i] >= e)
			{
				j = i;
				break;
			}
		for (i = L->last + 1; i >j; i--)
			L->elem[i] = L->elem[i - 1];
		L->elem[i] = e;
		L->last++;
		return OK;
	}
}

//拼接顺序表
SeqList ExtendList(SeqList L1, SeqList L2)
{
	Index i;
	SeqList L;
	InitList(&L);
	for (i = 0; i<= L1.last; i++)
		L.elem[i] = L1.elem[i];
	for (i = L1.last + 1; i<= L1.last + L2.last + 1; i++)
		L.elem[i] = L2.elem[i - L1.last - 1];
	L.last = L1.last + L2.last + 1;
	return L;
}

//删除子串
int RemoveList(SeqList* L, Index i, Num k)
{
	Index j;
	if (1<= i && i<= L->last + 1 && k >= 0)
	{
		for (j = i + k - 1; j<= L->last; j++)
			L->elem[j - k] = L->elem[j];
		L->last = L->last - k;
		return OK;
	}
	else
		return ERROR;
}

//顺序表比较
int CompareList(SeqList L1, SeqList L2)
{
	Index i = 0;
	while (i != L1.last && i != L2.last)
	{
		if (L1.elem[i] >L2.elem[i])
			return 1;
		if (L2.elem[i] >L1.elem[i])
			return -1;
		i++;
	}
	if (i == L1.last && i != L2.last)
		return -1;
	else if (i == L2.last && i != L1.last)
		return 1;
	else
		return 0;
}

//筛选删除元素
int SelectList(SeqList* L, ElemType min, ElemType max)
{
	Index i;
	if (min< max)
	{
		do
		{
			for (i = 0; i<= L->last; i++)
				if (L->elem[i]elem[i]>max)
					break;
		} while (DelList(L, i + 1));
		return OK;
	}
	else
		return ERROR;
}

//元素替换
void ReplaceList(SeqList* L, ElemType e, ElemType r)
{
	Index i;
	for (i = 0; i<= L->last; i++)
		if (L->elem[i] == e)
			L->elem[i] = r;
}

//元素计数
Num CountList(SeqList L, ElemType e)
{
	Num n = 0;
	Index i;
	for (i = 0; i<= L.last; i++)
		if (L.elem[i] == e)
			n++;
	return n;
}

//获取大值
ElemType MaxList(SeqList L)
{
	Index i;
	ElemType max;
	for (i = 0, max = L.elem[0]; i<= L.last; i++)
		if (L.elem[i] >max)
			max = L.elem[i];
	return max;
}

//获取最小值
ElemType MinList(SeqList L)
{
	Index i;
	ElemType min;
	for (i = 0, min = L.elem[0]; i<= L.last; i++)
		if (L.elem[i] >min)
			min = L.elem[i];
	return min;
}

//交叉插入元素
SeqList CrossInsList(SeqList L1, SeqList L2)
{
	SeqList L;
	Index i, j, k;
	InitList(&L);
	if (L1.last >L2.last)
	{
		for (i = 0, j = 0, k = 0; j<= L2.last; i++, j++)
		{
			L.elem[k] = L1.elem[i];
			k++;
			L.elem[k] = L2.elem[j];
			k++;
		}
		for (; i<= L1.last; i++, k++)
			L.elem[k] = L1.elem[i];
		L.last = k - 1;
	}
	else
	{
		for (i = 0, j = 0, k = 0; i<= L1.last; i++, j++)
		{
			L.elem[k] = L1.elem[i];
			k++;
			L.elem[k] = L2.elem[j];
			k++;
		}
		for (; j<= L2.last; j++, k++)
			L.elem[k] = L2.elem[j];
		L.last = k - 1;
	}
	return L;
}

typedef SeqList Set;

//初始化集合
void InitSet(Set* S)
{
	memset(S, 0, sizeof(ElemType) * MAX_SIZE);
	S->last = -1;
}

//判断元素存在
int IsInSet(Set S, ElemType e)
{
	Index i;
	for (i = 0; i<= S.last; i++)
		if (S.elem[i] == e)
			return TRUE;
	return FALSE;
}

//集合
Set SetList(SeqList L)
{
	Index i, k;
	Set S;
	InitSet(&S);
	S.last = L.last;
	for (i = 0, k = 0; i<= L.last; i++)
	{
		if (!IsInSet(S, L.elem[i]))
		{
			S.elem[k] = L.elem[i];
			k++;
		}
	}
	S.last = k - 1;
	return S;
}

//交集
Set IntersectionSet(Set S1, Set S2)
{
	Set S3;
	InitSet(&S3);
	Index i, j, k = 0;
	for (i = 0; i<= S1.last; i++)
	{
		for (j = 0; j<= S2.last; j++)
		{
			if (S2.elem[j] == S1.elem[i])
			{
				S3.elem[k] = S1.elem[i];
				k++;
			}
		}
	}
	S3.last = k - 1;
	return S3;
}

//并集
Set UnionSet(Set S1, Set S2)
{
	Set S3;
	InitSet(&S3);
	Index i, j, k;
	for (i = 0, k = 0; i<= S1.last; i++, k++)
		S3.elem[k] = S1.elem[i];
	S3.last = S1.last;
	for (j = 0; j<= S2.last; j++)
	{
		if (!IsInSet(S3, S2.elem[j]))
		{
			S3.elem[k] = S2.elem[j];
			k++;
		}
	}
	S3.last = k - 1;
	return S3;
}

//差集
Set DifferentSet(Set S1, Set S2)
{
	Set S3;
	InitSet(&S3);
	Index i, k;
	for (i = 0, k = 0; i<= S1.last; i++)
	{
		if (!IsInSet(IntersectionSet(S1, S2), S1.elem[i]))
		{
			S3.elem[k] = S1.elem[i];
			k++;
		}
	}
	S3.last = k - 1;
	return S3;
}

//对称差集
Set SymmetricDifferenceSet(Set S1, Set S2)
{
	Set S3;
	InitSet(&S3);
	Index i, j, k;
	for (i = 0, k = 0; i<= S1.last; i++)
	{
		if (!IsInSet(IntersectionSet(S1, S2), S1.elem[i]))
		{
			S3.elem[k] = S1.elem[i];
			k++;
		}
	}
	for (j = 0; j<= S2.last; j++)
	{
		if (!IsInSet(IntersectionSet(S1, S2), S2.elem[j]))
		{
			S3.elem[k] = S2.elem[j];
			k++;
		}
	}
	S3.last = k - 1;
	return S3;
}

这里包含顺序表的随机创建(长度，大值)，有序创建(下限，上限，步长)，输入创建。

顺序表初始化，判断空表，顺序表的打印，清空元素，销毁。

判断元素存在，查找元素，获取元素，元素追加。

序号插入，有序插入，插入子串……删除单个元素，删除多个元素，替换元素。

对于两个顺序表还有拼接，交叉插入，按顺序插入等操作。

在主函数中调用函数:

#include "SeqList.h"
int main()
{
	SeqList L, L1, L2;
	L = CreateList();
	L1 = CreateOrdList(10, 30, 2);
	L2 = { {1,2,3,4,5,6,7,8,9},8 };
	cout<< "L ";
	PrintList(L);
	cout<< "L1 ";
	PrintList(L1);
	cout<< "L2 ";
	PrintList(L2);
	cout<< "L逆排序"<< endl;
	SortList(&L, TRUE);
	PrintList(L);
	cout<< "L1和L2交叉插入"<< endl;
	PrintList(CrossInsList(L1, L2));
	cout<< "筛选出介于3，32之间的元素"<< endl;
	SelectList(&L, 3, 32);
	PrintList(L);
}

结果如下:

之后通过对顺序表的定义，引申出集合的定义:

typedef struct
{
	ElemType elem[MAX_SIZE];
	Index last;
}Set;

其实和顺序表的定义一模一样，大的区别是:元素无重复。

包括顺序表转化为集合(消除相同元素)，集合初始化，判断元素存在。

两集合的交集，并集，差集，对称差集……

在主函数中调用:

#include "SeqList.h"
int main()
{
	SeqList L;
	Set S, S1, S2;
	L = { {1,2,2,3,3,4,6,7,5,7,8,6,9,5},13 };
	S1 = { {1,2,3,4,5,6},5 };
	S2 = { {4,7,3,8,9,5,0,2},7 };
	cout<< "L ";
	PrintList(L);
	S = SetList(L);
	cout<< "S ";
	PrintList(S);
	cout<< "S1 ";
	PrintList(S1);
	cout<< "S2 ";
	PrintList(S2);
	cout<< "交集"<< endl;
	PrintList(IntersectionSet(S1, S2));
	cout<< "差集S1-S2"<< endl;
	PrintList(DifferentSet(S1, S2));
	cout<< "差集S2-S1"<< endl;
	PrintList(DifferentSet(S2, S1));
	cout<< "对称差集"<< endl;
	PrintList(SymmetricDifferenceSet(S1, S2));
}

结果如下:

之后我们在资源文件创建"Help.SeqList.txt"的文本文件，里面记录顺序的定义和方法索引:

typedef struct
{
	ElemType elem[MAX_SIZE];
	Index last;
}SeqList;

//初始化顺序表
void InitList(SeqList* L)

//创建顺序表
SeqList CreateList(Num Len = 20, ElemType Max = 100)

//创建有序顺序表
SeqList CreateOrdList(ElemType a = 0, ElemType b = MAX_SIZE, Step s = 1)

//输入顺序表
SeqList InputList()

//打印元素
void PrintList(SeqList L)

//元素个数
Num ListLength(SeqList L)

//判断元素存在
int IsInList(SeqList L, ElemType e)

//获取元素
ElemType GetDataList(SeqList L, Index i)

//查找元素
Index LocateList(SeqList L, ElemType e)

//插入单个元素
int InsList(SeqList* L, Index i, ElemType e)

//删除单个元素
int DelList(SeqList* L, Index i)

//判断空表
int EmptyList(SeqList L)

//清空元素
void ClearList(SeqList* L)

//销毁顺序表
void DestroyList(SeqList* L)

//顺序表转置
void ReverseList(SeqList* L)

//顺序表排序
void SortList(SeqList* L, int reverse = FALSE)

//末尾追加元素
int AppendList(SeqList* L, ElemType e)

//顺序拼接
SeqList MergeList(SeqList L1, SeqList L2)

//升序插入元素
int InsOrdList(SeqList* L, ElemType e)

//拼接顺序表
SeqList ExtendList(SeqList L1, SeqList L2)

//删除子串
int RemoveList(SeqList* L, Index i, Num k)

//顺序表比较
int CompareList(SeqList L1, SeqList L2)

//筛选删除元素
int SelectList(SeqList* L, ElemType min, ElemType max)

//元素替换
void ReplaceList(SeqList* L, ElemType e, ElemType r)

//元素计数
Num CountList(SeqList L, ElemType e)

//获取大值
ElemType MaxList(SeqList L)

//获取最小值
ElemType MinList(SeqList L)

//交叉插入元素
SeqList CrossInsList(SeqList L1, SeqList L2)

typedef struct
{
	ElemType elem[MAX_SIZE];
	Index last;
}Set;

//初始化集合
void InitSet(Set* S)

//判断元素存在
int IsInSet(Set S, ElemType e)

//集合
Set SetList(SeqList L)

//交集
Set IntersectionSet(Set S1, Set S2)

//并集
Set UnionSet(Set S1, Set S2)

//差集
Set DifferentSet(Set S1, Set S2)

//对称差集
Set SymmetricDifferenceSet(Set S1, Set S2)

之后继续更新线性单链表的方法。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章题目：数据结构(C语言描述)——顺序表-创新互联
网址分享：http://ybzwz.com/article/dsodoh.html

数据结构(C语言描述)——顺序表-创新互联

其他资讯