实验1线性表的物理实现
分别提交两个附件：
1：实验1的日志报告文件，提交规范，参看课程规范。
2：实验1的源码包。（文件名也要规范，可以参考报告文件的格式）
实验一线性表实验日志
基于顺序表的ADT实现
【2020.10.20】
任务：创建新的工程，将学习通中的代码模板对应导入到”list.h”、“AList.h”、“main.cpp”文件中。编译通过。理解三个文件分别的作用，理解“AList.h”中每个具体函数的实现方式和使用方法。
【2020.10.21】
任务：在理解线性表的各个函数后，自己完成main.cpp文件里的字符串分类统计功能。考虑到工作量问题，先实现了统计各类字符串个数的功能。
【2020.10.22】
任务：在线性表能够实现统计各类字符串个数的基础上，添加将线性表中的数字依次删除的功能。
遇到问题：在添加删除数字的功能后，程序运行出现错误。运行结果如下图：
错误原因：根据反馈信息提示，问题出在remove函数。经过初步分析，错误原因在于删除元素后线性表的长度计数未-1，对线性表进行遍历时超出了线性表的长度范围，导致报错。
改正方法：每删除一个数字，不仅要将当前位置往前走一个，线性表的长度值还要减一，预防超出范围。更改后的代码和运行截图如下：
可以发现已经实现删除数字的功能。
至此，main.cpp文件已经完成要求的统计各类字符串的功能和删去数字后重新输出线性表的功能。
基于链表的ADT实现
【2020.10.22】
任务：创建新的工程，将学习通中的代码模板对应导入到”link.h”、“list.h”、“LList.h”、“main.cpp”文件中。
遇到问题：此时编译报错，错误如下：
出错原因：经过提示发现，语句中部分变量未隔开，导致程序无法识别。增加空格隔开变量即可。
【2020.10.23】
任务：理解ADT的链表实现方式，并在此基础上完成main函数计数以及删除数字的两个功能。
出现问题一：编译无法通过。报错截图如下：
出错原因：报错显示Link类重复定义了。进过检查发现，”Link.h”头文件缺少了宏定义，造成了Link类的重复定义。
修改：在”Link.h”头文件中增加宏定义。如图：
修改后报错如下：
可以发现重复定义Link类的错误不见了。
出错原因二：编译器显示无法建立Line，因为LList是个虚基类。经过检查发现，是因为”LList.h”头文件中未实现”list.h”文件中声明的int length() const 函数和int currPos() const 函数，导致LList还是一个无法创建对象的虚基类。
修改：：在”LList.h”头文件中实现int length() const 函数和int currPos() const 函数。此时编译顺利通过。
至此，编译通过。进过初步测试，代码能够正常运行。运行结果如图：
【代码部分】
链表实现：
link.h
#include <iostream>
#ifndef LINK_H
#define LINK_H
template <typename E> class Link {
public:
E element; // Value forthis node 结点值
Link *next;
// Pointer to next node in list 结点指针：在链表中指向下一结点
// Constructors 构造函数
Link(const E& elemval, Link* nextval =NULL)
{ element =elemval; next = nextval; }
Link(Link*nextval =NULL) { next = nextval; }
};
#endif // LINK_H
list.h
//#ifndef LIST_H_INCLUDED
//#define LIST_H_INCLUDED
#ifndef LIST_H
#define LIST_H
template <typename E> class List { // List ADT 抽象数据类型定义
private:
void operator=(const List&) {} // Protect assignment
List(const List&) {} // Protect copy constructor
public:
List() {} // Default constructor 构造函数
virtual~List() {} // Base destructor 析构函数
// Clear contents from the list, to make itempty. 清空列表中的内容
virtual void clear() = 0;
// Insert an element at the current location.
// item: The element to be inserted 在当前位置插入元素item
virtual void insert(const E& item) = 0;
// Append an element at the end of the list.
// item: The element to be appended 在表尾添加元素item
virtual void append(const E& item) = 0;
// Remove and return the current element.
// Return: the element that was removed. 删除当前元素，并将其作为返回值
virtual E remove() = 0;
// Set the current position to the start ofthe list.将当前位置设置为顺序表起始处
virtual void moveToStart() = 0;
// Set the current position to the end of thelist. 将当前位置设置为顺序表末尾
virtual void moveToEnd() = 0;
// Move the current position one step left.No change
// if already at beginning. 将当前位置左移一步，如果当前位置在首位就不变
virtual void prev() = 0;
// Move the current position one step right.No change
// if already at end. 将当前位置右移一步，如果当前位置在末尾就不变
virtual void next()= 0;
// Return: The number of elements in thelist. 返回列表当前的元素个数
virtual int length() const = 0;
// Return: The position of the currentelement. 返回当前元素的位置
virtual int currPos() const = 0;
// Set current position.
// pos: The position to make current. 将当前位置设置为pos
virtual void moveToPos(int pos) = 0;
// Return: The current element. 返回当前元素
virtual const E& getValue() const = 0;
};
#endif
//#endif // LIST_H_INCLUDED
LList.h
#include"list.h"
#include"link.h"
#include<assert.h>
#ifndef LLIST_H_INCLUDED
#define LLIST_H_INCLUDED
//This is the declaration for LList. It is split into two parts
//because it is too big to fit on one book page
//Linked list implementation
using namespace std;
template <typename E> class LList:public List<E> {
private:
Link<E>* head; // Pointer to list header 指向链表头结点
Link<E>* tail; // Pointer to last element 指向链表最后一个结点
Link<E>* curr; // Access to current element 指向当前元素
int cnt; // Size of list 当前列表大小
void init() { // Intialization helper method 初始化
curr = tail = head = new Link<E>;
cnt = 0;
}
void removeall() {
while(head != NULL) {
curr = head;
head = head->next;
delete curr;
}
}
public:
LList(int size=100) { init(); } // Constructor 构造函数
~LList() { removeall(); } // Destructor 析构函数
void print() const; // Print list contents 打印列表内容
void clear() { removeall(); init(); } // Clear list清空列表
// Insert "it" atcurrent position 在当前位置插入“it”
void insert(const E& it) {
curr->next = new Link<E>(it, curr->next);
if (tail == curr) tail = curr->next; // New tail 新的尾指针
cnt++;
}
void append(const E& it) { // Append "it" to list 在列表的尾部追加“it”
tail = tail->next = new Link<E>(it, NULL);
cnt++;
}
// Remove and return current element 删除并返回当前元素
E remove() {
assert(curr->next != NULL); //"Noelement" 若当前没有元素则中断程序
E it = curr->next->element; // Remember value 保存元素值
Link<E>*ltemp = curr->next; // Remember link node保存指针域信息
if (tail == curr->next) tail = curr; // Reset tail 重置尾指针
curr->next = curr->next->next; // Remove from list从列表中删除
delete ltemp; // Reclaim space 回收空间
cnt--; // Decrement the count 当前链表长度减一
return it;
}
void moveToStart() // Place curr at list start将curr设置在链表头部
{ curr = head; }
void moveToEnd() // Place curr at list end 将curr设置在链表尾部
{curr = tail; }
// Move curr one step left; no change ifalready at front
// 将curr指针往前移一步；如果已经指向头部了就不需要改变
void prev() {
if (curr == head) return; // No previous element 若当前指针是头指针直接返回
Link<E>* temp = head;
// March down list until we findthe previous element 循环链表直到找到前一个元素
while (temp->next!=curr) temp=temp->next;
curr = temp;
}
// Move curr one step right; no changeif already at end
//将curr指针往后移一步；如果已经指向尾部了就不需要改变
void next()
{if (curr != tail) curr = curr->next; }
intlength() const { return cnt; } // Return length 返回当前列表大小
// Return the position of the current element 返回当前元素的位置
intcurrPos() const {
Link<E>* temp = head;
int i;
for (i=0; curr != temp; i++)
temp = temp->next;
return i;
}
// Move down list to "pos" position 向下移动到列表“pos”位置
void moveToPos(int pos) {
assert ((pos>=0)&&(pos<=cnt));//"Position out of range" 不在范围内
curr = head;
for(int i=0; i<pos; i++) curr = curr->next;
}
const E& getValue() const { // Return current element 返回当前元素
assert(curr->next != NULL);//"No value" 内容为空
return curr->next->element;
}
int length() const
{
return cnt;
}
int currPos() const
{
Link<E>* temp = head;
int i;
for(i = 0 ; curr != temp ; i++)
temp = temp->next;
return i;
}
};
#endif // LLIST_H_INCLUDED
main.c
#include "link.h"
#include "list.h"
#include "LList.h"
#include<iomanip>
#include<iostream>
#include <string.h>
using namespace std;
void print(LList<char> &A,int n);
int main()
{
LList<char> Line(100);//建立一个变量类型为char的线性表List
int char_num = 0 , number = 0 , other = 0;//char_num字母个数，number数字个数，other其他字符
char trans;//作为中转字符
while((trans = cin.get())!= '\n')//依次将字符串中的字符放入线性表
Line.append(trans);
int length_list = Line.length();
int len =length_list;
Line.moveToStart();//线性表的curr指针指向表头
for(int i = 0 ; i < len ; i++)//遍历线性表，统计各类字符的数量
{
char ch = Line.getValue();
if(ch >='0'&& ch <= '9')
{
number++;
Line.remove();
Line.prev();
length_list--;
}
else if((ch >='A'&& ch <= 'Z')||(ch >='a'&& ch <= 'z'))
char_num++;
else other++;
Line.next();
}
cout << char_num << ' ' << number << ' ' << other << endl;
print(Line,length_list);//打印修改后的线性表
return 0;
}
/***********************
*function ofprint
*打印顺序表中元素
************************/
void print(LList<char>& A,int n){
int i;
for(i=0;i<n;i++){
A.moveToPos(i);
cout<<A.getValue()<<""; //调用getValue操作得到当前元素
}
cout<<endl<<endl;
}