数据结构代码归纳

线性表

线性表的顺序表示

定义与初始化

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 ; 

 二叉树遍历

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