網站首頁 編程語言 正文
基本概念
線性表是由 n(n≥0)個數據元素組成的有窮序列
大白話：在內存上一個個排著，找到一個，剩下的挨著找就行
數據元素又稱作結點
吐槽：人類在創造術語的路上就是這么帶勁，上節課剛說數據元素又稱元素，這又來一個結點，得，記住吧
結點個數叫做表長，那么我們用一張完整的圖來說明一下
線性表的基本運算，需要了解一下
- 初始化 Initiate(L)
- 求表長 Length(L)
- 讀表元素 Get(L,i)
- 定位 Locate(L,i)
- 插入 Insert(L,x,i)
- 刪除 Delete(L,i)
線性表的順序存儲
用順序存儲實現的線性表稱為順序表。一般使用數組來表示順序表
接下就是刺激的時刻了，比較難的部分來了，因為要用 C 來實現線性表的基本運算
首先假定線性表的數據元素的類型為DataType ，這個DataType 可以是自定義的，也可以是默認的int,char等類型
const int Maxsize = 100 ; // 預先定義一個足夠大的常數
typedef struct{
DataType data[Maxsize]; // 存放數據的數組
int length ; // 順序表的實際長度
} SeqList; // 順序表類型名為SeqList
SeqList L ; // 定義一個L為順序表
實現插入操作，函數名字為InsertSeqList(SeqList L,DataType x,int i) 表示在順序表第 i（1≤i≤n+1）個元素之前，插入一個新元素。使得線性表長度加 1。
上面是邏輯上的 C 語言實現，接下來咱們先引用一個圖，說明一下如何用 C 語言在內存上開辟一塊空間，并且向里面存數據
#include <stdio.h>
#include <stdlib.h>
const int Maxsize = 10;
typedef struct SeqList{
int *data; //一個int指針，后面用來初始化數組用
int length;
} seq;
// 順序表的初始化函數
seq init(){
seq s;
s.data = (int*)malloc(Maxsize*sizeof(int)); // 構造一個空的順序表，動態申請存儲空間
if(!s.data) // 如果申請失敗，退出程序
{
printf("初始化失敗");
exit(0);
}
s.length = 0; // 空表的長度初始化為0
return s;
}
上述代碼，相當于在內存上做了圖示的操作
開辟空間之后，向每個小格子里面添加數字
void display(seq s){
for(int i=0;i<s.length;i++){
printf("%d",s.data[i]);
}
printf("\n");
}
int main()
{
seq s = init();
//添加一個元素進入
for(int i=1;i<=5;i++){
s.data[i-1] = i;
s.length++;
}
printf("初始化之后，表的數據為:\n");
display(s);
return 0;
}可以看動畫理解
添加元素完成之后，就是刪除元素了
刪除的基本步驟
- 結點 ai+1,....an依次向左移動一個元素位置
- 表長度減 1
看一下代碼吧
seq delete_seq(seq s,int i){
if(i<1||i>s.length){
printf("位置錯誤");
exit(0);
}
// 第i個元素下標修改為i-1
for(int j=i;j<s.length;j++){
s.data[j-1] = s.data[j];
}
s.length--;
return s;
}
接下來實現定位的算法，說白了，就是判斷一個值（x）的位置（i）
C 語言的代碼如下
// 注意，這個地方需要返回的為int了，也就是位置
int locate(seq s,int x){
int i =0;
while((i<s.length)&&(s.data[i]!=x)){
i++;
}
if(i<s.length) return i+1;
else return -1;
}線性表的順序存儲的時間復雜度
| 運算 | 插入 | 刪除 | 定位 | 求表長 | 讀取元素 |
|---|---|---|---|---|---|
| 時間復雜度 | O(n) | O(n) | O(n) | O(1) | O(1) |
具體是怎么來的，需要你自己看看算法的實現嘍，通過上述表格知道 順序表的插入、刪除算法在時間性能方面不是很理想，接下來我們就采用線性表的鏈接存儲來看一下，是否存在優化。
線性表的鏈接存儲
鏈式存儲結構，上來需要記住有三種常見的 單鏈表、循環鏈表、雙向循環鏈表
首先明確，單鏈表中每個結點由兩部分組成
- data 表示==數據域==
- next 表示==指針域==或==鏈域==
一些簡單的結點概念
線性表在單鏈表上實現基本運算
接下來重頭戲來了，我們要用代碼實現一個簡單的單鏈表
空的單鏈表由一個頭指針和一個頭結點組成
初始化
初始化之前，我們需要先用 C 語言定義一個新的結構體
//鏈表中的每個結點的實現
//包含數據域與指針域
typedef struct node{
int data;// 數據域，為了計算方便，類型設置為數字
struct node *next; // 指針域，指向后繼元素
} Node,*LinkList;
結構體定義好了之后，就可以開始初始化操作了 頭結點初始化其實就是在內存上開辟一塊空間，然后將指針域指向 NULL
請看代碼，注意返回的是一個指針類型，說白了就是頭結點的地址
// 初始化
LinkList init(){
Node *L; // 定義一個頭結點
L =(LinkList)malloc(sizeof(Node)); //頭結點申請地址
if(L == NULL){
printf("初始化失敗!\n");
exit(0);
}
L->next =NULL;
return L;
}
復制代碼初始化成功，開始插入元素
插入元素，有頭插入、尾插、任意插
先說一下頭插，當頭結點初始化完畢之后，第一個元素插入進來就比較簡單了，看動圖
這是插入一個元素，在用頭插法插入第二個元素呢？
新生成的 pnew2 首先將自己的指針域指向頭結點的指針域pnew2->next = L.next，然后L.next = pnew2 即可
上述的邏輯寫成代碼如下
// 頭插入法
void insert_head(Node *L){
int i,n,num; // n表示元素的個數
Node *pnew;
printf("請輸入要插入的元素個數：n = ");
scanf("%d",&n);
for(i=0;i<n;i++){
printf("請輸入第%d個元素： ",i+1);
scanf("%d",&num);
pnew = (LinkList)malloc(sizeof(Node));
pnew->data = num; // 將數字存儲到數據域
pnew->next = L->next; // 指針域指向L（頭結點）的指針域
L->next = pnew; // 頭結點指針域指向新結點地址
}
}
接下來看一下尾插法，其實理解起來也不難，說白了就是在鏈表后面追加元素即可 !
代碼如下，這個地方看一下里面有一個p=L請問直接使用 L 可以嗎？為什么不直接用，搞清楚了，你也就明白了
// 尾插法
void insert_tail(Node *L){
int i,n,num;
Node *p,*pnew;
p = L;
printf("要輸入元素的個數：n = ");
scanf("%d",&n);
for(i=0;i<n;i++){
printf("請輸入第%d個元素：",i+1);
scanf("%d",&num);
pnew = (LinkList)malloc(sizeof(Node));
if(pnew == NULL){
printf("初始化失敗");
exit(0);
}
pnew->data = num;
p->next = pnew;
p = pnew;
}
p->next = NULL;
}剩下的算法實現就比較簡單了，例如求表長，通過循環的方式，計算一下即可
//求表長
int get_length(LinkList L){
LinkList p;
int length = 0;
p = L->next; // p 指向第一個結點
while(p){
printf("單鏈表的數據為%d\n",p->data);
length++;
p = p->next;
}
return length;
}讀表中的元素
// 讀表中的元素
LinkList get_element(LinkList L,int i){
// 在單鏈表L中查找第i個結點，若找到，則返回指向該結點的指針，否則返回NULL
Node *p;
p = L->next;
int position = 1;
while((position<i)&&(p!=NULL)){ // 當未到第i結點且未到尾結點時繼續后移
p = p->next;
position++;
}
if(i==position) return p; //找到第i個結點
else return NULL; // 查找失敗
}讀取表的元素，還可以按照值去找，返回位置，嘗試一下吧，寫起來都是比較容易的
int get_element_by_data(LinkList L,int x){
Node *p;
p = L->next;
int i = 0;
while(p!=NULL && p->data == x){
p = p->next;
i++;
}
if (p!=NULL) return i+1;
else return 0;
}寫個復雜點的，在任意位置插入一個元素，這個還是好玩一些的
/在任意位置插入元素，x為要插入的內容，i為插入的位置
void insert(LinkList L,int x,int i){
Node *p,*q; //p表示要插入的元素，q表示要被插入的元素
if(i==1) q = L; //如果i==1,那么p=L進行初始化操作
else q = get_element(L,i-1); // 找到第i-1個元素
if(q==NULL){
printf("找不到位置");
exit(0);
}
else{
p =(LinkList)malloc(sizeof(Node));
p->data = x;
p->next = q->next; // 新生成的p指向q的下一個結點
q->next = p;//q的指針域指向新生成的p
}
}
簡單說明一下吧 大白話為 要在第 i 個位置插入一個元素 x,那么需要找到i-1位置的元素，這個元素叫做 q
讓新元素p（數據域為 x，指針域為空）的指針域指向第i 元素，也就是q原先的指針域，==防止丟失掉==
然后在叫q的指針域指向p的地址即可，如果還不明白，看圖
對于刪除任意位置的節點，這個就要留給你自己了
如果將 ai移除鏈表，需要找到直接前驅，讓直接前驅的指針域指向 ai+1的地址就可以了
記得，通過free(p)釋放結點
刪除全部結點也需要自己完成一下，盡量把代碼寫完哦~~~
單鏈表的時間復雜度
- insert(LinkList L,int x,int i) 時間復雜度為 O(n^2^)
- 頭插法和尾插法時間復雜度為 O(n)
循環鏈表
環狀鏈表只需要將表中最后一個結點的指針指向頭結點，鏈表就形成了一個環 如圖
循環鏈表如何想研究一下可以去實現約瑟夫環，由于本教材中不是重點，所以選修即可
雙向循環鏈表
雙向循環鏈表就是在單鏈表中的每個結點在增加一個指向直接前驅的指針域prior ，這樣每個結點就有兩個指針了
注意點
- 雙向循環鏈表是一種對稱結構，即可以直接訪問前驅結點又可以直接訪問后繼結點，所以找前驅和后繼結點的時間復雜度都是 O(1)，也可以得到結論雙向循環鏈表適合應用在需要經常查找結點的前驅和后繼場合
- p = p->prior->next = p->next->prior
教材中重點給出了刪除和插入的兩個邏輯，我們看一下
// p表示的是待刪除的結點 p->prior->next = p->next; p->next->prior = p->prior; free(p)
圖示如下
大白話 先讓 p 等于要刪除的結點，然后把 p 刪除前，需要將 p 的前驅和后繼結點連接起來，剛才的代碼干的就是這個事情！
插入邏輯
在 p 所指的結點后面插入一個新結點*t，需要修改四個指針：
t->prior = p; p->next = t; // 這兩個步驟將t和p連接起來了 t->next = p->next; p->next->prior = t; //這兩個步驟將t和p后繼結點連接起來了
期末考試
這章是期末考試或者自考的一個比較重要的考試章節，一般會出現算法設計題，難度系數挺高的
建議，在能力范圍內用 C 語言實現順序表的基本運算，實現單鏈表的基本運算
原文鏈接：https://juejin.cn/post/7147883328786399239
相關推薦
- 2022-07-12 合理使用gateWay過濾器，實現Concroller自動注入用戶信息
- 2022-09-01 基于MFC實現單個文檔的文件讀寫_C 語言
- 2022-01-17 類組件與函數組件的區別 react中class創建的組件與function創建的組件有什么區別
- 2023-03-27 詳解C++11中的類型推斷_C 語言
- 2022-08-14 hyper-v如何配置NAT網絡的實現_Hyper-V
- 2022-06-02 Apache?Hudi基于華米科技應用湖倉一體化改造_服務器其它
- 2022-04-18 python?dataframe實現統計行列中零值的個數_python
- 2022-07-30 基于docker安裝zabbix的詳細教程_zabbix
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速