Welcome to Aoki's Blog!

• 单循环链表

  2019-03-28

  数据结构

  数据结构  循环链表

  单循环链表

  
  
  

  写在前面

    单循环链表，简称循环链表（circular linked list)，是表的一种链式存储结构。   设p是指向循环链表的指针，currPtr是当前指向对的循环链表的指针，head是指向循环链表的头指针，与链表判断是否到达链尾相比，循环链表中判断是否到达链表尾的条件是：p!=head或者是currPtr!=head。所以，循环链表类中成员函数的实现与链表类中的成员函数的实现差别不大，只是把p!=null换成了p!=head，把currPtr!=null换成了currptr!=head.

  1.节点类的定义和实现

  Read All

  ---

• 顺序表的简单实现

  2019-03-27

  数据结构

  数据结构  顺序表

  顺序表的简单实现

  
  
  

  写在前面

    数据结构是一个数据对象，同时这个对象的实例以及构成实例的元素都存在着联系，而且这些联系是由相关函数来规定的。
    研究数据结构，关心的是数据对象（实际上是实例）的描述以及相关函数的具体实现。数据对象描述得好，函数的实现就会高效。
    最常用的数据对象以及操作都已经在C++中作为基本数据类型而实现，如整数对象，布尔对象等。其他数据对象均可以用基本数据类型以及由C++的类、数组和指针所提供的组合功能来实现。

  
  

  1.线性表的数据结构

    线性表（linear list)也称有序表，它的每一个实例都是元素的一个有序集合。
    对线性表实施的操作有：

  • 创建一个线性表
  • 撤销一个线性表
  • 确定线性表是否为空
  • 确定线性表的长度
  • 按给定的索引查找一个元素
  • 按一个给定的元素查找其索引
  • 按一个给定的索引删除一个元素
  • 按一个给定的索引插入一个元素
  • 从左至右顺序输出线性表元素

    用顺序存储结构存储的表称为顺序表（sequent list）。顺序表中任意数据元素的存取和访问都可以通过它的位置指针来（即数组下标）进行访问。对顺序表中元素访问的效率是一个比较重要的问题。通常情况下，有序顺序表的访问效率大大高于无序顺序表的访问效率。

  
  

  2.顺序表的类定义

  
  typedef int Seqlist_Entry;
  const int maxsize = 10;
  class Seqlist
  {
  public:
  	Seqlist();//构造函数
  	~Seqlist();//析构函数
  	int listsize()const;//返回元素的个数
  	bool listempty() const;//判断表是否为空
  	int find(const Seqlist_Entry  &item);//返回元素item在表中的位置
  	Seqlist_Entry getdata(int pos) const;//返回位置pos的元素
  	void insert(const Seqlist_Entry  &item, int pos);//在位置pos处插入元素item
  	Seqlist_Entry  Delete(const int pos);//删除位置pos的元素并返回
  	void clearlist();//清空表
  	void showall() const;//输出表
  private:
  	Seqlist_Entry  data[maxsize];
  	int size;//数据元素的个数
  };
  
  
  

  3.顺序表的类实现

  //构造函数
  Seqlist::Seqlist()
  {
  	size = 0;
  }
  //析构函数
  Seqlist::~Seqlist() {}
  
  //返回顺序表元素的个数
  int Seqlist::listsize() const
  {
  	return size;
  }
  //判断顺序表是否为空
  bool Seqlist::listempty() const
  {
  	return (size == 0);
  }
  //查找item，并返回位置索引
  int Seqlist::find(const Seqlist_Entry & item)
  {
  	if (size == 0)
  	{
  		cout << "list is empty " << endl;
  	}
  	int i = 0;
  	while (i < size&&item != data[i])
  	{
  		i++;
  	}
  	if (i < size)
  		return i;
  	else
  		cout << "illegal operator" << endl;
  }
  //取出pos位置上的元素
  Seqlist_Entry Seqlist::getdata(int pos) const
  {
  	if (pos<0 || pos>size - 1)
  	{
  		cout << "illegal operator" << endl;
  		exit(1);
  	}
  	return data[pos];
  }
  //在pos位置插入元素item
  void Seqlist::insert(const Seqlist_Entry & item, int pos)
  {
  	if (size == maxsize)
  	{
  		cout << "list is full" << endl;
  		return;
  	}
  	if (pos<0 || pos>size )
  	{
  		cout << "illegal operator" << endl;
  		return;
  	}
  	for (int i = size; i > pos; i--)
  	{
  		data[i] = data[i - 1];
  	}
  	data[pos] = item;
  	size++;
  }
  //删除pos位置的元素
  Seqlist_Entry Seqlist::Delete(const int pos)
  {
  	Seqlist_Entry tmp=data[pos];
  	if (size == 0)
  	{
  		cout << "list is empty" << endl;
  		exit(1);
  	}
  	if (pos<0 || pos>size - 1)
  	{
  		cout << "illegal operator" << endl;
  		exit(1);
  	}
  	for (int i = pos; i < size-1; i++)
  	{
  		data[i] = data[i + 1];
  	}
  	size--;
  	return tmp;
  }
  //置顺序表为空
  void Seqlist::clearlist()
  {
  	size = 0;
  	cout << "已清空" << endl;
  }
  //输出顺序表中所有元素
  void Seqlist::showall() const
  {
  	if (size == 0)
  	{
  		cout << "list is empty" << endl;
  	}
  	for (int i = 0; i < size; i++)
  	{
  		cout <<i<<"号元素:"<< data[i] << endl;
  	}
  }
  
  

  4.测试主函数

  void test()
  {
  	Seqlist list;
  	for (int i = 0; i < 10; i++)
  	{
  		list.insert(i * 12, i);
  	}
  	for (int i = 0; i < 10; i++)
  	{
  		cout << list.getdata(i) << endl;
  	}
  	int tmp = list.Delete(2);
  	cout << "元素" << tmp << "已经被删除了" << endl;
  	list.showall();
  	cout<<"84在顺序表的"<<list.find(84)<<"号位置"<<endl;
  	list.clearlist();
  	list.showall();
  }
  
  int main()
  {
  	test();
  
  }
  
  
  

  输出结果如下图：
  

  
  
  
  
  
  

  ---

  The End

  ---

  Read All

  ---

