List類成員函數(shù)拓展實驗報告

1、 2015/2016(1)實驗題目 List類成員函數(shù)拓展 學(xué)生姓名 韓笑 學(xué)生學(xué)號 2 學(xué)生班級 計算機(jī)+自動化1402班 任課教師 * 提交日期 2015-11-15 計算機(jī)科學(xué)與技術(shù)學(xué)院（軟件學(xué)院）14 / 15文檔可自由編輯打印實驗報告一、 題目的內(nèi)容l 將A1和B1中的數(shù)據(jù)導(dǎo)入鏈表中，形成鏈表A2和B2，并打印各自鏈表元素；l 將鏈表A2和B2中的元素各自排序（從大到?。纬涉湵鞟3和B3，并打印各自鏈表元素。l 合并鏈表A3，B3，合并后的鏈表C的元素從大到小排列，并打印鏈表C。對于給定的整數(shù)n，編寫一個算法把新的節(jié)點插入到鏈表中第n個節(jié)點之后的位置，該鏈表的第一個節(jié)點由firs

2、t指向。二、 做題思路及設(shè)計分析題目：作業(yè)中共有三題，都是基于鏈表并對其函數(shù)進(jìn)行擴(kuò)充，鏈表類在前一次實驗中已經(jīng)編寫過了，因此本次實驗只需在已有鏈表類的基礎(chǔ)上增加成員函數(shù)即可。List 類：在本實驗中不再重復(fù)描述，大致結(jié)構(gòu)框架如下NextNode節(jié)點示意圖：KeyPreList示意圖： 第 一 問：函數(shù)名定為add，并在構(gòu)造函數(shù)中增加對數(shù)組的重載，從頭節(jié)點first開始往后遍歷，由于如果利用push_back函數(shù)在每插入一元素時都會對鏈表進(jìn)行一次遍歷，在時間效率上不高，因此不直接采用push_back函數(shù)而直接在循環(huán)過程中保留上次插入結(jié)點的位置，與上次插入的結(jié)點后直接插入結(jié)點，代碼如下（詳細(xì)含義

3、見第四部分代碼注釋）：void add(int* x, int size)if(size = 0)first = new node();elsefirst = new node(x0); which value is x0 to node "first"node* q = first;/create a pointer "q" points to first for(int i = 1; i < size; i+)node *a = new node(xi);q->next = a;q = q->next;q->next = NU

4、LL;Size = size;List(int* x, int size)if(size = 0);elsefirst->key = x0;node* q = first; for(int i = 1; i < size; i+)node *a = new node(xi);q->next = a;q = q->next;q->next = NULL;Size = size;第 二 問：函數(shù)名定為sort，先復(fù)制構(gòu)造新的鏈表，利用快速排序?qū)崿F(xiàn)對新鏈表的排序，快排最核心的思想就是劃分，確定一個樞軸元素(pivot)，每一趟劃分的目的就是把待排序列分為兩部分，前一部分

5、比樞軸小(序列A)，后一部分比樞軸大(序列B)。經(jīng)過一趟劃分之后序列變?yōu)椋篈 pivot B。以下是具體步驟：1、確定每一次劃分的樞軸元素為當(dāng)前待排序列的頭節(jié)點。2、設(shè)置pHead和pEnd兩個游標(biāo)，pEnd指向序列A中的最后一個元素，初始化為樞軸本身(待排序列頭節(jié)點)。讓pHead遍歷一遍待排序列，當(dāng)所指元素比樞軸小時，將pEnd往前游一格，交換pEnd和pHead所指元素的值，這樣仍能保證pEnd指向的元素是序列A中的最后一個元素。3、交換pEnd所指元素和樞軸元素的值。4、對序列A和B重復(fù)步驟14。第 三 問：函數(shù)名定為merge_and_sort,先判斷兩鏈表是否已排好序，若沒有，則先

6、調(diào)用sort函數(shù)對其進(jìn)行排序（此步驟對于本題目可刪，但為保留程序可拓展性因此保留），之后創(chuàng)建兩個結(jié)點依次對應(yīng)兩鏈表的first結(jié)點，從大到小依次通過push_back函數(shù)插入新建鏈表中，并返回該新建鏈表，具體代碼見第四部分。三、 程序調(diào)試、測試、運行記錄 主要的測試經(jīng)過如下：四、 源代碼代碼實現(xiàn)工程名為:List具體函數(shù)聲明/定義如下：Ø List.h#pragma once/compile only once#ifndef _List_H_/if didn't define "_List_H_" before#define _List_H_/define

