C++ 實(shí)現(xiàn)靜態(tài)鏈表的簡(jiǎn)單實(shí)例
更新時(shí)間：2017年06月26日 16:33:46 投稿：lqh
這篇文章主要介紹了C++ 實(shí)現(xiàn)靜態(tài)鏈表的簡(jiǎn)單實(shí)例的相關(guān)資料,需要的朋友可以參考下
C++ 實(shí)現(xiàn)靜態(tài)鏈表的簡(jiǎn)單實(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)長(zhǎng)度
#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)為空
}
/* 返回表長(zhǎng) */
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<<"鏈表長(zhǎng)度為："<<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++簡(jiǎn)單實(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語言數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度及空間復(fù)雜度簡(jiǎn)要分析
我們?cè)谶M(jìn)行編程時(shí)，往往會(huì)開發(fā)諸多的算法，那么我們?cè)趺丛谀敲炊嗨惴ㄖ姓业阶詈玫哪莻€(gè)呢？本文主要介紹時(shí)間和空間復(fù)雜度概念及時(shí)間復(fù)雜度的求解，預(yù)祝讀者學(xué)習(xí)愉快2021-10-10
C 語言編寫一個(gè)計(jì)算器界面（可視化界面和多功能）
今天給大家分享一個(gè)計(jì)算器功能，主要功能有加法減法乘除法求余功能，用戶可以在主菜單選擇需要計(jì)算的功能，接下來根據(jù)用戶輸入的數(shù)字進(jìn)行計(jì)算輸出結(jié)果，喜歡的朋友拿去用吧2021-06-06
這篇文章主要介紹了Qt6.0開發(fā)環(huán)境搭建步驟(圖文)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
C/C++是兩種廣泛使用的編程語言,特別是在系統(tǒng)編程、嵌入式開發(fā)以及高性能計(jì)算領(lǐng)域,這篇文章主要介紹了C/C++錯(cuò)誤信息處理的常見方法及函數(shù),文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2025-04-04
opencv+arduino實(shí)現(xiàn)物體點(diǎn)追蹤效果
這篇文章主要為大家詳細(xì)介紹了opencv+arduino實(shí)現(xiàn)物體點(diǎn)追蹤效果，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
OpenCV實(shí)現(xiàn)Sobel邊緣檢測(cè)的示例
本文主要介紹了OpenCV實(shí)現(xiàn)Sobel邊緣檢測(cè)的示例，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
函數(shù)模板可以適用泛型來定義函數(shù)，其中泛型可以是（int, double, float）等替換。這篇文章主要來和大家聊聊函數(shù)模板的具體使用，感興趣的可以了解一下2023-03-03
這篇文章主要給大家介紹了關(guān)于C語言自定義數(shù)據(jù)類型的結(jié)構(gòu)體、枚舉和聯(lián)合的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04
這篇文章主要介紹了C++ 多態(tài)和虛函數(shù)的相關(guān)資料，文中示例代碼非常詳細(xì)，幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-07-07
strlen函數(shù)是用來求字符串長(zhǎng)度的函數(shù)，這個(gè)函數(shù)遇到‘\0’就會(huì)停止，且這個(gè)長(zhǎng)度不包含‘\0’，這篇文章給大家介紹了C語言中strlen()函數(shù)的使用，感興趣的朋友一起看看吧2024-02-02