鏈結串列(link list)是由節點(node)串接而成

而每個節點是採動態記憶體配置的方式來配置記憶體給他們

節點包含2個成員，第一個是該節點所儲存的資料

第二個是一個指標，用來指向下一個節點的位址

1  

鏈結串列是由許多節點鏈結而成，每一個節點均有一個指標指向下一個節點

2  

接下來我們就可以利用C語言中的結構來設計節點

3  

1.建立3節點的鏈結串列

 4  

#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *next;
};
typedef struct node Node;
int main(int argc, char *argv[])
{
Node a,b,c;
Node *ptr=&a; //宣告ptr，並將他只向節點a
a.data=12;
a.next=&b;
b.data=30;
b.next=&c;
c.data=64;
c.next=NULL;
while(ptr!=NULL){
printf("address=%p, ",ptr); //印出節點的位址
printf("data=%d ",ptr->data); //印出節點的資料
printf("next=%p\n",ptr->next); //印出下一個節點位址
ptr=ptr->next; //將ptr指向下一個節點
}
system("PAUSE");
return 0;
}
view raw gistfile1.txt hosted with ❤ by GitHub
 

未命名  

 

上述範例是以靜態的方式來配置，

也就是程式在編譯時已經配置好記憶空間給每一個節點

 

這種配置方式會有些不便，例如在新增節點，同時當一個節點不再使用

被他所占去的記憶空間也無法回收

 

以下範例是改用malloc()動態記憶體配置鏈結串列

 malloc()動態記憶體配置鏈結串列的教學點這

#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *next;
};
typedef struct node Node;
int main(int argc, char *argv[])
{
int i,val,num;
Node *first,*current,*previous;
printf("Number of nodes: ");
scanf("%d",&num);
for(i=0;i<num;i++){
current=(Node *) malloc(sizeof(Node));//建立新節點
printf("Data for node %d: ",i+1);
scanf("%d",&(current->data)); //輸入節點的data成員
if(i==0){
first=current; //如果是第一個成員把指標frist指向目前的節點
}else{
previous->next=current;//把前一個的next指向目前的節點
}
current->next=NULL; //把目前的節點的next指向NULL
previous=current; //把前一個節點設成目前的節點
}
current=first; //設current為第一個節點
while(current!=NULL){
printf("address=%p, ",current); //印出節點的位址
printf("data=%d ",current->data); //印出節點的資料
printf("next=%p\n",current->next); //印出下一個節點位址
current=current->next; //將ptr指向下一個節點
}
system("PAUSE");
return 0;
}
view raw gistfile1.txt hosted with ❤ by GitHub
 

未命名  

鏈結串列的操作

->(1)建立、列印、釋放空間函數

#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *next;
};
typedef struct node Node;
Node *createList(int*,int); //串列建立函數
Node printList(Node *); //串列列印函數
void freeList(Node *); //釋放串列記憶空間函數
int main(int argc, char *argv[])
{
Node *first;
int arr[]={14,27,32,46};
first=createList(arr,4);
printList(first);
freeList(first);
system("PAUSE");
return 0;
}
//串列建立函數
Node *createList(int *arr,int len){
int i;
Node *first,*current,*previous;
for(i=0;i<len;i++){
current=(Node *) malloc(sizeof(Node));//建立新節點
current->data=arr[i]; //設定節點的資料成員
if(i==0){
first=current; //如果是第一個成員把指標frist指向目前的節點
}else{
previous->next=current;//把前一個的next指向目前的節點
}
current->next=NULL; //把目前的節點的next指向NULL
previous=current; //把前一個節點設成目前的節點
}
return first;
}
//串列列印函數
Node printList(Node *first){
Node *node=first; //將node指向第一個節點
if(first==NULL){
printf("List is empty!\n");
}else{
while(node!=NULL){
printf("%3d",node->data);
node=node->next;
}
printf("\n");
}
}
//釋放串列記憶空間函數
void freeList(Node *first){
Node *current,*tmp;
current=first;
while(current!=NULL){
tmp=current;
current=current->next;
free(tmp);
}
}
view raw gistfile1.txt hosted with ❤ by GitHub
 

未命名  

 

 節點的搜尋與插入

