南審數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)個(gè)人任務(wù)題目一覽2015版

1、第二章線性表順序表的操作1、順序表的建立(從鍵盤或者數(shù)組中導(dǎo)入數(shù)據(jù))StatusInitList(SqList&L)/構(gòu)造一個(gè)空的順序表L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;2、順序表按照值查找位置intLocateElem(SqListL,ElemTypee)根據(jù)數(shù)據(jù)元素的值，返回它在線性表L中的位置inti=0;while(i<=L.length)&&

2、amp;(*(L.elem+i-1)!=e)i+;if(i<=L.length)returni;elsereturn(-1);3、順序表按照序號(hào)查找元素的值StatusGetElem(SqListL,inti,ElemType&e)根據(jù)數(shù)據(jù)元素在線性表L中的位置，返回它的值if(i<1|i>L.length)returnERROR;e=*(L.elem+i-1);returnOK;4、順序表數(shù)據(jù)元素的插入StatusListInsert(SqList&L,inti,ElemTypee)/在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e,L的長度加1ElemType*p,

3、*q,*newbase;if(i<1|i>L.length+1)returnERROR;if(L.length>=L.listsize)newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;)q=&(L.elemi-1);for(p=&(L.elemL.length-1);p>=q;-p)*(p+1)=*p;*q=e;+

4、L.length;returnOK;)5、順序表數(shù)據(jù)元素的刪除StatusListDelete(SqList&L,inti,ElemType&e)刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長度減1ElemType*q,*p;if(i<1|i>L.length)returnERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p<=q;+p)*(p-1)=*p;-L.length;returnOK;)6、順序表數(shù)據(jù)元素的輸出Statusvisit(SqListL)/按序輸出順序表的各個(gè)元素值inti;

