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

1第二章线性表顺序表的操作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((i=L.length)&&(*(L.elem+i-1)!=e))i++;if(i=L.length)returni;elsereturn(-1);}3、顺序表按照序号查找元素的值StatusGetElem(SqListL,inti,ElemType&e){//根据数据元素在线性表L中的位置，返回它的值if(i1||iL.length)returnERROR;e=*(L.elem+i-1);returnOK;}4、顺序表数据元素的插入StatusListInsert(SqList&L,inti,ElemTypee){//在L中第i个位置之前插入新的数据元素e，L的长度加1ElemType*p,*q,*newbase;if(i1||iL.length+1)returnERROR;if(L.length=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);2L.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;returnOK;}5、顺序表数据元素的删除StatusListDelete(SqList&L,inti,ElemType&e){//删除L的第i个数据元素，并用e返回其值，L的长度减1ElemType*q,*p;if(i1||iL.length)returnERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p=q;++p)*(p-1)=*p;--L.length;returnOK;}6、顺序表数据元素的输出Statusvisit(SqListL){//按序输出顺序表的各个元素值inti;for(i=1;i=L.length;i++)printf(%d,*(L.elem+i-1));coutendl;printf(L.elem=%uL.length=%dL.listsize=%d\n,L.elem,L.length,L.listsize);returnOK;}单链表的操作1、单链表的建立voidCreateList(LinkList&L,intn){//逆位序输入n个元素的值，建立带表头结构的单链线性表Linti;LinkListp;L=(LinkList)malloc(sizeof(LNode));L-next=NULL;printf(请输入%d个数据\n,n);for(i=n;i0;--i){3p=(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;i=n;i++){p=(LinkList)malloc(sizeof(LNode));scanf(%d,&p-data);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&&ji-1){p=p-next;++j;}4if(!p||ji-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&&ji-1){p=p-next;++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=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&&ji){p=p-next;j++;}5if(!p||ji)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的数据元素也按值非递减排列6LinkListpa,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、初始化一个顺序栈（从键盘或者数组中导入数据）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)7{//插入元素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(%d\t,head-data);}}//逆序后输出voidPrintList_L(LinkListL){8if(L!=NULL){printf(%d\t,L-data);PrintList_L(L-next);}}//正序输出3、递归实现链表的逆序LinkListreverse(LinkListp){LinkListq,h;if(p-next==NULL)returnp;else{q=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,&ch);if(ch=='')T=NULL;else{i