首页计算机计算机基础数据结构 10 数据结构作业详解.pptx

10 数据结构作业详解.pptx

页数:39页文件大小:578.8 KB来源: 数据结构ppt课件

本课件为数据结构课程作业详解,按章节编排典型作业题目,逐题给出算法思路、实现要点与参考代码,覆盖线性表、栈与队列、数组、树、图、查找与排序等章节,帮助学习者对照检查自己的实现并掌握标准解法。

数据结构作业详解封面,标示本课件为各章作业题目的讲解与代码实现
作业一题目页,列出顺序表逆置与单链表建立显示插入逆置删除等题目
建立单链表算法页,给出头插法建表代码与生成头结点的第一步示意
查看本课件的文字版(共 39 页,供检索与复制)

第1页:数据结构作业详解封面

数据结构作业详解

第2页:作业一线性表题目

作业1线性表1.将顺序表逆置,要求用最少的附加空间。(略)2.从键盘读入n个整数(升序),请编写算法实现:(1) CreateList():建立带表头结点的单链表;(2) PrintList():显示单链表,(H->10->20->30->40);(3) InsertList():在有序单链表中插入元素x;(4) ReverseList():单链表就地逆置;(5) DelList():在有序单链表中删除所有值大于mink且小于maxk的元素。typedef int ElemType;

typedef struct node {ElemType data;struct node *link;}Lnode, *LinkList;

第3页:建立单链表算法一

作业1线性表2. (1) CreateList():建立带表头结点的单链表;

void Create_L(LinkList&L, intn){LinkList p; int i;L=(LinkList)malloc(sizeof(Lnode));L->data=0; L->link = NULL;for (i = n; i > 0;--i){p=(LinkList)malloc(sizeof(Lnode));scanf("%d",&p->data);p-> link = L-> link;L-> link = p;}}生成头结点L头结点0^pan^

第4页:建立单链表算法二

作业1线性表2. (1) CreateList():建立带表头结点的单链表;

void Create_L(LinkList&L, intn){LinkList p; int i;L=(LinkList)malloc(sizeof(Lnode));L->data=0; L->link = NULL;for (i = n; i > 0;--i){p=(LinkList)malloc(sizeof(Lnode));scanf("%d",&p->data);p-> link = L-> link;L-> link = p;}}生成头结点L头结点0pan-1an^

第5页:建立单链表算法三

作业1线性表2. (1) CreateList():建立带表头结点的单链表;

void Create_L(LinkList&L, intn){LinkList p; int i;L=(LinkList)malloc(sizeof(Lnode));L->data=0; L->link = NULL;for (i = n; i > 0;--i){p=(LinkList)malloc(sizeof(Lnode));scanf("%d",&p->data);p-> link = L-> link;L-> link = p;}}生成头结点L头结点0an-1an^

第6页:建立单链表算法四

作业1线性表2. (1) CreateList():建立带表头结点的单链表;

void Create_L(LinkList&L, intn){LinkList p; int i;L=(LinkList)malloc(sizeof(Lnode));L->data=0; L->link = NULL;for (i = n; i > 0;--i){p=(LinkList)malloc(sizeof(Lnode));scanf("%d",&p->data);p-> link = L-> link;L-> link = p;}}生成头结点L头结点0a1a2^an^……

第7页:显示单链表算法

作业1线性表2. (2) PrintList():显示单链表,(H->10->20->30->40);

void xsList(LinkListL){LinkListp=L->link;while(p){printf("%d ",p->data);p=p->link;}}L头结点0a1a2^an^……

第8页:有序单链表插入算法

作业1线性表2. (3) InsertList():在有序单链表中插入元素x;

void yxcharu(LinkList &L, ElemTypee){LinkList pre,p,s;pre=L;p=L->link;while(p&&p->data<e){pre=p;p=p->link;}s=(LinkList)malloc(sizeof(Lnode));s->data=e;s->link=p;pre->link=s;}L头结点0a1a2^an^……

