北京邮电大学 数据结构 实验一 带头结点的单链表构造

数据结构实验报告

实验名称： 实验1——单链表的构造 学生姓名： XXXXNB 班 级： XXXX 班内序号： 学 号：XXXX 日 期： XXXXX

1．实验要求

根据线性表的抽象数据类型的定义，完成带头结点的单链表的基本功能。 单链表的基本功能：

1、构造：使用头插法、尾插法两种方法

2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁

7、其他：可自行定义

编写测试main()函数测试线性表的正确性。

2. 程序分

编程完成单链表的一般性功能如单链表的构造：使用头插法、尾插法两种方法插入：

要求建立的链表按照关键字从小到大有序，删除，查找，获取链表长度，销毁

用《数据结构》中的相关思想结合C++语言基本知识编写一个单链表结构。本程序为使用方便，几乎不用特殊的命令，只需按提示输入即可，适合更多的用户使用。

2.1 存储结构

单链表的存储结构：

第1页

北京邮电大学信息与通信工程学院

2.2 关键算法分析

1.头插法

自然语言描述：a.在堆中建立新结点

b.将a[i]写入到新结点的数据域 c.修改新结点的指针域

d.修改头结点的指针域,将新结点加入链表中 //在构建之初为了链表的美观性构造，进行了排序 代码描述：

//头插法构造函数 template

LinkList::LinkList(T a[], int n) {

for (int i = n - 1; i >= 1; i--)//冒泡排序，对数组进行从小到大排序 {

for (int j = 0; j < i; j++) { }

第2页

if (a[j]>a[j + 1]) { }

T t = a[j + 1]; a[j + 1] = a[j]; a[j] = t;

北京邮电大学信息与通信工程学院

}

}

front = new Node < T >;//为头指针申请堆空间 front->next = NULL;//构造空单链表 for (int i = n - 1; i >= 0; i--) { }

Node*s = new Node < T >;//建立新结点 s->data = a[i];//将a[i]写入新结点的数据域 s->next = front->next;//修改新结点的指针域

front->next = s;//修改头结点的指针域，将新结点加入到链表中

2.尾插法

自然语言描述：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 代码描述:

//尾插法构造函数 template

LinkList::LinkList(T a[], int n) {

front = new Node < T > ;

Node*r = front;//命名一个新变量进行转换 for (int i = 0; i < n; i++) {

Node*s = new Node < T > ;

第3页

北京邮电大学信息与通信工程学院

s->data = a[i]; r->next = s; r = s; }

r->next = NULL; }

时间复杂度：O(n)

3.析构函数

自然语言描述：a.新建立一个指针，指向头结点 b.移动a中建立的指针 c.逐个释放指针 代码描述: template

LinkList::~LinkList()//析构函数，销毁链表 {

Node * p = front; while(p) { }

第4页

front = p; p = p->next; delete front;

北京邮电大学信息与通信工程学院

}

4.按位查找函数

自然语言描述: a.初始化工作指针p和计数器j，p指向第一个结点，j=1 b.循环以下操作，直到p为空或者j等于1 b1：p指向下一个结点 b2：j加1

c.若p为空，说明第i个元素不存在，抛出异常

d.否则，说明p指向的元素就是所查找的元素，返回元素地址 代码描述: template

Node* LinkList::Get(int i)//按位查找 {

Node * p = front; int j=0; while(p) {

if(jp = p->next; j++;

}

if(!p) throw\"查找位置非法\"; else return p;

}

时间复杂度：O(n)

第5页

北京邮电大学信息与通信工程学院

5.按值查找函数

自然语言描述：a.初始化工作指针p和计数器j，p指向第一个结点，j=1 b.循环以下操作，找到这个元素或者p指向最后一个结点 b1.判断p指向的结点是不是要查找的值，如果是，返回j; b2.否则p指向下一个结点,并且j的值加一

c.如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息 代码描述: template

int LinkList::Locate(T x)//按值查找 {

Node * p = front->next; int j = 1; while(p) { } return -1;

if(p->data == x) return j; else {

p = p->next;

j++; }

}

时间复杂度：O(n) 6.插入函数

自然语言描述： a.在堆中建立新结点

第6页

北京邮电大学信息与通信工程学院

b.将要插入的结点的数据写入到新结点的数据域 c.修改新结点的指针域

d.修改前一个指针的指针域，使其指向新插入的结点的位置 代码描述: template

void LinkList::Insert(int i,T x)//插入函数 {

Node * p = Get(i-1); if(p) { }