• 栈的实现

  2019-03-27

  数据结构

  数据结构  栈

  栈的实现

  
  
  

  写在前面

   栈（Stack)是一种特殊的线性表，是一种只允许在表的一端进行插入和删除操作的线性表。栈中允许进行插入和删除操作的一端称为栈顶，另一端为栈底。栈顶的当前位置是动态的，标识栈顶当前位置的称为栈顶指示器（或栈顶指针）。栈的插入和删除操作通常称为入栈或进栈，栈的删除操作称为出栈或退栈。当栈中没有数据元素时称为空栈。
    根据栈的定义，每次进栈的数据元素都放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈的数据元素都是当前栈顶元素，这样，最后进入堆栈的数据元素总是最先出栈，因此栈也被成为后进先出表。

  1.栈的基本运算

  • 初始化栈
  • 销毁栈
  • 判断栈是否为空
  • 进栈
  • 出栈
  • 取栈顶元素

  2.顺序栈四要素

  • 栈空条件： top==-1
  • 栈满条件： top==max_stack - 1
  • item进栈操作：top++,将item放在top处
  • 退栈操作：从top处取出元素item，top–

  3.类说明

   对于顺序栈Stack的实现，应创建一个数组来存放栈中的元素，并用一个始终指向栈顶的变量top来表示栈顶的位置。类定义如下：

  typedef int Stack_Entry;
  const int max_stack = 10;
  class Stack
  {
  public:
  	Stack();
  	//构造函数
  	~Stack() {};
  	//析构函数
  	bool empty() const;
  	//判断栈是否为空
  	Stack_Entry pop();
  	//出栈数据元素
  	Stack_Entry Top(Stack_Entry &item) const;
  	//返回栈顶元素
  	void push(const Stack_Entry &item);
  	//数据元素item进栈
  	int getsize() const;
  	//获取栈中元素的个数
  	void clearstack();
  	//清空栈
  private:
  	int top;//栈顶位置指示器
  	Stack_Entry entry[max_stack];//Stack_Entry类型的数组
  };
  

  4.具体实现

  Stack::Stack()
  {
  	top=-1;
  }
  
  bool Stack::empty() const
  {
  	return (top==-1);
  }
  
  Stack_Entry Stack::pop()
  {
  	if (top==-1)
  	{
  		cout << "Stack is empty" << endl;
  	}
  	return entry[top--];
  	
  }
  
  Stack_Entry Stack::Top(Stack_Entry & item) const
  {
  	if (top == -1)
  	{
  		cout << "Stack is empty" << endl;
  	}
  	return entry[top];
  }
  
  void Stack::push(const Stack_Entry & item)
  {
  	if (top == max_stack - 1)
  	{
  		cout << "Stack is full" << endl;
  	}
  	top++;
  	entry[top] = item;
  }
  
  int Stack::getsize() const
  {
  	return top+1;
  }
  
  void Stack::clearstack()
  {
  	top = -1;
  }
  

  5.主函数

  void test()
  {
  	Stack stack;
  
  	for (int i = 0; i < 10; i++)
  	{
  		stack.push(i+10*i);
  	}
  	cout << "当前栈中元素数为：" << stack.getsize() << endl;
  	for (int i = 0; i < 10; i++)
  	{
  		Stack_Entry tmp;
  		tmp = stack.pop();
  		cout << "我是" << i << "号元素:"<<tmp << endl;
  	}
  	cout << "当前栈中元素数为：" << stack.getsize() << endl;
  	if (stack.empty())
  	{
  		cout << "Stack is empty" << endl;
  	}
  	else
  	{
  		cout << "Stack is not empty" << endl;
  	}
  }
  int main()
  {
  	test();
  	system("pause");
  	return EXIT_SUCCESS;
  }
  

  输出结果如下图：
  

  
  
  
  
  
  

  ---

  The End

  ---

  Read All

  ---

