利用C++简单实现顺序表和单链表的示例代码

本文主要给大家介绍了关于C++实现顺序表和单链表的相关内容,分享出来供大家参考学习,话不多说,来一起看看详细的介绍:

一、顺序表示例代码:

#include <assert.h>
#include <iostream>
using namespace std;

typedef int Datatype;

class SeqList
{
public:
 SeqList()
  :_array(NULL)
  ,_size(0)
  ,_capacity(0)
 {
 }

 SeqList(const SeqList& s)
 {
  _array = (Datatype*)malloc(s._size*(sizeof(Datatype)));
  memcpy(_array, s._array, s._size*(sizeof(Datatype)));
  _size = _capacity = s._size;
 }

 SeqList& operator=(SeqList& s)
 {
  free(_array);
  Swap(s);
  return *this;
 }

 void Swap(SeqList& s)
 {
  _array = s._array;
  _size = s._size;
  _capacity = s._capacity;
 }

 ~SeqList()
 {
  if (_array)
  {
   free(_array);
   _array = NULL;
   _size = _capacity = 0;
  }
 }

 void Print()
 {
  for (size_t i = 0; i < _size; i++)
  {
   cout << _array[i] << " ";
  }
  cout << endl;
 }

 void CheckCapcacity()
 {
  if (_size == _capacity)
  {
   _capacity = 2 * _capacity + 3;
   _array = (Datatype*)realloc(_array, _capacity*sizeof(Datatype));
   assert(_array);
  }
 }

 //后插
 void PushBack(Datatype x)
 {
  Insert(_size, x);
 }

 //前插
 void PushFront(Datatype x)
 {
  Insert(0, x);
 }

 //删除最后一个
 void PopBack()
 {
  Erase(_size);
 }

 //删除第一个
 void PopFront()
 {
  Erase(0);
 }

 //[]运算符重载
 Datatype& operator[](size_t pos)
 {
  assert(pos < _size);
  return _array[pos];
 }

 //pos位置前插入x
 void Insert(size_t pos, Datatype x)
 {
  assert(pos <= _size);
  CheckCapcacity();
  int end = (int)_size - 1;
  if (pos == 0)
  {
   while (end >= 0)
   {
    _array[end + 1] = _array[end];
    end--;
   }
   _array[0] = x;
  }
  else
  {
   while (end >= (int)pos)
   {
    _array[end + 1] = _array[end];
    end--;
   }
   _array[pos] = x;
  }
  _size++;
 }

 //删除pos位置的元素
 void Erase(size_t pos)
 {
  assert(pos < _size);
  //popfront的实现
  if (_size > 0)
  {
   if (pos == 0)
   {
    int end = 0;
    while (end < (int)_size - 1)
    {
     _array[end] = _array[end + 1];
     end++;
    }
    _size--;
   }
   //popback的实现
   else if (pos == _size)
   {
    _size--;
   }
   //erase
   else
   {
    int end = pos;
    while (end < (int)_size - 1)
    {
     _array[end] = _array[end + 1];
     end++;
    }
    _size--;
   }
  }
  return;
 }

private:
 Datatype* _array;
 size_t _size;
 size_t _capacity;
};

二、单链表(不含头结点)示例代码

#include <iostream>
#include <assert.h>
using namespace std;

typedef int DataType;

struct SListNode
{
 SListNode* _next;
 DataType _data;

 SListNode(DataType x)
  :_data(x)
  , _next(NULL)
 {}
};

typedef SListNode Node;

class SList
{
public:
 SList()
  :_head(NULL)
  , _tail(NULL)
 {}

 SList(const SList& s)
  :_head(NULL)
  ,_tail(NULL)
 {
  Copy(s);
 }

 SList& operator=(const SList& s)
 {
  Destroy();
  Copy(s);
  return *this;
 }

 ~SList()
 {
  Destroy();
 }

 void Copy(const SList& s)
 {
  Node* cur = s._head;
  while (cur)
  {
   PushBack(cur->_data);
   cur = cur->_next;
  }
 }

 void Destroy()
 {
  Node* cur = _head;
  while (_head != NULL)
  {
   cur = _head;
   _head = cur->_next;
   delete cur;
  }
  _head = _tail = NULL;
 }

 void PushBack(DataType x)
 {
  if ((_head == NULL)&&(_tail == NULL))
  {
   _head = _tail = new Node(x);
  }
  else
  {
   _tail->_next = new Node(x);
   _tail = _tail->_next;
  }
 }

