動態順序表(C++實現)

来源:http://www.cnblogs.com/Lynn-Zhang/archive/2016/04/15/5395316.html
-Advertisement-
Play Games

順序表是在電腦記憶體中以數組的形式保存的線性表,是指用一組地址連續的存儲單元依次存儲數據元素的線性結構。 這樣的存儲方式使得線性表邏輯上相鄰的元素,其在物理存儲單元中也是相鄰的。只要知道了第一個元素的存儲地址,就可以知道線性表中任何一個元素的存儲地址。因此,線性表中的任何一個元素, 本文利用C++語 ...


順序表是在電腦記憶體中以數組的形式保存的線性表,是指用一組地址連續的存儲單元依次存儲數據元素的線性結構。

這樣的存儲方式使得線性表邏輯上相鄰的元素,其在物理存儲單元中也是相鄰的。只要知道了第一個元素的存儲地址,就可以知道線性表中任何一個元素的存儲地址。因此,線性表中的任何一個元素,

本文利用C++語言,在Windows平臺 Visual Studio 2013開發環境下實現

1:動態增容 2:列印單鏈表 3:尾插 4:尾刪 5:頭插 6:頭刪 7:查找數據 8:在某位置後插入數據 9:刪除某位置的數據 10:找到並刪除x

****************************************************************************************************/
/*
     功能:應用C++語言實現順序表的各項操作
         
     基本的成員函數:
	               構造函數、拷貝構造函數、賦值運算符的重載、析構函數      


          **                  1:動態增容
          **                  2:列印單鏈表    
          **                  3:尾插
          **                  4:尾刪
          **                  5:頭插       
          **                  6:頭刪    
          **                  7:查找數據   
          **                  8:在某位置後插入數據   
          **                  9:刪除某位置的數據
          **                 10:刪除x    
          **
          **                              By :Lynn-Zhang
          **                    																				  
												 				                              */
/*****************************************************************************************************/
#define _CRT_SECURE_NO_WARNINGS 1

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

typedef int DataType;

class SeqList
{
public:
	SeqList();   //構造函數
	SeqList(const SeqList & sList);   //拷貝構造
	SeqList& operator=(const SeqList& sList);  //賦值運算符重載
	~SeqList();   //析構函數

	void CheckCapacity();    // 測容/擴容
	void Print();                    // 列印順序表
	void PushBack(const DataType & x);  // 尾插
	void PopBack();                                   // 尾刪
	void PushFront(const DataType & x);   // 頭插
	void PopFront();                                    // 頭刪
	   
	int Find(const DataType & x);                //查找數據
	void Insert(size_t pos, const DataType & x);   //固定位置插入數據
	void Erase(size_t pos);                                    //刪除某位置的數據
	int Remove(const DataType & x);                   //刪除數據x

private:
	DataType* _array;      //數據塊指針
	size_t   _size;             //定義當前有效數據的個數
	size_t _capicity;         //容量

};
  

基本的成員函數

SeqList::SeqList()
	:_array(NULL)
	, _size(0)
	, _capicity(0)
{}

SeqList::SeqList(const SeqList & sList)
	:_array(new DataType[sList._size])
	, _size(sList._size)
	, _capicity(sList._capicity)
{
	memcpy(_array, sList._array, sizeof(DataType)*_size);
}

SeqList& SeqList::operator=(const SeqList& sList)
{
	if (&sList != this)
	{
		DataType *tmp = new DataType[sList._size];
		delete[] _array;

		_array = tmp;
		_size = sList._size;
		_capicity = sList._capicity;
		memcpy(_array, sList._array, sizeof(DataType)*_size);
	}
	return *this;
}

SeqList::~SeqList()
{
	if (_array != NULL)
	{
		delete[] _array;
		_size = 0;
		_capicity = 0;
	}
}

測容,如果容量不夠要進行擴容

void SeqList::CheckCapacity()
{
           if (_size >= _capicity)
           {
                    _capicity = 2 * _capicity + 5;
                    _array = (DataType *)realloc(_array, _capicity*sizeof (DataType ));
           }
}

列印順序表

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

在尾部添加數據

void SeqList::PushBack(const DataType & x)
{
           CheckCapacity();    //添加數據前要進行測容
           _array[_size++] = x ;     //這裡註意:添加完數據意思要給size加1
}

尾刪

