[数据结构与算法]数据结构（王道）-顺序表，单链表 （基本代码）

/*顺序表用一串连续的存储单元存储数据元素。*/

/*顺序表的实现——静态分配*/
#define Maxsize 50
typedef struct{
	ElemType data[Maxsize]; //用数组来表示顺序表的元素,ELemType来表示数据元素的类型                                                                                             
	int length;				//当前长度
}SqList;					//静态分配顺序表
//顺序表的实现——动态分配
typedef struct{
	ElemType *data;			//用指针来表示顺序表的元素
	int Maxsize;			//最大容量
	int length;				//当前长度
}SeqList;					//动态分配顺序表

//*基本操作*//


//*插入*//
//*在顺序表L的第i个位置插入e*//
/*L.data[i-1]=e,下标从i-1到length-1的元素依次后移*/
/*i要有范围，[1,length+1],length要有范围，小于Maxsize*/
bool SqList_Insert(SqList &L,int i,ElemType e){
	if (i<1||i>length+1)	return false;
	if (L.length>=Maxsize)	return false;
	for(int j=length;j>=i;j--)//j从length到i
		L.data[j+1]=L.data[j];
	L.data[i-1]=e;//更新L中的数据
	L.length++;
	return true;
}


//*删除*/
/*e=L.data[i-1],下标从i到length-1的元素依次前移*/
/*i要有范围，[1,length]*/
bool SqList_delete(SqList &L,int i,ELemType e){//删除L中的第i个元素，用e返回
	if (i<1||i>length)	return false;
	e=L.data[i-1]; //e要提前表示出来
	for(int j=i;j<length;j++)//j从i到length-1
		L.data[j-1]=L.data[j];
	L.length--;
	return true;
}


//*按位查找*//
bool SqList_GetELem(SqList L,int i){
	return L.data[i-1];}

//*按值查找*//
int SqList_LocateElem(SqList L,ELemType e){
	for(int i=0;i<L.length;i++)//下标从0到length-1，比较是否相等
		if (L.data[i]==e) return i+1;
	return 0;
}

//*链表*//
/*单链表*/

/*定义*/
typedef struct LNode{
	ElemType data;//数据
	struct LNode *next;//指针，指向下一个数据
}LNode,*LinkList;//LNode *L 强调节点，LinkList L 强调单链表

/*带头节点的单链表初始化*/
bool InitList(LinkList &L){
	L=(LNode*)malloc(sizeof(LNode));//分配一个大小为一个LNode数据结构的空间，强制转换为LNode结构
									/*分配一个头结点*/
	if(L==NULL) return false;//内存不足
	L->next=NULL;//头指针之后没有结点
	return ture;
}

/*按位查找结点*/
/*在单链表L中，查找第i个结点（带头结点）*/
LNode *GetElem(LinkList L,int i){//由于查找的是结点,用LNode*定义
	if(i<0) return NULL;
	int j=0;
	LNode *p;
	p=L;
	while(p!=NULL&&j<i){
		p=p->next;
		j++;}
	return p;
}

/*按值查找结点*/
/*在带头结点的单链表L中，查找数据=e的结点*/
LNode *LocateElem(LinkList L,ELemType e){
	LNode *p;
	p=L->next;
	while(p!=NULL&&p->data!=e){
		p=p->next;}
	return p;
}

/*插入*/

/*指定结点的后插操作*/
/*p所指的结点后面插一个结点*/
bool InsertNextNode(LNode*p,Elemtype e){
	if(p==NULL) return false;//保证p所指不为空
	/*新分配一个新结点，来存e*/
	LNode *s=(LNode*)malloc(sizeof(LNode));//
	if(s==NULL) return false;//内存可能满了

	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}


/*指定结点的前插操作*/
/*p所指的结点前面插一个结点*/
/*将新分配的结点s后插到p结点上，p的数据放入s，e的数据放入p*/
bool InsertPriorNode(LNode*p,Elemtype e){
	if(p==NULL) return false;//保证p所指不为空
	/*新分配一个新结点，来存e*/
	LNode *s=(LNode*)malloc(sizeof(LNode));//p
	if(s==NULL) return false;

	s->next=p->next;
	p->next=s;

	s->data=p->data;
	p->data=e;
	return true;
}

/*按位序第i个位置上插入e*/
/*找到第i-1个元素，新结点插入其后*/
/*头结点所在位置视为第0个位置*/
bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1) return false;
	LNode *p;
	p=GetELem(L,i-1);/*找到L中第i-1个结点*/

	InsertNextNode(p,e);/*p所指的结点后面插一个结点*/
}

//*删除*//

/*按位序删除*/
bool DeleteLocate(LinkList &L,int i,ElemType e){
	if(i<1) return false;
	LNode *p;
	p=GetElem(L,i-1);//找到第i-1位

	/*p结点，以及之后的结点不能为空*/
	if(p==NULL||p->next==NULL) return false;
	LNode *q=p->next;//新建一个结点来删除
	p->next=q->next;
	e=q->data;
	free(q);
	return true;
}

/*指定结点删除*/
bool DeleteNode(LNode*p){
	if(p==NULL) return false;
	LNode *q=p->next;
	p->next=q->next;
	p->data=q->data;
	free(q);
	return true;
}