精华内容
下载资源
问答
  • 该资源为2014-2016年华中师范大学874数据结构C语言程序设计考研真题及部分参考答案,资源高清无水印哦! (注:2014、2016年参考答案)
  • 《874数据结构C语言程序设计》
  • 超级丰富的资源,适合考研和学习C语言数据结构使用,内含严蔚敏《数据结构>>,习题集,算法源码,算法演示,还有历年很多学校的考研真题
  • 数据结构C语言版——严蔚敏,考研需要
  • 该资源为严蔚敏《数据结构》(C语言版)笔记和习题(含考研真题)详解,资源高清无水印哦! 该资源为严蔚敏《数据结构》(C语言版)笔记和习题(含考研真题)详解,资源高清无水印哦!
  • 里面是2020王道数据结构课后习题可执行代码。https://blog.csdn.net/qq_40285036 可以参考这个博客一起学习。
  • 考研期间总结的数据结构代码大全,包括列表,栈,队列,树,图,查找,字符串,排序等数据结构的实现C语言实现版本,需要的朋友可以参考一下。
  • 清华大学 严蔚敏 数据结构C语言版 48小时教学大纲,讲得非常好
  • C语言考研试题和历年考试题和数据结构的知识·
  • 考研院校要求C语言实现数据结构,可前期做数据结构都是用Java实现,因此对于C不那么熟悉,花了一些时间重新捡起来C的语法,程序题通常不会考太过复杂的算法,因此自己将辅导书上一些母题进行了实现,其中层序遍历...

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

    链表

    结构体实现链表样例

    #include<stdio.h>
    #include<stdlib.h>
    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<stdio.h>
    #include<stdlib.h>
    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<stdio.h>
    #include<stdlib.h>
    #include<queue> //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<Node*> 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;i<n;i++){
    			Node *temp=q.front();
    			if(temp->left!=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<stdio.h>
    #include<stdlib.h>
    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->val<val){
    		if(root->right==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->val<val){
    		root=root->right;
    	}else{
    		root=root->left;
    	}
    	}
    	return NULL;
    }
     
    //插入节点 
    void insertNode(Node *root,Node *temp){
    	if(temp->val<root->val){
    		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<stdio.h>
    #include<stdlib.h>
    #include<queue>
    using namespace std;
    typedef struct Node{
    	int val;
    	int in; //在数组中哪个下标 
    	struct Node *left;
    	struct Node *right;
    }Node;
    queue<Node*> 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<stdio.h>
    #include<stdlib.h>
    //快速排序 
    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;i<n;i++){
    		printf("%d ",arr[i]);
    	}
    }
    void MergeSort(int arr[],int left,int right,int length){
    	if(left<right){
    		int mid=(left+right)/2;
    		MergeSort(arr,left,mid,length);
    		MergeSort(arr,mid+1,right,length);
    		Merge(arr,left,right,length);
    	}
    }
    void Merge(int arr[],int left,int right,int length){
    	int *temp=(int *)malloc(length*sizeof(int));
    	int mid=(left+right)/2;
    	for(int i=left;i<=right;i++){
    		temp[i]=arr[i];
    	}
    	int index=left,i=left,j=mid+1;
    	while(i<=mid&&j<=right){
    		if(temp[i]>temp[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<right){
    		while(left<right&&arr[right]>=temp){
    			right--;
    		}
    		arr[left]=arr[right];
    		while(left<right&&arr[left]<=temp){
    			left++;
    		}
    		arr[right]=arr[left];
    	}
    	arr[left]=temp;
    	return left;
    }
    void QuickSort(int arr[],int left,int right){
    	if(left<right){
    		int mid=returnIndex(arr,left,right);
    		QuickSort(arr,left,mid-1);
    		QuickSort(arr,mid+1,right);
    	}
    }
    

    查找

    二分查找

    #include<stdio.h>
    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<mid){
    		return HalfSearch(left,midIndex-1,arr,target);
    	}else{
    		return HalfSearch(midIndex+1,right,arr,target);
    	}
    }
    
    int HalfSearch2(int left,int right,int arr[],int target){
    	int index=-1;
    	while(left<=right){
    	index=(left+right)/2; //中间索引 
    	int mid=arr[(left+right)/2];  //中间值 
    	if(target==mid){
    		return index;
    	}else if(target<mid){
    		right=index-1;
    	}else{
    		left=index+1;
    	}
    }
    	return index;
    }
    

    邻接表代码较多,估计不好出考试题

    邻接矩阵

    #include<stdio.h>
    #include<stdlib.h>
    #include<queue>
    #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<int> 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;i<n;i++){
    			int j=q.front();
    			q.pop();
    			printf("%d ",g->Vex[j]);
    			g->Visited[j]=true;
    			for(int x=0;x<MAX;x++){
    				if(g->Edge[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;i<MAX;i++){
    		if(g->Edge[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;i<MAX;i++){
    		for(int j=0;j<MAX;j++){
    			g->Edge[i][j]=0; //此时顶点i与j之间没有通路 
    		}
    		g->Vex[i]=i; //0~9号顶点 
    		g->Visited[i]=false; //顶点初始为被访问 
    	}
    	g->vexNum=0; //初始顶点数为0  
    	g->arcNum=0; //初始边数为0
    } 
    

    总结

    这些整理希望能够帮助到你们【给个免费的赞吧】,祝你们考研成功,也祝我自己成功!

    展开全文
  • 北航991历年真题,答案以及c语言 数据结构电子版教材资料【1998-2018】
  • 991 复习资料  C语言程序设计 谭浩强 第四版、第五版 pdf 教程 C语言程序设计 谭浩强 第五版 课件 源程序 ...2018年北京航空航天大学硕士研究生招生考试专业课初试试题(数据结构C语言) 有偿资源,谢谢
  • 考研C语言进阶精讲课程,赵H英老师讲解C语言,高清,课程简单能懂
  • 写在前面: 恰逢期末复习,用了几天时间结合老师勾画的重点以及课件教材等,将全书重要内容做了个大整合。一方面便于自己复习记忆,另一方面po出来让更多需要的人也可以做个参考... 《数据结构C语言版 (清华严...

    写在前面:

    本系列参考书目: 清华大学出版社 《数据结构》(C语言版)

    《数据结构》(C语言版)是为“数据结构”课程编写的教材,是很多学校数据结构课程的指定教材也是经典教材,同时也是考研数据结构的必选书目。

    本系列根据课程重难点 整合此书精华部分,以求在尽可能短的时间内掌握相应知识,希望能够让你有所收获o(* ̄▽ ̄*)ブ

    后续还会进行更进一步的优化整理,欢迎关注,尽请期待。

    另附: 【刷题笔记0】系列目录索引(持续更新 & 推荐收藏)  与本系列基础知识搭配使用效果更佳!

    同类梳理:


              《数据库系统概论》第五版(王珊版)全书知识梳理


              《计算机组成原理》第五版(唐朔飞考研版) 全书知识梳理

              《软件工程与实践》第三版 软件工程课程知识梳理


    索引目录:

    《数据结构》| 第一章 绪论 知识梳理

    《数据结构》| 第二章 线性表 知识梳理

    《数据结构》| 第三章 栈和队列 知识梳理

    《数据结构》| 第四章 串 知识梳理

    《数据结构》| 第五章 数组和广义表 知识梳理

    《数据结构》| 第六章 树和二叉树 知识梳理 

    《数据结构》| 第七章 图 知识梳理 

    《数据结构》| 第九章 查找 知识梳理 

    《数据结构》| 第十章 排序 知识梳理

    如果有什么要补充的,欢迎下方👇评论区留言。

    1份赞许 = 100分的认可,如果感觉还不错,点个赞👍 支持一下吧 ~

    不定期分享 有趣、有料、有营养内容,欢迎 订阅关注 🤝 我的博客 ,期待在这里与你相遇 ~

    上一篇: 8种方法优雅地利用C++编程从1乘到20

    下一篇:  Facebook前身 哈佛大学"选美"网站核心算法 -- ELO等级分制度(附源码)

    展开全文
  • 北航 991数据结构C语言程序设计考试大纲(2018版),供2019年考研同学参考
  • 数据结构习题集leetcode21PAT 6-1 单链表逆转 (20 分)leetcode 141. 环形链表PAT 6-2 顺序表操作集 (20 分) leetcode21 /* Created by salmon on 2021-9-14 21:27. */ /** * Definition for singly-linked list....

    PAT
    leetcode
    代码github备份

    在这里插入图片描述

    在这里插入图片描述

    数据结构习题集

    leetcode 21. 合并两个有序链表

    在这里插入图片描述

    /* 
    Created by salmon on 2021-9-14 21:27.
    */
    
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
        struct ListNode head;
        struct ListNode* res = &head;
        while (l1 != NULL && l2 != NULL) { //l2小于等于l1时插入l2,否则插入l1; 每次插入后指针后移一位;
            if(l2 -> val <= l1 -> val){
                res -> next = l2;
                l2 = l2 -> next;
            } else {
                res -> next = l1;
                l1 = l1 -> next;
            }
            res = res -> next;
        }
        //此时循环结束,必定至少有一个链表被循环到最后一个节点之后的空指针上
        if(l1 == NULL){
            res -> next = l2;
        } else if (l2 == NULL){
            res -> next = l1;
        }
    
    
        //返回头指针
        //不能返回head->next,因为head不是指针是一个struct类型的变量
        //参考文档:https://blog.csdn.net/faihung/article/details/79190039
        return head.next;
    }
    

    PAT 6-1 单链表逆转 (20 分)

    在这里插入图片描述

    /* 
    Created by salmon on 2021-9-13 23:09.
     单链表逆转
    */
    
    typedef struct Node *PtrToNode;
    struct Node {
        ElementType Data; /* 存储结点数据 */
        PtrToNode   Next; /* 指向下一个结点的指针 */
    };
    typedef PtrToNode List; /* 定义单链表类型 */
    
    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef int ElementType;
    typedef struct Node *PtrToNode;
    struct Node {
        ElementType Data;
        PtrToNode   Next;
    };
    typedef PtrToNode List;
    
    List Read(); /* 细节在此不表 */
    void Print( List L ); /* 细节在此不表 */
    
    List Reverse( List L );
    
    int main()
    {
        List L1, L2;
        L1 = Read();
        L2 = Reverse(L1);
        Print(L1);
        Print(L2);
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    
    List Reverse( List L ){
        if(L==NULL || L->Next==NULL)
            return L;
    
        //需要三个指针,顺序为L,P1,P2
        //L指向L的头结点,并且为了实现目的将其孤立
        //p1指向L的下一个,p2指向p1的下一个,所以必定是p2先指向NULL
        List p1 = L->Next;
        L->Next = NULL;
        List p2 = p1->Next;
        while (p2) {
            //调转指针next方向
            p1->Next = L;
            //第一个指针后移一位
            L = p1;
            //第二个指针后移一位
            p1 = p2;
            第三个指针后移一位
            p2 = p2->Next;
        }
        //处理到这里时面临一种情况:L在倒数第二个节点,P1在倒数第一个结点,P2在空结点上
        //此时最后的P1结点没有处理,应该讲P1的next也逆转
        p1->Next = L;
        return p1;
    }
    

    leetcode 141. 环形链表

    在这里插入图片描述

    /**
    *Created by salmon on 2021-9-14 22:25.
    **/
    
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    bool hasCycle(struct ListNode *head) {
        if(head == NULL){ //若为空必定不存在环
            return false;
        }
    
        struct ListNode* fast = head -> next;
        struct ListNode* slow = head;
        //快慢指针,快的比慢的快一个位置
        //如果快的追上慢的就表明有环
        while (slow != fast) {
            if(fast == NULL || fast -> next == NULL){ 
                //因为fast一次移动两个元素,所以fast至少指向该链表倒数第二个节点
                //否则会发生空指针访问空指针域的问题
                return false;
            }
            fast = fast -> next -> next;
            slow = slow -> next;
        }
        return true;
    }
    

    PAT 6-2 顺序表操作集 (20 分)

    在这里插入图片描述

    /**
    *Created by salmon on 2021-9-14 23:32.
    **/
    
    /**
    *Created by salmon on 2021-9-14 22:57.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 7
    #define ERROR -1
    typedef enum {false, true} bool;
    typedef int ElementType;
    typedef int Position;
    typedef struct LNode *List;
    struct LNode {
        ElementType Data[MAXSIZE];
        Position Last; /* 保存线性表中最后一个元素的位置 */
    };
    
    List MakeEmpty();
    Position Find( List L, ElementType X );
    bool Insert( List L, ElementType X, Position P );
    bool Delete( List L, Position P );
    
    int main()
    {
        List L;
        ElementType X;
        Position P;
        int N;
    
        L = MakeEmpty();
        scanf("%d", &N);
        while ( N-- ) {
            scanf("%d", &X);
            if ( Insert(L, X, 0)==false )
                printf(" Insertion Error: %d is not in.\n", X);
        }
        scanf("%d", &N);
        while ( N-- ) {
            scanf("%d", &X);
            P = Find(L, X);
            if ( P == ERROR )
                printf("Finding Error: %d is not in.\n", X);
            else
                printf("%d is at position %d.\n", X, P);
        }
        scanf("%d", &N);
        while ( N-- ) {
            scanf("%d", &P);
            if ( Delete(L, P)==false )
                printf(" Deletion Error.\n");
            if ( Insert(L, 0, P)==false )
                printf(" Insertion Error: 0 is not in.\n");
        }
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    
    List MakeEmpty(){ //创建并返回一个空的线性表
        List list = (List)malloc(sizeof(struct LNode));
        list->Last = -1;
        return list;
    }
    
    Position Find( List L, ElementType X ){ //返回线性表中X的位置。若找不到则返回ERROR;
        for (int i = 0; i <= L->Last; ++i) {//TODO 这里可能错
            if(L->Data[i] == X){
                return i;
            }
        }
        return ERROR;
    }
    
    bool Insert( List L, ElementType X, Position P ){ // 将X插入在位置P并返回true。若空间已满,则打印“FULL”并返回false;如果参数P指向非法位置,则打印“ILLEGAL POSITION”并返回false;
        if(P < 0 || P > L->Last + 1){ //非法位置,正确:可以插入在[0,当前数组最大值+1]之间
            printf("ILLEGAL POSITION");
            return false;
        }
        if(L->Last == MAXSIZE - 1){ //顺序表已满
            printf("FULL");
            return false;
        }
        for (int i = L->Last + 1; i > P ; --i) { //i一直遍历到要插入下标P+1的位置
            L->Data[i] = L->Data[i - 1];
        }
        //当前P位置空缺出来
        L->Data[P] = X;
        //更新最后一个结点的下标
        L->Last++;
        return true;
    }
    
    bool Delete( List L, Position P ){// 将位置P的元素删除并返回true。若参数P指向非法位置,则打印“POSITION P EMPTY”(其中P是参数值)并返回false。
        if(P < 0 || P > L->Last){ //非法位置,正确:可以删除在[0,当前数组最大值]之间的任何数
            printf("POSITION %d EMPTY",P);
            return false;
        }
        for (int i = P; i < L->Last ; ++i) { //i一直遍历到数组倒数第二个元素
            L->Data[i] = L->Data[i + 1];
        }
        L->Data[L->Last] = -1; //去掉最后一个元素
        L->Last--;
        return true;
    }
    
    
    

    在这里插入图片描述

    PAT 6-3 求链式表长(10 分)

    /**
    *Created by salmon on 2021-9-15 22:15.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef int ElementType;
    typedef struct LNode *PtrToLNode;
    struct LNode {
        ElementType Data;
        PtrToLNode Next;
    };
    typedef PtrToLNode List;
    
    List Read(); /* 细节在此不表 */
    
    int Length( List L );
    
    int main()
    {
        List L = Read();
        printf("%d\n", Length(L));
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    int Length( List L ){
        int length = 0;
        while (L) {
            length++;
            L = L->Next;
        }
        return length;
    }
    
    

    在这里插入图片描述

    PAT 6-4 链式表的按序号查找 (10 分)

    在这里插入图片描述

    /**
    *Created by salmon on 2021-9-15 22:21.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR -1
    typedef int ElementType;
    typedef struct LNode *PtrToLNode;
    struct LNode {
        ElementType Data;
        PtrToLNode Next;
    };
    typedef PtrToLNode List;
    
    List Read(); /* 细节在此不表 */
    
    ElementType FindKth( List L, int K );
    
    int main()
    {
        int N, K;
        ElementType X;
        List L = Read();
        scanf("%d", &N);
        while ( N-- ) {
            scanf("%d", &K);
            X = FindKth(L, K);
            if ( X!= ERROR )
                printf("%d ", X);
            else
                printf("NA ");
        }
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    ElementType FindKth( List L, int K ){ //这里的K不是下标,是序号
        if(K <= 0) return ERROR;
        int index = 0;
        while (L) {
            if (index + 1 == K) {
                return L->Data;
            } else {
                L = L->Next;
                index++;
            }
        }
        return ERROR;
    }
    

    在这里插入图片描述

    leetcode 203. 移除链表元素

    在这里插入图片描述

    struct ListNode* removeElements(struct ListNode* head, int val){
        struct  ListNode* res = malloc(sizeof(struct ListNode));
        res -> next = head;//虚拟一个空的头结点出来
        struct ListNode* p = res;//拷贝res,用p进行遍历,保证无论如何删除使res的下一个就是头结点,如果不拷贝res而是使用head返回,那么如果删除第一个元素就会出现问题
    //    while (p) { 这里如果不是下面这样写的话,会出现访问空指针空间的异常
            while (p->next != NULL) {
            if(p -> next -> val == val) {
               p->next = p->next->next;
            } else {
                p = p -> next;
            }
        }
        return res->next;
    }
    

    在这里插入图片描述

    leetcode 83. 删除排序链表中的重复元素

    在这里插入图片描述

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    struct ListNode* deleteDuplicates(struct ListNode* head){
        if(head == NULL || head->next == NULL){
            return head;
        }
        struct ListNode* p = head;
        while (p->next != NULL) {
            if(p->next->val == p->val){
                p->next = p->next->next;
            } else {
                p = p->next;
            }
        }
        return head;
    }
    

    在这里插入图片描述

    PAT 6-5 链式表操作集 (20 分)

    在这里插入图片描述

    /**
    *Created by salmon on 2021-9-16 22:07.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR NULL
    typedef int ElementType;
    typedef struct LNode *PtrToLNode;
    struct LNode {
        ElementType Data;
        PtrToLNode Next;
    };
    typedef PtrToLNode Position;
    typedef PtrToLNode List;
    
    Position Find( List L, ElementType X );
    List Insert( List L, ElementType X, Position P );
    List Delete( List L, Position P );
    
    int main()
    {
        List L;
        ElementType X;
        Position P, tmp;
        int N;
    
        L = NULL;
        scanf("%d", &N);
        while ( N-- ) {
            scanf("%d", &X);
            L = Insert(L, X, L);
            if ( L==ERROR ) printf("Wrong Answer\n");
        }
        scanf("%d", &N);
        while ( N-- ) {
            scanf("%d", &X);
            P = Find(L, X);
            if ( P == ERROR )
                printf("Finding Error: %d is not in.\n", X);
            else {
                L = Delete(L, P);
                printf("%d is found and deleted.\n", X);
                if ( L==ERROR )
                    printf("Wrong Answer or Empty List.\n");
            }
        }
        L = Insert(L, X, NULL);
        if ( L==ERROR ) printf("Wrong Answer\n");
        else
            printf("%d is inserted as the last element.\n", X);
        P = (Position)malloc(sizeof(struct LNode));
        tmp = Insert(L, X, P);
        if ( tmp!=ERROR ) printf("Wrong Answer\n");
        tmp = Delete(L, P);
        if ( tmp!=ERROR ) printf("Wrong Answer\n");
        for ( P=L; P; P = P->Next ) printf("%d ", P->Data);
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    Position Find( List L, ElementType X ){//返回线性表中首次出现X的位置。若找不到则返回ERROR;
        Position res = L;
        while (L) {
            if(L->Data == X){
                return res;
            } else {
                L = L->Next;
                res = res->Next;
            }
        }
        return ERROR;
    }
    List Insert( List L, ElementType X, Position P ){ //将X插入在位置P指向的结点之前,返回链表的表头。如果参数P指向非法位置,
                                                        // 则打印“Wrong Position for Insertion”,返回ERROR;
        if(P < 0) {
            printf("Wrong Position for Insertion\n");
            return ERROR;
        }
        struct LNode *head = malloc(sizeof(struct LNode));
        head->Next = L;
        struct LNode *p = head;
        Position x = (Position)malloc(sizeof(struct LNode));
        x->Data = X;
        while (p) {
            if(p->Next == P){//P为没有加入一个虚拟的头结点的第一个结点下标 也可以这么想i指向-1,p指向0; 但使i=0时i总是在p前面一个位置
                struct LNode *temp = p->Next;
                p->Next = x;
                x->Next = temp;
                return head->Next;
            } else {
                p = p->Next;
            }
        }
        printf("Wrong Position for Insertion\n");
        return ERROR;
    }
    List Delete( List L, Position P ){ //将位置P的元素删除并返回链表的表头。若参数P指向非法位置,
                                        // 则打印“Wrong Position for Deletion”并返回ERROR
        if(P < 0) {
            printf("Wrong Position for Deletion\n");
            return ERROR;
        }
        struct LNode *head = malloc(sizeof(struct LNode));
        head->Next = L;
        struct LNode *p = head;
        while (p) {
            if (p->Next == P) {
               p->Next = p->Next->Next;
               return head->Next;
            } else {
                p = p->Next;
            }
        }
        printf("Wrong Position for Deletion\n");
        return ERROR;
    
    }
    

    在这里插入图片描述

    PAT 6-6 带头结点的链式表操作集 (20 分)

    /**
    *Created by salmon on 2021-9-17 22:05.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR NULL
    typedef enum {false, true} bool;
    typedef int ElementType;
    typedef struct LNode *PtrToLNode;
    struct LNode {
        ElementType Data;
        PtrToLNode Next;
    };
    typedef PtrToLNode Position;
    typedef PtrToLNode List;
    
    List MakeEmpty();
    Position Find( List L, ElementType X );
    bool Insert( List L, ElementType X, Position P );
    bool Delete( List L, Position P );
    
    int main()
    {
        List L;
        ElementType X;
        Position P;
        int N;
        bool flag;
    
        L = MakeEmpty();
        scanf("%d", &N);
        while ( N-- ) {
            scanf("%d", &X);
            flag = Insert(L, X, L->Next);
            if ( flag==false ) printf("Wrong Answer\n");
        }
        scanf("%d", &N);
        while ( N-- ) {
            scanf("%d", &X);
            P = Find(L, X);
            if ( P == ERROR )
                printf("Finding Error: %d is not in.\n", X);
            else {
                flag = Delete(L, P);
                printf("%d is found and deleted.\n", X);
                if ( flag==false )
                    printf("Wrong Answer.\n");
            }
        }
        flag = Insert(L, X, NULL);
        if ( flag==false ) printf("Wrong Answer\n");
        else
            printf("%d is inserted as the last element.\n", X);
        P = (Position)malloc(sizeof(struct LNode));
        flag = Insert(L, X, P);
        if ( flag==true ) printf("Wrong Answer\n");
        flag = Delete(L, P);
        if ( flag==true ) printf("Wrong Answer\n");
        for ( P=L->Next; P; P = P->Next ) printf("%d ", P->Data);
        return 0;
    }
    /* 你的代码将被嵌在这里 */
    List MakeEmpty(){//创建并返回一个带头节点的空的线性表;
        List list = (List)malloc(sizeof(struct LNode));
        list->Next = NULL;
        return list;
    }
    Position Find( List L, ElementType X ){// 返回线性表中X的位置。若找不到则返回ERROR;
        Position p = L;
        while (p->Next) {//至于这里为什么是p->Next是因为在下方的if中访问了p的下一个节点的内容,如果p的下一个节点为空,会发生段错误
            if(p->Next->Data == X){
                return p->Next;
            } else {
                p = p->Next;
            }
        }
        return ERROR;
    }
    bool Insert( List L, ElementType X, Position P ){// 将X插入在位置P指向的结点之前,返回true。如果参数P指向非法位置,
        // 则打印“Wrong Position for Insertion”,返回false;
        Position p = L;
        Position x = (Position)malloc(sizeof(struct LNode));
        x->Data = X;
        while (p) {
            if(p->Next == P){
                p->Next = x;
                x->Next = P;
                return true;
            } else {
                p = p->Next;
            }
        }
        printf("Wrong Position for Insertion\n");
        return false;
    }
    bool Delete( List L, Position P ){  // 将位置P的元素删除并返回true。若参数P指向非法位置,
        // 则打印“Wrong Position for Deletion”并返回false。
        Position p = L;
        while (p) {
            if(p->Next == P){
                p->Next = p->Next->Next;
                return true;
            } else {
                p = p->Next;
            }
        }
        printf("Wrong Position for Deletion\n");
        return false;
    }
    

    在这里插入图片描述

    PAT 6-7 在一个数组中实现两个堆栈 (20 分)

    在这里插入图片描述

    /**
    *Created by salmon on 2021-9-18 22:13.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR 1e8
    typedef int ElementType;
    typedef enum { push, pop, end } Operation;
    typedef enum { false, true } bool;
    typedef int Position;
    struct SNode {
        ElementType *Data;
        Position Top1, Top2;
        int MaxSize;
    };
    typedef struct SNode *Stack;
    
    Stack CreateStack( int MaxSize );
    bool Push( Stack S, ElementType X, int Tag );
    ElementType Pop( Stack S, int Tag );
    
    Operation GetOp();  /* details omitted */
    void PrintStack( Stack S, int Tag ); /* details omitted */
    
    int main()
    {
        int N, Tag, X;
        Stack S;
        int done = 0;
    
        scanf("%d", &N);
        S = CreateStack(N);
        while ( !done ) {
            switch( GetOp() ) {
                case push:
                    scanf("%d %d", &Tag, &X);
                    if (!Push(S, X, Tag)) printf("Stack  %d is Full!\n", Tag);
                    break;
                    case pop:
                        scanf("%d", &Tag);
                        X = Pop(S, Tag);
                        if ( X==ERROR ) printf("Stack %d is Empty!\n", Tag);
                        break;
                        case end:
                            PrintStack(S, 1);
                            PrintStack(S, 2);
                            done = 1;
                            break;
            }
        }
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    Stack CreateStack( int MaxSize ){//两端各有一个栈
        Stack s = (Stack) malloc(sizeof(struct SNode));
        s->Data = (ElementType *) malloc(sizeof(ElementType)*MaxSize);
        s->MaxSize = MaxSize;
        s->Top1 = -1;
        s->Top2 = MaxSize;
        return s;
    }
    bool Push( Stack S, ElementType X, int Tag ){//tag表示对哪个栈进行处理
        if (S->Top1 + 1 == S->Top2) {
            printf("Stack Full\n");
            return false;
        }
    
        if(Tag == 1){
            S->Top1++;
            S->Data[S->Top1] = X;
        } else {
            S->Top2--;
            S->Data[S->Top2] = X;
        }
        return true;
    
    }
    ElementType Pop( Stack S, int Tag ){
        if ((S->Top1 == -1 && Tag == 1) || (S->Top2 == S->MaxSize && Tag == 2)) {
            printf("Stack %d Empty\n",Tag);
            return ERROR;
        }
    
        if(Tag == 1){
            return S->Data[S->Top1--];
        } else {
            return S->Data[S->Top2++];
        }
    }
    

    在这里插入图片描述

    PAT 6-8 求二叉树高度 (20 分) 递归与非递归方法

    在这里插入图片描述

    int GetHeight( BinTree BT ){ //在脑中想象一颗只有2层的满二叉树可以更好地理解
        int maxLeft = 0,maxRight = 0;
        if(BT == NULL){ //第一次,一直递归到此树叶子结点的孩子结点时停止,此时该结点为NULL所以高度为0
            return 0;
        } else { //以当前BT为根节点判断左子树高度和右子树高度谁更大
            maxLeft = GetHeight(BT->Left);
            maxRight = GetHeight(BT->Right);
            return (maxLeft > maxRight ? maxLeft + 1 : maxRight + 1); //此时已经计算完成一个叶结点,返回结点到它的双亲节点,显然高度要加1
        }
    }
    

    非递归算法求二叉树的高度,一般利用层次遍历的方法,初始化一个队列,定义一个中间变量来保存每次循环一开始的rear,如果front追上了rear则二叉树高度加1

    int GetHeight( BinTree BT ){ //在脑中想象一颗只有2层的满二叉树可以更好地理解
        if (BT == NULL) return 0;
        BinTree Queque[999];
    
        //初始化队列
        Queque[0] = BT;
        int front = 0, rear = 1,last = rear;
        int high = 0;
    
        while (front < rear) {
            if (Queque[front]->Left != NULL) {
                Queque[rear] = Queque[front]->Left;
                rear++;
            }
            if(Queque[front]->Right != NULL) {
                Queque[rear] = Queque[front]->Right;
                rear++;
            }
            front++;
            if(front == last){
                high++;
                last = rear;
            }
        }
        return high;
    }
    

    在这里插入图片描述

    PAT 6-10 二分查找 (20 分)(递归和迭代版本)

    在这里插入图片描述

    Position trueBinarySearch( List L, ElementType X, Position low, Position high ){
        if(low > high) return NotFound;
        Position mid = (Position)((low + high) / 2);
        if (X < L->Data[mid]) {
            return trueBinarySearch(L,X,low,mid - 1);
        } else if (X > L->Data[mid]) {
            return trueBinarySearch(L,X,mid + 1,high);
        } else {
            return mid;
        }
    }
    
    Position BinarySearch( List L, ElementType X ){
        Position high = L->Last;
        Position low = 0;
        return trueBinarySearch(L,X,low,high);
    }
    
    
    
    Position BinarySearch( List L, ElementType X ){
        ElementType tag;
        Position low = 0;
        Position high = L -> Last;
        while (low <= high) {
            Position mid = (ElementType)((low + high) / 2);
            if (X < L->Data[mid]) {
                high = mid - 1;
            } else if (X > L->Data[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return NotFound;
    }
    

    在这里插入图片描述

    PAT 6-9 二叉树的遍历 (25 分) 迭代和递归版本

    在这里插入图片描述

    void InorderTraversal( BinTree BT ){//中序
        if (BT) {
            InorderTraversal(BT->Left);
            printf(" %c",BT->Data);
            InorderTraversal(BT->Right);
        }
    }
    void PreorderTraversal( BinTree BT ){
        if (BT) {
            printf(" %c",BT->Data);
            PreorderTraversal(BT->Left);
            PreorderTraversal(BT->Right);
        }
    }
    void PostorderTraversal( BinTree BT ){
        if (BT) {
            PostorderTraversal(BT->Left);
            PostorderTraversal(BT->Right);
            printf(" %c",BT->Data);
        }
    }
    void LevelorderTraversal( BinTree BT ){//层次遍历
        if (BT == NULL) return;
        BinTree Queque[999];
    
        //初始化队列
        Queque[0] = BT;
        int front = 0, rear = 1;
    
        while (front < rear) {
            if (Queque[front]->Left != NULL) {
                Queque[rear] = Queque[front]->Left;
                rear++;
            }
            if(Queque[front]->Right != NULL) {
                Queque[rear] = Queque[front]->Right;
                rear++;
            }
            printf(" %c",Queque[front]->Data);
            front++;
        }
    }
    
    BinTree assistStack[999];
    int assistTop = -1;
    void assistPush( BinTree BT ){
        if(assistTop >= 999) return;
        assistTop++;
        assistStack[assistTop] = BT;
    }
    
    BinTree assistPop(){
        if(assistTop <= -1) return NULL;
        return assistStack[assistTop--];
    }
    
    int assistStackIsEmpty(){
        if(assistTop <= -1) return -1; //-1为空
        else return 1;           //1为不空
    }
    
    
    BinTree Stack[999];
    int top = -1;
    void push( BinTree BT ){
        if(top >= 999) return;
        top++;
        Stack[top] = BT;
    }
    
    BinTree pop(){
        if(top <= -1) return NULL;
        return Stack[top--];
    }
    
    int stackIsEmpty(){
        if(top <= -1) return -1; //-1为空
        else return 1;           //1为不空
    }
    
    void InorderTraversal( BinTree BT ){//中序
        while (BT != NULL || stackIsEmpty() == 1) {
            while (BT != NULL) {
                push(BT);
                BT = BT->Left;
            }
            if (stackIsEmpty() == 1) {
                BT = pop();
                printf(" %c",BT->Data);
                BT = BT->Right;
            }
        }
    }
    void PreorderTraversal( BinTree BT ){
        if(BT == NULL) return;
        push(BT);
        while (stackIsEmpty() == 1) {
            BT = pop();
            printf(" %c",BT->Data);
            if(BT->Right != NULL){
                push(BT->Right);
            }
            if(BT->Left != NULL){
                push(BT->Left);
            }
        }
    }
    void PostorderTraversal( BinTree BT ){
        while (BT != NULL || assistStackIsEmpty() == 1) {
            while (BT != NULL) {
                assistPush(BT);
                push(BT);
                BT = BT->Right;
            }
            if(assistStackIsEmpty() == 1){
                BT = assistPop();
                BT = BT->Left;
            }
        }
        while (stackIsEmpty() == 1) {
            BinTree res = pop();
            printf(" %c",res->Data);
        }
    }
    void LevelorderTraversal( BinTree BT ){//层次遍历
        if (BT == NULL) return;
        BinTree Queque[999];
    
        //初始化队列
        Queque[0] = BT;
        int front = 0, rear = 1;
    
        while (front < rear) {
            if (Queque[front]->Left != NULL) {
                Queque[rear] = Queque[front]->Left;
                rear++;
            }
            if(Queque[front]->Right != NULL) {
                Queque[rear] = Queque[front]->Right;
                rear++;
            }
            printf(" %c",Queque[front]->Data);
            front++;
        }
    }
    

    参考博客:https://blog.csdn.net/dabusiGin/article/details/102736180?spm=1001.2014.3001.5501
    在这里插入图片描述
    这里我们总结一下非递归版本的二叉树遍历:

    • 先序遍历:没什么难的,先右后左,输出根
    1. 定义一个栈
    2. 把根节点入栈
    3. 建立一个以栈不空为条件的循环
    4. 出栈,当前指针指向出栈的元素,并输出当前元素的内容
    5. 将该节点按照先右后左的顺序入栈
    6. 循环往复直到退出循环
    • 中序遍历:稍微有点东西,先访问到最左下角的结点,一边访问一遍入栈。到底后出栈,并输出当前结点的内容,如果当前有右节点那么接着访问该节点左孩子节点,否则出栈回到父节点
    1. 建立一个以当前指针不空或栈不空的循环
    2. 如果当前指针不为空,就入栈,并一直访问到最左节点的左孩子
    3. 如果栈不空就出栈并输出当前元素内容
    4. 访问右节点(这里比较巧妙的是,如果右节点为空,什么也不做,只是出栈回到父节点)
    5. 循环往复
    • 后序遍历:有些难,需要两个栈配合,与中序反着来。先一直访问到最右结点,一边访问一边同时入两个栈。到底后出栈,如果出栈结点有左孩子结点就接着访问该节点的右孩子,否则出栈回到父节点
    1. 建立一个以当前指针不空或栈不空的循环
    2. 如果当前指针不为空,就入双栈,并一直访问到最右节点的右孩子
    3. 如果辅助栈不空就出辅助栈
    4. 访问左节点(这里比较巧妙的是,如果右节点为空,什么也不做,只是出栈回到父节点)
    5. 循环往复
    6. 输出非辅助栈内的元素
    • 层序遍历:没啥好说的一个队列就完事

    总的来说就是,前中后非递归遍历要利用好栈,用栈来代替递归中的回溯到父节点的功能。

    PAT 6-11 先序输出叶结点 (15 分)

    在这里插入图片描述

    /**
    *Created by salmon on 2021-9-23 22:22.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    BinTree CreatBinTree(); /* 实现细节忽略 */
    void PreorderPrintLeaves( BinTree BT );
    
    int main()
    {
        BinTree BT = CreatBinTree();
        printf("Leaf nodes are:");
        PreorderPrintLeaves(BT);
        printf("\n");
    
        return 0;
    }
    /* 你的代码将被嵌在这里 */
    void PreorderPrintLeaves( BinTree BT ){
        if(!BT) return;
        if(BT->Left == NULL && BT->Right == NULL){
            printf(" %c",BT->Data);
            return;
        }
        if(BT->Left != NULL){
            return PreorderPrintLeaves(BT->Left);
        }
        if(BT->Right != NULL){
            return PreorderPrintLeaves(BT->Right);
        }
    }
    

    在这里插入图片描述

    PAT 6-12 二叉搜索树的操作集 (30 分) 递归与非递归版本

    在这里插入图片描述

    BinTree Insert( BinTree BST, ElementType X ){
        if (!BST) { //当递归到正确位置时创造结点
            BST = (BinTree) malloc(sizeof(struct TNode));
            BST->Right = NULL;
            BST->Left = NULL;
            BST->Data = X;
        }
        if(BST->Data > X) BST->Left = Insert(BST->Left,X); //根据二叉搜索树的特性,小了往左,大了往右,一直到叶节点为止
        if(BST->Data < X) BST->Right = Insert(BST->Right,X);
        return BST;
    }
    /**
     * 二叉搜索树的删除有三种情况:
     *                  1.被删除节点为叶子结点,此时什么都不用做,直接删除
     *                  2.被删除节点只有左结点或右结点,用子结点代替即可
     *                  3.被删除节点有两个孩子,那么我们使用它的后继(或前驱)结点替换它,并且删除前驱结点
     * @param BST
     * @param X
     * @return
     */
    BinTree Delete( BinTree BST, ElementType X ){
    
        if(!BST){
            printf("Not Found\n");
            return BST;
        }
        if(BST->Data < X) BST->Right = Delete(BST->Right,X);
        if(BST->Data > X) BST->Left = Delete(BST->Left,X);
        if(BST->Data == X){
            if(BST->Left == NULL || BST->Right == NULL){
                BST = BST->Left == NULL ? BST->Right : BST->Left;
            } else {
                Position temp = FindMin(BST->Right);
                BST->Data = temp->Data; //注意只是把内容替换,务必不要整个替换节点
                BST->Right = Delete(BST->Right,BST->Data);//删除结点
            }
        }
        return BST;
    
    }
    Position Find( BinTree BST, ElementType X ){
        if(!BST) return NULL;
        if(BST->Data == X) return BST;
        else if(BST->Data > X) return Find(BST->Left,X);
        else return Find(BST->Right,X);
    }
    Position FindMin( BinTree BST ){
        if(!BST) return NULL;
        if (BST->Left) {
           return FindMin(BST->Left);
        }
        return BST;
    }
    Position FindMax( BinTree BST ){
        if(!BST) return NULL;
        if (BST->Right) {
            return FindMax(BST->Right);
        }
        return BST;
    }
    
    Position Find(BinTree BST, ElementType X){
    	while (BST){
    		if (X > BST->Data) BST = BST->Right;
    		else if (X < BST->Data) BST = BST->Left;//此处一定要加else,下同
    		else if(X==BST->Data) return BST;
    	}
    	return NULL;
    }
    
    Position FindMin( BinTree BST ){
        if(!BST) return NULL;
        while(BST->Left) BST = BST->Left;
        return BST;
    }
    
    Position FindMax( BinTree BST ){
        if(!BST) return NULL;
        while(BST->Right) BST = BST->Right;
        return BST;
    }
    
    BinTree Insert( BinTree BST, ElementType X ){
        if(!BST){
            BST = (BinTree)malloc(sizeof(struct TNode));
            BST->Data = X;
            BST->Left = NULL;
            BST->Right = NULL;
        }
        if(X < BST->Data) BST->Left = Insert(BST->Left, X);
        if(X > BST->Data) BST->Right = Insert(BST->Right, X);
        return BST;
    }
    
    BinTree Delete( BinTree BST, ElementType X ){
        Position temp;
        if(!BST){
            printf("Not Found\n");
            return BST;
        }
        if(X < BST->Data) BST->Left = Delete(BST->Left, X);
        if(X > BST->Data) BST->Right = Delete(BST->Right, X);
        if(X==BST->Data){
            if(BST->Left&&BST->Right){
                temp = FindMin(BST->Right);
                BST->Data = temp->Data;
                BST->Right = Delete(BST->Right, BST->Data);
            }
            else{
                if(BST->Left) BST = BST->Left;
                else BST = BST->Right;
            }
        }
        return BST;
    }
    
    

    在这里插入图片描述

    求二叉树中度为0、1、2结点的个数

    #include <iostream>
    
    /**
    *Created by salmon on 2021-9-25 22:30.
    **/
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    int degree0Count = 0;
    int degree1Count = 0;
    int degree2Count = 0;
    
    
    void nodeCountOfVariousDegree( BinTree BT ,int &degree0Count, int &degree1Count, int &degree2Count ){
        if(!BT) return;
        if(BT->Left == NULL && BT->Right == NULL){
            degree0Count++;
        }else if((BT->Left == NULL && BT->Right != NULL) || (BT->Right == NULL && BT->Left != NULL)){
            degree1Count++;
        }else if(BT->Left != NULL && BT->Right != NULL){
            degree2Count++;
        }
        if(BT->Left != NULL){
             nodeCountOfVariousDegree(BT->Left,degree0Count,degree1Count,degree2Count);
        }
        if(BT->Right != NULL){
             nodeCountOfVariousDegree(BT->Right,degree0Count,degree1Count,degree2Count);
        }
    }
    
    int main(){
        BinTree binTree = (BinTree)malloc(sizeof(struct TNode));
    //    binTree->Left = NULL;
        binTree->Left = (BinTree)malloc(sizeof(struct TNode));
        binTree->Left->Left = NULL;
        binTree->Left->Right = NULL;
    //    binTree->Right = (BinTree)malloc(sizeof(struct TNode));
    //    binTree->Right->Left = NULL;
    //    binTree->Right->Right = NULL;
        binTree->Right == NULL;
        nodeCountOfVariousDegree(binTree,degree0Count,degree1Count,degree2Count);
        printf("%d\n",degree0Count);
        printf("%d\n",degree1Count);
        printf("%d\n",degree2Count);
    
    }
    
    
    

    ---------------以下只给出伪代码--------------------

    二叉树自下而上,从右到左的层次遍历

    /**
    *Created by salmon on 2021-9-29 22:50.
    **/
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    void SpecialLevelTraversebt(BinTree BT){ //即与正常的层次遍历算法的输出反着来,多添加一个栈来实现
        if(BT == NULL) return;
        Queue Q = initQueue();
        Stack S = initStack();
        EnQueue(BT);
        while ( !isEmpty(Q) ) {
            BinTree temp = DeQueue();
            Push(temp);
            if(temp->Left){
                EnQueue(temp->Left);
            }
            if(temp->Right){
                EnQueue(temp->Right);
            }
        }
    
        while ( !isEmpty(S) ){
            BinTree res = Pop(S);
            visit(res->Data);
        }
    }
    

    判断二叉树是否为完全二叉树

    /**
    *Created by salmon on 2021-9-29 23:12.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    /**
     * 具体思路为,进行普通的层序遍历,唯一不同的是即使当前结点为叶子结点,我们依旧把左右孩子入队列,
     * 当遍历到空节点时,说明已经遍历到第一个叶子结点的孩子结点,那么从这里开始队列中的剩余结点均为空结点,
     * 所以如果剩余结点有不为空的结点,那么就不是完全二叉树
     * @param BT 
     * @return 
     */
    bool isCompleteTree(BinTree BT){
        if(!BT) return true; //如果树为空,是完全二叉树
        Queue Q = InitQueue();
        EnQueue(BT);
        while ( !isEmpty(Q) ){
            BinTree BT = DeQueue(Q);
            if(BT){
                EnQueue(BT->Left);
                EnQueue(BT->Right);
            } else {
                while ( !isEmpty(Q) ){
                    BinTree BT = DeQueue(Q);
                    if(BT) return false;
                }
                return true;
            }
        }
    }
    

    将二叉树所有结点的左右子树交换

    /**
    *Created by salmon on 2021-9-29 23:30.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    /**
     * 要自底向上的交换,递归方法类似于后序遍历
     * @param BT 
     */
    void swap(BinTree BT){
        if(BT){
            swap(BT->Left);
            swap(BT->Right);
            BinTree temp = BT->Left;
            BT->Left = BT->Right;
            BT->Right = temp;
        }
    }
    

    删除二叉树中所有值为X的节点,以及它的左右子树

    /**
    *Created by salmon on 2021-10-1 00:23.
    **/
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    void delete(BinTree BT){
        if(BT){ //删除该树时应从底部开始删除,类似于后序遍历
            delete(BT->Left);
            delete(BT->Right);
            free(BT);
        }
    }
    
    /**
     * 比较方便的思路是层次遍历整棵树,如果找到X则删除它以及以它为根节点的子树
     * @param BT 
     * @param X 
     */
    void searchAndDelete(BinTree BT,ElementType X){
        if(BT == NULL) return;
        if(BT->Data == X) return delete(BT);
    
        Queue Q = initQueue();
        EnQueue(BT);
        while ( !isEmpty(Q) ){
            BinTree temp = DeQueue(Q);
            if(temp->Left){
                if(temp->Left->Data == X){ //查找时,我们让指针停留在父节点,用父节点的左右孩子来进行对比,这样有利于删除操作。
                    delete(temp->Left);
                    temp->Left = NULL;
                } else {
                    EnQueue(temp->Left);
                }
            }
            if(temp->Right){
                if(temp->Right->Data == X){
                    delete(temp->Right);
                    temp->Right = NULL;
                } else {
                    EnQueue(temp->Right);
                }
            }
        }
    }
    

    在二叉树中查找值为X的结点,并输出其所有的祖先结点

    /**
    *Created by salmon on 2021-10-3 23:48.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    void SearchAncestorOfX(BiTree T, ElementType X){
        InitStack(S);
        BiTree p = T; //p为遍历指针
        BiTree record = NULL; //record为辅组指针,指向最近访问过的结点。
    
        while(p || !StackIsEmpty(S)) {
            if(p) {
                push(S, p);
                p = p->lchild; //左孩子不空,一直向左走
            } else { //向右
                GetTop(S,p); //读栈顶结点(非出栈)
                if(p->data == X) {//如果栈顶结点的值等于x
                    pop(S,P);//先把当前结点pop了,因为只需要打印所有祖先
        
                    while(!StackIsEmpty(S)) {//将剩下的祖先依次打印
                        pop(S, p);
                        visit(p); //访问该结点
                    }
                    return 0; //执行完毕返回
                }
        
                if(p->rchild && p->rchild != record) {//若右子树存在,且未被访问过
                    p = p->rchild; //转向右
                    push(S, p);
                    p = p->lchild; //再走到最左
                } else {//否则,弹出结点
                    pop(S, p);
                    record = p; //记录最近访问过的结点
                    p = NULL; //结点访问完毕后,重置p指针,不然该结点又会重新入栈
                }
            }
        }
    }
    

    求一个二叉树的宽度

    此题有些异议,一些题目中的宽度是树每层结点个数的最大值,另一些题目中先将一颗树转换为完全二叉树(一层中相隔的结点之间有空位的话补上结点),宽度指转换后的树每层结点个数的最大值

    /**
    *Created by salmon on 2021-10-5 00:33.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    
    int GetWidth( BinTree BT ){ //在脑中想象一颗只有2层的满二叉树可以更好地理解
        if (BT == NULL) return 0;
        Queque Q = initQueue();//初始化队列
        EnQueque(BT);
        int front = 0, rear = 1,last = rear;
        int width = 1;
    
        while (front < rear) {
            BinTree curr = DeQueue();
            if ( curr -> Left != NULL ) {
                EnQueue(curr -> Left);
                rear++;
            }
            if( curr -> Right != NULL ) {
                EnQueue(curr -> Right);
                rear++;
            }
            front++;
            if(front == last){
                width = width < (rear - front) ? (rear - front) : width;
                last = rear;
            }
        }
        return width;
    }
    

    求以孩子兄弟表示法存储的树的叶子节点数

    /**
    *Created by salmon on 2021-10-10 23:29.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree firstChild;
        BinTree nextsibling;
    };
    
    int leaves(BinTree BT){
        if(BT == NULL){
            return 0;
        } else {
            if(BT->firstChild == NULL){
                return 1 + leaves(BT->nextsibling);
            } else {
                return leaves(BT->nextsibling) + leaves(BT->firstChild);
            }
        }
    }
    

    求以孩子兄弟表示法存储的树的深度

    /**
    *Created by salmon on 2021-10-10 23:40.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree firstChild;
        BinTree nextsibling;
    };
    
    int Height(BinTree BT){
        if(BT == NULL){
            return 0;
        } else {
            int childHigh = Height(BT->firstChild);
            int broChildHigh = Height(BT->nextsibling);
            return childHigh + 1 > broChildHigh ? childHigh + 1 : broChildHigh;
        }
    }
    

    希尔排序

    /**
    *Created by salmon on 2021-10-8 23:41.
    **/
    
    #include <stdio.h>
    /**
     * 希尔排序大多数流行的是三种写法,这里取第二种:其它几种可参考链接:https://wenku.baidu.com/view/aa8a4fd2b0717fd5360cdced.html
     * 希尔排序即将原数组s[]分割成多个以增量d为标准的数组,再对其进行直接插入排序 默认为非递减排序
     * 本程序使用第二种写法,也是大多数教科书上的写法,这种写法与我们所学的分组后进行直接插入排序不同
     * 此种是从数组第一个元素开始依次向后扫描,每次比较的都是相隔d个的元素,显然也是符合希尔排序逻辑的实现方式,只不过进行了化整体为部分的操作
     * @param s
     * @param n
     */
    void shellSort( int s[], int n ) { //n为有效数组长度,实际数组长度为n+1,s[0]作为数据保存单元
        int i,j,d;    //d为增量,j为已有序数组的最后一个元素下标
        for (d = n / 2; d >= 1; d = d / 2) {
            for( i = d + 1; i <= n; i++ ) {   //数组下标从分好组的第二个元素开始进行直接插入排序,第一个元素默认形成了一个有序数列
                s[0] = s[i];    //保存当前参照元素
                for ( j = i - d; j > 0 && s[0] < s[j]; j = j - d )  {
                    //自后向前扫描已有序数组,如果已有序数组中有大于当前参照元素的,就将该元素后移
                    s[j + d] = s[j];
                    //继续向前扫描,j向前移d个位置,当j小于或等于0时结束
                }
                s[j + d] = s[0];   //找到了应该插入的位置的前一个位置
            }
        }
    }
    
    
    int main()
    {
        int a[11],i;    /*定义数组及变量为基本整型*/
        printf("请输入 10 个数据:\n");
        for(i=1;i<=10;i++)
            scanf("%d",&a[i]);    /*从键盘中输入10个数据*/
            shellSort(a, 10);    /* 调用 shsort()函数*/
            printf("排序后的顺序是:\n");
            for(i=1;i<=10;i++){
                printf("%5d",a[i]);    /*输出排序后的数组*/
            }
                return 0;
    }
    

    即以如图顺序遍历:
    在这里插入图片描述

    快速排序

    /**
    *Created by salmon on 2021-10-12 23:15.
    **/
    
    #include <stdio.h>
    void QuickSort(int *, int, int); /*现在只需要定义一个函数, 不用交换还省了一个函数, 减少了代码量*/
    
    int main()
    {
        int i; //循环变量
        int a[] = {900, 2, -58, 3, 34, 5, 76, 7, 32, 4, 43, 9, 1, 56, 8,-70, 635, -234, 532, 543, 2500};
        QuickSort(a, 0, 20); /*引用起来很简单, 0为第一个元素的下标, 20为最后一个元素的下标*/
        printf("最终排序结果为:\n");
    
        for (i=0; i<21; ++i)
        {
            printf("%d ", a[i]);
        }
        printf("\n");
        return 0;
    }
    
    void QuickSort (int *a, int low, int high) {
        int i = low;
        int j = high;
        int key = a[low]; //把比较值保存起来,有的书上是使用a[0]保存起来,以你报考学校参考书为准
        if (low >= high) return;
    
        while (low < high) {
            while (low < high && key <= a[high]) {
                high--;
            }
            if (low != high) {
                a[low] = a[high];
                low++;
            }
            while (low < high && key >= a[low]) {
                low++;
            }
            if (low != high) {
                a[high] = a[low];
                high--;
            }
        }
    
        //此时low == high ,已经找到key的最终位置
        a[low] = key; //此时以key为分界线将序列分成左右两部分
        QuickSort(a, i, low - 1); //用同样的方式对分出来的左边的部分进行同上的做法
        QuickSort(a, low + 1, j); //用同样的方式对分出来的右边的部分进行同上的做法
    }
    

    结果:在这里插入图片描述

    冒泡排序

    /**
    *Created by salmon on 2021-10-13 23:42.
    **/
    #include <stdio.h>
    
    void BubbleSort( int num[], int length ){ //num为传入的数组,length为数组长度,这里用从后往前冒泡
        for (int i = 0; i < length; i++) {
            int flag = 0;
            for (int j = length - 1; j > i; j--) {
                if(num[j] < num[j - 1]){
                    int temp = num[j - 1];
                    num[j - 1] = num[j];
                    num[j] = temp;
                    flag++;
                }
            }
            if(flag == 0){
                break;
            }
        }
    }
    
    int main()
    {
        int i;
        int a[] = {900, 2, -58, 3, 34, 5, 76, 7, 32, 4, 43, 9, 1, 56, 8,-70, 635, -234, 532, 543, 2500};
        BubbleSort(a, 21);
        printf("最终排序结果为:\n");
    
        for (i=0; i < 21; ++i){
            printf("%d ", a[i]);
        }
        printf("\n");
        return 0;
    }
    

    归并排序

    /**
    *Created by salmon on 2021-10-23 00:40.
    **/
    
    #include <stdio.h>
    #define Maxsize 100
    
    /**
     * 将num[low....mid]与num[mid + 1 ...high]合并成一个有序数组,升序
     * @param num
     * @param low
     * @param mid
     * @param high
     */
    void merge(int num[],int low,int mid,int high){
        int assist[Maxsize]; //定义一个辅助数组
        int i,j,cur;
        for (cur = low; cur <= high ; ++cur) {
            assist[cur] = num[cur];    //将A中数组复制到辅助数组中
        }
        for (i = low,j = mid + 1,cur = i; i <= mid && j <= high; cur++) { //比较两个数组,将较小的元素移动到左边
            if(assist[i] <= assist[j]){
                num[cur] = assist[i];
                i++;
            } else {
                num[cur] = assist[j];
                j++;
            }
        }
        
        //以下是当两个中有某一个数组率先扫描完成时所需要做的操作,即将剩余数按顺序放入到原数组中
        while (i <= mid) {
            num[cur] = assist[i];
            cur++;
            i++;
        }
        while (j <= high) {
            num[cur] = assist[j];
            cur++;
            j++;
        }
    }
    
    void mergeSort(int num[],int low, int high){
        if(low < high){
            int mid = (low + high) / 2;
            mergeSort(num,low,mid);
            mergeSort(num,mid + 1,high);
            merge(num,low,mid,high);
        }
    }
    

    简单选择排序

    /**
    *Created by salmon on 2021-10-15 23:58.
    **/
    #include <stdio.h>
    
    
    void SelectSort(int a[],int length){ //选择排序
        int mixIndex,temp;
        int i,j;
        for(i = 0; i < length - 1; i++){ //每次循环数组,找出最小的元素,放在前面,前面的即为排序好的
            mixIndex = i; //假设最小元素的下标
            for(j = i + 1; j < length; j++){ //将上面假设的最小元素与数组比较,交换出最小的元素的下标
                if(a[j] < a[mixIndex])
                    mixIndex = j;
            }
            if(i != mixIndex) {
                temp = a[i];
                a[i] = a[mixIndex];
                a[mixIndex] = temp;
            }
        }
    }
    
    int main()
    {
        int i;
        int a[] = {900, 2, -58, 3, 34, 5, 76, 7, 32, 4, 43, 9, 1, 56, 8,-70, 635, -234, 532, 543, 2500};
        SelectSort(a, 21);
        printf("最终排序结果为:\n");
    
        for (i=0; i < 21; ++i){
            printf("%d ", a[i]);
        }
        printf("\n");
        return 0;
    }
    

    由二分查找优化的直接插入排序

    /**
    *Created by salmon on 2021-10-20 23:54.
    **/
    
    #include <stdio.h>
    
    //二分查找过程,查找key应插入的位置
    int binarySearch(int num[], int key, int low, int high) {
        int mid = -1;
        //循环直到low>high,此时low即为要插入的位置
        while (low <= high) {
            mid = (low + high) / 2;
            if (key <= num[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }
    
    //使用二分查找改进插入排序,使之最坏情况下时间复杂度为Θ(nlgn)
    void binInsertionSort(int num[], int n) {
        for (int i = 1; i < n; i++) {
            int key = num[i];
            int index = binarySearch(num, key, 0, i);
            if (index != i) {
                //如果需要移动,则往后移动一个位置,把位置腾出来
                for (int j = i - 1; j >= index; j--) {
                    num[j + 1] = num[j];
                }
                //把A[i]放到正确的位置
                num[index] = key;
            }
        }
    }
    
    int main()
    {
        int i;
        int a[] = {900, 2, -58, 3, 34, 5, 76, 7, 32, 4, 43, 9, 1, 56, 8,-70, 635, -234, 532, 543, 2500};
        binInsertionSort(a, 21);
        printf("最终排序结果为:\n");
    
        for (i=0; i < 21; ++i){
            printf("%d ", a[i]);
        }
        printf("\n");
        return 0;
    }
    

    带头结点链表,将小于第一个元素的结点放在其前面,大于放在后面

    /**
    *Created by salmon on 2021-10-24 23:24.
    **/
    
    #include <stdio.h>
    #include <stdlib.h>
    //带头结点链表,将小于第一个元素的结点放在其前面,大于放在后面
    typedef int ElementType;
    typedef struct Node *PtrToNode;
    struct Node {
        ElementType data;
        PtrToNode   next;
    };
    typedef PtrToNode List;
    
    void change( List L ){
        if(L -> next == NULL)	return;
    
        List p, end, first, pre;//end是末尾指针
        first = L -> next;	    //first指向L单链表的第一个元素
        p = first -> next;  	//p指向遍历当前结点
        pre = first;            //pre指向p的前一个结点
    
        while ( p ) {	//遍历单链表
            end = p->next;
            if(p -> data < first -> data){	//遇到比第一个元素小的则头插法插入
                pre->next = end;
                p->next = L->next;
                L->next = p;
                p = end;
            } else {	//其他则继续往后遍历
                p = p->next;
                pre = pre->next;
            }
        }
    }
    

    判断一颗树是否对称

    /**
    *Created by salmon on 2021-10-24 23:58.
    **/
    
    
    Definition for a binary tree node.
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
    };
    
    
    bool traversal(struct TreeNode* left,struct TreeNode *right){
        if(left == NULL && right == NULL){
            return true;
        }
        if(left == NULL || right == NULL) {
            return false;
        }
        if(left->val != right-> val) {
            return false;
        }
    
        return traversal(left->left, right->right) && traversal(left->right, right->left);
    }
    
    bool isSymmetric(struct TreeNode* root){
        if (root == NULL) {
            return true;
        }
        return traversal(root->left, root->right);
    }
    

    -------------------一些零碎的知识点-----------------------

    二叉树在线索化后,仍不能有效求解的问题

    在这里插入图片描述
    在这里插入图片描述

    存储结构的相关问题

    • 数据的逻辑结构包括:集合、线性结构、树形结构、图状结构或网状结构。
    • 数据的存储结构(物理结构)包括:顺序存储、链式存储、索引存储和散列存储。

    在这里插入图片描述

    展开全文
  • 该资源为江西师范大学869C语言程序设计与数据结构历年考研真题汇编,资源高清无水印哦! 该资源为江西师范大学869C语言程序设计与数据结构历年考研真题汇编,资源高清无水印哦!
  • 该资源为华东师范大学839数据结构(含C语言程序设计)历年考研真题汇编,资源高清无水印哦!
  • 例如:ASCII码排序;单链表;三元组;最大公约数和最小公倍数等等。 每一个都有大量注解。
  • C语言数据结构 习题和答案 供考研和自学的人员参考
  • 2011广东工业大学831数据结构C语言真题与答案解析 2012广东工业大学831数据结构C语言真题与答案解析 2013广东工业大学831数据结构C语言真题与答案解析 2014广东工业大学831数据结构C语言真题与答案解析 2015...
  • 6套题啊 我该要60分的 北航 数据结构C语言程序设计991 高清
  • 教学笔记,基础课程笔记,适合考研复习基础比较薄弱同学,适合教师备课。网络上那么多资源,不过还是这个比较好,因为权威。。
  • 2010-北航考研真题数据结构C语言程序设计2010
  • 重庆工商大学 831 数据结构与 C 语言考研真题及答案 2021 年重庆工商大学计算机科学与信息工程学院人工智 能学院 831 数据结构与 C 语言程序设计考研全套 目录 说明本全套共包括 5 种电子书84 个高清视频 共68 课时4...
  • 该资源为2012-2019年沈阳农业大学931数据结构C语言考研真题,资源高清无水印哦!
  • 目 录 第1部分 华中师范大学874数据结构C语言程序设计专业课介绍 第2部分 华中师范大学874数据结构C语言程序设计考研真题 2015年华中师范大学874数据结构C语言程序设计考研真题 第3部分 其他院校考研真题 2017...
  • 数据结构》知识梳理,适合考前复习,高分冲刺。包含大量习题,偷偷告诉你,考试就考这个

    整理的算法模板合集: ACM模板


    本文《数据结构知识梳理》的全部内容的 Portable Document Format 版本全部 开 源 啦 !详见:我的所有优质博客全部 开 源 啦(我自己原创的《ACM模板》《算法全家桶》《算法竞赛中的初等数论》《数据结构知识梳理》)

    F o r w o r d Forword Forword

    准备开一个新坑,关于数据结构的这两天我们学校的数据结构课开课了,也都知道数据结构非常重要,虽然我已经把数据结构都给学完了,但是我学的还是非常浅的,只涉及到C++实现以及STL等对于ACM竞赛有用的东西,更多的是应用,基础的概念有些还是掌握的不是很熟练,以及我们开的课是用C语言版 的,而我更多的是用C++和python,所以我决定在数据结构学习之余,把课本上的一些重难点和各种C语言实现的代码整理一下发到博客里,根据我们学校的进度来更新(我也不是很想花太多的时间去完成这一项工程,毕竟我还要刷题和完成我的另外一个大项目算法竞赛学习笔记ACM模板 (模板先暂时搁置,现在主要把《算法竞赛进阶指南刷一遍》)的,没有太多的时间)。

    C语言版

    应该是每一章一个博客,顺便在每篇博客的最后放一些PAT上坑爹的知识点类的题,估计期末就是只考这个,最讨厌这种要死记硬背的东西了,哪有算法题有意思。

    数据结构(C语言版 第2版严蔚敏版)完整课后习题答案汇总

    非官方答案:

    数据结构(C语言版 第2版严蔚敏版)完整课后习题答案汇总

    官方答案:

    数据结构(C语言版)课后习题全套完整答案及详解 (答案由李冬梅老师撰写)

    数据结构(C语言版) 第 一 章 绪论 知识梳理 + 作业习题详解

    博客链接:

    数据结构(C语言版) 第 一 章 绪论 知识梳理 + 作业习题详解

    数据结构(C语言版) 第 二 章 线性表 知识梳理 + 作业习题详解

    博客链接:

    数据结构(C语言版) 第 二 章 线性表知识梳理 + 作业习题详解

    数据结构(C语言版) 第 三 章 栈与队列 知识梳理 + 作业习题详解

    博客链接:

    数据结构(C语言版) 第 三 章 栈与队列 知识梳理 + 作业习题详解

    数据结构(C语言版) 第 四 章 串、数组和广义表 知识梳理 + 作业习题详解

    博客链接:

    数据结构(C语言版) 第 四 章 串、数组和广义表 知识梳理 + 作业习题详详解

    数据结构(C语言版) 第 五 章 树与二叉树 知识梳理 + 作业习题详解

    博客链接:

    数据结构(C语言版) 第 五 章 树与二叉树 知识梳理 + 作业习题详解


    数据结构(C语言版) 第 六 章 图 知识梳理 + 习题详解

    博客链接:

    数据结构(C语言版) 第 六 章 图 知识梳理 + 习题详解

    数据结构(C语言版) 第 八 章 排序 知识梳理 + 习题详解

    博客链接:

    数据结构(C语言版) 第 八 章 排序 知识梳理 + 习题详解

    C++版

    【数据结构】——线性表

    【数据结构】——线性表


    【数据结构】单调栈和单调队列 详解+例题剖析

    【数据结构】单调栈和单调队列详解+例题剖析


    【树和二叉树】(四种遍历,建树)详解+二叉排序树(包含图像和相关习题)

    【树和二叉树】(四种遍历,建树)详解+二叉排序树(包含图像和相关习题)


    【堆,大根堆,小根堆,优先队列】 详解

    【堆,大根堆,小根堆,优先队列】详解


    【图论】图,实现图(三种方式),二分图 详解

    【图论】图,实现图(三种方式),二分图详解


    【数论/图论】树的计数,prufer(Prüfer)编码,Cayley公式及相应例题

    【数论/图论】树的计数,prufer(Prüfer)编码,Cayley公式及相应例题


    【最短路合集】(Dijkstra、SPFA、Floyd以及路径还原模板)

    最短路合集(Dijkstra、SPFA、Floyd以及路径还原模板)


    【图论】最小生成树算法(prim和kruskal详解及对比)

    【图论】最小生成树算法(prim和kruskal详解及对比)


    【并查集】

    【并查集】


    【树状数组】

    【树状数组】


    【线段树】 从入门到进阶(超清晰,简单易懂)

    【线段树】 从入门到进阶(超清晰,简单易懂)


    【可持久化线段树 (主席树)】

    【可持久化线段树(主席树)】


    注:如果您通过本文,有(qi)用(guai)的知识增加了,请您点个赞再离开,如果不嫌弃的话,点个关注再走吧,日更博主每天在线答疑 ! 当然,也非常欢迎您能在讨论区指出此文的不足处,作者会及时对文章加以修正 !如果有任何问题,欢迎评论,非常乐意为您解答!( •̀ ω •́ )✧

    展开全文
  • 该资源为2018年四川师范大学831C语言程序设计与数据结构考研真题,资源高清无水印哦!
  • C语言数据结构——简单易懂的代码大合集

    万次阅读 多人点赞 2019-03-17 14:24:14
    受众群体:有初级C语言语法基础的初学者、考前突击本科生、考研者 友情提醒:欢迎一切善意的建议与修改意见,但是拒绝无端的指责,自视清高的大神请右上角×掉,不浪费您时间 本人才疏学浅,知识有限,难免会出现疏漏...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,575
精华内容 2,230
关键字:

考研c语言数据结构

c语言 订阅
数据结构 订阅