logo头像

学如逆水行舟,不进则退!!!

文章目录

数据结构单链表

本文于1195天之前发表,文中内容可能已经过时。

直接贴代码

```

#ifndef LINKLIST_H

#define LINKLIST_H

#include
using namespace std;
template
struct Node
{
T data;
Nodenext;
};
template
class LinkList
{
public:
LinkList(); //无参构造函数,建立只有头结点的空链表
LinkList(T a[], int n); //有参构造函数,建立由n个元素的单链表
~LinkList(); //析构函数
int Length(); //求单链表的长度
T Get(int i); //按位查找,查找单链表中的第i个元素的数值
int Locate(T x); //查找该元素在单链表中的位置
void Insert(int i, T x); //在第i个位置插入该元素
T Delete(int i); //删除第i个元素
void PrintList(); //打印单链表
private:
Node
first; //创建单链表的头指针
};
template
LinkList::LinkList()
{
Nodefirst; //申明头结点
first = new Node; //生成头结点
first->next = NULL; //初始化头节点
}
template
LinkList::LinkList(T a[], int n)
{
Node
r, s; //申明两个临时结点
first = new Node; //生成头结点
r = first; //尾指针初始化
for (int i = 0; i < n; i++)
{
s = new Node; //生成S结点来存储数组中对应的元素
s->data = a[i]; //将数组中对应的元素赋值到对应结点的数值部位
r->next = s;
r = s; //上两部是将s插入到终端结点之后
}
r->next = NULL;
}
template
LinkList::~LinkList()
{
Node
q = NULL; //建立一个空的结点
while (first != NULL) //该循环释放结点的存储空间
{
q = first;
first = first->next;
delete q;
}
}
template
int LinkList::Length()
{
Nodep=first->next;
int count = 0; //初始化
while (p != NULL)
{
p = p->next; //p指针后移
count++;
}
return count;
}
template
T LinkList::Get(int i)
{
Node
p = first->next;
int count = 1;
while (p != NULL&&count < i)
{
p = p->next;
count++;
}
if (p == NULL)throw”位置”;
else return p->data; //单恋表中first是空结点,不算在单链表中的,所以第一个元素是在第一个结点中的。序号是对应的
}
template
int LinkList::Locate(T x)
{
Nodep = first->next;
int count = 1; //上述初始化工作量
while (p != NULL)
{
if (p->data == x)
return count;
p = p->next;
count++;
}
return 0; //推出循环查找,表示查找失败。
}
template
void LinkList::Insert(int i, T x)
{
Node
p = first;
int count = 0; //上述初始化工作量
while (p != NULL&&count < i - 1)
{
p = p->next;
count++;
}
if (p == NULL)throw”位置”;
else
{
Nodes;
s = new Node;
s->data = x;
s->next = p->next;
p->next = s;
}
}
template
T LinkList::Delete(int i)
{
Node
p = first;
T x;
int count = 0;
while (p != NULL&&count < i - 1)
{
p = p->next;
count++;
}
if (p == NULL || p->next == NULL)throw”位置”;
else
{
Nodeq;
q = p->next; x = q->data;
p->next = q->next;
delete q; return x;
}
}
template
void LinkList::PrintList()
{
Node
p;
p = first->next;
while (p != NULL)
{
cout << p->data<<”->”;
p = p->next;
}
}

#endif

*******************************************************************

#include”LinkList.h”

#include

#include
using namespace std;
void main()
{
int a[10] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };
int ch;
LinkListzxh(a,10);
cout << “生成的单链表为:”;
zxh.PrintList();
cout << endl;
cout << “1-求长度”<<setw(17);
cout << “2-按位查找” << endl;
cout << “3-按值查找” << setw(15);
cout << “4-插入操作” << endl;
cout << “5-删除操作” << setw(15);
cout << “6-遍历操作” << endl;
cout << “请输入您想进行的操作:”;
cin >> ch;
switch (ch)
{
case 1:zxh.Length(); break;
case 2:int m1;
cout << “请输入您想按位查找的位号:”;
cin >> m1;
zxh.Get(m1); break;
case 3:
int m2;
cout << “请输入您想查找的值:”;
cin >> m2;
zxh.Locate(m2); break;
case 4:int m3, m4;
cout << “请输入想插入的位置:”;
cin >> m3;
cout << “请输入想插入的元素:”;
cin >> m4;
zxh.Insert(m3, m4); break;
case 5:
int m5;
cout << “请输入想删除的位置:”;
cin >> m5;
zxh.Delete(m5); break;
case 6:
zxh.PrintList();
}
}
```
这个单恋表中我自己刚才测试了一下。基本上没什么大问题。但是好像在球长度的时候就不正确了。希望大家可以提出指证。

上一篇
坚持原创技术分享,您的支持将鼓励我继续创作!