資料結構之順序與鏈表

順序表
- 順序表的概念
- 順序表的一些操作[函式實作]
- - 1.初始化
  - 2.列印
  - 3.檢車是否需要擴容
  - 4.尾插實作
  - 5.頭插實作
  - 6.尾刪實作
  - 7.頭刪實作
  - 8.查找
  - 8.指定位置插入
  - 10.指定位置洗掉
  - 11.改變指定內容
  - 12.銷毀
鏈表
- 鏈表的概念
- 鏈表表的一些操作[函式實作]
- - 1.創建一個鏈表的節點
  - 2.尾插
  - 3.頭插
  - 4.尾刪
  - 5.頭刪
  - 6.查找
  - 7.在pos位置之后插入x
  - 8.在pos位置之后洗掉x
  - 9.在pos位置洗掉節點
  - 10.列印節點
總結

上一篇文章說到資料結構的四大基本結構，集合結構，線性結構，樹結構，圖結構，所以我們學習資料結構其實也是按照這個順序進行了，從邏輯結構的層次上然后又可以去認識到-----即便是一種邏輯結構也會有不同的存盤結構，順序存盤與鏈式存盤，
OK，那我們從集合結構開始學嗎？其實不必，集合其實對于我們來說并不陌生啊，C語言中的陣列在某一種程度來說，我認為他就是一種集合啊，陣列中存盤著大量的陣列或者是字符，他不就代表著數字或者字符的集合嗎？如果是學過python的小伙伴們應該知道，python中直接就有一個型別就是集合，
那我們資料結構就從線性結構開始了，

常見的線性結構有那些呢？順序表，鏈表，堆疊，佇列以及字串，我們把這些統稱為線性表【后續希望可以都出一篇總結總結@_@】
本篇我們考慮順序表和鏈表！

順序表

順序表的概念

順序表其實就是一種特殊的陣列(這里說的是動態順序表，靜態順序表可以說就是陣列了)
為什么說他是特殊的陣列呢？

可以動態的增長
并且資料是連續的，必須是從左到右連續的
要求不能有元素與元素中間不能有空著的

什么叫動態增長？回想定義陣列的時候，我們說int a[100]，這個100必須是一個常量是定值(C99之前)，或者不寫，但是后面跟需要跟初始化就能知道陣列的大小了，否則在進行操作的時候就會出現陣列越界，但是現實中，我們可能也不太清楚后續究竟會使用多少空間，這就是缺陷，順序表就完善了這個缺陷，使用malloc動態分配記憶體，

當然了動態增容確實完善了靜態陣列的缺陷，但是她本身也是有缺點了，使用malloc是有性能消耗的，同樣的由于我們也不確定可能會使用多大空間，所以也許開辟的空間我們沒有使用到，這也是一種浪費，

了解到了這些概念之后，我們開始創建一個順序表瞧瞧，

struct SeqList
{
	int* a;//使用指標，malloc創建，后續可以使用realloc擴容，這就是動態了
	int size;//記錄有效資料的個數
    int capicity;//記錄容量空間的大小
};

不知道會不會有人問前面說到順序表是陣列結果我寫了個結構體出來了，這里我們所說的順序表實際上還是操作到了a上不是嗎，就像陣列開辟一樣，arr[100]，我們不也有一個100可以表識她的大小嗎，這里的capicity和size就和100的作用是一樣的，就比如今天我們待了個眼睛和口罩，總不能說不是人了吧~

平時我們會因為寫結構體很繁瑣，創建一個順序表要寫成struct SeqList *seq，但是使用typedef就可以直接寫成SeqList *seq(雖然只是少些一個單詞，但是后續也不知道要寫幾遍，能少些一些就少些一些！)

typedef struct SeqList
{
	SeqDataType* a;
	int size;
	int capacity;
}SeqList;

順序表的一些操作[函式實作]

1.初始化

void SeqListInit(SeqList *seq)
{
	assert(seq != NULL);//終止程式了報錯
	seq->a = NULL;
	seq->size = seq->capacity = 0;
}

2.列印

void SeqListPrint(SeqList* seq)
{
	assert(seq);
	for (int i = 0; i < seq->size; i++)
	{
		printf("%d ", seq->a[i]);
	}
	printf("\n");
}

