考研数据结构程序题常见代码【C语言实现】

考研院校要求C语言实现数据结构，可前期做数据结构都是用Java实现，因此对于C不那么熟悉，花了一些时间重新捡起来C的语法，程序题通常不会考太过复杂的算法，因此自己将辅导书上一些母题进行了实现，其中层序遍历部分需要用到队列，查了一下发现C语言没有现成的头文件调入使用，因此这部分用了C++的语法，除此之外皆为C的语法，现整理如下

#include
#include
typedef struct Node{
	int num;
	struct Node *next;
}Node;
//创建一个数值为i的节点并插入在节点p后边 
void insert(Node *p,int i){
	//指针指向Node这么大的空间 
	Node *temp=(Node *)malloc(sizeof(Node));
	temp->next=NULL;
	temp->num=i;
	p->next=temp;
}
int main(){
	Node *node=(Node *)malloc(sizeof(Node));
	node->num=1;
	node->next=NULL;
	insert(node,10);
	while(node!=NULL){
		printf("%d ",node->num);
		node=node->next;
	}
}

#include
#include
typedef struct Node{
	int val;
	struct Node *next;
}Node;
void InsertNode(Node *head,Node *p);//头插法 
void InsertNodeBehind(Node *head,Node *p);//尾插法 
void reverseList(Node *head,Node *temp);//链表反转 (递归实现)
int main(){
	Node *head=(Node *)malloc(sizeof(Node)); 
	head->val=-1;
	head->next=NULL;//初始化很重要 
	for(int i=1;i<=10;i++){
		Node *temp=(Node *)malloc(sizeof(Node)); 
		temp->val=i;
		temp->next=NULL;
		InsertNode(head,temp);
	}
	reverseList(head,head->next);
	head=head->next;
	while(head!=NULL){
		printf("%d ",head->val);
		head=head->next;	
	}
}

void InsertNode(Node *head,Node *p){
	p->next=head->next;
	head->next=p;
}

void InsertNodeBehind(Node *head,Node *p){
	Node *temp=head;
	while(temp->next!=NULL){
		temp=temp->next;
	}
	temp->next=p;
}

void reverseList(Node *head,Node *temp){
	if(temp->next==NULL){
		head->next=temp;
		return;
	}
	else if(temp->next!=NULL){
		reverseList(head,temp->next);
		temp->next->next=temp;
		temp->next=NULL;
	}
}

#include
#include
#include //C语言实现兼容队列过于冗长复杂，不是树部分重点，因此队列部分用了C++的头部文件 
using namespace std; //除队列部分是C++外，其余部分皆为C的语法，笔试时关于Node队列可用文字描述，不影响做题 
typedef struct Node{
	int val;
	struct Node *left;
	struct Node *right;
}Node;
void initial(); //初始化 
void prePrint(Node *); //前序遍历 
void midPrint(Node *); //中序遍历 
void lastPrint(Node *); //后序遍历 
void rowPrint(Node *); //层序遍历 
int getHeight(Node *,int); //树的高度 
Node *root,*node1,*node2,*node3,*node4,*node5,*node6,*node7;
queue q; //创建Node型队列 
int main(){
	initial();
	rowPrint(root);
//	prePrint(root);
	printf("n%d",getHeight(root,0));
}

int getHeight(Node *root,int height){
	height++;
	int a=0,b=0;
	if(root->left!=NULL){
		a=getHeight(root->left,height);
	}
	if(root->right!=NULL){
		b=getHeight(root->right,height);
	}
	return height>a&&height>b?height:a>b?a:b;
}

void rowPrint(Node *root){
	q.push(root);
	while(!q.empty()){
		int n=q.size();
		for(int i=0;ileft!=NULL){
				q.push(temp->left);
			}
			if(temp->right!=NULL){
				q.push(temp->right);
			}
			printf("%d ",temp->val); 
			q.pop();
		}
	}
}

