|
|
3.鏈表節點的插入
4.鏈表節點的刪除
3.鏈表節點的插入
解：
??? 1) 首先聲明一個新節點供輸入要插入節點的內容
??? 2) 由用戶輸入一個節點內容(Key)，表示欲插入在哪一個節點之后
??? 3) 持續往下一個節點，直到節點內容Key或節點指針為NULL為止(即找不到該節點)
??? 4) 如果該節點不存在，則插入在節點前
????????New->Next=Head
????????Head=New
??? 5) 如果找到該節點，則
??????? New->Next=Pointer->Next
??????? Pointer->Next=New
*程序代碼如下：
#include<stdlib.h>
#include<stdio.h>
#define Max 10
struct List??????????? /*節點結構聲明*/
{
??? int Number;
??? int Total;
??? struct List *Next;
};
typedef struct List Node;
typedef Node *Link;
int Data[2][Max]={1,3,5,7,2,4,6,8,9,0,15,35,10,67,25,65,38,70,30,20};
/*插入節點至鏈表內*/
Link Insert_List(Link Head,Link New,int Key)
{
??? Link Pointer;??????? /*聲明節點*/
??? Pointer=Head;??????? /*Pointer指針設為首節點*/
??? while(1)
??? {
??????? if(Pointer==NULL)??? /*插入在首節點前*/
??????? {
??????????? New->Next=Head;
??????????? Head=New;
??????????? break;
??????? }
??????? if(Pointer->Number==Key)??? /*插入在鏈表中間或尾端*/
??????? {
??????????? New->Next=Pointer->Next;
??????????? Pointer->Next=New;
??????????? break;
??????? }
??????? Pointer=Pointer->Next;??? /*指向下一個節點*/
??? }
??? return Head;
}
/*輸出鏈表數據*/
void Print_List(Link Head)
{
??? Link Pointer;??????? /*節點聲明*/
??? Pointer=Head;??????? /*Pointer指針設為首節點*/
??? while(Pointer!=NULL)????/*當節點為NULL結束循環*/
??? {
????????printf("[%d,%d]",Pointer->Number,Pointer->Total);
????????Pointer=Pointer->Next;????/*指向下一個節點*/
??? }
??? printf("\n");
}
/*釋放鏈表*/
void Free_List(Link Head)
{
??? Link Pointer;??????? /*節點聲明*/
??? while(Head!=NULL)??? /*當節點為NULL結束循環*/
??? {
??????? Pointer=Head;
??????? Head=Head->Next;
??????? free(Pointer);
??? }
}
/*建立鏈表*/
Link Create_List(Link Head)
{
??? Link New;??????? /*節點聲明*/
??? Link Pointer;??? /*節點聲明*/
??? int i;
??? Head=(Link)malloc(sizeof(Node));??? /*分配內存*/
??? if(Head==NULL)
??????? printf("Memory allocate Failure!\n");??? /*內存分配失敗*/
??? else
??? {
??????? Head->Number=Data[0][0];??????? /*定義首節點數據編號*/
??????? Head->Total=Data[1][0];
??????? Head->Next=NULL;
??????? Pointer=Head;??????? /*Pointer指針設為首節點*/
??????? for(i=1;i<Max;i++)
??????? {
??????????? New=(Link)malloc(sizeof(Node));??? /*分配內存*/
??????????? New->Number=Data[0][i];
??????????? New->Total=Data[1][i];
??????????? New->Next=NULL;
??????????? Pointer->Next=New;??????? /*將新節點串連在原列表尾端*/
??????????? Pointer=New;??????????? /*列表尾端節點為新節點*/
??????? }
??? }
??? return Head;
}
/*主程序*/
void main()
{
??? Link Head;??????? /*節點聲明*/
??? Link New;
??? int Key;
??? Head=Create_List(Head);??? /*建立鏈表*/
??? if(Head!=NULL)
??? {
??????? Print_List(Head);????
??????? while(1)
??????? {
??????????? printf("Input 0 to Exit\n");??? /*數據輸入提示*/
??????????? New=(Link)malloc(sizeof(Node));??? /*分配內存*/
??????????? printf("Please input Data number:");
??????????? scanf("%d",&New->Number);
??????????? if(New->Number==0)??????? /*輸入0時結束循環*/
??????????????? break;
??????????? printf("Please input the data total:");
??????????? scanf("%d",&New->Total);
??????????? printf("Please input the data number for Insert:");
??????????? scanf("%d",&Key);
??????????? Head=Insert_List(Head,New,Key);??? /*插入節點*/
??????????? Print_List(Head);??????????????? /*輸出鏈表數據*/
??????? }
??????? Free_List(Head);??????? /*釋放鏈表*/
??? }
}
*程序運行結果如下：
------------------------------------------------------------------
4.鏈表節點的刪除
解：
??? 持續往下一個節點查找要刪除的節點，直到節點內容找到或節點指針為NULL(即找不到該節點)。
??? 在刪除時，必須記錄前一個節點的位置(Back)
??? 如果該節點不存在，輸出一個節點不存在的提示
??? 如果該節點存在，且是首節點：
??????? Head=Pointer->Next
??????? free(Pointer)
??? 如果該節點存在，但不是首節點(即鏈表內節點或尾端節點)，則：
??????? Back->Next=Pointer->Next
??????? free(Pointer)
*程序代碼如下：
#include<stdio.h>
#include<stdlib.h>
#define Max 10
struct List????????????/*節點結構聲明 */
{
????int Number;
????int Total;
????struct List *Next;
};
typedef struct List Node;
typedef Node *Link;
int Data[2][Max]={1,3,5,7,2,4,6,8,9,10,15,35,10,67,25,65,38,70,30,20};
/*刪除鏈表內節點*/
Link Delete_List(Link Head,int Key)
{
????Link Pointer;????????/*節點聲明*/
????Link Back;
????Pointer=Head;????????/*Pointer 指針設為首節點*/
????while(1)
????{
????????if(Pointer->Next==NULL)
????????{
????????????printf("Not Found!\n");
????????????break;
????????}
????????if(Head->Number==Key)????????/*刪除首節點*/
????????{
????????????Head=Pointer->Next;
????????????free(Pointer);
????????????break;
????????}
????????Back=Pointer;
????????Pointer=Pointer->Next;????/*指向下一個節點*/
????????if(Pointer->Number==Key)????/*插入在鏈表中間或尾端*/
????????{
????????????Back->Next=Pointer->Next;
????????????free(Pointer);
????????????break;
????????}
????}
????return Head;
}
/*輸出鏈表數據*/
void Print_List(Link Head)
{
????Link Pointer;????????/*節點聲明*/
????Pointer=Head;????????/*Pointer指針設為首節點*/
????while(Pointer!=NULL)????/*當節點為NULL結束循環*/
????{
????????printf("[%d,%d]",Pointer->Number,Pointer->Total);
????????Pointer=Pointer->Next;????/*指向下一個節點*/
????}
????printf("\n");
}
/*釋放鏈表*/
void Free_List(Link Head)
{
????Link Pointer;????????/*節點聲明*/
????while(Head!=NULL)????/*當節點為NULL結束循環*/
????{
????????Pointer=Head;
????????Head=Head->Next;????????/*指向下一個節點*/
????????free(Pointer);
????}
}
/*建立鏈表*/
Link Create_List(Link Head)
{
????Link New;????????/*節點聲明*/
????Link Pointer;
????int i;
????Head=(Link)malloc(sizeof(Node));????????/*分本內存*/
????if(Head==NULL)
????????printf("Memory allocate Failure!\n");????/*內存分配失敗*/
????else
????{
????????Head->Number=Data[0][0];????????/*定義首節點數據編號*/
????????Head->Total=Data[1][0];
????????Head->Next=NULL;
????????Pointer=Head;????????/*Pointer指針設為首節點*/
????????for(i=1;i<Max;i++)
????????{
????????????New=(Link)malloc(sizeof(Node));????????/*分配內存*/
????????????New->Number=Data[0][i];
????????????New->Total=Data[1][i];
????????????New->Next=NULL;
????????????Pointer->Next=New;????????/*將新節點串連在原列表尾端*/
????????????Pointer=New;????????????/*列表尾端節點為新節點*/
????????}
????}
????return Head;
}
/*主程序*/
void main()
{
????Link Head=NULL;????????/*節點聲明*/
????int Key;
????Head=Create_List(Head);????????/*建立鏈表*/
????if(Head!=NULL)
????{
????????Print_List(Head);
????????while(1)
????????{
????????????printf("Input 0 to exit\n");????/*數據輸入提示*/
????????????printf("Please input the data number for Delete:");
????????????scanf("%d",&Key);
????????????if(Key==0)????????/*時結束循環*/
????????????????break;
????????????Head=Delete_List(Head,Key);????/*刪除節點*/
????????????Print_List(Head);????????????? /*輸出鏈表*/
????????}
??????? Free_List(Head);????????/*釋放鏈表*/
????}
}
*程序運行結果如下：
??
|
|