南审（数据构造课程教学设计）个人讲明任务题目一览(2021年度版).docx

《南审（数据构造课程教学设计）个人讲明任务题目一览(2021年度版).docx》由会员分享，可在线阅读，更多相关《南审（数据构造课程教学设计）个人讲明任务题目一览(2021年度版).docx（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、南审（数据构造课程教学设计）个人讲明任务题目一览(2021年度版)第二章线性表顺序表的操作1、顺序表的建立从键盘或者数组中导入数据StatusInitList(SqList&L)/构造一个空的顺序表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)/根据数据元素的值，返回它在线性表L中的位置inti=0

2、;while(iL.length)returnERROR;e=*(L.elem+i-1);returnOK;4、顺序表数据元素的插入StatusListInsert(SqList&L,inti,ElemTypee)/在L中第i个位置之前插入新的数据元素e，L的长度加1ElemType*p,*q,*newbase;if(iL.length+1)returnERROR;if(L.length=L.listsize)newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exi

3、t(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;+L.length;returnOK;5、顺序表数据元素的删除StatusListDelete(SqList&L,inti,ElemType&e)/删除L的第i个数据元素，并用e返回其值，L的长度减1ElemType*q,*p;if(iL.length)returnERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+

4、p;pnext=NULL;printf(请输入%d个数据n,n);for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(%d,&p-data);p-next=L-next;L-next=p;voidCreateList2(LinkList&L,intn)/正位序输入n个元素的值，建立带表头构造的单链线性表inti;LinkListp,q;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;q=L;printf(请输入%d个数据n,n);for(i=1;idata);q-next=p;q=q-next;p-

5、next=NULL;2、单链表的输出Statusvisit(LinkListL)/按序输出单链表的各个元素值LinkListp=L-next;while(p)printf(%d,p-data);p=p-next;printf(n);returnOK;3、单链表结点的插入StatusListInsert(LinkList&L,inti,ElemTypee)LinkListp,s;p=L;intj=0;while(p&jnext;+j;if(!p|ji-1)returnERROR;s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-n

6、ext=s;returnOK;4、单链表结点的删除StatusListDelete(LinkList&L,inti,ElemTypee)LinkListp,q;p=L;intj=0;while(p-next&jnext;+j;if(!(p-next)|ji-1)returnERROR;q=p-next;p-next=q-next;e=q-data;free(q);returnOK;5、单链表中根据结点的值查找结点的位序intLocateElem(LinkListL,ElemTypee)/返回L中第1个值为e的数据元素的位序，若这样的数据元素不存在,则返回值为0inti=0;LinkListp=

7、L-next;while(p)i+;if(p-data=e)returni;p=p-next;return0;6、单链表中根据结点的位序返回结点的值StatusGetElem(LinkListL,inti,ElemType&e)/L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回ERRORintj=1;LinkListp=L-next;while(p&jnext;j+;if(!p|ji)returnERROR;e=p-data;returnOK;7、单链表的初始化新建一个只含头结点的单链表StatusInitList(LinkList&L)/构造一个空的单链表LL

8、=(LinkList)malloc(sizeof(LNode);if(!L)exit(OVERFLOW);L-next=NULL;returnOK;8、单链表的销毁所有结点都要销毁StatusDestroyList(LinkList&L)/销毁单链表LLinkListq;while(L)q=L-next;free(L);L=q;returnOK;9、求单链表的长度intListLength(LinkListL)/返回L中数据元素个数if(L=0)return0;inti=0;LinkListp=L-next;while(p)i+;p=p-next;returni;10、两个单链表的归并void

9、MergeList(LinkList&La,LinkList&Lb,LinkList&Lc)/已知线性表La和Lb中的数据元素按值非递减排列/归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列LinkListpa,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);第三章栈和队列栈的操作1、初始化一个顺序栈从键盘或者数组中导入数据Sta

10、tusInitStack(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;returnOK;2、判定栈能否为空StatusStackEmpty(SqStackS)/若栈S为空栈，则返回TRUE；否则返回FALSEif(S.top=S.base)returnTRUE;elsereturnFALSE;3、取栈顶元素StatusGetTop(SqStackS,SElemType

11、&e)/在教科书第47页/若栈S不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif(S.top=S.base)returnERROR;e=*(S.top-1);returnOK;4、元素进栈StatusPush(SqStack&S,SElemTypee)/插入元素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

12、.stacksize;S.stacksize+=STACK_INCREMENT;*S.top+=e;returnOK;5、元素出栈StatusPop(SqStack&S,SElemType&e)/在教科书第47页/若栈S不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top=S.base)returnERROR;e=*-S.top;returnOK;6、计算栈中数据元素的个数intStackLength(SqStackS)/返回栈S的元素个数，即栈的长度returnS.top-S.base;递归1、递归实现阶乘intf(intn)if(n=0)return1;e

13、lsereturn(n*f(n-1);2、递归实现链表的输出正序、逆序voidRevPrint(LNode*head)if(NULL!=head)if(NULL!=head-next)RevPrint(head-next);printf(%dt,head-data);/逆序后输出voidPrintList_L(LinkListL)if(L!=NULL)printf(%dt,L-data);PrintList_L(L-next);/正序输出3、递归实现链表的逆序LinkListreverse(LinkListp)LinkListq,h;if(p-next=NULL)returnp;elseq=p

14、-next;h=reverse(q);q-next=p;p-next=NULL;returnh;4、递归求链表的长度intListLength(LinkListL)intlen;if(!L)return0;len=1+ListLength(L-next);returnlen;第六章树和二叉树二叉树的操作采用二叉链式存储1、二叉树的建立StatusCreateBiTree(BiTree&T)/算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，charch;scanf(%c,if(ch=)T=NULL;elseif(!(T=(BiTNode*)malloc(sizeof

15、(BiTNode)exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);returnOK;2、二叉树的遍历四种StatusPreOrderTraverse(BiTreeT,void(*Visit)(TElemType)/初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1/操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次if(T)Visit(T-data);if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-

16、rchild,Visit)returnOK;elsereturnOK;StatusInOrderTraverse(BiTreeT,void(*Visit)(TElemType)/初始条件：二叉树T存在，Visit是对结点操作的应用函数/操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次if(T)InOrderTraverse(T-lchild,Visit);Visit(T-data);if(InOrderTraverse(T-rchild,Visit)returnOK;elsereturnOK;StatusPostOrderTraverse(BiTreeT,void(*Visi

17、t)(TElemType)/初始条件：二叉树T存在，Visit是对结点操作的应用函数/操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次if(T)PostOrderTraverse(T-lchild,Visit);if(PostOrderTraverse(T-rchild,Visit)Visit(T-data);returnOK;elsereturnOK;StatusLevelOrderTraverse(BiTreeT,void(*Visit)(TElemType)/初始条件：二叉树T存在，Visit是对结点操作的应用函数/操作结果：层序递归遍历T(利用队列)，对每个结点调用函

18、数Visit一次且仅一次LinkQueueq;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)intdepth,depthleft,depthright;if(!T)depth=0;elsedepthleft=TreeDe

19、pth(T-lchild);depthright=TreeDepth(T-rchild);depth=1+(depthleftdepthright?depthleft:depthright);returndepth;4、交换二叉树的左右子树Statusexchange(BiTreeT)/先序遍历if(T!=NULL)if(T-lchild!=NULL|T-rchild!=NULL)BiTree*p,*q;p=exchange(T-lchild);q=exchange(T-rchild);T-lchild=q;T-rchild=p;voidexchanget(BiTreeT)/后序遍历if(T!

20、=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、求二叉树的结点个数StatusNodeNum(BiTreeT,int*num)if(T)if(T-data)num+;if(NodeNum(T-lchild,num)if(NodeNum(T-rchild,num)returnOK;returnERROR;elsereturnOK;6、求二叉树的叶子数voidCountLeaf(BiTreeT,int&count)if(T)if(T-lchild=NULL&T-rchild=NULL)count+;elseCountLeaf(T-lchild,count);CountLeaf(T-rchild,count);