else throw\"插入位置非法\";

Node * s = new Node; s->data = x; s->next = p->next; p->next = s;

}

时间复杂度：O(n) 7.按位删除函数

自然语言描述：a.从第一个结点开始，查找要删除的位数i前一个位置i-1的结点 b.设q指向第i个元素 c.将q元素从链表中删除 d.保存q元素的数据 e.释放q元素 代码描述: template

T LinkList::Delete(int i)//删除函数 {

Node *p = Get(i-1); Node *q = p->next;

第7页

北京邮电大学信息与通信工程学院

T x=q->data; }

p->next = q->next; delete q; return x;

8.遍历打印函数

自然语言描述: a.判断该链表是否为空链表，如果是，报错 b.如果不是空链表，新建立一个temp指针 c.将temp指针指向头结点 d.打印temp指针的data域

e.逐个往后移动temp指针，直到temp指针的指向的指针的next域为空 代码描述: template

void LinkList::PrintList()//打印链表 { }

第8页

Node * p = front->next; while(p) { }

cout<cout<data<<' '; p = p->next;

北京邮电大学信息与通信工程学院

9.获取链表长度函数

自然语言描述： a.判断该链表是否为空链表，如果是，输出长度0

b.如果不是空链表，新建立一个temp指针，初始化整形数n为0 c.将temp指针指向头结点

d.判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n

e.使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n 代码描述: template

int LinkList::GetLength()//分析链表长度 { }

Node * p = front; int i=0; while(p) { } return i-1;

p = p->next; i++;

2.3 其他

异常处理

采用try catch 函数处理异常 如在插入时的异常处理：

template

void LinkList::Insert(int i, T x) {

Node*p = front;

if (i != 1) p = Get(i - 1); try

第9页

北京邮电大学信息与通信工程学院

}

{ }

catch (int i) { }

cout << \"插入到位置 \" << i << \" 处\" << \"为错误位置\"<else throw i;

Node*s = new Node < T > ; s->data = x; s->next = p->next; p->next = s;

3. 程序运行结果

主函数流程图： 建立 插入 否 测试截图：

初始化链表，菜单创建

开始 创建单链表菜单 初始化 查找 删除 获取长度 退出 是否退出 是 结束 第10页

北京邮电大学信息与通信工程学院

执行功能：

第11页

北京邮电大学信息与通信工程学院

4. 总结

.调试时出现了一些问题如：异常抛出的处理，书中并未很好的提及异常处理，通过查阅资料，选择用try catch 函数对解决。 2.心得体会

了解了单链表的基本的操作函数实现，对链式存储结构有了较好的认识 3.下一步的改进

可以增加完善报错机制，增强程序的健壮性

完整源代码：

//单链表的构造 #include using namespace std; template struct Node { };

template class LinkList { public:

LinkList(){ front = new Node ; front->next = NULL; }//无参构造函数 T data;//数据域

struct Node*next;//指针域

第12页

北京邮电大学信息与通信工程学院

};

LinkList(T a[], int n);//有参构造函数，使用含有n个元素的数组a初始化单链表 ~LinkList();

//析构函数,(其在void main 函数最后一句语句之后自动执行，旨在//按次序遍历线性表中的各个数据元素 //获取线性表的长度

//获取线性表第i个位置上的元素结点地址 //查找线性表中值为x的元素，找到后返回其位置

释放栈空间)

void PrintList(); int GetLength(); int Locate(T x);

Node * Get(int i);

void Insert(int i, T x);//后插，在线性表的第i个位置上插入值为x的新元素 void insert(int i, T x);//前插，在线性表的第i个位置上插入值为x的新元素 T Delete(int i); Node * front;

//删除线性表第i个元素，并将该元素返回 //头指针

private:

//头插法构造函数 template

LinkList::LinkList(T a[], int n) { }

//尾插法构造函数 //template

//LinkList::LinkList(T a[], int n) //{

// front = new Node < T > ;

for (int i = n - 1; i >= 1; i--)//冒泡排序，对数组进行从小到大排序 { }

front = new Node < T >;//为头指针申请堆空间 front->next = NULL;//构造空单链表 for (int i = n - 1; i >= 0; i--) { }

Node*s = new Node < T >;//建立新结点 s->data = a[i];//将a[i]写入新结点的数据域 s->next = front->next;//修改新结点的指针域

front->next = s;//修改头结点的指针域，将新结点加入到链表中 for (int j = 0; j < i; j++) { }

if (a[j]>a[j + 1]) { }

