DATA STRUCTURE(WORD文件及时更新)

31
算法示例
显然,当线性表中数据有序时,折半查找的效率要 比线性查找的效率高。 如何来分析算法的效率?
32
算法效率
程序跑的更快：
事后统计：利用计算机的时钟； 事前分析估算：用高级语言编写的程序运行 的时间主要取决于如下因素：

算法； 问题规模； 使用语言：级别越高，效率越低； 编译程序； 机器；
学生信息查询系统中的数据结构学号980001姓名性别专业年级吴承志男计算机科学与技术98级980002李淑芳女信息与计算科学98级99级99级99级990301刘丽女数学与应用数学990302990302张会友张会友男男信息与计算科学信息与计算科学计算机科学与技术99级计算机科学与技术2000级4990303石宝国男000801何文颖女000802赵胜利男数学与应用数学2000级2000级000803崔文靖男信息与计算科学计算机科学与技术2001级010601刘丽女010602魏永鸣男数学与应用数学2001级学生信息查询系统中的数据结构崔文靖8何文颖6李淑芳2刘丽刘丽石宝国5魏永鸣10吴承志1赵胜利7张会友43939计算机科学与技术1569248信息与计算科学数学与应用数学371052000级2001级67891098级99级12345非数值计算的例子oxoxooxxooxxoxooxoooxxxoo6ooxoxoxxxooxoooxxooxoo教学计划编排问题课程编号c1课程名称先修课程计算机导论无c1c4c2数据结构c3c3汇编语言汇编语言c程序设计语言c1c17c4c1c5计算机图形学c2c3c4c3c6接口技术c7数据库原理c2c9c4c8编译原理c9操作系统c2教学计划编排问题的数据结构8数据结构定义?由以上三个例子可见描述这类非数值计算问题的数学模型不再是数学方程而是诸如表树图之类的数据结构

