ITPub博客

首页 > Linux操作系统 > Linux操作系统 > C语言之单向链表

C语言之单向链表

原创 Linux操作系统 作者:mchdba 时间:2014-12-31 23:37:12 0 删除 编辑
1,单向链简洁。
单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指列表中的下一个结点;

列表是由结点构成,由head指针指向第一个成为表头的结点而终止于最后一个指向nuLL的指针;


2,例子要求:
根据示例代码中的例子,完成单向链表(single linked list)中的以字符串为数据的链表的插入、删除以及查找,并支持单向链表的反转;


3,代码实现。
#include
#include
#include
#include
#include


//节点的定义
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();


}

 ----------------------------------------------------------------------------------------------------------------
<版权所有,允许转载,但必须以链接方式注明源地址,否则追究法律责任!>
原博客地址:  http://blog.itpub.net/26230597/viewspace-1386593/
原作者:黄杉 (mchdba)
----------------------------------------------------------------------------------------------------------------


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/26230597/viewspace-1386593/,如需转载,请注明出处,否则将追究法律责任。

下一篇: C语言之双向链表
请登录后发表评论 登录
全部评论
Happy is the man who is living by his hobby.

注册时间:2011-09-05

  • 博文量
    147
  • 访问量
    3749121