7、 "_List_H_"#include <iostream>/include header "iostream"using namespace std;/using namespace "std"class List/statement of class listprivate:/statement of private functionsclass node/statement of class nodepublic:/statement of public functionsnode *next;/tail point

8、erint key;/numbernode();/constructed functionnode(int x);/Function overloading ;/the end of class nodeint Size;/size of the listnode* getpartion(node* pBegin, node* pEnd);/get the pivotal nodevoid quicksort(node* pBeign, node* pEnd);/quicksortinline void s* a, node* b);/exchange the number between n

9、ode a and bvoid erase(node* x);/remove the node x from the listinline node* get_node(int pos);/get the posth node's pointerpublic:/statement of public functionsnode *first;/first pointerList();/constructed functionList(const List& l);/copy constructorList(int* x, int size);/use array to crea

10、te a listList();/destructorList& operator= (const List& l);/operator "=" overloadingvoid erase(int pos);/erase the node at the position of posvoid display(ostream & out);/display functionvoid insert(int pos, int val);/insert x to the pos location in the listvoid add(int* x, int

11、 size);/use array to create a listvoid push_front(int val);/insert item to the begin of the listvoid push_back(int val);/insert item to the end of the listvoid reverse();/reverse the listbool judge_sorted(char c = '>');/judge whether the list is in order bool empty();/judge whether the li

12、st is emptyint size() const;/show size of the listfriend ostream& operator<<(ostream & out, List& l); /operator "<<" overloadingList List:sort();/sortList merge_and_sort(List l);/merge two list and sort;/the end of statement of class node#endif/the end of "ifnd

13、ef"Ø List.cpp#include "List.h"/include header "List.h" List:node:node(int x):next(NULL),key(x)/constructed functionList:node:node():next(NULL)/Function overloadingList:node* List:getpartion(node* pBegin, node* pEnd)/get the pivotal nodeint key = pBegin->key;/assign t

14、he key of "pBegin" to new key node* p = pBegin;/assign the node "pBegin" to new node "p" node* q = p->next;/*assign the next node of node "pBegin"to new node "q"*/while(q != pEnd)/judge whether "q" equals "pEnd"if(q->key >

15、; key)/*if do, judge whether if the key of node "q"bigger than the key of the node "q" before*/p = p->next;/*assign the address of the next node of node "p" tothe address of node "p"*/s);/exchange the number between node p and q/the end of if statementq = q

16、->next;/*assign the address of the next node of node "q" tothe address of node "q"*/the end of while statementswap(p, pBegin);/exchange the number between node p and pBeginreturn p;/return node* p/the end of function "getpartion"inline void List:s* a, node* b)/*excha

17、nge the number(not the node) between node a and b*/int temp = a->key;/*define number, "temp", as a middle section,assign the key of "a" to temp*/a->key = b->key;/assign the key of "b" to the key of "a"b->key = temp;/assign temp to the key of "

18、b" /the end of function "swap"void List:erase(node* x)/remove the node at the right of node "x" from the listif(Size = 1);/*judge the Size whether equals oneif do, go to line 56； if not, go next*/else if(x->next = NULL);/*judge whether the node is the last node of the lis

19、tif do, go to line 56； if not go next*/else/else statementif(first = x)/*judge the address of node "first" whether equals the address of node "x"*/first = x->next;/*if do, assign the address of which the next node of node "x" to "first"*/else/else statement

20、node *temp = first;/define node, "temp", as a middle sectionwhile(temp != x)/*judge the address of "temp" whether not equals the adress of "x"*/temp = temp->next;/*assign the address of which the next node of node "temp" to the address of the node "tem

21、p"*/temp->next = x->next;/*assign the address of which the next node of node “x” to the address of which the next node of node "temp"*/the end of else statement(line 52)/the end of else statement(line 47)delete x;/delete the node "x"x = NULL;/assign NULL to "x&quo

22、t;Size-;/size minus one/the end of "erase(node*)"inline List:node* List:get_node(int pos)/get the posth node's pointerif(pos > Size | pos < 0)/exceptional handlingcerr << "List:index range errorn"/print exceptional statementexit(1);/exit the program/end ifnode *x