第9页:单链表就地逆置示例

作业1线性表2. (4) ReverseList():单链表就地逆置;La1a2头结点a4^a3La4a3头结点a1^a2q

第10页:单链表就地逆置算法

作业1线性表2. (4) ReverseList():单链表就地逆置;

void nizhi(LinkList &L){LinkListp=L->link,q=L->link->link,u;p->link=NULL;while(q){u=q->link;q->link=L->link;L->link=q;q=u;}}La1^a2头结点a4^a3q将以q为头指针的链表中结点依次插入为L的后继pu

第11页:删除指定区间元素算法

作业1线性表2. (5)DelList():在有序单链表中删除所有值大于mink且小于maxk的元素。

void DelList(LinkList &L, ElemTypemink, ElemTypemaxk){LinkList p=L,q;while(p->link&&p->link->data<mink)p=p->link;q=p;while(q&&q->data<maxk)q=q->link;p->link=q;}L1020头结点40^30删除15-35间的元素ppp——第一个删除元素的前驱qqqqq——最后一个删除元素的后继

第12页:作业一主程序菜单

作业1线性表main(){

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");printf("9.就地逆置");printf("a.有序表插入");printf("q.退出\n");printf("\n请选择操作:");fflush(stdin);scanf("%c",&choice);

第13页:作业一主程序分支

作业1线性表switch(choice){case '1':

printf("请输入单链表中结点个数:");scanf("%d",&n); Create_L(L,n);break;case '2': printf("请输入元素位序:");scanf("%d",&i); GetElem_L(L,i,e);printf("元素值为:%d\n",e);break;case '3': printf("请输入要查找的元素:");scanf("%d",&e);if(dlbcz(L,e)) printf("查找成功!");elseprintf("查找失败。");break;……}}//end of while(choice!='q')}//end of main()

第14页:作业二栈与队列题目

作业2栈、队列、数组1.若进栈序列为ABCD,请写出全部可能的出栈序列和不可能的出栈序列。 可能的出栈序列:(14种)dcba cdba bacd cbda adcb cbad bdcaacdb bcda acbd bcad abdc badc abcd 不可能的出栈序列:(10种)dbca dbac dabc dacb dcab cabd cdabbdac cadb adbc2.简要说明循环队列如何判断队满和队空?当牺牲一个存储结点时(以“队列头指针在队列尾指针的下一位置”作为队列“满”状态的标志) 队满的条件:(rear+1) % MaxQsize==front; 判断队空的条件为:front == rear。

第15页:对称矩阵压缩存储题目

作业2栈、队列、数组3.设A为n阶对称矩阵,采用压缩存储存放于一维数组F[n(n+1)/2]中(从F[0]开始存放),请分别给出存放上三角阵时任一矩阵元素aij(1≤i,j≤n)的地址计算公式和存放下三角阵时任一矩阵元素aij(1≤i,j≤n)的地址计算公式。 存放上三角阵时,任一矩阵元素aij(1≤i,j≤n)的地址计算公式为: 存放下三角阵时,任一矩阵元素aij(1≤i,j≤n)的地址计算公式为:

第16页:稀疏矩阵与后缀表达式题目

作业2栈、队列、数组4.写出下面稀疏矩阵的三元组顺序表和十字链表表示。5.栈采用顺序栈存储,试设计算法实现将表达式转换成后缀表达式输出。(略)

第17页:三结点树与二叉树形态

作业3树1.请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 树 二叉树

第18页:由遍历序列构造二叉树

作业3树2.已知二叉树的先序遍历序列是EABDCFHGIKJ,中序遍历序列是ABCDEFGHIJK,请构造二叉树,并写出其层次遍历序列和后序遍历序列。先序左子树右子树根中序左子树右子树根先序E A B D C F H G I K J中序A B C D E F G H I J KEAAABBBDDDCFFFHHGHIIIKKJ层次序列为:后序序列为:EAFBHIGDCJKCDBAGJKIHFE