5、for(i=1;i<=L.length;i+)printf("%d",*(L.elem+i-1);cout<<endl;printf("L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.length,L.listsize);returnOK;)單鏈表的操作1、單鏈表的建立voidCreateList(LinkList&L,intn)/逆位序輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表Linti;LinkListp;L=(LinkList)malloc(sizeof(LNode);L->

6、;next=NULL;printf("請輸入%d個(gè)數(shù)據(jù)n",n);for(i=n;i>0;-i)p=(LinkList)malloc(sizeof(LNode);scanf("%d",&p->data);p->next=L->next;L->next=p;voidCreateList2(LinkList&L,intn)/正位序輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表inti;LinkListp,q;L=(LinkList)malloc(sizeof(LNode);L->next=NULL;q=L;p

7、rintf("請輸入%d個(gè)數(shù)據(jù)n",n);for(i=1;i<=n;i+)p=(LinkList)malloc(sizeof(LNode);scanf("%d",&p->data);q->next=p;q=q->next;p->next=NULL;2、單鏈表的輸出Statusvisit(LinkListL)/按序輸出單鏈表的各個(gè)元素值LinkListp=L->next;while(p)printf("%d",p->data);p=p->next;printf("n&qu

8、ot;);returnOK;3、單鏈表結(jié)點(diǎn)的插入StatusListInsert(LinkList&L,inti,ElemTypee)LinkListp,s;p=L;intj=0;while(p&&j<i-1)p=p->next;+j;if(!p|j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode);s->data=e;s->next=p->next;p->next=s;returnOK;4、單鏈表結(jié)點(diǎn)的刪除StatusListDelete(LinkList&L,inti,

9、ElemTypee)LinkListp,q;p=L;intj=0;while(p->next&&j<i-1)p=p->next;+j;if(!(p->next)|j>i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;free(q);returnOK;5、單鏈表中按照結(jié)點(diǎn)的值查找結(jié)點(diǎn)的位序intLocateElem(LinkListL,ElemTypee)/返回L中第1個(gè)值為e的數(shù)據(jù)元素的位序，若這樣的數(shù)據(jù)元素不存在，則返回值為0inti=0;LinkListp=L->

10、;next;while(p)i+;if(p->data=e)returni;p=p->next;return0;6、單鏈表中按照結(jié)點(diǎn)的位序返回結(jié)點(diǎn)的值StatusGetElem(LinkListL,inti,ElemType&e)/L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK,否則返回ERRORintj=1;LinkListp=L->next;while(p&&j<i)p=p->next;j+;if(!p|j>i)returnERROR;e=p->data;returnOK;7、單鏈表的初始化(新建一個(gè)

11、只含頭結(jié)點(diǎn)的單鏈表)StatusInitList(LinkList&L)/構(gòu)造一個(gè)空的單鏈表LL=(LinkList)malloc(sizeof(LNode);if(!L)exit(OVERFLOW);L->next=NULL;returnOK;8、單鏈表的銷毀(所有結(jié)點(diǎn)都要銷毀)StatusDestroyList(LinkList&L)/銷毀單鏈表LLinkListq;while(L)q=L->next;free(L);L=q;returnOK;9、求單鏈表的長度intListLength(LinkListL)/返回L中數(shù)據(jù)元素個(gè)數(shù)if(L=0)return0;i

12、nti=0;LinkListp=L->next;while(p)i+;p=p->next;returni;10、兩個(gè)單鏈表的歸并voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc)/已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列歸并La和Lb得到新的線性表Lc,Lc的數(shù)據(jù)元素也按值非遞減排列LinkListpa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb)(if(pa->data<=pb->data)pc-

13、>next=pa;pc=pa;pa=pa->next;elsepc->next=pb;pc=pb;pb=pb->next;pc->next=pa?pa:pb;free(Lb);第三章棧和隊(duì)列棧的操作1、初始化一個(gè)順序棧(從鍵盤或者數(shù)組中導(dǎo)入數(shù)據(jù))StatusInitStack(SqStack&S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;retur

14、nOK;2、判斷棧是否為空StatusStackEmpty(SqStackS)/若棧S為空棧，則返回TRUE否則返回FALSEif(S.top=S.base)returnTRUE;elsereturnFALSE;3、取棧頂元素StatusGetTop(SqStackS,SElemType&e)/在教科書第47頁/若棧S不空，則用e返回S的棧頂元素，并返回OK否則返回ERRORif(S.top=S.base)returnERROR;e=*(S.top-1);returnOK;4、元素進(jìn)棧StatusPush(SqStack&S,SElemTypee)/插入元素e為棧S新的棧頂元素

15、。if(S.top-S.base>=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACK_INCREMENT;*S.top+=e;returnOK;5、元素出棧StatusPop(SqStack&S,SElemType&e)/在教科書第47頁/若棧S不空，則刪除S的棧頂元素，用e返回其值，并返回OK否則

16、返回ERRORif(S.top=S.base)returnERROR;e=*-S.top;returnOK;6、計(jì)算棧中數(shù)據(jù)元素的個(gè)數(shù)intStackLength(SqStackS)/返回棧S的元素個(gè)數(shù)，即棧的長度returnS.top-S.base;遞歸1、遞歸實(shí)現(xiàn)階乘intf(intn)if(n=0)return1;elsereturn(n*f(n-1);2、遞歸實(shí)現(xiàn)鏈表的輸出(正序、逆序)voidRevPrint(LNode*head)if(NULL!=head)if(NULL!=head->next)RevPrint(head->next);printf("%dt

17、",head->data);/逆序后輸出voidPrintList_L(LinkListL)if(L!=NULL)(printf("%dt",L->data);PrintList_L(L->next);)正序輸出3、遞歸實(shí)現(xiàn)鏈表的逆序LinkListreverse(LinkListp)(LinkListq,h;if(p->next=NULL)returnp;else(q=p->next;h=reverse(q);q->next=p;p->next=NULL;returnh;)4、遞歸求鏈表的長度intListLength(

18、LinkListL)intlen;if(!L)return0;len=1+ListLength(L->next);returnlen;)第六章樹和二叉樹二叉樹的操作(采用二叉鏈?zhǔn)酱鎯?chǔ))1、二叉樹的建立StatusCreateBiTree(BiTree&T)/算法6.4:按先序次序輸入二叉樹中結(jié)點(diǎn)的值(可為字符型或整型，在主程中定義),charch;scanf("%c",&ch);if(ch='')T=NULL;elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T->

19、data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);returnOK;)2、二叉樹的遍歷(四種)StatusPreOrderTraverse(BiTreeT,void(*Visit)(TElemType)/初始條件：二叉樹T存在，Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)。修改算法6.1/操作結(jié)果：先序遞歸遍歷T,對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次if(T)Visit(T->data);if(PreOrderTraverse(T->lchild,Visit)if(PreOrderTraverse(T->rch

20、ild,Visit)returnOK;)elsereturnOK;)StatusInOrderTraverse(BiTreeT,void(*Visit)(TElemType)/初始條件：二叉樹T存在，Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)/操作結(jié)果：中序遞歸遍歷T,對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次if(T)InOrderTraverse(T->lchild,Visit);Visit(T->data);if(InOrderTraverse(T->rchild,Visit)returnOK;)elsereturnOK;)StatusPostOrderTraverse(BiTre

21、eT,void(*Visit)(TElemType)/初始條件：二叉樹T存在，Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)/操作結(jié)果：后序遞歸遍歷T,對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次if(T)PostOrderTraverse(T->lchild,Visit);if(PostOrderTraverse(T->rchild,Visit)Visit(T->data);returnOK;)elsereturnOK;)StatusLevelOrderTraverse(BiTreeT,void(*Visit)(TElemType)/初始條件：二叉樹T存在，Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)一

22、次且僅一次/操作結(jié)果：層序遞歸遍歷T(利用隊(duì)列)，對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)VisitLinkQueueq;QElemTypea;if(T)InitQueue(q);EnQueue(q,T);while(!QueueEmpty(q)DeQueue(q,a);Visit(a->data);if(a->lchild!=NULL)EnQueue(q,a->lchild);if(a->rchild!=NULL)EnQueue(q,a->rchild);printf("n");returnOK;3、求二叉樹高度intTreeDepth(BiTreeT)intde

23、pth,depthleft,depthright;if(!T)depth=0;elsedepthleft=TreeDepth(T->lchild);depthright=TreeDepth(T->rchild);depth=1+(depthleft>depthright?depthleft:depthright);returndepth;4、交換二叉樹的左右子樹Statusexchange(BiTreeT)先序遍歷if(T!=NULL)if(T->lchild!=NULL|T->rchild!=NULL)BiTree*p,*q;p=exchange(T->l

24、child);q=exchange(T->rchild);T->lchild=q;T->rchild=p;10returnT;)voidexchanget(BiTreeT)/后序遍歷(if(T!=NULL)if(T->lchild!=NULL|T->rchild!=NULL)(BiTree*p,*q;q=T->rchild;p=T->lchild;T->lchild=q;T->rchild=p;exchange(T->lchild);exchange(T->rchild);)returnT;)5、求二叉樹的結(jié)點(diǎn)個(gè)數(shù)StatusN

25、odeNum(BiTreeT,int*num)(if(T)(if(T->data)num+;if(NodeNum(T->lchild,num)if(NodeNum(T->rchild,num)returnOK;returnERROR;)elsereturnOK;)6、求二叉樹的葉子數(shù)voidCountLeaf(BiTreeT,int&count)(if(T)(if(T->lchild=NULL&&T->rchild=NULL)count+;else(CountLeaf(T->lchild,count);CountLeaf(T->

26、rchild,count);11)7、按照目錄形式輸出二叉樹StatusPrintTree(BiTreebt,intnLayer)/*按豎向樹狀打印的二叉樹*/(if(bt!=NULL)(PrintTree(bt->lchild,nLayer+1);for(inti=0;i<nLayer;i+)printf("-");printf("%cn",bt->data);PrintTree(bt->rchild,nLayer+1);)returnOK;)樹的操作(采用左孩子右兄弟存儲(chǔ)結(jié)構(gòu))1、求樹的深度intTreeDepth(CSTreeT)/初始條件：樹T存在。操作結(jié)果：返回T的深度intmaxd,d;CSTreep;if(!T)return0;elsefor(maxd=0,p=T->firstchild;p;p=p->nextsibling)if(d=TreeDepth(p)>maxd)maxd=d;returnmaxd+1;)2、求樹中給定結(jié)點(diǎn)的右兄弟