程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C語言之鏈表，c語言

C語言之鏈表，c語言

編輯：關於C語言

C語言之鏈表，c語言

　　這兩天在復習C語言的知識，為了給下個階段學習OC做准備，以下的代碼的編譯運行環境是Xcode5.0版本，寫篇博文把昨天復習的C語言有關鏈表的知識給大家分享一下，以下是小菜自己總結的內容，代碼也是按照自己的思路所編寫的，有不足之處還請大牛們批評指教。

　　確切的說鏈表屬於數據結構中線性表中的內容，在鏈表中存儲的內容是按線性排列的，就像是一條線把所要存的數據串起來，可以把鏈表類比成一串珠子，數據就是一個個的珠子，數據間的next指針就相當於穿珠子的線。

　　鏈表操作的時間復雜度：往鏈表中插入數據的時間復雜度為O(1)。

　　想真正的理解鏈表及在C語言中的表示方法的前提是理解C語言中的指針和結構體，閒話少說，進代碼才是關鍵，代碼中基本上都有注釋

　　1.用結構體定義鏈表的節點

1 //定義鏈表中的節點
2 typedef struct node{
3     //存儲數據
4     int data;
5     //指向下一個節點
6     struct node *next;
7 }Node;

　　2.定義鏈表的整體結構，存放鏈表的節點和鏈表中的信息

//定義鏈表結構
typedef struct {
    //存放頭節點
    Node *head;
    //記錄節點的個數
    int count;
}List;

　　3.鏈表的初始化，給鏈表分配頭結點，節點個數初始化為0

/************************************************
 *功能：初始化鏈表，分配頭結點，結點個數為0
 *參數：鏈表指針
 *作者：Mr.li
 *日期：14-07-23
 ************************************************/
void initLinkList(List *list)
{
    //給頭節點分配內存
    list->head = malloc(sizeof(Node));
    //頭結點的下一個節點為空
    list->head->next = NULL;
    //總節點個數為0
    list->count = 0;
}

　　4.建立單項鏈表，這裡為了簡單起見，把要存入數據先存入到array中，下面我是用逆序的方法來創建鏈表的，是從head節點後插入數據，也可以用順序建鏈表，從鏈表的後面插入數據

/************************************************
 *功能：逆序建立鏈表，從頭結點後插入
 *參數：鏈表指針
 *作者：Mr.li
 *日期：14-07-23
 ************************************************/
void createLinkList(List *list)
{
    //建立鏈表用到的數據
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    //臨時節點指針用於分配節點內存
    Node *p;
    for (int i = 0; i < 10; i++)
    {
        //給新的節點分配內存
        p = (Node *)malloc(sizeof(Node));
        //給新節點賦值
        p->data = a[i];
        //把值加入到頭節點後面，逆序建立鏈表
        p->next = list->head->next;
        list->head->next = p;
        //鏈表節點個數加一
        list->count++;
    }
}

　　5.為了方便查看鏈表中的值，需要一個打印鏈表中的數據的函數

/************************************************
 *功能：打印鏈表中的值
 *參數：鏈表指針
 *作者：Mr.li
 *日期：14-07-23
 ************************************************/
void printList(List *list)
{
    //臨時節點指針變量
    Node *p;
    //從頭開始遍歷
    p = list->head->next;
    while (p != NULL)
    {
        //自定義的輸出整的函數
        print(p->data);
        p = p->next;
    }
    putchar('\n');
}

　　6.查詢元素在鏈表中對於的位置

/************************************************
 *功能：查找鏈表中指定值的位置，有的返還其位置，無，返還-1
 *參數：鏈表指針，要查找的值
 *作者：Mr.li
 *日期：14-07-23
 ************************************************/
int search(List *list, int obj)
{
    //定義游標指針
    Node *p;
    //標記值的位置
    int local = 0;
    p = list->head->next;
    while (p != NULL)
    {
        local ++;
        if (p->data == obj)
        {
            //返回值的位置
            return local;
        }
        p = p->next;
    }
    //值不存在返回-1
    return -1;
}

　　7.刪除鏈表中的相應的數據

/************************************************
 *功能：刪除鏈表中的值
 *參數：鏈表指針，要刪除的值
 *作者：Mr.li
 *日期：14-07-23
 ************************************************/
