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

南审（数据构造课程教学设计）个人讲明任务题目一览(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;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)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;+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(+p;pnext=NULL;printf("请输入%d个数据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个元素的值，建立带表头构造的单链线性表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->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|j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode);s->data=e;s->next=p->next;p->next=s;returnOK;4、单链表结点的删除StatusListDelete(LinkList&L,inti,ElemTypee)LinkListp,q;p=L;intj=0;while(p->next&&jnext;+j;if(!(p->next)|j>i-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=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|j>i)returnERROR;e=p->data;returnOK;7、单链表的初始化新建一个只含头结点的单链表StatusInitList(LinkList&L)/构造一个空的单链表LL=(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、两个单链表的归并voidMergeList(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、初始化一个顺序栈从键盘或者数组中导入数据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;returnOK;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、元素进栈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.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;elsereturn(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->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(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->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(*Visit)(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(利用队列)，对每个结点调用函数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=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->lchild);q=exchange(T->rchild);T->lchild=q;T->rchild=p;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、求二叉树的结点个数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);