線性表

順序表的定義

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

順序表插入

在下標為i的位置插入元素e：

bool ListInsert(SqList &L, int i, ElemType e){
	if(i<0||i>L.length||L.length==MaxSize)			//i取0到length
		return false;
	for(int j=L.length-1; j>=i; --j)
		L.data[j+1]=L.data[j];			//從后往前，逐個將元素后移一個位置
	L.data[i]=e;
	++(L.length);
	return true;
}

順序表刪除

刪除下標為i的元素，并返回元素值e：

bool ListDelete(SqList &L, int i, ElemType &e){
	if(i<0||i>L.length-1)
		return false;
	e=L.data[i];
	for(int j=i; j<L.length-1; ++j)
		L.data[j]=L.data[j+1];
	--(L.length);
	return true;
}

順序表按值查找

查找第一個等于e的元素，并返回其下標：

int LocateElem(SqList L, ElemType e){
	int i;
	for(i=0; i<L.length; ++i){
		if(L.data[i]==e)
			return i;
	}
	return 0;
}

元素逆置

設計一個高效算法，將順序表所有元素逆置，要求算法的空間復雜度為O(1)：

void Reverse(SqList &L,){
	ElemType temp;		//定義一個臨時變量
	for(int i=0,j=L.length-1; i<j; ++i,--j){
		temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
}

合并順序表

將兩個有序順序表合并成新的有序順序表，并由函數返回結果順序表：

bool Merge(SqList A, SqList B, SqList &C){
	if(A.length+B.length>C.MaxSize)
		return false;
	int i=0,j=0,k=0;
	while(i<A.length && j<B.length){
		if(A.data[i]<=B.data[j]){		//若A中元素值小于B中元素值，則A值入C
			C.data[k]=A.data[i];
			++k;
			++i;
		}else{
			C.data[k]=B.data[j];
			++k;
			++j;
		}
	}
	while(i<A.length){				//若A中有剩余
			C.data[k]=A.data[i];
			++k;
			++i;
	}
	while(j<B.length){				//若A中有剩余
		C.data[k]=B.data[j];
			++k;
			++j;
	}
	C.length=k;
	return true;
}

單鏈表定義

typedef struct LNode{			//因為結構體中包含了LNode，所以定義結構體時struct后面要加LNode
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;

頭插法

頭插法建立單鏈表(天勤)

void List_HeadInsert(LNode *&C, int a[], int n){
	LNode *s;				//s用來指向新申請的結點
	int i;
	C=(LNode *)malloc(sizeof(LNode));	//申請C的頭結點空間
	C->next=NULL;
	for(i=0; i<n; ++i){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=a[i];
		s->next=C->next;	//新插入的s結點的next指向頭結點C的next
		C->next=s;			//頭結點C的next指向新建的s結點
	}
	r->next=NULL;
}

尾插法

尾插法建立單鏈表(天勤)

void List_TailInsert(LNode *&C, int a[], int n){
	LNode *s, *r;
	int i;
	C=(LNode *)malloc(sizeof(LNode));
	C->next=NULL;
	r=C;
	for(i=0; i<n; ++i){
		s=(LNode *)malloc(sizeof(LNode);
		s->data=a[i];
		r->next=s;		//r所在的next指向新建的s結點
		r=r->next;
	}
	r->next=NULL;
}

合并鏈表

A，B是兩個帶頭結點的單鏈表，其中元素遞增有序，設計一個算法，將A，B歸并成一個按元素值非遞減有序的鏈表C，C由A和B中的結點組成。

void Merge(LNode *A, LNode *B, LNode *&C){
	LNode *p=A->next;
	LNode *q=B->next;
	LNode *r;			//r始終指向C的終端結點
	C=A;
	C->next=NULL;
	free(B);
	r=C;
	while(p!=NULL && q!=NULL){
		if(p->data<=q->data){
			r->next=p;
			p=p->next;
			r=r->next;
		}
		else{
			r->next=q;
			q=q->next;
			r=r->next;
		}
	}
	r->next=NULL;
	if(p!=NULL)			//將剩余結點鏈接在C的尾部
		r->next=p;
	if(q!=NULL)
		r->next=q;
}

棧與隊列

循環隊列：

?隊空狀態：qu.rear==qu.front;

?隊滿狀態：(qu.rear+1)%maxSize==qu.front;

遞歸過程或者函數調用時，處理參數及返回地址要用棧。

串是一種特殊的線性表，其數據元素是一個字符。

樹與二叉樹

二叉樹鏈式存儲結構定義

typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

二叉樹遍歷

先序遍歷遞歸(根左右)

void PreOrder(BiTree T){
	if(T!=NULL){
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

中序遍歷遞歸(左根右)

void InOrder(BiTree T){
	if(T!=NULL){
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}

后序遍歷遞歸(左右根)

void PostOrder(BiTree T){
	if(T!=NULL){
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

先序遍歷遞歸(根左右)

void PreOrder(BiTree T){
	InitStack(S);
	BiTree T;
	while(p||!IsEmpty(S)){		//棧不空或p不空時循環
		if(p){					//一路向左
			visit(p);
			Push(S,p);
			p=p->lchild;
		}
		else{
			Pop(S,p);
			p=p->rchild;
		}
	}
}

中序遍歷非遞歸(左根右)

void InOrder(BiTree T){
	InitStack(S);
	BiTree p=T;
	while(p||!IsEmpty(S)){		//棧不空或p不空時循環
		if(p){
			Push(S,p);
			p=p->lchild;
		}
		else{
			Pop(S,p);
			visit(p);
			p=p->rchild;
		}
	}
}

后序遍歷非遞歸(左右根)

void PostOrder(BiTree){
	InitStack(S);
	p=T;
	r=NULL;
	while(p||!IsEmpty(S)){
		if(p){								//走到最左邊
			Posh(S,p);
			p=p->lchild;
		}
		else{								//向右
			GetTop(S,p);					//讀棧頂結點（非出棧）
			if(p->rchild && p->rchild!=r){	//若左子樹存在且未被訪問過
				p=p->rchild;				//轉向右
				Push(S,p);					//壓棧
				p=p->lchild;				//再走到最左
			}
			else{							//否則，彈出結點并訪問
				Pop(S,p);					//出棧
				visit(p->data);
				r=p;						//記錄最近訪問過的結點
				p=NULL;
			}
		}
	}
}

層次遍歷

void LevelOrder(BiTree T){
	InitQueue(Q);		//初始化輔助隊列
	BiTree T;
	EnQueue(Q,T);		//根節點入隊
	while(!IsEmpty(Q)){
		DeQueue(p);		//隊頭結點出隊
		visit(p);
		if(p->lchild!=NULL)		//若左子樹不空，左子樹根節點入隊
			EnQueue(Q,p->lchild);
		if(p->rchild!=NULL)
			EnQueue(Q,p->rchild);
	}
}

圖

基本概念

有向完全圖：若有向圖有n個頂點，則最多有n(n-1)條邊，將具有n(n-1)條邊的有向圖成為有向完全圖。

無向完全圖：若無向圖有n個結點，則最多有n(n-1)/2條邊，將具有n(n-1)/2條邊的有向圖成為無向完全圖。

連通圖：如果圖中任意兩個頂點都連通，則稱該圖為連通圖;否則，圖中的極大連通子圖稱為連通分量。

強連通圖：在有向圖中，從vi到vj和從vj到vi都有路徑，則稱該圖為強連通圖;否則將其中的極大強連通子圖稱為強連通分量。

圖的定義

鄰接矩陣定義

#define MaxVertexNum 100		//頂點數目的最大值
typedef char VertexType;		//頂點的數據類型
typedef int EdgeType;			//帶權圖中邊上權值的數據類型
typedef struct{
	VertexType Vex[MaxVertexMum];	//頂點表
	EdgeType Edge[MaxVertexMum][MaxVertexNum];	//鄰接矩陣，邊表
	int vexnum, arcnum;			//圖當前的定點數和邊數
}

鄰接表存儲結構定義

#define MaxVertexNum 100		//圖中頂點數的最大值
typedef struct ArcNode{			//邊表結點
	int adjvex;					//該弧指向的頂點的位置
	struct ArcNode *next;		//指向下一條弧的指針
}ArcNode;
typedef struct VNode{			//頂點表結點
	VertexType data;			//頂點信息
	ArcNode *first;				//指向第一條依附該頂點的弧的指針
}VNode, AdjList[MaxVertexNum];
typedef struct{					
	AdjList vertices;			//鄰接表
	int vexnum; arcnum;			//圖的頂點數和弧數
}ALGraph;						//ALGraph是以鄰接表存儲的圖類型

圖的遍歷

圖的廣度優先遍歷

bool visited[MAX_VERTEX_NUM];	//訪問標記數組
void BFSTraverse(Graph G){		//對圖G進行廣度優先遍歷
	for(i=0; i<G.vexnum; ++i)	
		visited[i]=FALSE;		//訪問標記數組初始化
	InitQueue(Q);				//初始化輔助隊列Q
	for(i=0; i<G.vexnum; ++i)	//從0號頂點開始遍歷
		if(!visited[i])			//對每個連通分量調用一次BFS
			BFS(G,i);			//vi未訪問過，從vi開始BFS
}
void BFS(Graph G, int v){		//從頂點v出發，廣度優先遍歷圖G
	visit(v);	
	visited[v]=TRUE;			//對v做以訪問標記
	EnQueue(Q,v);				//頂點v入隊Q
	while(!isEmpty(Q)){
		DeQueue(Q,v);
		for(w=FirstNeighbor(G,v); w>=0; w=NexNeighbor(G,v,w)){	//檢測v所有鄰接點
			if(!visited[w]){	//w為v的尚未訪問的鄰接頂點
				visit(w);
				visited[w]=TRUE;
				EnQueue(Q,w);
			}
		}
	}
}

圖的深度優先遍歷

bool visited[MAX_VERTEX_NUM];	//建立訪問標記數組
void DFSTraverse(Graph G){		//對圖G進行深度優先遍歷
	for(v=0; v<G.vexnum; ++v)	//將所有位置都置false
		visited[v]=FALSE;
	for(v=0; v<G.vexnum; ++v)	
		if(!visited[v])			//只要未被訪問過就執行DFS
			DFS(G,v);
}
void DFS(Graph G, int v){		//從頂點v出發，深度優先遍歷圖G
	visit(v);
	visited[v]=TRUE;
	for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w))
		if(!visited[w]){		//若w未被訪問，則執行DFS
			DFS(G,w);
		}
}

拓撲排序

拓撲排序算法實現

bool TopologicalSort(Graph G){
	InitStack(S);				//初始化棧，存儲入度為0的頂點
	for(int i=0; i<G; ++i)
		if(indegree[i]==0)		//將所有入度為0的頂點進棧
			Push(S,i);
	int count=0;				//記錄當前已經輸出的頂點數
	while(!IsEmpty(S)){			//棧不空則存在入度為0的頂帶你
		Pop(S,i);
		print[count++]=i;		//輸出頂點i
		for(p=G.vertices[i].firstarc; p; p=p->nextarc){
		//將所有i指向的頂點的入度減1，并且將入度為0的頂點壓入棧S
			v=p->adjvex;
			if(!(--indegree[v]))	//入度為0則入棧
				Push(S,v);
		}
	}
	if(count<G.vexnum)	//排序失敗，有向圖中有回路
		return false;
	else
		return true;	//排序成功
}

查找

順序查找

typedef struct{			//查找表的數據結構
	ElemType *elem;		//元素存儲空間基址，建表時按實際長度分配，0號單元留空
	int TableLen;		//表的長度
}SSTable;
int Search_Seq(SSTable ST, ElemType key){
	ST.elem[0]=key;		//“哨兵”
	for(i=ST.TableLen; ST.elem[i]!=key; --i);	//從后往前找
	return i;			//若表中不存在key，將查找到i為0時退出for循環
}

折半查找

int Binary_Search(SeqList L, ElemType key){
	int low=0, high=L.TableLen-1, mid;
	while(low<=high){
		mid=(low+high)/2;
		if(L.elem[mid]==key)
			return mid;
		else if(L.elem[mid]>key)
			high=mid-1;
		else
			low=mid+1;
	}
	return -1;
}

排序

冒泡排序

void BubbleSort(ElemType A[], int n){
	for(i=0; i<n-1; ++i){
		flag=false;				//表示本趟冒泡是否發生交換的標志
		for(j=n-1; j>i; --j){	//一趟冒泡過程
			if(A[j-1]>A[j]){	//若為逆序
				swap(A[j-1],A[j]);	//交換
				flag=true;
			}
		}
		if(flag==false)
			return 0;			//本趟遍歷后沒有發生交換，說明表已有序
	}
}

快速排序

void QuickSort(ElemType A[], int low, int high){
	if(low<high){									//遞歸跳出的條件
	//Partition()就是劃分操作，將表A[low···high]劃分為滿足上述條件的兩個子表
		int pivotpos=Partition(A,low,high);	//劃分
		QuickSort(A,low,pivotpos-1);		//依次對兩個子表進行遞歸排序
		QuickSort(A,pivotpos-1,high);
	}
}
int Partition(ElemType A[], int low, int high){		//一趟劃分
	ElemType pivot=A[low];	//將表中第一個元素設為樞軸，對表進行劃分
	while(low<high){		//循環跳出條件
		while(low<high && A[high]>=pivot)
			--high;
		A[low]=A[high];		//將比樞軸小的元素移動到左端
		while(low<high && A[low]<=pivot)
			++low;
		A[high]=A[low];		//將比樞軸大的元素移動到右端

	}
	A[low]=pivot;			//樞軸元素存放到最終位置
	return low;				//返回存放樞軸的最終位置
}

簡單選擇排序

void SelectSort(ElemType A[], int n){
	for(i=0; i<n-1; ++i){
		min=i;							//記錄最小元素位置
		for(j=i+1; j<n; ++j)			//在A[i...n-1]中選擇最小的元素
			if(A[j]<A[min])				//更新最小元素位置
				min=j;
		if(min!=i)						//封裝的swap()函數共移動元素3次
			swap(A[i],A[min]);
	}
}

如果想了解更多相關知識，大家可以關注一下動力節點的數據結構教程，里面有更多內容可以學習，希望對大家有所幫助。