void SeqList::PopBack()
{
//要進行邊界條件檢查 if (_size == 0) { cout << "This SeqList is Empty !" << endl; return; } else { _array[--_size]=NULL ; } }

頭插

void SeqList::PushFront(const DataType & x)   //頭插
{
           if (_size == 0)
           {
                    PushBack(x );
                    return;
           }
           else
           {
                    CheckCapacity();
                    int key = _size;
                    while (key)
                    {
                              _array[key--] = _array[key - 1];
                    }
                    _array[0] = x;
                    _size++;
           }
}

頭刪

void SeqList::PopFront()  //頭刪
{
           if (_size == 0||_size==1)
           {
                    PopBack();
           }
           else
           {
                    for (int i = 0; i < _size-1;i++)
                    {
                              _array[i] = _array[i + 1];
                    }
                    --_size;
           }
}

固定位置插入數據

void SeqList::Insert(size_t pos , const DataType& x)   
{
           assert( pos<_size);    //需檢驗pos的合法性
           CheckCapacity();
           if (pos == _size - 1)   //在最後一個位置插入數據等於尾插
           {
                    PushBack(x );
                    return;
           }
           else
           {
                    for (int i = _size; i > pos; --i)
                    {
                              _array[i] = _array[i - 1];
                    }
                    _array[pos ] = x ;
                    _size++;
           }
}

查找數據

int SeqList::Find(const DataType & x)    
{
           assert(_array != NULL);
           for (int i = 0; i < _size; i++)
           {
                    if (_array[i] == x )
                              return i;
           }
           return -1;
}

固定位置刪除數據

void SeqList::Erase(size_t pos )     
{
           assert(_array!= NULL);
           assert( pos < _size);
           if (pos == _size - 1)
           {
                    PopBack();
                    return;
           }
           if (pos == 0)
           {
                    PopFront();
                    return;
           }
           for (int i = pos; i < _size-1; i++)
           {
                    _array[i] = _array[i + 1];
           }
           --_size;
}

刪除x

int  SeqList::Remove(const DataType & x)   //刪除x
{
           assert(_array);
           int pos=Find(x );
           if (pos != -1)
           {
                    Erase(pos);
                    return 1;
           }
           else
           {
                    return -1;
           }
                    
}

測試用例

//void Test1()
//{
//   SeqList list1;
//   list1.PushBack(1);
//   list1.PushBack(2);
//   list1.PushBack(3);
//   list1.PushBack(4);
//   list1.PushBack(5);
//
//   list1.Print();
//
//   SeqList list2;
//   list2.PushBack(0);
//   list2.PushBack(9);
//   list2.PushBack(8);
//   list2.PushBack(7);
//   list2.PushBack(6);
//   list2.Print();
//
//   list1 = list2;
//   list1.Print();
//
//   SeqList list3(list1);
//   list3.Print();
//}
 
void Test2()
{
           SeqList list1;
 
           //list1.PushFront(0);
           //list1.Print();
 
           list1.PushBack(1);
           list1.PushBack(2);
           list1.PushBack(3);
           list1.PushBack(4);
           list1.PushBack(5);
           list1.Print();
 
           //list1.PopFront();
           //list1.Print();
           /*list1.Insert(2, 0);
    list1.Print();*/
           //cout <<"該數字出現在:_array["<< list1.Find(5) <<"]"<< endl;
           //list1.Erase(2);
           
           int ret=list1.Remove(7);
           if (ret == -1)
           {
                    cout << "not exit !" << endl;
           }
           else
           {
                    list1.Print();
           }
}
int main()
{
           //Test1();
           Test2();
           system("pause" );
           return 0;
}
  

  

 

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 我也是PHP新手,通過w3cschool瞭解了一下php基本原理之後就開寫了。但仍是菜鳥。 先不管3DES加密的方法對不對,方法都是網上的,在運行的時候報了個錯,把小弟整死了。找來找去終於自己摸出了方法。 代碼可以不看,就看裡面的一句:$td = mcrypt_module_open( MCRYPT ...
  • python有很多擴展模塊需要安裝 這個時候萬能的pip就可以提供幫助 首頁進入官網下載壓縮包: https://pypi.python.org/pypi/pip#downloads 解壓文件 cmd進入解壓文件路徑下輸入 python setup.py install 下來要使用pip一定要先進入 ...
  • 目錄 1. Apache Lucene(全文檢索引擎)—創建索引:http://www.cnblogs.com/hanyinglong/p/5387816.html 2. Apache Lucene(全文檢索引擎)—搜索:http://www.cnblogs.com/hanyinglong/p/53 ...
  • 1、簡介 這個和數組的排序又不一樣了。 其實Java針對數組和List的排序都有實現,對數組而言,你可以直接使用Arrays.sort,對於List和Vector而言,你可以使用Collections.sort方法。 Java API針對集合類型的排序提供了2個方法: 如果集合裡面的元素都是相同類型 ...
  • 項目中遇到將位元組數據文件解析成可展示的十進位,經過調查和測試得出下麵的轉換方法 1、將byte值轉換為二進位字元串: 2、將二進位字元串轉換為十進位: ...
  • 說明: 程式使用 io.h 中的 _findfirst 和 _findnext 函數遍歷文件夾,故而程式只能在 Windows 下使用。 程式遍歷當前文件夾,對其中的文件夾執行遞歸遍歷。同時檢查遍歷到的文件是否屬於指定類型,如果是,則將在該文件中查找指定字元串。 在文件中查找字元串時,開闢一個與指定 ...
  • eclipse中改變默然的workspace的方法可以有: 1.在創建project的時候,手動選擇使用新的workspace,如創建一個web project,在嚮導中的Location選項,取消使用"Use default location",同時在下麵選擇新的workspace. 2.在fil ...
  • 關於spl_autoload_register()和__autoload() 看兩者的用法: //__autoload用法 function __autoload($classname) { $filename = "./class/".$classname.".class.php"; if (is ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...