线性表

基本操作

Initlist(&L):初始化表
Length(L):求表长
LocateElem(L,e):按值查找操作
GetElem(L,i):按位查找操作
ListInsert(&L,i,e):插入操作
ListDelete(&L,i,&e):删除操作
PrintList(L):输出操作
Empty(L):判空操作
DestroyList(&L):销毁操作

顺序表

静态分配的顺序表存储结构

#define Maxsize 50
typedef struct{
	ElemType data[Maxsize];
	int length;
}SqList;

动态分配的顺序表存储结构

#define InitSize 100
typedef struct{
	ElemType *data;
	int Maxsize,length;
}SeqList;
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);或
L.data=new ElemType[InitSize]；

增加动态数组的长度 

#include <stdlib.h>
#define InitSize 10
typedef struct{
	int *data;
	int Maxsize,length;
}SeqList;

int main(){
	SeqList L;
	IniList(L);
	...
	IncreaseSize(L,5);
	return 0;
}

//初始化一个动态数组
void InitList(SeqList &L){
	L.data=(int*)malloc(InitSize*sizeof(int));
	L.length=0;
	L.MaxSize=InitSize;
}

//增加动态数组的长度
void IncreaseSize(SeqList &L,int len){
	int *p=L.data;
	L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));
	for(int i=0;i<L.length;i++){
		L.data[i]=p[i];//注意访问p指针指向的数组
	}
	L.MaxSize=L.MaxSize+len;
	free (p);
}

静态分配顺序表的初始化

void InitList(SqList &L){
	for(int i=0;i<MaxSize;i++){
		L.data[i]=0;
	}
	L.length=0;
}
或者
void InitList(sqList &L){
    L.length=0;
}

动态分配顺序表的初始化

void InitList(SeqList &L){
	L.data=(ElemType*)malloc(InitSize*sizeof(ElemType));
	L.length=0;
	L.MaxSize=InitSize;
}

插入操作（位置在1～L.length+1之间）

bool ListInsert(SqList &L,int i,ElemType e){
     if(i<1||i>L.length+1)
	       return false;
     if(L.length>=MaxSize)//存储空间满
	       return false;
	 for(int j=L.length;j>=i;j--)
	       L.data[j]=L.data[j-1];//第i个元素后的元素后移
	 L.data[i-1]=e;
	 L.length++;
	 return true;
}

删除操作（位置在1～L.length之间）

bool ListDelete(SqList &L,int i,ElemType &e){
     if(i<1||i>L.length) return false;
	 e=L.data[i-1];
	 for(int j=i;j<L.length;j--)
	        L.data[j-1]=L.data[j];//第i个元素后的元素前移
	 L.length--;
	 return true;
}

按值查找

int LocateElem(SqList L,ElemType e){
     int i;
	 for(i=0;i<L.length;i++)//若为i<InitSize，则初始化要全部初始化为0，防止脏数据影响
	        if(L.data[i]==e)  return i+1;//返回位序i+1
	 return 0;
}

按位查找（静态分配和动态分配一样）

ElemType GetElem(SqList L,int i){
     return L.data[i-1];
}

补充：结构体的比较不能直接用==，应该一个一个元素比较。

链表

单链表

单链表节点结构

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
相当于
struct LNode{
    ElemType data;
	struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;


LNode *L;//表明这是一个指向单链表第一个结点的指针，强调结点
LinkList L;//同上，更强调链表

单链表的初始化及判空（带头结点）

bool InitList(LinkList &L){
	L=(LNode*)malloc(sizeof(LNode));//分配第一个头结点
	if(L==NULL) return false; //内存不足，分配失败
	L->next=NULL;
	return true;
}

bool Empty(LinkList L){
	if(L->next==NULL) return true;
	else return false;
}

单链表的初始化及判空（不带头结点）

bool InitList(LinkList &L){
	L=NULL;
	return true;
}

bool Empty(LinkList L){
	if(L==NULL) return true;
	else return false;
}
或者
bool Empty(LinkList L){
    return (L==NULL):
}

求表长操作（带头结点）

int length(LinkList L){
    int len=0;//计数变量
	LNode* p=L;
	while(p->next!=NULL){
	     p=p->next;
		 len++;
    }
	return len;
}

按序号查找

LNode* GetElem(LinkList L,int i){
     if(i<0) return NULL;
     LNode *p=L;
	 int j=0;//记录当前结点的位序，头结点为第0个结点，方便把结点插在第1个位置
	 while(p!=NULL&&j<i){
	       p=p->next;
		   j++;
	 }
	 return p;//返回指向第i个结点的指针或NULL
}

按值查找

LNode *LocateElem(LinkList L,ElemType e){
	LNode *p=L->next;
	while(p!=NULL&&p->data!=e){
		p=p->next;
	}
	return p;//找到则返回该结点指针，否则返回NULL
}

按位序插入（带头结点）

bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1) return false;
	LNode *p=L;
	int j=0;//头结点是第0个结点
	while(p!=NULL&&j<i-1){//找到第i-1个结点
		p=p->next;
		j++;
	}
	if(p==NULL) return false;//i值不合法
	LNode *s=(LNode*)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

按位序插入（不带头结点）

bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1) return false;
	if(i==1){//仅第1一个结点与带头结点的操作不同
		LNode *s=(LNode*)malloc(sizeof(LNode));
		s->data=e;
		s->next=L;
		L=s;
		return true;
	}
	
	LNode *p=L;
	int j=1;//没有头结点了
	while(p!=NULL&&j<i-1){//找到第i-1个结点
		p=p->next;
		j++;
	}
	if(p==NULL) return false;//i值不合法
	LNode *s=(LNode*)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

指定结点的后插操作 

bool InsertNextNode(LNode *p,ElemType e){//在p结点之后插入元素e
	if(p==NULL) return false;
	LNode *s=(LNode*)malloc(sizeof(LNode));
	if(s==NULL) return false; //内存分配失败
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

指定结点的前插操作

bool InsertPriorNode(LNode *p,ElemType e){
	if(p==NULL) return false;
	LNode *s=(LNode*)malloc(sizeof(LNode));
	if(s==NULL) return false;//内存分配失败
	s->next=p->next;
	p->next=s;
	s->data=p->data;
	p->data=e;
	return true;
}

按位序删除（带头结点）