 void PopBack()
 {
  if (_head == NULL)
  {
   return;
  }
  else if (_head ->_next == NULL)
  {
   delete _head;
   _head = _tail = NULL;
  }
  else
  {
   Node* tmp = _head;
   while (tmp->_next->_next != NULL)
   {
    tmp = tmp->_next;
   }
   _tail = tmp;
   tmp->_next = NULL;
  }
 }

 void PushFront(DataType x)
 {
  if ((_head == NULL) && (_tail == NULL))
  {
   _head = _tail = new Node(x);
  }
  else
  {
   Node* tmp = new Node(x);
   tmp->_next = _head;
   _head = tmp;
  }
 }

 void PopFront()
 {
  if (_head == NULL)
  {
   return;
  }
  Node* cur = _head;
  _head = _head->_next;
  delete cur;
 }

 Node* Find(DataType x)
 {
  Node* tmp = _head;
  while (tmp)
  {
   if (tmp->_data == x)
    return tmp;
   tmp = tmp->_next;
  }
  return NULL;
 }

 // 插入一个节点在pos的前面
 void Insert(Node* pos, DataType x)
 {
  assert(pos);
  if (pos == 0)
  {
   PushFront(x);
  }
  else
  {
   Node* cur = _head;
   while (cur->_next != pos)
   {
    cur = cur->_next;
   }
   Node* tmp = new Node(x);
   tmp->_next = pos;
   cur->_next = tmp;
  }
 }

 void Erase(Node* pos)
 {
  assert(pos);
  if (pos == 0)
  {
   PopFront();
  }
  else if (pos->_next == NULL)
  {
   PopBack();
  }
  else
  {
   Node* cur = _head;
   while (cur->_next != pos)
   {
    cur = cur->_next;
   }
   Node* tmp = cur->_next;
   cur->_next = tmp->_next;
   delete tmp;
  }
 }

 void Print()
 {
  Node* tmp = _head;
  while (tmp != NULL)
  {
   cout <<tmp->_data << "->";
   tmp= tmp->_next;
  }
  cout <<"NULL"<<endl;
 }

private:
 Node* _head;
 Node* _tail;
};

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流,谢谢大家对我们的支持

时间: 2017-07-30

C语言实现静态顺序表的实例详解

C语言实现静态顺序表的实例详解 线性表 定义一张顺序表也就是在内存中开辟一段连续的存储空间,并给它一个名字进行标识.只有定义了一个顺序表,才能利用该顺序表存放数据元素,也才能对该顺序表进行各种操作. 接下来看看静态的顺序表,直接上代码: SeqList.h #define _CRT_SECURE_NO_WARNINGS 1 #ifndef __SEQLIST_H__ #define __SEQLIST_H__ #include <stdio.h> #include <stdlib.h&g

利用C语言实现顺序表的实例操作

本文实例讲述了C语言实现顺序表(线性表)的方法.分享给大家供大家参考,具体如下: 一:顺序表代码实现 #ifndef _SEQ_LIST_H #define _SEQ_LIST_H #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #define ElemType float //以float类型测试算法通用性,而不是以惯用的int #define I

c语言实现顺序表的基本操作

数据结构顺序表操作 复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <malloc.h>#define LIST_INIT_SIZE 100#define LISINCREMENT 10#define ElemType int#define Status inttypedef struct Sq{ ElemType *elem; int length; int listsize;}SqList;Statu

用C语言举例讲解数据结构中的算法复杂度结与顺序表

数据结构算法复杂度 1.影响算法效率的主要因素 (1)算法采用的策略和方法: (2)问题的输入规模: (3)编译器所产生的代码: (4)计算机执行速度. 2.时间复杂度 // 时间复杂度:2n + 5 long sum1(int n) { long ret = 0; \\1 int* array = (int*)malloc(n * sizeof(int)); \\1 int i = 0; \\1 for(i=0; i<n; i++) \\n { array[i] = i + 1; } for(

C语言线性表的顺序表示与实现实例详解

1.概述 通常来说顺序表是在计算机的内存中以数组的形式保存的线性表,是用一组地址连续的存储单元依次存储数据元素的线性数据结构.线性表采用顺序存储的方式存储就称之为顺序表.顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中. 将表中元素一个接一个的存入一组连续的存储单元中,这种存储结构就是顺序结构. 采用顺序存储结构的线性表简称为" 顺序表".顺序表的存储特点是:只要确定了起始位置,表中任一元素的地址都通过下列公式得到:LOC(ai)=LOC(a1)+(i-1)*L 1≤

C语言实现顺序表基本操作汇总

