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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)第二章 線性表順序表的操作順序表的建立（從鍵盤或者數(shù)組中導(dǎo)入數(shù)據(jù)）Status InitList(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; return OK; 順序表按照值查找位置int LocateElem(SqLis

2、t L, ElemType e) /根據(jù)數(shù)據(jù)元素的值，返回它在線性表L中的位置 int i=0; while (i=L.length)&(*(L.elem+i-1)!=e) i+; if (i=L.length) return i; else return(-1); 順序表按照序號查找元素的值Status GetElem(SqList L,int i,ElemType &e) /根據(jù)數(shù)據(jù)元素在線性表L中的位置，返回它的值if(iL.length )return ERROR;e=*(L.elem+i-1);return OK; 順序表數(shù)據(jù)元素的插入Status ListInsert(SqList

3、 &L,int i,ElemType e) / 在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e，L的長度加1 ElemType *p,*q,*newbase; if(iL.length+1) return ERROR; 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); fo

4、r(p=&(L.elemL.length-1);p=q; -p) *(p+1)=*p; *q=e; +L.length ; return OK; 順序表數(shù)據(jù)元素的刪除Status ListDelete(SqList &L,int i,ElemType &e) /刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長度減1 ElemType *q,*p; if(iL.length) return ERROR; p=&(L.elemi-1); e=*p; q=L.elem+L.length-1; for(+p;p=q;+p) *(p-1)=*p; -L.length; return OK; 順序表數(shù)據(jù)元素

