数据结构代码归纳

线性表

线性表的顺序表示

定义与初始化

typedef struct SqList{
	ElemType data[MaxSize];
	//ElemType *data  开动态数组 
	int length;
}Sqlist;
void InitList(SqList &L){
	L.length=0;//若静态数组
	//若动态数组 
	//L.data=(ElemType*)malloc(sizeof(ElemType)*MaxSize); 
} 

插入操作

在顺序表的第i（1<=i<=L.length+1）个位置插入元素 ,data的下标范围是从0开始。

bool ListInsert(SqList &L, int i, ElemType m){
	if(i<1||i>L.length)return false;//i超出数组范围 
	if(L.length>=MaxSize)return false;//length超出最大长度
	for(int j=L.length; j>=i; j--){
		L.data[i]=L.data[i-1];//将第i个及以后元素往后移动
	} 
	L.data[i-1]=m;
	L.length++;
    return true;
} 

删除操作

bool ListInsert(SqList &L, int i, ElemType &m){
	if(i<1||i>L.length)return false;//i超出数组范围 
	m=L.data[i-1];
	for(int j=i; j<L.length; j++){
		L.data[j-1]=L.data[j];//删除之后数组往前移 
	}
	L.length--;
	return true;
} 

线性表链式存储

 链头指能通过指针访问到链表所有结点的位置，链尾的next指针为空

定义与初始化 

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;
//带头结点 
bool InitList(LinkList &L){
	L=(LNode *)malloc(sizeof(LNode));//创建头结点 
	L->next=NULL;
	return true;
}
//不带头结点 
bool InitList(LinkList &L){
	L=NULL;
	return true;
}

插入结点

//插入结点操作
bool ListInsert(LinkList &L, int i, ElemType m){
	LNode *p=L;
	int j=1;
	//找到第i个结点 ，j=1表示p在第一个元素 
	while(p!=NULL&&j<=i-1){
		p=p->next;
		j++;
	}
	if(p==NULL)return false;
	LNode *s=(LNode*)malloc(sizeof(LNode));
	s->data=m;
	s->next=p->next;
	p->next=s;
	return true; 
}

删除结点

与插入节点类似

//删除结点
bool ListDelet(LinkList &L, int i, ElemType &m){
	LNode *p=L;
	int j=1;
	while(p!=NULL&&j<=i-1){
		p=p->next;
		j++;
	}
	if(p==NULL||p->next==NULL)return false;
	m=p->next->data;
	LNode *s=p->next;
	m=s->data;
	p->next=s->next;
	free(s);
	return true;
} 

头插法建立单链表/链表逆置

//头插法/链表逆置 
LinkList List_HeadInsert(LinkList &L){
	LNode *s;
	int x;
	L=(LNode*)malloc(sizeof(LNode));//带头结点的初始化 
	L->next=NULL;
	cin>>x;
	while(x!=99999){
		//每次添加结点必须新申请空间 
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		s->next=L->next;//L是头结点 
		L->next=s;
		cin>>x;
	}
	return L; 
}

尾插法

设置一个指针指向链表尾巴，每次从尾巴插入，得到的链表是正序

双链表

//双链表定义初始化
typedef struct DLNode{
	ElemType data;
	DNode *prior, *next;
}DNode, *DLinkList; 
bool InitDLinkList(DLinkList &L){
	L=(DNode *)malloc(sizeof(DNode));
	if(L==NULL)return false;//如果开空间失败，可有可无 
	L->next=NULL;//前后指针都设置为空
	L->prior=NULL;
	return true;
}

定义与初始化

//双链表定义初始化
typedef struct DNode{
	ElemType data;
	DNode *prior, *next;
}DNode, *DLinkList; 
bool InitDLinkList(DLinkList &L){
	L=(DNode *)malloc(sizeof(DNode));
	if(L==NULL)return false;//如果开空间失败，可有可无 
	L->prior=NULL;
	L->next=NULL;
	return true;
}

p结点后插入s