void prePrint(Node *root){
	printf("%d ",root->val);
	if(root->left!=NULL){
		prePrint(root->left);
	}
	if(root->right!=NULL){
		prePrint(root->right);
	}
}

void midPrint(Node *root){
	if(root->left!=NULL){
		midPrint(root->left);
	}
	printf("%d ",root->val);
	if(root->right!=NULL){
		midPrint(root->right);
	}
}

void lastPrint(Node *root){
	if(root->left!=NULL){
		lastPrint(root->left);
	}
	if(root->right!=NULL){
		lastPrint(root->right);
	}
	printf("%d ",root->val);
}

void initial(){
	root=(Node *)malloc(sizeof(Node));
	root->val=0;
	node1=(Node *)malloc(sizeof(Node));
	node1->val=1;
	node2=(Node *)malloc(sizeof(Node));
	node2->val=2;
	node3=(Node *)malloc(sizeof(Node));
	node3->val=3;
	node4=(Node *)malloc(sizeof(Node));
	node4->val=4;
	node5=(Node *)malloc(sizeof(Node));
	node5->val=5;
	node6=(Node *)malloc(sizeof(Node));
	node6->val=6;
	node7=(Node *)malloc(sizeof(Node));
	node7->val=7;
	
	root->left=node1;
	root->right=node2;
	node1->left=node3;
	node1->right=node4;
	node2->left=node5;
	node2->right=node6;
	node3->left=node7;
	node3->right=NULL;
	node4->left=NULL;
	node4->right=NULL;
	node5->left=NULL;
	node5->right=NULL;
	node6->left=NULL;
	node6->right=NULL;
	node7->left=NULL;
	node7->right=NULL;
} 

#include
#include
typedef struct Node{
	int val;
	struct Node *left;
	struct Node *right;
}Node;
Node *root,*node1,*node2,*node3,*node5,*node6,*node7;
void midPrint(Node *root);//中序遍历 (顺序输出)
void insertNode(Node *root,Node *temp);
void initial();
Node* searchByVal(Node *root,int val);
Node* searchByVal2(Node *root,int val);
int main(){
	initial();//初始化 
	insertNode(root,node2);
	insertNode(root,node6);
	insertNode(root,node1);
	insertNode(root,node3);
	insertNode(root,node5);
	insertNode(root,node7);
	printf("中序输出二叉排序树：");
	midPrint(root);
	Node *temp=searchByVal(root,10);
	printf("n%d",temp==NULL?-1:temp->val);
}

//递归查找某个值对应的节点 
Node* searchByVal(Node *root,int val){
	if(root->val==val){
		return root;
	}else if(root->valright==NULL){
			return NULL;
		}
		return searchByVal(root->right,val);
	}else{
		if(root->left==NULL){
			return NULL;
		}
		return searchByVal(root->left,val);
	}
}

//非递归查找 
Node* searchByVal2(Node *root,int val){
	while(root!=NULL){
	if(root->val==val){
		return root;
	}else if(root->valright;
	}else{
		root=root->left;
	}
	}
	return NULL;
}
 
//插入节点 
void insertNode(Node *root,Node *temp){
	if(temp->valval){
		if(root->left!=NULL){
			insertNode(root->left,temp);
		}else{
			root->left=temp;
		}
	}else{
		if(root->right!=NULL){
			insertNode(root->right,temp);
		}else{
			root->right=temp;
		}
	}
} 
void initial(){
	root=(Node *)malloc(sizeof(Node));
	root->val=4;
	root->left=NULL;
	root->right=NULL;
	
	node1=(Node *)malloc(sizeof(Node));
	node1->val=1;
	node2=(Node *)malloc(sizeof(Node));
	node2->val=2;
	node3=(Node *)malloc(sizeof(Node));
	node3->val=3;
	node5=(Node *)malloc(sizeof(Node));
	node5->val=5;
	node6=(Node *)malloc(sizeof(Node));
	node6->val=6;
	node7=(Node *)malloc(sizeof(Node));
	node7->val=7;
	node1->left=NULL;
	node1->right=NULL;
	node2->left=NULL;
	node2->right=NULL;
	node3->left=NULL;
	node3->right=NULL;
	node5->left=NULL;
	node5->right=NULL;
	node6->left=NULL;
	node6->right=NULL;
	node7->left=NULL;
	node7->right=NULL;
} 

