数据结构课件-作业详解

数据结构作业详解

作业1线性表1.将顺序表逆置，要求用最少的附加空间。(略)2.从键盘读入n个整数(升序)，请编写算法实现：

(1)CreateList()：建立带表头结点的单链表；

(2)PrintList()：显示单链表，(H->10->20->30->40);(3)InsertList()：在有序单链表中插入元素x；

(4)ReverseList()：单链表就地逆置；

(5)DelList()：在有序单链表中删除所有值大于mink且小于maxk的元素。

typedefintElemType;typedefstructnode{

ElemTypedata;

structnode*link;}Lnode,*LinkList;

作业1线性表2.(1)CreateList()：建立带表头结点的单链表；voidCreate_L(LinkList&L,intn){LinkListp;inti;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^

作业1线性表2.(1)CreateList()：建立带表头结点的单链表；voidCreate_L(LinkList&L,intn){LinkListp;inti;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

^

作业1线性表2.(1)CreateList()：建立带表头结点的单链表；voidCreate_L(LinkList&L,intn){LinkListp;inti;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-1

an

^

作业1线性表2.(1)CreateList()：建立带表头结点的单链表；voidCreate_L(LinkList&L,intn){LinkListp;inti;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头结点0a1

a2

^an

^……

作业1线性表2.(2)PrintList()：显示单链表，(H->10->20->30->40);voidxsList(LinkListL){ LinkListp=L->link; while(p) { printf("%d",p->data);

p=p->link; }}L头结点0a1

a2

^an

^……

作业1线性表2.(3)InsertList()：在有序单链表中插入元素x；voidyxcharu(LinkList&L,ElemTypee){ LinkListpre,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头结点0a1

a2

^an

^……

作业1线性表2.(4)ReverseList()：单链表就地逆置；La1a2头结点a4

^a3La4a3头结点a1

^a2q

作业1线性表2.(4)ReverseList()：单链表就地逆置；voidnizhi(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

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

voidDelList(LinkList&L,ElemTypemink,ElemTypemaxk){ LinkListp=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——最后一个删除元素的后继

作业1线性表main(){ LinkListL; intn,i,mink,maxk;

ElemTypee;charchoice='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);

作业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("查找成功！");else printf("查找失败。");break;……}}//endofwhile(choice!='q')}//endofmain()

作业2栈、队列、数组

1.若进栈序列为ABCD，请写出全部可能的出栈序列和不可能的出栈序列。

可能的出栈序列：(14种)dcbacdbabacdcbdaadcbcbadbdcaacdbbcdaacbdbcadabdcbadcabcd不可能的出栈序列：(10种)dbcadbacdabcdacbdcabcabdcdabbdaccadbadbc2.简要说明循环队列如何判断队满和队空？当牺牲一个存储结点时(以“队列头指针在队列尾指针的下一位置”作为队列“满”状态的标志)队满的条件：(rear+1)%MaxQsize==front；判断队空的条件为：front==rear。

作业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）的地址计算公式为：

作业2栈、队列、数组

4.写出下面稀疏矩阵的三元组顺序表和十字链表表示

。5.栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。(略)

作业3树

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

树二叉树

作业3树

2.已知二叉树的先序遍历序列是EABDCFHGIKJ，中序遍历序列是ABCDEFGHIJK，请构造二叉树，并写出其层次遍历序列和后序遍历序列。先序左子树右子树根中序左子树右子树根先序EABDCFHGIKJ中序ABCDEFGHIJKEAAABBBDDDCFFFHHGHIIIKKJ层次序列为：后序序列为：EAFBHIGDCJKCDBAGJKIHFE

作业3树

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

ABCDKLEFGHIJABCDEFGHIJKLABCDEFGHIJKL

作业3树

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

作业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

作业3树

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

如输入：AB#D##CE#F###(2)ExchangeBT(BiTreeT):设计递归算法实现二叉树中所有结点的左右孩子交换；(3)CountLeaf(BiTreeT,TElemTypex,int&count):统计以值为x的结点为根的子树中叶子结点的数目；(4)DispBiTree(BiTreeT,intlevel):按树状打印二叉树ABDCEF打印得到：#C###F##EA##D#B

作业3树

4.二叉树采用二叉链表存储，试设计算法实现:(1)CreateBT(BiTree&T)：从键盘输入二叉树的先序遍历序列字符串（以”#”代表空结点），建立其二叉链表;voidCreateBT(BiTree&T){charch;scanf("%c",&ch);

if(ch=='#')T=NULL;

else{ T=(BiTNode*)malloc(sizeof(BiTNode));T->data=ch;

CreateBT(T->lchild); CreateBT(T->rchild); }}

作业3树

(2)ExchangeBT(BiTreeT):设计递归算法实现二叉树中所有结点的左右孩子交换；voidExchangeBT(BiTreeT){ BiTreetemp;if(T){ temp=T->lchild; T->lchild=T->rchild; T->rchild=temp;

ExchangeBT(T->lchild); ExchangeBT(T->rchild); }}

作业3树

(3)CountLeaf(BiTreeT,TElemTypex,int&count):统计以值为x的结点为根的子树中叶子结点的数目；//查找值为x的结点BiTreeSearchTree(BiTreeT,charx){BiTreebt;if(T){ if(T->data==x) returnT;

bt=SearchTree(T->lchild,x);if(bt==NULL)

bt=SearchTree(T->rchild,x);

returnbt; }

returnNULL;}

作业3树

(3)CountLeaf(BiTreeT,TElemTypex,int&count):统计以值为x的结点为根的子树中叶子结点的数目；//统计根为T的子树的叶子结点个数intLeafCount(BiTreeT){staticintcount;if(T){if((T->lchild==NULL)&&(T->rchild==NULL))count++;else{count=LeafCount1(T->lchild);count=LeafCount1(T->rchild);

}}

returncount;}

作业3树

(4)DispBiTree(BiTreeT,intlevel):按树状打印二叉树voidDispBiTree(BiTreeT,intlevel){inti;

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层)左子树；

*结点左边的’#’个数为其层次数*

作业3树

main(){BiTreeT,SubT;charSubch;

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

作业4图

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

作业4图

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

作业4图

(1)画出该无向图；13247586

作业4图

(2)写出在该邻接表上，从顶点1出发所得到的深度优先遍历(DFS)和广度优先遍历(BFS)序列。

深度遍历：1347865200000000visited[M]1234567811111111结束

作业4图

(2)写出在该邻接表上，从顶点1出发所得到的深度优先遍历(DFS)和广度优先遍历(BFS)序列。

广度遍历：1324765800000000visited[M]1234567811111111结束

作业5

查找、排序

1.对下标为1～9的有序表进行折半查找，画出折半查找的判定树；并计算在等概率情况下查找成功的平均查找长度ASL。12345678951319213756647580527136849ASL=(1+2*2+3*4+4*2)/9=25/9

作业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

作业5

查找、排序

2.设有关键字序列{25，40，33，47，12，66，72，87，94，22