南审《数据结构课程设计》个人任务题目一览(2015版)

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; 顺序表按照值查找位置int LocateElem(SqLis

2、t 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); 顺序表按照序号查找元素的值Status GetElem(SqList L,int i,ElemType &e) /根据数据元素在线性表L中的位置，返回它的值if(iL.length )return ERROR;e=*(L.elem+i-1);return OK; 顺序表数据元素的插入Status ListInsert(SqList

3、 &L,int i,ElemType e) / 在L中第i个位置之前插入新的数据元素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; 顺序表数据元素的删除Status ListDelete(SqList &L,int i,ElemType &e) /删除L的第i个数据元素，并用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; 顺序表数据元素

5、的输出Status visit(SqList L) /按序输出顺序表的各个元素值 int i; for(i=1;i=L.length;i+) printf(%d ,*(L.elem+i-1); coutnext=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; void CreateList2(LinkList &L,int n) / 正位序输入n个元素的值，建立带表头结构的单链线性表int i;LinkL

6、ist p,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;单链表的输出Status visit(LinkList L) /按序输出单链表的各个元素值 LinkList p=L-next; while(p) printf(%d ,p-data); p=p-next; printf(n); return OK; 单链表结点的插入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;单链表结点的删除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;单链表中按照结点的值查找结点的位序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; 单链表中按照结点的位序返回结点的值Status GetElem(LinkList L,int i,ElemType &e) / L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给

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; 单链表的初始化（新建一个只含头结点的单链表） Status InitList(LinkList &L) / 构造一个空的单链表L L=(LinkList)malloc(sizeof(LNode); if (!L) exit(OVERFLOW); L-next=NULL; return OK; 单链表的销毁（所有结点都要销毁）Status DestroyList(LinkList

10、 &L) / 销毁单链表L LinkList q;while(L)q=L-next;free(L);L=q;return OK; 求单链表的长度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

11、的数据元素也按值非递减排列 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);第三章 栈和队列栈的操作初始化一个顺序栈（从键盘或者数组中导入数据）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;元素进栈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;计算栈中数据元素的个数int StackLength(SqStack S) / 返回栈S的元素个数，即栈的长度 return S.top-S.base;递归递归实现阶乘int f(int n) if(n=0) return 1; else return (n*f(n-1);递归实现

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); /正序输出递归实现链表的逆序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;第六章 树和二叉树二叉树的操作（采用二叉链式存储）二叉树的建立Status CreateBiTree(BiTree &T) / 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)， 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是对结点操作的应用函数。修改算法6.1/ 操作结果：先序递归遍历T，对每个结点调用函数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是对结点操作的应用函数/ 操作结果：中序递归遍历T，对每个结点调用函数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是对结点操作的应用函数/ 操作结果：后序递归遍历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)(TElem

20、Type) / 初始条件：二叉树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;求二叉树高度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;求二叉树的结点个数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; 求二叉树的叶子数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;树的操作（采用左孩子右兄弟存储结构）求树的深度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; 求树中给定结点的右兄弟TElemType RightSibling(CSTree T,TElemType cur_e) / 初始