关于计科专业数据结构的一些算法
很多人考上了计算机专业阿，就从他们嘴里听到一些这样的抱怨“我X这TM怎么学”“老师讲的啥X玩应啊”“啥事数据结构”事实上呢，很多学科，包括操作原理等等，都会有这些或多或少的“批判”包括我阿，这样的话也没少说。
那么今天呢，敲黑板！我们不讲这个数据结构，这篇文章的目的呢，是为了让即将考上这个计科专业的同学啊，先了解一下，咱们的这个课程内容中的几个主要的算法。
目的是啥呢？目的是为了让你们在开学前，对这个科目有信心，一个充分的了解和准备。
在这里整理了一些关于计科专业数据结构学科上面的一些算法，怎么说呢？前半部分（重点分析部分）是比较难的期末应该不会考，后半部分（题型分类部分）的算法全掌握，并且上课学的基本知识能理解，期末80+没问题。
还有啊，我有个个人博客，那上面的帖子更新的肯定会比公众号要快，这篇帖子也是从我博客上搬运下来的，博客上面有执行的截图，公众号没有展示，希望大家能多多关注吧！
TheMrxk个人博客
https://blog.orghub.cn
重点分析
简单题型 栈 队列 树 排序
简单题型
往下翻……………
栈
#include <iostream>
using namespace std;
const int stackmax=100;//c初始值分配量
typedef char st;
typedef struct{
char *base;
char *top;
int stacksize;
}stack;
int initstack(stack &s){//初始化
s.base=new st[stackmax];//为顺序栈动态分配d一个最大容量为stachkmax的数组空间
if (!s.base) {
return 0;//储存分配空间失败
}
s.top=s.base;//top初始为base，空栈
s.stacksize=stackmax;//置为栈的最大容量
return 1;
}
int putstack(stack &s,char e){//入栈
if(s.top-s.base==s.stacksize){//当相等时为满栈
cout<<"满栈"<<endl;
return 0;
}
*s.top=e;//元素e压入栈顶
s.top++;//栈顶指针+1
return 1;
}
char gettop(stack s){
if(s.top!=s.base)
cout<<*(s.top-1);//取q栈顶指针
return 0;
}
int outstack(stack &s,int e){
if (s.top==s.base) {
return 0;
}
e=*--s.top;//将d栈顶元素给e向下移一位
return 1;
}
void disp(stack s){
long int i;
for(i=0;i<s.top-s.base;i++){
cout<<s.base[i];
}
cout<<endl;
}
int main(){
char e;
stack s;
initstack(s);
putstack(s,'A');
putstack(s,'B');
putstack(s,'C');
putstack(s,'D');
cout<<"栈S为：";
disp(s);
cout<<"栈顶元素为：";
e=gettop(s);
cout<<e<<endl;
outstack(s,e);
cout<<"栈顶出栈后的S：";
disp(s);
return 0;
}队列
#include<iostream>
using namespace std;
const int MAXQSIZE=6;
typedef char QElemType;
typedef struct
{
QElemType *base;
int front ;
int rear;
} SqQueue;
int InitQueue(SqQueue &Q)
{
Q.base= new QElemType[MAXQSIZE];
if(!Q.base)
return 0;
Q.front =Q.rear=0;
return 1;
}
int EnQueue( SqQueue &Q,QElemType e)
{
if((Q.rear+1)%MAXQSIZE==Q.front)//队满
{
cout<<"错误"<<endl;
}
Q.base[Q.rear] =e;//新元素插入队尾
Q.rear=(Q.rear+1)%MAXQSIZE;//队尾指针向后移动一位
return 1;
}
int lengt(SqQueue &Q)//求队长度
{
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
int deleteQ(SqQueue &Q,QElemType &e)
{
if(Q.rear==Q.front)//队空
return 0;
e=Q.base[Q.front];//保存对头元素
Q.front=(Q.front+1)%MAXQSIZE;//队头指针向后移动一位
return 1;
}
int DisQ(SqQueue Q)
{
int m,i;
m=lengt(Q);
if(m==0)
cout<<"空队列";
if((Q.rear+1)%MAXQSIZE==Q.front)
cout<<"队满"<<endl;
for(i=Q.front; i%MAXQSIZE!=Q.rear;i++)
cout<<Q.base[i];
cout<<endl;
return 0;
}
int main()
{
SqQueue Q;
QElemType e;
InitQueue(Q);
DisQ(Q);
EnQueue(Q,'A');
EnQueue(Q,'B');
EnQueue(Q,'C');
EnQueue(Q,'D');
cout<<"长度=";
cout<<lengt(Q);
cout<<"队列为=";
DisQ(Q);
deleteQ(Q,e);
cout<<"长度=";
cout<<lengt(Q);
cout<<"队列为=";
DisQ(Q);
EnQueue(Q,'E');
cout<<"长度=";
cout<<lengt(Q);
cout<<"队列为=";
DisQ(Q);
EnQueue(Q,'F');
cout<<"队列为=";
DisQ(Q);
return 0;
}树
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef int InfoType;
typedef int KeyType; //假定关键字类型为整数
typedef struct node //结点类型
{
KeyType key; //关键字项
InfoType otherinfo; //其它数据域，InfoType视应用情况而定，下面不处理它
struct node *lchild,*rchild; //左右孩子指针
}BSTNode;
typedef BSTNode *BSTree; //BSTree是二叉排序树的类型
//在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NULL
BSTNode *findbst(BSTree t,KeyType key){
if(t==NULL||key==t->key)
return t;
if(key<t->key)
return findbst(t->lchild,key);
else
return findbst(t->rchild,key);
}
void InsertBST(BSTree *T,int key)
{ //插入一个值为key的节点到二叉排序树中
BSTNode *p,*q;
if((*T)==NULL)
{ //树为空树
(*T)=(BSTree)malloc(sizeof(BSTNode));
(*T)->key=key;
(*T)->lchild=(*T)->rchild=NULL;
}
else
{
p=(*T);
while(p)
{
q=p;
if(p->key>key)
p=q->lchild;
else if(p->key<key)
p=q->rchild;
else
{
cout<<endl<<"该二叉排序树中含有关键字为"<<key<<"的节点!"<<endl;
return;
}
}
p=(BSTree)malloc(sizeof(BSTNode));
p->key=key;
p->lchild=p->rchild=NULL;
if(q->key>key)
q->lchild=p;
else
q->rchild=p;
}
}
BSTree CreateBST(void)
{ //输入一个结点序列，建立一棵二叉排序树，将根结点指针返回
BSTree T=NULL; //初始时T为空树
KeyType key;
cin>>key; //读入一个关键字
while(key)
{ //假设key=0是输入结束标志
InsertBST(&T,key); //将key插入二叉排序树T
cin>>key; //读入下一关键字
}
return T; //返回建立的二叉排序树的根指针
}
void ListBinTree(BSTree T) //用广义表示二叉树
{
if(T!=NULL)
{
cout<<T->key;
if(T->lchild!=NULL||T->rchild!=NULL)
{
cout<<"(";
ListBinTree(T->lchild);
if(T->rchild!=NULL)
cout<<",";
ListBinTree(T->rchild);
cout<<")";
}
}
}
int main()
{
BSTNode *findbst(BSTree t,KeyType key);
void InsertBST(BSTree *Tptr,KeyType key);
BSTree CreateBST();
void ListBinTree(BSTree T);
BSTree T;
BSTNode *p;
int key;
cout<<"请输入关键字（输入0为结束标志）："<<endl;
T=CreateBST();
ListBinTree(T);
cout<<endl;
cout<<"请输入欲查找关键字:";
cin>>key;
p=findbst(T,key);
if(p==NULL)
cout<<"没有找到"<<key<<"！"<<endl;
else
cout<<"找到"<<key<<"！"<<endl;
ListBinTree(p);
cout<<endl;
return 0;
}冒泡排序
#include <stdio.h>
#define MaxSize 20
typedef int KeyType; //定义关键字类型
typedef char InfoType[10];
typedef struct //记录类型
{
KeyType key; //关键字项
InfoType data; //其他数据项,类型为InfoType
} RecType; //排序的记录类型定义
void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序
{
int i,j,k;
RecType tmp;
for (i=1; i<n; i++)
{
tmp=R[i];
j=i-1; //从右向左在有序区R[0..i-1]中找R[i]的插入位置
while (j>=0 && tmp.key<R[j].key)
{
R[j+1]=R[j]; //将关键字大于R[i].key的记录后移
j--;
}
R[j+1]=tmp; //在j+1处插入R[i]
printf("i=%d: ",i);
for (k=0; k<n; k++)
printf("%d ",R[k].key);
printf("\n");
}
}
int main()
{
int i,n=5;
RecType R[MaxSize];
KeyType a[]= {3,24,12,6,1};
for (i=0; i<n; i++)
R[i].key=a[i];
printf("排序前:");
for (i=0; i<n; i++)
printf("%d ",R[i].key);
printf("\n");
InsertSort(R,n);
printf("排序后:");
for (i=0; i<n; i++)
printf("%d ",R[i].key);
printf("\n");
return 0;
}题型分类
插入 删除 合并 排序 折半查找递归算法
顺序表题型
插入
int listinsert_sq(sqlist &l,int i,et e){
if(i<1||i>l.length+1)
return 0;
for (int j=l.length-1; j>=i-1; j--) {
l.elem[j+1]=l.elem[j];
}
l.elem[i-1]=e;
++l.length;
return 1;
}删除
int listdelete_sq(sqlist &l,int i,et &e){
if(i<1||i>l.length)
return 0;
e=l.elem[i-1];
for (int j=i; j<=l.length-1; j++) {
l.elem[j-1]=l.elem[j];
}
--l.length;
return 1;
}完整程序
#include"iostream"
using namespace std;
#define maxsize 100
typedef char et;
typedef struct{
et *elem;
int length;
}sqlist;
int initlist_sq(sqlist &l){
l.elem=new et[maxsize];
if(!l.elem)
return 0;
l.length=0;
return 1;
}
int listinsert_sq(sqlist &l,int i,et e){
if(i<1||i>l.length+1)
return 0;
for (int j=l.length-1; j>=i-1; j--) {
l.elem[j+1]=l.elem[j];
}
l.elem[i-1]=e;
++l.length;
return 1;
}
int listdelete_sq(sqlist &l,int i,et &e){
if(i<1||i>l.length)
return 0;
e=l.elem[i-1];
for (int j=i; j<=l.length-1; j++) {
l.elem[j-1]=l.elem[j];
}
--l.length;
return 1;
}
void disp_sq(sqlist l){
if(l.length==0)
cout<<"此顺序表为空"<<endl;
for(int i=0;i<l.length;i++){
cout<<l.elem[i];
}
cout<<endl;
}
int main(){
et e;
sqlist l;
initlist_sq(l);
disp_sq(l);
listinsert_sq(l,1,'A');
listinsert_sq(l,2,'B');
listinsert_sq(l,3,'C');
disp_sq(l);
listdelete_sq(l,1,e);
disp_sq(l);
cout<<"删除的元素是："<<e<<endl;
}链表题型
插入
int listinsert(lk &l,int i,et e){
lk p;
p=l;
int j=0;
while(p&&j<i-1){
p=p->next;
j++;
}
if (!p||j>i-1) {
return 0;
}
lk s=new ln;
s->date=e;//将e的值赋值给s的值域
s->next=p->next;//新元素s的指针域指向旧元素p的指针域
p->next=s;//将p的指针域指向s元素
return 1;
}删除
int listdelete(lk &l,int i,et &e){
lk p;
p=l;
int j=0;
while(p->next&&j<i-1){
p=p->next;
j++;
}
if (!(p->next)||j>i-1) {
return 0;
}
lk q;
q=p->next;//q的指针指向p的指针域
p->next=q->next;//p的指针域指向q的指针域
e=q->date;//将删除q的值域的值赋值给e的位置值
delete q;
return 1;
}求最大值
void mlist(lk l){//最大值
lk s=new ln;
lk p=l->next;
s->data=p->data;
while(p){
if(s->data<=p->data){
s->data=p->data;
p=p->next;
}
else{
p=p->next;
}
}
cout<<"最大值为："<<s->data<<endl;
}逆序输出
int rlist(lk &l){//逆序
lk p=l->next;
lk q;
l->next=NULL;
while(p){
q=p->next;
p->next=l->next;
l->next=p;
p=q;
}
return 1;
}合并
void mergelist(lk &la,lk &lb,lk &lc){
lk pa=la->next;
lk pb=lb->next;
lk pc=lc=la;
while(pa&&pb){
if(pa->data<pb->data){
pc->next=pa;
pc=pa;
pa=pa->next;
}
else{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?pa:pb;
}查找
int max(lk &la){
lk pa=la->next;//将pa指针指向la表的头结点
lk ps=la;//ps的初始值指向la的头结点
int i=1,k=0;//定义两个计数变量
ps->data=pa->data;//给ps的数据域赋初值
while(pa){
if(pa->data>=ps->data){
ps->data=pa->data;//将ps的数据域指向pa的数据域
pa=pa->next;//向下移一位
k=i;//满足条件用k记录
i++;//循环计数+1
}
else{
pa=pa->next;
i++;//循环计数+1
}
}
cout<<"最大元素是："<<ps->data<<endl;
cout<<"位置是第"<<k<<"个元素"<<endl;
return 1;
}折半查找
int xfind(lk st,keyt t, int low, int high){
if(low<=high){
int mid=(low+high)/2;
if(st.elem[mid].key==t)
return mid;
else if (st.elem[mid].key<t)
return (xfind(st, t, mid+1, high));
else
return (xfind(st, t, low, mid-1));
}
else
return 0;
}完整程序(插入,删除,最大,合并,逆序)
#include<iostream>
using namespace std;
typedef struct ln{
int data;
struct ln *next;
}*lk;
int initlist(lk &l){
l=new ln;
l->next=NULL;
return 1;
}
int insertlist(lk &l,int i,int e){
lk p=l;//错写成p=l->next
int j=0;
while(p&&j<i-1){
p=p->next;
j++;
}
if(!p||j>i-1){
return 0;
}
lk s=new ln;
s->data=e;
s->next=p->next;
p->next=s;
return 1;
}
int deletelist(lk &l,int i,int &e){
lk p=l;//错写成p=l->next
int j=0;
while(p&&j<i-1){
p=p->next;
j++;
}
if(!p||j>i-1){
return 0;
}
lk q=p->next;
p->next=q->next;
e=q->data;
delete q;
return 1;
}
int margeinlist(lk &la,lk &lb,lk &lc){//合并
lk pa=la->next;
lk pb=lb->next;
lk pc=lc=la;
while(pa&&pb){
if(pa->data<pb->data){
pc->next=pa;
pc=pa;
pa=pa->next;
}
else{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?pa:pb;
return 1;
}
int rlist(lk &l){//逆序
lk p=l->next;
lk q;
l->next=NULL;
while(p){
q=p->next;
p->next=l->next;
l->next=p;
p=q;
}
return 1;
}
void mlist(lk l){//最大值
lk s=new ln;
lk p=l->next;
s->data=p->data;
while(p){
if(s->data<=p->data){
s->data=p->data;
p=p->next;
}
else{
p=p->next;
}
}
cout<<"最大值为："<<s->data<<endl;
}
void disp(lk &l){
lk p=l->next;
if(!p){
cout<<"空表"<<endl;
}
while(p){
cout<<p->data;
p=p->next;
}
cout<<endl;
}
int main(){
lk la,lb,lc;
int e;
initlist(la);
initlist(lb);
insertlist(la, 1, 1);
insertlist(la, 2, 5);
insertlist(la, 3, 7);
insertlist(la, 4, 9);
insertlist(lb, 1, 2);
insertlist(lb, 2, 3);
insertlist(lb, 3, 6);
cout<<"la的元素是：";
disp(la);
cout<<"lb的元素是：";
disp(lb);
deletelist(la, 2, e);
cout<<"删除的元素是："<<e<<endl;
margeinlist(la, lb, lc);
cout<<"合并后的元素是：";
disp(lc);
rlist(lc);
cout<<"反序输出元素顺序为：";
disp(lc);
mlist(lc);
}
#include <iostream>
using namespace std;
typedef char et;
typedef struct ln{
et date;
struct ln *next;
}ln,*lk;
int initlist(lk &l){
l=new ln;
l->next=NULL;
return 1;
}
int listinsert(lk &l,int i,et e){
lk p;
p=l;
int j=0;
while(p&&j<i-1){
p=p->next;
j++;
}
if (!p||j>i-1) {
return 0;
}
lk s=new ln;
s->date=e;//将e的值赋值给s的值域
s->next=p->next;//新元素s的指针域指向旧元素p的指针域
p->next=s;//将p的指针域指向s元素
return 1;
}
int listdelete(lk &l,int i,et &e){
lk p;
p=l;
int j=0;
while(p->next&&j<i-1){
p=p->next;
j++;
}
if (!(p->next)||j>i-1) {
return 0;
}
lk q;
q=p->next;//q的指针指向p的指针域
p->next=q->next;//p的指针域指向q的指针域
e=q->date;//将删除q的值域的值赋值给e的位置值
delete q;
return 1;
}
void disp(lk l){
lk p=l->next;
if (!p) {
cout<<"此链表为空"<<endl;
}
while (p) {
cout<<p->date;
p=p->next;
}
cout<<endl;
}
int main(){
lk l;
et e;
initlist(l);
disp(l);
listinsert(l, 1, 'A');
listinsert(l, 2, 'B');
listinsert(l, 3, 'C');
disp(l);
listdelete(l, 2, e);
cout<<"删除的元素是："<<e<<endl;
disp(l);
return 0;
}完整代码(查找)
#include <iostream>
using namespace std;
typedef struct ln{
int data;
struct ln *next;
}*lk;
int inilist(lk &l){
l=new ln;
l->next=NULL;
return 1;
}
int listinsert(lk &l,int i,int e){
lk p=l;//定义一个指针p指向l的头结点
int j=0;//位置的初始值
while (p&&j<i-1) {
p=p->next;//当满足条件是p指向下一位
j++;//位置值加一
}
if (!p||j>i-1) {
return 0;
}
lk s=new ln;//建立一个节点s
s->data=e;//s节点的数据域等于e的数值
s->next=p->next;//s的next域指向p的next域
p->next=s;//p的next域指向s节点
return 1;
}
int max(lk &la){
lk pa=la->next;//将pa指针指向la表的头结点
lk ps=la;//ps的初始值指向la的头结点
int i=1,k=0;//定义两个计数变量
ps->data=pa->data;//给ps的数据域赋初值
while(pa){
if(pa->data>=ps->data){
ps->data=pa->data;//将ps的数据域指向pa的数据域
pa=pa->next;//向下移一位
k=i;//满足条件用k记录
i++;//循环计数+1
}
else{
pa=pa->next;
i++;//循环计数+1
}
}
cout<<"最大元素是："<<ps->data<<endl;
cout<<"位置是第"<<k<<"个元素"<<endl;
return 1;
}
int main(){
lk la;//定义三个表
inilist(la);//对表la的初始化
listinsert(la, 1, 2);//向la表中插入数据
listinsert(la, 2, 3);
listinsert(la, 3, 5);
listinsert(la, 4, 7);
listinsert(la, 5, 10);
listinsert(la, 6, 9);
listinsert(la, 7, 8);
max(la);
}完整代码(折半查找)
//
// main.cpp
// 实验六数据结构
//
// Created by PC-MAC on 2018/12/3.
// Copyright © 2018 PC-MAC. All rights reserved.
//
#include"iostream"
using namespace std;
const int tmax=10;
typedef int keyt;
typedef struct{
keyt key;
}elemtype;//每行内容
typedef struct{
elemtype *elem;
int length;
}lk;
int find(lk st,keyt key){
int i;
st.elem[0].key=key;
for(i=st.length;st.elem[i].key!=key;i--);
return i;
}
int twofind(lk st,keyt key){
int low,high,mid;
low=1;
high=st.length;
while(low<=high){
mid=(low+high)/2;
if(st.elem[mid].key==key)
return mid;
else if(st.elem[mid].key>key)
high=mid-1;
else
low=mid+1;
}
return 0;
}
int xfind(lk st,keyt t, int low, int high){
if(low<=high){
int mid=(low+high)/2;
if(st.elem[mid].key==t)
return mid;
else if (st.elem[mid].key<t)
return (xfind(st, t, mid+1, high));
else
return (xfind(st, t, low, mid-1));
}
else
return 0;
}
int main(){
keyt a[]={0,13,24,35,32,65,19,7,74,20,38};
lk t;
t.elem=new elemtype[tmax];
t.length=10;
for(int i=1;i<=10;i++){
t.elem[i].key=a[i];
}
cout<<"查找到的元素位置为："<<find(t, 35)<<endl;
lk s;
s.elem=new elemtype[tmax];
s.length=10;
keyt b[]={0,2,4,6,8,10,12,14,16,18,20};
for(int k=1;k<=10;k++){
s.elem[k].key=b[k];
}
cout<<"折半查找到的元素位置为："<<twofind(s, 14)<<endl;
int i, j;
keyt arr[10];
for (i = 0; i < 10; i++)
{
arr[i] = i * 2;
}
cout << "输入查找数字:";
cin >> j;
lk P;
P.elem = new elemtype;
P.length = 10;
for (int j = 1; j <= 10; j++)
{
P.elem[j].key = arr[j];
}
cout<<"递归折半查找到的元素位置为："<<xfind(P, j, 0, 10)<<endl;
return 0;
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-02-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录