首页 > 代码库 > 数据结构上机考试（楷神版）
数据结构上机考试（楷神版）
插入排序
#include<cstdio>
using namespace std;
const int maxn = 1111;
int array1[maxn];
int array2[maxn];
//1 2 4 7 -1
void insert(int v){
for(int i = 0;i <= v; i++){
if(i == v){ //如果需要插入到最后一个位置
array2[i] = array1[v];
return;
}
if(array2[i] > array1[v]){ //找到插入位置
//将位置空出来，也就是从这里开始的元素全部后移一位
for(int j = v; j > i; j--)
array2[j] = array2[j - 1];
array2[i] = array1[v];
return;
}
}
}
int main(){
int n;
printf("请输入带排序元素的个数:");
scanf("%d",&n);
printf("请输入集合元素的值:");
for(int i = 0; i < n; i++)
scanf("%d",&array1[i]);
//选择排序
array2[0] = array1[0];
for(int i = 1; i < n; i++)
insert(i); //将元素array1[i]进行插入
printf("排序之后的元素为:");
for(int i = 0; i < n; i++)
printf("%d ",array2[i]);
return 0;
}
二叉树操作
#include<cstdio>
#include<algorithm>
using namespace std;
struct Node{
int value; //节点值
Node *left; //左孩子结点
Node *right; //右孩子结点
};
int n;
int num = 0;//叶子结点个数
int num2 = 0;//树的深度
Node* BuildTree(int m){
if(m > n) return NULL;
printf("请输入%d/%d号结点的值:",m,n);
Node *node = (Node*)malloc(sizeof(Node));
int v;
scanf("%d",&v);
node -> value = http://www.mamicode.com/v;
node -> left = BuildTree(m * 2);
node -> right = BuildTree(m * 2 + 1);
return node;
}
void Pre(Node *node){ //前序遍历
if(node == NULL)
return;
printf("%d ",node -> value);
Pre(node -> left);
Pre(node -> right);
return;
}
void Mid(Node *node){ //中序遍历
if(node == NULL)
return;
Mid(node -> left);
printf("%d ",node -> value);
Mid(node -> right);
return;
}
void End(Node *node){ //后序遍历
if(node == NULL)
return;
Mid(node -> left);
Mid(node -> right);
printf("%d ",node -> value);
return;
}
void count_num(Node *node){
int son = 0;
if(node -> left == NULL) son++;
else count_num(node -> left);
if(node -> right == NULL) son++;
else count_num(node -> right);
if(son == 2)
num++;
return;
}
void count_deep(Node *node,int deep){
num2 = deep > num2 ? deep : num2;
if(node -> left != NULL)
count_deep(node -> left,deep + 1);
if(node -> right != NULL)
count_deep(node -> right,deep + 1);
return;
}
int main(){
printf("请输入二叉树的结点个数:"); scanf("%d",&n);
Node *root;
printf("请按照前序遍历的顺序输入节点值:\n");
root = BuildTree(1);
printf("前序遍历结果:");Pre(root);printf("\n");
printf("中序遍历结果:");Mid(root);printf("\n");
printf("后序遍历结果:");End(root);printf("\n");
count_num(root); //统计叶子结点个数
printf("二叉树的叶子结点个数为:");
printf("%d\n",num);
count_deep(root,1); //统计树的深度
printf("二叉树的深度为:");
printf("%d\n",num2);
}
冒泡排序
#include<cstdio>
using namespace std;
const int maxn = 1111l;
int main(){
int array[maxn];
int n;
printf("输入待排序元素的个数：");
scanf("%d",&n);
printf("请输入%d个集合元素:",n);
for(int i = 0; i < n; i++)
scanf("%d",&array[i]);
for(int i = 0; i < n; i++)
for(int j = 0; j < n - i - 1; j++){
if(array[j] > array[j + 1]){
int temp = array[j];
array[j] = array[j + 1];
array[j +1] = temp;
}
}
printf("排序之后集合元素为:");
for(int i = 0; i < n; i++)
printf("%d ",array[i]);
}
选择排序
#include<cstdio>
using namespace std;
const int maxn = 1111;
int array[maxn];
int main(){
int n,min;
printf("请输入集合的元素个数：");
scanf("%d",&n);
printf("请输入%d个集合元素的值:",n);
for(int i = 0; i < n; i++)
scanf("%d",&array[i]);
//进行选择排序
for(int i = 0; i < n; i++){
min = i;
for(int j = i + 1; j < n; j++){
if(array[j] < array[min])
min = j;
}
if(min != i){
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
printf("排序之后的集合为：");
for(int i = 0 ;i < n; i++)
printf("%d ",array[i]);
printf("\n");
}
有序链表的建立、插入、合并、删除指定结点
#include<cstdio>
#include<algorithm>
using namespace std;
/**************************
Shukai Han
[有序链表的建立、插入、
合并、删除指定结点]
**************************/
struct Node{ //结点结构体
int value;
Node *next;
};
void insert(Node *head,int value){ //向有序链表插入元素
Node *p = head -> next;
Node *q = head;
while(p != NULL){
if(p -> value > value){
Node *tmp = (Node*)malloc(sizeof(Node));
tmp -> value = http://www.mamicode.com/value;
q -> next = tmp;
tmp -> next = p;
return;
}
p = p -> next;
q = q -> next;
}
//如果需要在链表最后插入
Node *tmp = (Node*)malloc(sizeof(Node));
tmp -> value = http://www.mamicode.com/value; tmp -> next = NULL;
q -> next = tmp;
}
Node *CreateList(int n){
Node *head = (Node*)malloc(sizeof(Node)); //头结点内存申请
head -> next = NULL;
Node *q = head;
int v; //节点值
printf("请输入%d个链表元素的值:",n);
for(int i = 0; i < n; i++){
scanf("%d",&v);
insert(head,v);
}
return head;
}
void print(Node *head){ //链表的遍历
Node *now = head -> next;
printf("该链表的元素为: ");
while(now != NULL){
printf("%d ",now -> value);
now = now -> next;
}
printf("\n");
}
Node* combine(Node *head1,Node *head2){ //合并链表，储存在一条新的链表里返回
Node *head = (Node*)malloc(sizeof(Node));
head -> next = NULL;
Node *p = head1 -> next , *q = head2 -> next;
while(p != NULL){
insert(head,p -> value);
p = p -> next;
}
while(q != NULL){
insert(head,q -> value);
q = q -> next;
}
return head;
}
void Delete(Node *head,int pos){ //删除指定位置的链表结点
int now = 1;
Node *p = head;
Node *q = head -> next;
while(q != NULL){
if(now == pos){
p -> next = q -> next;
free(q);
return;
}
q = q -> next;
p = p -> next;
now++;
}
printf("删除错误!\n");
}
int main(){
int n1,n2;
Node *head1,*head2,*head;
printf("请输入链表1的元素个数:");
scanf("%d",&n1);
head1 = CreateList(n1);//创建链表函数
print(head1);
printf("请输入链表1的元素个数:");
scanf("%d",&n2);
head2 = CreateList(n2);//创建链表函数
print(head2);
head = combine(head1,head2); //链表的合并
print(head);
printf("请输入删除该链表的第几个元素:");
int k;
scanf("%d",&k);
Delete(head,k);
print(head);
}
有序顺序表的操作
#include<cstdio>
using namespace std;
const int maxn = 11111;
int List[maxn],L = 0;
int List2[maxn],L2 = 0;
void insert(int *_List,int &L,int v){ //将值为v的元素插入到长度为L顺序表_List
for(int i = 0; i <= L; i++){
if(i == L){ //如果是插入到最后
_List[L++] = v;
return;
}
if(_List[i] > v){
//从i开始的元素全部右移，腾出空位放置v
for(int j = L; j > i; j--)
_List[j] = _List[j - 1];
_List[i] = v;
L++; //顺序表加长
return;
}
}
}
void Delete(int *_List,int &L,int pos){ //删除长度为L顺序表中第pos个元素
if(pos <= 0 || pos > L){
printf("Error!\n");
return;
}
for(int i = pos - 1; i < L - 1; i++) //位置pos除的元素全部前移一位，覆盖
_List[i] = _List[i + 1];
L--; //链表缩短
printf("删除成功！\n");
return;
}
void combine(int *List1,int *List2,int &L1,int &L2){
//实现表的合并，结果储存在表1中，表2自动删除
for(int i = 0; i < L2 ; i++) //就是将表2的元素按顺序插入表1
insert(List1,L1,List2[i]);
while(L2 != 0) //删除表2
Delete(List2,L2,1);
}
void print(int *_List,int L){ //遍历顺序表
for(int i = 0 ;i < L; i++)
printf("%d ",_List[i]);
printf("\n");
}
int main(){
int n,pos;
//输入第一个顺序表
printf("请输入顺序表(1)元素个数:");
scanf("%d",&n);
printf("请输入%d个顺序表元素:",n);
for(int i = 0; i < n; i++){
int x;
scanf("%d",&x);
insert(List,L,x);
}
printf("顺序表中的元素为:");
print(List,L);
//输入第二个顺序表，操作同上
printf("请输入顺序表(2)元素个数:");
scanf("%d",&n);
printf("请输入%d个顺序表元素:",n);
for(int i = 0; i < n; i++){
int x;
scanf("%d",&x);
insert(List2,L2,x);
}
printf("顺序表中的元素为:");
print(List2,L2);
//删除操作测试，对表(1)进行删除操作
printf("请输出需要删除的位置:");
scanf("%d",&pos);
Delete(List,L,pos);
print(List,L);
combine(List,List2,L,L2);
print(List,L);
printf("表(2)的长度为: %d",L2);
return 0;
}
二分查找
#include<cstdio>
using namespace std;
/*************************
在一个有序序列中
查找一个数,判断其位置
*************************/
int main(){
int array[] = {1,2,3,4,5,6,7,8,9,100,200,300}; //集合
int L = 12; //表长度
int n,v;
printf("有序序列为:");
for(int i = 0; i < L; i++)
printf("%d ",array[i]);
printf("\n请输入需要查找的元素值:");
scanf("%d",&v);
int l = 0,r = L - 1,ok = 0;
while(l <= r){
int mid = (l + r) / 2;
if(array[mid] == v){
printf("%d为第%d个元素",v,mid + 1);
ok = 1; //标记为查找到了
break;
}
else if(array[mid] > v) r = mid;
else l = mid + 1;
}
if(!ok) printf("没有查找到指定元素\n");
}
数据结构上机考试（楷神版）