void midPrint(Node *root){
	if(root->left!=NULL){
		midPrint(root->left);
	}
	printf("%d ",root->val);
	if(root->right!=NULL){
		midPrint(root->right);
	}
}

#include
#include
#include
using namespace std;
typedef struct Node{
	int val;
	int in; //在数组中哪个下标 
	struct Node *left;
	struct Node *right;
}Node;
queue list; //Node队列部分借用了C++语法 
int rChild (int,int,int[]);//返回当前节点右孩子 
int lChild (int,int,int[]);//返回当前节点左孩子 
int Parent(int);//返回当前节点父节点
void prePrint(int,int [],int);//顺序二叉树的先序遍历 
void prePrint2(Node *); //链式二叉树先序遍历 
void BFS(int,int[],int);  //顺序二叉树的广度遍历直接for遍历数组即可，省略实现
Node *indexToNode(int,int[]);//创建一个节点
Node *arrToList(int[],int);  //将顺序存储二叉树转换为链式存储二叉树，返回根节点 
int main(){
	int arr[]={-1,52,30,68,20,50,60,70};
	int n=sizeof(arr)/sizeof(arr[0])-1;
	printf("顺序存储的前序遍历：n");
	prePrint(1,arr,n);
	printf("n链式存储的前序遍历：n");
	Node *root=arrToList(arr,n);
	prePrint2(root);
}

Node *arrToList(int arr[],int n){
	Node *root=indexToNode(1,arr);
	list.push(root);
	while(!list.empty()){
		Node *temp=list.front();
		list.pop();
		int left=lChild(temp->in,n,arr); //当前节点对应左节点下标 
		if(left!=-1){
			Node *lNode=indexToNode(left,arr);
			temp->left=lNode;
			list.push(lNode);
		}
		int right=rChild(temp->in,n,arr); //当前节点对应右节点下标 
		if(right!=-1){
			Node *rNode=indexToNode(right,arr);
			temp->right=rNode;
			list.push(rNode);
		}
	}
	return root;
}

Node *indexToNode(int index,int arr[]){
	Node *root=(Node *)malloc(sizeof(Node));
	root->val=arr[index];
	root->in=index;
	root->left=NULL;
	root->right=NULL;
	return root;
} 

void prePrint(int index,int arr[],int n){
	if(arr[index]!=-1){
		printf("%d ",arr[index]);
	}
	int left=lChild(index,n,arr);
	if(left!=-1){
		prePrint(left,arr,n);
	}
	int right=rChild(index,n,arr);
	if(right!=-1){
		prePrint(right,arr,n);
	}
}


int Parent(int index){
	int parent=index/2;
	if(parent>0){
		return parent;
	}else{
	return -1;}
} 


int lChild (int index,int n,int arr[]){
	int lIndex=index*2;
	if(lIndex<=n&&arr[lIndex]!=-1){
		return lIndex;
	}else{
		return -1;
	}
}

int rChild (int index,int n,int arr[]){
	int rIndex=(index*2)+1;
	if(rIndex<=n&&arr[rIndex]!=-1){
		return rIndex;
	}else{
		return -1;
	}
}
//链式前序遍历 
void prePrint2(Node *root){
	printf("%d ",root->val);
	if(root->left!=NULL){
		prePrint2(root->left);
	}
	if(root->right!=NULL){
		prePrint2(root->right);
	}
}