• 单链表的实现

  2019-03-27

  数据结构

  数据结构  链表

  单链表的实现

  
  
  

  写在前面

   链式存储结构是计算机中另一种最基本和最主要的数据存储结构。和顺序存储结构不同，初始化时链式存储结构为空链，每当有新的元素需要存储时用户向系统动态申请所需的存储空间插入链中。所有高级程序设计语言都为用户提供了向系统动态申请和动态释放存储空间的办法。C++提供了new 和delete运算符，分别用于向系统动态申请所需存储空间和动态释放用new申请的存储空间。new能自动计算要分配的类型大小并自动返回正确的指针类型。delete能自动释放由new分配的存储空间。
    在顺序存储结构中，用户向系统申请一块地址连续的有限空间用于存储数据元素，这样任意两个在逻辑上相邻的数据元素在物理上也必然相邻。但在链式存储结构中，由于它在初始化时为空链，每当有新的数据元素需要存储时用户才向系统动态申请所需的存储空间插入链中，而这些在不同时刻向系统动态申请的存储空间在内存上很可能是不连续的。因此，在链式存储结构中，任意两个在逻辑上相邻的数据元素在物理上不一定相邻，数据元素的逻辑次序是通过链中的指针连接实现的。
    链式存储结构存储线性结构数据元素集合的方法是用节点（Node)构造链。线性结构数据元素的特点是：除第一个和最后一个元素外，每个元素只有一个唯一的前驱和一个唯一的后继。链式结构中每个节点除数据域外，还有一个或两个以上的指针域，数据域用来存放数据元素，指针域用来构造数据元素之间的关系。

  1.单链表

   单链表简称链表（linked list)，是表数据元素的单链结构存储。链表使用一个一个的节点链接构成的。
    表要求允许在任意位置进行插入和删除。当选用带头节点的单链表时，在第一个位置插入节点和在其他位置插入节点一样不会改变头指针head的值，此时改变的是head->next的值。  在第一个位置删除节点和在其他位置删除节点一样也不会改变头指针head的值，此时改变的也是head->next的值。

  2.节点类的定义和实现

   在单链表中，每个节点构成包括数据域和指针域两部分。每个节点的基本操作包括构造一个节点对象、建立一个新节点、给出当前节点的下一个节点指针等。

  template<class T>
  class ListNode
  {
  	friend class LinList<T>;//声明友元类
  public:
  	T data;//数据域
  	ListNode(ListNode<T> *ptrNext = NULL);//构造函数，用于构造头节点，头节点没有data参数
  	ListNode(const T &item, ListNode<T> *ptrNext = NULL);//构造函数，主要用于构造非头节点的节点
  	~ListNode() {};//析构函数
  private:
  	ListNode<T> *next;//指向下一节点的指针
  };
  
  template<class T>
  inline ListNode<T>::ListNode(ListNode<T>* ptrNext):next(ptrNext)
  {}//构造函数，用于构造头节点，头节点没有值
  
  template<class T>
  inline ListNode<T>::ListNode(const T & item, ListNode<T>* ptrNext)
  {//构造函数，用于构造非头节点的节点
  	data = item;
  	next = ptrNext;
  }
  

   节点类的成员有data域和next域。data域中存放了该节点的数据值，由于应用问题中需要使用链表中的data值，所以定义为公有数据成员方便使用；next域定义为私有数据成员。节点类的成员函数由两个不同参数的构造函数和空的析构函数。析构函数为空是因为节点类中没有用new函数向系统申请空间，而节点对象本身分配的空间，系统可自动识别释放。

  
  

  3.单链表类的定义

  template<class T>
  class LinList
  {
  public:
  	LinList();//构造函数
  	~LinList();//析构函数
  	//表操作成员函数
  	int listsize() const;//返回链表中元素的个数
  	bool listempty() const;//链表是否为空
  	ListNode<T> *index(int pos);//返回指向第pos个节点的指针
  
  	void insert(const T& item, int pos);//在pos节点前插入一个data域为item的元素
  	T Delete(int pos);//删除第pos个节点并返回被删除节点的data域
  	T getdata(int pos);//返回第pos个节点的data值
  	void clearlist();//清空表为初始化状态
  	//遍历链表的成员函数
  	ListNode<T> *Reset(int pos = 0);//currPtr指向节点pos并返回currPtr
  	ListNode<T> *Next();//currPtr指向下一个节点并返回currPtr
  	bool endOfList() const;//currPtr==head？
  
  private:
  	ListNode<T> *head;//指向头节点的指针
  	ListNode<T> *currPtr;//当前指针
  	int size;//单链表中元素的个数
  };
  

   单链表类的数据成员有头指针、元素个数和当前节点指针。头指针指向头结点，任何对单链表中节点的操作都要从头指针进入。初始化状态下，节点个数为0.当前节点指针是遍历链表成员函数使用的数据成员，遍历链表成员函数通过控制当前节点指针来遍历链表。
    单链表类的成员函数由三组：构造函数和析构函数、表操作的成员函数和遍历链表的成员函数。由于单链表类中的节点是通过new函数向系统申请的，在释放单链表类对象的时候，系统无法自行释放这些空间，所以析构函数不能为空，析构函数必须用delete函数逐个释放这些空间。表操作成员函数时对表操作的基本成员函数，这与顺序表类中对表进行操作的成员函数意义相同，但是实现方法不同。链表的遍历操作是每次寻找当前节点的下一个节点，由于每次对链表类中节点的操作都要从头指针进入后寻找到相应的节点后才可完成，这样的单链表类遍历操作的时间复杂度返回大大增加，在单链表中增加一组遍历链表的成员函数可使单链表遍历操作的时间复杂度不增加。
  
  

  4.单链表类的实现

  template<class T>
  inline LinList<T>::LinList()
  {
  	head = new ListNode<T>();//头指针指向头结点
  	size = 0;
  }
  
  template<class T>
  inline LinList<T>::~LinList()
  {
  	clearlist();
  	delete head;
  	head = NULL;
  }
  
  template<class T>
  inline int LinList<T>::listsize() const//返回单链表中元素的个数
  {
  	return size;
  }
  
  template<class T>
  inline bool LinList<T>::listempty() const
  {
  	return size == 0;
  }
  
  template<class T>
  inline ListNode<T>* LinList<T>::index(int pos)
  {
  	if (pos == -1)
  		return head;
  	if (pos<0 || pos>size)
  	{
  		cout << "illegal operator" << endl;
  		exit(1);
  	}
  	
  	ListNode<T> *p = head->next;//p指向第一个节点
  	int i = 0;
  	while (p != NULL && i < pos)
  	{
  		p = p->next;
  		i++;
  	}
  	return p;
  }
  
  template<class T>
  inline void LinList<T>::insert(const T & item, int pos)
  {
  	ListNode<T> *p = index(pos - 1);
  	ListNode<T> *newnode = new ListNode<T>(item, p->next);
  	p->next = newnode;
  	size++;
  
  }
  
  template<class T>
  inline T LinList<T>::Delete(int pos)
  {
  	if (size == 0)
  	{
  		cout << "list is empty" << endl;
  		exit(1);
  	}
  	ListNode<T>*q, *p = index(pos - 1);//p为指向第pos-1个节点的指针
  	q = p->next;//q指向要删除节点
  	p->next = p->next->next;//p指向要删除节点的后一节点
  	T data = q->data;  //data保存要删除节点值
  	delete q;
  	size--;
  	return data;
  
  }
  
  template<class T>
  inline T LinList<T>::getdata(int pos)
  {
  	ListNode<T> *p = index(pos);//指针p指向第pos个节点
  	return p->data;
  }
  
  template<class T>
  inline void LinList<T>::clearlist()
  {
  	ListNode<T> *p, *p1;
  	p = head->next;
  	while (p != NULL)
  	{//delete所有new出来的空间
  		p1 = p;
  		p = p->next;
  		delete p1;
  	}
  	size = 0;
  }
  
  template<class T>
  inline ListNode<T>* LinList<T>::Reset(int pos)
  {
  	if (head == NULL)
  		return NULL;
  	if (pos < -1 || pos>size)
  	{
  		cout << "mistake" << endl;
  		exit(1);
  	}
  	if (pos == -1)
  		return head;
  	if (pos == 0)
  	{
  		currPtr = head->next;
  	}
  	else
  	{
  		currPtr = head->next;
  		ListNode<T> prevPtr = head;
  		for (int i = 0; i < pos; i++)
  		{
  			prevPtr = currPtr;
  			currPtr = currPtr->next;
  		}
  	}
  	return currPtr;
  }
  
  template<class T>
  inline ListNode<T>* LinList<T>::Next()
  {
  	if (currPtr != NULL)
  	{
  		currPtr = currPtr->next;
  	}
  	return currPtr;
  }
  
  template<class T>
  inline bool LinList<T>::endOfList() const
  {
  	return currPtr == NULL;
  }
  
  

    这些成员函数基本上实现了单链表所需的基本操作。

  5.主函数测试

  测试主函数如下：

  void test()
  {
  	LinList<int> list;
  	cout << "单链表中的元素个数为："<<list.listsize() << endl;
  	for (int i = 0; i < 10; i++)
  	{
  		list.insert(15 * i, i);
  	}
  	cout << "单链表中的元素个数为：" << list.listsize() << endl;
  	cout << "5号为：" << list.getdata(5) << endl;
  	cout<<list.Delete(5)<<"已被删除"<<endl;
  	cout << "5号为：" << list.getdata(5) << endl;
  	ListNode<int> *p = list.Reset();
  	while (!list.endOfList())
  	{
  		cout << p->data << endl;
  		p = list.Next();
  	}
  
  }
  
  int main()
  {
  	test();
  	system("pause");
  	return EXIT_SUCCESS;
  }
  

  输出结果如下：
  

  
  
  
  
  
  

  ---

  The End

  ---

  Read All

  ---