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

2015/2016(1)实验题目 List类成员函数拓展 学生姓名 韩笑 学生学号 201426811704 学生班级 计算机+自动化1402班 任课教师 * 提交日期 2015-11-15 计算机科学与技术学院（软件学院）实验报告一、 题目的内容l 将A1和B1中的数据导入链表中，形成链表A2和B2，并打印各自链表元素；l 将链表A2和B2中的元素各自排序（从大到小），形成链表A3和B3，并打印各自链表元素。l 合并链表A3，B3，合并后的链表C的元素从大到小排列，并打印链表C。对于给定的整数n，编写一个算法把新的节点插入到链表中第n个节点之后的位置，该链表的第一个节点由first指向。二、 做题思路及设计分析题目：作业中共有三题，都是基于链表并对其函数进行扩充，链表类在前一次实验中已经编写过了，因此本次实验只需在已有链表类的基础上增加成员函数即可。List 类：在本实验中不再重复描述，大致结构框架如下NextNode节点示意图：KeyPreList示意图： 第 一 问：函数名定为add，并在构造函数中增加对数组的重载，从头节点first开始往后遍历，由于如果利用push_back函数在每插入一元素时都会对链表进行一次遍历，在时间效率上不高，因此不直接采用push_back函数而直接在循环过程中保留上次插入结点的位置，与上次插入的结点后直接插入结点，代码如下（详细含义见第四部分代码注释）：void add(int* x, int size)if(size = 0)first = new node();elsefirst = new node(x0); which value is x0 to node firstnode* q = first;/create a pointer q points to first for(int i = 1; i next = a;q = q-next;q-next = NULL;Size = size;List(int* x, int size)if(size = 0);elsefirst-key = x0;node* q = first; for(int i = 1; i next = a;q = q-next;q-next = NULL;Size = size;第 二 问：函数名定为sort，先复制构造新的链表，利用快速排序实现对新链表的排序，快排最核心的思想就是划分，确定一个枢轴元素(pivot)，每一趟划分的目的就是把待排序列分为两部分，前一部分比枢轴小(序列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,先判断两链表是否已排好序，若没有，则先调用sort函数对其进行排序（此步骤对于本题目可删，但为保留程序可拓展性因此保留），之后创建两个结点依次对应两链表的first结点，从大到小依次通过push_back函数插入新建链表中，并返回该新建链表，具体代码见第四部分。三、 程序调试、测试、运行记录 主要的测试经过如下：四、 源代码代码实现工程名为:List具体函数声明/定义如下： List.h#pragma once/compile only once#ifndef _List_H_/if didnt define _List_H_ before#define _List_H_/define _List_H_#include /include header iostreamusing namespace std;/using namespace stdclass List/statement of class listprivate:/statement of private functionsclass node/statement of class nodepublic:/statement of public functionsnode *next;/tail pointerint 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 swap(node* a, node* b);/exchange the number between node a and bvoid erase(node* x);/remove the node x from the listinline node* get_node(int pos);/get the posth nodes pointerpublic:/statement of public functionsnode *first;/first pointerList();/constructed functionList(const List& l);/copy constructorList(int* x, int size);/use array to create 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 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 list is emptyint size() const;/show size of the listfriend ostream& operator(ostream & out, List& l); /operator key;/assign the 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 pBeginto new node q*/while(q != pEnd)/judge whether q equals pEndif(q-key key)/*if do, judge whether if the key of node qbigger 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*/swap(p,q);/exchange the number between node p and q/the end of if statementq = q-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 getpartioninline void List:swap(node* a, node* b)/*exchange 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 ab-key = temp;/assign temp to the key of b /the end of function swapvoid 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 listif 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 statementnode *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 temp*/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 xx = NULL;/assign NULL to xSize-;/size minus one/the end of erase(node*)inline List:node* List:get_node(int pos)/get the posth nodes pointerif(pos Size | pos 0)/exceptional handlingcerr 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 while 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, *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 key of node p to itq-next = a;/the pointer next in node q points to node aq = 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/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 firstelse/else statementfirst = new node(x0);/create a node which value is x0 to node firstnode* q = first;/create a pointer q points to first for(int i = 1; i next = a;/the pointer next in node q points to node aq = q-next;/the pointer q move to the next/the end of loopq-next = NULL;/let the pointer next in the last node nullSize = size;/assign size to Size /the end of overloading constructorList:List()/constructed functionfirst = new node();/create a null node to node firstfirst-next = NULL;/assign the pointer next to nullSize = 0;/assign zero to Size/the end of constructorList:List()/destructornode* p;/define a node pointer pwhile(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 position 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 firstint cnt = Size;/*define number, cnt, as a middle section,assign Size to temp*/while(cnt-)/whether cnt != 0out key;/-if do, output-if(cnt != 0)/-all list number-out next;/-likes x1 x2 x3 . /the end of while statement/the end of function displayvoid 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 next = a;/the pointer next in node q points to node aq = q-next;/the pointer q move to the next/the end of loopq-next = NULL;/let the pointer next in the last node nullSize = size;/assign size to Size /the end of function addvoid 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 pointer next in node firstequals 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(val);/create a node which value is val to node aif(x-next = NULL)/judge whether x is the last node in the listx-next = a;/the next pointer in node x equals to node aa-next = NULL;/the next pointer in node a equals to null/end ifelse/else statementa-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(int val)/insert item to the begin of the listinsert( 1, val);/*call function insert and addthe node as the second node of the list*/swap(first, first-next);/swap the 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);/*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)/exchange all nodes head pointer and tail pointer r = q-next;/pointer r points to the next node of node qq-next = temp;/the next node of node q equals to tempif(r = NULL)/judge whether r is the next pointer in end of node first = q;/let the last node to be the first onebreak;/break loop/end iftemp = q;/let temp equals qq = r;/let q equals r/the end of while statement/the end of function reversebool List:judge_sorted(char c)/judge whether the list is in order int t = first-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 = key t)/once if p-key bigger than treturn false;/reutrn falset = p-key;/let t equals to p-keyp = p-next;/p move to the next/the end of while statement/end ifelse/else statementwhile(p != NULL)/in reverse order:if(t key)/once if p-key smalleer than treturn false;/reutrn falset = p-key;/let t equals to p-keyp = p-next;/p move to the next/the end of while statement/the end of else statementreturn true;/return 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& operator (ostream & out, List & l)/operator 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, 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 aq = 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 lreturn *this;/return *this/the end of operator = overloading functionvoid List:quicksort(node* pBeign, node* pEnd)/quicksortif(pBeign != pEnd)/judge whether pBegin equals to pEndnode* partion = getpartion(pBeign,pEnd);/get the pivotal node between pBegin and pEndquicksort(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.quicksort(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 llif(!judge_sorted()/jugdge the list whether is sortedll = sort();/*if not, sort first(not chage the original list),assign the sorted(in reverse order) list to ll*/else/if do,ll = *this;/assign *this to llif(!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*/nod