C說話創立和操作單鏈表數據構造的實例教程。本站提示廣大學習愛好者：（C說話創立和操作單鏈表數據構造的實例教程）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話創立和操作單鏈表數據構造的實例教程正文
1，為何要用到鏈表
數組作為寄存同類數據的聚集，給我們在法式設計時帶來許多的便利，增長了靈巧性。但數組也異樣存在一些弊端。如數組的年夜小在界說時要事前劃定，不克不及在法式中停止調劑，如許一來，在法式設計中針對分歧成績有時須要3 0個年夜小的數組，有時須要5 0個數組的年夜小，難於同一。我們只可以或許依據能夠的最年夜需求來界說數組，經常會形成必定存儲空間的糟蹋。
我們願望結構靜態的數組，隨時可以調劑數組的年夜小，以知足分歧成績的須要。鏈表就是我們須要的靜態數組。它是在法式的履行進程中依據須要稀有據存儲就向體系請求請求存儲空間，決不組成對存儲區的糟蹋。
鏈表是一種龐雜的數據構造，其數據之間的互相關系使鏈表分紅三種：單鏈表、輪回鏈表、雙向鏈表，上面將一一引見。
2，單向鏈表
單鏈表有一個頭節點head，指向鏈表在內存的首地址。鏈表中的每個節點的數據類型為構造體類型，節點有兩個成員：整型成員（現實須要保留的數據）和指向下一個構造體類型節點的指針即下一個節點的地址（現實上，此單鏈表是用於寄存整型數據的靜態數組）。鏈表按此構造對各節點的拜訪需從鏈表的頭找起，後續節點的地址由以後節點給出。不管在表中拜訪那一個節點，都須要從鏈表的頭開端，次序向後查找。鏈表的尾節點因為無後續節點，其指針域為空，寫作為NULL。
如圖所示：
上圖還給出如許一層寄義，鏈表中的各節點在內存的存儲地址不是持續的，其各節點的地址是在須要時向體系請求分派的，體系依據內存確當前情形，既可以持續分派地址，也能夠騰躍式分派地址。
3，單向鏈表法式的完成
（1），鏈表節點的數據構造界說
struct node
{
int num;
struct node *p;
} ;
在鏈表節點的界說中，除一個整型的成員外，成員p是指向與節點類型完整雷同的指針。
在鏈表節點的數據構造中，異常特別的一點就是構造體內的指針域的數據類型應用了不決義勝利的數據類型。這是在C中獨一劃定可以先應用後界說的數據構造。
（2），鏈表的創立、輸入步調
單鏈表的創立進程有以下幾步：
1 ) 界說鏈表的數據構造;
2 ) 創立一個空表;
3 ) 應用malloc ( )函數向體系請求分派一個節點;
4 ) 將新節點的指針成員賦值為空。若是空表，將新節點銜接到表頭；若長短空表，將新
節點接到表尾;
5 ) 斷定一下能否有後續節點要接入鏈表，如有轉到3 )，不然停止;
單鏈表的輸入進程有以下幾步
1) 找到表頭;
2) 若長短空表，輸入節點的值成員，是空表則加入;
3 ) 跟蹤鏈表的增加，即找到下一個節點的地址;
4) 轉到2 ).
（3），法式代碼例子：
創立一個寄存正整數單鏈表，輸出0或小於0的數，停止創立鏈表，並打印出鏈表中的值，法式以下：
#include <stdlib.h> /*含ma l l o c ( ) 的頭文件*/
#include <stdio.h>
//①界說鏈表數據構造
struct node
{
int num;
struct node *next;
};
//函數聲明
struct node *creat();
void print();
main( )
{
struct node *head;
head=NULL; //②建一個空表
head=creat(head);/*創立單鏈表*/
print(head);/*打印單鏈表*/
}
/******************************************/
struct node*creat(struct node *head)/*前往的是與節點雷同類型的指針*/
{
struct node*p1,*p2;
int i=1;
//③應用malloc ( )函數向體系請求分派一個節點
p1=p2=(struct node*)malloc(sizeof(struct node));/*新節點*/
printf("請輸出值，值小於等於0停止，值寄存地址為：p1_ADDR= %d\n",p1);
scanf("%d",&p1->num);/*輸出節點的值*/
p1->next=NULL;/*將新節點的指針置為空*/
while(p1->num>0)/*輸出節點的數值年夜於0*/
{
//④將新節點的指針成員賦值為空。若是空表，將新節點銜接到表頭；若長短空表，將新節點接到表尾;
if(head==NULL)
head=p1;/*空表，接入表頭*/
else
p2->next=p1;/*非空表，接到表尾*/
p2=p1;
p1=(struct node*)malloc(sizeof(struct node));/*下一個新節點*/
i=i+1;
printf("請輸出值，值小於等於0停止，值寄存地址為：p%d_ADDR= %d\n",i,p2);
scanf("%d",&p1->num);/*輸出節點的值*/
//⑤斷定一下能否有後續節點要接入鏈表，如有轉到3 )，不然停止;
}
//==============本來法式更正部門：（多謝@daling_datou提示）================================
free(p1); //請求到的沒錄入，所以釋放失落
p1=NULL; //使指向空
p2->next = NULL; //到表尾了，指向空
printf("鏈表輸出停止（END）\n");
//==============================================
return head;/*前往鏈表的頭指針*/
}
/*******************************************/
void print(struct node*head)/*出以head為頭的鏈表各節點的值*/
{
struct node *temp;
temp=head;/*獲得鏈表的頭指針*/
printf("\n\n\n鏈表存入的值為：\n");
while(temp!=NULL)/*只需長短空表*/
{
printf("%6d\n",temp->num);/*輸入鏈表節點的值*/
temp=temp->next;/*跟蹤鏈表增加*/
}
printf("鏈表打印停止!!");
}
在鏈表的創立進程中，鏈表的頭指針長短常主要的參數。由於對鏈表的輸入和查找都要從鏈表的頭開端，所以鏈表創立勝利後，要前往一個鏈表頭節點的地址，即頭指針。
法式履行流程：
4，單鏈表操作基本示例
#include <stdio.h>
#include <malloc.h>
#define LEN sizeof(NODE)
typedef struct _NODE//節點聲明
{
int val;
struct _NODE* next;
} NODE, *PNODE;
void print(PNODE head){//打印一切節點
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){//依據值找到知足前提的第一個節點
while (head != NULL && head->val != val)
{
head = head->next;
}
return head;
}
PNODE findByIndex(PNODE head, int index){//依據索引找節點
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){//依據索引拔出節點
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)//依據結點索引刪除結點
{
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)//依據值刪失落第一個知足前提的
{
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是要找的節點則加入
{
t = t->next;
}
if (t->next)//假如t指向要找的結點的上一個節點
{
PNODE n = t->next->next;//刪除要找的結點
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);
}
