數據結構2----線性表順序存儲和鏈式存儲的實現(霜之小刀)

2019-11-11 05:24:43

字體：大中小

來源：轉載

供稿：網友

歡迎轉載和引用，若有問題請聯系若有問題，請聯系 Email : lihn1011@163.com QQ:2279557541

定義

所謂線性表，其實就是具有“線”一樣性質的表，所謂線一樣的性質，也就是具有n個數據元素的優先序列。其中n>=0

抽象數據模型

/** * 抽象的線性表接口 * 其中DataType表示線性表中所存儲的數據類型 */template<class DataType>class ListInterface{public: /** * @brief 用于判斷當前線性表是否為空 * @return true:為空 false:不為空 */ virtual bool IsEmpty() = 0; /** * @brief 獲取當前線性表的長度 * @return 表的長途 */ virtual unsigned int GetLength() = 0; /** * @brief 獲取線性表中的一個數據 * @param i數據所在的位置，也就是第幾個數據 * @param data 若數據獲取成功，則用于傳出數據 * @return 數據是否獲取成功 */ virtual bool GetItem(unsigned int i, DataType& data) = 0; /** * @brief 查找某個數據在線性表中的位置 * @param data 要查找的數據 * @return -1：查找失敗 else 查找的數據在線性表中的位置 */ virtual int FindItem (DataType data) = 0; /** * @brief 刪除線性表中的所有數據 */ virtual void Clear(); /** * @brief 向線性表中插入數據 * @param i 要插入線性表的位置 * @param data 要插入的數據 * @return 是否插入成功 */ virtual bool InsertItem(unsigned int i, DataType data) = 0; /** * @brief 刪除線性表中的某個數據 * @param i 要刪除的數據所處的位置 * @return 是否刪除成功 */ virtual bool DeleteItem(unsigned int i) = 0;};

其實線性表是可以擁有更多操作的，但是這里只列出了我認為最常用的一些。雖然抽象完成了，但是要寫具體實現，這里就有點問題了，因為線性表的物理結構有兩種，分別為

順序存儲結構鏈式存儲結構

順序存儲結構的實現方式

我們發現這個線性表的順序存儲結構有以下特點

表中數據的多少只需修改m_length即可改變。無論表中當前數據有多少，實際的存儲數據的區域都不會發生變化，也就是有多余的內存空間會被浪費。最大容量有限制，如果要動態，則會增加拷貝和內存管理工作，效率底下。插入刪除一個元素時，需要移動操作點后面的所有數據，效率底下。獲取表中某個數據時，可以直接索引，效率非常高。

鏈式存儲結構的實現方式