23、= first;/*declare *x, assign the adress of node "first"to the address of node "x"*/while(pos > 0)/judge whether pos bigger than zerox = x->next;/*if do, the pointer of "x" points to the pointer of the next node of "x"*/pos-;/pos minus one/the end of whil

24、e statementreturn x;/return *x/the end of function get_nodeList:List(const List& l)/copy constructorfirst = new node(l.first->key);/*create a new node to the pointer "first", the value of the node equals to the value of the fist node oflist "l"*/node* p = l.first->next,

25、 *q = first;/*define pointer "p" points to the next node of which is the first node of the list "l", pointer "q" points to the first pointer of this list*/while(p != NULL)/judge whether "p" is nonenode *a = new node(p->key);/create a new node and assign the

26、 key of node "p" to itq->next = a;/the pointer "next" in node "q" points to node "a"q = q->next;/the pointer "q" move to the nextp = p->next;/the pointer "p" move to the next/the end of while statementq->next = NULL;/let the poi

27、nter "next" in the last node null Size = l.size();/let Size equals the size of list "l"/the end of copy constructorList:List(int* x, int size)/use array to create a listif(size = 0)/judge whether size equals zerofirst = new node();/if do, create a null node to node "first&qu

28、ot;else/else statementfirst = new node(x0);/create a node which value is x0 to node "first"node* q = first;/create a pointer "q" points to first for(int i = 1; i < size; i+)/*int i from 1 to size-1, which means the subscriptof array "x"*/node *a = new node(xi);/creat

29、e a node which value is xi to node "a"q->next = a;/the pointer "next" in node "q" points to node "a"q = q->next;/the pointer "q" move to the next/the end of loopq->next = NULL;/let the pointer "next" in the last node nullSize = siz

30、e;/assign size to Size /the end of overloading constructorList:List()/constructed functionfirst = new node();/create a null node to node "first"first->next = NULL;/assign the pointer "next" to nullSize = 0;/assign zero to Size/the end of constructorList:List()/destructornode*

31、p;/define a node pointer "p"while(first != NULL)/judge whether first is not nullp = first;/if do, let p equals to firstfirst = first->next;/first move to the nextdelete p;/delete node p/the end of while statement/the end of destructorvoid List:erase(int pos)/erase the node at the positi

32、on of poserase(get_node(pos-1);/*call function "get_node(int)" and than call function "erase(node*)"*/the end of functionvoid List:display(ostream & out)/display functionnode *p = first;/define a node pointer "p" equals to "first"int cnt = Size;/*define nu

33、mber, "cnt", as a middle section,assign Size to temp*/while(cnt-)/whether cnt != 0out << p->key;/-if do, output-if(cnt != 0)/-all list number-out << ' '/-in order which-p = p->next;/-likes "x1 x2 x3 ." /the end of while statement/the end of function &quo

34、t;display"void List:add(int* x, int size)/use array to create a listif(size = 0);/judge whether size equals zeroelse/else statementfirst->key = x0;/the key of node "first" equals x0node* q = first;/create a pointer "q" points to first for(int i = 1; i < size; i+)/*int

35、i from 1 to size-1, which means the subscriptof array "x"*/node *a = new node(xi);/create a node which value is xi to node "a"q->next = a;/the pointer "next" in node "q" points to node "a"q = q->next;/the pointer "q" move to the next/

36、the end of loopq->next = NULL;/let the pointer "next" in the last node nullSize = size;/assign size to Size /the end of function "add"void List:insert(int pos, int val)/insert x to the pos location in the listif(Size = 0)/if Size = 0first->key = val;/*let the key of the poi

37、nter "next" in node "first"equals to val*/Size = 1;/Size equals to 1return;/the end of insert function/the end of if statementnode *x = get_node(pos-1);/*call function "get_node(int)" to get the (pos-1)th node, assign it to the pointer "x"*/node *a = new node(

38、val);/create a node which value is val to node "a"if(x->next = NULL)/judge whether x is the last node in the listx->next = a;/the next pointer in node "x" equals to node "a"a->next = NULL;/the next pointer in node "a" equals to null/end ifelse/else st

39、atementa->next = x->next;/*the next pointer in node "a" equals tothe next pointer in node "a"*/x->next = a;/the next pointer in node "x" equals to node "a"/the end of else statementSize+;/Size plus one/the end of insert functionvoid List:push_front(in

40、t val)/insert item to the begin of the listinsert( 1, val);/*call function "insert" and addthe node as the second node of the list*/s, first->next);/s first two numbers in the list/the end of the functionvoid List:push_back(int val)/insert item to the end of the listinsert( Size, val);/

