#include <iostream> //引入輸入輸出流
using namespace std;
template <typename DataType>
struct Node
{
DataType data; //資料域
Node<DataType> *next; //指標域
};
template <typename DataType>
class LinkList
{
public:
LinkList( ); //無參建構式，建立只有頭結點的空鏈表
LinkList(DataType a[ ], int n); //有參建構式，建立有n個元素的單鏈表
~LinkList( ); //解構式
int Length( ); //求單鏈表的長度
int Empety();
DataType Get(int i); //按位查找。查找第i個結點的元素值
int Locate(DataType x); //按值查找。查找值為x的元素序號
void Insert(int i, DataType x); //插入操作，第i個位置插入值為x的結點
DataType Delete(int i); //洗掉操作，洗掉第i個結點
void PrintList( ); //遍歷操作，按序號依次輸出各元素
private:
Node<DataType> *first; //單鏈表的頭指標
};
template <typename DataType>
LinkList<DataType> :: LinkList( )
{
first = new Node<DataType>; //生成頭結點
first->next = nullptr; //頭結點的指標域置空
}
template <class DataType>
LinkList<DataType> :: ~LinkList( )
{
Node<DataType> *q = NULL;
while (first != NULL) //釋放單鏈表的每一個結點的存盤空間
{
q = first; //暫存被釋放結點
first = first->next; // first指向被釋放結點的下一個結點
delete q;
}
}
template <typename DataType>
int LinkList<DataType> :: Empety()
{
if(first->next == nullptr)
return 1;
else
return 0;
}
template <typename DataType>
void LinkList<DataType> :: PrintList( )
{
Node<DataType> *p = first->next; //作業指標p初始化
while (p != nullptr)
{
cout << p->data << "\t";
p = p->next; //作業指標p后移，注意不能寫作p++
}
}
template <typename DataType>
int LinkList<DataType> :: Length( )
{
Node<DataType> *p = first->next; //作業指標p初始化為開始接點
int count = 0; //累加器count初始化
while (p != nullptr)
{
p = p->next;
count++;
}
return count; //注意count的初始化和回傳值之間的關系
}
template <typename DataType>
DataType LinkList<DataType> :: Get(int i)
{
Node<DataType> *p = first->next; //作業指標p初始化
int count = 1; //累加器count初始化
while (p != nullptr && count < i)
{
p = p->next; //作業指標p后移
count++;
}
if (p == nullptr) throw "位置";
else return p->data;
}
template <typename DataType>
int LinkList<DataType> :: Locate(DataType x)
{
Node<DataType> *p = first->next; //作業指標p初始化
int count = 1; //累加器count初始化
while (p != nullptr)
{
if (p->data == x) return count; //查找成功，結束函式并回傳序號
p = p->next;
count++;
}
return 0; //退出回圈表明查找失敗
}
template <typename DataType>
void LinkList<DataType> :: Insert(int i, DataType x)
{
Node<DataType> *p = first, *s = nullptr ; //作業指標p初始化
int count = 0;
while (p != nullptr && count < i - 1) //查找第i – 1個結點
{
p = p->next; //作業指標p后移
count++;
}
if (p == nullptr) throw "位置"; //沒有找到第i – 1個結點
else {
s = new Node<DataType>; s->data = x; //申請結點s，資料域為x
s->next = p->next; p->next = s; //將結點s插入到結點p之后
}
}
// 頭插法構造
//template <typename DataType>
//LinkList<DataType> :: LinkList(DataType a[ ], int n)
//{
// first = new Node<DataType>; first->next = nullptr; //初始化一個空鏈表
// for (int i = 0; i < n; i++)
// {
// Node<DataType> *s;
// s = new Node<DataType>; s->data = a[i];
// s->next = first->next; first->next = s; //將結點s插入到頭結點之后
// }
//}
template <typename DataType>
LinkList<DataType> :: LinkList(DataType a[ ], int n)
{
first = new Node<DataType>; //生成頭結點
Node<DataType> *r = first, *s = nullptr; //尾指標初始化
for (int i = 0; i < n; i++)
{
s = new Node<DataType>; s->data = a[i];
r->next = s; r = s; //將結點s插入到終端結點之后
}
r->next = nullptr; //單鏈表建立完畢，將終端結點的指標域置空
}
template <typename DataType>
DataType LinkList<DataType> :: Delete(int i)
{
DataType x;
Node<DataType> *p = first, *q = nullptr; //作業指標p指向頭結點
int count = 0;
while (p != nullptr && count < i - 1) //查找第i-1個結點
{
p = p->next;
count++;
}
if (p == nullptr || p->next == nullptr) //結點p不存在或p的后繼結點不存在
throw "位置";
else {
q = p->next; x = q->data; //暫存被刪結點
p->next = q->next; //摘鏈
delete q;
return x;
}
}
int main( )
{
int r[5] = {1, 2, 3, 4, 5}, i, x;
LinkList<int> L（r, 5）;
cout << "當前線性表的資料為：";
L.PrintList( ); //輸出當前鏈表1 2 3 4 5
cout << endl;
try
{
L.Insert(2, 8); //在第2個位置插入值為8的結點
cout << "執行插入操作后資料為：";
L.PrintList( ); //輸出插入后鏈表1 8 2 3 4 5
cout << endl;
} catch(char* str)
{
cout << str << endl;
}
cout << "當前單鏈表的長度為：" << L.Length( ) << endl; //輸出單鏈表長度6
cout << "請輸入查找的元素值：";
cin >> x;
i = L.Locate(x);
if (1 <= i) cout << "元素" << x << "的元素位置為：" << i << endl;
else cout << "單鏈表中沒有元素" << x << endl;
try
{
cout << "請輸入要洗掉第幾個元素：";
cin >> i;
x = L.Delete(i); //洗掉第i個元素
cout << "洗掉的元素值是" << x << "執行洗掉操作后資料為：";
L.PrintList( ); //輸出洗掉后鏈表
} catch(char* str)
{
cout << str << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/152888.html
標籤：C++ 語言
上一篇：來自一個小白的QT大作業求助