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