C++ 實現(xiàn)靜態(tài)鏈表的簡單實例
更新時間：2017年06月26日 16:33:46 投稿：lqh
這篇文章主要介紹了C++ 實現(xiàn)靜態(tài)鏈表的簡單實例的相關(guān)資料,需要的朋友可以參考下
C++ 實現(xiàn)靜態(tài)鏈表的簡單實例
用數(shù)組描述的鏈表，即稱為靜態(tài)鏈表。
在C語言中，靜態(tài)鏈表的表現(xiàn)形式即為結(jié)構(gòu)體數(shù)組，結(jié)構(gòu)體變量包括數(shù)據(jù)域data和游標cur。
這種存儲結(jié)構(gòu)，仍需要預先分配一個較大的空間，但在作為線性表的插入和刪除操作時不需移動元素，僅需修改指針，故仍具有鏈式存儲結(jié)構(gòu)的主要優(yōu)點。
下圖表示了靜態(tài)鏈表的一中存儲結(jié)構(gòu)：
圖中用彩色途上的是兩個頭結(jié)點，不存放數(shù)據(jù)，分別用來記錄第一個備用節(jié)點和第一個數(shù)據(jù)節(jié)點的下標。
下面給出靜態(tài)鏈表的C++實現(xiàn)代碼：
首先給出頭文件：StaticList.h:
#include<iostream>
#include<assert.h>
using namespace std;
#define MAXSIZE 20 // 靜態(tài)鏈表（數(shù)組）默認長度
#define ElemType int // 值類型
class StaticList;
//節(jié)點類
typedef class StaticListNode // 靜態(tài)鏈表的節(jié)點類型（數(shù)組元素類型）
{
friend class StaticList;
private:
ElemType data; // 值域
int cur; // 游標 （指示當前節(jié)點的下一個元素下標）
}StaticListNode;
// 靜態(tài)鏈表類</strong></span>
class StaticList
{
public:
StaticList()
{
for(int i = 2; i<MAXSIZE-1; ++i)
space[i].cur = i+1;
space[i].cur = 0; //整個鏈表結(jié)束
space[0].cur = 2;
space[1].cur = 0; //數(shù)據(jù)節(jié)點頭的游標為空，沒有數(shù)據(jù)
}
~StaticList()
{}
// 尾部插入法
void push_back(const ElemType &x)
{
int i = Malloc_SL();
if(0 == i) // 空間申請失敗
{
cout<<"已滿！"<<x<<"不能插入"<<endl;
return ;
}
space[i].data = x;
space[i].cur = 0;
int k = 1;
while(0!=k && 0!=space[k].cur) // 找到最后一個節(jié)點
k = space[k].cur;
space[k].cur = i; // 把剛申請的下標為i的節(jié)點鏈到最后一個節(jié)點后面
}
// 頭部插入法
void push_front(const ElemType &x)
{
int i = Malloc_SL();
if(0 == i) // 同上，空間申請失敗
{
cout<<"已滿！"<<x<<"不能插入"<<endl;
return ;
}
space[i].data = x; // 把x放入剛申請的節(jié)點中
space[i].cur = space[1].cur; // 此時剛申請的節(jié)點i的游標指向第一個數(shù)據(jù)節(jié)點，稱為第一個結(jié)點
space[1].cur = i; // 使頭結(jié)點指向第一個數(shù)據(jù)節(jié)點
}
// 尾部刪除
void pop_back()
{
int i = space[1].cur;
int j = 0;
for(; 0!=space[i].cur; j = i, i = space[i].cur)
{} // 找到最后一個節(jié)點以及倒數(shù)第二個節(jié)點
space[j].cur = 0; // 倒數(shù)第二個節(jié)點的游標賦空
Free_SL(i); // 最后一個節(jié)點被釋放
}
// 頭部刪除
void pop_front()
{
int i = space[1].cur; // i是第一個數(shù)據(jù)節(jié)點的下標
space[1].cur = space[i].cur; // 頭結(jié)點指向第二個數(shù)據(jù)節(jié)點的下標
Free_SL(i); // i 節(jié)點被釋放
}
void show_list()
{
for(int i = space[1].cur; i!=0; i = space[i].cur)
cout<<space[i].data<<" ";
cout<<"Over"<<endl;
}
/* 靜態(tài)鏈表從小到大排序的前提下，插入x */
void insert_val(const ElemType &x)
{
int k = 1;
while(0!=k && 0!=space[k].cur && space[space[k].cur].data<x)
k = space[k].cur; //在下標k之后插入
if(0 == space[k].cur) // 如果k指向最后一個節(jié)點，執(zhí)行尾插
push_back(x);
else if(k == 1) // 如果k指向第一個節(jié)點，執(zhí)行頭插
push_front(x);
else // 在中間任意位置插入x
{
int i = Malloc_SL();
assert(0 != i);
space[i].data = x;
space[i].cur = space[k].cur; // i節(jié)點的游標指向k節(jié)點后面的一個節(jié)點
space[k].cur = i; // k節(jié)點的游標指向新開辟的i節(jié)點
}
}
/* 返回key的前一個節(jié)點下標*/
int find(const ElemType &key)
{
int i = 1;
while(0!=i && space[space[i].cur].data!=key)
i = space[i].cur;
if(0 == i)
{
cout<<"沒找到 "<<key<<endl;
return -1;
}
return i;
}
/* 刪除給定的值key所在節(jié)點，若沒找到則返回 */
void delete_val(const ElemType &key)
{
int i = find(key);
if(-1 == i) // 說明靜態(tài)鏈表中沒有元素key
return ;
else if(1 == i) // key 處于下標為2的節(jié)點(第一個數(shù)據(jù)節(jié)點)
pop_front();
else if(0 == space[i].cur) // key處于最后一個節(jié)點
pop_back();
else // key 處于中間任意位置
{
int k = space[i].cur; // 記錄要刪除位置的下標
space[i].cur = space[k].cur; // 脫離出要刪除節(jié)點
Free_SL(k); // 刪除key所在節(jié)點
}
}
/* sl1 和 sl2已存在，把它們糅合到另一個鏈表，使之按非遞減排列 */
void merge(StaticList &sl1, StaticList &sl2)
{
sl1.sort();
sl2.sort();
if(0==sl1.length() || 0==sl2.length())
return ;
int p = sl1.space[1].cur;
int q = sl2.space[1].cur;
while(0!=p && 0!=q)
{
// 哪個數(shù)據(jù)較小，就把該數(shù)據(jù)尾插到新鏈表中，并使游標指向下一個
if(sl1.space[p].data < sl2.space[q].data)
{
push_back(sl1.space[p].data);
p = sl1.space[p].cur;
}
else
{
push_back(sl2.space[q].data);
q = sl2.space[q].cur;
}
}
while(0!=p)
{ // 因為sl1已經(jīng)有序，如果sl1還沒有全部插入新鏈表，就把剩下的全部插入
push_back(sl1.space[p].data);
p = sl1.space[p].cur;
}
while(0!=q)
{ // 因為sl2已經(jīng)有序，如果sl2還沒有全部插入新鏈表，就把剩下的全部插入
push_back(sl2.space[q].data);
q = sl2.space[q].cur;
}
}
/* 如果靜態(tài)鏈表無序，使其按非遞減順序排列 */
void sort()
{
int s = space[1].cur;
int p = space[s].cur;
if(0 == p)
return ;
space[s].cur = 0;
int k = 1;
int k1 = 0;
while(0 != p)
{
s = p;
p = space[p].cur;
k = 1; // 找到一個位置k, 在k后插入s所指節(jié)點的數(shù)據(jù)
while(0!=k && space[space[k].cur].data < space[s].data)
{
k1 = k; //如果k==0,用k1記錄最后一個數(shù)據(jù)節(jié)點
k = space[k].cur; //在下標k之后插入
}
if(0 == k) //尾插
{
space[k1].cur = s;
space[s].cur = 0;
}
else //頭插和中間插
{
space[s].cur = space[k].cur;
space[k].cur = s;
}
}
}
/* 逆置靜態(tài)鏈表 */
void reserve()
{
int s = space[1].cur;
int p = space[s].cur;
if( 0==p )
return ;
space[s].cur = 0;
while(0 != p)
{
s = p;
p = space[p].cur;
space[s].cur = space[1].cur; // 把s所指節(jié)點 頭插進原有鏈表
space[1].cur = s; // s成為第一個數(shù)據(jù)節(jié)點
}
}
/* 清空靜態(tài)鏈表 */
void clear()
{
for(int i = 2; i<MAXSIZE-1; ++i)
space[i].cur = i+1;
space[i].cur = 0;
space[0].cur = 2; // 下標2成為第一個備用節(jié)點
space[1].cur = 0; // 第一個數(shù)據(jù)節(jié)點為空
}
/* 返回表長 */
int length()
{
if(0 == space[1].cur)
return 0;
int i = 1;
int count = -1;
do
{
++count;
i = space[i].cur;
}while(0 != i);
return count;
}
/* 返回下標為k的節(jié)點的下一個節(jié)點下標 在靜態(tài)鏈表中用處不大*/
int next(const int k)
{
if(0==k || 1==k)
return -1;
return space[k].cur;
}
/* 返回下標為k的節(jié)點的上一個節(jié)點下標 */
int prio(const int k)
{
if(0==k || 1==k)
return -1;
int p = 1;
while(0!=p && space[p].cur!=k)
p = space[p].cur;
return p;
}
protected:
/* 用來申請一個空間，返回該節(jié)點的下標 */
int Malloc_SL()
{
int i = space[0].cur; // 0下標的游標指向第一個備用節(jié)點
if(space[0].cur) space[0].cur = space[i].cur; // 修改頭結(jié)點保存的第一個備用節(jié)點下標
return i;
}
/* 釋放下標為k的節(jié)點 */
void Free_SL(int k)
{
space[k].cur = space[0].cur; // 該節(jié)點的游標指向第一個備用節(jié)點
space[0].cur = k; // 該節(jié)點稱為第一個備用節(jié)點
}
private:
StaticListNode space[MAXSIZE];
};
下面是測試代碼：Main.cpp
#include"StaticList.h"
void main()
{
StaticList SL;
StaticList SL1; //測試merge()
StaticList SL2;
SL1.push_back(1);
SL1.push_back(9);
SL1.push_back(0);
SL1.push_back(6);
SL1.push_back(999);
SL2.push_back(5);
SL2.push_back(8);
SL2.push_back(100);
ElemType Item = 0;
int select = 1;
while(select)
{
cout<<"********************************************"<<endl;
cout<<"*[1] push_back [2] push_front *"<<endl;
cout<<"*[3] show_list [4] pop_back *"<<endl;
cout<<"*[5] pop_front [6] insert_val *"<<endl;
cout<<"*[7] length [8] find *"<<endl;
cout<<"*[9] merge [10] delete_val *"<<endl;
cout<<"*[11] sort [12] reserve *"<<endl;
cout<<"*[13] next [14] prio *"<<endl;
cout<<"*[15] clear [16] destroy *"<<endl;
cout<<"*[0] quit_sys *"<<endl;
cout<<"********************************************"<<endl;
cout<<"請選擇：》";
cin>>select;
switch(select)
{
case 1:
cout<<"輸入要尾插的數(shù)據(jù):(-1結(jié)束)>";
while(cin>>Item && -1 != Item)
SL.push_back(Item);
break;
case 2:
cout<<"輸入要頭插的數(shù)據(jù):(-1結(jié)束)>";
while(cin>>Item && -1 != Item)
SL.push_front(Item);
break;
case 3:
SL.show_list();
break;
case 4:
SL.pop_back();
break;
case 5:
SL.pop_front();
break;
case 6:
cout<<"輸入要插入的數(shù)據(jù):>";
cin>>Item;
SL.insert_val(Item);
break;
case 7:
cout<<"鏈表長度為："<<SL.length()<<endl;
break;
case 8:
cout<<"輸入要查找的數(shù)據(jù):>";
cin>>Item;
SL.find(Item);
break;
case 9:
SL.merge(SL1, SL2);
break;
case 10:
cout<<"輸入要刪除的數(shù)據(jù):>";
cin>>Item;
SL.delete_val(Item);
break;
case 11:
SL.sort();
break;
case 12:
SL.reserve();
break;
case 13:
SL.next(0);
break;
case 14:
SL.prio(0);
break;
case 15:
SL.clear();
break;
case 16:
SL.~StaticList();
break;
default:
break;
}
}
}
下面是測試截圖：
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關(guān)文章
這篇文章主要介紹了C語言枚舉的使用以及使用，閱讀下面內(nèi)容我們將掌握枚舉的相關(guān)概念、掌握枚舉的幾種用法、掌握枚舉在實際產(chǎn)品中的用法,需要的朋友可以參考一下2022-03-03
本篇文章主要介紹C語言中char的知識,并附有代碼實例,以便大家在學習的時候更好的理解,有需要的可以看一下2016-07-07
這篇文章主要為大家詳細介紹了C語言員工信息管理系統(tǒng)源代碼，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-12-12
探討:C++實現(xiàn)鏈式二叉樹(用非遞歸方式先序,中序,后序遍歷二叉樹)
本篇文章是對用C++實現(xiàn)鏈式二叉樹(用非遞歸方式先序,中序,后序遍歷二叉樹)的方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
文件通常是駐留在外部介質(zhì)(如磁盤等)上的,在使用時才調(diào)入內(nèi)存中來,本文主要來和大家介紹一下C語言中的文件操作,有需要的可以了解下2024-02-02
C++實現(xiàn)LeetCode(154.尋找旋轉(zhuǎn)有序數(shù)組的最小值之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(154.尋找旋轉(zhuǎn)有序數(shù)組的最小值之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了使用win32 api實現(xiàn)簡單的消息窗口示例,需要的朋友可以參考下2014-03-03
多維數(shù)組與多級指針是初學者經(jīng)常感覺迷糊的一個地方。超過二維的數(shù)組和超過二級的指針其實并不多用。但只要掌握一定的方法，理解多級指針和“多維”數(shù)組完全可以像理解一級指針和一維數(shù)組那樣簡單。2016-08-08
這篇文章主要給大家介紹了如何利用C++實現(xiàn)最長公共子序列與最長公共子串，文章一開始就給大家簡單的介紹了什么是子序列，子串應該比較好理解就不用多介紹了，人后通過算法及示例代碼詳細介紹了C++實現(xiàn)的方法，有需要的朋友們可以參考借鑒，下面來一起看看吧。2016-12-12
這篇文章主要介紹了C++虛函數(shù)的實現(xiàn)機制分析,需要的朋友可以參考下2014-07-07