41、*call function "insert" and addthe node as the last node of the list*/the end of the functionvoid List:reverse()/reverse the listnode *q = first, *r, *temp = NULL;/*pointer "q" equals to first, "temp" equals tonull, and define node pointer "r"*/while(1)/exchan

42、ge all nodes' head pointer and tail pointer r = q->next;/pointer "r" points to the next node of node "q"q->next = temp;/the next node of node "q" equals to "temp"if(r = NULL)/judge whether "r" is the next pointer in end of node first = q;/l

43、et the last node to be the first onebreak;/break loop/end iftemp = q;/let "temp" equals "q"q = r;/let "q" equals "r"/the end of while statement/the end of function "reverse"bool List:judge_sorted(char c)/judge whether the list is in order int t = fir

44、st->key;/*define number, "t", as a middle section,and assign the key of node "first" to t*/node* p = first->next;/*define node pointer "p" points the next node of node first*/if(c = '<')/judge whether is in proper order or in reverse orderwhile(p != NUL

45、L)/in proper order:if(p->key > t)/once if "p->key" bigger than "t"return false;/reutrn falset = p->key;/let "t" equals to "p->key"p = p->next;/"p" move to the next/the end of while statement/end ifelse/else statementwhile(p != NULL)

46、/in reverse order:if(t < p->key)/once if "p->key" smalleer than "t"return false;/reutrn falset = p->key;/let "t" equals to "p->key"p = p->next;/"p" move to the next/the end of while statement/the end of else statementreturn true;/re

47、turn true/the end of the functionbool List:empty()/judge whether the list is emptyreturn Size = 0;/return whether the size of the list is zero/the end of the functionint List:size() const/show size of the listreturn Size;/return the size of the list/the end of function "size()"ostream&

48、 operator<< (ostream & out, List & l)/operator "<<" overloadingl.display(out);/call function "display(ostream&)"return out;/return ostream&/the end of the functionList& List:operator= (const List& l)/operator "=" overloadingfirst = ne

49、w node(l.first->key);/*create a new node to the pointer "first", the value ofthe node equals to the value of the fist node of list "l"*/node* p = l.first->next, *q = first;/*define pointer "p" points to the next node of whichis the first node of the list "l&q

50、uot;, pointer "q" points to the first pointer of this list*/while(p != NULL)/judge whether "p" is nonenode *a = new node(p->key);/create a new node and assign the key of node "p" to itq->next = a;/the pointer "next" in node "q" points to node &

51、quot;a"q = q->next;/the pointer "q" move to the nextp = p->next;/the pointer "p" move to the next/the end of while statementq->next = NULL;/let the pointer "next" in the last node null Size = l.size();/let Size equals the size of list "l"return *

52、this;/return *this/the end of operator "=" overloading functionvoid List:quicksort(node* pBeign, node* pEnd)/quicksortif(pBeign != pEnd)/judge whether "pBegin" equals to "pEnd"node* partion = getpartion(pBeign,pEnd);/get the pivotal node between "pBegin" and &

53、quot;pEnd"quicksort(pBeign,partion);/call quicksort(sort from "pBeign" to "partion")quicksort(partion->next,pEnd);/call quicksort(sort from "partion->next" to "pEnd")/end if/end quicksortList List:sort()/sortList l(*this);/call copy constructorl.qui

54、cksort(l.first, NULL);/call quicksort to make l in reverse orderreturn l;/return l/the end of sort functionList List:merge_and_sort(List l)/merge two list and sortList ll;/define list "ll"if(!judge_sorted()/jugdge the list whether is sortedll = sort();/*if not, sort first(not chage the ori

55、ginal list),assign the sorted(in reverse order) list to "ll"*/else/if do,ll = *this;/assign "*this" to "ll"if(!l.judge_sorted()/judge the list l whether is sortedl = l.sort();/* sort first(not chage the original list),assign the sorted(in reverse order) list to "l"*/node *a = ll.first, *b = l.first;/*define node pointer "a" po