师大数据结构历年真题-创新互联

//2014数据结构865

//1.单链表结点的删除
LNode Delete(LinkList &L,int K){LNode p=L->next;
	LNode pre=L;
	while(p!=NULL){if(p->data>K){	pre->next=p->next;
			Delete(p);
			return p;
		}
		pre=p;
		p=p->next;
	}
	return -1;
}

//2.求邻接表存储有向图顶点的出度
typedef struct ArcNode{int adjvex;
	struct ArcNode *nextarc;
}ArcNode;
typedef struct{VertexType data;
	struct ArcNode *firstArc;
}VNode;
typedef struct{VNode adjlist[MAX_NUM];
	int v,e;
}ALGraph;
void OutDu(ALGraph G,int h){int n=0;
	ArcNode *e;
	while(G.adjlist[h].firstArc!=0)
		n++;
		e=G.adjlist[h].firstArc->nextarc;
		G.adjlist[h].firstArc=e;
	}
	print("%d",n);
}

//3.快速排序
void QuickSort(ElemType A[],int low,int high){if(lowint pivotpos=Partition(A,low,high);
		QuickSort(A,low,pivotpos-1);
		QuickSort(A,pivotpos+1,high);
	}
}
int Partition(ElemType A[],int low,int high){int pivot=A[low];
	while(lowwhile(low=pivot) j--;
		A[low]=A[high];
		while(lowif(T!=NULL){visit(T);
		L_Order(T->lchild);
		R_Order(T->rchild);
	}
}
void L_Order(BiTree T){if(T!=NULL){L_Order(T->lchild);
		visit(T);
		L_Order(T->rchild);
	}
}
void R_Order(BiTree T){if(T!=NULL){R_Order(T->rchild);
		visit(T);
		R_Order(T->lchild);
	}
}

//2015数据结构865

//1.单链表结点的删除
void Delete(LinkList &L,int k){LNode p=L->next;
	LNode pre=L;
	while(p!=NULL){if(p->data	pre->next=p->next;
			free(p);
			p=pre->next;
		}
		pre=p;
		p=p->next;
	}
}

//2.求有向图顶点的入度和出度
typedef struct ArcNode{int adjvex;
	ArcNode *nextarc;
}ArcNode;
typedef struct{VertexType data;
	ArcNode *firstarc;
}VNode;
typedef struct{VNode adjlist[MAX_NUM];
	int v,e;
}ALGraph;
void OutDu(ALGraph G){int n=0,i=0;
	ArcNode *e;
	for(i=0;iwhile(G.adjlist[i].firstarc!=NULL){	n++;
			e=G.adjlist[i].firstarc->nextarc;
			G.adjlist[i].firstarc=e;
		}
		printf("%d",n);
		n=0;
	}
}
void InDu(ALGraph G){int i,j,n=0;
	int A[G.v];
	ArcNode *e;
	for(i=0;iA[i]=0;
	}
	for(j=0;jwhile(G.adjlist[j].firstarc!=NULL){	A[G.adjlist[j].firstarc->adjvex]++;
			e=G.adjlist[j].firstarc->nextarc;
			G.adjlist[j].firstarc=e;
		}
	}
	for(i=0;iprintf("%d",A[i]);
	}
}

//3.快速排序-略

//4.将二叉树叶子结点形成一个单链表
typedef struct BiTree{char data;
	struct BiTree *lchild;
	struct BiTree *rchild;
};
struct BiTree *pre=NULL;
struct BiTree *h=(struct BiTree *)malloc(sizeof(struct BiTree));
BiTree *LeafLink(BiTree *b){if(b){LeafLink(b->lchild);
		if(!b->lchild && !b->rchild){//链表加入条件
			if(pre==NULL){//处理第一个结点
				h=b;
				pre=b;
			}else{//使用尾插法不断插入叶子节点，使用pre指针指向最后一个结点
				pre->rchild=b;
				pre=b;
			}
		}
		LeafLink(b->rchild);
		pre->rchild=NULL;
	}
	return h;
}

//2016数据结构865

//1.单向链表结点的删除 略

//2.求二叉树树高
int Tree_Height(BiTree *T){int h=0,h1=0,hr=0;
	if(T==NULL){return 0;
	}else{h1=Tree_Height(T->lchild);
		hr=Tree_Height(T->rchild);
		h=((h1>hr)?h1:hr)+1;
		return h;
	}
}

//3.有向图邻接表表示增加一条边
typedef struct VNode{int data;
	struct VNode *next;
}VNode, *NodeList;
typedef struct{NodeList V[MAX_NUM];
	int vexnum,arcnum;
}ALGraph;
void InsertArc(ALGraph G){int c1,c2;
	cin>>c1>>c2;
	NodeList p1=new VNode;
	p1->data=c2;
	p1->next=G.V[c1]->next;
	G.V[c1]->next=p1;
}

//4.求一维数组递归
int Sum(int A[],int len){if(len==1){return A[len-1];
	}else{return A[len-1]+Sum(A,len-1);
	}
}

//2017数据结构865

//1.递归计算平均值
int Average(int A[],int i){if(i==0) return A[0];
	else return (Average(A[i-1],i-1)*(i-1)+A[i-1])/i;
}

//2.判断括号匹配函数
void ExpIsCorrect(char exp[],int n){SeqStack mystack;
	int i;
	char c;
	StackInitiate(&mystack);
	for(i=0; iif(exp[i] == "(") StackPush(&mystack, exp[i]);
		else if(exp[i] == ")" && StackNotEmpty(mystack)){	StackTop(mystack,&c);
			if(c == "("){		StackPop(&mystack,&c);
			}else{		printf("左右括号不匹配\n");
				return;
			}
		}
		else if(exp[i] == ")" && !StackNotEmpty(mystack)){	printf("右括号多于左括号\n");
			return;
		}
	}
	if(StackNotEmpty(mystack)){printf("左括号多于右括号\n");
	}else{printf("括号完全匹配\n");
	}
}

//3.邻接表存储图的顶点出度统计
void InDegree(AdjGraph G){Node *p;
	int i,inD;
	for(i=0;iinD=0;
		p=G.adj[i].first;
		while(p){	inD++;
			p=p->next;
		}
		printf("顶点%d的出度为%d\n",i,inD);
	}
}

//4.二叉树的层序遍历
void LevelOrder(BiTree T){InitQueue(Q);
	BiTree p;
	EnQueue(Q,T);
	while(!IsEmpty(Q)){DeQueue(Q,p);
		visit(p);
		if(p->lchild!=NULL)
			EnQueue(Q,p->lchild);
		if(p->rchild!=NULL)
			EnQueue(Q,p->rchild);
	}
}

//2018数据结构865

//1.折半查找
int Binary_Search(SeqList L,ElemType key){int low=0,high=L.len-1,mid;
	while(lowmid = (low+high)/2;
		if(L.Elem[mid]==key){	return mid;
		else if(L.Elem[mid]	low=mid+1;
		}else{	high=mid-1;
		}
	}
	return -1;
}

//2.苹果问题 略

//3.求树高
int Height(BiTree T){if(T==NULL) return 0;
	int lh=Height(T->lchild);
	int rh=Height(T->rchild);
	if(lhreturn rh+1;
	}else{return lh+1;
	}
}

//4.二叉树层序遍历 略

//2019数据结构865

//1.二叉树先序遍历 略

//2.希尔排序
void ShellSort(ElemType A[],int n){for(int dk=n/2;dk>=1;dk=dk/2){for(int i=dk+1;i<=n;i++){	if(A[i]		A[0]=A[i];
				for(int j=i-dk;j>0 && A[0]A[j+dk]=A[j];
				}
				A[j+dk]=A[0];
			}
		}
	}
}

//3.邻接表建图
int MaxNum=2010;
int n=0;
vectoradj[MaxNum];
void CreatMap(){scanf("%d",&n);
	for(int i=1;i<=n;i++){int m=0;
		scanf("%d",&m);
		for(int j=1;j<=m;j++){	int next;
			scanf("%d",&next);
			adj[next].push_back(i);
		}
	}
}

//4.十字链表的输出

//十字链表存储表示
typedef struct OLNode{int i,j;//该非零元的行标和列标
	ElemType e;//非零元元素值
	OLNode *right,*down;//该非零元所在行表和列表
}OLNode, *OLink;
typedef struct{OLNode *rhead,*chead;//行表和列表头指针
	int mu,nu,tu;//稀疏矩阵的行数、列数和非零元数
}CrossList;
void OutCSM(CrossList M,void(*Out3)(int,int,int)){int i;
	OLink p;
	for(i=1;i<=M.mu;i++){p=M.rhead[i];//p指向每一行的基址
		while(p){	Out3(p->i,p->j,p->e);
			p=p->right;
		}
	}
}

//2020数据结构865

//1.非递归实现二叉树中序遍历
void InOrder2(BiTree T){InitStack(S);
	BiTree p=T;
	while(p||!IsEmpty(S)){if(p){	Push(S,p);
			p=p->lchild;
		}else{	Pop(S,p);
			visit(p);
			p=p->rchild;
		}
	}
}

//2.拓扑排序
vectorG[MAXV];
int n,InDegree[MAXV];
bool ToPo_Logical_Sort(){int num=0;
	queueq;
	for(int i=0;iif(InDegree[i]==0){	q.push(i);
		}
	}
	while(!q.empty()){int u=q.front();
		q.pop();
		for(int j=0;j	int v=G[u][j];
			InDegree[v]--;
			if(InDegree[v]==0)
				q.push(v);
		}
		G[u].clear();
		num++;
	}
	if(num==n) return true;
	else return false;
}

//3.改进的快速排序算法 略

//2021数据结构865

//1.递归实现折半查找
int Binary_Search(SeqList L,ElemType key,int low,int high){if(lowmid=(low+high)/2;
		if(L.elem[mid]==key)
			return mid;
		else if(L.elem[mid]for(int v=0;vvisit(v);
	visited[v]=true;
	for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){if(!visited[w])
			DFS(G,w);
	}
}

//3.二叉排序树进行排序
void Creat_BST(BiTree &T,KeyType str[],int i){T=NULL;
	int i=0;
	while(iBST_Insert(T,str[i]);
		i++;
	}
}
int BST_Insert(BiTree &T,KeyType k){if(T==NULL){T=(BiTree)malloc(sizeof(BSTNode));
		T->data=k
		T->lchild=T->rchild=NULL;
		return 1;
	}
	else if(k==T->data)
		return 0;
	else if(kdata)
		return BST_Insert(T->lchild,k);
	else
		return BST_Insert(T->rchild,k);
}

//2021数据结构885

//1.BFS算法
bool visited[MAX_NUM];
void BFSTraverse(Graph G){for(int i=0;ivisit(v);
	visited[v]=true;
	EnQueue(Q,v);
	while(!IsEmpty(Q)){DeQueue(Q,v);
		for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){	if(!visited[w]){		visit(w);
				visited[w]=true;
				EnQueue(Q,w);
			}
		}
	}
}

//2.BFS求单源最短路径问题
void BFS_MIN_Distance(Graph G,int u){for(int i=0;id[i]=9999;
	}
	visited[u]=true;
	d[u]=0;
	EnQueue(Q,u);
	while(!IsEmpty(Q)){DeQueue(Q,u);
		for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){	if(!visited[w]){		visited[w]=true;
				d[w]=d[u]+1;
				EnQueue(Q,w);
			}
		}
	}
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