第19页:森林转换为二叉树

作业3树3.将下图所示的森林转换成一棵二叉树。ABCDKLEFGHIJABCDEFGHIJKLABCDEFGHIJKL

第20页:二叉树还原为树或森林

作业3树3.将下图所示的二叉树还原成树或森林。ABCDEFGHIKLMNJABCDEFGHIKLMNJABCDLMNEFGHIJK

第21页:哈夫曼编码设计

作业3树3.假设用于通信的电文由7个字母组成{A,B,C,D,E,F,G},字母在电文中出现的频率分别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。试为这7个字母设计哈夫曼编码,并计算其带权路径长度WPL。0.17A0.09B0.12C0.06D0.32E0.03F0.21G0.090.180.290.390.611.00010000011111A :B :C :D :E :F :G :101001100000111000001WPL=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56

第22页:二叉树算法设计题目

作业3树4.二叉树采用二叉链表存储,试设计算法实现:(1) CreateBT(BiTree &T):从键盘输入二叉树的先序遍历序列字符串(以”#”代表空结点),建立其二叉链表;如输入:AB#D##CE#F###(2) ExchangeBT(BiTree T):设计递归算法实现二叉树中所有结点的左右孩子交换;(3) CountLeaf(BiTree T, T

ElemType x, int &count):统计以值为x的结点为根的子树中叶子结点的数目;(4) DispBiTree(BiTree T, int level) :按树状打印二叉树ABDCEF打印得到:#C###F##EA##D#B

第23页:建立二叉链表算法

作业3树4.二叉树采用二叉链表存储,试设计算法实现:(1) CreateBT(BiTree &T):从键盘输入二叉树的先序遍历序列字符串(以”#”代表空结点),建立其二叉链表;

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);}}

第24页:交换左右孩子算法

作业3树(2) ExchangeBT(BiTree T):设计递归算法实现二叉树中所有结点的左右孩子交换;

void ExchangeBT(BiTreeT){BiTree temp;if(T){temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;ExchangeBT(T->lchild);ExchangeBT(T->rchild);}}

第25页:查找指定值结点算法

作业3树(3) CountLeaf(BiTree T, T

ElemType x, int &count):统计以值为x的结点为根的子树中叶子结点的数目;//查找值为x的结点BiTree SearchTree(BiTreeT,charx){ BiTree bt;if(T){if(T->data==x)return T;bt=SearchTree(T->lchild,x);if(bt==NULL)bt=SearchTree(T->rchild,x);return bt;}return NULL;}

第26页:统计叶子结点算法

作业3树(3) CountLeaf(BiTree T, T

ElemType x, int &count):统计以值为x的结点为根的子树中叶子结点的数目;//统计根为T的子树的叶子结点个数int LeafCount (BiTreeT){static int count;if ( T ){if ((T->lchild==NULL)&& (T->rchild==NULL))count++;else{count=LeafCount1( T->lchild);count=LeafCount1( T->rchild);}}return count;}

第27页:按树状打印二叉树

作业3树(4) DispBiTree(BiTree T, int level) :按树状打印二叉树

void DispBiTree(BiTreeT,intlevel){ int i;if(T){DispBiTree(T->rchild, level + 1);for(i = 0; i < level;i++) printf("#");printf("%c\n",T->data);DispBiTree(T->lchild, level + 1);}}ABDCEF打印:#C###F##EA##D#B对于根为T,层次为level的子树:①打印其下一层(level+1层)右子树;②打印level个#后,打印根结点;③打印其下一层(level+1层)左子树;*结点左边的’#’个数为其层次数*

第28页:作业三主程序

作业3树main(){BiTree T,SubT; char Subch;int countl=0;

printf("输入先序序列建立二叉树:\n");CreateBT(T);printf("\n二叉树为:\n");DispBiTree(T,0);printf("交换结点的左右孩子\n");ExchangeBT(T);printf("\n此时二叉树为:\n");DispBiTree(T,0);printf("输入要统计叶子结点个数的子树的根:");fflush(stdin);scanf("%c",&Subch);SubT=SearchTree(T,Subch);countl=LeafCount1(SubT);printf("叶子结点数为:%d\n",countl);}

