数据结构实验作业二

算法与数据结构实验报告实验二实验名称：线性表实现集合运算姓名：卢丽娟学号：211006289专业：软件工程班级：二班指导教师：陈亦萍日期: 2012年3月24日一、实验目的本实验是要实现线性表的集合运算，通过该实验更深刻地理解线性结构的特点，学会并掌握线性表的顺序或链式表示和实现。

二、实验内容与实验步骤采用线性表表示集合，用线性表实现集合以及基本操作，实现两个集合的并、交、差运算。

用到的各种函数如下程序步骤所示。

步骤：1. 链表销毁void DestoryList_L(list& L){ list p=L->next,s;while(p){ s=p; p=p->next;free(s);}L->next=NULL;}2. 链表初始化void InitList(list &L){ L=NULL;}3. 往链表L中插入元素e，并按升序排列，如果L中已有元素e，则不插入ListInsert_L(list &L, char e){ list p=L->next,t,s; t = L;while(p!=NULL &&p->data<= e){ if(p->data==e) return OK;t=p; p=p->next;}s =(list)malloc(sizeof(LNode));s->data=e;s->next=p;t->next=s;return OK;}4. 创建链表,按字符串输入元素void CreateList_L(list &L, int n){ L =(list)malloc(sizeof(LNode));L->next=NULL;int i=0;for(i=n;i>0;i--){ char e; scanf("%c",&e);ListInsert_L(L,e);}getchar();}5.定义输入函数，分配存储空间void inputdata(list head)//定义输入函数{ list p;char tmp;scanf("%c",&tmp);while(tmp!='\n'){ p=(list)malloc(sizeof(struct LNode));//分配存储空间p->data=tmp;p->next=head->next;head->next=p;scanf("%c",&tmp); }}6.定义输出函数，初始化，并判断其是否为空void outputdata(list head)//定义输出集合函数{ list p;p=head->next;//初始化，p指向第一个结点while(p!=NULL)//判断是否为空{ printf("%c",p->data);p=p->next;} printf("\n");//输出集合函数}7.定义集合的并集函数，其中函数的数据元素均已按值非递减排列void MergeList(list head1,list head2,list head3)//定义集合的并集函数{//已知p1、p2中的数据元素按值非递减排列。

实验报告课程名称_______数据结构实验__________________ 实验项目___ 栈和队列的基本操作与应用____ 实验仪器_____________________________________系别 ___ 计算机学院_______________ 专业 __________________班级/学号______ _________学生姓名_____________________ __实验日期__________________成绩_______________________指导教师____ __________________一、实验内容：本次实验主要内容是表达式求值，主要通过栈和队列来编写程序，需要实现整数运算其中需要实现的功能有加减乘除以及括号的运用，其中包含优先级的判断。

二、设计思想1.优先级中加减、乘除、小括号、以及其他可以分组讨论优先级2.优先级关系用“>”“<”“=”来表示三种关系3.为实现运算符优先使用两个栈：OPTR 运算符栈与OPND操作符栈4.运用入栈出栈优先级比较等方式完成运算三、主要算法框架1.建立两个栈InitStack(&OPTR);InitStack(&OPND);2.Push“#”到 OPTR3.判断优先级做入栈出栈操作If“<” Push(&OPTR, c);If“=” Pop(&OPTR, &x)If“>” Pop(&OPTR, &theta);Pop(&OPND, &b);Pop(&OPND, &a);Push(&OPND, Operate(a, theta, b));四、调试报告遇到的问题与解决1.C语言不支持取地址符，用*S代替&S来编写代码2.一开始没有计算多位数的功能只能计算一位数，在几个中间不含运算符的数字中间做p = p*10+c运算。

数据结构第二次作业答案一、单项选择题1. C2. B3. A4. A5. D6. A7. D 8. C 9. D 10. C 11. D 12. C 13. A二、填空题1. 存储2. 先进先出3. 栈顶指针4. 队尾5. 一6. 局部变量7. 表尾8. 重数9. 3 10. 6 11. 6 12. 2h+1-1三、判断题1. 错2. 对3. 对4. 对5. 错6. 对7. 对8. 错9. 错四、运算题1.叶子结点数： 5单分支结点数：3两分支结点数：2三分支结点数：12.元素 34 56 58 63 94比较次数 2 1 3 4 43.左子树为空的所有单支结点：15,23,42,44右子树为空的所有单支结点：304.插入时造成不平衡的结点个数：45.结点 a b c d e出度 1 1 2 1 2入度 2 2 1 1 16.(1) 1,3,4,6,5,2 (3分)(2) 1,3,2,4,5,6 (3分)五、算法分析题1.利用"栈"作为辅助存储,将队列中的元素逆置（即相反次序放置）。

