线性表
线性表的顺序表示
定义与初始化
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 ; 二叉树遍历
二叉树三种遍历方式以及线索二叉树