第29页:作业四图题目一

作业4图1.已知带权有向图,画出该图的邻接矩阵存储结构。2afbdgche69783251302421

第30页:作业四图题目二

作业4图2.无向图邻接表存储结构如图所示:(1)画出该无向图;(2)写出在该邻接表上,从顶点1出发所得到的深度优先遍历(DFS)和广度优先遍历(BFS)序列。

第31页:由邻接表还原无向图

作业4图(1)画出该无向图;13247586

第32页:深度优先遍历序列

作业4图(2)写出在该邻接表上,从顶点1出发所得到的深度优先遍历(DFS)和广度优先遍历(BFS)序列。深度遍历:134786520 0 0 0 0 0 0 0visited[M]1 2 3 4 5 6 7 811111111结束

第33页:广度优先遍历序列

作业4图(2)写出在该邻接表上,从顶点1出发所得到的深度优先遍历(DFS)和广度优先遍历(BFS)序列。广度遍历:132476580 0 0 0 0 0 0 0visited[M]1 2 3 4 5 6 7 811111111结束

第34页:折半查找判定树题目

作业5查找、排序1.对下标为1~9的有序表进行折半查找,画出折半查找的判定树;并计算在等概率情况下查找成功的平均查找长度ASL。1 2 3 4 5 6 7 8 95 13 19 21 37 56 64 75 80527136849ASL=(1+2*2+3*4+4*2)/9=25/9

第35页:线性探查散列表

作业5查找、排序2.设有关键字序列{25,40,33,47,12,66,72,87,94,22,5,58},散列表长12,散列函数为h(key)=key%11,用线性探查再散列、链地址法处理冲突,请分别画出散列表,并计算。3661010730035用线性探查再散列法处理冲突72402547873312669422558113126113591ASL=(1*6+2*1+3*2+5*1+6*1+9*1)/12=2.83

第36页:链地址法散列表

作业5查找、排序2.设有关键字序列{25,40,33,47,12,66,72,87,94,22,5,58},散列表长12,散列函数为h(key)=key%11,用线性探查再散列、链地址法处理冲突,请分别画出散列表,并计算。3661010730035用链地址法处理冲突2540330123456789101147126672879422558^^^^^^^^^^^^ASL=(1*7+2*3+3*2)/12=1.58

第37页:第一趟排序结果一

作业5查找、排序3.已知待排序序列为{50,86,72,41,45,93,57,46},请写出按下列排序方法进行升序排序时的第一趟排序结果:

  • 直接插入排序;
  • 冒泡排序;
  • 简单选择排序;
  • 堆排序初建堆序列。直接插入排序初始第一趟0 1 2 3 4 5 6 7 850724145 93 57 46860 1 2 3 4 5 6 7 850j8672 41 45 93 57 46冒泡排序5072414586935746

第38页:第一趟排序结果二

简单选择排序72414586935746 作业5查找、排序3.已知待排序序列为{50,86,72,41,45,93,57,46},请写出按下列排序方法进行升序排序时的第一趟排序结果:

  • 直接插入排序;
  • 冒泡排序;
  • 简单选择排序;
  • 堆排序初建堆序列。50

第39页:第一趟排序结果三

作业5查找、排序3.已知待排序序列为{50,86,72,41,45,93,57,46},请写出按下列排序方法进行升序排序时的第一趟排序结果:

  • 直接插入排序;
  • 冒泡排序;
  • 简单选择排序;
  • 堆排序初建堆序列。堆排序初建堆利用大顶堆得到的是升序序列507286579345414646419372935072504.设计一种方法,以少于2n-3次的比较在顺序存储的n(n>=2)个数中同时找出最大和最小值。(略)
顶部目录