(数据结构)上级考试//

首页 > 代码库 > (数据结构)上级考试//

2024-08-09 06:58:47 217人阅读

//1. 有序顺序表插入及合并

#include<stdio.h>
#include<malloc.h>
typedef struct {
int l;
int *a;
}list;
int insert_(list &l,int v){

if(l.l == 0){ // 线性表有 0个元素直接插入
l.a[0] = v;
++l.l;
return 1;
}
else{
int wh;
for(wh = 0; wh < l.l; wh++){ // 找出需要插入的位置
if(l.a[wh] > v)
break;
}
for(int i = l.l-1; i >= wh; i--){ // 需要插入位置后的元素全部后移一位
l.a[i+1] = l.a[i];
}
l.a[wh] = v;
++l.l; // 不要忘记长度加一
return 1;
}
}

void con_(list &l,list &p){
for(int i=0;i<p.l;i++)
insert_(l,p.a[i]);

}
void print(list &p){
for(int i=0;i<p.l;i++)
{
printf("%d ",p.a[i]);
}
printf("\n");
}
int main(){
list p;
p.a=(int*)malloc(sizeof(int)*1000);
p.l=0;
list q;
q.a=(int*)malloc(sizeof(int)*1000);
q.l=0;
//初始化有序表1
for(int i=1;i<=5;i++)
{
// printf("%d ",p.l);
insert_(p,i);
}
printf("有序表1\n");
print(p);
//初始化有序表2
for(int i=6;i<=10;i++)
{
// printf("%d ",p.l);
insert_(q,i);
}
printf("有序表2\n");
print(q);
con_(p,q);
printf("合并\n");
print(p);
printf("插入元素吧");
insert_(p,99);
print(p);
system("pause");
}

