数据结构顺序表基本操作（C/C++实现）
 
注意：本代码为了测试运行默认含有操作所需数据，如有需要可自己增删改相关数据
 
涉及基本运算
 
初始化顺序表
依次插入元素
输出顺序表
输出顺序表的长度
判断顺序表是否为空
输出顺序表的第n个元素
输出元素x的位置
在第n个元素位置上插入x元素
输出顺序表
删除顺序表的第n个元素
输出顺序表
释放顺序表
 
GitHub地址（包含.cpp文件和可执行程序exe）
 
我的数据结构GitHub地址
 
源代码（经VS2015、devC++编译器运行通过）
 
#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;          /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char ElemType;        /* ElemType类型根据实际情况而定，这里假设为int */


Status visit(ElemType c)
{
	printf("%c ", c);
	return OK;
}

typedef struct
{
	ElemType data[MAXSIZE];        /* 数组，存储数据元素 */
	int length;                                /* 线性表当前长度 */
}SqList;

/* 1.初始化顺序线性表 */
Status InitList(SqList *L)
{
	L->length = 0;
	return OK;
}

/* 2.初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L, int i, ElemType e)
{
	int k;
	if (L->length == MAXSIZE)  /* 顺序线性表已经满 */
		return ERROR;
	if (i<1 || i>L->length + 1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
		return ERROR;

	if (i <= L->length)        /* 若插入数据位置不在表尾 */
	{
		for (k = L->length - 1; k >= i - 1; k--)  /* 将要插入位置之后的数据元素向后移动一位 */
			L->data[k + 1] = L->data[k];
	}
	L->data[i - 1] = e;          /* 将新元素插入 */
	L->length++;

	return OK;
}


/* 3.初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{
	int i;
	for (i = 0; i<L.length; i++)
		visit(L.data[i]);
	printf("\n");
	return OK;
}

/* 4.初始条件：顺序线性表L已存在。
操作结果：返回L中数据元素个数 */
int ListLength(SqList L)
{
	return L.length;
}

/* 5.初始条件：顺序线性表L已存在。
操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(SqList L)
{
	if (L.length == 0)
		return TRUE;
	else
		return FALSE;
}

/* 6.初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L, int i, ElemType *e)
{
	if (L.length == 0 || i<1 || i>L.length)
		return ERROR;
	*e = L.data[i - 1];

	return OK;
}

/* 7.初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(SqList L, ElemType e)
{
	int i;
	if (L.length == 0)
		return 0;
	for (i = 0; i<L.length; i++)
	{
		if (L.data[i] == e)
			break;
	}
	if (i >= L.length)
		return 0;

	return i + 1;
}



/* 初始条件：顺序线性表L已存在。
操作结果：将L重置为空表 */
Status ClearList(SqList *L)
{
	L->length = 0;
	return OK;
}







/* 10.初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L, int i, ElemType *e)
{
	int k;
	if (L->length == 0)               /* 线性表为空 */
		return ERROR;
	if (i<1 || i>L->length)         /* 删除位置不正确 */
		return ERROR;
	*e = L->data[i - 1];
	if (i<L->length)                /* 如果删除不是最后位置 */
	{
		for (k = i; k<L->length; k++)/* 将删除位置后继元素前移 */
			L->data[k - 1] = L->data[k];
	}
	L->length--;
	return OK;
}

void unionL(SqList *La, SqList Lb)
{
	int La_len, Lb_len, i;
	ElemType e;
	La_len = ListLength(*La);
	Lb_len = ListLength(Lb);
	for (i = 1; i <= Lb_len; i++)
	{
		GetElem(Lb, i, &e);
		if (!LocateElem(*La, e))
			ListInsert(La, ++La_len, e);
	}
}

