歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

C語言之單向鏈表

1,單向鏈簡潔。

單向鏈表(單鏈表)是鏈表的一種,其特點是鏈表的鏈接方向是單向的,對鏈表的訪問要通過順序讀取從頭部開始;鏈表是使用指針進行構造的列表;又稱為結點列表,因為鏈表是由一個個結點組裝起來的;其中每個結點都有指針成員變量指列表中的下一個結點;

列表是由結點構成,由head指針指向第一個成為表頭的結點而終止於最後一個指向nuLL的指針;

2,例子要求:

根據示例代碼中的例子,完成單向鏈表(single linked list)中的以字符串為數據的鏈表的插入、刪除以及查找,並支持單向鏈表的反轉;

3,代碼實現。

#include <stdio.h>
#include <math.h>
#include <cstring>
#include <memory.h>
#include <malloc.h>


//節點的定義
typedef struct Node {
    void *data; //數據域 //鏈域
    struct Node *next;
} NodeStruct, *pNode;


pNode head = NULL;

 


typedef char (*pCompareFunc)(void *a, void *b);
typedef void* (*pChar)(void *p);


// 字符串判斷
int str_compare(void *a, void *b) {
    char *pa = (char*)a;
    char *pb = (char*)b;
    return strcmp(pa , pb);
}


// 分配一個節點
pNode allocate_node(void *data, pChar char_func) {
    pNode node = allocate();
    node->data = char_func(data);
    return node;
}


// 創建節點
pNode allocate() {
    void *p = malloc(sizeof(NodeStruct));
    pNode node = (pNode)p;
    node->next = NULL;
    node->data = NULL;
    return node;
}


// 添加一個節點
void insertNode(pNode node){
    if (head == null){
        head=node;
    }
    else {
        node->next = head;
        head = node;
    }
}


void* char_char(void *p) {
    char* pa = (char*)malloc(sizeof(char));
    memcpy(pa, p, sizeof(char));
    return pa;
}


// 初始化節點
pNode allocate_node(void *data, pChar char_func) {
    pNode node = allocate();
    node->data = char_func(data);
    return node;
}


// 釋放資源
void free_list(pNode node) {
    pNode next = node;


    while (next != NULL) {
        if (next->data != NULL)
            free(next->data);
        pNode temp = next;
        next = next->next;
        free(temp);
    }
}


// 1.1 添加一個節點
void insert(pNode node) {
    if (head == NULL)
        head = node;
    else {
        node->next = head;
        head = node;
    }
}


//1.2查找
int str_search(void* data,pCompareFunc compare){
    pNode next = head;
    pNode prev = NULL;
    while (next != NULL ) {
        if (compare(data, next->data) == 0) {
          // 如果查找到了,就退出返回1
          return 1;
          break;
        }
        prev = next;
        next = next->next;
    }
    // 如果一直查找不到,就返回0
    return 0;
}


// 1.3刪除節點
void remove(void* data,pCompareFunc compare) {
    pNode next = head;
    pNode prev = NULL;
    while (next != NULL) {


        if (compare(data, next->data) == 0) {
            if (prev == NULL) {
                head = next->next;
                next->next = NULL;
                free_list(next);
            } else {
                prev->next = next->next;
                next->next = NULL;
                free_list(next);
            }
            break;
        }
        prev = next;
        next = next->next;
    }


}


//1.4反轉
void invert_order()
{
    node *This,*prev;
    p=head.next;
    This=NULL;
    while(p) {
            prev=This;
            This=p;
            p=p->next;
            This->next=prev;


    }
    head.next=This;
}


void main(){
    // 1單向鏈表
    char a1[] = 'aaa1';
    char a2[] = 'aaa2';
    char a3[] = 'aaa3';
    // 1.1添加
    insertNode(allocate_node(a1, init_char));
    insertNode(allocate_node(a2, init_char));
    insertNode(allocate_node(a3, init_char));
    // 1.2查找
    int flag = 0;
    flag = str_search(&a2,str_compare);
    // 1.3刪除
    remove(&a2,str_compare);
    // 1.4反轉
    invert_order();


}

C++ 隱式類類型轉化 Implicit Class-Type Conversions http://www.linuxidc.com/Linux/2013-01/78071.htm

C語言變長數組之剖析 http://www.linuxidc.com/Linux/2013-07/86997.htm

C語言需要注意的問題 http://www.linuxidc.com/Linux/2013-05/84301.htm

C語言位域的使用及其注意點 http://www.linuxidc.com/Linux/2013-07/87027.htm

C語言中簡單的for循環和浮點型變量 http://www.linuxidc.com/Linux/2013-08/88514.htm

Copyright © Linux教程網 All Rights Reserved