網(wǎng)站首頁(yè) 編程語(yǔ)言 正文
1. 順序表
順序表是指用一段連續(xù)的地址，依次存放數(shù)據(jù)元素的線性數(shù)據(jù)結(jié)構(gòu)。此種存儲(chǔ)方式使得順序表的物理結(jié)構(gòu)與邏輯結(jié)構(gòu)都是連續(xù)的。
與數(shù)組的區(qū)別：函數(shù)中的數(shù)組被存放在棧段中，而棧段有系統(tǒng)限制的大小（可使用ulimit -s查看系統(tǒng)限制的大小，單位為KB），因此順序表往往使用在堆段中操作管理動(dòng)態(tài)數(shù)組的方式實(shí)現(xiàn)。
1.1 管理結(jié)點(diǎn)
在順序表中，管理節(jié)點(diǎn)內(nèi)部一般存放：數(shù)據(jù)域地址(*data)、**總?cè)萘?size)以及當(dāng)前數(shù)據(jù)量(len)**等等。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Vector {
//數(shù)據(jù)域
int *data;
//總?cè)萘?
int size;
//當(dāng)前元素個(gè)數(shù) 或 指向末尾元素的后一位
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 ;
//維護(hù)順序表的特性 將 idx 及之后的元素后移
for(int i = v->len; i > idx ;i++){
v->data[i] = v->data[i - 1];
}
//在 idx 處插入數(shù)據(jù)
v->data[i] = val;
//更新當(dāng)前元素個(gè)數(shù)
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 順序表的擴(kuò)容
擴(kuò)容：新創(chuàng)建 原size * 2 的空間，然后將原數(shù)據(jù)從原空間遷移到新空間
//倍增法擴(kuò)容 size -> size + exsize
int expand(Vector *v){
//擴(kuò)容為 size + exSize
int exSize = v->size;
int *tmp;
while(exSize){
//嘗試向內(nèi)存申請(qǐng)空間
tmp = (int *) realloc(v->data, sizeof(int) * (v->size + exSize));
//申請(qǐng)成功
if(tmp) break;
//申請(qǐng)不成功 exSize/2 繼續(xù)申請(qǐng)
exSize >>= 1;
}
//徹底失敗 未申請(qǐng)到空間
if(!tmp) return 0;
//擴(kuò)容成功
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) {
//嘗試擴(kuò)容 擴(kuò)容成功為 1 失敗為 0
if(!expand(v)) return;
}
...
} 2. 鏈表
2.1 定義
鏈表是一種物理結(jié)構(gòu)不連續(xù)，但可以依靠結(jié)點(diǎn)中的指針實(shí)現(xiàn)邏輯結(jié)構(gòu)連續(xù)的線性數(shù)據(jù)結(jié)構(gòu)。
構(gòu)成鏈表的數(shù)據(jù)元素被稱(chēng)為“結(jié)點(diǎn)”，節(jié)點(diǎn)內(nèi)部存放數(shù)據(jù)與指向下一個(gè)結(jié)點(diǎn)的指針。
//定義結(jié)點(diǎn)
typedef struct Node{
int val;
struct Node *next;
} Node;
//結(jié)點(diǎn)初始化
Node *initNode(int val){
Node *node = (Node *) malloc(sizeof(Node));
node->val = val;
node->next = NULL;
return node;
}
//釋放結(jié)點(diǎn)
void freeNode(Node *node){
if(!node) return ;
free(node);
}
只有單一結(jié)點(diǎn)指針的鏈表的全程是“單鏈表”，經(jīng)常被簡(jiǎn)稱(chēng)為鏈表。
鏈表的管理結(jié)點(diǎn)一般僅需要存放頭結(jié)點(diǎn)指針(*head)。
如果需要頻繁獲取鏈表長(zhǎng)度，管理結(jié)點(diǎn)中可以額外存放鏈表長(zhǎng)度(len)。
//定義鏈表 管理結(jié)點(diǎn)
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 頭部插入
頭插法：將新插入的節(jié)點(diǎn)放在 head 后，時(shí)間復(fù)雜度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 尾部插入
尾插法：找到最后一個(gè)結(jié)點(diǎn)，將新節(jié)點(diǎn)插入。如果沒(méi)有設(shè)計(jì)尾指針，則時(shí)間復(fù)雜度為O（n）。
//尾部插入
void insertToTail(List *list, int val){
if(!list) return ;
Node *node = initNode(val);
//如果list為空 則node為第一個(gè)結(jié)點(diǎn) 讓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++;
}
//測(cè)試
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;
}
輸出結(jié)果：
2.4 任意位置插入
//任意位置的插入
// idx = 0 待插入結(jié)點(diǎn)為頭結(jié)點(diǎn)
// idx > 0 插入至第 i 個(gè)結(jié)點(diǎn)后
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);
//結(jié)點(diǎn)索引為 0
Node *p = list->head;
//p 找到第 idx - 1個(gè)結(jié)點(diǎn)
// i = 1 結(jié)點(diǎn)索引為 1
// i = 2 結(jié)點(diǎn)索引為 2
// i = idx - 1 結(jié)點(diǎn)索引為 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號(hào)索引結(jié)點(diǎn)
Node *p = list->head;
//刪除索引為 0 的結(jié)點(diǎn) 更改head
if(idx == 0){
list->head = p->next;
list->len--;
freeNode(p);
return;
}
//找到idx-1個(gè)結(jié)點(diǎn)
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 虛頭結(jié)點(diǎn)
在需要特殊處理頭結(jié)點(diǎn)的時(shí)候，可以實(shí)現(xiàn)一個(gè)帶有虛頭結(jié)點(diǎn)的鏈表。在鏈表初始化或在某些操作執(zhí)行時(shí)，將一個(gè)額外的結(jié)點(diǎn)放在頭指針執(zhí)行的地方。虛頭結(jié)點(diǎn)可以使得整個(gè)鏈表永遠(yuǎn)不空，永遠(yuǎn)有頭。所以擁有虛頭結(jié)點(diǎn)的鏈表在處理各類(lèi)結(jié)點(diǎn)操作時(shí)會(huì)更加便捷。
任意位置插入：不需要特殊考慮插入位置是否在鏈表頭部。
任意位置刪除：不需要特殊考慮刪除的結(jié)點(diǎn)是否是鏈表的第一個(gè)結(jié)點(diǎn)。
//結(jié)點(diǎn)部分沒(méi)有改動(dòng)
//定義結(jié)點(diǎn)
typedef struct Node{
int val;
struct Node *next;
} Node;
//結(jié)點(diǎn)初始化
Node *initNode(int val){
Node *node = (Node *) malloc(sizeof(Node));
node->val = val;
node->next = NULL;
return node;
}
//釋放結(jié)點(diǎn)
void freeNode(Node *node){
if(!node) return ;
free(node);
}
//定義鏈表 管理結(jié)點(diǎn)
typedef struct List{
Node *head;
int len;
} List;
//初始化鏈表
List *initList() {
List *list = (List *) malloc(sizeof(List));
//變動(dòng) ：初始化的時(shí)候賦予一個(gè)結(jié)點(diǎn) 任意數(shù)值都可以
list->head = initNode(-1);
list->len = 0;
return list;
}
//頭部插入
void insertToHead(List *list, int val){
if(!list) return ;
Node *node = initNode(val);
// 變動(dòng)
node->next = list->head->next;
// 變動(dòng)
list->head->next = node;
list->len++;
}
//尾部插入
void insertToTail(List *list, int val){
if(!list) return ;
Node *node = initNode(val);
//變動(dòng) 刪除對(duì)鏈表是否為空的判斷 可以直接進(jìn)行插入
//此處可以謝偉 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 ;
//變動(dòng) ： 刪除對(duì)鏈表是否為空的判斷
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);
}
原文鏈接：https://blog.csdn.net/zkx990121/article/details/123900021
相關(guān)推薦
- 2023-03-28 Python中的len()函數(shù)是什么意思_python
- 2022-10-08 React中useState的使用方法及注意事項(xiàng)_React
- 2022-06-02 C#生成帶注釋的dll并引用實(shí)現(xiàn)_C#教程
- 2023-01-20 Go語(yǔ)言實(shí)現(xiàn)定時(shí)器的原理及使用詳解_Golang
- 2022-08-23 Selenium多窗口切換解決方案_python
- 2022-01-09 webpack-code split代碼分割
- 2022-05-28 C++?超詳細(xì)講解stack與queue的使用_C 語(yǔ)言
- 2022-05-08 聊聊docker?單機(jī)部署redis集群的問(wèn)題_docker
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過(guò)濾器
- Spring Security概述快速入門(mén)
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡(jiǎn)單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速