T t = a[j + 1]; a[j + 1] = a[j]; a[j] = t;

第13页

北京邮电大学信息与通信工程学院

// Node*r = front;//命名一个新变量进行转换 // for (int i = 0; i < n; i++) // {

//Node*s = new Node < T > ; //s->data = a[i]; //r->next = s; //r = s; //}

//r->next = NULL; //}

template

void LinkList::PrintList()//遍历线性表元素并打印到屏幕 { }

template

LinkList::~LinkList()//析构函数 { }

template

Node * LinkList::Get(int i)//获取线性表第i个位置上的元素结点地址 { }

Node*p = front->next; int k = 1;

while (p && (k != i)) { } return p;

p = p->next; k++;

Node*p = front;//初始化工作指针P while (p)//要释放的结点存在 { }

front = p; p = p->next;

delete front;//释放结点 Node*p = front->next; while (p) { }

cout << endl;

cout << p->data << \" \"; p = p->next;

第14页

北京邮电大学信息与通信工程学院

template

int LinkList::Locate(T x)//按值查找某元素的位置 { } //后插

template

void LinkList::Insert(int i, T x) { }

template

T LinkList::Delete(int i) {

Node*p = front;

if (i != 1) p = Get(i - 1);//若不是在第一个位置删除，获取第i-1个元素的地址 try {

if (p && (p->next)) {

Node*q = p->next;

Node*p = front;

if (i != 1) p = Get(i - 1); try { }

catch (int i) { }

cout << \"插入到位置 \" << i << \" 处\" << \"为错误位置\"<else throw i;

Node*s = new Node < T > ; s->data = x; s->next = p->next; p->next = s;

Node*p = front->next; int k = 1;

while (p&&(p->data != x)) { } return k;

p = p->next; k++;

第15页

北京邮电大学信息与通信工程学院

}

}

}

p->next = q->next; T x = q->data; delete q; return x;

else throw i;

catch (int i) { }

cout << \"删除位置 \" << i << \" 处\" << \"为错误位置\" << endl;

template

int LinkList::GetLength() { }

void main() {

int m=1;

int a[7] = { 3, 2, 1, 4, 6, 5, 7 }; LinkList list(a, 7); cout << \"排序后的链表为:\"; list.PrintList();

cout << \"\\**************************************************\" << endl

<< \"\\※ ※\" << endl << \"\\※ 对该单链表的操作 ※\" << endl << \"\\※ ※\" << endl << \"\\※ 1. 获取线性表的长度 ※\" << endl << \"\\※ ※\" << endl << \"\\※ 2. 查找值为x的元素，并返回其位置 ※\" << endl << \"\\※ ※\" << endl << \"\\※ 3. 在线性表的第i个位置上插入值为x的新元素 ※\" << endl << \"\\※ ※\" << endl << \"\\※ 4. 删除线性表第i个元素，并将该元素返回 ※\" << endl << \"\\※ ※\" << endl

<< \"\\**************************************************\" << endl << endl; Node*p = front->next; int i;

for (i = 0; p != NULL; i++) { } return i;

p = p->next;

while (m != 0)

第16页

北京邮电大学信息与通信工程学院

{

cout<< \"\\\选择你需要的功能:\"; int choice;

cin >> choice;//输入需要的功能 switch (choice) { case 1: { } { } { } }

break;

cout << \"!!无此功能项\" << endl; break; default:

cout << \"请输入想要删除的元素的位置值:\" << endl; int location_3; cin >> location_3;

int value_2 = list.Delete(location_3);

cout << \"删除的元素值为：\" << value_2 << endl; break;

case 4:// 删除线性表第i个元素，并将该元素返回

cout << \"请输入想插入的位置值：\" << endl; int location_2;//位置值 cin >> location_2;

cout << \"请输入想插入的新元素的值\" << endl; int value_1;//元素值 cin >> value_1;

list.Insert(location_2, value_1);

cout << \"执行插入操作后的链表为:\" << endl; list.PrintList(); break;

case 3://在线性表的第i个位置上插入值为x的新元素

cout << \"请输入想查找的元素的值:\" << endl; int value; cin >> value;

int location = list.Locate(value);

cout << \"该元素的位置为:\" << location << endl;

cout << \"线性表的长度为:\" << list.GetLength()<case 2://查找值为x的元素，并返回其位置

第17页

北京邮电大学信息与通信工程学院

}

}

cout << \" ※※※ 那您是否想继续？继续请输入 1 不想继续请输入 0 ※※※\" << cin >> m;

endl;

第18页