#include
#include
//快速排序 
void QuickSort(int [],int,int);//对确定好位置的左右进行快速排序 
int returnIndex(int [],int,int);//快速排序中每次确定的索引位置 
//归并排序 
void MergeSort(int [],int,int,int);//数组一分为二，分别进行排序 
void Merge(int [],int,int,int);//将一分为二排好序的数组进行最终排序 
int main(){
	int arr[]={5,7,4,8,9,2,1,3,6};
	int n=sizeof(arr)/sizeof(int);
//	QuickSort(arr,0,n-1);
	MergeSort(arr,0,n-1,n);
	for(int i=0;itemp[j]){
			arr[index++]=temp[j++];
		}else{
			arr[index++]=temp[i++];
		}
	}
	while(i<=mid){
		arr[index++]=temp[i++];
	}
	while(j<=right){
		arr[index++]=temp[j++];
	}
}
int returnIndex(int arr[],int left,int right){
	int temp=arr[left];
	while(left=temp){
			right--;
		}
		arr[left]=arr[right];
		while(left 
查找 
二分查找 
#include
int HalfSearch(int left,int right,int arr[],int target);//递归方式的二分查找 
int HalfSearch2(int left,int right,int arr[],int target); //非递归方式的二分查找 
int main(){
	int arr[]={1,2,3,4,5,6,7,8};
	int n=sizeof(arr)/sizeof(int);
	int index=HalfSearch(0,n-1,arr,1);
	printf("目标位置索引为：%d",index);
}

int HalfSearch(int left,int right,int arr[],int target){
	if(left>right){
		return -1;
	}
	int midIndex=(left+right)/2;
	int mid=arr[midIndex];
	if(target==mid){
		return midIndex;
	}else if(target 
图 
 
 
邻接表代码较多，估计不好出考试题
 
 
邻接矩阵 
#include
#include
#include
#define MAX 10
using namespace std;
typedef struct{
	int Vex[MAX]; //顶点表
	int Edge[MAX][MAX]; //邻接矩阵
	int vexNum,arcNum;//顶点数和弧数
	bool Visited[MAX]; //节点是否访问 
}Graph;
Graph *g;
queue q; //
void initial(); //初始化顶点表，矩阵等信息 
void insertEdge(int,int,int); //无向图插入边 
void DFS(int); //广度优先遍历 
void BFS(int); //深度优先遍历 
int main(){
	initial();
	insertEdge(1,2,1); //顶点1与顶点2之间有通路 
	insertEdge(1,4,1);
	insertEdge(2,3,1);
	insertEdge(3,5,1);
	insertEdge(5,2,1);
	insertEdge(4,3,1);
//	printf("深度优先遍历：");
//	DFS(1);
	printf("广度优先遍历：");
	BFS(1);
}

void BFS(int index){
	q.push(index);
	while(!q.empty()){
		int n=q.size();
		for(int i=0;iVex[j]);
			g->Visited[j]=true;
			for(int x=0;xEdge[j][x]!=0&&g->Visited[x]==false){
					q.push(g->Vex[x]);
					g->Visited[x]=true;  //放进队列就相当于访问过 
				}
			}
		}
	}
}

void DFS(int index){
	printf("%d ",g->Vex[index]);
	g->Visited[index]=true;
	for(int i=0;iEdge[index][i]!=0&&g->Visited[i]==false){
			DFS(i);
		}
	}
}

void insertEdge(int Vex1,int Vex2,int Power){
	g->Edge[Vex1][Vex2]=Power;
	g->Edge[Vex2][Vex1]=Power; //无向图添两边 
}

void initial(){
	g=(Graph *)malloc(sizeof(Graph));
	for(int i=0;iEdge[i][j]=0; //此时顶点i与j之间没有通路 
		}
		g->Vex[i]=i; //0~9号顶点 
		g->Visited[i]=false; //顶点初始为被访问 
	}
	g->vexNum=0; //初始顶点数为0  
	g->arcNum=0; //初始边数为0
} 
 
总结 
 
 
这些整理希望能够帮助到你们【给个免费的赞吧】，祝你们考研成功，也祝我自己成功！