数据结构-线性表-单链表(c++)

  • Post author:
  • Post category:其他

线性表的运算

  1. 求长度GetLength(L),求线性表L的长度
  2. 置空表SetNull(L),将线性表置成空表
  3. 按位查找Get(L,i),查找线性表L第i个元素
  4. 按值查找Location(L,x),查找线性表L值为x的元素
  5. 修改Set(L,i,x),将线性表L第i位置的元素,修改为x
  6. 插入Insert(L,i,x),在线性表L的第i位置插入x
  7. 删除Delete(L,i),删除线性表L的第i位置元素
  8. 排序Sort

单链表

LinkList.h

#ifndef LINKLIST_H_
#define LINKLIST_H_
#include<iostream>
template<class T>
struct Node
{
 T data;
 struct Node<T>* next;
};
template<class T>
class LinkList
{
private:
 Node<T>* front;
public:
 LinkList();
 LinkList(T a[], int n);
 ~LinkList();
 int Length();
 void PrintList();
 Node<T>* Get(int i);
 int Location(int x);
 void Insert(int i,T x);
 T Delete(int i);
};
template<class T>
LinkList<T>::LinkList()
{
 front = new Node<T>; 
 front->next = nullptr;
}
template<class T>
LinkList<T>::LinkList(T a[], int n)
{
 front = new Node<T>;
 /**头插法**/
 //front->next = nullptr;
 //for (int i = n-1; i >=0n; i--)
 //{
 // Node<T>* s = new Node<T>;
 // s->data = a[i];
 // s->next = font->next;
 // fornt->next = s;
 //}
 /**尾插法**/
 Node<T>* r = front;
 for (int i = 0; i < n; i++)
 {
  Node<T>* s = new Node<T>;
  s->data = a[i];
  r->next = s;
  r = s;
 }
 r->next = nullptr;
}
template<class T>
LinkList<T>::~LinkList()
{
 Node<T>* p = front;
 while (p)
 {
  front = p;
  p = p->next;
  delete front;
 }
}
template<class T>
int LinkList<T>::Length()
{
 Node<T>* p = front->next;
 int len = 0;
 while (p)
 {
  len++;
  p = p->next;
 }
 return len;
}
template<class T>
void LinkList<T>::PrintList()
{
 std::cout << "链表内容:" << std::endl;
 int i=0;
 Node<T>* p = front->next;
 while (p)
 {
  std::cout << p->data<<" ";
  
  if (i % 5 == 4)
   std::cout << std::endl;
  i++;
  p = p->next;
 }
 if (i % 5 != 0)
  std::cout << std::endl;
}
template<class T>
Node<T>* LinkList<T>::Get(int i)
{
 int j = 1;
 Node<T>* p = front->next;
 while (p && j != i)
 {
  p = p->next;
  j++;
 }
 return p;
}
template<class T>
int LinkList<T>::Location(int x)
{
 Node<T>* p = front->next;
 int j = 1;
 while (p)
 {
  if (p->data == x)return j;
  p = p->next;
  j++;
 }
 return -1;
}
template<class T>
void LinkList<T>::Insert(int i, T x)
{
 Node<T>* p = front;
 if (i != 1)
  p = Get(i-1);
 if (p)
 {
  Node<T>* s = new Node<T>;
  s->data = x;
  s->next = p->next;
  p->next = s;
 }
 else throw"位置异常";
}
template<class T>
T LinkList<T>::Delete(int i)
{
 Node<T>* p = front;
 if (i != 1)
  p = Get(i - 1);
 if (!p && !p->next)throw"位置错误";
 Node<T>* q = p->next;
 p->next = q->next;
 T x = q->data;
 delete q;
 return x;
}
#endif // !LINKLIST_H_

use.cpp

#include<iostream>
#include"LinkList.h"
int main()
{
 using std::cout;
 using std::endl;
 cout << "Start!" << endl;
 int s[10] = { 0,1,2,3,4,5,6,7,8,9 };
 LinkList<int> grade(s, 10);
 cout << "长度为:" << grade.Length() << endl;
 cout << "befor delete: ";
 grade.PrintList();
 grade.Delete(1);
 cout << "after delete: ";
 grade.PrintList();
 cout << endl;
 cout << "befor insert: ";
 grade.PrintList();
 grade.Insert(3, 5);
 cout << "after insert: ";
 grade.PrintList();
 cout << "第2个元素值:" << grade.Get(2) << endl;
 cout << "7的位置:" << grade.Location(7) << endl;
 return 0;
}

说明:

因为链表的数据类型不确定,所以使用模板类(模板类的定义和声明必须放在一个文件中编译);模板并未加上所有运算,可自行添加

(一)结点

包含数据域data和指针域next(指向直接后继)

data next
template<class T>
struct Node
{
 T data;
 struct Node<T>* next;
}

(二)无参构造函数

template<class T>
LinkList<T>::LinkList()
{
 front = new Node<T>; 
 front->next = nullptr;
}

建立有个头结点front,front下一个为空(front->next=nullptr;),即空链表

(三)有参构造函数

LinkList<T>::LinkList(T a[], int n)
{
 front = new Node<T>;
 /**头插法**/
 //front->next = nullptr;
 //for (int i = n-1; i >=0n; i--)
 //{
 // Node<T>* s = new Node<T>;
 // s->data = a[i];
 // s->next = font->next;
 // fornt->next = s;
 //}
 /**尾插法**/
 Node<T>* r = front;
 for (int i = 0; i < n; i++)
 {
  Node<T>* s = new Node<T>;
  s->data = a[i];
  r->next = s;
  r = s;
 }
 r->next = nullptr;
 }

将个数为n类型为T的数组元素a[],赋值给链表;分为头插法和尾插法,使用头插法需要注意要想与a[]元素顺序一样,需要先插入a[]最后一个元素,然后再一次插入前面的

  1. 创建头结点front
  2. 创建数据结点s
  3. 赋值,将a[i]赋给s->data
  4. 将原先front的直接后继地址赋给s->next;
  5. 更改front直接后继地址

尾插法类似。

(四)析构函数

 template<class T>
LinkList<T>::~LinkList()
{
 Node<T>* p = front;
 while (p)
 {
  front = p;
  p = p->next;
  delete front;
 }
}

因为是使用new来创建结点,所以需要使用delete释放每一个结点;所以需要遍历与每一个结点,并逐一释放

  1. 创建一个工作指针p,并将头结点赋给它
  2. 遍历每个结点(while(p),当p不为空的时候)
  3. 移动p,p=p->next;
  4. 将p赋给front,并释放

其他功能与上述类似


版权声明:本文为qq_40666149原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。