// 2.实现有序顺序表插入及遍历，调试成功
#include<stdio.h>
#include<malloc.h>
typedef struct {
int l;
int *a;
}list;
int insert_(list &l,int v){

void print(list &p){
for(int i=0;i<p.l;i++)
{
printf("%d ",p.a[i]);
}
printf("\n");
}
int main(){
list p;
p.a=(int*)malloc(sizeof(int)*1000);
p.l=0;
list q;
q.a=(int*)malloc(sizeof(int)*1000);
q.l=0;
//初始化有序表
for(int i=1;i<=5;i++)
{
// printf("%d ",p.l);
insert_(p,i);
}
printf("有序表1\n");
print(p);

printf("插入元素吧");
insert_(p,99);
print(p);
system("pause");
}

// 3有序顺序表建立、删除指定序号节点及遍历，调试成功

#include<stdio.h>
#include<malloc.h>
typedef struct {
int l;
int *a;
}list;
int insert_(list &l,int v){

int del_(list &l, int sta){
if(sta > l.l || sta <= 0)
return 0;
sta--;
for(int i = sta; i < l.l-1; i++)
l.a[i] = l.a[i+1];
l.l--;
return 1;
}

printf("删除元素吧");
del_(p,1);
print(p);
// printf("被删除元素%d\n",m);
system("pause");
}

// 4有序单链表插入及合并

#include<stdio.h>
#include<stdlib.h>

typedef struct Node{
int data;
Node *next;
}*list,node;
void init_(list &p){
p=(node *)malloc(sizeof(node));
p->next=NULL;
}

int insert_(list & p,int v){
list l,s;
l=p;
s=(node *)malloc(sizeof(node));
if(l->next==NULL)
{
s -> data = http://www.mamicode.com/v;
l -> next = s;
s -> next = NULL;
return 1;
}

while(((l->next)->data) < v)
{
l=l->next;
if((l->next)==NULL)
break;
}

s->data=http://www.mamicode.com/v;
s->next=l->next;
l->next=s;
return 0;
}
int con(list & p,list &l){
list m=p,n=l;
while(m->next){
insert_(n,m->next->data);
m=m->next;
}
}
int print(list p){

while(p->next)
{

printf("%d ",p->next->data);
p=p->next;
}
printf("\n");
}
int main(){
int i,j,n;
list p;
list l;
init_(p);
init_(l);
for(i=5;i>0;i--)
{
insert_( p,i);
}
print(p);//链表1
for(i=6;i<10;i++)
{
insert_( l,i);
}
print(l);//链表2
con(l,p);
print(p);//合并

printf("输入插入元素：");
scanf("%d",&n);
insert_(p,n);
print(p);//插入后

system("pause");

}

//5 有序单链表插入及遍历
#include<stdio.h>
#include<stdlib.h>

typedef struct Node{
int data;
Node *next;
}*list,node;
void init_(list &p){
p=(node *)malloc(sizeof(node));
p->next=NULL;
}

int insert_(list & p,int v){
list l,s;
l=p;
s=(node *)malloc(sizeof(node));
if(l->next==NULL)
{
s -> data = http://www.mamicode.com/v;
l -> next = s;
s -> next = NULL;
return 1;
}

while(((l->next)->data) < v)
{
l=l->next;
if((l->next)==NULL)
break;
}

s->data=http://www.mamicode.com/v;
s->next=l->next;
l->next=s;
return 0;
}
int print(list p){

while(p->next)
{

printf("%d ",p->next->data);
p=p->next;
}
printf("\n");
}
int main(){
int i,j,n;
list p;
list l;
init_(p);
init_(l);
for(i=5;i>0;i--)
{
insert_( p,i);
}
print(p);//链表1
printf("输入插入元素：");
scanf("%d",&n);
insert_(p,n);
print(p);//插入后

system("pause");

}

// 6有序单链表建立、删除指定序号节点及遍历
#include<stdio.h>
#include<stdlib.h>

typedef struct Node{
int data;
Node *next;
}*list,node;

void init_(list &p){
p=(node *)malloc(sizeof(node));
p->next=NULL;
}

int insert_(list & p,int v){
list l,s;
l=p;
s=(node *)malloc(sizeof(node));
if(l->next==NULL)
{
s -> data = http://www.mamicode.com/v;
l -> next = s;
s -> next = NULL;
return 1;
}

while(((l->next)->data) < v)
{
l=l->next;
if((l->next)==NULL)
break;
}

s->data=http://www.mamicode.com/v;
s->next=l->next;
l->next=s;
return 0;
}
int del_(list & l,int n)
{
int i=0,m;
list p;
p=l;
while(p->next)
{
if(i==n-1)
{
m=p->next->data;
p->next=p->next->next;
}

i++;
p=p->next;
}
return m;
}

int print(list p){

while(p->next)
{

printf("%d ",p->next->data);
p=p->next;
}
printf("\n");
}
int main(){
int i,j,n;
list p;
list l;
init_(p);
init_(l);
for(i=5;i>0;i--)
{
insert_( p,i);
}
print(p);//链表1
printf("输入删除元素实际位置：");
scanf("%d",&n);
int m=del_(p,n);
print(p);//
printf("被删除元素%d\n",m);
system("pause");

}

// 7二叉树建立以及先序遍历,int型调试成功

#include "iostream" //cout,cin
#include<malloc.h> // malloc,remalloc
#include<stdio.h>
#include<conio.h>
using namespace std;

typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

// 构造空二叉树
void InitBiTree(BiTree &T)
{
T=NULL;
}
// 建立二叉树
void CreateBiTree(BiTree &T)
{
TElemType ch;
cin>>ch;
if(ch==0) // 空
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点

T->data=http://www.mamicode.com/ch;
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
}

// 先序遍历二叉树
void PreOrderTraverse(BiTree T)
{
if(T) // T不空
{

cout<<T->data<<" ";
PreOrderTraverse(T->lchild); // 再先序遍历左子树

PreOrderTraverse(T->rchild); // 最后先序遍历右子树

}
}

int main(){
BiTree p;
InitBiTree(p);
cout<<"测试二叉树的先序建立，请输入二叉树的节点数据(0代表空节点)"<<endl;
CreateBiTree(p);
cout<<"测试二叉树的遍历，先序遍历二叉树为"<<endl;
PreOrderTraverse(p);
system("pause");
return 0;
}

// 8二叉树建立以及中序遍历,int型调试成功

#include "iostream" //cout,cin
#include<malloc.h> // malloc,remalloc
#include<stdio.h>
#include<conio.h>
using namespace std;

typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

T->data=http://www.mamicode.com/ch;
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
}

