C語言創(chuàng)建和操作單鏈表數(shù)據(jù)結(jié)構(gòu)的實例教程
1，為什么要用到鏈表
數(shù)組作為存放同類數(shù)據(jù)的集合，給我們在程序設計時帶來很多的方便，增加了靈活性。但數(shù)組也同樣存在一些弊病。如數(shù)組的大小在定義時要事先規(guī)定，不能在程序中進行調(diào)整，這樣一來，在程序設計中針對不同問題有時需要3 0個大小的數(shù)組，有時需要5 0個數(shù)組的大小，難于統(tǒng)一。我們只能夠根據(jù)可能的最大需求來定義數(shù)組，常常會造成一定存儲空間的浪費。
我們希望構(gòu)造動態(tài)的數(shù)組，隨時可以調(diào)整數(shù)組的大小，以滿足不同問題的需要。鏈表就是我們需要的動態(tài)數(shù)組。它是在程序的執(zhí)行過程中根據(jù)需要有數(shù)據(jù)存儲就向系統(tǒng)要求申請存儲空間，決不構(gòu)成對存儲區(qū)的浪費。
鏈表是一種復雜的數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)之間的相互關(guān)系使鏈表分成三種：單鏈表、循環(huán)鏈表、雙向鏈表，下面將逐一介紹。
2，單向鏈表
單鏈表有一個頭節(jié)點head，指向鏈表在內(nèi)存的首地址。鏈表中的每一個節(jié)點的數(shù)據(jù)類型為結(jié)構(gòu)體類型，節(jié)點有兩個成員：整型成員（實際需要保存的數(shù)據(jù)）和指向下一個結(jié)構(gòu)體類型節(jié)點的指針即下一個節(jié)點的地址（事實上，此單鏈表是用于存放整型數(shù)據(jù)的動態(tài)數(shù)組）。鏈表按此結(jié)構(gòu)對各節(jié)點的訪問需從鏈表的頭找起，后續(xù)節(jié)點的地址由當前節(jié)點給出。無論在表中訪問那一個節(jié)點，都需要從鏈表的頭開始，順序向后查找。鏈表的尾節(jié)點由于無后續(xù)節(jié)點，其指針域為空，寫作為NULL。
如圖所示：
上圖還給出這樣一層含義，鏈表中的各節(jié)點在內(nèi)存的存儲地址不是連續(xù)的，其各節(jié)點的地址是在需要時向系統(tǒng)申請分配的，系統(tǒng)根據(jù)內(nèi)存的當前情況，既可以連續(xù)分配地址，也可以跳躍式分配地址。
3，單向鏈表程序的實現(xiàn)
（1），鏈表節(jié)點的數(shù)據(jù)結(jié)構(gòu)定義
struct node
{
int num;
struct node *p;
} ;
在鏈表節(jié)點的定義中，除一個整型的成員外，成員p是指向與節(jié)點類型完全相同的指針。
在鏈表節(jié)點的數(shù)據(jù)結(jié)構(gòu)中，非常特殊的一點就是結(jié)構(gòu)體內(nèi)的指針域的數(shù)據(jù)類型使用了未定義成功的數(shù)據(jù)類型。這是在C中唯一規(guī)定可以先使用后定義的數(shù)據(jù)結(jié)構(gòu)。
（2），鏈表的創(chuàng)建、輸出步驟
單鏈表的創(chuàng)建過程有以下幾步：
1 ) 定義鏈表的數(shù)據(jù)結(jié)構(gòu);
2 ) 創(chuàng)建一個空表;
3 ) 利用malloc ( )函數(shù)向系統(tǒng)申請分配一個節(jié)點;
4 ) 將新節(jié)點的指針成員賦值為空。若是空表，將新節(jié)點連接到表頭；若是非空表，將新
節(jié)點接到表尾;
5 ) 判斷一下是否有后續(xù)節(jié)點要接入鏈表，若有轉(zhuǎn)到3 )，否則結(jié)束;
單鏈表的輸出過程有以下幾步
1) 找到表頭;
2) 若是非空表，輸出節(jié)點的值成員，是空表則退出;
3 ) 跟蹤鏈表的增長，即找到下一個節(jié)點的地址;
4) 轉(zhuǎn)到2 ).
（3），程序代碼例子：
創(chuàng)建一個存放正整數(shù)單鏈表，輸入0或小于0的數(shù)，結(jié)束創(chuàng)建鏈表，并打印出鏈表中的值，程序如下：
#include <stdlib.h> /*含ma l l o c ( ) 的頭文件*/
#include <stdio.h>
//①定義鏈表數(shù)據(jù)結(jié)構(gòu)
struct node
{
int num;
struct node *next;
};
//函數(shù)聲明
struct node *creat();
void print();
main( )
{
struct node *head;
head=NULL; //②建一個空表
head=creat(head);/*創(chuàng)建單鏈表*/
print(head);/*打印單鏈表*/
}
/******************************************/
struct node*creat(struct node *head)/*返回的是與節(jié)點相同類型的指針*/
{
struct node*p1,*p2;
int i=1;
//③利用malloc ( )函數(shù)向系統(tǒng)申請分配一個節(jié)點
p1=p2=(struct node*)malloc(sizeof(struct node));/*新節(jié)點*/
printf("請輸入值，值小于等于0結(jié)束，值存放地址為：p1_ADDR= %d\n",p1);
scanf("%d",&p1->num);/*輸入節(jié)點的值*/
p1->next=NULL;/*將新節(jié)點的指針置為空*/
while(p1->num>0)/*輸入節(jié)點的數(shù)值大于0*/
{
//④將新節(jié)點的指針成員賦值為空。若是空表，將新節(jié)點連接到表頭；若是非空表，將新節(jié)點接到表尾;
if(head==NULL)
head=p1;/*空表，接入表頭*/
else
p2->next=p1;/*非空表，接到表尾*/
p2=p1;
p1=(struct node*)malloc(sizeof(struct node));/*下一個新節(jié)點*/
i=i+1;
printf("請輸入值，值小于等于0結(jié)束，值存放地址為：p%d_ADDR= %d\n",i,p2);
scanf("%d",&p1->num);/*輸入節(jié)點的值*/
//⑤判斷一下是否有后續(xù)節(jié)點要接入鏈表，若有轉(zhuǎn)到3 )，否則結(jié)束;
}
//==============原來程序更正部分：（多謝@daling_datou提醒）================================
free(p1); //申請到的沒錄入，所以釋放掉
p1=NULL; //使指向空
p2->next = NULL; //到表尾了，指向空
printf("鏈表輸入結(jié)束（END）\n");
//==============================================
return head;/*返回鏈表的頭指針*/
}
/*******************************************/
void print(struct node*head)/*出以head為頭的鏈表各節(jié)點的值*/
{
struct node *temp;
temp=head;/*取得鏈表的頭指針*/
printf("\n\n\n鏈表存入的值為：\n");
while(temp!=NULL)/*只要是非空表*/
{
printf("%6d\n",temp->num);/*輸出鏈表節(jié)點的值*/
temp=temp->next;/*跟蹤鏈表增長*/
}
printf("鏈表打印結(jié)束!!");
}
在鏈表的創(chuàng)建過程中，鏈表的頭指針是非常重要的參數(shù)。因為對鏈表的輸出和查找都要從鏈表的頭開始，所以鏈表創(chuàng)建成功后，要返回一個鏈表頭節(jié)點的地址，即頭指針。
程序執(zhí)行流程：
4，單鏈表操作基礎示例
#include <stdio.h>
#include <malloc.h>
#define LEN sizeof(NODE)
typedef struct _NODE//節(jié)點聲明
{
int val;
struct _NODE* next;
} NODE, *PNODE;
void print(PNODE head){//打印所有節(jié)點
while (head)
{
printf("%3d",head->val);
head = head->next;
}
printf("\n");
}
void insertHead(PNODE *pHead, int val){//頭插法
PNODE n = (PNODE)malloc(LEN);
n->val = val;
n->next = *pHead;
*pHead = n;
}
void insertTail(PNODE *pHead, int val){//尾插法
PNODE t = *pHead;
PNODE n = (PNODE)malloc(LEN);
n->val = val;
n->next = NULL;
if (*pHead == NULL)
{
n->next = *pHead;
*pHead = n;
}else{
while (t->next)
{
t = t->next;
}
t->next = n;
}
}
void deleteHead(PNODE *pHead){//刪除頭
if (*pHead == NULL)
{
return;
}
else
{
PNODE t = *pHead;
*pHead = (*pHead)->next;
free(t);
}
}
void deleteTail(PNODE *pHead){//刪除尾
PNODE t = *pHead;
if (t == NULL)
{
return;
}
else if (t->next == NULL)
{
free(t);
*pHead = NULL;
}
else{
while (t->next->next != NULL)
{
t = t->next;
}
free(t->next);
t->next = NULL;
}
}
PNODE findByVal(PNODE head, int val){//根據(jù)值找到滿足條件的第一個節(jié)點
while (head != NULL && head->val != val)
{
head = head->next;
}
return head;
}
PNODE findByIndex(PNODE head, int index){//根據(jù)索引找節(jié)點
if (index == 1)
{
return head;
}
else
{
int c = 1;
while (head != NULL && index != c)
{
head = head->next;
c++;
}
}
return head;
}
void insertByIndex(PNODE *pHead, int index, int val){//根據(jù)索引插入節(jié)點
if (index == 1)
{
insertHead(pHead, val);
}
else
{
PNODE t = findByIndex(*pHead,index - 1);
if (t == NULL)
{
return;
}
else
{
PNODE n = t->next;
t->next = (PNODE)malloc(LEN);
t->next->next = n;
t->next->val = val;
}
}
}
void deleteByIndex(PNODE *pHead, int index)//根據(jù)結(jié)點索引刪除結(jié)點
{
if (index == 1)
{
deleteHead(pHead);
}
else
{
PNODE t= findByIndex(*pHead, index - 1);
if (t == NULL || t->next == NULL)
{
return;
}else{
PNODE n = t->next->next;
free(t->next);
t->next = n;
}
}
}
void deleteByVal(PNODE *pHead, int val)//根據(jù)值刪掉第一個滿足條件的
{
if (*pHead == NULL)//如果空表退出
{
return;
}
else
{
if ((*pHead)->val == val)//如果第一個就是，刪頭
{
deleteHead(pHead);
}
else
{
PNODE t = *pHead;
while (t->next != NULL && t->next->val != val)//遍歷，若t的next為空或者next是要找的節(jié)點則退出
{
t = t->next;
}
if (t->next)//如果t指向要找的結(jié)點的上一個節(jié)點
{
PNODE n = t->next->next;//刪除要找的結(jié)點
free(t->next);
t->next = n;
}
}
}
}
void clear(PNODE *pHead)//清除鏈表
{
while ((*pHead) != NULL)
{
deleteHead(pHead);//從頭刪除
}
}
void main()
{
PNODE head = NULL;
insertTail(&head,1);
deleteHead(&head);
insertTail(&head,2);
insertTail(&head,3);
insertTail(&head,4);
insertTail(&head,5);
insertTail(&head,6);
print(head);
insertByIndex(&head, 6, 9);
print(head);
//deleteByIndex(&head,3);
deleteByVal(&head, 2);
print(head);
clear(&head);
print(head);
insertByIndex(&head,1,12);
print(head);
}
相關(guān)文章
顧名思義可以把自己的數(shù)據(jù)發(fā)送給在特定范圍內(nèi)的所有人；我們網(wǎng)絡編程中的廣播一般是通過特定的廣播地址把自己的數(shù)據(jù)發(fā)送給局域網(wǎng)內(nèi)當前在線的客戶端2022-05-05
想突破C語言的學習，對指針的掌握是非常重要的，本文為大家總結(jié)了C語言中指針的相關(guān)知識點，文中的示例代碼講解詳細，感興趣的可以學習一下2022-07-07
這篇文章主要介紹了C++編程指向成員的指針以及this指針的基本使用指南,與C語言一樣,存儲的數(shù)值被解釋成為內(nèi)存里的一個地址,需要的朋友可以參考下。2016-07-07
以下是對C語言中的位域和位段進行了詳細的分析介紹，需要的朋友可以過來參考下2013-08-08
在最流行的博彩游戲中有一種名為“擲雙骰”(craps)的骰子游戲，這種游戲在世界各地的娛樂場所和大街小巷非常受歡迎。本文將用C++語言實現(xiàn)這一游戲，需要的可以參考一下2022-03-03
這篇文章主要介紹了C/C++中比較字符串的方法，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
淺談返回函數(shù)內(nèi)部new分配的內(nèi)存的引用
下面小編就為大家?guī)硪黄獪\談返回函數(shù)內(nèi)部new分配的內(nèi)存的引用。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
在Qt應用程序開發(fā)中,良好的日志系統(tǒng)至關(guān)重要,本文將介紹如何使用spdlog 1.5.0創(chuàng)建滿足以下要求的日志系統(tǒng),感興趣的朋友一起看看吧2025-04-04
C語言實現(xiàn)YUV文件轉(zhuǎn)JPEG格式
這篇文章主要為大家詳細介紹了如何利用C語言實現(xiàn)將YUV文件轉(zhuǎn)為JPEG格式,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2023-12-12
這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)拼圖板小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-05-05