int main()
{

	SqList L;
	SqList Lb;

	ElemType e;
	Status i;
	int j, k;
	/*1.初始化*/
	i = InitList(&L);
	printf("1.初始化L后：L.length=%d\n", L.length);

	/*2.依次插入abcde*/
	i = ListInsert(&L, 1, 'e');
	i = ListInsert(&L, 1, 'd');
	i = ListInsert(&L, 1, 'c');
	i = ListInsert(&L, 1, 'b');
	i = ListInsert(&L, 1, 'a');
	printf("2.abcde插入执行完毕\n");

	/*3.输出顺序表*/
	printf("3.在L的表头依次插入a～e后：L.data=\n");
	ListTraverse(L);

	/*4.顺序表长度*/
	printf("4.L.length=%d \n", L.length);

	/*5.判空*/
	i = ListEmpty(L);
	printf("5.L是否空：i=%d(1:是 0:否)\n", i);

	/*6.输出顺序表L的第三个元素*/
	GetElem(L, 3, &e);
	printf("6.第3个元素的值为：%c\n", e);

	/*7.输出顺序表a的位置*/
	int l = LocateElem(L, 'a');
	printf("7.返回元素a的位序：%d\n", l);

	/*8.在第4个元素位置上插入f元素*/
	i = ListInsert(&L, 5, 'f');
	printf("8.在第4个元素位置上插入f元素执行完毕\n", L.length);

	/*9.输出顺序表*/
	printf("9.在L的第4个元素位置上插入f元素后：L.data=\n");
	ListTraverse(L);

	/*10.删除顺序表L的第三个元素*/

	i = ListDelete(&L, 3, &e); /* 删除第j个数据 */
	if (i == ERROR)
		printf("删除第%d个数据失败\n", 3);
	else
		printf("10.删除第个的元素成功\n");

	/*11.输出顺序表L*/
	printf("11.输出顺序表\n");
	ListTraverse(L);

	/*12.释放顺序表*/
	i = ClearList(&L);
	printf("释放顺序表执行完毕\n"); 
	system("pause");
		return 0;
}

数据结构顺序表的指针（C语言）简单实现
 
思来想去决定向嵌入式系统方向靠拢。虽然本科是电子信息科学与技术，但是从未学过数据结构、操作系统等计算机方面的专业课。故最近开始学习数据结构，使用严蔚敏老师的第二版教材。
 
为了更好的理解这门课程，每学一部分就用代码来实现一下。写本文的目的是分享一下代码，并希望大佬能给萌新提出宝贵的建议。
 
 
 
《数据结构（C语言）（第2版）》严蔚敏 李冬梅 吴伟民 编著
 
 
1.顺序表
 
 
线性表的顺序表示
 指的是用一组地址连续的存储单元依次存储线性表的数据元素，也称线性表的顺序存储结构或顺序映像。通常称这种存储结构的线性表为顺序表。
 
 
顺序表特点
 逻辑上相邻的数据元素，其物理次序也相邻。
 
 
顺序表中地址关系
 假设线性表的每个元素占用 L 个存储单元，以第一个单元的存储地址为数据元素的存储起始位置。则线性表中第i+1个数据元素的存储位置LOC（ai+1）和第i个数据元素的存储位置LOC（ai)之间的关系为:
 LOC（ai+1）=LOC（ai)+L
 一般来说，线性表的第i个元素ai的存储位置为：
 LOC(ai)=LOC(a1)+(i-1)*L。
 综上，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。
 
 
 
顺序表的抽象数据类型定义
 
	ADT List{
   		数据对象： D={a~i~|a~i~∈ElemSet,i=1,2,...,n,n≥0}
   		数据关系： R={<a~i-1~,a~i~>|a~i-1~,a~i~∈D，i=1,2..n}
   		基本操作:

   		InitList(*L)
   		操作结果： 构造一个空的顺序表。
   		
   		ApeendList(*L,pl)
   		初始条件：顺序表L已存在
   		操作结果： 构造一个空的顺序表。
   		
   		InsertList(*L,index,pl)
   		初始条件：顺序表L已存在且不为空
   		操作结果： 在顺序表L中的index位置插入pl

   	    DeleteList(*L,index)
   	    初始条件：顺序表L已存在且不为空
   	    操作结果：删除顺序表L中的index位置元素

   	    FindList(*L，pl)
   	    初始条件：顺序表L已存在且不为空
   	    操作结果：在顺序表L中查找数据元素pl，返回当前位置，若不存在则返回ERROR
   
   		PrintList(L)
   		操作结果：打印顺序表
}ADT List
 