// 先序遍历二叉树
void PreOrderTraverse(BiTree T)
{
if(T) // T不空
{

PreOrderTraverse(T->lchild); // 再先序遍历左子树
cout<<T->data<<" ";
PreOrderTraverse(T->rchild); // 最后先序遍历右子树

}
}

// 9二叉树建立以及后序遍历,int型调试成功

#include "iostream" //cout,cin
#include<malloc.h> // malloc,remalloc
#include<stdio.h>
#include<conio.h>
using namespace std;

typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

T->data=http://www.mamicode.com/ch;
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
}

// 先序遍历二叉树
void PreOrderTraverse(BiTree T)
{
if(T) // T不空
{

PreOrderTraverse(T->lchild); // 再先序遍历左子树

PreOrderTraverse(T->rchild); // 最后先序遍历右子树
cout<<T->data<<" ";
}
}

// 10二叉树求深度

#include "iostream" //cout,cin
#include<malloc.h> // malloc,remalloc
#include<stdio.h>
#include<conio.h>
using namespace std;

typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

T->data=http://www.mamicode.com/ch;
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
}

// 求二叉树的深度
int depth(BiTree root)
{
int ldepth,rdepth;
if(!root) return 0;
else{
ldepth = depth(root->lchild);
rdepth = depth(root->rchild);
return ldepth>rdepth?ldepth+1:rdepth+1;
}
}

int main(){
BiTree p;
InitBiTree(p);
cout<<"测试二叉树的先序建立，请输入二叉树的节点数据(0代表空节点)"<<endl;
CreateBiTree(p);
cout<<"测试二叉树的深度，二叉树的深度为"<<endl;
cout<<depth(p);
system("pause");
return 0;
}

// 11统计二叉树节点数

#include "iostream" //cout,cin
#include<malloc.h> // malloc,remalloc
#include<stdio.h>
#include<conio.h>
using namespace std;

typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

T->data=http://www.mamicode.com/ch;
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
}

// 统计节点数
int tmp=0;
void tj(BiTree T)
{
if(T) // T不空
{

tmp++;
tj(T->lchild); // 再先序遍历左子树

tj(T->rchild); // 最后先序遍历右子树

}
}

int main(){
BiTree p;
InitBiTree(p);
cout<<"测试二叉树的先序建立，请输入二叉树的节点数据(0代表空节点)"<<endl;
CreateBiTree(p);
cout<<"测试二叉树的节点数"<<endl;
tj(p);
cout<<tmp;
system("pause");
return 0;
}

// 12折半查找(非递归) 调试成功

#include<iostream>
#include<malloc.h>
using namespace std;

typedef int KeyType;
typedef struct // 数据元素类型
{
int key;
}ElemType;

typedef struct
{
ElemType *elem; // 数据元素存储空间基址，建表时按实际长度分配，0号单元留空
int length; // 表长度
}SSTable;

//----------------------------------------折半查找操作---------------------------------//

// 创建静态表
void Creat_Seq(SSTable &ST,int n)
{ // 操作结果：由含n个数据元素的数组r构造静态顺序查找表ST(见图9?2)
int i,k;
ST.elem=(ElemType*)calloc(n+1,sizeof(ElemType));// 动态生成n+1个数据元素空间(0号单元不用)
// if(!ST.elem)
// exit(ERROR);
for(i=1;i<=n;i++){
cin>>k;
ST.elem[i].key=k;
}
// ST.elem[i].key=r[i-1]; // 将数组r的值依次赋给ST
ST.length=n;
}

