C語言超詳細講解線性表

2022-07-03 14:02:36

1. 順序表

順序表是指用一段連續的地址，依次存放資料元素的線性資料結構。此種儲存方式使得順序表的物理結構與邏輯結構都是連續的。

與陣列的區別：函數中的陣列被存放在棧段中，而棧段有系統限制的大小（可使用ulimit -s檢視系統限制的大小，單位為KB），因此順序表往往使用在堆段中操作管理動態陣列的方式實現。

1.1 管理結點

在順序表中，管理節點內部一般存放：資料域地址(*data)、**總容量(size)以及當前資料量(len)**等等。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Vector {
	//資料域 
	int *data;
	//總容量 
	int size;
	//當前元素個數 或 指向末尾元素的後一位
	int len;
} Vector; 
//初始化
Vector *initVector(int size){
	Vector *v = (Vector *) malloc(sizeof(Vertor));
	v->data = (int *) malloc(sizeof(int) * size);
	v->len = 0;
	v->size = size;
	return v; 
} 
//釋放
void freeVector(Vector *v){
	if(!v) return;
	free(v->data);
	free(v);
}
int main(){
	//初始化size為10的線性表
	Vector *v = initVector(10)
	return 0;
}

1.2 順序表的插入

//插入 
//將 v->data[idx] 處變成 val 
void insert(Vector *v, int idx, int val){
	//判斷 v 是否為空 返回 
	if(!v) return; 
	//判斷 idx 是否合法 
	if(idx > v->len || idx < 0) return ;
	//判斷 v 的容量是否已滿
	if(v->len == v->size) return ; 
	//維護順序表的特性  將 idx 及之後的元素後移 
	for(int i = v->len; i > idx ;i++){
		v->data[i] = v->data[i - 1];
	}
	//在 idx 處插入資料 
	v->data[i] = val;
	//更新當前元素個數 
	v->len++; 
}

1.3 順序表的刪除

//刪除
//將 v->data[idx] 刪除 
void delete(Vector *v, int idx){
	if(!v) return ;
	if(idx >= v->len || idx < 0) return ;
	// idx 之後的元素前移
	for(int i = idx; i < v->len-1; i++){
		v->data[i] = v->data[i + 1];
	}
	v->len--;
}

1.4 順序表的擴容

擴容：新建立原size * 2 的空間，然後將原資料從原空間遷移到新空間

//倍增法擴容 size -> size + exsize
int expand(Vector *v){
	//擴容為 size + exSize 
	int exSize = v->size;
	int *tmp;
	while(exSize){
		//嘗試向記憶體申請空間 
		tmp = (int *) realloc(v->data, sizeof(int) * (v->size + exSize));
		//申請成功 
		if(tmp) break;
		//申請不成功 exSize/2 繼續申請 
		exSize >>= 1; 
	}
	//徹底失敗 未申請到空間 
	if(!tmp) return 0;
	//擴容成功
	v->data = tmp; 
	v->size += exSize;
	return 1;
}
//插入 
//將 v->data[idx] 處變成 val 
void insert(Vector *v, int idx, int val){
	...
	if(v->len == v->size) {
		//嘗試擴容 擴容成功為 1 失敗為 0 
		if(!expand(v)) return; 
	} 
	...
}

2. 連結串列

2.1 定義

連結串列是一種物理結構不連續，但可以依靠結點中的指標實現邏輯結構連續的線性資料結構。

構成連結串列的資料元素被稱為“結點”，節點內部存放資料與指向下一個結點的指標。

//定義結點 
typedef struct Node{
	int val;
	struct Node *next;
} Node; 
//結點初始化 
Node *initNode(int val){
	Node *node = (Node *) malloc(sizeof(Node));
	node->val = val;
	node->next = NULL;
	return node;
} 
//釋放結點
void freeNode(Node *node){
	if(!node) return ;
	free(node);
}

只有單一結點指標的連結串列的全程是“單連結串列”，經常被簡稱為連結串列。

連結串列的管理結點一般僅需要存放頭結點指標(*head)。

如果需要頻繁獲取連結串列長度，管理結點中可以額外存放連結串列長度(len)。

//定義連結串列 管理結點 
typedef struct List{
	Node *head;
	int len;
} List;
//初始化連結串列
List *initList() {
	List *list = (List *) malloc(sizeof(List));
	list->head = NULL;
	list->len = 0;
	return list;
}

2.2 頭部插入

頭插法：將新插入的節點放在 head 後，時間複雜度O（1）

//頭部插入
void insertToHead(List *list, int val){
	if(!list) return ;
	Node *node = initNode(val);
	node->next = list->head;
	list->head = node;
	list->len++;
}

2.3 尾部插入

尾插法：找到最後一個結點，將新節點插入。如果沒有設計尾指標，則時間複雜度為O（n）。

