下载文档原格式
第1篇一、引言数据结构是计算机科学中一门重要的学科，它研究如何有效地组织、存储和操作数据。
在计算机科学和软件开发中，数据结构的选择直接影响着程序的效率、可读性和可维护性。
本文将对常见的数据结构进行归类总结，分析其特点、应用场景以及优缺点，旨在为读者提供全面的数据结构知识。
二、数据结构分类1. 基本数据结构基本数据结构包括线性表、栈、队列、字符串等。
（1）线性表线性表是一种有序的数据集合，包括顺序表和链表两种形式。
顺序表是一种通过数组实现的线性表，具有随机访问的特点；链表则通过指针连接节点，实现动态存储。
特点：顺序表支持随机访问，链表支持动态扩展。
应用场景：数组、链表、栈、队列等数据结构。
（2）栈栈是一种后进先出（LIFO）的线性表，只能在表的一端进行插入和删除操作。
特点：先进后出，具有明确的操作顺序。
应用场景：递归算法、函数调用栈、表达式求值等。
（3）队列队列是一种先进先出（FIFO）的线性表，只能在表的一端进行插入操作，在另一端进行删除操作。
特点：先进先出，具有明确的操作顺序。
应用场景：打印任务、缓冲区、资源分配等。
（4）字符串字符串是由字符组成的序列，是处理文本信息的重要数据结构。
特点：可变长度，支持字符操作。
应用场景：文本编辑、搜索引擎、自然语言处理等。
2. 树状数据结构树状数据结构包括二叉树、堆、平衡树等。
（1）二叉树二叉树是一种每个节点最多有两个子节点的树形结构。
特点：层次结构，具有明确的父子关系。
应用场景：数据结构中的查找、排序、遍历等。
（2）堆堆是一种特殊的完全二叉树，满足堆性质：每个节点的值大于或等于其子节点的值（最大堆）或小于或等于其子节点的值（最小堆）。
特点：支持快速查找、插入和删除操作。
应用场景：优先队列、动态数组、排序等。
（3）平衡树平衡树是一种保持平衡的二叉搜索树，如AVL树、红黑树等。
特点：保持平衡，查找、插入和删除操作具有对数时间复杂度。
应用场景：数据库索引、搜索树等。
HUNAN UNIVERSITY数据结构实验报告题目：实验5四则运算表达式求值学生姓名谢毅学生姓名冯吉禹学生姓名吕志远学生学号20110806109学生学号20110806110学生学号20110806114专业班级信息安全1101班指导老师夏艳完成日期2013 年04 月 19日一．需求分析1、利用二叉树后序遍历来实现表达式的转换，同时可以使用实验3的结果来求解后缀表达式的值。
2、输入输出格式：输入：在字符界面上输入一个中缀表达式，回车表示结束。
输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。
输入：21+23*（12-6）输出：21 23 12 6 -*+一．概要设计抽象数据类型1.使用二叉树来实现2．本程序包含四个基本模块①主程序模块：建树的过程②没有括号时的输入③有括号时的输入○4后序输出三﹑算法（C++）物理数据类型建树的时候对于优先级比较高的符号最为子结点插入，对于优先级比较低的则作为父结点插入，数据直接插入在字符的左右子结点位置。
/*问题描述四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。
基本要求使用二叉树来实现。
实现提示利用二叉树后序遍历来实现表达式的转换，同时可以使用实验3的结果来求解后缀表达式的值。
输入输出格式：输入：在字符界面上输入一个中缀表达式，回车表示结束。
输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。
*/#include<iostream.h>#include <stdio.h>/*二叉树的节点类*/class Node{public:int num;//元素char c;//操作符Node* lc;//左指针Node* rc;//右指针Node* pa;//父指针Node(int num,Node* lc=NULL,Node* rc=NULL){this->num=num;this->lc=lc;this->rc=rc;}Node(char c,Node* lc=NULL,Node* rc=NULL){this->c=c;this->lc=lc;this->rc=rc;}bool isLeaf(){return (lc==NULL)&&(rc==NULL);}};void Nomal(char &t,char &c,Node* &one,Node* &two);//正常输入void UNomal(char &t,char &c,Node* &one,Node* &two);//带括号输入void BHVisit(Node* root);/*二叉树类*/class TwoTree{private:Node* root;//根节点Node* present;//当前表达式节点public:TwoTree(){root=NULL;present=root;}Node* getroot(){return root;}bool gt(Node* two,Node* present)//比较优先级的函数{char ct=two->c;char cp=present->c;if(ct=='*'||ct=='/')if(cp=='+'||cp=='-')return true;return false;}void insert(Node* one,Node* two=NULL)//向插入的方法{cout<<" 要插入了 "<<one->num<<" "<<two->c<<endl;if(root==NULL){root=two;root->lc=one;one->pa=root;present=root;return;}if(two->c=='\n'){present->rc=one;one->pa=present;return;}if(gt(two,present))//如果输入的操作符的优先等级大于当前指针的优先级{two->lc=one;one->pa=two;present->rc=two;two->pa=present;present=two;return;}present->rc=one;while(!gt(two,present)&&present!=root)//如果输入的操作符的优先等级不大于当前指针的优先级{present=present->pa;//指向父节点}if(gt(two,present))//如果输入的操作符的优先等级大于当前指针的优先级{two->lc=present->rc;present->rc->pa=two;present->rc=two;two->pa=present;present=two;return;}else{two->lc=present;present->pa=two;root=two;present=two;}}};void main(){TwoTree tt;Node* root;Node* one;Node* two;char c,t;int index=0;cout<<"请输入一个中缀表达式"<<endl;while(1){t=getchar();cout<<t<<endl;if(t!='(')Nomal(t,c,one,two);elseUNomal(t,c,one,two);tt.insert(one,two);if(c=='\n')break;}root=tt.getroot();BHVisit(root);return;}void Nomal(char &t,char &c,Node* &one,Node* &two) {int num;num=t-'0';cout<<num<<"--------"<<endl;c=getchar();one=new Node(num);two=new Node(c);}void UNomal(char &t,char &c,Node* &one,Node* &two) {int num;TwoTree ttp;while(1){t=getchar();num=t-'0';cout<<num<<"+++++++++++"<<t<<endl;c=getchar();if(c==')'){char cp='\n';c=getchar();one=new Node(num);two=new Node(cp);ttp.insert(one,two);break;}one=new Node(num);two=new Node(c);ttp.insert(one,two);}one=ttp.getroot();two=new Node(c);}void BHVisit(Node* root)//后序遍历函数{if(root==NULL)return;BHVisit(root->lc);BHVisit(root->rc);if(root->isLeaf())cout<<root->num<<" ";elsecout<<root->c<<" ";}六．算法的时间复杂度：整个程序的时间复杂度是O(n).七．实验心得谢毅：本次实验相对上次实验来说难度提升比较大，刚开始的时候觉得无从下手，后来翻阅了书上的关于树的内容，并且和同学们经过了讨论，终于想出了这次实验的建树方式。
2014年数据结构考研大纲——湘潭大学湘潭大学2014数据结构考研大纲(一)考试对象参加全日制专业学位研究生《计算机技术》和《软件工程》专业复试考生。
(二)考试目的考核学生对本课程知识的掌握和运用能力，属水平测试。
(三)考试的内容、要求第一章绪论考试内容数据结构的基本概念和术语; 算法的描述; 算法设计的要求; 算法效率的度量; 算法的存储空间需求。
考试要求1.有关数据的基本概念;2.领会抽象数据类型与数据结构的关系及抽象数据类型在算法设计中的意义和作用;3.掌握数据的逻辑结构及有关术语的定义，掌握数据结构的表示方法，能用序偶集合表示关系;4.了解数据的逻辑结构和存储结构的分类;5.掌握描述算法的语言;6.算法的存储空间需求;7.领会算法设计的要求算法效率度量的意义和作用，懂得算法分析原理，掌握算法分析技术;第二章线性表考试内容线性表的逻辑结构; 线性表的顺序存储结构; 线性表的链式存储结构; 一元多项式的表示及相加和相乘算法。
考试要求1.熟练掌握顺序存储的线性表的基本操作的实现，熟练掌握链式存储的线性表的动态存储和静态存储的方法及其算法;2.循环链表的应用，一元多项式的表示及相加和相乘算法;3.掌握顺序存储的线性表和链式存储的线性表的主要优缺点;4.掌握对顺序存储的线性表和链式存储的线性表的各种算法的评价;第三章栈与队列考试内容栈;表达式求值; 栈与递归过程; 队列。
考试要求1.顺序栈与链栈的结构及操作，要求达到综合应用层次;2.顺序栈与链栈的比较;3.顺序队与链队的结构及操作，要求达到综合应用层次;4.顺序队与链队的比较;5.弄清队与栈及线性表的异同。
掌握循环队的组织方法及有关算法;6.递归过程的模拟。
第四章串考试内容串及其操作; 串的存储结构; 串基本操作的实现。
考试要求1.领会串的逻辑结构定义，掌握串的基本操作;2.掌握串的存储结构及其算法实现;3.掌握模式匹配的原理及其KMP算法。
第五章数组和广义表考试内容数组的定义和数组分量的地址计算; 数组的顺序存储结构; 矩阵的压缩存储; 广义表的定义; 广义表的存储结构; 广义表的递归算法。
1、n个顶点的图的最小生成树必定（ D ），是不正确的描述。
A）不唯一 B）权的总和唯一C）不含回路 D）有n条边2、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。
A）3 B）4 C）5 D）13、设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ A ）。
A）p->next=p->next->next; B） p=p->next;C）p=p->next->next; D） p->next=p;4、与无向图相关的术语有（ C ）。
A）强连通图 B）入度C）路径 D）弧5、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a??11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。
A）13 B）33 C）18 D）406、n个顶点的强连通图至少有（ A ）条边。
A）n B）n+1 C）n-1 D）n(n-1)7、广义表head(((a,b),(c,d)))的运算结果为（ A ）。
A）(a,b) B）(c,d)C）空表 D）（（a,b）,(c,d)）8、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（ A ）。
A）一个数量级别 B）一个平均值C）一个最大值 D）一个均方值9、与无向图相关的术语有（ C ）。
A）强连通图 B）入度C）路径 D）弧10、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。
A）4 B）5C）6 D）711、有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}。
当用二分查找法查找键值为84的结点时，经（ B ）比较后查找成功。
A) 4 B)3 C)2 D)1212、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ C ）。
1、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。
（注：双向起泡排序即相邻两趟排序向相反方向起泡）2、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。
（注：图中不存在顶点到自己的弧）有向图判断回路要比无向图复杂。
利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。
下面用0，1，2表示这三种状态。
前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。
对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。
void Print(int v,int start ) //输出从顶点start开始的回路。
{for(i=1;i<=n;i++)if(g[v][i]!=0 && visited[i]==1 ) //若存在边（v,i），且顶点i的状态为1。
{printf(“%d”,v);if(i==start) printf(“\n”); else Print(i,start);break;}//if}//Printvoid dfs(int v){visited[v]=1;for(j=1;j<=n;j++ )if (g[v][j]!=0) //存在边(v,j)if (visited[j]!=1) {if (!visited[j]) dfs(j); }//ifelse {cycle=1; Print(j,j);}visited[v]=2;}//dfsvoid find_cycle() //判断是否有回路，有则输出邻接矩阵。
1、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注:向量d可视为循环表），其原则为，先将r[l]赋给d[1]，再从r[2] 记录开始分二路插入。
编写实现二路插入排序算法。
2、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。
但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。
void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2)//将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。
{if(h1>=l1){post[h2]=pre[l1]; //根结点half=(h1-l1)/2; //左或右子树的结点数PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列} }//PreToPost32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。
设置前驱结点指针pre，初始为空。
第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。
LinkedList head,pre=null; //全局变量LinkedList InOrder(BiTree bt)//中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head{if(bt){InOrder(bt->lchild); //中序遍历左子树if(bt->lchild==null && bt->rchild==null) //叶子结点if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表InOrder(bt->rchild); //中序遍历左子树pre->rchild=null; //设置链表尾}return(head); } //InOrder时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)3、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。
1、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}写出G的拓扑排序的结果。
G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V72、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。
#define MAX 100typedef struct Node{char info; struct Node *llink, *rlink; }TNODE;char pred[MAX],inod[MAX];main(int argc,int **argv){ TNODE *root;if(argc<3) exit 0;strcpy(pred,argv[1]); strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE *restore(char *ppos,char *ipos,int n){ TNODE *ptr； char *rpos; int k;if(n<=0) return NULL;ptr->info=(1)_______;for((2)_______ ; rpos<ipos+n;rpos++) if(*rpos==*ppos) break;k=(3)_______;ptr->llink=restore(ppos+1, (4)_______,k );ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);return ptr;}postorder(TNODE*ptr){ if(ptr=NULL) return;postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); }3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。
现要求采用循环链表结构设计一个算法，模拟此过程。
#include<stdlib.h>typedef int datatype;typedef struct node{datatype data;struct node *next;}listnode;typedef listnode *linklist;void jose(linklist head,int s,int m){linklist k1,pre,p;int count=1;pre=NULL;k1=head; /*k1为报数的起点*/while (count!=s) /*找初始报数起点*/{pre=k1;k1=k1->next;count++;}while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/{ p=k1; /*从k1开始报数*/count=1;while (count!=m) /*连续数m个结点*/{ pre=p;p=p->next;count++;}pre->next=p->next; /*输出该结点，并删除该结点*/printf("%4d",p->data);free(p);k1=pre->next; /*新的报数起点*/}printf("%4d",k1->data); /*输出最后一个结点*/free(k1);}main(){linklist head,p,r;int n,s,m,i;printf("n=");scanf("%d",&n);printf("s=");scanf("%d",&s);printf("m=",&m);scanf("%d",&m);if (n<1) printf("n<0");else{/*建表*/head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/ head->data=n;r=head;for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/{ p=(linklist)malloc(sizeof(listnode));p->data=i;p->next=head;head=p;}r->next=head; /*生成循环链表*/jose(head,s,m); /*调用函数*/}}4、(1)p->rchild (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild)(5)ADDQ(Q,p->rchild)25. (1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild) (5)count(t->rchild)26. .(1)top++ (2) stack[top]=p->rchild (3)top++ (4)stack[top]=p->lchild27. (1)*ppos // 根结点（2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+15、本题应使用深度优先遍历，从主调函数进入dfs(v)时，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。
将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。
题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。
建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。
int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。
const n=用户定义的顶点数;AdjList g ; //用邻接表作存储结构的有向图g。
void dfs(v){visited [v]=1; num++; //访问的顶点数＋1if (num==n) {printf(“%d是有向图的根。
\n”,v); num=0;}//ifp=g[v].firstarc;while (p){if (visied[p->adjvex]==0) dfs (p->adjvex);p=p->next;} //whilevisited[v]=0; num--; //恢复顶点v}//dfsvoid JudgeRoot()//判断有向图是否有根，有根则输出之。
{static int i ;for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。
{num=0; visited[1..n]=0; dfs(i); }}// JudgeRoot算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。
6、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。
现要求采用循环链表结构设计一个算法，模拟此过程。
#include<stdlib.h>typedef int datatype;typedef struct node{datatype data;struct node *next;}listnode;typedef listnode *linklist;void jose(linklist head,int s,int m){linklist k1,pre,p;int count=1;pre=NULL;k1=head; /*k1为报数的起点*/while (count!=s) /*找初始报数起点*/{pre=k1;k1=k1->next;count++;}while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/{ p=k1; /*从k1开始报数*/count=1;while (count!=m) /*连续数m个结点*/{ pre=p;p=p->next;count++;}pre->next=p->next; /*输出该结点，并删除该结点*/printf("%4d",p->data);free(p);k1=pre->next; /*新的报数起点*/}printf("%4d",k1->data); /*输出最后一个结点*/free(k1);}main(){linklist head,p,r;int n,s,m,i;printf("n=");scanf("%d",&n);printf("s=");scanf("%d",&s);printf("m=",&m);scanf("%d",&m);if (n<1) printf("n<0");else{/*建表*/head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/head->data=n;r=head;for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/{ p=(linklist)malloc(sizeof(listnode));p->data=i;p->next=head;head=p;}r->next=head; /*生成循环链表*/jose(head,s,m); /*调用函数*/}}7、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