// 折半查找
int Search_Bin(SSTable ST,KeyType key)
{ // 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则返回
// 该元素在表中的位置；否则返回0。算法9.2
int low,high,mid;
low=1; // 置区间初值
high=ST.length;
while(low<=high)
{
mid=(low+high)/2;
if (ST.elem[mid].key == key) // EQ(key,ST.elem[mid].key) // 找到待查元素
return mid;
else if (ST.elem[mid].key>key) // LT(key,ST.elem[mid].key)
high=mid-1; // 继续在前半区间进行查找
else
low=mid+1; // 继续在后半区间进行查找
}
return 0; // 顺序表中不存在待查元素
}

//-------------------------------main函数测试------------------------------//

int main(){
int n;
SSTable T;
cout<<"测试静态表的输入，请输入静态数据表元素的个数以及各元素"<<endl;
cin>>n;
Creat_Seq(T,n);
cout<<"静态表创建成功，请输入查找数据"<<endl;
cin >> n;
cout<<"查找的数据在"<<Search_Bin(T,n)<<endl;
system("pause");
return 0;
}
// 12折半查找(递归) 调试成功

#include<iostream>
#include<malloc.h>
using namespace std;

typedef int KeyType;
typedef struct // 数据元素类型
{
int key;
}ElemType;

typedef struct
{
ElemType *elem; // 数据元素存储空间基址，建表时按实际长度分配，0号单元留空
int length; // 表长度
}SSTable;

//----------------------------------------折半查找操作---------------------------------//

// 创建静态表
void Creat_Seq(SSTable &ST,int n)
{ // 操作结果：由含n个数据元素的数组r构造静态顺序查找表ST(见图9?2)
int i,k;
ST.elem=(ElemType*)calloc(n+1,sizeof(ElemType));// 动态生成n+1个数据元素空间(0号单元不用)
// calloc 和malloc是一样的效果，初始值calloc为0,malloc为乱值
// if(!ST.elem)
// exit(ERROR);
for(i=1;i<=n;i++){
cin>>k;
ST.elem[i].key=k;
}
// ST.elem[i].key=r[i-1]; // 将数组r的值依次赋给ST
ST.length=n;
}

// 折半查找，递归
int Search_Bin(SSTable ST,int low, int high,int key)
{
int mid;
if(low>high)
return 0; // 顺序表中不存在待查元素
else{
mid = (low+high) / 2;
if(ST.elem[mid].key==key)
return mid;
if(key>ST.elem[mid].key)
return Search_Bin(ST,mid+1,high,key); /*在序列的后半部分查找*/
else
return Search_Bin(ST,low,mid-1,key); /*在序列的前半部分查找*/
}
}

//-------------------------------main函数测试------------------------------//

int main(){
int n,k;
SSTable T;
cout<<"测试有序静态表的输入，请输入静态数据表元素的个数以及各元素"<<endl;
cin>>n;
Creat_Seq(T,n);
cout<<"静态表创建成功，请输入查找数据"<<endl;
cin >> k;
cout<<"查找的数据在第"<<Search_Bin(T,1,n,k)<<"位"<<endl;
system("pause");
return 0;
}
//13二叉排序树
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
typedef struct tree{
int v;
tree *left,*right;
tree():left(NULL),right(NULL){}
}*root,node;
int creat_tree(root & t,int val){
if(t == NULL){
t = (node*)malloc(sizeof(node));
t -> v = val;
t -> right = t -> left = NULL;
return 1;
}
if(val == t->v)
return 0;
if(val > t -> v)
return creat_tree(t -> right, val); // 递归搜索要插入的位置，小于该节点一定在左侧
else
return creat_tree(t -> left, val);
}
int midorder(root &t){ // 其实先序中序后序遍历程序都差不多，只不过跟输出的位置不一样罢了
if(t){
if(midorder(t->left)){
printf("%d ",t->v);
if(midorder(t->right))
return 1;
}
}
return 1;
}
int main (){
root t;
int n;
scanf("%d",&n);
t = NULL;
for(int i = 0; i < n; i++){
int val;
scanf("%d",&val);
creat_tree(t,val); //abd e cf g .(.之前的全部输入包括空格)
}
midorder(t);
printf("\n");
system("pause");
return 0;
}