//尾部插入 
void insertToTail(List *list, int val){
	if(!list) return ;
	Node *node = initNode(val);
	//如果list為空 則node為第一個結點 讓head等於node
	//判斷條件可更改為list->len == 0 
	if(list->head == NULL){
		list->head = node;
		list->len++;
		return ;
	}
	Node *p = list->head;
	while(p->next != NUll){
		p = p->next;
	}
	p->next = node;
	list->len++;
}

//測試
int main(){
	List *list1 = initList();
	List *list2 = initList();
	for(int i = 0;i <= 10;i += 2){
		insertToHead(list1,i);
	}
	Node *p = list1->head;
	while(p){
		printf("%d -> ",p->val);
		p = p->next;
	}
	printf("n");
	for(int i = 1;i <= 10;i += 2){
		insertToTail(list2,i);
	}
	Node *q = list2->head;
	while(q){
		printf("%d -> ",q->val);
		q = q->next;
	}
	printf("n");
	return 0;
}

輸出結果：

2.4 任意位置插入

//任意位置的插入
// idx = 0 待插入結點為頭結點
// idx > 0 插入至第 i 個結點後
void insert(List *list, int idx, int val){
	if(!list) return ;
	if(idx > list->len || idx < 0) return ;
	if(idx == 0){
		//頭插法 
		insertToHead(list,val);
		return;
	}
	Node *node = initNode(val);
	//結點索引為 0 
	Node *p = list->head;
	//p 找到第 idx - 1個結點
	// i = 1  結點索引為 1 
	// i = 2 結點索引為 2
	// i = idx - 1 結點索引為 idx - 1 
	for(int i = 1;i <= idx - 1;i++){
		p = p->next;
	} 
	//插入
	node->next = p->next;
	p->next = node;
	list->len++;
}

2.5 任意位置刪除

//任意位置的刪除 
void remove(List *list, int idx){
	if(!list) return ;
	if(idx > list->len || idx < 0) return ;
	//p為0號索引結點
	Node *p = list->head;
	//刪除索引為 0 的結點 更改head 
	if(idx == 0){
		list->head = p->next; 
		list->len--;
		freeNode(p);
		return;
	}
	//找到idx-1個結點
	for(int i = 1;i <= idx - 1;i ++){
		p = p->next;
	}
	Node *node = p->next;
	//刪除 
	p->next = p->next->next;
	list->len--;
	freeNode(node);
}

2.6 虛頭結點

在需要特殊處理頭結點的時候，可以實現一個帶有虛頭結點的連結串列。在連結串列初始化或在某些操作執行時，將一個額外的結點放在頭指標執行的地方。虛頭結點可以使得整個連結串列永遠不空，永遠有頭。所以擁有虛頭結點的連結串列在處理各類結點操作時會更加便捷。

任意位置插入：不需要特殊考慮插入位置是否在連結串列頭部。

任意位置刪除：不需要特殊考慮刪除的結點是否是連結串列的第一個結點。

//結點部分沒有改動
//定義結點 
typedef struct Node{
	int val;
	struct Node *next;
} Node; 
//結點初始化 
Node *initNode(int val){
	Node *node = (Node *) malloc(sizeof(Node));
	node->val = val;
	node->next = NULL;
	return node;
} 
//釋放結點
void freeNode(Node *node){
	if(!node) return ;
	free(node);
}

//定義連結串列 管理結點 
typedef struct List{
	Node *head;
	int len;
} List;
//初始化連結串列
List *initList() {
	List *list = (List *) malloc(sizeof(List));
	//變動  ：初始化的時候賦予一個結點 任意數值都可以 
	list->head = initNode(-1);
	list->len = 0;
	return list;
}
//頭部插入
void insertToHead(List *list, int val){
	if(!list) return ;
	Node *node = initNode(val);
	// 變動
	node->next = list->head->next;
	// 變動
	list->head->next = node;
	list->len++;
} 
//尾部插入 
void insertToTail(List *list, int val){
	if(!list) return ;
	Node *node = initNode(val);
	//變動 刪除對連結串列是否為空的判斷  可以直接進行插入
	//此處可以謝偉 Node *p = list->head->next; 
	Node *p = list->head;
	while(p->next != NULL){
		p = p->next;
	}
	p->next = node;
	list->len++;
}
//任意位置的插入
void insert(List *list, int idx, int val){
	if(!list) return ;
	if(idx > list->len || idx < 0) return ;
	//變動 ： 刪除對連結串列是否為空的判斷 
	Node *node = initNode(val);
	Node *p = list->head;
	for(int i = 1;i <= idx;i++){
		p = p->next;
	} 
	//插入
	node->next = p->next;
	p->next = node;
	list->len++;
} 
//任意位置的刪除 
void remove(List *list, int idx){
	if(!list) return ;
	if(idx > list->len || idx < 0) return ;
	Node *p = list->head;
	for(int i = 1;i <= idx;i ++){
		p = p->next;
	}
	Node *node = p->next;
	//刪除 
	p->next = p->next->next;
	list->len--;
	freeNode(node);
}

到此這篇關於C語言超詳細講解線性表的文章就介紹到這了,更多相關C語言線性表內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！