想要计算机处理数据， 就必须把数据的逻辑结构映射为数据的存储结构。 逻辑结构可以映射为以下两种存储结构：
1.顺序存储结构 ：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。
2.链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物
3.树形结构 ：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一
个元素 （根）之外，其它 每个数据元素都只有一个直接前驱， 以及多个或零个 直接后继。
4.图状结构 ：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个（或零个）直接后继。
（2）数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。
结点定义：
typedef int datatype;//结点数据类型，假设为int
typedef struct node {//结点结构
datatype data;
struct node *next;//双向链表还应加上*previous
3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。（有时候也
叫做属性。）
4．数据结构 ：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
（1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。
数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。
2 / 13
插入：p->next=head->next;head->next=p;
输出：printf(“%d”,p->data);
删除：q=p->next;p->next = q->next ;free(q);

数据结构实验报告一．题目要求1）编程实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进行先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。

4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?二．解决方案对于前三个题目要求，我们用一个程序实现代码如下#include<windows.h>#include <stdio.h>#include <malloc.h>#include "Stack.h" //栈的头文件，没有用上typedef int ElemType; //数据类型typedef int Status; //返回值类型//定义二叉树结构typedef struct BiTNode{ElemType data; //数据域struct BiTNode *lChild, *rChild;//左右子树域}BiTNode, *BiTree;int InsertBST(BiTree &T,int key){//插入二叉树函数if(T==NULL){T = (BiTree)malloc(sizeof(BiTNode));T->data=key;T->lChild=T->rChild=NULL;return 1;}else if(key<T->data){InsertBST(T->lChild,key);}else if(key>T->data){InsertBST(T->rChild,key);}elsereturn 0;}BiTree CreateBST(int a[],int n){//创建二叉树函数BiTree bst=NULL;int i=0;while(i<n){InsertBST(bst,a[i]);i++;}return bst;}int Delete(BiTree &T){BiTree q,s;if(!(T)->rChild){ //右子树为空重接它的左子树q=T;T=(T)->lChild;free(q);}else{if(!(T)->lChild){ //若左子树空则重新接它的右子树q=T;T=(T)->rChild;}else{q=T;s=(T)->lChild;while(s->rChild){q=s; s=s->rChild;}(T)->data=s->data; //s指向被删除结点的前驱if(q!=T)q->rChild=s->lChild;elseq->lChild=s->lChild;free(s);}}return 1;}//删除函数，在T中删除key元素int DeleteBST(BiTree &T,int key){if(!T) return 0;else{if(key==(T)->data) return Delete(T);else{if(key<(T)->data)return DeleteBST(T->lChild,key);elsereturn DeleteBST(T->rChild,key);}}}int PosttreeDepth(BiTree T){//求深度int hr,hl,max;if(!T==NULL){hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;}elsereturn 0;}void printtree(BiTree T,int nlayer){//打印二叉树if(T==NULL) return ;printtree(T->rChild,nlayer+1);for(int i=0;i<nlayer;i++){printf(" ");}printf("%d\n",T->data);printtree(T->lChild,nlayer+1);}void PreOrderNoRec(BiTree root)//先序非递归遍历{BiTree p=root;BiTree stack[50];int num=0;while(NULL!=p||num>0){while(NULL!=p){printf("%d ",p->data);stack[num++]=p;p=p->lChild;}num--;p=stack[num];p=p->rChild;}printf("\n");}void InOrderNoRec(BiTree root)//中序非递归遍历{BiTree p=root;int num=0;BiTree stack[50];while(NULL!=p||num>0){while(NULL!=p){stack[num++]=p;p=p->lChild;}num--;p=stack[num];printf("%d ",p->data);p=p->rChild;}printf("\n");}void PostOrderNoRec(BiTree root)//后序非递归遍历{BiTree p=root;BiTree stack[50];int num=0;BiTree have_visited=NULL;while(NULL!=p||num>0){while(NULL!=p){stack[num++]=p;p=p->lChild;}p=stack[num-1];if(NULL==p->rChild||have_visited==p->rChild){printf("%d ",p->data);num--;have_visited=p;p=NULL;}else{p=p->rChild;}}printf("\n");}int main(){//主函数printf(" ---------------------二叉排序树的实现-------------------");printf("\n");int layer;int i;int num;printf("输入节点个数:");scanf("%d",&num);printf("依次输入这些整数（要不相等）");int *arr=(int*)malloc(num*sizeof(int));for(i=0;i<num;i++){scanf("%d",arr+i);}BiTree bst=CreateBST(arr,num);printf("\n");printf("二叉树创建成功!");printf("\n");layer=PosttreeDepth(bst);printf("树状图为:\n");printtree(bst,layer);int j;int T;int K;for(;;){loop:printf("\n");printf(" ***********************按提示输入操作符************************:");printf("\n");printf(" 1:插入节点2:删除节点3:打印二叉树4:非递归遍历二叉树5:退出");scanf("%d",&j);switch(j){case 1:printf("输入要插入的节点:");scanf("%d",&T);InsertBST(bst,T);printf("插入成功!");printf("树状图为:\n");printtree(bst,layer);break;case 2:printf("输入要删除的节点");scanf("%d",&K);DeleteBST(bst,K);printf("删除成功!");printf("树状图为:\n");printtree(bst,layer);break;case 3:layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4:printf("非递归遍历二叉树");printf("先序遍历:\n");PreOrderNoRec(bst);printf("中序遍历:\n");InOrderNoRec(bst);printf("后序遍历:\n");PostOrderNoRec(bst);printf("树状图为:\n");printtree(bst,layer);break;case 5:printf("程序执行完毕!");return 0;}goto loop;}return 0;}对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为typedef int ElemType; //数据类型typedef string SlemType;typedef int Status; //返回值类型//定义二叉树结构typedef struct BiTNode{SlemType name;ElemType score;ElemType no; //数据域struct BiTNode *lChild, *rChild;//左右子树域}BiTNode, *BiTree;参数不是key,而是另外三个int InsertBST(BiTree &T,int no,int score,string name){//插入二叉树函数if(T==NULL){T = (BiTree)malloc(sizeof(BiTNode));T->no=no;T->name=name;T->score=score;T->lChild=T->rChild=NULL;return 1;}else if(no<T->no){InsertBST(T->lChild,no,score,name);}else if(key>T->data){InsertBST(T->rChild, no,score,name);}elsereturn 0;}其他含参函数也类似即可完成50个信息存储用数组存储50个信息，查看以往代码#include<iostream>#include<string>using namespace std;class student{private:int num;string name;int ob1;int ob2;int ara;public:void set(int a,string b,int c,int d);void show();int average();};void student ::set(int a,string b,int c,int d){num=a;name=b;ob1=c;ob2=d;ara=(c+d)/2;}void student::show(){cout<<"学号："<<num<<" 姓名："<<name<<" 科目一："<<ob1<<" 科目二："<<ob2<<" 平均成绩："<<ara<<endl;}int student::average(){return ara;}int main(){cout<<" 欢迎来到学生管理系统"<<endl;cout<<" 0.查询学号信息："<<endl;cout<<" 1.删除学号信息："<<endl;cout<<" 2.添加学号新信息"<<endl;cout<<" 3.按平均分降序显示所有学生信息"<<endl;cout<<" 4. 退出"<<endl;student *ptr=new student[21];ptr[1].set(1,"小明",88,67);//已存入的学生信息ptr[2].set(2,"小李",68,82);ptr[3].set(3,"小王",68,62);ptr[4].set(4,"小陈",79,82);ptr[5].set(5,"小张",63,82);ptr[6].set(6,"小红",68,73);ptr[7].set(7,"小木",62,77);ptr[8].set(8,"小添",65,86);ptr[9].set(9,"小天",68,82);ptr[10].set(10,"张三",88,82);ptr[11].set(11,"李四",98,82);ptr[12].set(12,"王五",88,81);ptr[13].set(13,"小月",58,82);ptr[14].set(14,"小鑫",78,80);ptr[15].set(15,"小良",68,92);ptr[16].set(16,"小成",68,82);ptr[17].set(17,"小敏",98,92);ptr[18].set(18,"小问",88,88);ptr[19].set(19,"小文",48,82);ptr[20].set(20,"小瑞",98,62);//已存入的学生信息int numlock;int j=0;int i,k,m;int q,e,r;string w;while(1){cout<<" 按0,1,2,3,4进行操作"<<endl;cin>>numlock;switch(numlock){case 0:cout<<"输入想查询的学号"<<endl;cin>>i;if(i==j){cout<<"该学号信息已被删除"<<endl;break;}ptr[i].show();break;case 1:cout<<"输入想删除的学号"<<endl;cin>>j;delete[j]ptr;cout<<"删除成功"<<endl;break;case 2:cout<<"输入想添加的学号信息"<<endl;cin>>k;if(k!=j){cout<<"该学号信息已经存在，添加失败"<<endl;break;}cout<<"重新输入添加的学号"<<endl;cin>>q;cout<<"输入姓名"<<endl;cin>>w;cout<<"输入科目一的成绩"<<endl;cin>>e;cout<<"输入科目二的成绩"<<endl;cin>>r;ptr[k].set(q,w,e,r);break;case 3:for( m=1;m<20;m++){for(int n=m+1;n<20;n++){if(ptr[m].average()<ptr[n].average()){student a;a=ptr[m];ptr[m]=ptr[n];ptr[n]=a;}}ptr[m].show();}break;case 4:cout<<"谢谢使用"<<endl;return 0;default:cout<<"number out of 0 to 4"<<endl;break;}}return 0;}三．测试结果二叉排序树储存数据界面（储存学生信息略）创建二叉树：插入节点：删除节点：非递归遍历：退出：数组储存学生信息界面分析查找效率：因为二叉树查找要创建二叉树，而数组查找只创建一个数组，二叉树的创建时间比较长，所以对于数据量较少的情况下数组的查找效率比较高。

n->+∞， T(n)的数量级称为渐进时间复杂
度，记作
T(n)=O(f(n))
渐进时间复杂度是算法的时间性能主要评价 标准
例２ {temp=i;j=j;j=temp} 语句频度为１，即时间复杂度为Ｏ(1)
例３、for(i=1;i<n+1;++i) {++x;s+=x;}
语句频度为：2n 其时间复杂度为：O(n) 即时间复杂度为线性阶。
数据结构在各种软件系统中所起的作用
程序=算法+数据结构★
选择合适的数据结构是解决应用问题的关 键步骤
例1、电话号码查询系统
设有一个电话号码薄，它记录了N个人的名字 和其相应的电话号码，假定按如下形式安排：
(a1，b1)(a2，b2)…(an，bn) 其中ai，bi(i=1，2…n) 分别表示某人的名字
数据结构的逻辑结构，简称数据结构
数据之间的相互关系称为逻辑结构。通常分为2 类基本结构： 一、线性结构 结构中的数据元素之间存在一 对一的关系。（1-4章） 二、非线性结构 结构中的数据元素之间存 在一对多的关系（5-7章）
学生成绩表数据结构
直接前趋 直接后趋 开始结点 终端结点
结点间的关系构成了逻辑结构 计算机如何表示各结点间的关系？ 如何进行查找、删除、插入等数学运算？
主要内容
1.2 数据结构及计算机系统中作用 （记） 1.1 基本概念和术语（记） 1.3 算法描述和分析 （领会）
重点：数据结构的逻辑结构、存储结构及数 据运算的概念和关系
难点：算法复杂度分析
1.2数据结构
计算机是一门研究用计算机进行信息表示和 处理的科学。这里面涉及到两个问题：