// 14冒泡排序

#include <stdio.h>
#include<iostream>
using namespace std;

// 冒泡排序算法
void bubblesort(int k[],int n){ /*冒泡排序*/
int i,j,tmp ,flag = 1;
for(i=1;i<=n-1 && flag == 1;i++){ /*执行n-1趟排序*/
flag = 0; // 用来判断数据已经排好序
for(j=1;j<=n-i;j++){
if(k[j]<k[j+1]){ /*数据交换*/
tmp = k[j+1];
k[j+1] = k[j];
k[j] = tmp;
flag = 1;
}
}
}
}

int main()
{
int i,n; /*初始化序列，a[0]可任意置数*/
cout<<"请输入数据个数，以及数据元素"<<endl;
cin>>n; int a[n];
for(i=1;i<=n;i++) /*显示原序列之中的元素*/
cin>>a[i];
bubblesort(a,n); /*执行冒泡排序*/
cout<<"冒泡排序后的顺序为"<<endl;
for(i=1;i<=n;i++)
cout<<a[i]<<" "; /*输出排序后的结果*/
getchar();
return 0;
}

// 15 直接选择排序
#include <stdio.h>
#define M 20
void insert_sort(int a[],int n)
//待排序元素用一个数组a表示，数组有n个元素
{
int i,j;
int temp;
for (i=1;i<n;i++) //i表示插入次数，共进行n-1次插入
{
temp=a[i]; //把待排序元素赋给temp，temp在while循环中并不改变，这样方便比较，并且它是要插入的元素
j=i-1;
//while循环的作用是将比当前元素大的元素都往后移动一个位置
while ((j>=0)&& (temp<a[j])){
a[j+1]=a[j];
j--; // 顺序比较和移动,依次将元素后移动一个位置
}
a[j+1]=temp;//元素后移后要插入的位置就空出了，找到该位置插入
}
}
int main(){
int a[M];
int i,n;
printf("请输入元素个数:\n");
scanf("%d",&n);
printf("请输入元素:\n");
for (i=0; i<n; i++)
scanf("%d",&a[i]);
insert_sort(a,n);
for(i=0;i<n;i++)
printf("%d\t",a[i]);
return 0;
}

// 16简单选择排序

#include <stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;

// 简单选择排序
void SelectSort(int r[], int length)
{ // 对记录数组r做简单选择排序，length为数组的长度
int k,i,j,x; int n=length;
for ( i=1 ; i<=n-1; ++i)
{
k = i;
for ( j=i+1 ; j<=n ; ++j)
if(r[j] < r[k] ) k=j;
if (k!=i)
{
x= r[i]; r[i]= r[k]; r[k]=x;
}

}

int main()
{
int i,n; /*初始化序列，a[0]可任意置数*/
cout<<"请输入数据个数，以及数据元素"<<endl;
cin>>n; int a[n];
for(i=1;i<=n;i++) /*显示原序列之中的元素*/
cin>>a[i];
SelectSort(a,n); /*执行冒泡排序*/
cout<<"选择排序后的顺序为"<<endl;
for(i=1;i<=n;i++)
cout<<a[i]<<" "; /*输出排序后的结果*/
getchar();
system("pause");
return 0;
}

(数据结构)上级考试//

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > (数据结构)上级考试//

(数据结构)上级考试//

看完仍有疑问？有类似问题直接问程序猿