本文汇总了C语言下实现及操作顺序表的方法,对于学习数据结构的朋友来说是一个不错的参考程序.完整代码如下: #include<stdio.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int status ;

C语言实现动态顺序表的实现代码

C语言实现动态顺序表的实现代码 顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构.线性表采用顺序存储的方式存储就称之为顺序表.顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中. 静态实现:结构体内部只需两个成员,其中一个为固定大小(MAX)的数组,用来存放我们的数据.数组大小我们可以通过在头文件中改变MAX的值来改变. 动态实现:在内存中开辟一块空间,可以随我们数据数量的增多来扩容. 来看看动态的顺序表实现: 1.seqli

C++实现动态顺序表

本文实例为大家分享了C++实现动态顺序表的具体代码,供大家参考,具体内容如下 Vector.h #pragma once #include <stdio.h> #include <iostream> #include <assert.h> #include <string.h> using namespace std; typedef int DataType; class Vector { public: Vector() :_first(NULL) ,

C语言顺序表的实现代码

本文实例为大家分享了C语言实现顺序表的具体代码,供大家参考,具体内容如下 seqlist.h #ifndef __SEQLIST_H__ #define __SEQLIST_H__ #include<cstdio> #include<malloc.h> #include<assert.h> #define SEQLIST_INIT_SIZE 8 #define INC_SIZE 3 //空间增量的大小 typedef int ElemType; typedef stru

Python数据结构之顺序表的实现代码示例

顺序表即线性表的顺序存储结构.它是通过一组地址连续的存储单元对线性表中的数据进行存储的,相邻的两个元素在物理位置上也是相邻的.比如,第1个元素是存储在线性表的起始位置LOC(1),那么第i个元素即是存储在LOC(1)+(i-1)*sizeof(ElemType)位置上,其中sizeof(ElemType)表示每一个元素所占的空间. 追加直接往列表后面添加元素,插入是将插入位置后的元素全部往后面移动一个位置,然后再将这个元素放到指定的位置,将长度加1删除是将该位置后面的元素往前移动,覆盖该元素,然

C++顺序表的实例代码

本文实例为大家分享了C++实现顺序表的具体代码,供大家参考,具体内容如下 #include <iostream> using namespace std; typedef int DataType; class SeqList { public: SeqList() :_a(NULL) , _size(0) , _capacity(0) {} SeqList(const SeqList& s) :_a(new DataType[s._size]) , _size(s._size) ,

MyBatis动态创建表的实例代码

项目中业务需求的不同,有时候我们需要动态操作数据表(如:动态建表.操作表字段等).常见的我们会把日志.设备实时位置信息等存入数据表,并且以一定时间段生成一个表来存储,log_201806.log_201807等.在这里我们用MyBatis实现,会用到动态SQL. 动态SQL是Mybatis的强大特性之一,MyBatis在对sql语句进行预编译之前,会对sql进行动态解析,解析为一个BoundSql对象,也是在此对动态sql进行处理. 在动态sql解析过程中,#{ }与${ }的效果是不一样的:

python实现顺序表的简单代码

顺序表即线性表的顺序存储结构.它是通过一组地址连续的存储单元对线性表中的数据进行存储的,相邻的两个元素在物理位置上也是相邻的.比如,第1个元素是存储在线性表的起始位置LOC(1),那么第i个元素即是存储在LOC(1)+(i-1)*sizeof(ElemType)位置上,其中sizeof(ElemType)表示每一个元素所占的空间. 下面是顺序表的python实现: #coding:utf-8 ''' author:xzfreewind ''' class SeqList(object): def

C++实现动态顺序表(vector)

vector是连续存储结构,支持随机的高效的随机和在尾部进行插入.删除操作,其它位置的插入.删除操作相对来说效率较低. vector相当于一个数组,但它的数组空间大小需要写一程序来实现. 它的内存分配原理大概可分为下面几步: 1)首先分配一块内存空间进行存储: 2)当所需存储的数据超过分配的空间时,再重新分配一块空间: 3)将旧元素复制到新空间: 4)释放旧空间. 实现代码如下: vector.h #pragma once #include<stdio.h> #include<asser

C语言实现的顺序表功能完整实例

本文实例讲述了C语言实现的顺序表功能.分享给大家供大家参考,具体如下: seqlist.h #ifndef __SEQLIST_H__ #define __SEQLIST_H__ #include<cstdio> #include<malloc.h> #include<assert.h> #define SEQLIST_INIT_SIZE 8 #define INC_SIZE 3 //空间增量的大小 typedef int ElemType; typedef struc