5、的輸出Status visit(SqList L) /按序輸出順序表的各個(gè)元素值 int i; for(i=1;i=L.length;i+) printf(%d ,*(L.elem+i-1); coutnext=NULL; printf(請輸入%d個(gè)數(shù)據(jù)n,n); for(i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode); scanf(%d,&p-data); p-next=L-next; L-next=p; void CreateList2(LinkList &L,int n) / 正位序輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表int i;LinkL

6、ist p,q;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;q=L; printf(請輸入%d個(gè)數(shù)據(jù)n,n);for(i=1;idata); q-next=p;q=q-next;p-next=NULL;單鏈表的輸出Status visit(LinkList L) /按序輸出單鏈表的各個(gè)元素值 LinkList p=L-next; while(p) printf(%d ,p-data); p=p-next; printf(n); return OK; 單鏈表結(jié)點(diǎn)的插入Status ListInsert(LinkList &L,int i,ElemTy

7、pe e)LinkList p,s;p=L;int j=0;while(p&jnext; +j;if(!p|ji-1)return ERROR;s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;return OK;單鏈表結(jié)點(diǎn)的刪除Status ListDelete(LinkList&L,int i,ElemType e)LinkList p,q;p=L;int j=0;while(p-next&jnext; +j;if(!(p-next)|ji-1)return ERROR;q=p-next;p-next=q-ne

8、xt;e=q-data;free(q);return OK;單鏈表中按照結(jié)點(diǎn)的值查找結(jié)點(diǎn)的位序int LocateElem(LinkList L,ElemType e) / 返回L中第1個(gè)值為e 的數(shù)據(jù)元素的位序，若這樣的數(shù)據(jù)元素不存在,則返回值為0 int i=0;LinkList p=L-next;while(p) i+; if(p-data=e) return i; p=p-next;return 0; 單鏈表中按照結(jié)點(diǎn)的位序返回結(jié)點(diǎn)的值Status GetElem(LinkList L,int i,ElemType &e) / L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)?shù)趇個(gè)元素存在時(shí),其值賦給

9、e并返回OK,否則返回 ERROR int j=1; LinkList p=L-next; while(p&jnext; j+; if(!p|ji) return ERROR; e=p-data; return OK; 單鏈表的初始化（新建一個(gè)只含頭結(jié)點(diǎn)的單鏈表） Status InitList(LinkList &L) / 構(gòu)造一個(gè)空的單鏈表L L=(LinkList)malloc(sizeof(LNode); if (!L) exit(OVERFLOW); L-next=NULL; return OK; 單鏈表的銷毀（所有結(jié)點(diǎn)都要銷毀）Status DestroyList(LinkList

10、 &L) / 銷毀單鏈表L LinkList q;while(L)q=L-next;free(L);L=q;return OK; 求單鏈表的長度int ListLength(LinkList L) / 返回L中數(shù)據(jù)元素個(gè)數(shù) if(L=0) return 0;int i=0;LinkList p=L-next; while(p) i+;p=p-next; return i;10、兩個(gè)單鏈表的歸并void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc) /已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列 /歸并La和Lb得到新的線性表Lc,Lc

11、的數(shù)據(jù)元素也按值非遞減排列 LinkList pa,pb,pc;pa=La-next;pb=Lb-next; Lc=pc=La; while(pa&pb) if(pa-datadata) pc-next=pa; pc=pa; pa=pa-next; elsepc-next=pb; pc=pb; pb=pb-next; pc-next=pa?pa:pb; free(Lb);第三章 棧和隊(duì)列棧的操作初始化一個(gè)順序棧（從鍵盤或者數(shù)組中導(dǎo)入數(shù)據(jù)）Status InitStack(SqStack &S) S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(S

12、ElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;判斷棧是否為空Status StackEmpty(SqStack S) / 若棧S為空棧，則返回TRUE；否則返回FALSE if(S.top=S.base)return TRUE; else return FALSE;取棧頂元素Status GetTop(SqStack S,SElemType &e) / 在教科書第47頁 / 若棧S不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR if(S.top=S.ba

13、se)return ERROR; e=*(S.top-1); return OK;元素進(jìn)棧Status Push(SqStack &S,SElemType e) / 插入元素e為棧S新的棧頂元素。 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.to

14、p+=e; return OK;元素出棧Status Pop(SqStack &S,SElemType &e) / 在教科書第47頁 / 若棧S不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR if(S.top=S.base)return ERROR; e=*-S.top; return OK;計(jì)算棧中數(shù)據(jù)元素的個(gè)數(shù)int StackLength(SqStack S) / 返回棧S的元素個(gè)數(shù)，即棧的長度 return S.top-S.base;遞歸遞歸實(shí)現(xiàn)階乘int f(int n) if(n=0) return 1; else return (n*f(n-1);遞歸實(shí)現(xiàn)

15、鏈表的輸出（正序、逆序）void RevPrint(LNode *head)if(NULL!=head)if(NULL!=head-next)RevPrint(head-next);printf(%dt,head-data); /逆序后輸出void PrintList_L(LinkList L)if(L!=NULL)printf(%dt,L-data);PrintList_L(L-next); /正序輸出遞歸實(shí)現(xiàn)鏈表的逆序LinkList reverse(LinkList p) LinkList q,h; if(p-next=NULL) return p; else q=p-next; h=r

16、everse(q); q-next=p; p-next=NULL; return h; 遞歸求鏈表的長度int ListLength(LinkList L) int len; if(!L) return 0; len=1+ListLength(L-next); return len;第六章 樹和二叉樹二叉樹的操作（采用二叉鏈?zhǔn)酱鎯Γ┒鏄涞慕tatus CreateBiTree(BiTree &T) / 算法6.4：按先序次序輸入二叉樹中結(jié)點(diǎn)的值(可為字符型或整型，在主程中定義)， char ch; scanf(%c,&ch); if(ch= ) T=NULL; else if(!(T=(

17、BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data=ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); return OK;二叉樹的遍歷（四種）Status PreOrderTraverse(BiTree T,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-l

18、child,Visit)if(PreOrderTraverse(T-rchild,Visit) return OK;else return OK;Status InOrderTraverse(BiTree T,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) return OK;else retu

19、rn OK;Status PostOrderTraverse(BiTree T,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); return OK;else return OK;Status LevelOrderTraverse(BiTree T,void(*Visit)(TElem

20、Type) / 初始條件：二叉樹T存在，Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)/ 操作結(jié)果：層序遞歸遍歷T(利用隊(duì)列)，對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次 LinkQueue q;QElemType a;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); return OK;求二叉樹高度int TreeDep

21、th(BiTree T)int depth,depthleft,depthright;if(!T) depth=0;elsedepthleft=TreeDepth(T-lchild);depthright=TreeDepth(T-rchild);depth=1+(depthleftdepthright?depthleft:depthright);return depth;交換二叉樹的左右子樹Status exchange(BiTree T) /先序遍歷 if(T!=NULL) if(T-lchild!=NULL|T-rchild!=NULL) BiTree *p,*q; p = exchang

22、e(T-lchild); q = exchange(T-rchild); T-lchild = q; T-rchild = p; return T; void exchanget(BiTree T) / 后序遍歷 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); return T;求二叉樹的結(jié)點(diǎn)個(gè)數(shù)Status NodeNum(BiTr

23、ee T,int *num) if (T) if(T-data) num+; if (NodeNum(T-lchild,num) if(NodeNum(T-rchild,num) return OK; return ERROR; else return OK; 求二叉樹的葉子數(shù)void CountLeaf(BiTree T,int &count) if(T)if(T-lchild=NULL&T-rchild=NULL)count+; else CountLeaf(T-lchild, count);CountLeaf(T-rchild,count); 按照目錄形式輸出二叉樹 Status Pri

24、ntTree(BiTree bt,int nLayer) /* 按豎向樹狀打印的二叉樹 */ if(bt!=NULL) PrintTree(bt-lchild,nLayer+1); for(int i=0;idata); PrintTree(bt-rchild,nLayer+1); return OK;樹的操作（采用左孩子右兄弟存儲結(jié)構(gòu)）求樹的深度int TreeDepth(CSTree T) / 初始條件：樹T存在。操作結(jié)果：返回T的深度 int maxd,d; CSTree p; if(!T) return 0; else for(maxd=0,p=T-firstchild;p;p=p-nextsibling) if(d=TreeDepth(p)maxd) maxd=d; return maxd+1; 求樹中給定結(jié)點(diǎn)的右兄弟TElemType RightSibling(CSTree T,TElemType cur_e) / 初始