資料結構代碼

1.線性表

1.順序表

typedef struct{
	int data[maxSize];
	int length;
}Sqlist; 
           

2.單連結清單

typedef struct LNode{
	int data;
	struct DLNode *next;
}LNode;
           

3.雙連結清單

typedef struct DLNode{
	int data;
	struct DLNode *prior;
	struct DLNode *next;
}DLNode;
           

2.棧和隊列

1.順序棧

int stack[maxSize];
int top=-1;
進棧：stack[++top]=x;
出棧：x=stack[top--];
	
           

2.鍊棧

typedef struct LNode{
	int data;
	struct LNode *next;
}lst;
棧空： lst->next==NULL; 
進棧： p->next=lst->next; lst->next=p;
出棧： p=lst->next; x=p->data; lst->next=p->next; free(p);
           

3.順序隊列

typedef struct{
	int data[maxSize];
	int front,reat;
}SeQueue;
進隊：qu.rear=(qu.rear+1)%maxsize; qu.data[qu.rear]=x;
出隊：qu.front=(qu.front+1)%maxsize; x=qu.data[qu.front];
判空：qu.rear==qu.front; 
           

4.鍊隊

typedef	struct QNode{
	int data;
	struct QNode *next;
}QNode;
typedef struct{
	QNode *front;
	QNode *rear;
}LiQueue;
隊空：lqu->rear==NULL 或者 lqu->front==NULL
進隊: lqu->rear->next=p;lqu->rear=p;
出隊：p=lqu->front;lqu->front=p->next;x=p->data;free(p);
           

3.樹與二叉樹

1.二叉連結清單

typedef struct BTNode
{
	char data;
	struct BTNode *lchild;
	stryct BTNode *rchild;
}BTNode;
           

2.先序周遊

void preorder(BTNode *p)
{
	if(p!=NULL)
	{
		visit(p); //1.前
		preorder(p->lchild);
		//2.中
		preorder(p->rchild);
		//3.後
	}
}
           

3.中綴表達式求值問題

int comp(BTNode *p)
{
	int A,B;
	if(p!=NULL)	
	{
		if(p->lchild!=NULL&&p->rchild!=NULL)
		{
			A=comp(p->lchild);
			B=comp(p->rchild);
			return op(A,B,p->data);
		}
		else	return p->data-'0';
	}
	else return 0;
}
           

4.求二叉樹的深度

int getDepth(BTNode *p)
{
	int LD,RD;
	if(!p)	return 0;
	else
	{
		LD=getDepth(p->lchild);
		RD=getDepth(p->rchild);
		return (LD>RD?LD:RD)+1;
	}
}
           

5.先序周遊第K個值

int n=0;
void trave(BTNode *p,int k)
{
	if(p!=NULL)
	{
		++n;
		if(k==n)	{cout<<p->data<<endl; return ;}
		trave(p->lchild,k);
		trave(p->rchild,k);
	}
}	
           

6.層序周遊

void level(BTNode *p)
{
	int front,rear;
	BTNode *que[maxSize];
	front=rear=0;
	BTNode *q;
	if(p!=NULL)
	{
		rear=(rear+1)%maxSize;
		que[rear]=p;
		while(front!=rear)
		{
			front=(front+1)%maxSize;
			q=que[front];
			visit(q);
			if(q->lchild!=NULL)	{rear=(rear+1)%maxSize;que[rear]=q->lchild;}
			if(q->rchild!=NULL)	{rear=(rear+1)%maxSize;que[rear]=q->rchild;}
		}
	}
}
           

7.先序非遞歸

void preorder(BTNode *bt)
{
	if(!bt)
	{
		BTNode *Stack[maxSize];
		int top=-1;
		BTNode *p;
		Stack[++top]=bt;
		while(top!=-1)
		{
			p=Stack[top--];
			visit(p);
			if(p->rchild!=NULL)	Stack[++top]=p->rchild;
			if(p->lchild!=NULL)	Stack[++top]=p->lchild;
		}
	}

           

8.中序非遞歸

1.根結點入棧

2.循環執行，若棧頂左存在，則左入棧；若不存在則輸出棧頂并檢查右，如右存在則右入棧

3.棧空時結束

9.後序非遞歸

void preorder(BTNode *bt)
{
	if(!bt)
	{
		BTNode *Stack1[maxSize]，*Stack2[maxSize];
		int top1=-1,top2=-1;
		BTNode *p;
		Stack1[++top]=bt;
		while(top1!=-1)
		{
			p=Stack1[top--];
			Stack2[++top2];
			visit(p);
			if(p->lchild!=NULL)	Stack1[++top]=p->lchild;
			if(p->rchild!=NULL)	Stack1[++top]=p->rchild;
		}
	}
	while(top2!=-1)
	{
		p=Stack[top2--];
		visit(p);
	}
}
           

4.圖

typedef struct
{
	int edges[maxSize][maxSize];
	int n,e;
	VertexType vex[maxSize];
}MGraph;