第一篇：南航計算機軟件數據結構上機實踐報告
數據結構實踐報告整理 031040102 劉玉 ? 簡述每一部分的對象、目的和要求；
? 畫出程序流程圖；另附A4紙手繪； ? 附源程序清單； ? 實驗的收獲：遇到的問題以及解決的辦法、方法的優缺點。
實驗一 單鏈表的基本操作與運算
題目一：單鏈表的定義、創建、插入和刪除操作，將數據元素顯示出來。
本題目針對單鏈表。聯表示通過一組任意的存儲單元來存儲線性表格中的數據元素。為了建立起數據元素之間的存儲關系，設置每一個結點，結點既存放數據data，又存放其后繼地址的部分next。而每個結點中只有一個指向后繼的指針，所以稱其為單鏈表。本題目的要求是創建一個新的鏈表，并且完成鏈表的創建定義。鏈表是一種動態管理的存儲結構，鏈表中的每一個結點所占用的空間是根據運行是的實際需要的空間生成的。因此建立單鏈表是從空鏈表開始的，每次讀入一個數據元素就申請一個結點鏈表的一段。在單鏈表中插入一個結點不需要移動元素指針的指向。而刪除則需要找到木比啊偶元素的前驅結點，并且修改指針的指向。題目一需要的操作就是，對于一個新建的空鏈表，以其為對象進行具體的數據的插入填寫。待鏈表中存有數據后，再進行數據的整理查找，然后刪除目標數據。
//031040102單鏈表 #include
//定義一個鏈表 { int data;SLNODE *next;};void CREATE_SL(SLNODE *h)//創建一個單鏈表 { SLNODE *p,*s;int x;h->next=NULL;
cout<<“輸入以-1結尾的一組數”< cin>>x; //開始輸入數據 while(x!=-1) { s=new SLNODE[sizeof(SLNODE)]; //申請一個動態新空間 s->data=x; if(h->next==NULL) h->next=s; else p->next=s; p=s; cin>>x; } p->next=NULL; //鏈表最后指向空 };int Insert_LinkList(SLNODE *h,int i,int x) //在單鏈表第i個位置插入x { SLNODE *p,*s;int j=0; p=h;while(p->next!=NULL&&j { p=p->next; j++; } if(j!=i-1){ cout<<“i is invalid!”< return 0;} else { s=new SLNODE[sizeof(SLNODE)]; s->data=x; s->next=p->next; p->next=s; return 1; } };int Del_LinkList(SLNODE *h,int i) //刪除單鏈表上第i個結點 { SLNODE *p,*s;int j=0;p=h;while(p->next!=NULL&&j p=p->next;j++; } if(j!=i-1){ cout<<“i is invalid!”< return 0;4 6 8 9 7 2 6 9 7 5-1 } 鏈表數據如下 else 4 6 8 9 7 2 6 9 7 5 { 輸入需插入的數據8 if(p->next==NULL)輸入需插入的結點3 { 插入成功 cout<<“第i個結點不存在鏈表數據如下 ”< return 0;輸入需刪除的結點 4 } 刪除成功 else 鏈表數據如下 {s=p->next;p->next=s->next; 7 2 6 9 7 */ //刪除結點 Deletes; //釋放結點空間 return 1; } } };void Print_LinkList(SLNODE *h)//輸出鏈表中所有元素 { SLNODE *p;p=h->next;cout<<“鏈表數據如下”< cout< data<<'t';} cout< data< cout<<“插入成功”< cout<<“插入失敗”< cout<<“刪除成功”< cout<<“刪除失敗”< 實驗一的收獲 實驗一讓我對于鏈表的創建于定義有了更多的接觸與認識。之前的學習經驗里主要是 扎實，VC++，涉及鏈表的內容，我學的不夠所以這次在軟件基礎時間里重新再次 學習。題目一比較簡單，設僅是創建和插入以及刪除的基本操作。實驗一的困難較小，我也是比較順利參照課本，完成體題目一，也讓我對于進一步學習鏈表有了興趣和動力。由淺入深，我會一點點開展學習。在圖書館借閱一本《數據結構教程上機實驗指 導》，里面對于實驗的指導比較全面而且有很多實例可以參考。 上機實踐二 題目二：棧、隊列的順序存儲結構、鏈式存儲結構的定義、創建、插入和刪除操作，將數據元素顯示出來。本題目要求掌握棧和列隊。棧和列隊是 兩種常見的數據結構。它們的邏輯結構和線性表相同。其特點是，插入和刪除等運算的位置有所限制：棧是按照先進后出的規則進行操作，而是按照先進先出的規則進行操作。堆棧技術現在的應用非常廣泛，不管是編譯軟件還是程序設計，在操作系統和事務管理中則是廣泛應用了隊列技術。棧是限制在一段進行插入和刪除的線性表，允許插入刪除的這一端稱為棧頂，固定端稱為棧底。棧是運算受到限制的一種線 性表，采用順序存儲的是順序棧，采用鏈式存儲的是鏈棧。題目要求對于兩種存儲結構 的棧進行定義創建。對于順序棧，首先需要申請共享的一位數組空間。即為先置空棧，然后入棧插入元素（特別要注意棧滿不能插入），刪除出棧（特別要注意?？詹荒艹鰲＃τ阪湕?，采用帶頭指針的單鏈表來實現.隊列操作的順序隊列，插入在表的隊尾一端，刪除在表的另外的隊頭一端。隊的隊頭和隊尾都是活動的，特別地需要設置隊頭和隊尾兩個指針。需要實現置空隊、入隊、出對、以及判別隊列是否為空的運算。對于鏈式隊列，通常是用帶頭結點的單鏈表實現的，并且設置一個隊頭指針（始終指向頭結點）和一個隊尾指針（指向當前的最后一個元素），特別地，當隊列為空時隊頭和隊尾指針均指向頭結點。顯示創建一個帶頭結點的空隊，申請頭尾結點，然后進行如對操作不斷申請新的結點，還需要進行隊列是否為空的判斷操作，隊空則出隊失敗。 //031040102 順序棧 #include return 1;else return 0;};int Push_SeqStack(SqStack *s,ElemType x)//入棧 { if(s->top==MaxSize-1) return 0;else { s->top++; s->data[s->top]=x; return 1; } };int Pop_SeqStack(SqStack *s,ElemType x) //出棧 { if(IsEmpty_SeqStack(s)) return 0;else { x=s->data[s->top]; s->top--; return 1; } }; ElemType Top_SeqStack(SqStack *s) //取出棧頂元素 { if(IsEmpty_SeqStack(s)) return 0; else return(s->data[s->top]); };void Print(SqStack *s) //輸出棧內所有元素 { if(IsEmpty_SeqStack(s)) cout<<“ 此棧為空 ”< cout<<“棧內元素為”< for(int i=s->top;i>-1;i--) cout< } };void main(){ SqStack *s;int x; s=Init_SeqStack();cout<<“ 輸入一組以-1結尾的數”< s->top++; s->data[s->top]=x; cin>>x;} Print(s);cout<<“輸入需插入的數”< cout<<“插入成功”< cout<<“插入失敗”< Print(s); delete p;if(Pop_SeqStack(s,x)) return top; cout<<“刪除成功”< cout<<“刪除失敗”< Print(s);} 輸入一組以-1結尾的數 5 8 9 7 3 6 2 1 8-1 棧內元素為 8 1 2 6 3 7 9 8 5 輸入需插入的數4 插入成功 棧內元素為 4 8 1 2 6 3 7 9 8 5 刪除成功 棧內元素為 8 1 2 6 3 7 9 8 5 //031040102 鏈棧 #include //定義一個鏈棧 { elemtype data;LinkStack *next;};LinkStack *Init_LinkStack()//鏈棧的初始化 { LinkStack *top;top=new LinkStack[sizeof(LinkStack)];top=NULL;return top;};LinkStack *Push_LinkStack(LinkStack *top,elemtype x) //數據入棧 { LinkStack *s;s=new LinkStack[sizeof(LinkStack)];s->data=x;s->next=top;top=s;return top;};LinkStack *Pop_LinkStack(LinkStack *top,elemtype x) //數據出棧 { LinkStack *p;if(top==NULL) return NULL;else { x=top->data; p=top; top=top->next;//輸出棧內所有元素 { LinkStack *p;p=top;if(p==NULL) cout<<“此棧為空”< cout<<“棧內元素為”< for(;p->next!=NULL;p=p->next) cout< data<<'t'; cout< data< s=new LinkStack[sizeof(LinkStack)]; s->data=x; s->next=top; top=s; cin>>x;} Print(top);cout<<“輸入需插入的數”< 輸入需插入的數15 棧內元素為 15 65 23 1 6 3 4 8 9 7 棧內元素為 65 23 1 6 3 4 8 9 7 //031040102 順序隊列 #include typedef struct queue //定義一個順序隊列 { ElemType data[MaxSize];int rear,front;}SeQueue;SeQueue*Init_Queue()//隊列的初始化 { SeQueue *sq;sq=new SeQueue[sizeof(SeQueue)];sq->front=sq->rear=-1;return sq;};int IsEmpty_Queue(SeQueue *sq)//判空隊列 { if(sq->rear==-1) return 1;else return 0;};int In_Queue(SeQueue *sq,ElemType x) //入隊 { if(sq->rear==MaxSize-1) return 0;else { sq->rear++; sq->data[sq->rear]=x; return 1;} };int Out_Queue(SeQueue*sq) //出隊 { if(IsEmpty_Queue(sq)) return 0;else { sq->front++; return(sq->data[sq->front]);} };int Front_Queue(SeQueue *sq)//讀隊頭元素 { if(IsEmpty_Queue(sq)) return 0;else { return(sq->data[sq->front+1]);} };void Print(SeQueue *sq)//輸出隊列所有元素 { if(IsEmpty_Queue(sq)) cout<<“此隊列為空”< cout<<“隊列內元素為”< for(int i=sq->front+1;i<=sq->rear;i++) cout< cout< cin>>x;while(x!=-1){ sq->rear++; sq->data[sq->rear]=x; cin>>x;} Print(sq);cout<<“輸入需插入的數”< cout<<“插入成功”< cout<<“插入失敗”< cout<<“刪除成功”< cout<<“刪除失敗”< //定義鏈隊的結點類型 { ElemType data;QNODE *next;}; typedef struct linkqueue p=q->front->next; //封裝頭尾指針 if(IsEmpty_LQueue(q)){ cout<<“此棧為空”< cout<<“ 隊列內元素為 ”< { for(;p->next!=q->rear->next;p=p->next)LinkQueue *q; cout< data<<'t';QNODE *p; cout< data< } //申請頭尾節點 p=new QNODE[sizeof(QNODE)];//申請鏈隊頭結點 p->next=NULL;q->front=q->rear=p;return q;};void In_LQueue(LinkQueue *q,ElemType x)//入隊操作 { QNODE *p;p=new QNODE[sizeof(QNODE)];//申請新結點 p->data=x;p->next=NULL;q->rear->next=p;q->rear=p;};int IsEmpty_LQueue(LinkQueue *q)//判隊空 { if(q->front==q->rear) return 1;else return 0;};int Out_LQueue(LinkQueue *q,ElemType x)//出隊操作 { QNODE *p;if(IsEmpty_LQueue(q)) return 0;else { p=q->front->next; q->front->next=p->next; x=p->data; delete p; if(q->front->next==NULL) //一個元素時，出隊后隊空還要改隊尾指針 q->rear=q->front; return 1;} };void Print(LinkQueue *q){ QNODE *p;}; void main(){ LinkQueue *q;QNODE *s;int x; q=Init_LQueue();cout<<“輸入一組以-1結尾的數”< { s=new QNODE[sizeof(QNODE)]; s->data=x; s->next=NULL; q->rear->next=s; q->rear=s; cin>>x; } Print(q);cout<<“輸入需插入的數”< cout<<“刪除成功”< else cout<<“刪除失敗”< 隊列內元素為 8 9 4 5 3 2 1 實驗二的收獲 實驗二是全新的知識需要理解。在之前的學習經歷中沒有接觸到棧和隊列。所以這 次是從概念開始學習的。在具體程序的學習應用時候，我對于書上提到的，首先需要的是為棧申請共享空間，有了理解和認識。特別地，在?？盏臅r候有s->top[0]==-1;s->top[1]==Maxsize。再有就是棧滿的時候不可以入棧操作，未滿的入棧操作則是先移動再賦入值。例如語句(兩句的順序不可以顛倒)s->top++;s->data[s->top]=x;由于棧的主要運算是在棧頂插入、刪除。因此我在鏈表的頭部作為棧頂，這樣方便了程序，而且不需要像單鏈表一樣為了運算方便附加一個頭結點。在聯系隊列的相關程序時候，我理解了，列隊單向空間無法利用，即為前面的已經被指針制動過的空間不能釋放也無法利用。除此，隊列的操作里面。有可能出現“隊滿”“隊空”的條件相同，front==rear;需要具體區分。 上機實踐三 題目三：二叉樹的鏈式存儲結構的數據結構定義、創建、先序和后序遍歷，并將結果序列輸出。 二叉樹是有限個元素的集合，該集合或者為空、或者由一個稱為根的元素以及兩個不相交的、被稱為左子樹右子樹的二叉樹組成。二叉樹的臉是存儲結構是指，用鏈表來表示一顆二叉樹，即用鏈表來表示元素的邏輯關系。二叉樹的鏈表存儲的結點有三個域組成，除了數據域外，還有兩個指針域，分別用來指向該節點的左子結點和右子結點的存儲地址。當左子結點或者右子結點不存在的時候，相應的指針值域為空。二叉樹的遍歷是指按照某種順序結構訪問二叉樹的每個結點，使每個結點僅被訪問一次。限定先左后右，只有三種方式即為先序遍歷、中序遍歷、后序遍歷。遍歷其實是一個遞歸的過程，若二叉樹為空，則遍歷結束，不然就按照順序依次訪問根結點、左結點、右結點。 //031040102 二叉樹 #include //定義二叉樹結點 { elemtype data; BiTNode *lchild,*rchild;//兩結點指針 }BiTree; BiTree *Create()//二叉樹的創建,遞歸算法 { BiTree *bt;elemtype ch;cin>>ch;if(ch=='0'){ bt=NULL;} else { bt=new BiTNode[sizeof(BiTNode)]; bt->data=ch; bt->lchild=Create(); bt->rchild=Create();} return bt;}; void PreOrder(BiTree *bt) //先序遍歷二叉樹，遞歸算法 { if(bt==NULL) return;cout< void PostOrder(BiTree *bt) //先序遍歷二叉樹，遞歸算法 { if(bt==NULL) return;PostOrder(bt->lchild);PostOrder(bt->rchild);cout< void main(){ BiTree *bt;cout<<“輸入所需字符（空結點以零代替）”< 輸入所需字符（空結點以零代替）frt0e000qj00m00 先序遍歷可得二叉樹元素為 f r t e q j m 后序遍歷可得二叉樹元素為 e t r j m q f 實驗三的收獲 二叉樹可以用計算機語言來讀取，通過遍歷可以恢復二叉樹。通過這次試驗更加深刻理解二叉樹。本體操作不斷調用函數，遞歸實現遍歷。實際需要的時候對于已知的二叉樹的每個結點逐一訪問。一次完整的便利科室的一個二叉樹的結點信息由非線性排列轉變為意義上的線性排列。在二叉樹的鏈表中無法根據結點找到其父結點。不過，二叉樹的鏈表結構靈巧簡便、操作方便。特別地還節省空間。對于一個龐大的工程型程序的話，空間與簡便十分重要。同樣的目的，同樣的結果，需要比較選擇，肯定是精巧簡單操作性強等等優勢作為判斷取舍。 上機實踐四 題目四：查找：順序查找、二分查找 查找是許多程序中最為耗費時間的部分。因此需要方法提高運行的速度和效率。順序查找又稱為線性查找，也是最為基本的查找方法之一。具體實現為：從表的一端開始，依次將關鍵碼與給定的值比較，若找到查找成功，并且給出數據元素在表中的位置，若整個表查找完成仍未找到相同的關鍵碼，則查找失敗給出失敗信息。 二分法查找只適用于順序存儲的有序表。有序表即是表中數據元素按照關鍵碼的升序或者降序排列。去中間元素作為比較對象，若給定值與中間元素的關鍵碼相等，則為查找成功；若給定值小于中間元素的關鍵碼，則在中間元素的左半區繼續查找，若給定值大于中間元素的關鍵碼，則在中間元素的右半區繼續查找。不斷重復上述的查找過程直到查找成功，或者所查找的區域，沒有該元素查找失敗。 //031040102順序查找 #include #define MaxSize 1024 typedef struct { KeyType key; //定義關鍵碼字段 ElemType elem;//定義其他字段 }elemtype; typedef struct //順序存儲結構定義 { elemtype elem[MaxSize];//定義數組 int length; //表長度 }S_TBL; S_TBL *Init_S_TBL() //順序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;}; int s_search(S_TBL *tbl,KeyType kx)//在表tbl中查找關鍵碼為kx的數據元素 { tbl->elem[0].key=kx; //存放檢測 for(int i=tbl->length;tbl->elem[i].key!=kx;i--); //從表尾向前查找 return i;}; void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“輸入一組以-1結尾的數(關鍵碼字段)”< tbl->length++; i=tbl->length+1; tbl->elem[i].key=k; cin>>k;} i=1;cout<<“輸入一組以-1結尾的數(數據元素)”< tbl->elem[i].elem=k; i++; cin>>k;} cout<<“請輸入所需查找數的關鍵碼字段：”< { flag=mid; cout<<“查找成功”< break; cout<<“所查找的數為//查找成功，元素位置設置到flag中 ”< } } } else return flag; cout<<“查找失敗”< //定義關鍵碼字段 ElemType elem; //定義其他字段 }elemtype;typedef struct //順序存儲結構定義 { elemtype elem[MaxSize];//定義數組 int length; //表長度 }S_TBL;S_TBL *Init_S_TBL() //順序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;};int Binary_search(S_TBL *tbl,KeyType kx)//在表tbl中查找關鍵碼為kx的數據元素 { int mid,flag=0,low=1,high=tbl->length;//1.設置初始區間 while(low<=high) //2.表空測試 { //非空，進行比較測試 mid=(low+high)/2; //3.得到中間點 if(kx high=mid-1; //調整到左半區 else if(kx>tbl->elem[mid].key) low=mid+1; //調整到右半區 else { //返回該元素在表中的位置，或返回0 };void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“輸入一組以-1結尾的數(關鍵碼字段)”< tbl->length++; i=tbl->length+1; tbl->elem[i].key=k; cin>>k;} i=1;cout<<“輸入一組以-1結尾的數(數據元素)”< tbl->elem[i].elem=k; i++; cin>>k;} cout<<“輸入所需查找數的關鍵碼字段”< cout<<“查找成功”< cout<<“所查找的數為”< } else cout<<“查找失敗”< -1結尾的數(數據元素)33 22 11 55 99 77 88 66 44-1 輸入所需查找數的關鍵碼字段3 查找成功 所查找的數為33 實驗四的收獲 查找的程序對我來說不陌生。兩種基本方法的比較和應用里，我留意了最大查找次 數的不同。順序查找的進行，如果查找不成功那么會議共比較N+1次。當數據量很大的時候，平均查找長度過大，當然順序查找對于數據的存貯方式沒有任何的要求。折半查找會有一個平均查找長度以及查找的最大長度。 我比較傾向于這本查找，其查找的效率明顯會高于順序查找。特別地，我還留意到對于單鏈表結構，無法進行二分法的查找，因為全部的元素的定位只能從指針開始。對于線性列表只能采取順序查找的方式。 上機實踐五 題目五：排序(插入排序選擇排序冒泡排序)排序是數據處理中經常使用的一種重要的運算，其目的就是將一組數據按照規定的順序進行排列。排序的目的是便于查詢和處理。插入排序的基本思想是每一步將一個待排序的元素，按照其關鍵字嗎的大小，插入到前面已經排序號的一組元素的適當的位置上，知道所有的元素都插入為止。一般地認為插入排序是一個穩定的排序方法。選擇排序，每次從當前待排序的記錄中，通過依次地進行關鍵字媽的比較從中選擇一個關鍵字最小的記錄，并且把它與當前待排序的第一個記錄進行交換。直接選擇排序是一個不穩定的排序方法。冒泡排序是一種簡單的交換排序的方法。一次地比較相鄰兩個記錄的關鍵字，若發現兩個記錄的次序相反（即位前一個記錄的關鍵字大雨后有一個記錄的關鍵字），進行記錄的交換一直到沒有反序為止。極端情況下，冒泡排序會有最短與最長時間，整個隊列越是接近有序，則冒泡排序的進行次數越少。 //031040102 插入排序 #include //定義關鍵碼字段 ElemType elem; //定義其他字段 }elemtype; typedef struct //順序存儲結構定義 { elemtype elem[MaxSize]; //定義數組 int length; //表長度 }S_TBL; S_TBL *Init_S_TBL() //順序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;}; int Binary_search(S_TBL *tbl,KeyType kx)//在表tbl中查找關鍵碼為kx的數據元素 { int mid,flag=0,low=1,high=tbl->length;//1.設置初始區間 while(low<=high) //2.表空測試 { //非空，進行比較測試 mid=(low+high)/2; //3.得到中間點 if(kx high=mid-1; //調整到左半區 else if(kx>tbl->elem[mid].key) low=mid+1; //調整到右半區 else { flag=mid; break; //查找成功，元素位置設置到flag中 } } Return flag;//返回該元素在表中的位置，或返回0 }; void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“輸入一組以-1結尾的數(關鍵碼字段)”< tbl->length++; i=tbl->length+1; tbl->elem[i].key=k; cin>>k;} i=1;cout<<“輸入一組以-1結尾的數(數據元素)”< while(k!=-1)};{ void Print(RecType R[],int n) tbl->elem[i].elem=k; i++; cin>>k;} cout<<“輸入所需查找數的關鍵碼字段”< cout<<“查找成功”< cout<<“所查找的數為”< cout<<“查找失敗”< k=i; for(j=i+1;j<=n;j++) if(R[j].key k=j; if(k!=i) { R[0]=R[k]; R[k]=R[i]; R[i]=R[0]; } } //輸出數組內所有元素 { cout<<“關鍵字段為：”< cout< cout< R[++n].key=x; cin>>x;} n=0;cout<<“請輸入一組以-1結尾的數(數據元素)：”< R[++n].otherinfo=x; cin>>x;} cout<<“ 排序前 ”< Print(R,n);SelectSort(R,n);cout<<“排序后”< 請輸入一組以-1結尾的數(數據元素)： 33 22 11 44 55 66 99 88 77-1 排序前 關鍵字段為： 6 9 7 4 1 5 6 8 3 所有元素為： 33 22 11 44 55 66 99 88 排序后 關鍵字段為： 1 3 4 5 6 6 7 8 9 所有元素為： 55 44 66 33 99 11 88 22 //031040102 冒泡排序 #include #define MaxSize 50 cin>>x;typedef struct RecType } //定義排序記錄的形式 cout<<“排序前：”< 請輸入一組以 -1結尾的數(關鍵碼字段)： //選擇排序函數 { int i,j,flag;for(i=1;i flag=1; for(j=1;j<=n-i;j++) if(R[j+1].key { flag=0; R[0]=R[j]; R[j]=R[j+1]; R[j+1]=R[0]; } if(flag==1) return;} };void Print(RecType R[],int n)//輸出數組內所有元素 { cout<<“關鍵字段為：”< cout< cout< R[++n].key=x; cin>>x;} n=0;cout<<“請輸入一組以-1結尾的數(數據元素)：”< R[++n].otherinfo=x;9 8 7 4 1 5 6-1 請輸入一組以-1結尾的數(數據元素)： 11 22 33 44 66 55 77 88-1 排序前： 關鍵字段為： 6 9 8 7 4 1 5 6 所有元素為： 11 22 33 44 66 55 77 88 排序后： 關鍵字段為： 1 4 5 6 6 7 8 9 所有元素為： 55 66 77 11 88 44 33 22 實驗五的收獲 三種不同的排序方式，都是之前C++ 學習時候的重點掌握內容。 直接插入排序的算法很簡潔，也很容易實現。從空間看，它只需要一個元素的輔助，從實踐看該算法的主程序運行次數只比元素的個數少一。當然由于原列表的排序狀況未知，其總比較次數和總的移動次數也是未定的，取平均數約為0.25N^2。對于直接選擇排序，比較次數與原表元素的排列順序無關，移動次數有關。根據冒泡排序的思想，待排序的記錄有序之 后，則在下一趟的排序時候不會再有記錄的交換位置，由此，我增加了一個標記flag，來直觀表示每一次的排序是否需要發生交換，無交換則已經完成可以結束冒泡。特別地冒泡排序需要增加一個附加的單元來實現元素的交換。在交換時需要留意免得出錯。 · 數據結構實驗報告 課程 數據結構 _ 院 系 專業班級 實驗地點 姓 名 學 號 實驗時間 指導老師 數據結構上機實驗報告1 一﹑實驗名稱： 實驗一——鏈表 二﹑實驗目的： 1.了解線性表的邏輯結構特性； 2.熟悉鏈表的基本運算在順序存儲結構上的實現，熟練掌握鏈式存儲結構的描述方法； 3.掌握鏈表的基本操作（建表、插入、刪除等）4.掌握循環鏈表的概念，加深對鏈表的本質的理解。5.掌握運用上機調試鏈表的基本方法 三﹑實驗內容： （1）（2）（3）（4）創建一個鏈表 在鏈表中插入元素 在鏈表中刪除一個元素 銷毀鏈表 四﹑實驗步驟與程序 #include LinkList p,q;L=(LinkList)malloc(sizeof(Lnode));L->next=NULL;q=L; cout<<“請輸入一個鏈表：”< for(int i=0;i { p=(LinkList)malloc(sizeof(Lnode)); cin>>p->data; p->next=q->next; q->next=p; q=p; } } int PrintLinkList(LinkList &L){//輸出鏈表L的數據元素 LinkList p; } void LinkListLengh(LinkList &L){//計算鏈表L的數據元素個數。int i=0;p=L->next;if(L->next==NULL){ } cout<<“鏈表的數據元素為:”;while(p) { cout< data<<“ ”; p=p->next;} cout<<“鏈表沒有元素!”< } LinkList p;p=L->next;while(p){ i++; p=p->next; } cout<<“鏈表的數據元素個數為:”< LinkList p,s;int j=0;p=L; while(p&&j } if(!p||j>i-1){ p=p->next;++j; } } cout<<“插入元素的位置不合理!”;return 0;s=(LinkList)malloc(sizeof(LNode));s->data=x;s->next=p->next;p->next=s;return 1;int DeleteLinkList(LinkList &L,int i){//刪除鏈表L的第I個數據元素。 LinkList p,q;int j=0;p=L;while(p->next&&j } if(!(p->next)||j>i-1){ p=p->next;++j; } } cout<<“刪除元素的位置不合理!”;return 0;q=p->next;p->next=q->next;i=q->data;free(q);return 1;void DestroyLinkList(LinkList &L){//銷毀鏈表L。 LinkList p,q;p=L->next;while(L->next!=NULL){ q=p->next;L->next=q; free(p);} p=q; free(L); cout<<“鏈表已經被銷毀!”< LinkList L; int i,j,x;cout<<“第一次數據結構上機實驗—鏈表”< CreatLinkList(L,j); LinkListLengh(L); PrintLinkList(L); cout<<“在第幾個元素前插入:”;cin>>i;cout<<“輸入插入的元素:”;cin>>x; InsertLinkList(L,i,x); LinkListLengh(L); PrintLinkList(L); cout<<“輸入刪除元素的位置:”;cin>>i; DeleteLinkList(L,i); LinkListLengh(L); PrintLinkList(L); cout<<“銷毀程序后為:”< DestroyLinkList(L);} 五﹑實驗結果 六﹑實驗心得體會： 鏈表是一種常見的重要的數據結構。它是動態地進行存儲分配的一種結構。它可以根據需要開辟內存單元。鏈表中每一個元素稱為“結點”，每個結點都應包括兩個部分：一為用戶需要用的實際數據，二為下一個結點的地址。 實驗的程序設計規劃（實現的功能、分幾個模塊、子函數）（1）編寫鏈表創建子函數void CreatLinkList(L,j)（2）編寫鏈表插入子函數 int InsertLinkList(LinkList &L, int i, int x)（3）鏈表的打印int PrintLinkList(LinkList &L)（4）編寫鏈表刪除子函數 int DeleteLinkList(LinkList &L,int i)（5）編寫鏈表銷毀子函數void DestroyLinkList(LinkList &L)（6）編寫主函數Main()，通過功能菜單調用子函數（7）編譯調試程序 經過多次的調試，修改，實驗結果終于正確了，在這個過程中，經歷了不知道怎么進行聲明區的編寫如包含文件，宏定義，函數聲明，全局變量聲明，結構體等的定義等的結合，到學會了使用先把程序主要規劃為四個部分來寫就簡單多了，第一，定義；第二，寫所要調用的子函數；第三，寫主函數，調用子函數；第四就是程序的編譯與調試，修改。數據結構實驗需要我們對每個程序的算法有深刻的理解，才能應用到實際中去，因此我們需要在做實驗之前要熟悉實驗的內容，且先把所要實驗的程序寫出來，在實驗中就可以查找錯誤并加以改正，這是一個成長的過程。 數據結構上機實驗報告一﹑實驗名稱： 實驗二—隊列 二﹑實驗目的： 1.掌握隊列這種抽象數據類型的特點, 掌握棧與隊列在實際問題中的應用和基本編程技巧,并能在相應的問題中選用它;2.熟練掌握循環隊列和鏈隊列的基本操作實現算法，特別是隊滿和隊空的描述方法； 3．掌握棧與隊列的數據類型描述及特點； 4.掌握棧的順序和鏈式存儲存表示與基本算法的實現； 5.掌握隊列的鏈式存儲表示與基本操作算法實現;6.按照實驗題目要求，獨立完成實際程序的編寫編寫、調試和運行，并通過用例數據的運行過程抓獲相關屏面驗證程序設計的正確性； 7.認真書寫實驗報告，并按時提交。 三﹑實驗內容： 對順序循環隊列，常規的設計方法是使用対尾指針和對頭指針，對尾指針用于指示當前的対尾位置下標，對頭指針用于指示當前的対頭位置下標。現要求： （1）掌握棧和隊列的特點，即后進先出和先進先出的原則。（2）設計一個使用對頭指針和計數器的順序循環隊列抽象數據類型，其中操作包括：初始化，入隊列，出隊列，取對頭元素和判斷隊列是否為空； （3）編寫主函數進行測試。 四﹑實驗步驟與程序 #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef struct QNode { int data;struct QNode *next;}QNode,*QueuePtr;typedef struct { QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue &Q){ } Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode));if(!Q.rear)exit(OVERFLOW);Q.front->next=NULL;return OK;void QueueEmpty(LinkQueue Q){ } void EnQueue(LinkQueue &Q,int e){ } int EnnQueue(LinkQueue &Q,int e){ QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf(“error”);if(Q.front==Q.rear)printf(“該鏈隊為空:”);else printf(“該鏈隊不為空:”);p->data=e;Q.rear->next=p;Q.rear=p;printf(“元素%d入隊成功”,e); } if(!p)return ERROR;p->data=e;Q.rear->next=p;Q.rear=p; return OK;void DeQueue(LinkQueue &Q){ } void GetHead(LinkQueue &Q){ QueuePtr p;QueuePtr p;if(Q.front==Q.rear)printf(“該鏈隊為空”);p=Q.front->next;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);printf(“隊首元素刪除成功”); } if(Q.front==Q.rear)printf(“該鏈隊為空”);p=Q.front->next;printf(“隊首元素為:%d”,p->data);void OutQueue(LinkQueue &Q){ } void LengthQueue(LinkQueue &Q){ int f=0;QueuePtr p;if(Q.front==Q.rear)QueuePtr p;if(Q.front==Q.rear)printf(“該鏈隊為空”);p=Q.front->next;while(p!=Q.rear->next){ } printf(“%d%,”,p->data);p=p->next; } printf(“該隊列的長度為:%d”,f);else { } p=Q.front->next;while(p!=Q.rear->next){ } printf(“該隊列的長度為:%d”,f);p=p->next;f++;void main(){ system(“cls”);int flag=1,i;LinkQueue Q;InitQueue(Q);printf(“************************鏈隊列功能菜單***********************n”);printf(“1:初始化鏈隊列，2:判斷鏈隊列是否為空, 3:進入隊列，4:取出隊首元素n”);printf(“5:輸出該隊列的所有元素,6:輸出該隊列的長度，7:結束程序，8:清屏n”); while(flag){ printf(“n請輸入操作符:”);scanf(“%d”,&i);switch(i){ case 1: int e,n,k;printf(“請輸入隊列的長度:”);scanf(“%d”,&n);printf(“請輸入隊列的元素:”);for(e=1;e<=n;e++){ } printf(“初始化鏈隊成功”);break;scanf(“%d”,&k);EnnQueue(Q,k);case 2: QueueEmpty(Q); break;case 3: int j;printf(“請輸入要進入隊列的元素”);scanf(“%d”,&j);EnQueue(Q,j);break;case 4: GetHead(Q);break;case 5: printf(“該隊列的元素為:”);OutQueue(Q);break; case 6: LengthQueue(Q);break;case 7: flag=0;break;case 8: system(“cls”);} break; } } 五﹑實驗結果 六﹑實驗心得體會： 程序主要構造了主函數main（）和 InitQueue（），QueueEmpty（）EnQueue()，OutQueue()等調用函數，實現了隊列的創立，隊列是否為空的判斷，入隊和出隊等功能。 通過此次實驗，加深了對隊列的存儲結構的了解，同時也對程序設計能力有了提高，加深了對隊列先進先出性質的理解，它允許在表的一端進行插入，在另一端刪除元素，這和我們日常生活中的排隊是一致的，最早進入隊列的元素最早離開。我們往往寫不出程序，這其中的原因我覺得是對程序的結構不是很了解，對實驗的內容也不熟練的結果，數據結構給我們許多程序的算法和模型，對我們寫程序的思維有很大的鍛煉，我們應珍惜每次上機實驗的機會去實踐課堂上所學的東西并從中發現問題，從而達到提升寫程序的能力。 數據結構上機實驗報告一﹑實驗名稱： 實驗三—二叉樹的遍歷 二﹑實驗目的： 1、熟悉二叉樹的結構特性，了解相應的證明方法； 2、掌握二叉樹的生成，掌握二叉樹的定義和存儲表示，學會建立一棵特定二叉樹的方法； 3、理解二叉樹的三種遍歷方法：先序遍歷、中序遍歷和后序遍歷； 4、學會編寫實現樹的各種操作的算法。 二、實驗內容： 1、使用類定義實現二叉樹，補充完整所缺的函數，并實現創建和遍歷二叉樹的基本操作； 2、編程實現在二叉鏈表這種存儲方式下，實現二叉的遍歷，可采用遞歸或者非遞歸實現，遍歷算法為在先序、中序和后序遍歷算法。 三、實驗步驟與程序： #include void PreOrder(BiTree T)//先序 { if(T!=NULL){ printf(“%c”,T->data);PreOrder(T->lchild);PreOrder(T->rchild);} } void InOrder(BiTree T)//中序 { if(T!=NULL){ InOrder(T->lchild);printf(“%c”,T->data);InOrder(T->rchild);} } void PostOrder(BiTree T)//后序 { if(T!=NULL){ PostOrder(T->lchild);PostOrder(T->rchild);printf(“%c”,T->data);} } void main()//主函數 { printf(“------------二叉樹的遍歷-------------n”);printf(“請輸入要遍歷的數：”);BiTree Ta;Ta=CreateBiTree();printf(“先序遍歷:”);printf(“n”);PreOrder(Ta);printf(“n”);printf(“中序遍歷:”);printf(“n”);InOrder(Ta);printf(“n”);printf(“后序遍歷:”);printf(“n”);PostOrder(Ta);} 五﹑實驗結果 六﹑實驗心得體會： 實驗的程序設計規劃（實現的功能、分幾個模塊、子函數）（1）先序遍歷遞歸算法函數：void PreOrder(BiTree T)（2）中序遍歷遞歸算法函數：void InOrder(BiTree T)（3）后續遍歷遞歸算法函數：void PostOrder(BiTree T)（4）主函數的實現：void main() 在實驗前我認真閱讀關于二叉樹的實現的內容，為編程實現第一步，本次實驗通過按上述的實驗步驟一步步實現的，實驗過程中出現了一些錯誤，經過一步步的調試，修改錯誤，得到了二叉樹的遍歷用遞歸運算的方法的程序。通過這個實驗，我體會到了理解數據結構的重要性，這有真正理解了定義數據類型的好處，才能用好這樣一種數據結構。二叉樹的先序，中序與后序的輸出都用了遞歸的算法，而且用起來不是很復雜，這使我更進一步理解了函數遞歸調用并得到靈活運用；在實現算法上，從算法的效率看，遞歸方法書寫形式較為簡潔，更為直觀，一般具有較好的空間效率。 總之，不管做什么實驗，我們在做實驗前都要先預習，對所做的實驗有較深的理解，在做實驗的時候需要很嚴謹，仔細的查找錯誤，從而能在實驗中收獲知識，提升自己。 數據結構上機實驗報告4 一﹑實驗名稱： 實驗四—查找 二﹑實驗目的： 1、熟悉掌握順序表的查找方法； 2、熟練掌握二叉排序樹的構造方法和查找算法 3、掌握描述查找過程的判定樹的構造方法，以及按照定義計算各種查找方法在等概率情況下查找成功時的平均查找長度； 4、學會定義線性表的儲存類型，實現C++程序的基本結構對線性表的一些基本操作和具體的函數定義； 5、掌握順序表的基本操作，實現順序表的查找的等基本運算； 6、掌握對于多函數程序的輸入，編輯，調試和運算過程。 二、實驗內容： 1、實現順序表的查找算法 2、關于衡量查找的主要操作—查找的查找平均效率的平均長度的討論。 三、實驗步驟與程序： #include element list[MAX_SIZE]; int seqsearch(element list[],int searchnum,int num);int main(){ int i,num,searchnum,k; printf(“---------------數據結構查找實驗-------------n”);printf(“請輸入數據元素的個數：”);scanf(“%d”,&num);printf(“請輸入數據的元素：n”);for(i=0;i printf(“請輸入要查詢的數據元素:”);scanf(“%d”,&searchnum);k=seqsearch(list,searchnum,num);if(k!=-1){ printf(“所查詢元素的下標為：”);printf(“%dn”,k);} else printf(“查詢元素不存在。n”);} return 0;} int seqsearch(element list[],int searchnum,int num){ int j; list[num].key=searchnum; for(j=0;list[j].key!=searchnum;j++);return j 六﹑實驗心得體會： 實驗的程序設計規劃為先寫一個主函數int main()，再寫一個查找的子函數int seqsearch(element list[],int searchnum,int num)，主函數通過調用子函數的方法實現程序的設計。 所謂“查找”即為在一個眾多的數據元素（或記錄）的查找表中找出某個“特定的”數據元素（或記錄），通過本次實驗，我更進一步的了解數據結構程序實驗設計實現算法的基本模型，和算法實現等基本內容，學會了順序表的查找方法。 數據結構上機實驗報告5 一﹑實驗名稱： 實驗五—內部排序 二﹑實驗目的： 1、通過實現下述實驗內容，學習、實現、對比各種排序算法，掌握各種排序算法的優劣，以及各種算法使用的情況，并加以靈活應用。 2、掌握各種排序時間復雜度的分析方法。 二、實驗內容： 1、插入排序：依次將待排序的序列中的每一個記錄插入到先前排序好的序列中，直到全部記錄排序完畢。 2、快速排序：首先選擇一個基準，將記錄分割為兩部分，左支小于或等于基準，右支則大于基準，然后對兩部分重復上述過程，直至整個序列排序完成。 3、討論各種內部排序方法的基本思路，算法特點，排序過程及它們的時間復雜度的分析。 三、實驗步驟與程序： #include } int x;void charu();void kuaisu();printf(“----------內部排序---------n”);printf(“ 1、插入排序：n”);printf(“ 2、選擇排序：n”);printf(“請根據序號選擇：”);scanf(“%d”,&x);if(x==1)charu();else kuaisu();void charu(){ int a[7],j,i,m; printf(“插入排序n”); printf(“請輸入個您想排序的數據:n”); for(i=0;i<7;i++)scanf(“%d”,&a[i]); for(j=1;j<7;j++) { m=a[j]; for(i=j-1;i>=0;i--) { if(a[i] break; else a[i+1]=a[i]; } a[i+1]=m; } printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} quick(int first,int end,int L[]){ int left=first,right=end,key; key=L[first]; while(left { while((left right--; if(left L[left++]=L[right]; while((left left++; if(left L[left]=key; return left; } quick_sort(int L[],int first,int end) { int split; if(end>first) { split=quick(first,end,L); quick_sort(L,first,split-1); quick_sort(L,split+1,end); } } void kuaisu(){ int a[7],i; printf(“快速排序n”); printf(“請輸入個您想排序的數據:n”); for(i=0;i<7;i++) scanf(“%d”,&a[i]); quick_sort(a,0,9); printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} 五﹑實驗結果： 六﹑實驗心得體會： 排序的功能是將一個數據元素（或記錄）的任意序列，從新排成按關鍵字有序的序列；直接插入排序的穩定性比快速排序高，且算法較簡單。本次實驗運用到的是插入排序和快速排序。 實習報告 題 目 : 實現一個約瑟夫環程序 班級：031021姓名：王帥學號：03102076 一、需求分析 1． 本演示程序中，利用單向循環鏈表存儲結構存儲約瑟夫環數據（即n個人的編號和密碼）。 2． 演示程序以用戶和計算機的對話方式執行，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中需要輸入的數據，運算結果顯示在其后。 3． 程序執行的命令包括： 1)構造單向循環鏈表；2）進行數值的輸入，并作判斷分析；3）約瑟夫算法的實現與結果輸出；4）結束。 4． 測試數據 m 的初值為20；n=7，7個人的密碼依次為：3，1，7，2，4，8，4，（正確的出列順序為6，1，4，7，2，1，3，5）。 二、概要設計 1．單向循環鏈表的抽象數據類型定義為： ADT List｛ 數據對象：D=｛ai | ai?正整數，I=1，2，......，n,n≥0｝數據關系：R1=｛< ai-1，ai > |，ai-1，ai?D,I=1，2，......，n｝基本操作： Init List(&L) 操作結果：構造一個空的線性表L。 List Insert(&L,i,e) 初始條件：線性表L已存在，1≤i≤List Length(L)+1.操作結果：在L中第i個位置之前插入新的數據元素e，L長度加1。List Delete(&L,i,&e) 初始條件：線性表L存在非空，1≤i≤List Length(L).操作結果：刪除L的第i個元素，并用e返回其值，L長度減1。 2． 程序包含四個模塊： 1）主程序模塊： void main() { 初始化； for（;;） {} while（命令=開始） { 接受命令； 處理命令； } for（;;） { } } 2）有序表單元模塊——實現有序表的抽象數據類型； 3）節點結構單元模塊——定義有序表的節點結構； 4）數據輸入分析模塊——判斷輸入數據正確有效； 各模塊之間的調用關系如下： 主程序模塊 ↓ 有序表結構模塊 ↓ 節點結構單元模塊 ↓ 數據輸入分析模塊 三、詳細設計 1、結點類型，指針類型 TypedefstructLNode{ int code,date;//code 為人所在位置 date為人持有的密碼 struct LNode *next; };// 結點類型，指針類型 2、構造單向循環鏈表 struct LNode *p,*head,*q;//定義頭節點，和指針 for(i=2;i<=n;i++) { struct LNode *s=(struct LNode *)malloc(sizeof(struct LNode));//分配 新結點空間 s->code=i; input(s->date); p->next=s; p=p->next; } p->next=head;//根據輸入的人數，進行單項循環鏈表的創建，p指向最后一個結點，并與頭節點鏈接，形成單項循環鏈表 3、約瑟夫環的程序實現部分 while(n!=1)//判斷輸入人數，如為1則直接輸出結果，不循環 { for(i=1，m=m%n;i { p=p->next; } q=p->next;//找到要刪除節點 p->next=q->next;//找到要刪除節點的后繼，并連接新環m=q->date;//找到下一個密碼 printf(“%d”,q->code); free(q);//釋放已刪除節點空間 n--;//鏈表長度減一 } printf(“%d”,p->code);//約瑟夫環的結果輸出 4、其他函數代碼 數值的輸入限制 int input() { int y,k,z=0; char c;//元素類型 char a[4];//數組初始化 if(!z)//輸入判斷，確定位數字或控制字符且位置和密碼不為零 { for(y=0;y<4;y++) { c=getch(); if(c>=48&&c<=57)//確定為輸入數字 {a[y]=c; putch(c); } else { y--; if(c=='r')//確定輸入為控制字符 即回車或者刪除 break; else if(c==8) {a[y]='n'; y--;} continue; } } k=atoi(a);//確定最終輸入數字的值 printf(“n”); z=k; if(z==0) printf(“ERROR!The number couldn't be 0!n”);// 輸入為零，重新輸入 } return(k);//數值的返回 5、函數的調用關系圖反映程序層次結構 Main→input 四、調試分析 1、早期程序只寫了約瑟夫環的實現部分，沒有對輸入數據進行篩選，調試的時候會經常出錯。比如是輸入字母，或者輸入0，大于32767溢出； 2、早期的循環過程中沒有進行優化，導致循環次數過多，浪費時間； 3、為了輸出時美觀，分別在input和main函數主體內做了兩次，輸入非零的判斷，浪費了資源； 4、算法的時空分析 為了限制在輸入過程中不會上溢，只在輸入中限定為四個不全為零的數字，但是做的是do……while循環，復雜度為o（1）; 當n大于1時： 在數據輸入中，鏈表的創建是for循環，時間復雜度為o（n-1） 在約瑟夫環實現程序中，為for循環。時間復雜度為o（m%n-1） 當n=1時，復雜度為o（1）。 五、用戶手冊 用戶根據提示，先輸入起始密碼m，然后輸入人數n，再根據人數，分別輸入每個人的密碼date，數值均不能為0，否則會提示重新輸入，輸入為字母則自動丟棄，輸入錯誤可用刪除鍵進行修改，輸入完成后按回車鍵確定本次輸入完畢（若輸入數字大于9999，則第五位自動轉換為下一個數字的起始位，依此類推）。 當n個數字全部輸入完畢，則自動顯示結果，按任意鍵則退出本程序。 六、測試結果 第一組：m 的初值為20；n=7，7個人的密碼依次為：3，1，7，2，4，8，4，出列順序為6，1，4，7，2，1，3，5。 第二組： m 的初值為30；n=8，7個人的密碼依次為：5，1，6，9，4，7，2，3，出列順序為6，5，2，3，7，1，4，8。 第三組 : m 的初值為15；n=6，7個人的密碼依次為：5，3，4，7，6，9，出列順序為3，1，2，6，4，5。 七、附錄 源程序頭文件名清單： #include “malloc.h”//內存空間分配頭文件 #include “stdio.h”//輸入輸出函數頭文件 #include “stdlib.h”//input函數中字符串轉短整形函數的頭文件 #include “conio.h”//最后顯示結果、清屏函數頭文件 數據結構上機實驗六 實驗內容:圖的基本操作 實驗要求: 1)圖的遍歷與基本操作要作為函數被調用.2)把自己使用的圖結構明確的表達出來.3)基本上實現每個實驗題目的要求.分組要求：可單獨完成，也可兩人一組。 實驗目的: 1)熟悉C/C++基本編程,培養動手能力.2)通過實驗,加深對圖的理解.評分標準： 1)只完成第一和第二題，根據情況得4，5分； 2）完成前3題，根據情況得5至7分； 3）在2）基礎上，選做四）中題目，根據情況得8至10分。 題目: 一)建立一個無向圖+遍歷+插入 (1)以數組表示法作為存儲結構，從鍵盤依次輸入頂點數、弧數與各弧信息建立一個無向圖； (2)對（1）中生成的無向圖進行廣度優先遍歷并打印結果； (3)向（1）中生成的無向圖插入一條新弧并打印結果； 二)建立一個有向圖+遍歷+插入+刪除 (1)以鄰接表作為圖的存儲結構，從鍵盤輸入圖的頂點與弧的信息建立一個有向圖； (2)對（1）中生成的有向圖進行深度優先遍歷并打印結果； (3)在（1）中生成的有向圖中，分別插入與刪除一條弧并打印其結果； (4)在（1）中生成的有向圖中，分別插入與刪除一個頂點并打印結果； (5)在（1）中生成的有向圖中,各頂點的入度與出度并打印結果； 三）基本應用題 （1）編寫算法，判斷圖中指定的兩個頂點是否連通。 （2）編寫算法，判斷圖的連通性。如果不連通，求連通分量的個數 （3）編寫算法，判斷圖中任意兩個頂點的連通性 （4）編寫算法，判斷圖中是否存在回路。 （5）實現圖的廣度優先搜索算法。 四）高級應用題 （1）實現Prim算法 （2）實現Kruskal算法 （3）實現迪杰斯特拉算法 （4）實現拓撲排序算法 （5）實現關鍵路徑算法 實驗一 線性表 一、實驗題 線性表的應用———多項式計算 二、程序設計思路 包括每個函數的功能說明，及一些重要函數的算法實現思路一鏈式存儲： 1.void InitPoly(LNode *&p)初始化多項式 2.void TraversePoly(LNode *&p)遍歷多項式 3.void ClearPoly(LNode *&p)清除多項式 4.void InsertPoly(LNode *&p, double a, int e)插入一項 5.void DeletetPoly(LNode *&p,int pos) 刪除一項 6.double PolySum(LNode *&p, double x) 多項式求值 7.LNode * PolyAdd(LNode *&p1,LNode *& p2) 多項式相加 順序存儲： 1.void InitPoly1(SeqList &L)初始化多項式 2.void ClearPoly1(SeqList &L)清除多項式 3.void TraversePoly1(SeqList L) 遍歷多項式 4.bool InsertPoly1(SeqList &L, ElemType item)插入一項 5.double PolySum1(SeqList L,double x) 多項式求值 6.bool DeleteList1(SeqList &L,int pos) 刪除一項 7.SeqList PolyAdd1(SeqList &L1,SeqList& L2) 多項式相加 三、源程序代碼 #include { if(pos>1||pos<-1)return false;NodeType *cp=p->next;NodeType *np=p;if(pos==0){ while(cp!=p){ if(cp->coef==a&&cp->exp==e)break;else{ np=cp;cp=cp->next;} } } else if(pos==-1)while(cp!=p){ 刪除np=cp;cp=cp->next;} np->next=cp->next;delete cp;return true;} double PolySum(NodeType *p, float x)//多項式求值 { int i;double sum=0,item;NodeType *cp=p->next;while(cp!=p){ item=1;for(i=1;i<=cp->exp;i++)item=item*x;sum=sum+item*cp->coef;cp=cp->next;} return sum;} NodeType *PolyAdd(NodeType *p1, NodeType *p2)//多項式相加 { float coef;NodeType *a=p1->next,*b=p2->next,*c,*pc;InitPoly(c);pc=c;while(a!=p1&&b!=p2){ if(a->exp==b->exp){ coef=a->coef+b->coef;if(coef!=0){ InsertPoly(pc, coef, a->exp);pc=pc->next;} a=a->next;b=b->next;} else if(a->exp 輸出多項式 } void ClearPoly1(ListType &p)//清除多項式 { if(p.list!=NULL){ delete []p.list;p.list=NULL;} p.size=0;} void InsertPoly1(ListType &p, float a, int e)//項 { p.list[e]=a;if(p.size { int i,n;if(p.size==0){ cout<<“多項式為空,刪除無效!”< 插入一if(p.list[e]==a)p.list[e]=0;else if(pos==-1)p.list[p.size]=0;return true;} double PolySum1(ListType p, float x)//值 { double sum=0,item;int i,j;for(i=0;i<=p.size;i++){ item=1;for(j=1;j<=i;j++)item=item*x;sum=sum+item*p.list[i];} return sum;} ListType PolyAdd1(ListType p1, ListType p2)//項式相加 { ListType p;InitPoly1(p);float coef; 多項式求多int i,j;for(i=0;i<=p1.size;i++){ coef=p1.list[i]+p2.list[i];InsertPoly1(p, coef, i);} if(i<=p1.size)for(j=i;j<=p1.size;j++)InsertPoly1(p, p1.list[j], j);if(i<=p2.size)for(j=i;j<=p2.size;j++)InsertPoly1(p, p2.list[j], j);return p;四實驗結果分析 五.心得體會 對于結構體的認識增加了，對于動態存儲也有了更多的認識，也是在不知不覺中提高了。 實驗二 字符串的操作 一、實驗題目——字符串的操作 二、程序設計思路 采用定長順序存儲表示，由用戶創建串s和串t，實現在串s中下標為pos的字符之前插入串t。 三、源程序代碼 #define MAXLEN 10 typedef struct { /*串結構定義*/ char ch[MAXLEN]; int len;}SString;void createstring(SString *s) /*創建串s*/ { int i,j;char c;printf(“input the length of the string:”); scanf(“%d”,&j); for(i=0;i { printf(“input the %d:”,i+1); fflush(stdin); scanf(“%c”,&c); s->ch[i] = c; } s->len = j;} void output(SString *s) /*輸出串s*/ { int i;for(i=0;i printf(“%c ”,s->ch[i]); printf(“n”);} int StrInsert(SString *s, int pos, SString *t)/*在串s中下標為pos的字符之前插入串t */ { int i;if(pos<0 || pos>s->len) /*插入位置不合法*/ return(0); if(s->len + t->len<=MAXLEN) /*插入后串長≤MAXLEN*/ { for(i=s->len + t->len-1;i>=t->len + pos;i--) s->ch[i]=s->ch[i-t->len];/*將下標為pos的字符后的元素往后移動t->len個長度*/ for(i=0;i s->ch[i+pos]=t->ch[i]; /*將串t從下標為pos位置開始插入到串s*/ s->len=s->len+t->len;} else { if(pos+t->len<=MAXLEN)/*插入后串長>MAXLEN,但串t的字符序列可以全部插入*/ { for(i=MAXLEN-1;i>t->len+pos-1;i--) s->ch[i]=s->ch[i-t->len]; for(i=0;i s->ch[i+pos]=t->ch[i]; /*將串t從下標為pos位置開始插入到串s*/ s->len=MAXLEN; } else /*插入后串長>MAXLEN,并且串t的部分字符也要舍棄*/ { for(i=0;i s->ch[i+pos]=t->ch[i]; /*直接從下標為pos的位置按順序插入串t*/ s->len=MAXLEN; } return(1);} } void main(){ SString *str1;SString *str2;int i,j,k,pos;int flag=0;str1 =(SString *)malloc(sizeof(SString));str1->len = 0;printf(“creat the string 1:n”);createstring(str1);printf(“creat the string 2:n”);createstring(str2);printf(“input the insert local:”);scanf(“%d”,&pos);flag=StrInsert(str1,pos,str2);if(flag == 0) printf(“insert error!”);else { printf(“after insert:n”); output(str1);} } 四、實驗結果 五、實驗體會 通過本次實驗，我加深了對串數據結構的理解。在串的定長順序存儲結構中，按照預定義的大小，為每個定義的串變量分配一個固定長度的存儲區。在存儲方式中，結點大小的選擇和順序存儲方式的格式選擇一樣都很重要，它直接影響著串處理的效率。 實驗三 一、實驗題目——非遞歸算法對二叉樹進行中前序遍歷 二、程序設計思路 創建一棵10個節點構造的完全二叉樹，并對其進行前、中、后序遍歷。 三、源程序代碼 #define STUDENT EType #define SType SType #define HeadEType int #include //定義數據結構類型 struct STUDENT { char name[8];int age;char number[15];char address[20];}; struct BinaryTreeNode { EType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;};typedef BinaryTreeNode BinaryTree; typedef struct { BinaryTreeNode *ptr;bool status;}SType; typedef struct { SType *element;int top;int MaxSize;}Stack; void CreatStack(Stack &S, int MaxStackSize){// 構造一個最大容量為MaxStackSize 的堆棧 S.MaxSize = MaxStackSize; S.element = new SType[S.MaxSize]; S.top =-1;} bool IsEmpty(Stack &S){// 判斷堆棧S是否為空 if(S.top ==-1) return true; return false;} bool IsFull(Stack &S){// 判斷堆棧S是否為空 if(S.top == MaxSize-1) return true; return false;} bool Push(Stack &S , SType &x){// x進s棧，返回進棧后的狀態值 if(IsFull(S)) return false; S.top++; S.element[S.top] = x; return true;} bool Pop(Stack &S , SType &x){// 將s棧頂的值取至x中，返回出棧后的狀態值 if(IsEmpty(S)) return false; x = S.element[S.top]; S.top--; return true;} BinaryTreeNode *MakeNode(EType &x) {//構造結點 BinaryTreeNode *ptr; ptr = new BinaryTreeNode; if(!ptr)return NULL; ptr->data = x; ptr-> LChild = NULL; ptr-> RChild = NULL; return ptr;} void MakeBinaryTree(BinaryTreeNode *root, BinaryTreeNode *left, BinaryTreeNode *right){// 聯接root，left, right所指的結點指針為二叉樹 root->LChild=left; root->RChild=right;} void PreOrderNoRecursive(BinaryTreeNode *BT){//二叉樹前序遍歷非遞歸的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設堆的空間足夠大，即MaxStackSize值足夠大 CreatStack(S,MaxStackSize);//產生一個空棧 while(q||!IsEmpty(S)){ if(q) { cout< ele.ptr=q; Push(S,ele);//節點指針進棧，以后回溯時在退棧 q=q->LChild;//指針指向剛剛被訪問的“根”節點的左子樹 } else //當左子樹為空時，利用堆棧回溯 if(!IsEmpty(S)) { Pop(S,ele);//退?；厮?/p> q=ele.ptr;//指針重新指向剛剛被訪問的“根”節點 q=q->RChild;//指針指向該回溯節點的右子樹 } } } void InOrderNoRecursive(BinaryTreeNode *BT){//二叉樹的中序遍歷非遞歸的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設堆的空間足夠大，即MaxStackSize值足夠大 CreatStack(S,MaxStackSize);//產生一個空棧 while(q ||!IsEmpty(S)){ while(q)//找到最左邊的子樹 { ele.ptr=q; Push(S,ele);//指針非空時，將當前的“根”節點指針進棧，用于以后回溯 q=q->LChild;//指針繼續指向該“根”節點的左子樹 } if(!IsEmpty(S))//當左子樹為空時，進行退?；厮?/p> { Pop(S,ele);//從堆棧中回溯節點指針（節點還未訪問） q=ele.ptr; cout< q=q->RChild;//指針向回溯的節點右子樹推進 } } } void PostOrderNoRecursive(BinaryTreeNode *BT){//二叉樹的后序遍歷非遞歸的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設堆的空間足夠大，即MaxStackSize值足夠大 CreatStack(S,MaxStackSize);//產生一個空棧 while(q ||!IsEmpty(S)){ if(q)//找最左邊的子樹 { ele.ptr=q; ele.status=false;//進棧前標記為第一次進棧 Push(S,ele); q=q->LChild;//指針繼續向左推進 } else if(!IsEmpty(S))//直到左子樹為空時，退?；厮?/p> { Pop(S,ele);//從堆棧中彈出回溯節點（還未訪問） q=ele.ptr;//q指向當前回溯節點 if(ele.status)//判斷節點進棧標志，是否對其進行訪問 { cout< q=NULL;//將q設為空，為了繼續退棧 } else { ele.status=true;//改變回溯節點的進棧標記，以便再次進棧 Push(S,ele); q=q->RChild;//指針向該回溯節點的右孩子推進 } } } } //主函數 void main(){ BinaryTreeNode *ptr[11]; char Name[][8]={“ ”,“A”,“B”,“C”,“D”,“E”,“F”,“G”,“H”,“I”,“J”};EType x[11];for(int i=1;i<11;i++){ strcpy(x[11-i].name,Name[11-i]); ptr[11-i]=MakeNode(x[11-i]);//構造10個二叉樹節點 } //將節點鏈接域填值，構造一個二叉樹 //這里構造的是一棵有10個節點的完全二叉樹 for(int j=1;j<5;j++){ MakeBinaryTree(ptr[j],ptr[2*j],ptr[2*j+1]);} MakeBinaryTree(ptr[5],ptr[10],NULL);//該完全二叉樹構造完畢 //***********對已構造的完全二叉樹進行前序非遞歸遍歷************// cout<<“對該二叉樹進行前序遍歷結果：”< //***********對已構造的完全二叉樹進行中序非遞歸遍歷************// cout< //***********對已構造的完全二叉樹進行中序非遞歸遍歷************// cout< 四、實驗結果分析 五、實驗總結 二叉樹是一種非常重要的數據結構，很多其它數據結構都是基于二叉樹的基礎演變而來的。對于二叉樹，有前序、中序以及后序三種遍歷方法。因為樹的定義本身就是遞歸定義，因此采用遞歸的方法去實現樹的三種遍歷不僅容易理解而且代碼很簡潔。而對于樹的遍歷若采用非遞歸的方法，就要采用棧去模擬實現。在三種遍歷中，前序和中序遍歷的非遞歸算法都很容易實現，非遞歸后序遍歷實現起來相對來說要難一點。 實驗四 一、實驗題目——深度優先算法實現圖的遍歷 二、程序設計思路 以鄰接矩陣或鄰接表為存儲結構，以用戶指定的頂點為起始點，實現無向連通圖的深度優先，并輸出遍歷的結點序列。首先，根據用戶輸入的頂點總數和邊數，構造無向圖，然后以用戶輸入的頂點為起始點，進行深度優先，并輸出遍歷的結果。 三、源程序代碼 #include };struct vexnode { char vertex;edgenode* edgelink;};struct Graph { vexnode adjlists[MaxVerNum];int vexnum;int arcnum;};//隊列的定義及相關函數的實現 struct QueueNode { int nData;QueueNode* next;};struct QueueList { QueueNode* front;QueueNode* rear;};void EnQueue(QueueList* Q,int e){ QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q==NULL) return;if(Q->rear==NULL) Q->front=Q->rear=q;else { Q->rear->next=q; Q->rear=Q->rear->next;} } void DeQueue(QueueList* Q,int* e){ if(Q==NULL) return;if(Q->front==Q->rear){ *e=Q->front->nData; Q->front=Q->rear=NULL;} else { *e=Q->front->nData; Q->front=Q->front->next;} } //創建圖 void CreatAdjList(Graph* G){ int i,j,k;edgenode* p1;edgenode* p2;cout<<“請輸入頂點數和邊數:”< cin>>G->adjlists[i].vertex; G->adjlists[i].edgelink=NULL;} cout<<“開始輸入邊表信息:”< cout<<“請輸入邊 cin>>i>>j; p1=new edgenode; p1->endver=j; p1->edgenext=G->adjlists[i].edgelink; G->adjlists[i].edgelink=p1; p2=new edgenode; p2->endver=i; p2->edgenext=G->adjlists[j].edgelink; G->adjlists[j].edgelink=p2; //因為是無向圖，所以有兩次建立邊表的過程 } } //------------------------------深度優先遍歷 void DFS(Graph *G,int i,int visit[]){ cout< DFS(G,p->endver,visit);} } void DFStraversal(Graph *G,char c)//深度優先遍歷 { cout<<“該圖的深度優先遍歷結果為:”< visit[i]=0;//全部初始化為0，即未訪問狀態 } int m;for(i=0;i if(G->adjlists[i].vertex==c)//根據字符查找序號 { m=i; DFS(G,i,visit); break; } } //繼續訪問未被訪問的結點 for(i=0;i if(visit[i]==0) DFS(G,i,visit);} cout< int e=0; DeQueue(Q,&e); cout< visit[e]=1; edgenode* p=new edgenode; p=G->adjlists[e].edgelink; if(p) { int m=p->endver; if(m==0) { EnQueue(Q,m); while(visit[m]==0) { p=p->edgenext; if(p==NULL) break; m=p->endver; EnQueue(Q,m); } } } } } void BFStraversal(Graph *G,char c){ cout<<“該圖的廣度優先遍歷結果為:”< visited[i]=0;} int m;for(i=0;i if(G->adjlists[i].vertex==c) { m=i; BFS(G,i,visited); break; } } //繼續訪問未被訪問的結點 for(i=0;i if(visited[i]==0) BFS(G,i,visited);} cout< 四、實驗結果及分析 五、實驗總結 本次試驗采用的是鄰接表的方式實現圖的深度優先遍歷和。對于深度優先遍歷，主要是采用遞歸的方式。試驗本身問題不是太大，但要注意輸入的問題，什么時候用空格，什么時候用回車，這一點是需要注意的，因為一旦數據的輸入有問題，結果當然也就不可能正確了。只有正確的輸入數據，建立圖，才能得出正確的遍歷結果。第二篇：數據結構上機實驗報告
第三篇：數據結構上機實驗報告
第四篇：數據結構上機實驗--圖
第五篇：數據結構上機作業
點擊咨詢 