數(shù)據(jù)結(jié)構(gòu)作業(yè)答案(大連理工大學(xué))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)作業(yè)答案(大連理工大學(xué))專心-專注-專業(yè)作業(yè)1. 線性表l 編程作業(yè)：1 將順序表逆置，要求用最少的附加空間。參考答案#include <stdio.h>#include <malloc.h>#include <process.h>#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 -2t

2、ypedef int Status;typedef int ElemType;typedef struct ElemType *elem; int length; int listsize; SqList;/創(chuàng)建空順序表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;/順序表在第i個元素

3、之前插入eStatus sxbcr(SqList &L, int i, ElemType e) ElemType *p,*q;if(i<1) | (i>L.length+1) return (ERROR); else q=&(L.elemi-1); for(p=&(L.elemL.length-1);p>=q;-p) *(p+1)=*p; *q=e; +L.length; return (OK); /順序表顯示void xsList(SqList L)int i=L.length,k;for(k=0;k<i;k+)printf("%d

4、",L.elemk);printf("n");/順序表逆置void nizhi(SqList &L)int i=0,j=L.length-1; ElemType temp;for(;i<j;i+,j-)temp=L.elemi;L.elemi=L.elemj;L.elemj=temp;main()SqList L;char flag1='y',flag2='n'int i;ElemType k;if(InitList_Sq(L)printf("建立空順序表成功！n");doprintf("

5、當(dāng)前線性表長度為：%dn",L.length);printf("請輸入要插入元素的位置：");scanf("%d",&i);printf("請輸入要插入的元素值：");scanf("%d",&k);if(sxbcr(L,i,k)printf("插入成功，插入后順序表長度為：%dn",L.length);printf("插入后的順序表為：");xsList(L);elseprintf("插入失敗");printf("n繼續(xù)

6、插入元素？(y/n) ");fflush(stdin);scanf("%c",&flag1);while(flag1='y'); nizhi(L); printf("順序表逆置后為：n"); xsList(L);2 從鍵盤讀入n個整數(shù)（升序），請編寫算法實現(xiàn)：（1） CreateList()：建立帶表頭結(jié)點的單鏈表；（2） PrintList()：顯示單鏈表，（形如：H->10->20->30->40）;（3） InsertList()：在有序單鏈表中插入元素x；（4） ReverseList()

7、：單鏈表就地逆置；（5） DelList()：在有序單鏈表中刪除所有值大于mink且小于maxk的元素。選作：使用文本菜單完成功能選擇及執(zhí)行。參考答案：#include<stdio.h>#include<malloc.h>#include<process.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct n

8、ode ElemType data; struct node *link;Lnode, *LinkList;/頭插法建立單鏈表void Create_L1(LinkList &L, int n) LinkList p; int i; L=(LinkList)malloc(sizeof(Lnode); L->link = NULL; for (i = n; i > 0; -i) p=(LinkList)malloc(sizeof(Lnode); scanf("%d",&p->data); p-> link = L-> link;

9、L-> link = p; /尾插法建立單鏈表void Create_L2(LinkList &L,int n) LinkList s, p; int i; L=(LinkList)malloc(sizeof(Lnode); L->data=0; L->link=NULL; p=L; for(i=1;i<=n;i+) s=(LinkList)malloc(sizeof(Lnode); scanf("%d",&s->data);s->link=NULL;p->link=s;p=s; /查找是否存在結(jié)點eLinkList

10、 dlbcz(LinkList L, ElemType e) LinkList p=L->link; while(p!=NULL && p->data!=e) p=p->link; return (p);/在第i個元素之前插入結(jié)點eStatus ListInsert_L(LinkList L, int i, ElemType e) LinkList p = L,s; int j = 0; while (p && j < i-1) p = p->link;+j; if (!p | j > i-1) return ERROR; s

11、 = (LinkList) malloc ( sizeof (Lnode); s->data = e; s->link = p->link; p->link = s; return OK;/刪除第i個結(jié)點Status ListDelete_L(LinkList L, int i, ElemType &e) LinkList p = L,q; int j = 0; while (p->link && j < i-1) p = p->link; +j; if (!(p->link) | j > i-1) return E

12、RROR; q=p->link; p->link=q->link; e=q->data; free(q); return OK;/求第i個元素值Status GetElem_L(LinkList L, int i, ElemType &e) int j=1; LinkList p=L->link; while(p&&j<i) p=p->link; j+; if(!p|j>i) return ERROR; e=p->data; return OK;/顯示單鏈表中元素void xsList(LinkList L)Link

13、List p=L->link;while(p)printf("%d ",p->data);p=p->link;/刪除大于mink且小于maxk的元素void DelList(LinkList &L, ElemType mink, ElemType maxk)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;

14、/就地升序排序void sh_sort(LinkList &L)LinkList p=L->link,pre=L,q=L->link->link,u;p->link=NULL;while(q)p=L->link;pre=L;while(p&&p->data<q->data)pre=p;p=p->link;u=q->link;pre->link=q;q->link=p;q=u;/就地逆置void nizhi(LinkList &L)LinkList p=L->link,q=L->l

15、ink->link,u;p->link=NULL;while(q)u=q->link;q->link=L->link;L->link=q;q=u;/有序表插入void yxcharu(LinkList &L, ElemType e)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;

16、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.刪除大

17、于mink且小于maxk的元素值 ");printf("8.就地升序排序n");printf("9.就地逆置 ");printf("a.有序表插入 ");printf("q.退出n");printf("n請選擇操作：");fflush(stdin);scanf("%c",&choice);switch(choice)case '1': printf("請輸入單鏈表中結(jié)點個數(shù)："); scanf("%d"

18、,&n); Create_L2(L,n); break;case '2': printf("請輸入元素位序："); scanf("%d",&i); GetElem_L(L,i,e); printf("元素值為：%dn",e); break;case '3': printf("請輸入要查找的元素："); scanf("%d",&e); if(dlbcz(L,e) printf("查找成功！"); else printf(&

19、quot;查找失敗。"); break;case '4': printf("請輸入插入位置："); scanf("%d",&i); printf("請輸入要插入的元素："); scanf("%d",&e); if(ListInsert_L(L,i,e) printf("插入成功！單鏈表為："); else printf("插入失敗。"); break;case '5': printf("請輸入刪除位置：&qu

20、ot;); scanf("%d",&i); 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",&mink,&maxk); DelList(L,min

21、k,maxk); break;case '8': sh_sort(L); break;case '9': nizhi(L); break;case 'a': printf("請輸入在有序表中插入的元素值:"); scanf("%d",&e); yxcharu(L,e); break;作業(yè)2. 棧、隊列、數(shù)組l 非編程作業(yè)：1 若進(jìn)棧序列為ABCD，請寫出全部可能的出棧序列和不可能的出棧序列。參考答案：可能的出棧序列：(14種) dcba cdba bacd cbda adcb cbad bdca a

22、cdb bcda acbd bcad abdc badc abcd 不可能的出棧序列：(10種)dbca dbac dabc dacb dcab cabd cdab bdac cadb adbc 2 簡要說明循環(huán)隊列如何判斷隊滿和隊空？參考答案：當(dāng)犧牲一個存儲結(jié)點，約定以“隊列頭指針在隊列尾指針的下一位置（指環(huán)狀的下一個位置）上” 作為隊列“滿”狀態(tài)的標(biāo)志時，循環(huán)隊列判斷隊滿的條件為：(rear+1) % MaxQsize=front；判斷隊空的條件為：front = rear。3 設(shè)A為n階對稱矩陣，采用壓縮存儲存放于一維數(shù)組Fn(n+1)/2中（從F0開始存放），請分別給出存放上三角陣時任

23、一矩陣元素aij（1i,jn）的地址計算公式和存放下三角陣時任一矩陣元素aij（1i,jn）的地址計算公式。參考答案：存放上三角陣時，任一矩陣元素aij（1i,jn）的地址計算公式為：存放下三角陣時，任一矩陣元素aij（1i,jn）的地址計算公式為：4 寫出下面稀疏矩陣的三元組順序表和十字鏈表表示。參考答案：l 編程作業(yè)棧采用順序棧存儲，試設(shè)計算法實現(xiàn)將表達(dá)式轉(zhuǎn)換成后綴表達(dá)式輸出。例如，輸入表達(dá)式： a+b/c-(d*e+f)*g 輸出其后綴表達(dá)式：abc/+de*f+g*- 參考答案：#include <stdio.h>#include <stdlib.h>#incl

24、ude <string.h>#define OVERFLOW -2#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int Status;typedef char SElemType; typedef char string80; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; Status InitStack(SqStack &S) S.base=(S

25、ElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType);if(!S.base) exit(OVERFLOW);S.top=S.base; S.stacksize=STACK_INIT_SIZE; return(OK);Status ClearStack(SqStack &S)S.base=(SElemType*)realloc(S.base,STACK_INIT_SIZE *sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT

26、_SIZE; return(OK);void DestroyStack(SqStack &S)S.stacksize=0;if(S.base)free(S.base);S.base=S.top=NULL;Status StackEmpty(SqStack S)if(S.top=S.base)return true;elsereturn false;SElemType GetTop(SqStack S) SElemType e;if(S.top>S.base) e=*(S.top-1); return e;Status Push(SqStack &S, SElemType

27、e) if(S.top-S.base>=S.stacksize) /棧滿 S.base=(SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) *sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+ S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;Status Pop(SqStack &S, SElemType &e) if(S.top = S.base) /?？誶

28、eturn ERROR; e =*-S.top; return OK;Status InOP(SElemType c)char Operators='+','-','*','/','(',')','#','0'int len=strlen(Operators);for(int i=0;i<len;i+)if(c=Operatorsi)return true;return false;SElemType Precede(SElemType curtop,SElem

29、Type input)SElemType order;switch(input)case '+':case '-':switch(curtop)case '+':case '-':case '*':case '/':case ')':order='>'break;case '(':case '#':order='<'break;break;case '*':case '/':s

30、witch(curtop)case '+':case '-':case '(':case '#':order='<'break;case '*':case '/':case ')':order='>'break;break;case '(':switch(curtop)case '+':order='<'break;case '-':order='<'

31、;break;case '*':order='<'break;case '/':order='<'break;case '(':order='<'break;case '#':order='<'break;break;case ')':switch(curtop)case '+':order='>'break;case '-':order='>'brea

32、k;case '*':order='>'break;case '/':order='>'break;case '(':order='='break;case ')':order='>'break;break;case '#':switch(curtop)case '+':order='>'break;case '-':order='>'break;case &

33、#39;*':order='>'break;case '/':order='>'break;case ')':order='>'break;case '#':order='='break;break;return order;void Pass( string Suffix, SElemType ch)*Suffix=ch;void Transform(string Infix, string Suffix ) SqStack S;SElemType ch,

34、e; int flag=0,len;InitStack(S); Push(S, '#');len=strlen(Infix);*(Infix+len)='#'ch = *Infix;while (!StackEmpty(S) if (!InOP(ch) Pass( Suffix+, ch);elseswitch(Precede(GetTop(S),ch)case '<':Push(S,ch);flag=0;break;case '=':Pop(S,e);flag=0;break;case '>':Pop

35、(S,e);Pass( Suffix+, e);flag=1;break;if(!flag)if (ch!='#') ch = *+Infix; Pass(Suffix, '0');DestroyStack(S); void main()string Infix,Suffix;gets(Infix);Transform(Infix, Suffix) ;puts(Suffix);作業(yè)3. 樹l 非編程作業(yè)：1 請分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。參考答案：具有3個結(jié)點的樹： 具有3個結(jié)點的二叉樹： 2 已知二叉樹的先序遍歷序列是EABDCF

36、HGIKJ，中序遍歷序列是ABCDEFGHIJK，請構(gòu)造二叉樹，并寫出其層次遍歷序列和后序遍歷序列。參考答案：EACBDIJHFGK 層次：E A F B H D G I C K J 后序-C D B A G J K I H F E3 將下圖所示的森林轉(zhuǎn)換成一棵二叉樹。參考答案：BACDFGEHIJKL轉(zhuǎn)換成的二叉樹為：4 將下圖所示的二叉樹還原成樹或森林。參考答案：轉(zhuǎn)換為森林：ACHBFDMEGNJIKL5 假設(shè)用于通信的電文由7個字母組成A,B,C,D,E,F,G，字母在電文中出現(xiàn)的頻率分別為0.17、0.09、0.12、0.06、0.32、0.03、0.21。試為這7個字母設(shè)計哈夫曼編碼

37、，并計算其帶權(quán)路徑長度WPL。參考答案： 10.390.610.180.210.090.090.290.320.120.170.030.06AEGBDF哈夫曼樹為：WPL=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56A:101 B:001 C:100 D:0001 E:11 F:0000 G:01l 編程作業(yè)：二叉樹采用二叉鏈表存儲，試設(shè)計算法實現(xiàn)：1 CreateBT(BiTree &T)：從鍵盤輸入二叉樹的先序遍歷序列字符串（以”#”代表空結(jié)點），建立其二叉鏈表；如輸入：AB#D#CE#F# 則建立如下圖所示二叉樹的二叉鏈表

38、2 ExchangeBT(BiTree T): 設(shè)計遞歸算法實現(xiàn)二叉樹中所有結(jié)點的左右孩子交換；3 CountLeaf(BiTree T, TElemType x, int &count): 統(tǒng)計以值為x的結(jié)點為根的子樹中葉子結(jié)點的數(shù)目；4 DispBiTree(BiTree T, int level) : 按樹狀打印二叉樹。BCFAED 打印得到：#C#F#EA#D#B提示：對于根為T，層次為level的子樹： 打印其下一層(level+1層)右子樹； 打印根結(jié)點； 打印其下一層(level+1層)左子樹； *結(jié)點左邊的#個數(shù)為其層次數(shù)*參考答案：#include <stdio

39、.h>#include <malloc.h>typedef struct BiTNodechardata;struct BiTNode *lchild,*rchild;BiTNode, *BiTree;/輸入先序序列，創(chuàng)建二叉樹的二叉鏈表void CreateBT(BiTree &T)char ch; scanf("%c",&ch); if (ch = '#') T = NULL; elseT = (BiTNode *)malloc(sizeof(BiTNode); T->data = ch; CreateBT(T-&

40、gt;lchild); CreateBT(T->rchild);/交換二叉樹中結(jié)點的左右孩子void ExchangeBT(BiTree T) BiTree temp; if(T)temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; ExchangeBT(T->lchild); ExchangeBT(T->rchild);/先序遍歷二叉樹void PreOrderTraverse(BiTree T) if(T) printf("%c ", T->data); PreOrder

41、Traverse(T->lchild); PreOrderTraverse(T->rchild); /查找值為x的結(jié)點BiTree SearchTree(BiTree T,char X) 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;/統(tǒng)計以T為根的子樹中葉子結(jié)點數(shù)int LeafCount1 (BiTree T) static int count;if

42、( T ) if (T->lchild=NULL)&& (T->rchild=NULL) count+; else count=LeafCount1( T->lchild); count=LeafCount1( T->rchild); return count; void LeafCount2 (BiTree T, int &count) if ( T ) if (T->lchild=NULL)&& (T->rchild=NULL) count+; LeafCount2( T->lchild, count); LeafCount2( T->rchild, count); /按樹狀打印輸出二叉樹的元素,level表示結(jié)點的層次void DispBiTree(BiTree T,int level)int i; if(T) DispBiTree(T->rchild, level + 1); for(i = 0; i < level;i+) printf("#"); printf("%cn",T->data);