单链表的c++实现

#include

using namespace std;

template

struct Node //结点定义

{

T data;

Node *next;

};

template

class Linklist

{

Node *head;

public:

Linklist(); //不含参数构造

Linklist(T a[],int i);//含参

~Linklist(); // 析构函数

int listlength();//求长度

T get(int i);//按位查找

int locate(T x);//按值查找

void Insert(int i,T item);//插入数据

T Delete(int i); //删除数据

void output();//输出

void clear();//清空

};

template

Linklist::Linklist()

{

head = new Node;

head->next = NULL;

}

template

Linklist::Linklist(T a[],int i)

{

head = new Node;

Node *p = head;

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

{

Node *s = new Node;

s->data = a[j];

p->next = s;

p = s;

}

p->next = NULL;

}

template

Linklist::~Linklist()

{

Node *p = head;

while (p)

{

Node *q = p;

p = p->next;

delete q;

}

head = NULL;

}

template

int Linklist::listlength()

{

int sum = 0;

Node *p = head->next;

while (p)

{

p = p->next;

sum++;

}

return sum;

}

template

T Linklist::get(int i)

{

Node *p = head->next;

while (--i && p)

{

p = p->next;

}

if (!p || i < 0)

{

cout << "位置非法" << endl;

exit(1);

}

else

return p->data;

}

template

int Linklist::locate(T x)

{

Node *p = head->next;

int i = 1;

while (p)

{

if (p->data == x)

return i;

p = p->next;

i++;

}

exit(1);

}

template

void Linklist::output()

{

Node *p = head->next;

while (p)

{

cout << p->data << " ";

p = p->next;

}

}

template

T Linklist::Delete(int n)//删除数据

{

Node *p = head;

int j = 0;

while (p&&j < n - 1)//找到第i-1个结点的位置

{

p = p->next;

j++;

}

if (!p || !p->next)//位置合法性

{

cout << "错误位置" << endl;

exit(1);

}

else

{

Node *q = p->next;

int x = q->data;

p->next = q->next;

delete q;

return x;

}

}

template

void Linklist::Insert(int i,T item)

{

Node *p = head;

int j = 0;

while (p&&j < i - 1)

{

p = p->next;

j++;

}

if (!p)

{

cout << "插入位置非法";

exit(1);

}

else

{

Node *s = new Node;//生成元素值为item的新结点

s->data = item;

s->next = p->next;//用后插法将s插入到结点p的后面

p->next = s;

}

}

template

void Linklist::clear()

{

Node *p = head;

while (p)

{

Node *q = p;

p = p->next;

delete q;

}

head = NULL;

}

int main()

{

int a[5] = { 1,2,3,4,5 };

cout << "初始化一个链表" << endl;

Linklist x(a,5);

x.output();

cout << endl;

cout << "在第一个位置插入元素 0" << endl;

x.Insert(1,0);

x.output();

cout << endl;

cout << "删除第二个位置的元素" << endl;

x.Delete(2);

x.output();

cout << endl;

cout << "查找元素 3" << endl;

cout<<"元素3的位置为："<

x.clear();//清空

system("pause");

return 0;

}

测试结果：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!