List类成员函数拓展实验报告

1、 2015/2016(1)实验题目 List类成员函数拓展 学生姓名 韩笑 学生学号 2 学生班级 计算机+自动化1402班 任课教师 * 提交日期 2015-11-15 计算机科学与技术学院（软件学院）14 / 15文档可自由编辑打印实验报告一、 题目的内容l 将A1和B1中的数据导入链表中，形成链表A2和B2，并打印各自链表元素；l 将链表A2和B2中的元素各自排序（从大到小），形成链表A3和B3，并打印各自链表元素。l 合并链表A3，B3，合并后的链表C的元素从大到小排列，并打印链表C。对于给定的整数n，编写一个算法把新的节点插入到链表中第n个节点之后的位置，该链表的第一个节点由firs

2、t指向。二、 做题思路及设计分析题目：作业中共有三题，都是基于链表并对其函数进行扩充，链表类在前一次实验中已经编写过了，因此本次实验只需在已有链表类的基础上增加成员函数即可。List 类：在本实验中不再重复描述，大致结构框架如下NextNode节点示意图：KeyPreList示意图： 第 一 问：函数名定为add，并在构造函数中增加对数组的重载，从头节点first开始往后遍历，由于如果利用push_back函数在每插入一元素时都会对链表进行一次遍历，在时间效率上不高，因此不直接采用push_back函数而直接在循环过程中保留上次插入结点的位置，与上次插入的结点后直接插入结点，代码如下（详细含义

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;第 二 问：函数名定为sort，先复制构造新的链表，利用快速排序实现对新链表的排序，快排最核心的思想就是划分，确定一个枢轴元素(pivot)，每一趟划分的目的就是把待排序列分为两部分，前一部分

5、比枢轴小(序列A)，后一部分比枢轴大(序列B)。经过一趟划分之后序列变为：A pivot B。以下是具体步骤：1、确定每一次划分的枢轴元素为当前待排序列的头节点。2、设置pHead和pEnd两个游标，pEnd指向序列A中的最后一个元素，初始化为枢轴本身(待排序列头节点)。让pHead遍历一遍待排序列，当所指元素比枢轴小时，将pEnd往前游一格，交换pEnd和pHead所指元素的值，这样仍能保证pEnd指向的元素是序列A中的最后一个元素。3、交换pEnd所指元素和枢轴元素的值。4、对序列A和B重复步骤14。第 三 问：函数名定为merge_and_sort,先判断两链表是否已排好序，若没有，则先

6、调用sort函数对其进行排序（此步骤对于本题目可删，但为保留程序可拓展性因此保留），之后创建两个结点依次对应两链表的first结点，从大到小依次通过push_back函数插入新建链表中，并返回该新建链表，具体代码见第四部分。三、 程序调试、测试、运行记录 主要的测试经过如下：四、 源代码代码实现工程名为:List具体函数声明/定义如下：Ø 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