2.C语言指针的简单实现
 
将电压和电流的瞬时值表达式变换成极坐标形式存储在顺序表中。例:U=Um*sqrt(2)sin（wt+α),通过欧拉公式得U=Um/sqrt(2)（cosα+jsinα) —>U=a+bj。
 
 将以上与存储关系相对应，如下图：
 
 
预处理阶段
 
#define OK 1		//状态值
#define ERROR -1 
#define OVERFLOW -2	
#define MAXSIZE 50 //顺序表长度
 
构建相关结构体
 
typedef int Status;

/*构建复数结构体*/
typedef struct {
	float real;			//实部
	double complex;		//虚部
}Ploy;

/*构建顺序表结构体*/
typedef struct {
	Ploy* elem;		//顺序表地址指针，指向Ploy结构体
	int lenth;			//顺序表长度
}SqList;
 
基本函数
 
（1）顺序表的初始化
 ①为顺序表L动态分配一个预定义大小的空间，使elem指向这段空间的基地址。
 ②将表的当前长度设为0。
 
Status InitList(SqList* L) {
	L->elem = (Ploy*)malloc(sizeof(Ploy*)*MAXSIZE);
	if (L->elem == NULL) {    //若elme为NULL则分配空间失败
		printf("Init Error");
		return ERROR;
	}

	L->lenth = 0;
	return OK;
}
 
（2）追加数据元素
 ①给顺序表追加一个数据元素，若超出设置的最大长度返回OVERFLOW。
 ②将表的当前长度+1。
 
Status AppendList(SqList* L, Ploy pl) {
	if (L->lenth > MAXSIZE) return OVERFLOW;
	*(L->elem + L->lenth) = pl;   //追加数据元素
	L->lenth++;
	return OK;
}
 
（3）删除数据元素
 ①删除顺序表中index位置的元素，后续元素向上补位。当index<1或index>当前顺序表长度则返回OVERFLOW。
 ②将表的当前长度-1
 
Status DeleteList(SqList* L, int index) {
index--;   //以1为数据的第一个元素
	if (index<0 || index > L->lenth) {
		printf("Over Round");
		return OVERFLOW;
	}

	for (int i = index; i < L->lenth; i++) {
		*(L->elem + i) = *(L->elem + i + 1);
	}

	L->lenth--;
	return OK;
}
 
（4）插入数据元素
 ①在顺序表中的index位置插入数据元素，index后的数据元素向下依次存入，并将当前顺序表长度+1。
 ②当index<1或index>当前顺序表长度时返回OVERFLOW。当index为最后一个元素位置(等于MAXSIZE)时替换MAXSIZE位置元素，当前顺序表长度不变。
 
Status InsertList(SqList* L, int index ,Ploy pl) {
	--index;

	if (index<0 || index>L->lenth) { 
		printf("Over Round!");
		return OVERFLOW; 
	}

	if (index == L->lenth) {
		*(L->elem + L->lenth) = pl;
		if (L->lenth == MAXSIZE )
			return OK;
		else{
			L->lenth++;
			return OK;
		}
	}

	for (int i = L->lenth; i >=index; i--)   
		*(L->elem + i + 1) = *(L->elem + i);
		//index后的数据元素向下依次存入
		
	*(L->elem + index) = pl;

	L->lenth++;
	return OK;
}
 
（5）查找元素位置
 ①在顺序表中查找元素所在位置，返回值为int型。
 ②元素不存在，则返回ERROR。
 
int FindList(SqList L, Ploy pl) {
	for (int i = 0; i < L.lenth; i++)
		if (
			L.elem[i].real == pl.real &&
			L.elem[i].complex == pl.complex 
			)
			return i + 1;

	printf("None");
	return ERROR;
}
 
（6）打印当前顺序表
 