void delete(List *list, int obj)
{
    //查詢要刪除的元素是否在鏈表中，有返還相應的位置，沒有則返還-1
    int flag = search(list, obj);
    
    //判斷值的合法性
    if (flag == -1)
    {
        printf("沒有要刪除的值！\n");
    }
    else
    {
        //定義兩個輔助游標指針
        Node *p, *q;
        
        //給q,p賦值
        q= list->head;
        p = list->head->next;
        
        //循環查找相應的值並刪除
        while (p != NULL)
        {
            if (p->data == obj)
            {
                q->next = p->next;
                p->next = NULL;
                free(p);
                break;
            }
            q = p;
            p = p->next;
        }
    }
}

　　8.往鏈表中插入數據

/************************************************
 *功能：往指定的位置後插入相應的值
 *參數：鏈表指針，插入的位置，插入的值
 *作者：Mr.li
 *日期：14-07-23
 ************************************************/
void insert(List *list, int local, int number)
{
    int count = 0;
    //判斷值的合法性
    if(count > list->count)
    {
        printf("你輸入的值不合法\n");
    }
    else
    {
        //定義游標指針,指向鏈表的頭結點
        Node *p = list->head;
        while (count != local) {
            p++;
            count++;
        }
        
        //分配新的結點並給新的結點賦值
        Node *q = (Node *) malloc(sizeof(Node));
        q->data = number;
        q->next = NULL;
        
        //插入新的結點
        q->next = p->next;
        p->next = q;
    }
    
}

　　以上是小菜學習鏈表的代碼了，給大家分享一下！！

C語言中怎定義鏈表，最好把各個代碼都詳細的解釋一下

/*creat a list*/
#include "stdlib.h"
#include "stdio.h"
struct list
{ int data;
struct list *next;
};
typedef struct list node;
typedef node *link;
void main()
{ link ptr,head;
int num,i;
ptr=(link)malloc(sizeof(node));
ptr=head;
printf("please input 5 numbers==>\n");
for(i=0;i<=4;i++)
{
scanf("%d",&num);
ptr->data=num;
ptr->next=(link)malloc(sizeof(node));
if(i==4) ptr->next=NULL;
else ptr=ptr->next;
}
ptr=head;
while(ptr!=NULL)
{ printf("The value is ==>%d\n",ptr->data);
ptr=ptr->next;
}
}

上面是一個簡單的創建鏈表的C程序。所謂鏈表形象的講就是一個數據塊裡面存有數據，並且存有下一個數據的指針，這樣一個指一個形成一個數據鏈。這個數據鏈可以被操作，例如插入數據，刪除數據，等。至於指令，首先定義一個結構體，它存有數據和指向下一個數據塊的指針。然後分配空間。注意最後一個為NULL，當然你也可以指向開頭一個數據塊形成一個循環鏈表。

C語言中鏈表與隊列有很不同？

樓主你好。
鏈表是一種數據結構，而隊列是一種抽象的概念，就像棧一樣。
船是一個比較抽象的概念，具體實現有木船、鐵船等等。隊列好比是船，鏈表好比是造船的材料。
隊列可以用鏈表實現，也可以用動態數組實現，這個抽象的概念可以用各種具體的數據結構實現。
SQQUEUE的第一個元素elemtype *elem;其實是指向了一個數組，該數組中存儲著類型為elemtype的元素，然後front和rear就標識了隊首和隊尾元素對應的數組下標。

typedef struct _Point{
int x,y;
}Point;
#define elemtype Point//這個elemtype可以是任意你自己定義的結構，可以是結構體，也可以是簡單數據類型
elemtype array[10]={0};//這個是隊列的數據結構，在這裡是一個Point數組
SQQUEUE queue={0};
queue.elem=array;//這樣array中的元素就是queue中的元素了。
queue.front=queue.rear=queue.size=0;

你說的next指針是鏈表節點中的成員。你想想鏈表和鏈表節點間的區別。
typedef struct _ListNode{//這是鏈表節點
int x,y;//這是存儲的數據
struct _ListNode *next;
}ListNode;
typedef struct _List{//這是鏈表，這裡並不存儲next
ListNode* front,rear;
}List;
如果還不懂，可以追問我。