#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *next;
};
typedef struct node Node;
Node *createList(int*,int); //串列建立函數
Node printList(Node *); //串列列印函數
void freeList(Node *); //釋放串列記憶空間函數
Node *searchNode(Node *,int); //搜尋節點函數
void *insertNode(Node *,int); //插入節點函數
int main(int argc, char *argv[])
{
Node *first,*node;
int arr[]={12,38,57};
first=createList(arr,3);
printList(first);
node=searchNode(first,38); //找出節點值為38的位址
insertNode(node,46); //將節點46插入在節點38之後
printList(first);
freeList(first);
system("PAUSE");
return 0;
}
//串列建立函數
Node *createList(int *arr,int len){
int i;
Node *first,*current,*previous;
for(i=0;i<len;i++){
current=(Node *) malloc(sizeof(Node));//建立新節點
current->data=arr[i]; //設定節點的資料成員
if(i==0){
first=current; //如果是第一個成員把指標frist指向目前的節點
}else{
previous->next=current;//把前一個的next指向目前的節點
}
current->next=NULL; //把目前的節點的next指向NULL
previous=current; //把前一個節點設成目前的節點
}
return first;
}
//串列列印函數
Node printList(Node *first){
Node *node=first; //將node指向第一個節點
if(first==NULL){
printf("List is empty!\n");
}else{
while(node!=NULL){
printf("%3d",node->data);
node=node->next;
}
printf("\n");
}
}
//釋放串列記憶空間函數
void freeList(Node *first){
Node *current,*tmp;
current=first;
while(current!=NULL){
tmp=current;
current=current->next;
free(tmp);
}
}
//搜尋節點函數
Node *searchNode(Node *first,int item){
Node *node=first;
while(node!=NULL){
if(node->data ==item){ //如果node的data等於item
return node; //傳回node為該節點的位址
}else{
node=node->next; //否則將指標指向下一個節點
}
}
return NULL; //如果找不到符合的節點，則傳回NULL
}
//插入節點函數
void *insertNode(Node *node,int item){
Node *newnode;
newnode=(Node *) malloc(sizeof(Node));
newnode->data=item;
newnode->next=node->next;
node->next=newnode;
}
view raw gistfile1.txt hosted with ❤ by GitHub
 

未命名  

 

節點的刪除

#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *next;
};
typedef struct node Node;
Node *createList(int*,int); //串列建立函數
Node printList(Node *); //串列列印函數
void freeList(Node *); //釋放串列記憶空間函數
Node *searchNode(Node *,int); //搜尋節點函數
void *insertNode(Node *,int); //插入節點函數
Node *deleteNode(Node *,Node*);//刪除節點函數
int main(int argc, char *argv[])
{
Node *first,*node;
int arr[]={12,38,57};
first=createList(arr,3);
printList(first);
node=searchNode(first,38); //找出節點值為38的位址
first=deleteNode(first,node); //刪除節點38
printList(first);
first=deleteNode(first,first); //刪除地一個節點
printList(first);
first=deleteNode(first,first); //刪除地一個節點
printList(first);
freeList(first);
system("PAUSE");
return 0;
}
//串列建立函數
Node *createList(int *arr,int len){
int i;
Node *first,*current,*previous;
for(i=0;i<len;i++){
current=(Node *) malloc(sizeof(Node));//建立新節點
current->data=arr[i]; //設定節點的資料成員
if(i==0){
first=current; //如果是第一個成員把指標frist指向目前的節點
}else{
previous->next=current;//把前一個的next指向目前的節點
}
current->next=NULL; //把目前的節點的next指向NULL
previous=current; //把前一個節點設成目前的節點
}
return first;
}
//串列列印函數
Node printList(Node *first){
Node *node=first; //將node指向第一個節點
if(first==NULL){
printf("List is empty!\n");
}else{
while(node!=NULL){
printf("%3d",node->data);
node=node->next;
}
printf("\n");
}
}
//釋放串列記憶空間函數
void freeList(Node *first){
Node *current,*tmp;
current=first;
while(current!=NULL){
tmp=current;
current=current->next;
free(tmp);
}
}
//搜尋節點函數
Node *searchNode(Node *first,int item){
Node *node=first;
while(node!=NULL){
if(node->data ==item){ //如果node的data等於item
return node; //傳回node為該節點的位址
}else{
node=node->next; //否則將指標指向下一個節點
}
}
return NULL; //如果找不到符合的節點，則傳回NULL
}
//插入節點函數
void *insertNode(Node *node,int item){
Node *newnode;
newnode=(Node *) malloc(sizeof(Node));
newnode->data=item;
newnode->next=node->next;
node->next=newnode;
}
//刪除節點函數
Node *deleteNode(Node *first,Node *node){
Node* ptr=first;
if(first==NULL){ //如果串列是空的，則印出Nothing to delete! */
printf("Nothing to delete!\n");
return NULL;
}
if(node==first){ //如果刪除的是第一個節點
first=first->next;//把first指向下一個節點(NULL)
}else{
while(ptr->next!=node){ //找到要刪除之節點的前一個節點
ptr=ptr->next;
}
ptr->next=node->next; //重新設定ptr的next成員
}
free(node);
return first;
}
view raw gistfile1.txt hosted with ❤ by GitHub
 

未命名  

 

 

arrow
arrow
    文章標籤
    C語言 鏈結串列(link list)
    全站熱搜
    創作者介紹
    創作者 Mark Zhang 的頭像
    Mark Zhang

    讀處

    Mark Zhang 發表在 痞客邦 留言(5) 人氣()

    E-mail轉寄