首页 淘文阁 - 分享文档赚钱的网站 > 教育专区 > 教案示例 > 南审《数据结构课程教学设计》个人说明任务题目一览(2015年度版).doc

南审《数据结构课程教学设计》个人说明任务题目一览(2015年度版).doc

收藏

编号：2582515    类型：共享资源    大小：62.02KB    格式：DOC    上传时间：2020-04-22
8
金币
举报
举报 版权申诉
版权申诉 word格式文档无特别注明外均可编辑修改；预览文档经过压缩，下载后原文更清晰！ 立即下载
关 键 词：
数据结构课程教学设计 南审 数据结构 课程 教学 设计 个人 说明 任务 题目 一览 年度
资源描述：
.- 第二章 线性表 顺序表的操作 1、 顺序表的建立（从键盘或者数组中导入数据） Status InitList(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; } 2、 顺序表按照值查找位置 int LocateElem(SqList L, ElemType e) { //根据数据元素的值，返回它在线性表L中的位置 int i=0; while ((i<=L.length)&&(*(L.elem+i-1)!=e)) i++; if (i<=L.length) return i; else return(-1); } 3、 顺序表按照序号查找元素的值 Status GetElem(SqList L,int i,ElemType &e) { //根据数据元素在线性表L中的位置，返回它的值 if(i<1||i>L.length ) return ERROR; e=*(L.elem+i-1); return OK; } 4、 顺序表数据元素的插入 Status ListInsert(SqList &L,int i,ElemType e) { // 在L中第i个位置之前插入新的数据元素e，L的长度加1 ElemType *p,*q,*newbase; if(i<1||i>L.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.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q; --p) *(p+1)=*p; *q=e; ++L.length ; return OK; } 5、 顺序表数据元素的删除 Status ListDelete(SqList &L,int i,ElemType &e) { //删除L的第i个数据元素，并用e返回其值，L的长度减1 ElemType *q,*p; if(i<1||i>L.length) return ERROR; p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p<=q;++p) *(p-1)=*p; --L.length; return OK; } 6、 顺序表数据元素的输出 Status visit(SqList L) { //按序输出顺序表的各个元素值 int i; for(i=1;i<=L.length;i++) printf("%d ",*(L.elem+i-1)); cout<next=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; } } void CreateList2(LinkList &L,int n) { // 正位序输入n个元素的值，建立带表头结构的单链线性表 int i; LinkList p,q; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; q=L; printf("请输入%d个数据\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、 单链表的输出 Status visit(LinkList L) { //按序输出单链表的各个元素值 LinkList p=L->next; while(p) { printf("%d ",p->data); p=p->next; } printf("\n"); return OK; } 3、 单链表结点的插入 Status ListInsert(LinkList &L,int i,ElemType e) { LinkList p,s;p=L;int j=0; while(p&&jnext; ++j; } if(!p||j>i-1)return ERROR; s=(LinkList)malloc(sizeof(LNode)); s->data=e;s->next=p->next; p->next=s; return OK; } 4、 单链表结点的删除 Status ListDelete(LinkList&L,int i,ElemType e) { LinkList p,q;p=L; int j=0; while(p->next&&jnext; ++j; } if(!(p->next)||j>i-1)return ERROR; q=p->next;p->next=q->next; e=q->data;free(q); return OK; } 5、 单链表中按照结点的值查找结点的位序 int LocateElem(LinkList L,ElemType e) { // 返回L中第1个值为e 的数据元素的位序，若这样的数据元素不存在,则返回值为0 int i=0; LinkList p=L->next; while(p) { i++; if(p->data==e) return i; p=p->next; } return 0; } 6、 单链表中按照结点的位序返回结点的值 Status GetElem(LinkList L,int i,ElemType &e) { // L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回 ERROR int j=1; LinkList p=L->next; while(p&&jnext; j++; } if(!p||j>i) return ERROR; e=p->data; return OK; } 7、 单链表的初始化（新建一个只含头结点的单链表） Status InitList(LinkList &L) { // 构造一个空的单链表L L=(LinkList)malloc(sizeof(LNode)); if (!L) exit(OVERFLOW); L->next=NULL; return OK; } 8、 单链表的销毁（所有结点都要销毁） Status DestroyList(LinkList &L) { // 销毁单链表L LinkList q; while(L){ q=L->next; free(L); L=q; } return OK; } 9、 求单链表的长度 int ListLength(LinkList L) { // 返回L中数据元素个数 if(L==0) return 0; int i=0; LinkList p=L->next; while(p) { i++; p=p->next; } return i; } 10、两个单链表的归并 void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc) { //已知线性表La和Lb中的数据元素按值非递减排列 //归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列 LinkList pa,pb,pc; pa=La->next;pb=Lb->next; Lc=pc=La; while(pa&&pb) { if(pa->data<=pb->data) { pc->next=pa; pc=pa; pa=pa->next; } else{pc->next=pb; pc=pb; pb=pb->next;} } pc->next=pa?pa:pb; free(Lb); } 第三章 栈和队列 栈的操作 1、 初始化一个顺序栈（从键盘或者数组中导入数据） Status InitStack(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; return OK; } 2、 判断栈是否为空 Status StackEmpty(SqStack S) { // 若栈S为空栈，则返回TRUE；否则返回FALSE if(S.top==S.base)return TRUE; else return FALSE; } 3、 取栈顶元素 Status GetTop(SqStack S,SElemType &e) // 在教科书第47页 { // 若栈S不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(S.top==S.base)return ERROR; e=*(S.top-1); return OK; } 4、 元素进栈 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.top++=e; return OK; } 5、 元素出栈 Status Pop(SqStack &S,SElemType &e) // 在教科书第47页 { // 若栈S不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(S.top==S.base)return ERROR; e=*--S.top; return OK; } 6、 计算栈中数据元素的个数 int StackLength(SqStack S) { // 返回栈S的元素个数，即栈的长度 return S.top-S.base; } 递归 1、 递归实现阶乘 int f(int n) { if(n==0) return 1; else return (n*f(n-1)); } 2、 递归实现链表的输出（正序、逆序） void RevPrint(LNode *head) { if(NULL!=head) { if(NULL!=head->next) { RevPrint(head->next); } printf("%d\t",head->data); } } //逆序后输出 void PrintList_L(LinkList L) { if(L!=NULL) { printf("%d\t",L->data); PrintList_L(L->next); } } //正序输出 3、 递归实现链表的逆序 LinkList reverse(LinkList p) { LinkList q,h; if(p->next==NULL) return p; else { q=p->next; h=reverse(q); q->next=p; p->next=NULL; return h; } } 4、 递归求链表的长度 int ListLength(LinkList L) { int len; if(!L) return 0; len=1+ListLength(L->next); return len; } 第六章 树和二叉树 二叉树的操作（采用二叉链式存储） 1、 二叉树的建立 Status CreateBiTree(BiTree &T) { // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)， char ch; scanf("%c",&ch); if(ch== ) T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK; } 2、 二叉树的遍历（四种） Status PreOrderTraverse(BiTree T,void(*Visit)(TElemType)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1 // 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) { Visit(T->data); if(PreOrderTraverse(T->lchild,Visit)) if(PreOrderTraverse(T->rchild,Visit)) return OK; } else return OK; } Status InOrderTraverse(BiTree T,void(*Visit)(TElemType)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) { InOrderTraverse(T->lchild,Visit); Visit(T->data); if(InOrderTraverse(T->rchild,Visit)) return OK; } else return OK; } Status PostOrderTraverse(BiTree T,void(*Visit)(TElemType)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：后序递归遍历T，对每个结点调用函数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)(TElemType)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：层序递归遍历T(利用队列)，对每个结点调用函数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; } 3、 求二叉树高度 int TreeDepth(BiTree T) { int depth,depthleft,depthright; if(!T) depth=0; else { depthleft=TreeDepth(T->lchild); depthright=TreeDepth(T->rchild); depth=1+(depthleft>depthright?depthleft:depthright); } return depth; } 4、 交换二叉树的左右子树 Status exchange(BiTree T) //先序遍历 { 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; } 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; } 5、 求二叉树的结点个数 Status NodeNum(BiTree 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; } 6、 求二叉树的叶子数 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); } } } 7、 按照目录形式输出二叉树 Status PrintTree(BiTree bt,int nLayer) /* 按竖向树状打印的二叉树 */ { if(bt!=NULL) { PrintTree(bt->lchild,nLayer+1); for(int i=0;idata); PrintTree(bt->rchild,nLayer+1); } return OK; } 树的操作（采用左孩子右兄弟存储结构） 1、 求树的深度 int TreeDepth(CSTree T) { // 初始条件：树T存在。操作结果：返回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; } } 2、 求树中给定结点的右兄弟 TElemType RightSibling(CSTree T,TElemType cur_e) { // 初始条件：树T存在，cur_e是T中某个结点 // 操作结果：若cur_e有右兄弟，则返回它的右兄弟；否则返回“空” CSTree f; f=Point(T,cur_e); if(f&&f->nextsibling) return f->nextsibling->data; else return ; } 3、 树的后根遍历 void PostOrderTraverse(CSTree T,void(*Visit)(TElemType)) { CSTree p; if(T) { if(T->firstchild) { PostOrderTraverse(T->firstchild,Visit); p=T->firstchild->nextsibling; while(p) { PostOrderTraverse(p,Visit); p=p->nextsibling; } } Visit(T->data); } 第九章 查找 1、顺序查找法 int Search_Seq(SSTable ST,KeyType key) { // 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为 // 该元素在表中的位置，否则为0。 int i=0; ST.elem[0].key=key; for(i=ST.length;ST.elem[i].key!=key;--i); return i; } 2、 折半查找法 int Search_Bin(SSTable ST,KeyType key) { // 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为 // 该元素在表中的位置，否则为0。 int low=1,high=ST.length,mid; while(low<=high) { mid=(low+high)/2; if(key==ST.elem[mid].key) return mid; else if(key
展开阅读全文
提示  淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
关于本文
本文标题：南审《数据结构课程教学设计》个人说明任务题目一览(2015年度版).doc
链接地址：https://www.taowenge.com/p-2582515.html
关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

本站为文档C TO C交易模式，本站只提供存储空间、用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知淘文阁网，我们立即给予删除！客服QQ：136780468 微信：18945177775 电话：18904686070

工信部备案号：黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

收起
在线客服
意见反馈
返回顶部
展开
QQ交谈
返回顶部