3.檢車是否需要擴容

realloc會檢測記憶體后面空間是否足夠使用，如果夠就不用增容，如果不夠就會增容了，并且增容的時候還會檢查增容的地方是否已經被占用了，如果被占用了還會在另一塊記憶體開辟空間，然后將資料拷貝過去，回傳新記憶體的地址，
所以說擴容也是有代價的，

void SeqCheckCapacity(SeqList* seq)
{
	//滿了需要增容
	if (seq->size == seq->capacity)
	{
		//一般增容會多增一些2倍基準增容
		int newcapacity = seq->capacity == 0 ? 4 : seq->capacity * 2;
		SeqDataType* newA = realloc(seq->a, sizeof(SeqDataType) * newcapacity);
		if (newA == NULL)
		{
			printf("relloc fail\n");
			exit(-1);
		}
		seq->a = newA;
		seq->capacity = newcapacity;
	}
}

4.尾插實作

兩種實作方式，如果使用使用下面寫到的任意位置洗掉的函式，認為是最后一個位置洗掉就好

void SeqListPushBack(SeqList* seq, SeqDataType x)
{
	SeqListInsert(seq, seq->size,x);
}

不使用的時候直接洗掉size位

	assert(seq);
	//滿了需要增容
	SeqCheckCapacity(seq);
	seq->a[seq->size] = x;
	seq->size++;

5.頭插實作

同樣的兩種實作方式
使用的時候

void SeqListPushBack(SeqList* seq, SeqDataType x)
{
	SeqListInsert(seq, 0, x);
}

不使用的時候

void SeqListPushBack(SeqList* seq, SeqDataType x)
{
	assert(seq);
	SeqCheckCapacity(seq);//seq在這里是&s，本身就是已經是地址了，所以不要取地址了
	int end = seq->size - 1;
	while (end >= 0)
	{
		seq->a[end + 1] = seq->a[end];
		--end;
	}
	seq->a[0] = x;
	seq->size++;
}

6.尾刪實作

使用后續封裝函式

void SeqListPopBack(SeqList* seq)
{
	SeqListErase(seq, seq->size - 1);
}

不使用

void SeqListPopBack(SeqList* seq)
{
	assert(seq);
	assert(seq->size>0);
	--seq->size;
}

7.頭刪實作

使用后續封裝函式

void SeqListPopBack(SeqList* seq)
{
	SeqListErase(seq,0);
}

不使用

void SeqListPopBack(SeqList* seq)
{
	assert(seq);
	assert(seq->size>0);
	int begin = 0;
	while (begin < seq->size - 1)
	{
		seq->a[begin] = seq->a[begin + 1];
		++begin;
	}
	seq->size--;
}

8.查找