/** * 線性列表的順序存儲實現 * 未考慮max_size溢出的情況 */template<class DataType,int max_size>class QueueList:public ListInterface<DataType>{public: QueueList() { m_length = 0; } /** * @brief 用于判斷當前線性表是否為空 * @return true:為空 false:不為空 */ virtual bool IsEmpty() { return m_length?true:false; } /** * @brief 獲取當前線性表的長度 * @return 表的長途 */ virtual unsigned int GetLength() { return m_length; } /** * @brief 獲取線性表中的一個數據 * @param i數據所在的位置，也就是第幾個數據 * @param data 若數據獲取成功，則用于傳出數據 * @return 數據是否獲取成功 */ virtual bool GetItem(unsigned int i, DataType& data) { if(i >= m_length)return false; data = m_data_list[i]; return true; } /** * @brief 查找某個數據在線性表中的位置 * @param data 要查找的數據 * @return -1：查找失敗 else 查找的數據在線性表中的位置 */ virtual int FindItem (DataType data) { for(int i = 0; i < m_length; i++) { if(data == m_data_list[i]) { return i; } } return -1; } /** * @brief 刪除線性表中的所有數據 */ virtual void Clear() { m_length = 0; } /** * @brief 向線性表中插入數據 * @param i 要插入線性表的位置 * @param data 要插入的數據 * @return 是否插入成功 */ virtual bool InsertItem(unsigned int i, DataType data) { if(i <= m_length) { for(int idx = m_length;idx > i; idx--) { m_data_list[idx] = m_data_list[idx-1]; } m_data_list[i] = data; m_length++; return true; } return false; } /** * @brief 刪除線性表中的某個數據 * @param i 要刪除的數據所處的位置 * @return 是否刪除成功 */ virtual bool DeleteItem(unsigned int i) { if(i >= m_length) { return false; } for(int idx = i; idx < m_length; idx++) { m_data_list[idx] = m_data_list[idx+1]; } m_length--; return true; }private: DataType m_data_list[max_size]; unsigned int m_length;public: void Show() { qDebug()<<"start========"; for(int i = 0; i < m_length; i++) { DataType data; GetItem(i, data); qDebug()<<data; } qDebug()<<"end========"; }};template<class DataType>class LinkedList:public ListInterface<DataType>{public: LinkedList():m_length(0),m_head(NULL) { } /** * @brief 用于判斷當前線性表是否為空 * @return true:為空 false:不為空 */ virtual bool IsEmpty() { return m_length?true:false; } /** * @brief 獲取當前線性表的長度 * @return 表的長途 */ virtual unsigned int GetLength() { return m_length; } /** * @brief 獲取線性表中的一個數據 * @param i數據所在的位置，也就是第幾個數據 * @param data 若數據獲取成功，則用于傳出數據 * @return 數據是否獲取成功 */ virtual bool GetItem(unsigned int i, DataType& data) { if(i >= m_length)return false; LinkStu* p = m_head; while(i--) { p=p->m_next; } data = p->m_data; return true; } /** * @brief 查找某個數據在線性表中的位置 * @param data 要查找的數據 * @return -1：查找失敗 else 查找的數據在線性表中的位置 */ virtual int FindItem (DataType data) { int finded_idx = 0; LinkStu* p = m_head; while(p) { if(data == p->m_data) { return finded_idx; } finded_idx++; } return -1; } /** * @brief 刪除線性表中的所有數據 */ virtual void Clear() { while(DeleteItem(0)); m_length = 0; } /** * @brief 向線性表中插入數據 * @param i 要插入線性表的位置 * @param data 要插入的數據 * @return 是否插入成功 */ virtual bool InsertItem(unsigned int i, DataType data) { if(i <= m_length) { LinkStu* new_link = new LinkStu(); new_link->m_data = data; if(i == 0) { new_link->m_next = m_head; m_head = new_link; } else { LinkStu* p = m_head; LinkStu* pre_p = m_head; for(int idx = 0; idx != i; idx++) { pre_p = p; p = p->m_next; } pre_p->m_next = new_link; new_link->m_next = p; } m_length++; return true; } return false; } /** * @brief 刪除線性表中的某個數據 * @param i 要刪除的數據所處的位置 * @return 是否刪除成功 */ virtual bool DeleteItem(unsigned int i) { if(i >= m_length) { return false; } if(i == 0) { LinkStu* p = m_head; m_head = m_head->m_next; delete p; } else { LinkStu* p = m_head; LinkStu* pre_p = m_head; for(int idx = 0; idx != i; idx++) { pre_p = p; p = p->m_next; } pre_p->m_next = p->m_next; delete p; } m_length--; return true; }private: struct LinkStu { DataType m_data; LinkStu* m_next; LinkStu():m_next(NULL){} }; unsigned int m_length; LinkStu* m_head;};表中數據的增減會直接增加或減少內存的占用量。邏輯上表的大小是無限的。插入刪除一個元素時，只要找到了元素的位置，操作效率非常高。獲取表中某個數據時，效率較低。

上一篇：bzoj 3687: 簡單題（dp+bitset）

下一篇：The 10th Zhejiang Provincial Collegiate Programming Contest