資料結構學習實錄一 — 靜态連結清單

大家好，我是良哥，眼見期末考試越來越近，但由于我們資料結構老師技術太過厲害，導緻全班都處于不聽不聽，王八念經的狀态，是以今天我開始自學資料結構，并對其中難點部分進行C++程式設計實作，以此打破老師所謂的給你們正确代碼你們就不好好學的理由。他的代碼都是用word打的，‘=’打成‘-’，還自稱自己是專家，技術證明一切，計算機不存在老專家和經典。最新才最具有生命力，不進步就是外行，長江後浪推前浪，前浪死在沙灘上，歐耶！

首先我們來了解下靜态連結清單，什麼是靜态連結清單？我們知道，連結清單是動态結構，通過指針将資料串聯起來，隻要記憶體有空間就可以繼續配置設定連結清單，沒有固定的長度限制，是一種非常好用存儲結構，而且從作業系統原理上來說，他可以利用記憶體的碎片化空間，并且更容易找到合适空間配置設定，減少作業系統對記憶體空閑區域的檢索時間，在一定程度上提高了程式的速度，但是浪費了一定的空間用來存放指針，相對來說，犧牲空間，提升時間，對于較大記憶體調入來說，這個犧牲還是比較劃算的。

那麼什麼是靜态連結清單？我們指導，跟連結清單對應的是數組，在記憶體劃分一段連續空間，用來存放資料。優點是操作簡單，尋址快，但缺點同樣要命。首先數組要求在記憶體劃分連續區域，隻能使用較大的連續區域，這樣在一定程度上增加了作業系統的負擔，而且，連續區域不好找啊，劃分連續區域一定程度上就會造成記憶體碎片化，造成資源浪費。再考慮數組大小固定，擴容很麻煩，是以一般程式員會設定一個較大的空間，以防止記憶體溢出。但是如果使用者使用的資料量較小，就會造成浪費，同時也可能會造成記憶體溢出，導緻程式崩潰，也給計算機安全造成危害。不過對于小資料，使用數組的确是友善快捷。

而我們所讨論的靜态連結清單，簡直就是逆天的存在，将數組與連結清單結合起來，各取其缺點……，或許你内心一萬隻草泥馬在呼倫貝爾大草原上狂野奔騰，why ？猴子請來的逗比嗎？事實上，為了使用連結清單，在一些語言中是不能使用指針或者連結清單的，而為了使用連結清單，我們不得不把數組當連結清單用。

靜态連結清單：

1.定義結構體：SLinkList

typedef struct SLinkList
{
	int date;//存放資料
	int next;//指向下一個節點
}SLinkList;

我們知道，一般連結清單指向下一個節點的是指針，這個為什麼是數字？原因是他要記錄下一個節點在數組中的位置。并且我們約定，指針位為-2時，代表此位為空，指針位為-1時，代表他是連結清單末節點。

2.為靜态連結清單劃分空間

//為靜态連結清單劃分空間
SLinkList *newSl(int n)
{
	SLinkList* a = new SLinkList[n];
	for (int i = 0; i < n; i++)
	{
		a[i].date = 0;
		a[i].next = -2;
	}
	return a;
}

3.功能函數傳回靜态連結清單中的一個空位位址（以整形數字存儲）

//對靜态連結清單空位置進行檢索  return n,n為數組長度,-1為無空位
int nothing_num(SLinkList *a, int n)
{
	for (int i = 0; i < n; i++)
	{
		if (a[i].next == -2)
			return i;
	}
	return -1;
}

4.功能函數傳回靜态連結清單的末結點

//對靜态連結清單末節點進行檢索，傳回值為-1為檢索失敗
int end_num(SLinkList* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		if (a[i].next == -1)
			return i;
	}
	if (a[0].next == -2) return 0;
	return -1;
}

傳回值為‘-1’時，代表檢索失敗或是連結清單損壞。

5.功能函數對靜态連結清單進行初始或續寫入

//對靜态連結清單進行寫入或補充寫入
bool write(SLinkList* a, int *b, int nS,int nInt)
{
	int End_num = end_num(a, nS);
	int No_num = nothing_num(a, nS);
	for (int i = 0; i < nInt; i++)
	{
		if (End_num == -1 || No_num == -1)
			return false;
		a[End_num].next = No_num;
		a[No_num].date = b[i];
		a[No_num].next = -1;
		End_num = end_num(a, nS);
		No_num = nothing_num(a, nS);
	}
	return true;
}

傳回值為确定寫入是否成功

6.功能函數查找數值為num的節點位置

//查找數值為num的節點
int ifind(SLinkList* a, int n, int num)
{
	for (int i = 0; i < n; i++)
	{
		if (a[i].date == num)
			return i;
	}
	return -1;
}

傳回值為-1代表查找失敗

7.功能函數插入結點 poineer為其前結點位置，num為插入值

//插入結點
bool interposition(SLinkList* a, int n, int poineer,int num)
{
	int No_num = nothing_num(a, n);
	if (No_num == -1)return false;
	a[No_num].date = num;
	a[No_num].next = a[poineer].next;
	a[poineer].next = No_num;
	return true;
}

8.功能函數找到指向結點為NO的結點

//找到指向節點NO的結點
int Jfind(SLinkList* a, int n, int NO)
{
	for (int i = 0; i < n; i++)
	{
		if (a[i].next == NO)
			return i;
	}
	return -1;
}

9.功能函數删除某一結點

//删除節點
bool idelete(SLinkList* a, int n,int NO)
{
	if (NO > n || NO == n)
		return false;
	int J = Jfind(a, n, NO);
	if (J == -1)
		return false;
	a[J].next = a[NO].next;
	a[NO].next = -2;
	a[NO].date = 0;
	return true;
}

