1.结构体定义-顺序

线性表存储结构：



首先

typedef int ElementType;//定义别名
#define MAXSIZE 100		//宏定义

//第一种
typedef struct LNode
{
     ElementType Data[MAXSIZE];
     int Last;	//Last表示位置（n-1）
}L,*List;
List PtrL; //等价于typedef struct LNode *PtrL
L PtrL1;	//等价于typedef struct LNode PtrL1

或者

typedef struct LNode *List;
typedef struct LNode L;
struct LNode
{
	ElementType Data[MAXSIZE];
	int Last;

};
L PtrL1;
List PtrL;

2.初始化(建立空的顺序表)

List MakeEmpty()
{
	List PtrL;
	PtrL = (List)malloc(sizeof(struct LNode));	//分配空间
	PtrL->Last =-1;
	return PtrL;
}

3.查找（按元素查找）

int Find(ElementType X,List PtrL)
{
	int i = 0;
	while(i <= PtrL->Last && PtrL->Data[i]!= X) //表的长度Last+1
	{
		i++;
	}
	if(i > PtrL->Last)	return -1;	//没找到
	else return i+1;	//返回所在位置
}

平均比较次数(n+1)/2： 运气好第一次找到，运气差最后一次找到

4.插入

（第i(1<=i<=n+1)个位置上插入一个值为X的新元素）:使X变为第i个位置

void Insert(ElementType X,int i,List Ptrl)
{
	int j;
	if( PtrL->Last == MAXSIZE-1) //现有长度已经最长最长
	{
		printf("表已满");
		return;
	}
	if(i < 1 || i > PtrL->Last + 2)  //保证插入位置在第1个到第n+1个之间
	{
		printf("插入位置不合法");
		return;
	}
	for(j = PtrL->Last;j>=i-1;j--)
	{
		PtrL->Data[j+1] = PtrL->Data[j];
	}
	PtrL->Data[i-1] = X;
	PtrL->Last++;	//末尾Last后移一位
}

平均移动次数为n/2

5.删除

void Delete(int i,List PtrL)
{
	int j;
	if(i < 1 || i > PtrL->Last+1)
	{
		printf("不存在第%d个元素",i);
		return;
	}
	for(j = i;j<PtrL->Last;j++)		//把第i+1个元素往前移动覆盖掉第i个元素
	{
		PtrL->Data[j-1] = PtrL->Data[j];	//从前向后移动
	}
	PtrL->Last--;
	return;
}

平均移动次数(n-1)/2

6.查找（按位置查找）

int Find1(int i,List PtrL)
{
	if(i < 1 ||i > PtrL->Last + 1)
	{
		printf("不存在第%d个元素",i);
		
	}
	else
		return PtrL->Data[i-1];
}

测试

	//测试插入
	printf("插入\n");
	Insert(5,1,PtrL);
	Insert(4,1,PtrL);
	Insert(3,1,PtrL);
	Insert(2,1,PtrL);
	for(int i = 0;i<=PtrL->Last;i++)
	{
		printf("%d ",PtrL->Data[i]);
	}
	printf("\n*****************\n");

	//测试删除
	printf("删除\n");
	Delete(4,PtrL);
	for(int i = 0;i<=PtrL->Last;i++)
	{
		printf("%d ",PtrL->Data[i]);
	}
	printf("\n*****************\n");

	//测试元素查找
	printf("按元素查找\n");
	printf("4在第%d个位置",Find(4,PtrL));
	printf("\n*****************\n");

	//测试位置查找
	printf("按位置查找\n");
	printf("第2个位置的元素是： %d",Find1(2,PtrL));
	printf("\n*****************\n");

	system("pause");
	return 0;
}

完整代码

//线性表实现——顺序表
#include<stdio.h>
#include <stdlib.h>
using namespace std;
typedef int ElementType;
#define MAXSIZE 100

//两种定义方式
typedef struct LNode *List;
typedef struct LNode L;
struct LNode
{
	ElementType Data[MAXSIZE];
	int Last;

};
L PtrL1;
List PtrL;

//typedef struct LNode
//{
//     ElementType Data[MAXSIZE];
//     int Last;
//}L,*List;
//List PtrL;
//L PtrL1;

//初始化(建立空的顺序表)
List MakeEmpty()
{
	List PtrL;
	PtrL = (List)malloc(sizeof(struct LNode));
	PtrL->Last =-1;
	return PtrL;
}

//查找
int Find(ElementType X,List PtrL)
{
	int i = 0;
	while(i <= PtrL->Last && PtrL->Data[i]!= X) //表的长度Last+1
	{
		i++;
	}
	if(i > PtrL->Last)	return -1;//没找到
	else return i+1;
}
//平均比较次数（n+1）/2：运气好第一次找到，运气差最后一次找到


//插入（第i（1<=i<=n+1）个位置上插入一个值为X的新元素）:使X变为第i个位置
//先移动，后插入：
//插入前将第i个位置（下标为i-1）及其以后的元素后挪（从后向前）
void Insert(ElementType X,int i,List Ptrl)
{
	int j;
	if( PtrL->Last == MAXSIZE-1) //现有长度已经最长最长
	{
		printf("表已满");
		return;
	}
	if(i < 1 || i > PtrL->Last + 2)  //保证插入位置在第1个到第n+1个之间
	{
		printf("插入位置不合法");
		return;
	}
	for(j = PtrL->Last;j>=i-1;j--)
	{
		PtrL->Data[j+1] = PtrL->Data[j];
	}
	PtrL->Data[i-1] = X;
	PtrL->Last++;	//末尾Last后移一位
}
//平均移动次数n/2


//删除
void Delete(int i,List PtrL)
{
	int j;
	if(i < 1 || i > PtrL->Last+1)
	{
		printf("不存在第%d个元素",i);
		return;
	}
	for(j = i;j<PtrL->Last;j++)
	{
		PtrL->Data[j-1] = PtrL->Data[j];	//从前向后移动
	}
	PtrL->Last--;
	return;
}

//按位置查找
int Find1(int i,List PtrL)
{
	if(i < 1 ||i > PtrL->Last + 1)
	{
		printf("不存在第%d个元素",i);
		
	}
	else
		return PtrL->Data[i-1];
}



//平均移动次数(n-1)/2
int main()
{
	PtrL = MakeEmpty();

	//测试插入
	printf("插入\n");
	Insert(5,1,PtrL);
	Insert(4,1,PtrL);
	Insert(3,1,PtrL);
	Insert(2,1,PtrL);
	for(int i = 0;i<=PtrL->Last;i++)
	{
		printf("%d ",PtrL->Data[i]);
	}
	printf("\n*****************\n");

	//测试删除
	printf("删除\n");
	Delete(4,PtrL);
	for(int i = 0;i<=PtrL->Last;i++)
	{
		printf("%d ",PtrL->Data[i]);
	}
	printf("\n*****************\n");

	//测试元素查找
	printf("按元素查找\n");
	printf("4在第%d个位置",Find(4,PtrL));
	printf("\n*****************\n");

	//测试位置查找
	printf("按位置查找\n");
	printf("第2个位置的元素是： %d",Find1(2,PtrL));
	printf("\n*****************\n");

	system("pause");
	return 0;
}

注：此博文为浙大数据结构笔记