void PrintList(SqList* L,const char c) {
	printf("num\treal\t    complex\n");
	for (int i = 0; i < L->lenth; i++){
		printf("%c%d\t%.3f      %.4f\n",c,i+1,(L->elem+i)->real, (L->elem+i)->complex);
	}
	return;
}
 
（7）函数的实现
 
int main()
{	
	SqList Volt;	//创建一个电压的顺序表
	Ploy u1 = { 12.653 , 2.189 };  //仅举例说明电压的极坐标形式 
	Ploy u2 = { 13.15 , 65.17 };  //U=Um*sin(wt+α) -> u=Um/sqrt(2)*(cosα+sinα*j)  
	Ploy u3 = { 50.23  , 8.395 };  
	
	InitList(&Volt);	//对电压顺序表操作

	AppendList(&Volt, u1);	//追加数据元素
	AppendList(&Volt, u2);
	AppendList(&Volt, u3);

	Ploy u4 = { 11.0   ,  15.68 };
	InsertList(&Volt,3, u4);  //在第三个位置插入数据元素u4

	DeleteList(&Volt, FindList(Volt, u3));   //查找数据元素u3的位置并删除

	PrintList(&Volt,'u');		//打印电压顺序表
	printf("\n");

	return 0;
}
 
（8）调试结果
 
 
3.总结
 
本篇文章实现了顺序表的指针简单实现，还未进行对时间复杂的的优化，以后的文章会深入这些问题。
 
（初入数据结构，可能会漏掉重要知识点，而且C语言不大熟练，还望大佬给予宝贵的建议。）

数据结构顺序表
 

 

/*
 *顺序表的查找算法（重点是哨兵的设置）
 *创建一个数据结构体
 *创建一个顺序表的结构体
 *顺序表结构体里面包含 数据数组 和 数组长度
 *采用两种查找方法 哨兵设置 普通查找
 *哨兵排序算法的设置的好处是可以降低时间的复杂度 节省 for循环的次数
 *程序 的步骤分为 初始化顺序表 创建顺序表 查找 输出 测试
 */
 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 1024//数据的个数
typedef  int KeyType;//关键字的数据类型
typedef  char* ValueType;//标识字符串的数据类型
typedef int Statu;//返回值的数据类型

#define ERROR 0
#define OK 1
typedef struct elementtype
{
    KeyType key;//关键字
    ValueType value;//数据域

}ElementType;//顺序表中的数据结构体
typedef struct seqlist
{
    ElementType *datas;//数据数组
    int length;//顺序表长度
}SeqList;//顺序表点的结构体数据类型
void InIt(SeqList*s);//顺序表的初始化
void test();//测试函数
void print_seqlist(SeqList*s);//打印顺序表
Statu search_seqlist1(SeqList*s,KeyType key);//顺序表的节点数据的查找
Statu search_seqlist2(SeqList*s,KeyType key);//顺序表的节点数据的查找(设置哨兵元素)

void main()
{
    test();//测试函数
}
void InIt(SeqList*s)//顺序表的初始化
{
    s->datas=(ElementType*)malloc(sizeof(ElementType)*MAX_SIZE);//创建顺序表的储存空间
    s->length=0;//初始化顺序表的长度
}
void print_seqlist(SeqList*s)//打印顺序表的元素
{
    int i;
    for(i=1;i<=s->length;i++)//下标为0的位置不放数据
          printf("%d %s\n",s->datas[i].key,s->datas[i].value);



}
Statu search_seqlist1(SeqList*s,KeyType key)//顺序表的节点数据的查找
{
    int i;
   // printf("%d\n",s->length);
    for(i=1;i<=s->length;i++)
    {
        if(s->datas[i].key==key)
            return i;
    }
    return 0;
}
Statu search_seqlist2(SeqList*s,KeyType key)//顺序表的节点数据的查找(设置哨兵元素)
{
    //好处节省了for循环中循环条件的判断
      //设置哨兵和将第一个数组的位置空下来是一样的
     s->datas[0].key=key;
    int i;
    for(i=s->length-1;s->datas[i].key!=key;i--)
           return i;






}