//双链表插入操作  
bool InsertDList(DNode *p, DNode *s){
	if(p==NULL||s==NULL)return false; 
	s->next=p->next;
	if(p->next!=NULL){//如果p有后继结点 
		p->next->prior=s;	
	}
	s->prior=p;
	p->next=s; 
	return true;
}

循环单链表

定义

//循环单链表 
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;
//带头结点 
bool InitList(LinkList &L){
	L=(LNode *)malloc(sizeof(LNode));//创建头结点 
	L->next=L;//把链尾结点next指针指向链头结点 
	return true;
}

判断为空条件:L->next==L

循环双链表

定义与初始化

 typedef struct DNode{
	ElemType data;
	DNode *prior, *next;
}DNode, *DLinkList; 
bool InitDLinkList(DLinkList &L){
	L=(DNode *)malloc(sizeof(DNode));
	if(L==NULL)return false;//如果开空间失败，可有可无 
	L->prior=L;//头结点的prior指向头结点 
	L->next=L;头结点的next指向头结点 
	return true;
}

删除结点

//可以无顾虑删除，不可能有空的结点
bool InsertDList(DNode *p, DNode *s){
	s->next=p->next;
	p->next->prior=s;	
	s->prior=p;
	p->next=s; 
	return true;
}

 栈

定义以及基本操作

栈判断空是判断top==-1，满是top==MaxSize-1;

共享栈是一个数组空间分为两个栈，判断左边栈空：top1==-1,右边栈空：top2==MaxSize.判断栈满条件top1+1==top2

//栈
#define MaxSize 100
typedef struct{
	ElemType data[MaxSize];
	int top;//栈顶指针 
}SqStack;
int main()
{
	SqStack s;
	s.top=-1;//初始化，栈顶指针为-1：判断栈是否为空 
	//进栈
	ElemType x;
	s.data[++s.top]=x; 
	//出栈
	s.top--;//前提top!=-1; 
    return 0;
}

队列

队列的顺序存储

//队列
typedef struct{
	ElemType data[MaxSize];
	int front , rear;
}SqQueue;

循环队列 

以牺牲一个结点判断队满队空：

头指针指向队列第一个元素，尾指针为空，指向队尾指针的下一个元素，新加入结点的位置

队满条件：(Q.rear+1)%MaxSize==Q.front

队空条件：Q.rear==Q.front

队内元素个数：（Q.rear-Q.front+MaxSize）% MaxSize

初始化

void InitQueue(SqQueue &Q){
	Q.front=Q.rear=0;
} 

入队

bool EnQueue(SqQueue &Q, ElemType m){
	if((Q.rear+1)%MaxSize==Q.front)return false;//判断是否队满 
	Q.data[Q.rear]=m;
	Q.rear=(Q.rear+1)%MaxSize;//尾指针加一要取模 
	return true;
}

出队 

//出队
bool DeQueue(SqQueue &Q, ElemType &m){
	if(Q.front==Q.rear)return false;//队空
	m=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize; 
	return true;
} 

队列的链式存储

定义

//链式存储定义
typedef struct LinkNode{
	ElemType data;
	struct LinkNode *next;
}LinkNode;
typedef struct {
	LinkNode *front, *rear;
}LinkQueue;

带头结点的链式存储，front指向不存储数据的头结点，rear指向队尾指针

入队

//入队
bool EnQueue(LinkQueue &Q, ElemType m){
	LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
	p->data=m;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
} 

出队

//出队
bool DeQueue(LinkQueue &Q, ElemType &m){
	if(Q.front==Q.rear)return false;//空队
	LinkNode *p=Q.front->next;
	m=p->data;
	Q.front->next=p->next;//删除 
	if(p==Q.rear)Q.rear=Q.front;//如果只有一个结点，删除后为空 
	free(p);
	return true; 
}

树与二叉树 

二叉树的定义：

树的顺序存储

跟适合完全二叉树

 一定要把结点编号与完全二叉树结合起来

树的链式存储：

typedef struct ThreadNode{
	Elemtype data;
	struct ThreadNode* lchild, *rchild; 
	int ltag, rtag;//线索标记 
}ThreaNode, *ThreadTree ; 

 二叉树遍历

二叉树三种遍历方式以及线索二叉树