10.測試用主函數

int main()
{
	SLinkList *a = newSl(20);
	int b[10] = { 1,2,3,4,5,6,7,8,9,10 };
	bool pd = write(a, b, 20, 10);
	int ii = 0;
	if (pd == false)
		cout << "寫入失敗" << endl;
	else
	{
		cout << "寫入成功，寫入結果為：" << endl;
		while (a[ii].next != -1)
		{
			cout << a[ii].date << '\t';
			ii = a[ii].next;
		}
		cout << endl;
		cout << "測試查找結點，正确答案為：4 測試結果為" << ifind(a, 20, 5);
		cout << endl;
		cout << "測試插入函數" << endl;
		if (!interposition(a, 20, 2, 11))
			cout << "插入失敗" << endl;
		else
		{
			cout << "插入結果為：" << endl;
			ii = 0;
			while (a[ii].next != -1)
			{
				cout << a[ii].date << '\t';
				ii = a[ii].next;
			}
		}
		cout << endl;
		cout << "測試删除函數" << endl;
		if (idelete(a, 20, 10))
		{
			cout << "删除結果為：" << endl;
			ii = 0;
			while (a[ii].next != -1)
			{
				cout << a[ii].date << '\t';
				ii = a[ii].next;
			}
		}
		else
			cout << "删除失敗" << endl;
		cout << endl;

	}
	system("pause");
    return 0;
}

附贈整個解決方案，使用VS2015編輯

// SLinkList.cpp : 定義控制台應用程式的入口點。
//

#include "stdafx.h"
#include"iostream"

using namespace std;

typedef struct SLinkList
{
	int date;
	int next;
}SLinkList;
//生成新的靜态連結清單
SLinkList *newSl(int n)
{
	SLinkList* a = new SLinkList[n];
	for (int i = 0; i < n; i++)
	{
		a[i].date = 0;
		a[i].next = -2;
	}
	return a;
}
//對靜态連結清單空位置進行檢索  return n,n為位置,-1為無空位
int nothing_num(SLinkList *a, int n)
{
	for (int i = 0; i < n; i++)
	{
		if (a[i].next == -2)
			return i;
	}
	return -1;
}
//對靜态連結清單末節點進行檢索，傳回值為-1為檢索失敗
int end_num(SLinkList* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		if (a[i].next == -1)
			return i;
	}
	for (int i = 0; i < n; i++)
	{
		if (a[i].next != -2) return -1;
	}
	return 0;
}

//對靜态連結清單進行寫入或補充寫入
bool write(SLinkList* a, int *b, int nS,int nInt)
{
	int End_num = end_num(a, nS);
	int No_num = nothing_num(a, nS);
	for (int i = 0; i < nInt; i++)
	{
		if (End_num == -1 || No_num == -1)
			return false;
		a[End_num].next = No_num;
		a[No_num].date = b[i];
		a[No_num].next = -1;
		End_num = end_num(a, nS);
		No_num = nothing_num(a, nS);
	}
	return true;
}
//查找數值為num的節點
int ifind(SLinkList* a, int n, int num)
{
	for (int i = 0; i < n; i++)
	{
		if (a[i].date == num)
			return i;
	}
	return -1;
}
//插入結點
bool interposition(SLinkList* a, int n, int poineer,int num)
{
	int No_num = nothing_num(a, n);
	if (No_num == -1)return false;
	a[No_num].date = num;
	a[No_num].next = a[poineer].next;
	a[poineer].next = No_num;
	return true;
}
//找到指向節點NO的結點
int Jfind(SLinkList* a, int n, int NO)
{
	for (int i = 0; i < n; i++)
	{
		if (a[i].next == NO)
			return i;
	}
	return -1;
}
//删除節點
bool idelete(SLinkList* a, int n,int NO)
{
	if (NO > n || NO == n)
		return false;
	int J = Jfind(a, n, NO);
	if (J == -1)
		return false;
	a[J].next = a[NO].next;
	a[NO].next = -2;
	a[NO].date = 0;
	return true;
}

int main()
{
	SLinkList *a = newSl(20);
	int b[10] = { 1,2,3,4,5,6,7,8,9,10 };
	bool pd = write(a, b, 20, 10);
	int ii = 0;
	if (pd == false)
		cout << "寫入失敗" << endl;
	else
	{
		cout << "寫入成功，寫入結果為：" << endl;
		while (a[ii].next != -1)
		{
			cout << a[ii].date << '\t';
			ii = a[ii].next;
		}
		cout << endl;
		cout << "測試查找結點，正确答案為：4 測試結果為" << ifind(a, 20, 5);
		cout << endl;
		cout << "測試插入函數" << endl;
		if (!interposition(a, 20, 2, 11))
			cout << "插入失敗" << endl;
		else
		{
			cout << "插入結果為：" << endl;
			ii = 0;
			while (a[ii].next != -1)
			{
				cout << a[ii].date << '\t';
				ii = a[ii].next;
			}
		}
		cout << endl;
		cout << "測試删除函數" << endl;
		if (idelete(a, 20, 10))
		{
			cout << "删除結果為：" << endl;
			ii = 0;
			while (a[ii].next != -1)
			{
				cout << a[ii].date << '\t';
				ii = a[ii].next;
			}
		}
		else
			cout << "删除失敗" << endl;
		cout << endl;

	}
	system("pause");
    return 0;
}

本文為作者原創，任何形式的引用、轉載等操作請提前獲得作者授權，未經授權，禁止以任何形式引用或轉載此文。

資料結構學習實錄一 — 靜态連結清單

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器