int SeqListFind(SeqList* seq, SeqDataType x)
{
	assert(seq);
	for (int i = 0; i < seq->size; i++)
	{
		if (seq->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

8.指定位置插入

void SeqListInsert(SeqList* seq, int pos, SeqDataType x)
{
	assert(seq);
	assert(pos >= 0&&pos<=seq->size);
	SeqCheckCapacity(seq);
	int end = seq->size - 1;
	while (end >= pos)
	{
		seq->a[end + 1] = seq->a[end];
		--end;
	}
	seq->a[pos] = x;
	seq->size++;
}

10.指定位置洗掉

void SeqListErase(SeqList* seq, int pos)
{
	assert(seq);
	assert(pos >= 0 && pos < seq->size);//不能=，上面是方便尾插
	int begin = pos;
	for (; begin < seq->size; begin++)
	{
		seq->a[begin] = seq->a[begin + 1];
	}
	seq->size--;
}

11.改變指定內容

void SeqListModify(SeqList* seq, int pos, SeqDataType x)
{
	assert(seq);
	assert(pos >= 0 && pos < seq->size);
	seq->a[pos] = x;
}

12.銷毀

void SeqListDestory(SeqList* seq)
{
	free(seq->a);
	seq->a = NULL;
	seq->capacity = seq->size = 0;
}

鏈表

鏈表的概念

說完了順序表，我們開始學習鏈表了，
在此之前依舊是知道為什么會出現鏈表，后續可能會更好理解一些，其實在實作順序表的程序中我們就會發現，頭插的時候我們會將所有的元素后移然后空出第一個位置

其實實作的時候就發現了這個程序容易需要想清楚移動結束條件，就比尾插難了一點了，而且這對于程式來說也不好受，如果需要移動大量元素，時間復雜度會越來越大，以及上述所說的，增容也是一大消耗

所以鏈表就出現了，它就完美解決了這兩個問題，第一它使用鏈式(指標結構)，直接就可以在某一個位置連接上一個部分，解決了第一個問題，不用挪動大量元素，然后它開辟記憶體是需要就開辟，不需要就不開辟的，不僅僅結局了動態增容的消耗，甚至解決了增容可能出現的空間浪費，

怎么去理解鏈式結構，大家做過火車動車吧，如果說有一節火車出現了問題，那是不是可以直接把這一節車廂換下來，但是不影響其他車型連接，去百度了一番圖片，甚至發現了一節車廂的火車哈哈哈哈

這里說個插曲，我上學期回家坐高鐵回家的時候，車廂是14節某座，進站之后，那個高鐵只要8節，嚇壞我了，然后我去問附近的乘務員，人家看了我網上車票說不可能吧，這個車只有8節啊，雖說這樣但是還是讓我上去了，但是還是跟列車長反映了，最后大概就是后面那8節維修或者什么原因給拆了

在這里插入圖片描述
現在是不是對于鏈表有了一定認識？
依舊是創建一個鏈表看看

通過指標達到鏈式的結構了

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

鏈表的結構復雜多樣，還有回圈鏈表，雙向鏈表，帶頭節點鏈表，不帶頭節點鏈表，初學鏈表，我們以不帶頭節點不回圈非雙向入門鏈表~

鏈表表的一些操作[函式實作]

1.創建一個鏈表的節點

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	node->data = x;
	node->next = NULL;
	return node;
}

2.尾插

void SListPushBack(SLTNode **pplist,SLTDataType x)
{
	//創建新節點
	SLTNode* newnode = BuySLTNode(x);
	SLTNode* tail = *pplist;
	//分空指標與非空指標
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//newnode是指標變數就是一個地址
		tail->next = newnode;
	}
}

3.頭插

void SListPushFront(SLTNode** pplist, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

4.尾刪

void SListPopBack(SLTNode** pplist)
{
	//沒有節點的情況
	if (*pplist == NULL)
	{
		return;
	}
	else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pplist;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;//注意前一個節點的next要置空
	}
	
}

5.頭刪

void SListPopFront(SLTNode** pplist)
{
	if (*pplist != NULL)
	{
		SLTNode* tail = *pplist;
		*pplist = (*pplist)->next;
		free(tail);
		tail = NULL;
	}
	else
	{
		return;
	}
}

6.查找

SLTNode* SListFind(SLTNode* plist, SLTDataType x)
{
	SLTNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

7.在pos位置之后插入x

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

在單鏈表pos位置插入插入節點

注意這里要保存前一個節點，不然無法實作前插

void SListInsertbefore(SLTNode** pplist, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);

	//如果在第一個節點那插入，就是頭插法
	if (pos == *pplist)
	{
		newnode->next = pos;
		*pplist = newnode;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* cur = *pplist;
		while (cur != pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}

}

8.在pos位置之后洗掉x

void SListEraseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* next = pos->next;
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

9.在pos位置洗掉節點

void SListEraseCur(SLTNode **pplist,SLTNode* pos)
{
	assert(pos);
	if (pos==*pplist)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SLTNode* cur = NULL;
		SLTNode* tail = *pplist;
		while (tail != pos)
		{
			cur = tail;
			tail = tail->next;			
		}
		cur->next = tail->next ;
		free(pos);
		pos = NULL;
	}
}

10.列印節點

void SListPrint(SLTNode* plist)
{
	SLTNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

總結

今天就寫到這里了，后續會更新其他線性結構的內容了，
要學的東西真多，但是學著有意義，希望自己可以保持樂而不疲的狀態~

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/395121.html

標籤：其他

上一篇：[JDK原始碼]-J.U.C-ConcurrentSkipListMap

下一篇：如何在aspnetcorewebAPI上正確地將串列轉換為IQueryable

【資料結構】從零實作順序表+鏈表相關操作