北郵數(shù)據(jù)結構實驗報告

北郵數(shù)據(jù)結構實驗報告北郵數(shù)據(jù)結構實驗報告「篇一」數(shù)據(jù)結構實驗報告總結設計題目：模擬計算器程序?qū)W生姓名：謝先斌系別：計算機與通信工程學院專業(yè)：計算機科學與技術班級：1班學號：541007010144指導教師：盧冰李曄2012年6月21日鄭州輕工業(yè)學院課程設計任務書題目模擬計算器程序?qū)I(yè)、班級計算機科學與技術10-01班學號541007010144姓名謝先斌主要內(nèi)容：設計一個模擬計算器的程序，要求能對包含加、減、乘、除、括號運算符及SQR和ABS函數(shù)的任意整型表達式進行求解?；疽螅阂獧z查有關運算的條件，并對錯誤的條件產(chǎn)生報警。主要參考資料：[1]嚴蔚敏吳偉民編著《數(shù)據(jù)結構(C語言版)》清華大學出版社第44頁3.1棧、第52頁3.2.5表達式求值完成期限：2012年6月21日指導教師簽名：課程負責人簽名：2012年6月21日一、設計題目模擬計算器的程序設計一個模擬計算器的程序，要求能對包含加、減、乘、除、括號運算符及SQR和ABS函數(shù)的任意整型表達式進行求解。設計要求：要檢查有關運算的條件，并對錯誤的條件產(chǎn)生報警。二、算法設計的思想本程序設計主要是應用了棧，利用棧的“先進后出”原理，建立了兩個棧，分別為運算符棧pOStack和運算數(shù)棧pDStack。算法的基本思想(參考課本p53頁)是：(1)首先置操作數(shù)棧為pDStack空棧，表達式起始符為“=”，位運算符棧的棧底元素;(2)依次讀入表達式中的每個字符，若是操作數(shù)則進入pDStack棧，若是運算符則和pOStack棧的棧定運算符比較優(yōu)先權后作相應操作，直到整個表達式求值完畢(即pOStack棧的棧定元素和當前讀入的字符均為“=”)。三、算法的流程圖本程序的流程如下附圖1所示：附圖1程序流程圖四、算法設計分析首先創(chuàng)建了兩個棧：typedefstructOPStack//定義運算符棧{charopStack[MAX_OPERATOR_NUM];inttop;}OPStack,*pOPStack;typedefstructDATAStack//定義運算數(shù)棧{doublestack[MAX_DATA_NUM];inttop;}DATAStack,*pDATAStack;來分別存放運算符和運算數(shù)。在兩個結構體中均有一個top數(shù)據(jù)域，當top=-1時，表示該站為空棧。定義一個Evaluateexpression_r函數(shù)來完成函數(shù)運算的主要功能：讀入表達式，并計算結果。以下是對該函數(shù)的分析：當一次運算開始時，分別調(diào)用InitpOPStack(pOPStack&pOStack)函數(shù)和InitpDATAStack(pDATAStack&pDStack)函數(shù)分別對運算符棧和運算數(shù)棧進行初始化。調(diào)用PushOPStack(pOStack,=)函數(shù)來完成運算符棧棧低元素的設置。通過PushOPStack(pOPStack&pOStack,charch)函數(shù)、PopOPStack(pOPStack&pOStack,char&ch)函數(shù)、PushDATAStack(pDATAStack&pDStack,doubled)函數(shù)和PopDATAStack(pDATAStack&pDStack,double&d)函數(shù)來分別完成運算符和運輸數(shù)的進出棧操作。getToppOPStack(pOPStack&pOStack)函數(shù)和getToppDATAStack(pDATAStack&pDStack)函數(shù)主要是進行得到棧定元素的作用，特別是在對運算符棧優(yōu)先級的比較中十分重要，其中還會調(diào)用IsOP(char&ch)函數(shù)來區(qū)分讀入的是運算符還是運算數(shù)。ChangeChar(char&c)函數(shù)當每次讀入一個字符是都會調(diào)用一次，主要的作用就是完成不用區(qū)分A、S的大小的功能。Precede(charop1,charop2)函數(shù)主要是通過一個二維字符串數(shù)組來存放9種運算符的優(yōu)先級比較的結果，每當讀到一個運算符后就進行與運算符棧頂元素比較，通過返回的“<、>、=”結果來進行下一步的操作：<表示棧頂元素優(yōu)先級低，運算符進棧;=表示脫括號并接受下一個字符;>表示運算符和運算數(shù)各退棧一次并調(diào)用Operate(doublea,chartheta,doubleb)函數(shù)(主要是對出棧的運算符和運算數(shù)進行計算)，最后將運算結果壓入運算數(shù)棧pDStack。當操作結束時運算數(shù)棧的棧頂元素就是計算結果，分別調(diào)用ClearpOPStack(pOStack)函數(shù)清空運算符棧、ClearpDATAStack(pDStack)函數(shù)清空運算數(shù)棧以待下一次繼續(xù)進行相關操作。print_user函數(shù)和exit_E函數(shù)開始和結束時個調(diào)用一次，分別完成歡迎界面和退出界面的布置。main是本程序的主函數(shù)，主要通過while語句和switch語句來完成本程序的運行，當輸入Y(y)時調(diào)用Evaluateexpression_r函數(shù)完成計算，當輸入N(n)時，調(diào)用exit_E函數(shù)退出本程序的運行。本程序還考慮到各種異常的處理，如運算時除數(shù)為0、被開方數(shù)為0等情況的出現(xiàn)，最終的處理是直接退出程序的運行。五、運行結果分析1.程序開始界面，如附圖2：附圖2開始界面2.如下附圖3，附圖4分別是選擇進入和退出程序界面：附圖3(在以下界面輸入計算式即可運行出計算結果如附圖5)附圖4退出界面附圖5運行界面2.對異常的處理a)對異常1除數(shù)為0，如輸入“1+2/0=”程序?qū)⒅苯油顺?，如附圖6：附圖6異常1除數(shù)為0b)對異常2被開方數(shù)為負數(shù)，如輸入“3+S(-9)=”程序?qū)⒅苯油顺觯绺綀D7：附圖7異常2被開方數(shù)為負數(shù)3.以下是對各種簡單運算的運行結果，如附圖8：附圖8簡單運算3.綜合運算：如式子“1/2+A(7-8)-S(9*8)=”運行結果如附圖9附圖9綜合運算六、收獲及體會本程序以C語言的棧的相關知識為基礎，通過控制兩個棧(運算數(shù)棧和運算符棧)的進出的棧操作，來實現(xiàn)對包含加、減、乘、除、括號運算符及SQRT和ABS函數(shù)的任意整型表達式的求解運算。從程序的編寫來看，感覺這次自己真的學到了好多，特別是對程序的開發(fā)流程。從最初的選定程序，到最終的程序運行成功，讓我感到如果是僅僅掌握課本上的知識是遠遠不能夠很好的應用到實際的編程中去的。在這個過程中還需要我們更多的去考慮到實際條件的種種限制和約束。我在寫本程序的過程中也遇到了很多的問題，當然本程序的核心問題就是對兩個棧的壓出棧操作，需要做優(yōu)先級判斷，并要考慮什么時候進棧，什么時候出棧等操作。我采用了課本上第52-54頁講的通過一個二維字符串數(shù)組來控制比較“+-*、AS=”共9個運算符的優(yōu)先級控制。對異常，如除數(shù)為0、被開方數(shù)小于0等異常也進行了精心的處理。對操作過程中要用到的Y、N、A、S等字符也進行了改進，最終本程序可以不區(qū)分大小寫就完成相關操作。總之，經(jīng)過本次專業(yè)課程設計，讓我掌握了開發(fā)應用軟件的基本流程，運用所學編程技能的基本技巧，也讓我初步了解了軟件設計的基本方法，提高進行工程設計的基本技能及分析、解決實際問題的能力，為以后畢業(yè)設計和工程實踐等打下良好的基礎。相信通過這次的課程設計，我對所學的《數(shù)據(jù)結構(C語言版)》和各種編程語言都有了一個全新的認識。我也會積極吸取本次課程設計的經(jīng)驗，繼續(xù)研究數(shù)據(jù)結構和所學的各種編程語言。七、源代碼#include#include#include#include#defineMAX_OPERATOR_NUM100//運算符棧數(shù)組長度#defineMAX_DATA_NUM100//運算數(shù)棧數(shù)組長度typedefstructOPStack//定義運算符棧{charopStack[MAX_OPERATOR_NUM];inttop;}OPStack,*pOPStack;typedefstructDATAStack//定義運算數(shù)棧{doublestack[MAX_DATA_NUM];inttop;}DATAStack,*pDATAStack;voidInitpOPStack(pOPStack&pOStack)//初始化運算符棧{if(！(pOStack=(pOPStack)malloc(sizeof(OPStack))))//為運算符棧分配空間{printf("分配內(nèi)存空間失敗！");exit(-1);}pOStack->top=-1;}voidInitpDATAStack(pDATAStack&pDStack)//初始化運算數(shù)棧{if(！(pDStack=(pDATAStack)malloc(sizeof(DATAStack))))//為運算數(shù)棧分配空間{printf("分配內(nèi)存空間失?。?);exit(-1);}pDStack->top=-1;}voidPushOPStack(pOPStack&pOStack,charch)//運算符進棧{pOStack->opStack[++(pOStack->top)]=ch;}voidPopOPStack(pOPStack&pOStack,char&ch)//運算符出棧{ch=pOStack->opStack[pOStack->top];pOStack->top--;}voidPushDATAStack(pDATAStack&pDStack,doubled)//運算數(shù)進棧{++(pDStack->top);pDStack->stack[pDStack->top]=d;}voidPopDATAStack(pDATAStack&pDStack,double&d)//運算數(shù)出棧{d=pDStack->stack[pDStack->top];pDStack->top--;}voidClearpOPStack(pOPStack&pOStack)//清空運算符棧{pOStack->top=-1;}voidClearpDATAStack(pDATAStack&pDStack)//清空運算數(shù)棧{pDStack->top=-1;}charGetToppOPStack(pOPStack&pOStack)//獲取運算符棧頂元素{returnpOStack->opStack[pOStack->top];}doubleGetToppDATAStack(pDATAStack&pDStack)//獲取運算數(shù)棧頂元素{returnpDStack->stack[pDStack->top];}boolIsOP(char&ch)//區(qū)分運算符和運算數(shù)的函數(shù)，是運算符時返回true,否則返回false{//判斷是否為符號if((ch==+)||(ch==-)||(ch==*)||(ch==/)||(ch===)||(ch==A)||(ch==S)||(ch==a)||(ch==s)||(ch==()||(ch==)))returntrue;elsereturnfalse;}charPrecede(charop1,charop2)//參考《數(shù)據(jù)結構》(C語言版)第53頁3.2.5表達式求值表3.1{chartab[9][10];//定義字符串的二維數(shù)組來存放運算符優(yōu)先級的關系strcpy(tab[0],">><<<><<>");strcpy(tab[1],">><<<><<>");strcpy(tab[2],">>>><><<>");strcpy(tab[3],">>>><><<>");strcpy(tab[4],"<<<<<=<strcpy(tab[5],">>>>E>>>>");strcpy(tab[6],">>>><>>>>");strcpy(tab[7],">>>><>>>>");strcpy(tab[8],"<<<<printf("|歡迎您的下次使用！謝謝！|");//退出使用printf("|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|");}doubleOperate(doublea,chartheta,doubleb)//對出棧的運算符和運算數(shù)進行計算{doubles;switch(theta){case+:s=a+b;break;case-:s=a-b;break;case*:s=a*b;break;case/:if(b！=0)//判斷除數(shù)是否為0，若為0，退出程序{s=a/b;break;}else{printf("####除數(shù)為0，非法運算。程序終止！####");exit_E//打印結束菜單exit(-1);}caseA:s=fabs(b);//調(diào)用FABS函數(shù)break;caseS:if(b>=0)//判斷被開方數(shù)是否為0，若為0，退出程序{s=sqrt(b);//調(diào)用SQRT函數(shù)break;}else{printf("####求負數(shù)的平方根是非法運算。程序終止！####");exit_E//打印結束菜單exit(-1);}}returns;}charChangeChar(char&c)//通過ChangeChar函數(shù)來把a、s的小寫字母改為大寫的{if(c==a)c=Aelseif(c==s)c=Sreturnc;}//參考《數(shù)據(jù)結構》(C語言版)第53頁3.2.5表達式求值算法3.4Evaluateexpression_r函數(shù)voidEvaluateexpression_r//計算函數(shù)：讀入表達式，并計算結果{pOPStackpOStack;//聲明運算符棧pDATAStackpDStack;//聲明運算數(shù)棧doubleresult;//存運算的結果charx,theta,c;//c存放讀取的字符,x、theta存放運算符棧的棧頂元素intflag,data;//標識符，用來讀入連續(xù)的數(shù)字doubles;doublegetd;//存放GetTop的結果doublea,b,cc;//a,b存放數(shù)據(jù)棧出棧的棧頂元素,c存放運算結果flag=0;//初始化標識符，用來判斷字符串中的連續(xù)數(shù)字data=0;//InitpOPStack(pOStack);//初始化運算符棧InitpDATAStack(pDStack);//初始化運算數(shù)棧PushOPStack(pOStack,=);//在運算符棧底放入=printf("&請輸入表達式以=結束：");c=get);//讀入字符ChangeChar(c);//通過調(diào)用函數(shù)來實現(xiàn)把小寫的a、s改為大寫的A、Swhile(c！==||GetToppOPStack(pOStack)！==){if(！IsOP(c))//不是運算符進棧{s=c-0//把字符轉化為數(shù)字if(flag==1){PopDATAStack(pDStack,getd);s=getd*10+s;}PushDATAStack(pDStack,s);flag=1;c=get);ChangeChar(c);}else{flag=0;switch(Precede(GetToppOPStack(pOStack),c))//輸入元素和運算符棧頂元素比較{case<://棧頂元素優(yōu)先級低PushOPStack(pOStack,c);c=get);ChangeChar(c);break;case=://托括號并接受下一個字符PopOPStack(pOStack,x);c=get);ChangeChar(c);break;case>://退棧并將運算結果進棧PopOPStack(pOStack,theta);PopDATAStack(pDStack,b);PopDATAStack(pDStack,a);cc=Operate(a,theta,b);PushDATAStack(pDStack,cc);break;}//switch}//else}//whileresult=GetToppDATAStack(pDStack);//運算結束時，運算數(shù)棧的棧底元素就是計算結果ClearpOPStack(pOStack);//清空運算符棧ClearpDATAStack(pDStack);//清空運算數(shù)棧printf("->計算結果為：%.2f",result);//輸出運算結果return;}voidprint_user//歡迎界面{printf("歡迎使用C語言版模擬計算器");printf("");printf("|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|");printf("|模擬計算器使用說明|");printf("|作者：謝先斌|");printf("|本程序包括對+、-、*、/、的運算|");printf("|本程序中ABS算用A替代、SQRT運算用S代替|");printf("|本程序中的一切字母均不區(qū)分大小寫|");printf("正確的表達式如：1+A(7-8)+S(9*8)=");printf("|輸入=表示表達式輸入結束！|");printf("|歡迎使用！-->-->|");printf("|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|");printf("");}intmain//主函數(shù){charin;boolb;//標識符，用來標識是否結束程序b=true;//初始化，不結束print_user//打印歡迎界面printf("*請確認使用計算器Y/N:");while(1){scanf("%c",&in);//確認是否繼續(xù)操作get);//吃掉會車，避免干擾switch(in){caseY:casey:{Evaluateexpression_r//進入計算函數(shù)：讀入表達式，并計算結果break;}caseN:casen:{exit_Eb=false;break;}//default://printf("輸入錯誤，請重新輸入Y/N:");//break;}if(b==false)//如果b==false,退出整個程序break;printf("*您確定要繼續(xù)使用計算機Y/N:");get);//用getchar吃掉回車，避免對后續(xù)輸入中in的干擾}return0;}北郵數(shù)據(jù)結構實驗報告「篇二」一、實驗目的及要求1)掌握棧和隊列這兩種特殊的線性表，熟悉它們的特性，在實際問題背景下靈活運用它們。本實驗訓練的要點是“?！焙汀瓣犃小钡挠^點;二、實驗內(nèi)容1)利用棧，實現(xiàn)數(shù)制轉換。2)利用棧，實現(xiàn)任一個表達式中的語法檢查(選做)。3)編程實現(xiàn)隊列在兩種存儲結構中的基本操作(隊列的初始化、判隊列空、入隊列、出隊列);三、實驗流程、操作步驟或核心代碼、算法片段順序棧：StatusInitStack(SqStack&S){S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(！S.base)returnERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusDestoryStack(SqStack&S){free(S.base);returnOK;}StatusClearStack(SqStack&S){S.top=S.base;returnOK;}StatusStackEmpty(SqStackS){if(S.base==S.top)returnOK;returnERROR;}intStackLength(SqStackS){returnS.top-S.base;}StatusGetTop(SqStackS,ElemType&e){if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(！S.base)returnERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}StatusPush(SqStack&S,ElemTypee){if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(！S.base)returnERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}StatusPop(SqStack&S,ElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}StatusStackTraverse(SqStackS){ElemType*p;p=(ElemType*)malloc(sizeof(ElemType));if(！p)returnERROR;p=S.top;while(p！=S.base)//S.top上面一個。{p--;printf("%d",*p);}returnOK;}StatusCompare(SqStack&S){intflag,TURE=OK,FALSE=ERROR;ElemTypee,x;InitStack(S);flag=OK;printf("請輸入要進棧或出棧的元素：");while((x=getchar)！=#&&flag){switch(x){case(:case[:case{:if(Push(S,x)==OK)printf("括號匹配成功！\n\n");break;case):if(Pop(S,e)==ERROR||e！=(){printf("沒有滿足條件\n");flag=FALSE;}break;case]:if(Pop(S,e)==ERROR||e！=[)flag=FALSE;break;case}:if(Pop(S,e)==ERROR||e！={)flag=FALSE;break;}}if(flag&&x==#&&StackEmpty(S))returnOK;elsereturnERROR;}鏈隊列：StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(！Q.front)returnERROR;Q.front->next=NULL;returnOK;}StatusDestoryQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}StatusQueueEmpty(LinkQueue&Q){if(Q.front->next==NULL)returnOK;returnERROR;}StatusQueueLength(LinkQueueQ){inti=0;QueuePtrp,q;p=Q.front;while(p->next){i++;p=Q.front;q=p->next;p=q;}returni;}StatusGetHead(LinkQueueQ,ElemType&e){QueuePtrp;p=Q.front->next;if(！p)returnERROR;e=p->data;returne;}StatusClearQueue(LinkQueue&Q){QueuePtrp;while(Q.front->next){p=Q.front->next;free(Q.front);Q.front=p;}Q.front->next=NULL;Q.rear->next=NULL;returnOK;}StatusEnQueue(LinkQueue&Q,ElemTypee){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(！p)returnERROR;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;//p->next為空returnOK;}StatusDeQueue(LinkQueue&Q,ElemType&e)北郵數(shù)據(jù)結構實驗報告「篇三」《數(shù)據(jù)結構與算法》實驗報告專業(yè)班級姓名學號實驗項目實驗一二叉樹的應用實驗目的1、進一步掌握指針變量的含義及應用。2、掌握二叉樹的結構特征，以及各種存儲結構的特點及使用范圍。3、掌握用指針類型描述、訪問和處理二叉樹的運算。實驗內(nèi)容題目1:編寫一個程序，采用一棵二叉樹表示一個家譜關系。要求程序具有如下功能：（1）用括號表示法輸出家譜二叉樹。（2）查找某人的所有兒子。（3）查找某人的所有祖先。算法設計分析（一）數(shù)據(jù)結構的定義為了能夠用二叉樹表示配偶、子女、兄弟三種關系，特采用以下存儲關系，則能在二叉樹上實現(xiàn)家譜的各項運算。二叉樹型存儲結構定義為：typedefstructSNODE{charname[MAX];//人名structSNODE*left;//指向配偶結點structSNODE*right;//指向兄弟或子女結點}FNODE;（二）總體設計實驗由主函數(shù)、家譜建立函數(shù)、家譜輸出函數(shù)、兒子查找函數(shù)、祖先查找函數(shù)、結點定位函數(shù)、選擇界面函數(shù)七個函數(shù)共同組成。其功能描述如下：（1）主函數(shù)：統(tǒng)籌調(diào)用各個函數(shù)以實現(xiàn)相應功能voidmain（2）家譜建立函數(shù)：與用戶交互建立家族成員對應關系voidInitialFamily(FNODE*&head)//家譜建立函數(shù)（3）家譜輸出函數(shù)：用括號表示法輸出家譜輸出形式為：父和母（子1和子妻1（孫1），子2和子妻2（孫2））voidPrintFamily(FNODE*head)//家譜輸出函數(shù)（4）兒子查找函數(shù)：在家譜中查找到某人所有的子女并輸出，同時也能辨別出其是否為家族成員與是否有子女voidFindSon(FNODE*b,charp[])//兒子查找函數(shù)（5）祖先查找函數(shù)：在家譜中查找到某人所有的祖先并輸出，同時也能辨別出其是否為家族中成員。intFindAncestor(FNODE*head,charson[])//祖先查找函數(shù)（6）結點定位函數(shù)：在家譜中找到用戶輸入人名所對應的結點。FNODE*findnode(FNODE*b,charp[])//結點定位函數(shù)（7）選擇界面函數(shù)：為便于編寫程序，將用戶選擇部分獨立為此函數(shù)。voidPRINT(int&n)（三）各函數(shù)的詳細設計：voidInitialFamily(FNODE*&head)//家譜建立函數(shù)1：首先建立當前人的信息，將其左右結點置為空。2：然后讓用戶確定其是否有配偶，如果沒有配偶，則當前程序結束。3：如果有則建立其配偶信息，并將配偶結點賦給當前人的左結點；4：再讓用戶確定其是否有子女，如果有則遞歸調(diào)用家譜建立函數(shù)建立子女結點，并將其賦給配偶結點的下一個右結點。5：如無，則程序結束voidPrintFamily(FNODE*head)//家譜輸出函數(shù)1：首先判斷當前結點是否為空，如果為空則結束程序；2：如果不為空，則輸出當前結點信息。3：然后判斷其左結點（配偶結點）是否為空，如不為空則輸出“和配偶信息。4：再判斷配偶結點的右結點是否為空，如不為空則遞歸調(diào)用輸出其子女信息，最后輸出“）”；5：當配偶結點為空時，則判斷其右結點（兄弟結點）是否為空6：如果不為空，則輸出“，”，并遞歸調(diào)用輸出兄弟信息7程序結束FNODE*findnode(FNODE*b,charp[])//結點定位函數(shù)1：當前結點是否為空，為空則返回空；2：如果和查找信息相同，則返回當前結點；3：如不然，則先后遞歸訪問其左結點，再不是則遞歸訪問右結點voidFindSon(FNODE*b,charp[])//兒子查找函數(shù)1：在家譜中定位到要查找的結點，如無則輸出“查找不到此人”。2：判斷其配偶結點與子女結點是否為空，為空則輸出“無子女”。3：不為空則輸出其配偶結點的所有右結點（子女結點）。intFindAncestor(FNODE*head,charson[])//祖先查找函數(shù)1：先在家譜中定位到要查找的結點，如為空輸出“不存在此人”，程序結束2：先將父母結點入棧，當棧為空時程序結束。3：棧不為空時，判斷棧頂元素是否已訪問過。4：訪問過，再判斷是否為查找結點，如是則輸出棧中保存的其祖先結點，并濾過其兄弟結點不輸出；不是查找結點，則退棧一個元素5：未訪問過，則取當前棧頂元素，置訪問標志――1，同時取其右結點6：棧不為空或當前所取結點不為空時，轉到2；實驗測試結果及結果分析（一）測試結果（二）結果分析（略）實驗總結（略）北郵數(shù)據(jù)結構實驗報告「篇四」北郵數(shù)據(jù)結構實驗報告線性表實驗報告;課程名稱：數(shù)據(jù)結構班級：軟件工程實驗成績;1206;實驗名稱：打印機隊列模擬學號：20124848批;程序的設計;實驗編號：實驗一姓名：實驗日期：2014年5月2;一、實驗目的;對隊列的理解;對STL中的queue的使用;實驗仿真一個網(wǎng)絡打印過程;二、實驗內(nèi)容與實驗步驟流程圖;這個任務隊列的測試使用STL隊列適配器;具體地說,每一行中包含的信息是實驗報告課程名稱：數(shù)據(jù)結構班級：軟件工程實驗成績：1206實驗名稱：打印機隊列模擬學號：20124848批閱教師簽字：程序的設計實驗編號：實驗一姓名：實驗日期：2014年5月24日一、實驗目的對隊列的理解對STL中的queue的使用實驗仿真一個網(wǎng)絡打印過程二、實驗內(nèi)容與實驗步驟流程圖這個任務隊列的測試使用STL隊列適配器。程序要求完成模擬的實現(xiàn)共享打印機。這個打印機使用先進先出隊列。仿真是通過讀取和處理事件數(shù)據(jù)文件的列表。一個有效的數(shù)據(jù)文件中的每一行包含信息打印作業(yè)和提交這份工作的時間。具體地說,每一行中包含的信息是提交工作的時間(以秒為單位),和在頁面的工作長及工作的計算機的名稱。在模擬的開始,每個這些事件的每一個應該被程序所讀，存儲在繼承工作負載隊列。程序應該通過循環(huán)遞增計數(shù)器或while-loop模擬時間的流逝。程序應該將計數(shù)器初始化為零,然后依次增加1秒。當模擬等于當前時間的打印作業(yè)的提交時間在工作隊列的前面，一個打印作業(yè)完成。當這一切發(fā)生的時候,從工作隊列取出這個事件,然后把它放在另一個隊列對象。這個隊列對象存儲已完成的打印作業(yè)。當程序仿真其他的打印工作的時候，這些工作在隊列等待。Win8，VisualC++6.0四、實驗過程與分析(1)實驗主要函數(shù)及存儲結構main.cpp包括主函數(shù)和主要的功能simulator.h仿真類的聲明simulator.cpp仿真類的定義event.h事件類的聲明event.cpp-事件類的定義job.h作業(yè)類的聲明job.cpp作業(yè)類的定義arbitrary.run包括任意打印作業(yè)數(shù)的數(shù)據(jù)文件arbitrary.out輸出arbitrary.runbigfirst.run包括打印較大作業(yè)的數(shù)據(jù)文件bigfirst.out輸出bigfirst.run(2)實驗代碼#ifndefFIFO_H//fifo.h#defineFIFO_H#include"simulator.h"classfifo:publicsimulator{protected:queuewaiting;priority_queuepriority_waiting;public:fifo(intseconds_per_page);voidsimulate(stringfile);};booloperator<(eventevtleft,eventevtright);#endif#include"fifo.h"http://fifo.cpp#includeusingnamespacestd;fifo:fifo(intseconds_per_page):simulator(seconds_per_page){}voidfifo:simulate(stringfile){intfinish_time=0;floatagg_latency=0;inttotaljob=0;eventevt;if(file.find("arbitrary")！=string:npos){stringoutfile="arbitrary.out";ofstreamosf(outfile.c_str);loadworkload(file);osf<<"FIFOSimulation"<for(inttime=1！waiting.empty||！workload.emptytime++){while(！workload.empty&&time==workload.frontarrival_time){evt=workload.frontosf<<"Arriving:"<workload.pop}if(！waiting.empty&&time>=finish_time){totaljob++;evt=waiting.frontagg_latency+=time-evt.arrival_timeosf<<"Servicing:"<finish_time=time+evt.getjobgetnumpages*seconds_per_page;}}osf<<"totaljob"<osf<<"aggregatelatency:"<osf<<"meanlatency:"<return;}if(file.find("bigfirst")！=string:npos){stringoutfile="bigfirst.out";ofstreamosf(outfile.c_str);loadworkload(file);osf<<"FIFOSimulation"<for(inttime=1！priority_waiting.empty||！workload.emptytime++){while(！workload.empty&&time==workload.frontarrival_time){evt=workload.frontosf<<"Arriving:"<workload.pop}if(！priority_waiting.empty&&time>=finish_time){totaljob++;evt=priority_waiting.topagg_latency+=time-evt.arrival_timeosf<<"Servicing:"<finish_time=time+evt.getjobgetnumpages*seconds_per_page;}}osf<<"totaljob"<osf<<"aggregatelatency:"<osf<<"meanlatency:"<return;}cerr<<"Theprogramdontknowwhatalgorithmtouse"<cerr<<"Youshouldspecifythefilenamewitharbitraryorbigfirst"<booloperator<(eventevtleft,eventevtright){returnevtleft.getjobgetnumpages<evtright.getjobgetnumpages}五、實驗結果總結經(jīng)測試，功能較為完整。代碼流程簡圖如下：通過這次實驗，我了解了有關隊列方面的知識。掌握了隊列的邏輯結構，抽象數(shù)據(jù)類型，隊列的存儲方式等。運用先進先出表，仿真了網(wǎng)絡打印隊列。這都使我對數(shù)據(jù)結構的學習有了新的認識與幫助。在實驗過程中，我也遇到了許多困難，從開始時對隊列運算的不熟悉，到逐漸查找資料，從而完成了實驗;六、附錄;-《數(shù)據(jù)結構與算法分析》以及網(wǎng)上資料;逐漸查找資料，從而完成了實驗。在今后的學習中，我將繼續(xù)努力，加強對堆棧，隊列等知識的學習，以達到精益求精。六、附錄-《數(shù)據(jù)結構與算法分析》以及網(wǎng)上資料1.北郵數(shù)據(jù)結構實驗報告線性表2.北郵數(shù)據(jù)結構實驗報告圖北郵數(shù)據(jù)結構實驗報告「篇五」一實驗內(nèi)容：實現(xiàn)哈夫曼編碼的生成算法。二實驗目的：1、使學生熟練掌握哈夫曼樹的生成算法。2、熟練掌握哈夫曼編碼的方法。三問題描述：已知n個字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼。1、讀入n個字符，以及字符的權值，試建立一棵Huffman樹。2、根據(jù)生成的Huffman樹，求每個字符的Huffman編碼。并對給定的待編碼字符序列進行編碼，并輸出。四問題的實現(xiàn)(1)郝夫曼樹的存儲表示typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲郝夫曼樹郝夫曼編碼的存儲表示typedefchar**HuffmanCode;//動態(tài)分配數(shù)組存儲郝夫曼編碼(2)主要的實現(xiàn)思路：a.首先定義郝夫曼樹的存儲形式，這里使用了數(shù)組b.用select遍歷n個字符，找出權值最小的兩個c.構造郝夫曼樹HT，并求出n個字符的郝夫曼編碼HC總結1.基本上沒有什么太大的問題，在調(diào)用select這個函數(shù)時，想把權值最小的兩個結點的序號帶回HuffmanCoding，所以把那2個序號設置成了引用。2.在編程過程中，在什么時候分配內(nèi)存，什么時候初始化花的時間比較長3.最后基本上實現(xiàn)后，發(fā)現(xiàn)結果仍然存在問題，經(jīng)過分步調(diào)試，發(fā)現(xiàn)了特別低級的輸入錯誤。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2寫成了i附：//動態(tài)分配數(shù)組存儲郝夫曼樹typedefstruct{intweight;//字符的權值intparent,lchild,rchild;}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲郝夫曼編碼typedefchar**HuffmanCode;//選擇n個(這里是k=n)節(jié)點中權值最小的兩個結點voidSelect(HuffmanTree&HT,intk,int&s1,int&s2){inti;i=1;while(i<=k&&HT[i].parent！=0)i++;//下面選出權值最小的結點，用s1指向其序號s1=i;for(i=1;i<=k;i++){if(HT[i].parent==0&&HT[i].weight}//下面選出權值次小的結點，用s2指向其序號for(i=1;i<=k;i++){if(HT[i].parent==0&&i！=s1)break;}s2=i;for(i=1;i<=k;i++){if(HT[i].parent==0&&i！=s1&&HT[i].weight}}//構造Huffman樹，求出n個字符的編碼voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){intm,c,f,s1,s2,i,start;char*cd;if(n<=1)return;m=2*n-1;//n個葉子n-1個結點HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號單元未用，預分配m+1個單元HuffmanTreep=HT+1;w++;//w的號單元也沒有值，所以從號單元開始for(i=1;i<=n;i++,p++,w++){p->weight=*w;p->parent=p->rchild=p->lchild=0;}for(;i<=m;++i,++p){p->weight=p->parent=p->rchild=p->lchild=0;}for(i=n+1;i<=m;i++){Select(HT,i-1,s1,s2);//選出當前權值最小的HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}//從葉子到根逆向求每個字符的郝夫曼編碼HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n個字符編碼的頭指針變量cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間cd[n-1]=//編碼結束符for(i=1;i<=n;i++)//逐個字符求郝夫曼編碼{start=n-1;//編碼結束符位置for(c=i,f=HT[i].parent;f！=0;c=f,f=HT[f].parent)//從葉子到根逆向求編碼{if(HT[f].lchild==c)cd[--start]=0elsecd[--start]=1}HC[i]=(char*)malloc((n-start)*sizeof(char));//為第i個字符編碼分配空間strcpy(HC[i],&cd[start]);//從cd復制編碼到HC}free(cd);//釋放工作空間}voidmain{intn,i;int*w;//記錄權值char*ch;//記錄字符HuffmanTreeHT;HuffmanCodeHC;cout<<"請輸入待編碼的字符個數(shù)n=";cin>>n;w=(int*)malloc((n+1)*sizeof(int));//記錄權值，號單元未用ch=(char*)malloc((n+1)*sizeof(char));//記錄字符，號單元未用cout<<"依次輸入待編碼的字符data及其權值weight"<for(i=1;i<=n;i++){cout<<"data["<}北郵數(shù)據(jù)結構實驗報告「篇六」北郵數(shù)據(jù)結構實驗報告北京郵電大學信息與通信工程學院2009級數(shù)據(jù)結構實驗報告實驗名稱：實驗三哈夫曼編/解碼器的實現(xiàn)學生姓名：陳聰捷日期：2010年11月28日1.實驗要求一、實驗目的：了解哈夫曼樹的思想和相關概念;二、實驗內(nèi)容：利用二叉樹結構實現(xiàn)哈夫曼編/解碼器1.初始化：能夠?qū)斎氲娜我忾L度的字符串s進行統(tǒng)計，統(tǒng)計每個字符的頻度，并建立哈夫曼樹。2.建立編碼表：利用已經(jīng)建好的哈夫曼樹進行編碼，并將每個字符的編碼輸出。3.編碼：根據(jù)編碼表對輸入的字符串進行編碼，并將編碼后的字符串輸出。4.譯碼：利用已經(jīng)建好的哈夫曼樹對編碼后的字符串進行譯碼，并輸出譯碼結果。5.打?。阂灾庇^的方式打印哈夫曼樹。6.計算輸入的字符串編碼前和編碼后的長度，并進行分析，討論哈夫曼編碼的壓縮效果。7.用戶界面可以設計成“菜單”方式，能進行交互，根據(jù)輸入的字符串中每個字符出現(xiàn)的次數(shù)統(tǒng)計頻度，對沒有出現(xiàn)的字符一律不用編碼。2.程序分析2.1存儲結構二叉樹templateclassBiTree{public:BiTree//構造函數(shù)，其前序序列由鍵盤輸入~BiTree(void);//析構函數(shù)BiNode*Getroot//獲得指向根結點的指針protected:BiNode*root;//指向根結點的頭指針};//聲明類BiTree及定義結構BiNodeData：二叉樹是由一個根結點和兩棵互不相交的左右子樹構成哈夫曼樹類的數(shù)據(jù)域，繼承節(jié)點類型為int的二叉樹classHuffmanTree:publicBiTreedata:HCode*HCodeTable;//編碼表inttSize;//編碼表中的總字符數(shù)二叉樹的節(jié)點結構templatestructBiNode//二叉樹的結點結構{Tdata;//記錄數(shù)據(jù)Tlchild;//左孩子Trchild;//右孩子Tparent;//雙親};編碼表的節(jié)點結構structHCode{chardata;//編碼表中的字符charcode[100];//該字符對應的編碼};待編碼字符串由鍵盤輸入，輸入時用鏈表存儲，鏈表節(jié)點為structNode{charcharacter;//輸入的字符unsignedintcount;//該字符的權值boolused;//建立樹的時候該字符是否使用過Node*next;//保存下一個節(jié)點的地址};示意圖：2.2關鍵算法分析1.初始化函數(shù)(voidHuffmanTree:Init(stringInput))算法偽代碼：1.初始化鏈表的頭結點2.獲得輸入字符串的第一個字符，并將其插入到鏈表尾部,n=1(n記錄的是鏈表中字符的個數(shù))3.從字符串第2個字符開始，逐個取出字符串中的字符3.1將當前取出的字符與鏈表中已經(jīng)存在的字符逐個比較，如果當前取出的字符與鏈表中已經(jīng)存在的某個字符相同，則鏈表中該字符的權值加1。3.2如果當前取出的字符與鏈表中已經(jīng)存在的字符都不相同，則將其加入到鏈表尾部，同時n++4.tSize=n(tSize記錄鏈表中字符總數(shù)，即哈夫曼樹中葉子節(jié)點總數(shù))5.創(chuàng)建哈夫曼樹6.銷毀鏈表源代碼：voidHuffmanTree:Init(stringInput){Node*front=newNode;//初始化鏈表的頭結點if(！front)throwexception("堆空間用盡");front->next=NULL;front->character=NULL;front->count=0;Node*pfront=front;charch=Input[0];//獲得第一個字符Node*New1=newNode;if(！New1)throwexception("堆空間用盡");New1->character=ch;//將第一個字符插入鏈表New1->count=1;New1->next=pfront->next;pfront->next=New1;boolreplace=0;//判斷在已經(jīng)寫入鏈表的字符中是否有與當前讀出的字符相同的字符intn=1;//統(tǒng)計鏈表中字符個數(shù)for(inti=1;i{ch=Input[i];//獲得第i個字符do{pfront=pfront->next;if((int)pfront->character==(int)ch)//如果在鏈表中有與當前字符相同的字符，該字符權值加1{pfront->count++;replace=1;break;}}while(pfront->next);if(！replace)//如果在鏈表中沒找到與當前字符相同的字符，則將該字符作為新成員插入鏈表{Node*New=newNode;if(！New)throwexception("堆空間用盡");New->character=ch;New->count=1;New->next=pfront->next;pfront->next=New;n++;}pfront=front;//重置pfront和replace變量為默認值replace=0;}tSize=n;//tSize記錄的是編碼表中字符個數(shù)CreateHTree(front,n);//創(chuàng)建哈夫曼樹pfront=front;while(pfront)//銷毀整個鏈表{front=pfront;pfront=pfront->next;front;}時間復雜度：若輸入的字符串長度為n，則時間復雜度為O(n)2.創(chuàng)建哈夫曼樹(voidHuffmanTree:CreateCodeTable(Node*p))算法偽代碼：1.創(chuàng)建一個長度為2*tSize-1的三叉鏈表2.將存儲字符及其權值的鏈表中的字符逐個寫入三叉鏈表的前tSize個結點的data域，并將對應結點的孩子域和雙親域賦為空3.從三叉鏈表的第tSize個結點開始，i=tSize3.1從存儲字符及其權值的鏈表中取出兩個權值最小的結點x,y，記錄其下標x,y。3.2將下標為x和y的哈夫曼樹的結點的雙親設置為第i個結點3.3將下標為x的結點設置為i結點的左孩子，將下標為y的結點設置為i結點的右孩子，i結點的權值為x結點的權值加上y結點的權值，i結點的雙親設置為空4.根據(jù)哈夫曼樹創(chuàng)建編碼表源代碼：voidHuffmanTree:CreateHTree(Node*p,intn){root=newBiNode[2*n-1];//初始化哈夫曼樹Node*front=p->next;if(n==0)throwexception("沒有輸入字符");for(inti=0;iroot[i].data=front->count;root[i].lchild=-1;root[i].rchild=-1;root[i].parent=-1;front=front->next;}front=p;intNew1,New2;for(i=n;i<2*n-1;i++){SelectMin(New1,New2,0,i);//從0~i中選出兩個權值最小的結點root[New1].parent=root[New2].parent=i;//用兩個權值最小的結點生成新結點，新節(jié)點為其雙親root[i].data=root[New1].data+root[New2].data;//新結點的權值為其孩子的權值的和root[i].lchild=New1;root[i].rchild=New2;root[i].parent=-1;}CreateCodeTable(p);//創(chuàng)建編碼表}時間復雜度：在選取兩個權值最小的結點的函數(shù)中要遍歷鏈表，時間復雜度為O(n),故該函數(shù)的時間復雜度為O(n^2)3.創(chuàng)建編碼表(voidHuffmanTree:CreateCodeTable(Node*p))算法偽代碼：1.初始化編碼表2.初始化一個指針，從鏈表的頭結點開始，遍歷整個鏈表2.1將鏈表中指針當前所指的結點包含的字符寫入編碼表中2.2得到該結點對應的哈夫曼樹的葉子結點及其雙親2.3如果哈夫曼樹只有一個葉子結點，將其字符對應編碼設置為02.4如果不止一個葉子結點，從當前葉子結點開始判斷2.4.1如果當前葉子結點是其雙親的左孩子，則其對應的編碼為0，否則為12.4.2child指針指向葉子結點的雙親，parent指針指向child指針的雙親，重復2.4.1的操作2.5將已完成的編碼倒序2.6取得鏈表中的下一個字符3.輸出編碼表源代碼：voidHuffmanTree:CreateCodeTable(Node*p){HCodeTable=newHCode[tSize];//初始化編碼表Node*front=p->next;for(inti=0;i{HCodeTable[i].data=front->character;//將第i個字符寫入編碼表intchild=i;//得到第i個字符對應的葉子節(jié)點intparent=root[i].parent;//得到第i個字符對應的葉子節(jié)點的雙親intk=0;if(tSize==1)//如果文本中只有一種字符，它的編碼為0{HCodeTable[i].code[k]=0k++;}while(parent！=-1)//從第i個字符對應的葉子節(jié)點開始，尋找它到根結點的路徑{if(child==root[parent].lchild)//如果當前結點為雙親的左孩子，則編碼為0，否則編碼為1HCodeTable[i].code[k]=0elseHCodeTable[i].code[k]=1k++;child=parent;parent=root[child].parent;}HCodeTable[i].code[k]=Reverse(HCodeTable[i].code);//將編碼逆置front=front->next;//得到下一個字符}cout<<"編碼表為："<for(i=0;i{cout<parent=root[parent].lchild;else//編碼為1則尋找右孩子parent=root[parent].rchild;i++;}if(tSize==1)//如果編碼表只有一個字符，則根結點即為葉子結點i++;d.append(1,HCodeTable[parent].data);//將葉子節(jié)點對應的字符追加到解碼串中}cout<}時間復雜度：設待解碼串長度為n，則復雜度為O(n)8.計算哈夫曼編碼的壓縮比(voidHuffmanTree:Calculate(strings1,strings2))算法偽代碼：1.獲得編碼前字符串的長度，即其占用的字節(jié)數(shù)2.獲得編碼后的字符串的長度，將其除以8然后向上取整，得到其占用的字節(jié)數(shù)3.壓縮比將兩個相除源代碼：voidHuffmanTree:Calculate(strings1,strings2){intcal1=s1.lengthintcal2=s2.lengthcal2=ceill((float)cal2/8);//將編碼串的比特數(shù)轉化為字節(jié)數(shù)cout<<"編碼前的字符串長度："<cout<<"編碼后的字符串長度："<cout<<"壓縮比為："<<((double)cal2/(double)cal1)*100<<"%"<}時間復雜度：O(1)9.打印哈夫曼樹(voidHuffmanTree:PrintTree(intTreeNode,intlayer))算法偽代碼：1.如果待打印結點為空，則返回2.遞歸調(diào)用函數(shù)打印當前結點的右子樹3.根據(jù)當前結點所在的層次確定其前面要輸出多少空格，先輸出空格，在打印當前結點的權值4.遞歸調(diào)用函數(shù)打印當前結點的左子樹源代碼：voidHuffmanTree:PrintTree(intTreeNode,intlayer){if(TreeNode==-1)//如果待打印結點為空，則返回return;else{PrintTree(root[TreeNode].rchild,layer+1);//先打印該結點的右子樹，layer記錄的是該結點所在的層次for(inti=0;i空格cout<<cout<PrintTree(root[TreeNode].lchild,layer+1);//打印該結點的左子樹}}時間復雜度：中序遍歷哈夫曼樹，復雜度為O(n)10.菜單函數(shù)(voidHuffmanTree:Menu)算法偽代碼：1.逐一讀取鍵盤緩存區(qū)中的字符，并將它們逐一追加到記錄輸入字符串的string變量中，直到讀到回車輸入符為止2.刪除string變量末尾的回車輸入符3.利用string變量創(chuàng)建哈夫曼樹，初始化編碼表。4.直觀打印哈夫曼樹5.對輸入的字符串進行編碼6.對編碼后的字符串進行解碼7.計算編碼前后的壓縮比并輸出源代碼：voidHuffmanTree:Menu{cout<<"請輸入你要編碼的文本,按回車鍵確定輸入"<stringInput;charletter;do//將字符逐個讀入Input變量中{letter=cin.getInput.append(1,letter);}while(letter！=);Input.erase(Input.length-1,1);//去掉Input末尾的回車符Init(Input);//根據(jù)輸入的字符串創(chuàng)建哈夫曼樹及其編碼表cout<<"直觀打印哈夫曼樹"<PrintTree(2*tSize-1-1,1);//打印哈夫曼樹cout<<<<stringd1,d2;cout<<"編碼后的字符串為"<Encode(Input,d1);//編碼并打印編碼串cout<<"解碼后的字符串為"<Decode(d1,d2);//解碼并打印解碼串cout<<"ASCII碼編碼與HUFFMAN編碼的比較"<Calculate(Input,d1);//計算編碼前后的壓縮比}2.3其他1.由于題目要求能輸入任意長的字符串，所以本程序采用了string變量來記錄輸入的字符串，并采用string類的類成員函數(shù)來完成各項任務2.打印哈夫曼樹時采用了遞歸函數(shù)，且采用了凹凸表的形式打印哈夫曼樹。3.為了輸入空格，輸入時采取逐個字符輸入的方式3.程序運行結果主函數(shù)流程圖：運行結果：各函數(shù)運行正常，沒有出現(xiàn)bug4.總結經(jīng)過這次實驗，我了解了哈夫曼樹的創(chuàng)建過程，了解了一種不等長編碼的方法，用設斷點調(diào)試的方法更加熟練，同時熟悉了STL中string類型的用法，對C++更加熟悉北郵數(shù)據(jù)結構實驗報告「篇七」c數(shù)據(jù)結構實驗報告數(shù)據(jù)結構(C語言版)實驗報告;專業(yè)：計算機科學與技術、軟件工程;學號:____201240703061_____;班級:_________軟件二班________;姓名:________朱海霞__________;指導教師:___劉遵仁_____________;青島大學信息工程學院;2013年10月;實驗1;實驗題目：順序存儲結構線性表的插入和刪除;實驗目數(shù)據(jù)結構(C語言版)實驗報告專業(yè)：計算機科學與技術、軟件工程學號:____201240703061___________________班級:_________軟件二班______________姓名:________朱海霞______________指導教師:___劉遵仁________________青島大學信息工程學院2013年10月實驗1實驗題目：順序存儲結構線性表的插入和刪除實驗目的：了解和掌握線性表的邏輯結構和順序存儲結構，掌握線性表的基本算法及相關的時間性能分析。實驗要求：建立一個數(shù)據(jù)域定義為整數(shù)類型的線性表，在表中允許有重復的數(shù)據(jù);根據(jù)輸入的數(shù)據(jù)，先找到相應的存儲單元，后刪除之。實驗主要步驟：1、分析、理解給出的示例程序。2、調(diào)試程序，并設計輸入一組數(shù)據(jù)(3，-5，6，8，2，-5，4，7，-9)，測試程序的如下功能：根據(jù)輸入的數(shù)據(jù)，找到相應的存儲單元并刪除，顯示表中所有的數(shù)據(jù)。程序代碼:#include#include#defineOK1#defineERROR0#defineOVERFLOW-2#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{int*elem;intlength;intlistsize;}Sqlist;intInitList_Sq(Sqlist&L){L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(！L.elem)return-1;L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}intListInsert_Sq(Sqlist&L,inti,inte){if(i<1||i>L.length+1)returnERROR;if(L.length==L.listsize){int*newbase;newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(！newbase)return-1;L.elem=newbase;L.listsize+=LISTINCREMENT;}int*p,*q;q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}intListDelete_Sq(Sqlist&L,inti,inte){int*p,*q;if(i<1||i>L.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;}intmain{SqlistL;InitList_Sq(L);//初始化inti,a[]={3,-5,6,8,2,-5,4,7,-9};for(i=1;i<10;i++)ListInsert_Sq(L,i,a[i-1]);for(i=0;i<9;i++)printf("%d",L.elem[i]);printf("");//插入9個數(shù)ListInsert_Sq(L,3,24);for(i=0;i<10;i++)printf("%d",L.elem[i]);printf("");//插入一個數(shù)inte;ListDelete_Sq(L,2,e);for(i=0;i<9;i++)printf("%d",L.elem[i]);//刪除一個數(shù)printf("");return0;}實驗結果：3、-5,6,8,2，-5,4,7，-93、