定義
鏈式存儲的線性表
頭文件相關定義?
typedef int datatype;//定義數據域類型
typedef struct Node
{union{int len; //頭結點數據域datatype data; //普通節點數據域};struct Node *next; //節點指針域
}Node,*Node_ptr;
鏈表的函數?
注意事項?
1.創建節點時,需要初始化節點的數據域和指針域
2.創建節點后需要判斷地址來查看是否創建成功
3.無論是聲明何種函數都需要判斷頭節點是否為空
? ? 如果長度發生改變需要添加長度邏輯
? ? ? ? //判斷邏輯
? ? ? ? //功能邏輯
? ? ? ? (長度邏輯)
? ? ? ? //返回邏輯
4.任意位置的增刪改查都需要判斷插入位置是否合理
5.釋放節點后,需要將指針置空,防止野指針
6.遍歷下一個節點的操作為p=p->next;
7.理解鏈表反轉
8.頭節點不允許增刪改查
創建單向鏈表
Node_ptr linklist_create();
函數功能:從堆區空間申請一個頭結點并初始化,并檢查鏈表是否創建成功
參數:
void
返回值:成功返回頭結點地址,失敗返回
NULL
?主要代碼
Node_ptr l=(Node_ptr)malloc(sizeof(Node));
if(l==NULL)
{printf("創建鏈表失敗\n");return NULL;
}
//頭結點初始化
l->len=0;//初始化長度為0
l->next=NULL;//初始化指針為空,防止野指針
鏈表判空操作
int link_empty(Node_ptr );
函數功能:判斷鏈表是否為空
參數:鏈表頭結點地址
返回值:為空返回
1
,否則返回0
?主要代碼
//通過判斷頭結點的后繼節點指針是否為空
return l->next==NULL;
創建節點
Node_ptr Node_apply(datatype );
函數功能:從堆區申請一個新節點并判斷是否申請成功,并初始化數據域
參數:節點數據域的值
返回值:成功返回節點地址,失敗返回
NULL
?主要代碼
//堆區申請空間
Node_ptr p=(Node_ptr)malloc(sizeof(Node));
if(p==NULL)
{printf("節點空間申請失敗\n");return NULL;
}
printf("節點申請成功\n");
p->data=e; //初始化數據域
p->next=NULL; //初始化指針為空
return p; //封裝好的節點地址
單向鏈表頭插
int link_insert_head(Node_ptr ,datatype );
函數功能:通過創建節點函數申請節點,并在鏈表頭部插入新節點
參數:鏈表頭結點地址、待插入數據
返回值:成功返回
0
,失敗返回-1
//創建節點
//pa指針接收節點的地址
Node_ptr pa=Node_apply(e);
if(pa==NULL)
{printf("插入失敗\n");return -1;
}
//頭插邏輯
pa->next=L->next;//先繼承頭節點的指向
L->next=pa; //再將頭節點指針指向插入的節點
//長度自增
L->len++;
單向鏈表按位置查找
Node_ptr link_find_post(Node_ptr ,int );
函數功能:先判斷位置是否合理,根據位置查找節點地址
參數:鏈表頭結點地址、位置索引(從0開始)
返回值:成功返回節點地址,失敗返回
NULL
主要代碼?
//判斷邏輯
if(L==NULL||post<0||post>L->len)
{printf("查找失敗\n");return NULL;
}
//查找邏輯
Node_ptr q=L; //定義一個遍歷指針
for(int i=0;i<post;i++) //先移動再自加,所有不需要等于post
{q=q->next;//指向下一個節點
}
//返回節點
return q;
鏈表遍歷
void show(Node_ptr );
函數功能:先判斷是否為空,再打印鏈表中所有節點的數據
參數:鏈表頭結點地址
返回值:
void
?主要代碼
//判斷邏輯
if(link_empty(L))
{printf("遍歷失敗\n");
}
Node_ptr q=L->next; //遍歷指針指向第一個節點
while(q) //如果遍歷為空,結束遍歷
{printf("%-4d",q->data);//遍歷數據q=q->next;//指向下一個節點
}
鏈表任意位置插入
int link_insert_post(Node_ptr ,int ,datatype);
函數功能:先判斷位置是否合理,再在指定位置插入新節點
參數:鏈表頭結點地址、位置索引、待插入數據
返回值:成功返回
0
,失敗返回-1
?
//創建節點
Node_ptr p=Node_apply(e);
if(p==NULL)
{printf("插入失敗2\n");return -1;
}
//調用函數找到post-1的地址,用q接收
Node_ptr q=link_find_post(L,post-1);
//利用頭插
p->next=q->next; //插入節點繼承post-1節點的指針指向
q->next=p; //psost-1節點指向插入節點
//長度自增
L->len++;
鏈表頭刪
int link_delete_head(Node_ptr );
函數功能:判斷是否為空,刪除鏈表首節點(非頭結點)
參數:鏈表頭結點地址
返回值:成功返回
0
,失敗返回-1
//p記錄節點地址
Node_ptr p=L->next;
//刪除邏輯,頭節點指向下一個節點
L->next=p->next;
//釋放節點
free(p);
p=NULL;//防止野指針
//長度自減
L->len--;
任意位置刪除
int link_delete_post(Node_ptr ,int );
函數功能:先判斷位置是否合理,刪除指定位置的節點
參數:鏈表頭結點地址、位置索引
返回值:成功返回
0
,失敗返回-1
//遍歷到post前驅節點,p接收post-1地址
Node_ptr p=link_find_post(L,post-1);
//刪除邏輯
//本質是p->next=(p->next)->next
Node_ptr q=p->next;
p->next=q->next; //q被孤立
//釋放節點,置空
free(q);
q=NULL;
//長度自減
L->len--;
按值查找位置
int link_find_value(Node_ptr ,datatype );
函數功能:查找數據值首次出現的位置
參數:鏈表頭結點地址、待查找數據
返回值:成功返回位置索引(從
1
開始),失敗返回-1
//查找邏輯
Node_ptr p=L->next; //p指向第一個節點
for(int i=1;i<=L->len;i++) //遍歷查找
{ if(p->data==e)return i;p=p->next; //不匹配p往后移動
}
return -1;
按位置修改
int link_updata_post(Node_ptr ,int ,datatype);
函數功能:修改鏈表中指定位置節點的數據
參數:鏈表頭結點地址、位置索引、新數據
返回值:成功返回
0
,失敗返回-1
//查找邏輯,用p接收post地址
Node_ptr p=link_find_post(L,post);
//修改邏輯
p->data=e;
按值修改
int link_updata_value(Node_ptr,datatype,datatype);
函數功能:修改鏈表中值的節點數據
參數:鏈表頭結點地址、舊數據、新數據
返回值:成功返回
0
,失敗返回-1
int link_updata_value(Node_ptr L,datatype old,datatype new)
{//查找邏輯int post=link_find_value(L,old);//判斷邏輯if(post==-1){return -1;}//修改邏輯link_updata_post(L,post,new);return 0;
}
單向鏈表反轉
int link_reverse(Node_ptr );
函數功能:反轉鏈表(頭結點除外)
參數:鏈表頭結點地址
返回值:成功返回
0
,失敗返回-1
Node_ptr H=L->next; //H記錄第一個節點地址
L->next=NULL; //清空頭節點
while(H!=NULL) //遍歷
{Node_ptr q=H; //記錄H的指向,搬運作用H=H->next;//頭插形式插入q->next=L->next;L->next=q;
}
鏈表釋放
void link_free(Node_ptr);
函數功能:釋放鏈表所有節點(包括頭結點)
參數:鏈表頭結點地址
返回值:
void
//釋放邏輯
while(!link_empty(L))
{//調用頭參函數link_delete_head(L);
}
//釋放頭節點,置空
free(L);
L=NULL;
完整代碼
linklist.h?
#ifndef LINKLIST_H
#define LINKLIST_H
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef int datatype;//定義數據域類型
typedef struct Node
{union{int len; //頭結點數據域datatype data; //普通節點數據域};struct Node *next; //節點指針域
}Node,*Node_ptr;
//創建單向鏈表
Node_ptr linklist_create();
//鏈表判空操作
int link_empty(Node_ptr );
//創建節點
Node_ptr Node_apply(datatype );
//單向鏈表頭插
int link_insert_head(Node_ptr ,datatype );
//單向鏈表按位置查找返回地址
Node_ptr link_find_post(Node_ptr ,int );
//鏈表的遍歷
void show(Node_ptr );
//鏈表任意位置插入
int link_insert_post(Node_ptr ,int ,datatype);
//鏈表頭刪
int link_delete_head(Node_ptr );
//任意位置刪除
int link_delete_post(Node_ptr ,int );
//按值查找返回位置
int link_find_value(Node_ptr ,datatype );
//按位置修改
int link_updata_post(Node_ptr ,int ,datatype);
//按值修改
int link_updata_value(Node_ptr,datatype,datatype);
//單向鏈表反轉
int link_reverse(Node_ptr );
//
//鏈表的釋放
void link_free(Node_ptr);#endif
linklist.c
#include"linklist.h"
//此處頭結點的地址都用l表示
//其他節點用p/pa表示//創建單向鏈表
Node_ptr linklist_create()
{ //申請一個頭結點的空間Node_ptr l=(Node_ptr)malloc(sizeof(Node));if(l==NULL){printf("創建鏈表失敗\n");return NULL; }//頭結點初始化l->len=0;//初始化長度為0l->next=NULL;//初始化指針為空,防止野指針printf("創建鏈表成功\n");return l;
}
//鏈表判空操作
//鏈表為空返回1,非空返回0
int link_empty(Node_ptr l)
{ //判斷鏈表傳入地址是否為空if(l==NULL){printf("鏈表不合法\n");return -1;}//通過判斷頭結點的后繼節點指針是否為空return l->next==NULL;
}
//創建節點
//成功返回節點地址,失敗返回空
Node_ptr Node_apply(datatype e)
{//堆區申請空間Node_ptr p=(Node_ptr)malloc(sizeof(Node));if(p==NULL){printf("節點空間申請失敗\n");return NULL;}printf("節點申請成功\n");p->data=e; //初始化數據域p->next=NULL; //初始化指針為空return p; //封裝好的節點地址
}
//單向鏈表頭插
//成功返回0失敗返回-1
//插入的數據是逆序,先進的在后面
int link_insert_head(Node_ptr L ,datatype e )
{//判斷邏輯if(L==NULL){printf("插入失敗\n");return -1;}//創建節點//pa指針接收節點的地址Node_ptr pa=Node_apply(e);if(pa==NULL){printf("插入失敗\n");return -1;}//頭插邏輯pa->next=L->next;//先繼承頭節點的指向L->next=pa; //再將頭節點指針指向插入的節點//長度自增L->len++;printf("頭插成功\n");return 0;
}
//單向鏈表查找
//成功返回地址,失敗返回空
Node_ptr link_find_post(Node_ptr L,int post)
{//判斷邏輯if(L==NULL||post<0||post>L->len){printf("查找失敗\n");return NULL;}//查找邏輯Node_ptr q=L; //定義一個遍歷指針for(int i=0;i<post;i++) //先移動再自加,所有不需要等于post{q=q->next;//指向下一個節點}//返回節點return q;
}
//鏈表的遍歷
void show(Node_ptr L)
{//判斷邏輯if(link_empty(L)){printf("遍歷失敗\n");}Node_ptr q=L->next; //遍歷指針指向第一個節點while(q) //如果遍歷為空,結束遍歷{printf("%-4d",q->data);//遍歷數據q=q->next;//指向下一個節點}putchar(10);
}
//鏈表任意位置插入
//成功插入返回0,失敗返回-1
int link_insert_post(Node_ptr L ,int post,datatype e)
{//判斷邏輯if(L==NULL||post<1||post>L->len+1) //判斷地址和插入邏輯的合理性{printf("插入失敗1\n");return -1;}//創建節點Node_ptr p=Node_apply(e);if(p==NULL){printf("插入失敗2\n");return -1;}//調用函數找到post-1的地址,用q接收Node_ptr q=link_find_post(L,post-1);//插入邏輯p->next=q->next; //插入節點繼承post-1節點的指針指向q->next=p; //psost-1節點指向插入節點//長度自增L->len++;printf("插入數據成功\n");return 0;
}
//鏈表頭刪
//成功返回0,失敗返回-1
int link_delete_head(Node_ptr L)
{//判斷邏輯if(link_empty(L)){printf("刪除失敗\n");return -1;}//p記錄節點地址Node_ptr p=L->next;//刪除邏輯,頭節點指向下一個節點L->next=p->next;//釋放節點free(p);p=NULL;//防止野指針//長度自減L->len--;printf("鏈表頭刪成功\n");return 0;
}
//任意位置刪除
//成功返回0,失敗返回-1
int link_delete_post(Node_ptr L,int post)
{//判斷邏輯if(L==NULL||post<1||post>L->len){printf("按位置刪除失敗\n");return -1;}//遍歷到post前驅節點,p接收post-1地址Node_ptr p=link_find_post(L,post-1);//刪除邏輯//本質是p->next=(p->next)->next Node_ptr q=p->next; p->next=q->next; //q被孤立//釋放節點,置空free(q);q=NULL;//長度自減L->len--;printf("刪除成功\n");return 0;
}
//按值查找返回位置
int link_find_value(Node_ptr L ,datatype e)
{//判斷邏輯if(L==NULL||link_empty(L)){printf("查找失敗\n");return -1;}//查找邏輯Node_ptr p=L->next; //p指向第一個節點for(int i=1;i<=L->len;i++) //遍歷查找{ if(p->data==e)return i;p=p->next; //不匹配p往后移動}printf("未找到,查詢失敗\n");return -1;
}
//按位置修改
int link_updata_post(Node_ptr L,int post,datatype e)
{//判斷邏輯if(L==NULL||link_empty(L)||post<0||post>L->len+1){printf("修改失敗\n");return -1;}//查找邏輯,用p接收post地址Node_ptr p=link_find_post(L,post);//修改邏輯p->data=e;return 0;
}
//按值修改
int link_updata_value(Node_ptr L,datatype old,datatype new)
{//查找邏輯int post=link_find_value(L,old);//判斷邏輯if(post==-1){return -1;}//修改邏輯link_updata_post(L,post,new);return 0;
}
//單向鏈表反轉
int link_reverse(Node_ptr L)
{if(L==NULL||L->len<=1){printf("翻轉失敗\n");return -1;}Node_ptr H=L->next; //H記錄第一個節點地址L->next=NULL; //清空頭節點while(H!=NULL) //遍歷{Node_ptr q=H; //記錄H的指向,搬運作用H=H->next;//頭插形式插入q->next=L->next;L->next=q;}return 0;
}
//鏈表的釋放
void link_free(Node_ptr L)
{//判斷邏輯if (L=NULL){printf("釋放失敗\n");return;}//釋放邏輯while(!link_empty(L)){//調用頭參函數link_delete_head(L);}//釋放頭節點,置空free(L);L=NULL;printf("釋放成功\n");
}
main.c
#include"linklist.h"
int main(int argc, const char *argv[])
{ //定義指針x接收申請空間的首地址 Node_ptr x=linklist_create(); if(x==NULL){printf("創建失敗\n");}printf("創建鏈表成功\n");printf("%d\n",link_empty(x));//Node_apply(e);//頭插link_insert_head(x,1);link_insert_head(x,2);link_insert_head(x,3);link_insert_head(x,4);printf("%d\n",x->len);//鏈表查找//指針q接收地址Node_ptr q=link_find_post(x,2);printf("%d\n",q->data);printf("11111\n");show(x);link_insert_post(x,2,99);show(x);link_delete_head(x);show(x);link_delete_post(x,3);show(x);printf("%d\n",link_find_value(x,3));link_updata_post(x,3,88);show(x);link_updata_value(x,3,77);show(x);link_reverse(x);show(x);link_free(x);return 0;
}