大连理工大学数据结构(一)上机作业答案——张老师
1．将顺序表逆置，要求用最少的附加空间。
参考答案
#include
#include
#include
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
#define LIST_INIT_SIZE 100
#define LISTTINCREMENT 10
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
//创建空顺序表
Status InitList_Sq(SqList &L){
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)exit(OVERFLOW);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return OK;
}
//创建顺序表，插入元素
void ListInput_Sq(SqList &L){
int n,i;
printf("input the length of Sqlist:");
scanf("%d",&n);
L.length=n;
for(i=0;i { printf("input elem:"); scanf("%d",&L.elem[i]); } } //输出顺序表中的元素 void ListOutput_Sq(SqList L){ int i,n; n=L.length; for(i=0;i printf("%2d",L.elem[i]); } //顺序表逆置 void ReverseList_Sq(SqList &L){ int i,n; ElemType p; n=L.length; for(i=0;i { p=L.elem[i]; L.elem[i]=L.elem[n-i-1]; L.elem[n-i-1]=p; } } void main(){ SqList L; InitList_Sq(L); ListInput_Sq(L); ListOutput_Sq(L); ReverseList_Sq(L); printf("\n"); printf("输出结果为："); ListOutput_Sq(L); printf("\n"); } 2．从键盘读入n个整数（升序），请编写算法实现： （1）CreateList()：建立带表头结点的单链表； （2）PrintList()：显示单链表，（形如：H->10->20->30->40）; （3）InsertList()：在有序单链表中插入元素x； （4）ReverseList()：单链表就地逆置； （5）DelList()：在有序单链表中删除所有值大于mink且小于maxk 的元素。 选作：使用文本菜单完成功能选择及执行。 参考答案： #include #include #include #define OK 1 #define ERROR 0 typedef int ElemType; typedef int Status; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; void CreateList(LinkList &L,int n){ int i; LNode *p,*q; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; q=L; printf("请输入所要建立的单链表所包含的元素："); for(i=0;i p=(LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data); p->next=NULL; q->next=p; q=p; } } void PrintList(LinkList L){ LNode *p; p=L->next; while(p){ printf("%d",p->data); p=p->next; } printf("\n"); } void InsertList(LinkList L,ElemType m){ LNode *p,*q,*s; p=L; q=L->next; while(q&&q->data p=q; q=q->next; } if(q){ s=(LinkList)malloc(sizeof(LNode)); s->data=m; s->next=q; p->next=s; } else{ s=(LinkList)malloc(sizeof(LNode)); s->data=m; s->next=NULL; p->next=s; } } void ReverseList(LinkList &L){ LNode *p,*q; if(L->next&&L->next->next){ p=L->next; q=p->next; p->next=NULL; while(q){ p=q; q=q->next; p->next=L->next; L->next=p; } } } void DeleteList(LinkList &L,ElemType mink,ElemType maxk){ LNode *p=L,*q; while(p->next&&p->next->data<=mink) p=p->next; q=p; while(q&&q->data q=q->next; p->next=q; } void main(){ LinkList L; int n,number; ElemType e,mink,maxk; do{ printf("*********************************\n"); printf("建立单链表请按1.\n"); printf("显示单链表请按2.\n"); printf("有序插入新元素请按3.\n"); printf("单链表就地逆置请按4.\n"); printf("删除大于mink且小于maxk的所有元素请按5.\n"); printf("退出请按0.\n"); printf("*********************************\n"); printf("\n请选择操作：\n"); scanf("%d",&number); switch(number){ case 1: printf("请输入单链表中的节点个数："); scanf("%d",&n); CreateList(L,n); break; case 2: printf("要执行本操作请先建立单链表，请输入单链表中的节点个数："); scanf("%d",&n); CreateList(L,n); printf("单链表为："); PrintList(L); break; case 3: printf("要执行本操作请先建立单链表，请输入单链表中的节点个数："); scanf("%d",&n); CreateList(L,n); printf("请输入有序表中插入的值："); scanf("%d",&e); InsertList(L,e); PrintList(L); break; case 4: printf("要执行本操作请先建立单链表，请输入单链表中的节点个数："); scanf("%d",&n); CreateList(L,n); printf("单链表逆置："); ReverseList(L); PrintList(L); break; case 5: printf("要执行本操作请先建立单链表，请输入单链表中的节点个数："); scanf("%d",&n); CreateList(L,n); printf("请输入mink和maxk："); scanf("%d%d",&mink,&maxk); DeleteList(L,mink,maxk); PrintList(L); break; } }while(number!=0);} 栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。 例如，输入表达式：a+b/c-(d*e+f)*g 输出其后缀表达式：abc/+de*f+g*- 参考答案： #include #include #include #include #define OVER -2 #define OK 1 #define ERROR 0 #define ture 1 #define false 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef char SElemType; typedef char ElemType; typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack;//定义结构 int InitStack(SqStack&S){ S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base) exit(OVER); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }//建栈 int Push(SqStack&S,SElemType e){ if(S.top-S.base>=S.stacksize) { S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S.base) exit(OVER); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; }//插入 int GetTop(SqStack&S,SElemType &e){ if(S.top==S.base)return ERROR; e=*(S.top-1); }//获取栈顶元素 int Pop(SqStack&S,SElemType &e){ if(S.top==S.base) return ERROR; e=*--S.top; return OK; }//删除栈顶并用e返回值 int StackEmpty(SqStack S){ if(S.top==S.base) return ture; else return false; } int Pass(char suffix[],SElemType ch) { char *p; p=suffix; while(*p!='\0') p++; *p=ch; *(p+1)='\0'; return 0; }//把操作数ch传进数组suffix void add(char exp[]) { char *p; p = exp; while (*p != '\0') ++p; *p = '#'; *(p + 1) = '\0'; }//在表达式结尾加结束符 void del(char suffix[]) { char *p; p = suffix; while (*p != '#') p++; *p = '\0'; } //将字符串结尾附成\0 int Precede(char c) { if (c == '*' || c == '/') return 2; if (c == '+' || c == '-') return 1; if (c == '(' || c == ')') return -1; else return -2; }//优先级比较 void transform(char suffix[], char exp[]) { char *p, ch, c; p = exp; ch = *p; SqStack S; InitStack (S); Push (S, '#'); while(!StackEmpty(S)) { if (ch>='a'&&ch<='z') { Pass(suffix, ch); } else { switch (ch) { case '(': Push(S, ch); break; case ')': Pop (S, c); while(c != '(') { Pass(suffix, c); Pop(S, c); } break; default : if (ch == '#') while(!StackEmpty(S)) { Pop(S, c); Pass(suffix, c); } else { GetTop(S, c); while (Precede(c) >= Precede(ch)) { Pop(S, c); Pass(suffix, c); GetTop(S, c); } Push(S, ch); } break; } } if (ch != '#') ch = *++p; } }//后缀表达式转化 int main() { char suffix[100]; suffix[0] = '\0'; char exp[100]; printf ("请输入一个表达式：\n"); gets(exp); add(exp); transform (suffix, exp); del(suffix); printf ("后缀表达式为：%s\n", suffix); return 0; } 第三次作业 二叉树采用二叉链表存储，试设计算法实现： 1．CreateBT(BiTree &T)：从键盘输入二叉树的先序遍历序列字符串（以”#”代表空结点），建立其二叉链表； 如输入：AB#D##CE#F###则建立如下图所示二叉树的二叉链表2．ExchangeBT(BiTree T): 设计递归算法实现二叉树中所有结点的左右孩子交换； 3． CountLeaf(BiTree T, TElemType x, int &count ): 统计以值为x 的结点为根的子树中叶子结点的数目； 4． DispBiTree(BiTree T, int level ) : 按树状打印二叉树。 打印得到：#C ###F ##E A ##D #B 提示：对于根为T ，层次为level 的子树： ① 打印其下一层(level+1层)右子树； ② 打印根结点； ③ 打印其下一层(level+1层)左子树； *结点左边的’#’个数为其层次数* 参考答案： #include #include typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //输入先序序列，创建二叉树的二叉链表 void CreateBT(BiTree &T){ char ch; scanf("%c",&ch); if(ch=='#') T=NULL; else{ T=(BiTNode *)malloc(sizeof(BiTNode)); T->data=ch; CreateBT(T->lchild); CreateBT(T->rchild); } } //交换二叉树中结点的左右孩子 void ExchangeBT(BiTree &T){ BiTree temp; if(T){ temp=T->lchild; B C F A E D T->lchild=T->rchild; T->lchild=temp; ExchangeBT(T->lchild); ExchangeBT(T->rchild); } } //查找值为x的结点 BiTree SearchTree(BiTree T,char x){ BiTree NTree; if(T){ if(T->data==x) return T; NTree=SearchTree(T->lchild,x); if(NTree==NULL) NTree=SearchTree(T->rchild,x); return NTree; } return NULL; } //统计一x为根的子树中叶子结点的个数 void LeafCount(BiTree T,int &count){ if(T){ if((T->lchild==NULL)&&(T->rchild==NULL)) count++; LeafCount(T->lchild,count); LeafCount(T->rchild,count); } } //按树状打印输出二叉树的元素，level表示结点的层次void PrintBiTree(BiTree T,int level){ int i; if(T){ PrintBiTree(T->lchild,level+1); for(i=0;i printf("#"); printf("%c\n",T->data); PrintBiTree(T->rchild,level+1); } } void main(){ BiTree T,SecT; char Secch; int count=0; printf("输入先序序列建立二叉树：\n"); CreateBT(T); printf("二叉树为：\n"); PrintBiTree(T,0); printf("交换结点的左右孩子\n"); ExchangeBT(T); printf("\n此时二叉树为：\n"); PrintBiTree(T,0); printf("输入要统计叶子结点个数的子树的根："); fflush(stdin);//清理缓存 scanf("%c",&Secch); SecT=SearchTree(T,Secch); LeafCount(SecT, count); printf("叶子结点数为：%d\n",count); } 数据结构上机实验报告 学院：电子工程学院 专业：信息对抗技术 姓名： 学号： 教师：饶鲜日期： 目录 实验一线性表................................................. - 4 - 一、实验目的................................................ - 4 - 二、实验代码................................................ - 4 - 三、实验结果............................................... - 14 - 四、个人思路............................................... - 15 -实验二栈和队列.............................................. - 15 - 一、实验目的............................................... - 15 - 二、实验代码............................................... - 16 - 三、实验结果............................................... - 24 - 四、个人思路............................................... - 25 -实验三数组.................................................. - 26 - 一、实验目的............................................... - 26 - 二、实验代码............................................... - 26 - 三、实验结果............................................... - 28 - 四、个人思路............................................... - 28 -实验四树.................................................... - 29 - 一、实验目的............................................... - 29 - 二、实验代码............................................... - 29 - 工科数学分析上机作业 说明：以下两道题均是使用Matlab 语言，且在Matlab 7.0中运行通过。 1.（两个重要极限）计算下列函数的函数值并画出图形，观察两个重要极限值。 (1)y=f(x)=; (2)y=f(x)=. sin x x (1+x)1x 解：（1）求解过程如下： >> syms x >> y=limit(sin(x)/x) y = 1 >> ezplot(sin(x)/x,[-10*pi,10*pi]) >> ezplot(sin(x)/x,[-1*pi,1*pi]) 其图形如下： （2）求解过程如下：>> syms x >> y=(1+x)^(1/x) y = (1+x)^(1/x) >> y=limit((1+x)^(1/x)) y = exp(1) >> ezplot((1+x)^(1/x),[-1000,1000]) >> ezplot((1+x)^(1/x),[-10,10]) >> ezplot((1+x)^(1/x),[-1,1]) 其图像如下： 分析如下：（1）当x 取值为[-30,30]时，由该题的第一个图像可以看到，函数值在不断震荡，一会为正数，一会为负数。 而当x 取值为[-3，3]时，函数值始终大于0。当x 趋近于0时，由该题的第二个图像可以得到函数值为1。 另外，该结论也可以由夹逼法则证明，结果不变，当x 趋近于0时，函数值仍为1。 （2）由该题的三个图像可以知道，该函数在定义域内为单调递减函数。且由该题的第一和二个图像知道，当x 在 [0,10]区间内，函数递减趋势非常迅速。由该题的第三个图像知道，当x 趋于0 时，函数值为自然对数的底数 e ,即约为2.71828. 3.计算f(x)=, 12+1√2π ∫x 0e ?t 2/2dt 1?x ?3的函数值{f （0.1k ）;k=1,2,…,30}.计算结果取7位有效数字。 解：计算过程为： >> f1= @(t) exp(-(t).^2/2) f1 = @(t) exp(-(t).^2/2) >> for i=1:30 华农数据结构上机实验答案 数据结构上机答案 1.1顺序线性表的基本操作 #include { newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*size of(ElemType)); L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; } int ListDelete_Sq(SqList &L,int i,int &e) { ElemType *q,*p; if(i<1||i>L.length) return ERROR; p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p<=q;p++) *(p-1)=*p; L.length--; return OK; } int main() { SqList T; int a,i; ElemType e,x; if(InitList_Sq(T)) { printf("A Sequence List Has Created.\n"); } while(1) { printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a) 2011上机实习基本要求及内容 上机实习基本目标 计算机学科分为理论、抽象、设计三个形态。 数据结构是计算机学科的重要分支研究领域之一。在算法分析与设计、操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等专业基础课和专业课程中均有涉及。对特定领域或应用要使用到头特定的数据结构：编译系统要使用栈、散列表及语法树；操作系统中要用队列、存储管理表及目录树等；数据库系统要用线性表、多链表及索引树等；在人工智能领域依求解问题性质的差异将涉及到各种不同的数据结构，如广义表，集合、搜索树及各种有向图等等。 通过数据结构上机实习要让学生掌握链表、树、图是如何实现的，进一步从理论、抽象、设计的角度来考虑问题。第一，让学生真正理解“数据结构＋算法＝程序”。程序不仅仅是求解算法的实现，也要配有恰当的数据结构；第二，培养学生数据抽象的能力。让学生了解链表、树、图等数据结构是如何实现的，特别要加强对数据逻辑关系的分析与认识；第三，培养学生使用数据结构的能力。要把数据结构与算法的理论分析与编程实践相结合，灵活运用于实际解题中。 需要强调以下几个方面的知识和能力： （1）掌握并能够灵活应用基本数据结构的抽象数据类型、存储方法、主要的算法，特别是线性结构、二叉树、树、图、文件等； （2）掌握并应用常用的排序、检索和索引算法和方法； （3）掌握基本的算法设计和分析技术，并结合具体的设计，对所设计的数据结构和算法进行分析； （4）在进行程序设计、调试中，注意综合应用，将所学到的数据结构和算法知识应用到对具体数据对象的特性分析。结合实际例子进行设计，选择合适的数据结构和存贮结构以及相应的算法。 上机实习基本要求 1．合理地选用组织数据、有效地表示数据、正确地处理数据，清晰地表述算法。 2．完成选定题目，按照规范格式（附件一）写出实习报告(原问题、设计算法、DS、程序、给出实例并分析结果、讨论T(n))。 3．线性关系、非线性关系、算法三部分的实习报告电子版提交日期在上机后2日内提交；第四次机考电子版在上机结束时提交(电子版交liuxd@https://www.wendangku.net/doc/1616097085.html,，将四次上机汇总打印纸版笔试前1周交西1楼711室)；请按时提交注意上交电子版与纸版应一致。 4. 请按照附件给定报告内容格式安排。 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 2016年理工大学优化方法上机大作业学院： 专业： 班级： 学号： ： 上机大作业1： 1.最速下降法： function f = fun(x) f = (1-x(1))^2 + 100*(x(2)-x(1)^2)^2; end function g = grad(x) g = zeros(2,1); g(1)=2*(x(1)-1)+400*x(1)*(x(1)^2-x(2)); g(2) = 200*(x(2)-x(1)^2); end function x_star = steepest(x0,eps) gk = grad(x0); res = norm(gk); k = 0; while res > eps && k<=1000 dk = -gk; ak =1; f0 = fun(x0); f1 = fun(x0+ak*dk); slope = dot(gk,dk); while f1 > f0 + 0.1*ak*slope ak = ak/4; xk = x0 + ak*dk; f1 = fun(xk); end k = k+1; x0 = xk; gk = grad(xk); res = norm(gk); fprintf('--The %d-th iter, the residual is %f\n',k,res); end x_star = xk; end >> clear >> x0=[0,0]'; >> eps=1e-4; >> x=steepest(x0,eps) 2.牛顿法： function f = fun(x) f = (1-x(1))^2 + 100*(x(2)-x(1)^2)^2; end function g = grad2(x) g = zeros(2,2); 《数据结构实验指导书》答案 实验一： 1、请编写函数int fun(int *a, int *b),函数的功能是判断两个指针a和b所指存储单 元的值的符号是否相同；若相同函数返回1，否则返回0。这两个存储单元中的值都不为0。在主函数中输入2个整数、调用函数fun、输出结果。 #include 数fun、输出结果。 #define N 10 #include 习题六树和二叉树6.1 单项选择题 (A) (B) (C) (D) 图8.7 4棵二叉树 1. 如图8.7所示的4棵二叉树，_ _不是完全二叉树。 图8.8 4棵二叉树 2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。 3. 在线索化二叉树中，t所指结点没有左子树的充要条件是B__o A. t —> left二NULL B. t —> ltag=1 C. t —> ltag=1 且t —> left=NULL D. 以上都不对 4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说 法_B__ o A.正确 B. 错误 5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 _A__。 A.正确 B. 错误 6. 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法 _B_o A.正确 B. 错误 7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为—B__o A. 2h B. 2h-1 C. 2h+1 D. h+1 a 8. 如图8.9所示二叉树的中序遍历序列 B o 图8.9 一棵二叉树 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 9. 已知某二叉树的后序遍历序列是d abec，中序遍历序 列是debac，它的前序遍历 序列是D ___ 。 A. acbed B. decab C. deabc D. cedba 10. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 11?假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结 点数为个。B A. 15 B. 16 C. 17 D. 47 12. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是D _____ 。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、 小于其右孩子的值。这种说法__B__ o A.正确 B. 错误 14. 按照二叉树的定义，具有3个结点的二叉树有_。__种。 A. 3 B. 4 C. 5 D. 6 15. 一棵二叉树如图8.10所示，其中序遍历的序列为 数据结构实验报告 一．顺序表 要求：实现顺序表的初始化、在指定位置插入和删除元素。 算法思路：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的初始化操作就是为顺序表分配一个预定义大小的空间，并将线性表的当前长度设为“0”。线性表的插入操作是在线性表的第i-1个数据元素和第i个元素之间插入新的数据元素，使得长度为n的线性表变成长度为n+1的线性表，而删除恰好相反长度变为n-1的线性表，而且删除点后面的元素要往前移动一个位。 程序代码： #include for(i=0;i 函数定义： % 目标函数 function f = fun(x) fm=0; for i=1:499 fmi = (1-x(i))^2 + 100*(x(i+1)-x(i)^2)^2; fm=fm+fmi; end f =fm; end % 梯度 function g = grad(x) g = zeros(500,1); g(1)=2*(x(1)-1)+400*x(1)*(x(1)^2-x(2)); for i=2:499 g(i)=2*(x(i)-1)+400*x(i)*(x(i)^2-x(i+1))+200*(x(i)-x(i-1)^2); end g(500) = 200*(x(500)-x(499)^2); end % 二阶梯度 function g = grad2(x) g = zeros(500,500); g(1,1)=2+400*(3*x(1)^2-x(2)); g(1,2)=-400*x(1); for i=3:500 g(1,i)=0; end for i=1:498 g(500,i)=0; end g(500,499)=-400*x(499); g(500,500)=200; for i=2:499 for j=1:500 if j==i-1 g(i,j)= -400*x(i-1); elseif j==i g(i,j)= 2+400*(3*x(i)^2-x(i+1))+200; elseif j==i+1 g(i,j)= -400*x(i); else g(i,j)=0; end end end end 1.最速下降法 function x_star = steepest(x0,eps) gk = grad(x0); res = norm(gk); k = 0; while res > eps && k<=50000 dk = -gk; 《数据结构》上机作业 (黑色--必做；蓝色--选作) 线性表 1、某软件公司大约有30名员工，每名员工有姓名、工号、职务等属性，每年都有员工离 职和入职。 把所有员工按照顺序存储结构建立一个线性表，建立离职和入职函数，当有员工离职或入职时，修改线性表，并且打印最新的员工名单。（动态分配存储，malloc，realoc）2、约瑟夫（Josephus）环问题：编号为1,2,3,…,n的n个人按顺时针方向围坐一圈，每 人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一人开始重新从1报数，如此下去，直到所有人全部出列为止。 建立n个人的单循环链表存储结构，运行结束后，输出依次出队的人的序号。（必须用链表） 栈和队列 3、某商场有一个100个车位的停车场，当车位未满时，等待的车辆可以进入并计时；当车 位已满时，必须有车辆离开，等待的车辆才能进入；当车辆离开时计算停留的的时间，并且按照每小时1元收费。汽车的输入信息格式可以是（进入/离开，车牌号，进入/离开时间），要求可以随时显示停车场内的车辆信息以及收费历史记录。（选作，用指针轮询数组，有空位就入，利用时间函数计时） 4、某银行营业厅共有6个营业窗口，设有排队系统广播叫号，该银行的业务分为公积金、 银行卡、理财卡等三种。公积金业务指定1号窗口，银行卡业务指定2、3、4号窗口，理财卡业务指定5、6号窗口。但如果5、6号窗口全忙，而2、3、4号窗口有空闲时，理财卡业务也可以在空闲的2、3、4号窗口之一办理。客户领号、业务完成可以作为输入信息，要求可以随时显示6个营业窗口的状态。（复杂，选作） 5、4阶斐波那契序列如下：f0=f1=f2=0, f3=1,…,f i=f i-1+f i-2+f i-3+f i-4， 利用容量为k=4的循环队列，构造序列的前n+1项（f0, f1 , f2 ,… fn ），要求满足f n≤200而f n+1 >200。 6、八皇后问题：设8皇后问题的解为(x1, x2, x3, …,x8), 约束条件为：在8x8的棋盘上， 其中任意两个xi 和xj不能位于棋盘的同行、同列及同对角线。要求用一位数组进行存储，输出所有可能的排列。 7、迷宫求解：用二维矩阵表示迷宫，自动生成或者直接输入迷宫的格局，确定迷宫是否能 走通，如果能走通，输出行走路线。 8、英国人格思里于1852年提出四色问题(four colour problem，亦称四色猜想），即在为一平 面或一球面的地图着色时，假定每一个国家在地图上是一个连通域，并且有相邻边界线的两个国家必须用不同的颜色，问是否只要四种颜色就可完成着色。现在给定一张地图，要求对这张地图上的国家用不超过四种的颜色进行染色。 要求建立地图的邻接矩阵存储结构，输入国家的个数和相邻情况，输出每个国家的颜色代码。 数组与广义表 1．将顺序表逆置，要求用最少的附加空间。 参考答案 #include 实习一： 1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。 2、设有一个单位的人员工资有如下信息：name、department、 base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。请编写能够完成上述工作的程序。 代码如下： 1.#include 《数据结构》课程上机实验指导书 实验一 【实验名称】顺序表的基本算法 【实验目的】 创建一个顺序表，掌握线性表顺序存储的特点。设计和验证顺序表的查找、插入、删除算法。 【实验要求】 （1）从键盘读入一组整数，按输入顺序形成顺序表。并将创建好的顺序表元素依次打印在屏幕上。 设计一个带选择菜单的主函数，菜单中具备任意选择删除、插入、查找数据元素（2）的功能。 当选择删除功能时，从键盘读入欲删除的元素位置或元素值，按指定方式删除；3（）当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号。 （4）每种操作结束后，都能在屏幕上打印出此时顺序表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 上机编写程序。2、编译。3、调试。4、 综合实例！，2-62-8！带菜单的主函数参考书上2.5，，，书上参考算法例程：2-12-42-5注意：顺序表的结构体！typedef struct { datatype items[listsize]; int length; }SpList; 实验二 【实验名称】单链表的基本算法 【实验目的】 创建一个单链表，掌握线性表链式存储的特点。设计和验证链表的查找、插入、删除、求表长的算法。【实验要求】 （1）从键盘读入一组整数，按输入顺序形成单链表。并将创建好的单链表元素依次打印在屏幕上。（注意：选择头插法或者尾插法！） 设计一个带选择功能菜单的主函数，菜单中至少具备任意选择删除、插入、查找（2）数据元素，和求单链表表长等几项功能。 当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插）（3入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。 （4）每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 、上机编写程序。2 编译。3、调试。4、 综合实例！！带菜单的主函数参考书上，2-132-15，2-172.5，，书上参考算法例程：2-102-12 另外，注意，指针的初始化！指针的操作必须谨慎！链表的结构体如下：typedef struct Node { Datatype ch; struct Node *next; }LNode, *Pnode, *Linklist; 实验三 第一次上机作业 1.利用Matlab自带命令产生1000个均匀随机变量服从U(0,1)。 >>unifrnd(0,1,20,50) ans= Columns1through10 0.81470.65570.43870.75130.35170.16220.10670.85300.78030.5470 0.90580.03570.38160.25510.83080.79430.96190.62210.38970.2963 0.12700.84910.76550.50600.58530.31120.00460.35100.24170.7447 0.91340.93400.79520.69910.54970.52850.77490.51320.40390.1890 0.63240.67870.18690.89090.91720.16560.81730.40180.09650.6868 0.09750.75770.48980.95930.28580.60200.86870.07600.13200.1835 0.27850.74310.44560.54720.75720.26300.08440.23990.94210.3685 0.54690.39220.64630.13860.75370.65410.39980.12330.95610.6256 0.95750.65550.70940.14930.38040.68920.25990.18390.57520.7802 0.96490.17120.75470.25750.56780.74820.80010.24000.05980.0811 0.15760.70600.27600.84070.07590.45050.43140.41730.23480.9294 0.97060.03180.67970.25430.05400.08380.91060.04970.35320.7757 0.95720.27690.65510.81430.53080.22900.18180.90270.82120.4868 0.48540.04620.16260.24350.77920.91330.26380.94480.01540.4359 0.80030.09710.11900.92930.93400.15240.14550.49090.04300.4468 0.14190.82350.49840.35000.12990.82580.13610.48930.16900.3063 0.42180.69480.95970.19660.56880.53830.86930.33770.64910.5085 0.91570.31710.34040.25110.46940.99610.57970.90010.73170.5108 0.79220.95020.58530.61600.01190.07820.54990.36920.64770.8176 0.95950.03440.22380.47330.33710.44270.14500.11120.45090.7948 Columns11through20 0.64430.31110.08550.03770.03050.05960.17340.95160.03260.2518 0.37860.92340.26250.88520.74410.68200.39090.92030.56120.2904 0.81160.43020.80100.91330.50000.04240.83140.05270.88190.6171 0.53280.18480.02920.79620.47990.07140.80340.73790.66920.2653 0.35070.90490.92890.09870.90470.52160.06050.26910.19040.8244 0.93900.97970.73030.26190.60990.09670.39930.42280.36890.9827 0.87590.43890.48860.33540.61770.81810.52690.54790.46070.7302 习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。 解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else {p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); } 2016年大连理工大学优化 方法上机大作业 -标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII 2016年大连理工大学优化方法上机大作业学院： 专业： 班级： 学号： 姓名： 上机大作业1： 1.最速下降法： function f = fun(x) f = (1-x(1))^2 + 100*(x(2)-x(1)^2)^2; end function g = grad(x) g = zeros(2,1); g(1)=2*(x(1)-1)+400*x(1)*(x(1)^2-x(2)); g(2) = 200*(x(2)-x(1)^2); end function x_star = steepest(x0,eps) gk = grad(x0); res = norm(gk); k = 0; while res > eps && k<=1000 dk = -gk; ak =1; f0 = fun(x0); f1 = fun(x0+ak*dk); slope = dot(gk,dk); while f1 > f0 + 0.1*ak*slope ak = ak/4; xk = x0 + ak*dk; f1 = fun(xk); end k = k+1; x0 = xk; gk = grad(xk); res = norm(gk); fprintf('--The %d-th iter, the residual is %f\n',k,res); end x_star = xk; end >> clear >> x0=[0,0]'; >> eps=1e-4; >> x=steepest(x0,eps) 实验报告 （2015 / 2016学年第二学期） 课程名称数据结构A 实验名称内排序算法的实现以及性能比较 实验时间2016 年 5 月26 日 指导单位计算机科学与技术系 指导教师骆健 学生姓名耿宙班级学号B14111615 学院(系) 管理学院专业信息管理与信息系统 —— 实习题名:内排序算法的实现及性能比较 班级 B141116 姓名耿宙学号 B14111615 日期2016.05.26 一、问题描述 验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速排序算法，使得当子集合小于10个元素师改用直接插入排序；使用随即数发生器产生大数据集合，运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。 二、概要设计 文件Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，冒泡排序BubbleSort()，两路合并排序Merge()，快速排序QuickSort()以及改进的快速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示： 三、详细设计 1.类和类的层次设计 在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机 生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函 数main的流程图： —— main() 2.核心算法 1)简单选择排序： 简单选择排序的基本思想是：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到数据结构上机实验报告
Removed_大连理工大学工科数学分析上机作业
华农数据结构上机实验答案
数据结构上机作业模板
数据结构实验报告全集
2016年大连理工大学优化方法上机大作业
数据结构上机实验答案
数据结构书面作业练习题
数据结构上机实验报告
大连理工大学优化方法上机大作业程序
数据结构上机作业
大连理工大学数据结构(一)上机作业答案——张老师
数据结构上机答案(c语言版)
数据结构上机实验指导
大连理工大学概率上机作业
数据结构上机例题及答案
大连理工大学优化方法上机大作业
南邮数据结构上机实验四内排序算法的实现以及性能比较
- 数据结构作业答案 大连理工大学
- 大工数据结构课程考试模拟试卷a
- 大工19春《数据结构》在线作业1
- 大连理工大学《数据结构》作业2016-参考答案
- 大连理工大学2018年《数据结构》考研大纲
- [大连理工大学]20春《数据结构》在线作业1-复习资料答案
- 大连理工大学《数据结构》作业 参考答案
- 大连理工大学数据结构(一)上机作业答案——张老师
- 数据结构作业答案(大连理工大学)
- 2021年大连理工大学810数据结构和计算机组成原理考研精品资料之历年真题汇编及考研大纲
- 2017年研究生考试大连理工大学810数据结构和计算机组成原理题库
- 大工数据结构课程考试模拟试卷A
- 39565大连理工大学大工19秋《数据结构》在线作业3答案
- 大连理工大学软件学院2014数据结构期末考试(学长手抄整理)
- 大工20秋《数据结构》在线作业3
- 2016年大连理工大学考研大纲——810数据结构和计算机组成原理
- 数据结构作业答案(大连理工大学)
- 0384.2021年大连理工大学810数据结构和计算机组成原理精品资料之严蔚敏《数据结构(C语言版)》复习提纲
- 大工16春《数据结构》开卷考试复习资料
- 大工20秋《数据结构》在线作业2【答案】