2.(1) q = q->lLink(2) return 1(3) return 03.1→21→32→34.(1) return PT(2) (PT=ParentPtr(BT->right,BT,X))(3) return NULL 或return 0六、算法设计题1.float poly(float x, float A[], int n) { if(!n) return A[0];else return x*poly(x, A, n-1)+A[n];}2.int BTreeHeight(BinTreeNode* BT){if(BT==NULL)//对于空树，返回-1并结束递归return –1;else{//计算左子树的高度int h1=BTreeHeight(BT->left); //计算右子树的高度int h2=BTreeHeight(BT->right); //返回树的高度if(h1>h2) return h1+1;else return h2+1;}}3.int BTreeLeafCount(BinTreeNode* BT){if(BT==NULL) return 0;else if(BT->left==NULL && BT->right==NULL) return 1;else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);}数据结构第三次作业答案一、单项选择题1. D2. A3. B4. C5. C6. A7. B 8. C 9. C 10. A 11. A 12. D 13. C二、填空题1. 2i+12. 最大值3. 20.54. 右子树5. 16. 右单旋转7. 2(n-1)8. 29. n-1 10. 高 11. 直接插入三、判断题1. 错2. 对3. 对4. 对5. 错6. 对7. 错8. 对四、运算题1.(1) 1,5,6,4,3,2(2) 1,5,3,2,6,42.顶点： 0 1 2 3 4 5 6路径长度： 0 16 10 14 25 21 313.拓扑序列：1,3,6,0,2,5,4,74.所有关键活动：<0,1>5,<1,3>10,<3,4>9,<4,5>12关键路径长度：365.（1）归并路数：5 （2）需要归并躺数：2答案解释：(1) 设归并路数为k，初始归并段个数m = 80，根据归并趟数计算公式S = ⎡log k m⎤ = ⎡log k80⎤ = 3得：k3≥80。

第二章线性表及其应用【实验目的】1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；4. 通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。

第一节知识准备一、线性表的逻辑结构线性表是由一组具有相同特性的数据元素组成的有限序列。

至于每个数据元素，它可以是一个数，一个符号，也可以是一页书，甚至更复杂的信息。

例如：26个英文字母构成一个线性表（A，B，C，…，Y，Z）一串数字构成另一个线性表（45，45，32，65，123）每个数据元素可以由若干数据项组成，常把此数据元素称为记录。

能唯一标识一个记录的数据项的值称为关键字。

如：一个学校的学生情况表如表2-1所示，表中每个学生的情况为一个记录，它由学号、姓名、性别、年龄、年级等五个数据项组成。

学号姓名性别年龄年级96001 张平女 21 大二96002 王极男 20 大一96003 膨磊男 23 大三96004 严正英女 19 大一96005 李强男 20 大二综上所述，线性表有如下特性：1．除第一个和最后一个元素以外，每个元素有且仅有一个直接前趋和一个直接后继；第一个结点只有直接后继，最后一个结点只有直接前趋。

2．线性表中的每个数据元素，其数据类型是一致的。

3．数据元素之间的相对位置是线性的，结构中的数据元素之间存在一个对一个的关系。

二、线性表的顺序表示和实现计算机的内存是由有限多个存储单元组成的，每个存储单元都有对应的整数地址，各存储单元的地址是连续编号的。

对于一个线性表，如果用一组连续的存储单元依次存放它的各个数据元素，这就是线性表的顺序分配。

也就是说，在线性表的顺序分配结构中，逻辑结构上相邻的数据元素，其物理位置也是相邻的。

若一个数据元素只占用一个存储单元，则这种分配方式如图2-1所示。

15春《数据结构》作业2一、单选题（共20 道试题，共100 分。

）V1.A. AB. BC. CD. D满分：5 分2.A. AB. BC. CD. D满分：5 分3. 如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用___。

A. 只有表头指针没有表尾指针的循环单链表B. 只有表尾指针没有表头指针的循环单链表C. 非循环双链表D. 循环双链表满分：5 分4. 在长度为n的顺表表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为___。

A. n-i+1B. n-iC. iD. i-1满分：5 分5. 下列四种排序中___的空间复杂度最大。

A. 插入排序B. 冒泡排序C. 堆排序D. 归并排序满分：5 分6. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着___。

A. 数据元素具有同一特点B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C. 每个数据元素都一样D. 数据元素所包含的数据项的个数要相等满分：5 分7. 排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为___。

A. 希尔排序B. 冒泡排序C. 插入排序D. 选择排序满分：5 分8. 算法分析的目的是___。

A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易读性和文档性满分：5 分9.A. AB. BC. CD. D满分：5 分10. 与单链表相比，双链表的优点之一是___。

A. 插入、删除操作更简单B. 可以进行随机访问C. 可以省略表头指针或表尾指针D. 顺序访问相邻结点更灵活满分：5 分11.A. AB. BC. CD. D满分：5 分12. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储___。

A. 数据的处理方法B. 数据元素的类型C. 数据元素之间的关系D. 数据的存储方法满分：5 分13.设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址是___。

数据结构实验报告2广东金融学院实验报告课程名称：数据结构实验编号 及实验名称实验二：排序和查找实验 系 别计算机科学与技术系姓 名 学 号 班 级 实验地点 实验日期 实验时数 6 指导教师同组其他成员无成 绩一、实验目的及要求1、 通过编写和调用直接插入排序、希尔排序、冒泡排序和快速排序四种排序算法实现数据排序，充分理解各种排序算法的算法思想、排序过程及各自的时间复杂度、稳定性。

2、 通过编写和调用顺序查找和二分查找算法实现数据查找，掌握两个查找算法的基本思想、实现方法和时间性能。

二、实验环境及相关情况（包含使用软件、实验设备、主要仪器及材料等）1、实验设备：微型计算机；2、软件系统：Windows XP 、DWMX 。

装订○○○○三、实验内容（一）排序（1）参照课本，分别编写Java程序，实现顺序表记录类RecordNode、类KeyType。

（2）参照课本，编写一个Java程序，实现顺序表类SeqList，并在其中添加成员函数：length()求顺序表的当前长度；display()输出数组元素的关键字；直接插入排序算法；带监视哨的直接插入排序；希尔排序算法；起泡排序算法；快速排序算法。

（3）编写主程序，循环选择调用以上5个排序算法，对数组元素排序,并输出排序过程。

（二）查找（1）在排序实验的基础上，在类SeqList中添加成员函数：不带监视哨的顺序查找算法；带监视哨的顺序查找算法；二分查找算法。

（2）编写主程序，循环选择调用以上3个查找算法，分别对键入的关键字记录进行成功和不成功查找public class KeyType implements Comparable<KeyType>{private int key;public KeyType(){}public KeyType(int key){this.key=key;}public int getKey(){return key;}public void setKey(int key){this.key=key;}public String toString(){return key +"";}public int compareTo(KeyType another){int thisVal=this.key;int anotherVal=another.key;return(thisVal<anotherVal? -1:(thisVal==anotherVal? 0:1));}}public class RecordNode{private Comparable key;private Object element;public Object getElement(){return element;}public void setElement(Object element){this.element=element;}public C omparable getKey(){r[j]=r[j-1];}r[i]=x;this.curlen++;}public void insertSort(){ //直接插入RecordNode temp;int i,j;for(i=1;i<this.curlen;i++){temp=r[i];for(j=i-1;j>=0&&temp.getKey().compareTo(r[j].getKey())<0;j--){r[j+1]=r[j];}r[j+1]=temp;}}public void shellSort(int[]d){ //希尔RecordNode temp;int i,j;for(int k=0;k<d.length;k++){int dk=d[k];for(i=dk;i<this.curlen;i++){temp=r[i];for(j=i-dk;j>=0&&temp.getKey().compareTo(r[j].getKey())<0;j-=dk){ r[j+dk]=temp;}}}}public void insertSortWithGuard(){ //带监视哨的直接插入int i,j;for(i=1;i<this.curlen;i++){r[0]=r[i];for(j=i-1;r[0].getKey().compareTo(r[j].getKey())<0;j--){r[j+1]=r[j];}r[j+1]=r[0];}}public void bubbleSort(){ //冒泡RecordNode temp;boolean flag=true;for(int i=1;i<this.curlen&&flag;i++){flag=false;for(int j=0;j<this.curlen-1;j++){if(r[j].getKey().compareTo(r[j+1].getKey())>0){temp=r[j];r[j]=r[j+1];r[j+1]=temp;flag=true;}}}}public int Partition(int i,int j){RecordNode pivot = r[j];while (i<j){while (i<j && pivot.getKey().compareTo(r[j].getKey())<=0){ j--;}if(i<j){r[i]=r[j];i++;}while(i<j && pivot.getKey().compareTo(r[i].getKey())>0){ i++;}if(i<j){r[j]=r[i];j--;}}r[i]=pivot;return i;}public void qSort(int low,int high){if(low<high){int pivotloc = Partition(low,high);qSort(low,pivotloc-1);qSort(pivotloc + 1,high);}}public void quickSort(){qSort(0,this.curlen - 1);}public int seqSearch(Comparable key){int i=0;int n=length();while(i<n&&r[i].getKey().compareTo(key)!=0){ i++;}if(i<n){return i;}else{return -1;}}public int seqSearchWithGuard(Comparable key){ int i=length()-1;r[0].setKey(key);while((r[i].getKey()).compareTo(key)!=0){ i--;}if(i>0){return i;}else{return -1;}}public int binarySearch(Comparable key){ if(length()>0){int low=0;int high=length()-1;while(low<=high){int mid=(low +high)/2;if(r[mid].getKey().compareTo(key)==0){return mid;}else if(r[mid].getKey().compareTo(key)>0){high=mid-1;}else{low=mid+1;}}}return -1;}}package paixu;import java.util.Scanner;import paixu.RecordNode;import paixu.SeqList;public class Test2{public static void main(String[] args) throws Exception{ Scanner in=new Scanner(System.in);while(true){SeqList a=new SeqList(6);String d[]={"25","20","15","35","10","55"};for(int i=0;i<6;i++){RecordNode c=new RecordNode(d[i]);a.insert(i,c);}System.out.print("原数组：");a.display();System.out.println("");System.out.println("输入0~5进行选择");System.out.println("1直接插入排序");System.out.println("2带监视哨的直接插入排序");System.out.println("3希尔排序");System.out.println("4冒泡排序");System.out.println("5快速排序");System.out.println("0退出");int g=in.nextInt();switch(g){case 0:return;case 1:a.insertSort();System.out.print("排序后:");a.display();System.out.println("");break;case 2:a.insertSortWithGuard();System.out.print("排序后:");a.display();System.out.println("");break;case 3:int[] aa={1,3,5};a.shellSort(aa);System.out.print("排序后:");a.display();System.out.println("");break;case 4:a.bubbleSort();System.out.print("排序后:");a.display();System.out.println("");break;case 5:a.quickSort();System.out.print("排序后:");a.display();System.out.println("");break;}}}}import java.util.Scanner;public class Test{public static void main(String[] args){while(1<2){SeqList a=new SeqList(4);Scanner in=new Scanner(System.in);for(int i=0;i<4;i++){try{System.out.println("输入第"+i+"个元素:");String c=in.next();RecordNode d=new RecordNode(c);a.insert(i, d);}catch(Exception e){System.out.println("错误："+e.getMessage());}}a.display();System.out.println("");System.out.println("不带监视哨顺序查找方法查找1的结果为"+a.seqSearch("1"));System.out.println("带监视哨顺序查找方法查找2的结果为"+a.seqSearchWithGuard("2"));System.out.println("二分查找方法查找3的结果为"+a.binarySearch("3"));}}}四、实验步骤及结果（包含简要的实验步骤流程、结论陈述，可附页）排序运行结果：查找运行结果：五、实验总结（包括心得体会、问题回答及实验改进意见）答:通过这次试验，编写和调用顺序查找和二分查找算法实现数据查找，我掌握两个查找算法的基本思想、实现方法和时间性能。

作业二作业二一、单项选择题1. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是（ C ）。

A.O(1)B. O(n)C. O(n2)D. O(nlog2n)2. 带表头的双向循环链表的空表满足（ B ）。

A. first＝NULL;B. first->rLink==firstC. first->lLink==NULLD. first->rLink==NULL3. 栈的插入和删除操作在( A )进行。

A. 栈顶B. 栈底C. 任意位置D. 指定位置4. 在一个顺序存储的循环队列中，队头指针指向队头元素的( A )位置。

A. 前一个B. 后一个C. 当前D. 后面5. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为( D )。

A. front+1 == rearB. rear+1 == frontC. front == 0D. front == rear6. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。

若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行( A )操作。

A. x=top->data; top=top->link;B. top=top->link; x=top->data;C. x=top; top=top->link;D. x=top->data;7. 为增加内存空间的利用率和减少溢出的可能性, 由两个栈共享一块连续的内存空间时, 应将两栈的( D )分别设在这块内存空间的两端。

A. 长度B. 深度C. 栈顶D. 栈底8. 在系统实现递归调用时需利用递归工作记录保存（ C ），当递归调用程序执行结束时通过它将控制转到上层调用程序。

A. 调用地址B. 递归入口C. 返回地址D. 递归出口9. 如果一个递归函数过程中只有一个递归语句，而且它是过程体的最后语句，则这种递归属于（ D ），它很容易被改写为非递归过程。