網站首頁 編程語言 正文
導語
無論是順序存儲結構還是鏈式存儲結構，在內存中進行存放元素的時候，不僅需要存放該元素的相關信息，還需要存放該元素和其他元素之間的關系，而我們之前所學的順序表“與生俱來”的物理結構自然地能夠表達出元素和元素之間的關系，不需要額外的信息去表達元素和元素之間的關系，而對于鏈式存儲這種非順序存儲的結構，需要額外附加指針去表示這種關系。
單鏈表
每個結點除了存放數據元素外，還要存儲指向下一個節點的指針。
單鏈表的特點
優點：不要求大片連續空間，改變容量方便
缺點：不可隨機存取，要耗費一定空間存放指針
定義
typedef struct LNode {
int data;
struct LNode* next;//指針指向下一個節點，指針的類型為節點類型；
}*LinkNode;//聲明*LinkNode為結構體指針類型
除了上述這種方法外，我們還可以先先聲明LinkNode為結構體類型，在使用該類型的時候，將對應的變量定義為指針即可。
單鏈表分為帶頭結點和不帶頭結點，我們一般主要學習帶頭結點的。
初始化操作
在所有的操作之前，我們首先需要建立一個空的單鏈表，那么首先需要做的就是分配頭結點。
void InistLinkNode(LinkNode& L) {
L = (LNode*)malloc(sizeof(LNode));//分配頭結點
L->next = NULL;
}
頭插法
“頭插法”顧名思義就是將元素插入到頭結點之后，插入一次好像和我們通常所講的插入沒什么區別，但多次這樣插到頭結點之后，也就是“第一個真正的節點”，那么是不是會產生一種現象，它最終的存儲數據和我們所插入時的順序是相反的。
void InsertLinkNode(LinkNode& L) {
LNode* s;
int x,Length;
printf("請輸入你要插入的元素個數：");
scanf("%d", &Length);
printf("請輸入你要插入的元素：\n");
for (int j = 0; j < Length; j++) {
s = (LNode*)malloc(sizeof(LNode));//每插入一個元素之前，都需要給它分配節點空間
scanf("%d", &x);
s->data = x;
s->next = L->next;
L->next = s;
}
}
通過程序驗證以下：
尾插法
“尾插法”顧名思義就是將元素插入到表尾，也就是我們普通的插入，那么怎么要找到表尾的位置呢？在順序表中，我們完全可以利用它順序存儲結構的天然特性，通過下標即可以找到，但是單鏈表是沒有辦法的，我們只有兩種方式，要么循環遍歷，要么嘗試在表尾的地方做個標記。
那么那種方法是好的呢？
答案是第二種！循環遍歷的方式，如果只插入一個元素看似沒什么問題，但如果多次的重復遍歷循環無疑增加了時間復雜度，這顯然不是好的方法。
第二個方法就不存在時間復雜度的問題，只需要在表尾位置做個標記，使它永遠指向表尾即可。
void TailInsertLinkNode(LinkNode& L) {
LNode* s,*r;
int x,Length;
r = L;//r為表尾指針
printf("請輸入你要插入的元素個數：");
scanf("%d", &Length);
printf("請輸入你要插入的元素：\n");
for (int j = 0; j < Length; j++) {
s = (LNode*)malloc(sizeof(LNode));
scanf("%d", &x);
s->data = x;
r->next = s;
r = s;//s為當前的表尾指針，將他的值賦值給r----使r永遠指向表尾
}
printf("\n");
r->next = NULL;
}
刪除第i個元素
既然要刪除某個元素，那么首先我們需要保證這個元素是非NULL，其次，我們還需要保證它前面的那個節點也是非NULL，為什么呢？因為如果將該元素從鏈表中刪除后，只有前面節點非NULL的情況下，才可以實現后續元素和前面子表的連接。
void DeleteLinkNode(LinkNode& L) {
int x, j = 0,e;
printf("請輸入你要刪除的元素位序：\n");
scanf("%d", &x);
LNode*p = L;
while (p != NULL && j < x - 1) {//尋找要刪除元素前的元素
p = p->next;
j++;
}
if (p == NULL)
{
printf("不存在我們要刪除的元素！");
}
if (p->next == NULL)//判斷該要刪除的節點是否為NULL
{
printf("不存在我們要刪除的元素！");
}
LNode* q = p->next;//q為我們要刪除的節點
e = q->data;
p->next = q->next;
free(q);//需要及時的將刪除了的元素空間進行釋放
}
其他的基本操作都是很常規化的，這里就不單獨的進行解釋了，需要注意的點，我會在文章結尾部分的完整代碼的注釋中展出。
在第i個位置插入
void IncreaseLinkNode(LinkNode& L) {
printf("請輸入你要插入的元素和位序：（元素和位序之間用逗號隔開）\n");
int x, j = 0, e;
scanf("%d,%d",&e, &x);
LNode* s = L, * r= (LNode*)malloc(sizeof(LNode));
while (j < x-1 && s != NULL) {
j++;
s = s->next;
}
r->data = e;
r->next = s->next;
s->next = r;
}
如下所示的代碼順序不能發生改變，否則會出現無法和后面的節點；
r->next = s->next;
s->next = r;
完整代碼如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
int data;
struct LNode* next;
}*LinkNode;
//初始化
void InistLinkNode(LinkNode& L) {
L = (LNode*)malloc(sizeof(LNode));//分配頭結點
L->next = NULL;
}
//頭插法
void InsertLinkNode(LinkNode& L) {
LNode* s;
int x,Length;
printf("請輸入你要插入的元素個數：");
scanf("%d", &Length);
printf("請輸入你要插入的元素：\n");
for (int j = 0; j < Length; j++) {
s = (LNode*)malloc(sizeof(LNode));
scanf("%d", &x);
s->data = x;
s->next = L->next;
L->next = s;
}
}
//尾插法
void TailInsertLinkNode(LinkNode& L) {
LNode* s,*r;
int x,Length;
r = L;
printf("請輸入你要插入的元素個數：");
scanf("%d", &Length);
printf("請輸入你要插入的元素：\n");
for (int j = 0; j < Length; j++) {
s = (LNode*)malloc(sizeof(LNode));
scanf("%d", &x);
s->data = x;
r->next = s;
r = s;
}
printf("\n");
r->next = NULL;
}
//輸出單鏈表
void PrintLinkNode(LinkNode& L)
{
LNode* s=L->next;
printf("單鏈表元素如下：\n");
while (s != NULL) {
printf("%d", s->data);
s =s->next;
}
printf("\n");
}
//求線性表長度
void lengthLinkNode(LinkNode& L)
{
LNode* s = L->next;
int n=0;
while (s != NULL) {
n++;
s = s->next;
}
printf("單鏈表長度為：%d",n);
printf("\n");
}
//取第i個元素
void GetElemLinkNode(LinkNode& L) {
printf("請輸入你要查找的元素位序：\n");
int i, j = 0;
LNode* s=L;
scanf("%d", &i);
while (j < i && s != NULL) {
j++;
s = s->next;
}
if (s == NULL) {
printf("不存在我們要查找的元素！");
}
else {
printf("元素位序為%d的元素是%d",i, s->data);
}
printf("\n");
}
//刪除第i個元素
void DeleteLinkNode(LinkNode& L) {
int x, j = 0,e;
printf("請輸入你要刪除的元素位序：\n");
scanf("%d", &x);
LNode*p = L;
while (p != NULL && j < x - 1) {
p = p->next;
j++;
}
if (p == NULL)
{
printf("不存在我們要刪除的元素！");
}
if (p->next == NULL)
{
printf("不存在我們要刪除的元素！");
}
LNode* q = p->next;
e = q->data;
p->next = q->next;
free(q);
}
//在第i個位置插入
void IncreaseLinkNode(LinkNode& L) {
printf("請輸入你要插入的元素和位序：（元素和位序之間用逗號隔開）\n");
int x, j = 0, e;
scanf("%d,%d",&e, &x);
LNode* s = L, * r= (LNode*)malloc(sizeof(LNode));
while (j < x-1 && s != NULL) {
j++;
s = s->next;
}
r->data = e;
r->next = s->next;
s->next = r;
}
//查找位序
void SearchLinkNode(LinkNode &L) {
int x,j=1;
LNode* p=L->next;
printf("請輸入你要查找的元素:\n");
scanf("%d", &x);
while (p != NULL && p->data != x) {
p = p->next;
j++;
}
if (p == NULL) {
printf("您要查找的元素不存在！");
}
else {
printf("你要查找的元素%d的位序為%d", x, j);
}
}
int main() {
LinkNode L;
InistLinkNode(L);
/*InsertLinkNode(L);*/
TailInsertLinkNode(L);
PrintLinkNode(L);
lengthLinkNode(L);
GetElemLinkNode(L);
IncreaseLinkNode(L);
PrintLinkNode(L);
DeleteLinkNode(L);
PrintLinkNode( L);
SearchLinkNode(L);
}
輸出：
原文鏈接：https://blog.csdn.net/m0_64365419/article/details/127464995
相關推薦
- 2022-05-20 flume的負載均衡load balancer
- 2022-01-27 SpringBoot成功啟動后自動關閉
- 2022-06-19 解決MybatisPlus?SqlServer?OFFSET?分頁問題_MsSql
- 2022-08-13 圖像處理之matlab中meshgrid函數用法詳解
- 2022-06-12 C語言函數指針數組實現計算器功能_C 語言
- 2022-11-04 react-router-dom?v6?使用詳細示例_React
- 2022-10-26 jQuery中DOM?屬性使用實例詳解下篇_jquery
- 2022-04-05 easyswoole轉發報錯 writev() failed (104 nginx
- 最近更新
-
- 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加速