鍊表(單鍊表)的基本操作及C語言實現

2021-01-15 楓楓知道

邏輯結構上一個接一個的數據,在實際存儲時,並沒有像順序表那樣也相互緊挨著。恰恰相反,數據隨機分布在內存中的各個位置,這種存儲結構稱為線性表的鏈式存儲。

由於分散存儲,為了能夠體現出數據元素之間的邏輯關係,每個數據元素在存儲的同時,要配備一個指針,用於指向它的直接後繼元素,即每一個數據元素都指向下一個數據元素(最後一個指向NULL(空))。

如圖所示,當每一個數據元素都和它下一個數據元素用指針連結在一起時,就形成了一個鏈,這個鏈子的頭就位於第一個數據元素,這樣的存儲方式就是鏈式存儲。

線性表的鏈式存儲結構生成的表,稱作「鍊表」。

鍊表中數據元素的構成

每個元素本身由兩部分組成:

本身的信息,稱為「數據域」;指向直接後繼的指針,稱為「指針域」。這兩部分信息組成數據元素的存儲結構,稱之為「結點」。n個節點通過指針域相互連結,組成一個鍊表。

由於每個節點中只包含一個指針域,生成的鍊表又被稱為 線性鍊表 或 單鍊表。

鍊表中存放的不是基本數據類型,需要用結構體實現自定義:

typedefstructLink{char elem;//代表數據域structLink* next;//代表指針域,指向直接後繼元素}link;線性表的鏈式存儲相比於順序存儲,有兩大優勢:

鏈式存儲的數據元素在物理結構沒有限制,當內存空間中沒有足夠大的連續的內存空間供順序表使用時,可能使用鍊表能解決問題。(鍊表每次申請的都是單個數據元素的存儲空間,可以利用上一些內存碎片)鍊表中節點之間採用指針進行連結,當對鍊表中的數據元素實行插入或者刪除操作時,只需要改變指針的指向,無需像順序表那樣移動插入或刪除位置的後續元素,簡單快捷。鍊表和順序表相比,不足之處在於,當作遍歷操作時,由於鍊表中節點的物理位置不相鄰,使得計算機查找起來相比較順序表,速度要慢。

#未來計劃#

相關焦點

  • C語言的一些高級議題
    指針是C語言的靈魂,我們經常聽到這樣的說法,當我們初學C語言的時候,似乎覺得也沒有什麼,但是當你越來越深入的了解它,你就會發現C語言的強大有時甚至超乎你的想像。C語言作為一種相對較為底層的語言,在某些方面有著不可替代的優勢。
  • 一篇文章搞懂 數據結構中的 線性表存儲方式(順序表 與 鍊表)
    線性表線性表是線性結構的基本表現。線性表有兩種存儲方式:順序表鍊表。下面分別來看這兩種存儲方式:順序表順序表 是 開闢連續的空間(如一維數組),順次把每一個元素存進來。鍊表鍊表就是 每一個數據存儲單元有兩部分 一是存數據的地方,另一個是存指針的地方。
  • 如何使用鍊表實現 LRU 算法
    編碼實現結構定義#include <stdio.h>#include <stdlib.h>#include <string.h>// 默認容量#define N 10// 表示這個鍊表的長度信息int len = 0;//當前鍊表的元素個數信息int count = 0;typedefstruct Node{ /*
  • 一文學會鍊表解題 - CSDN
    作者 | 碼海來源 | 碼海前言如果說數據結構是算法的基礎,那麼數組和鍊表就是數據結構的基礎。 因為像堆,棧,對,圖等比較複雜的數組結基本上都可以由數組和鍊表來表示,所以掌握數組和鍊表的基本操作十分重要。
  • 計算機二級考試C語言高頻考點
    (2)源程序的擴展名為.c,目標程序的擴展名為.obi,可執行程序的擴展名為.exe。,1,&基本語句1.賦值運算符和賦值表達式字符輸出函數 putchar()函數的作用是向終端輸出一個字符2.字符輸入函數 getchar()getchar()函數的作用是接收終端輸人一個
  • 自考「C語言程序設計」模擬試題九
    int  x;   char  y;   char  z[20];  A. scanf(「%d%c%c」,&x,&y,&z);     B. scanf(「%d%c%s」,&x,&y,&z);  C. scanf(「%d%c%c」,&x,&y,z);
  • C語言相關文件的基本知識
    用過計算機的人,對文件都不陌生,大多數人都接觸過,今天我們來講講關於C語言相關文件的基本知識。首先,我們先來了解了解什麼是文件。文件有不同的類型,在程序的設計中,主要有兩種文件; 1.程序文件;包括源程序文件(後綴為.c),目標文件(後綴為.obj),可執行文件(後綴為.exe)等,這類文件的內容是程序代碼。
  • 乾貨分享:計算機二級考試C語言基礎知識,送給考二級的同學!
    第一章 數據結構與算法1.1 算法1.算法的基本概念(1) 概念:算法是指一系列解決問題的清晰指令。(2) 4個基本特徵:可行性、確定性、有窮性、擁有足夠的情報。(3) 兩種基本要素:對數據對象的運算和操作、算法的控制結構(運算和操作時問的順序)。
  • 常考算法面試題系列:鍊表的操作
    鍊表鍊表存儲有序的元素集合,但不同於數組,鍊表中每個元素在內存中並不是連續放置的。
  • 回文鍊表 | Python
    回文鍊表題目來源:力扣(LeetCode)https://leetcode-cn.com/problems/palindrome-linked-list/ 題目 請判斷一個鍊表是否為回文鍊表。但是鍊表不能夠隨意訪問特定的數據,上面的方法也就無效。那麼,這裡可以使用列表,遍歷鍊表存儲元素的值,然後再使用上面的方法進行判斷。具體的代碼實現如下。# Definition for singly-linked list.
  • leetcode鍊表之回文鍊表
    序本文主要記錄一下leetcode鍊表之回文鍊表題目
  • 奇怪的C語言代碼,在變量前加上(void)是什麼操作?有什麼用?
    C語言的語法極其簡潔,即使是初次接觸程式語言的初學者也能很快學完它的語法。不過,C語言也是一門「靈活得過了頭」的程式語言,對於很多初學者來說,編寫C語言程序就好像拿著一堆最基本的磚塊,要修建一座大廈一樣,茫然找不到方向。
  • C語言怎麼樣?今天聊聊C語言的發展史!
    為什麼用基本這個詞呢?因為,在系統裡面有一部分命令是用B語言寫的。C語言和編譯器強大到,足以讓我們在當年夏天用C重寫PDP-11的Unix內核 (也就是Unix的V3版本)。 到了這個時間節點,基本可以肯定的是C語言、Unix的大部分核心都已經完善。剩下要做的就是,可移植性、標準化。
  • 原型鏈就是個鍊表,有啥好研究的,隔三差五來一下,走馬燈麼?
    正文掘金最近bug很多, 優弧很煩惱,mind想離職, 至於我的文章點讚和評論數莫名消失就不提了, 畢竟我是個佛系作者 讓我們回到本次吐槽的主題, 我想說的是, 如果你對JavaScript的原型系統有細節上的困惑或者愛好, 去看規範就好了, 那玩意你能看懂, 研究明白基本上已經是語言規範專家了
  • C語言程序設計試題及答案
    20個小題,每小題1分,共20分)1、C語言程序的基本單位是( )。A) int:a, b, c; B) int a; b; c;C) int a, b, c D) int a, b, c;20、C語言用( )表示邏輯「真」值。
  • 第六篇:C語言中結構體與文件操作相關知識點梳理
    前面總結過,C語言中的基本數據類型有四種,分別是整型、浮點型和字符型;後面又講到可以保存字符串的字符數組。但這遠遠不夠實際應用的需要。01問題引入問題一:基本數據類型無法滿足應用需要注意:這個學生信息是一個整體,用前面學到的基本數據類型是無法實現的。有沒有一種學生的數據類型可以使用?系統沒有定義,就只能自行設計了。這就是本文要總結的第一個核心知識點:結構體。在C語言中結構體是對數據類型的無限擴展。
  • 「C語言從入門到入土」必備C語言基礎筆記整理
    一、C語言1、什麼是C語言?C語言是人寫機器看的一種語言。C語言是高級語言中的低級語言。C語言貼近硬體。C語言的入門學習比較簡單。彙編語言——>B語言——>C語言2、C語言的特性首先C語言就是你的女朋友。無論你讓它幹什麼,它絕對不會自己找到方法。
  • 用C語言實現FFT算法
    } FFT(s,Num); for(i=1;i0x101;i++) { result[i]=sqrt(pow(s[i].real,2)+pow(s[i].imag,2)); }} c語言相關文章