中国地质大学数据结构实习报告

-1-PracticeReportforDataStructuresandAlgorithmAnalysisDataStructuresCourseReportCandidate:StudentNumber:Major:CommunicationEngineeringSupervisor:WurangzhongChinaUniversityofGeosciences(Wuhan)Wuhan,Hubei430074,P.R.ChinaMay18,2013ChinaUniversityofGeosciences,FacultyofMechanicsandElectronicInformation-2-线性表的实现1.用链表实现线性表这些是程序中一些子程序的声明，用它们来创建链表，并完成插入、删除、查找元素等操作，并且可以按照元素位置或者元素大小来进行这些操作。pNodeCreateLinkLists();voidPrintLists(pNodeL);voidInsertRear(pNodeL);voidInsertHead(pNodeL);voidInsertkTh(pNodeL,intposition,ElemTypex);intGetLength(pNodeL);pNodeFind(ElemTypex,pNodeL);pNodeFindPrevoius(ElemTypex,pNodeL);intIsEmpty(pNodeL);intIsLast(pNodeP,pNodeL);voidDelete(ElemTypex,pNodeL);voidDeletekTh(intposition,pNodeL);voidDeleteList(pNodeL);插入程序代码voidInsertkTh(pNodeL,intposition,ElemTypex){inti;pNodeTmpNode,Tmp=L;TmpNode=(pNode)malloc(sizeof(structNode));TmpNode-data=x;TmpNode-next=NULL;for(i=0;iposition-1;i++){if(Tmp-next==NULL){printf(Theinsertionpositionisinvalid!\n);return;}elseTmp=Tmp-next;}TmpNode-next=Tmp-next;Tmp-next=TmpNode;}-3-删除程序代码voidDeletekTh(intposition,pNodeL){pNodeTmp=L,TmpPre=NULL;inti=0;for(i=0;iposition;i++){if(Tmp-next!=NULL){TmpPre=Tmp;Tmp=Tmp-next;}elseif(Tmp-next==NULL&&iposition){printf(TheDeletionpositionisinvalid!\n);return;}}TmpPre-next=Tmp-next;free(Tmp);}这是程序主函数，以此来完成以上子函数的功能#includestdio.h#includemalloc.h#includelianbiao.hintmain(){inti,x,position;pNodem;pNodeLinkLists;{printf(输入元素来建立链表，0为结束输入的标志);LinkLists=CreateLinkLists();printf(链表为:);PrintLists(LinkLists);}printf(选择你需要的操作，输入序号：\n);printf(1.建立一个链表\n);printf(2.输出链表\n);-4-printf(3.插入一个元素到链表中\n);printf(4.查找链表中的元素\n);printf(5.删除链表中的元素\n);printf(6.清空链表\n);scanf(%d,&i);switch(i){case1:{printf(输入元素来建立链表，0为结束输入的标志);LinkLists=CreateLinkLists();printf(链表为:);PrintLists(LinkLists);}case2:{PrintLists(LinkLists);break;}case3:{printf(依次输入插入的位置和元素);scanf(%d,&position);scanf(%d,&x);InsertkTh(LinkLists,intposition,ElemTypex);break;}case4:{printf(输入要查找的元素);scanf(%d,&x);m=Find(ElemTypex,LinkLists);printf(%d,m);break;}case5:{printf(输入要删除的元素的位置);scanf(%d,&position);DeletekTh(intposition,LinkLists);break;}case6:{DeleteList(LinkLists);break;}}-5-}2.数组实现线性表用数组实现的功能和用链表表示的相同部分子函数如下//初始化顺序表：给出初始化长度intinitialArray(arrayListarrLst,intlen){arrLst-length=0;arrLst-size=len;arrLst-Array=(ElemType*)malloc(len*sizeof(ElemType));if(arrlst-Array==NULL)return0;elsereturn1;}//删除顺序表voiddeleteArray(arrayListarrLst){arrLst-length=0;arrLst-size=0;free(arrLst-Array);arrLst-Array=NULL;}//清空顺序表voidclearArray(arrayListarrLst){-6-arrLst-length=0;}//判断是否为空intis_empty(arrayListarrLst){if(0==arrLst-length){printf(thearrayListisempty!\n);return1;}else{printf(thearrayListisnotempty!\n);return0;}}//求有多少个元素intarrayLength(arrayListarrLst){returnarrLst-length;}//取出某个元素intgetElem(arrayListarrLst,intindex,ElemTypee){if(index0||indexarrayLength(arrLst)-1)return0;else{e=arrLst-Array[index];return1;}}//遍历顺序表，并打印voidprintArray(arrayListarrLst){inti;printf(arrayelementsare:);for(i=0;iarrayLength(arrLst);++i){printf(%d\t,arrLst-Array[i]);-7-}printf(\n);}//判断某个元素的位置intlocateElem(arrayListarrLst,ElemTypee){inti;for(i=0;iarrayLength(arrLst);++i){if(e==arrLst-Array[i])returni;}return-1;}堆栈主要是实现元素的进栈、出栈、判断栈中元素个数堆栈的源函数#includestdio.h#includemalloc.h#includeduizhan.hSTACKCreatStack(){STACKS;S=(STACK)malloc(sizeof(structStack));if(S==NULL){printf(无法建立堆栈!);return0;}S-top=-1;returnS;}intIsFull(STACKS){return(S-top==MAX-1);}intIsEmpty(STACKS){-8-return(S-top==-1);}voidPush(ElemTypeX,STACKS){if(IsFull(S)){printf(堆栈已满，元素无法进栈\n);}else{S-top++;S-data[S-top]=X;}}voidPop(STACKS){if(IsEmpty(S))printf(堆栈为空，元素无法出栈\n);elseS-top--;}ElemTypeTop(STACKS){if(!IsEmpty(S))returnS-data[S-top];elseprintf(堆栈为空！\n);}intDisposeStack(STACKS){if(S==NULL)return0;else{free(S);printf(堆栈已成功清空！\n);return1;}}-9-intStackLen(STACKS){if(!IsEmpty(S))returnS-top;elsereturn0;}堆栈的主函数#includestdio.h#includemalloc.h#includeduizhan.hvoidmain(){STACKliliS;liliS=CreatStack();Push(1,liliS);Push(2,liliS);Push(3,liliS);Pop(liliS);Pop(liliS);DisposeStack(liliS);}设置断点可以看到栈中的元素-10-模式匹配这是模式匹配原函数，采用了KMP方式进行匹配#includestdio.h#includemoshipipei.hintIndexKMP(STRING*S,STRING*T,intnext[]){inti=0;intj=0;while(iS-length&&jT-length){if(j==-1||S-p_str[i]==T-p_str[j]){++i;++j;}elsej=next[j];}if(j==T-length)returni-T-length+1;elsereturn0;}voidGetNext(STRING*P,intnext[]){inti=0;next[0]=-1;intj=-1;while(iP-length){if(j==-1||P-p_str[i]==P-p_str[j]){++i;++j;next[i]=j;}elsej=next[j];}}#includestdio.h#includemalloc.h#includestring.h#includemoshipipei.h-11-主函数voidmain(){STRING*Str,*Pat;intposition=0;Str=(STRING*)malloc(sizeof(STRING));Pat=(STRING*)malloc(sizeof(STRING));charS_str[20]=ababcabcacbab;charP_str[20]=abcac;Str-p_str=S_str;Str-length=strlen(S_str);Pat-p_str=P_str;Pat-length=strlen(P_str);int*next=(int*)malloc(sizeof(int)*(Pat-length+1));GetNext(Pat,next);position=IndexKMP(Str,Pat,next);printf(%d\n,position);}显示两个字符串是在第6个元素开匹配的。-12-稀疏矩阵TSMatrixNewMatrix(intm,intn){//新建一个三元组表示的稀疏矩阵TSMatrixM;M.mu