《大连理工大学《数据结构》作业2016-参考 答案》由会员分享，可在线阅读，更多相关《大连理工大学《数据结构》作业2016-参考 答案（26页珍藏版）》请在金锄头文库上搜索。
1、数据结构作业参考答案 作业作业 1. 线性表线性表 编程作业： 1 将顺序表逆置，要求用最少的附加空间。 参考答案参考答案 #include #include #include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int ElemType; typedef struct
2、ElemType *elem; int length; int listsize; SqList; /创建空顺序表创建空顺序表 Status InitList_Sq( SqList if (!L.elem) exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE; return OK; /顺序表在第顺序表在第 i 个元素之前插入个元素之前插入 e Status sxbcr(SqList if(iL.length+1) return (ERROR); else q= for(p=p=q;-p) *(p+1)=*p; *q=e; +L.l
3、ength; return (OK); /顺序表显示顺序表显示 void xsList(SqList L) int i=L.length,k; for(k=0;k10-20-30-40）; （3） InsertList()：在有序单链表中插入元素 x； （4） ReverseList()：单链表就地逆置； （5） DelList()：在有序单链表中删除所有值大于 mink 且小于 maxk 的 元素。 选作：使用文本菜单完成功能选择及执行。 参考答案：参考答案： #include #include 数据结构作业参考答案 #include #define TRUE 1 #define FALSE
4、 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int ElemType; typedef struct node ElemType data; struct node *link; Lnode, *LinkList; /头插法建立单链表头插法建立单链表 void Create_L1(LinkList int i; L=(LinkList)malloc(sizeof(Lnode); L-link = NULL; for (i = n; i
5、0; -i) p=(LinkList)malloc(sizeof(Lnode); scanf(“%d“, p- link = L- link; L- link = p; /尾插法建立单链表尾插法建立单链表 void Create_L2(LinkList int i; L=(LinkList)malloc(sizeof(Lnode); L-data=0; L-link=NULL; 数据结构作业参考答案 p=L; for(i=1;idata); s-link=NULL; p-link=s; p=s; /查找是否存在结点查找是否存在结点 e LinkList dlbcz(LinkList L, El
6、emType e) LinkList p=L-link; while(p!=NULL return (p); /在第在第 i 个元素之前插入结点个元素之前插入结点 e Status ListInsert_L(LinkList L, int i, ElemType e) LinkList p = L,s; int j = 0; while (p +j; if (!p | j i-1) return ERROR; s = (LinkList) malloc ( sizeof (Lnode); s-data = e; s-link = p-link; p-link = s; return OK; /
7、删除第删除第 i 个结点个结点 Status ListDelete_L(LinkList L, int i, ElemType int j = 0; 数据结构作业参考答案 while (p-link +j; if (!(p-link) | j i-1) return ERROR; q=p-link; p-link=q-link; e=q-data; free(q); return OK; /求第求第 i 个元素值个元素值 Status GetElem_L(LinkList L, int i, ElemType LinkList p=L-link; while(p j+; if(!p|ji) r
8、eturn ERROR; e=p-data; return OK; /显示单链表中元素显示单链表中元素 void xsList(LinkList L) LinkList p=L-link; while(p) printf(“%d “,p-data); p=p-link; /删除大于删除大于 mink 且小于且小于 maxk 的元素的元素 void DelList(LinkList while(p-link 数据结构作业参考答案 q=p; while(q p-link=q; /就地升序排序就地升序排序 void sh_sort(LinkList p-link=NULL; while(q) p=L
9、-link; pre=L; while(p p=p-link; u=q-link; pre-link=q; q-link=p; q=u; /就地逆置就地逆置 void nizhi(LinkList p-link=NULL; while(q) u=q-link; q-link=L-link; L-link=q; q=u; 数据结构作业参考答案 /有序表插入有序表插入 void yxcharu(LinkList pre=L; p=L-link; while(p s=(LinkList)malloc(sizeof(Lnode); s-data=e; s-link=p; pre-link=s; mai
10、n() LinkList L; int n,i,mink,maxk; ElemType e; char choice=0; while(choice!=q) printf(“n*n“); printf(“1.建立单链表建立单链表 “); printf(“2.取元素值取元素值 “); printf(“3.查找查找 n“); printf(“4.插入插入 “); printf(“5.删除删除 “); printf(“6.显示显示n“); printf(“7.删除大于删除大于 mink 且小于且小于 maxk 的元素值的元素值 “); printf(“8.就地升序排序就地升序排序n“); print
11、f(“9.就地逆置就地逆置 “); printf(“a.有序表插入有序表插入 “); printf(“q.退出退出n“); printf(“n 请选择操作：请选择操作：“); fflush(stdin); scanf(“%c“, 数据结构作业参考答案 switch(choice) case 1: printf(“请输入单链表中结点个数：请输入单链表中结点个数：“); scanf(“%d“, Create_L2(L,n); break; case 2: printf(“请输入元素位序请输入元素位序：“); scanf(“%d“, GetElem_L(L,i,e); printf(“元素值为元素值
12、为：%dn“,e); break; case 3: printf(“请输入要查找的元素请输入要查找的元素：“); scanf(“%d“, if(dlbcz(L,e) printf(“查找成功查找成功！“); else printf(“查找失败。查找失败。“); break; case 4: printf(“请输入插入位置请输入插入位置：“); scanf(“%d“, printf(“请输入要插入的元素请输入要插入的元素：“); scanf(“%d“, if(ListInsert_L(L,i,e) printf(“插入成功！单链表为：插入成功！单链表为：“); else printf(“插入失败
13、。插入失败。“); break; case 5: printf(“请输入删除位置请输入删除位置：“); scanf(“%d“, if(ListDelete_L(L,i,e) printf(“删除成功！删除成功！“); else printf(“删除失败。删除失败。n“); break; case 6: printf(“n 单链表为：单链表为：“); xsList(L); break; case 7: printf(“请输入请输入 mink 和和 maxk:“); scanf(“%d,%d“, DelList(L,mink,maxk); 数据结构作业参考答案 break; case 8: sh_
14、sort(L); break; case 9: nizhi(L); break; case a: printf(“请输入在有序表中插入的元素值请输入在有序表中插入的元素值:“); scanf(“%d“, yxcharu(L,e); break; 作业作业 2. 栈、队列、数组栈、队列、数组 非编程作业： 1 若进栈序列为 ABCD，请写出全部可能的出栈序列和不可能的出栈序列。 参考答案参考答案： 可能的出栈序列：(14 种) dcba cdba bacd cbda adcb cbad bdca acdb bcda acbd bcad abdc badc abcd 不可能的出栈序列：(10 种)
15、 dbca dbac dabc dacb dcab cabd cdab bdac cadb adbc 2 简要说明循环队列如何判断队满和队空？ 参考答案：参考答案： 当牺牲一个存储结点，约定以“队列头指针在队列尾指针的下一位置（指环 状的下一个位置） 上” 作为队列“满”状态的标志时， 循环队列判断队满的条件为： (rear+1) % MaxQsize=front；判断队空的条件为：front = rear。 3 设 A 为 n 阶对称矩阵， 采用压缩存储存放于一维数组 Fn(n+1)/2中 （从 F0 开始存放） ，请分别给出存放上三角阵时任一矩阵元素 aij（1i,jn）的地址 计算公式和存放下三角阵时任一矩阵元素 aij（1i,jn）的地址计算公式。 参考答案：参考答案： 存放存放下下三角阵时三角阵时，任一矩阵元素 aij（1i,jn）的地址计算公式为： i j1 1 -1 Loc(a )=Loc(a )+1* 2 ii jl
