嵌入式Memo35 数据结构：链式表操作 链表与结构体指针 链表小程序 On Aug 19 2013

数据结构含三个内容：逻辑结构；线性（线性表、栈、队）和非线性（树形、图形）
                              储存结构；顺序和链式
                              运算算法；检索，排序，插入，删除，修改等
实现对链表的基本操作：重点是掌握    指针与结构体   链表与结构体指针
链表含有头结点，对链表的操作就是以头结点开始的遍历过程，在过程中操作；
是单向链表，链表的操作主要是指针的操作，本程序clist.c的实现细节不重要，重要的是指针的应用。
conmon.h

//本程序中的链表都带头节点
#ifndef _COMMON_H_
#define _COMMON_H_

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <strings.h>

#define TRUE 1
#define FALSE 0

typedef int datatype;
typedef struct clist
{
    datatype data;
    struct clist *next;
}clistnode, *clistlink;

clistlink creat_clist_node(datatype x);
clistlink creat_clist(void);
void set_empty_clist(clistlink head);
int isempty_clist(clistlink head);
int get_length_clist(clistlink head);
int get_elem_clist(clistlink head, int i, datatype *ret);
int locate_clist(clistlink head, datatype x);
void insert_clist(clistlink head, datatype x, int i);
int del_clist(clistlink head, int i, datatype *ret);
void show_clist(clistlink head);
#endif

clist.c

////本程序中的链表都带头节点
#include "common.h"

clistlink creat_clist_node(datatype x)//创建空节点
{
    clistlink q = (clistlink)malloc(sizeof(clistnode));
    assert(q);
    q->data = x;
    q->next = NULL;
    return q;
}
clistlink creat_clist(void)//创建头节点
{
    clistlink head = creat_clist_node(-1);
    return head;
}
void set_empty_clist(clistlink head)//清空链表，（不是对内存单元的清空，而是对头指针的指向操作）
{
    head->next = NULL;
}
int isempty_clist(clistlink head)//判断是否为空链表
{
    return head->next == NULL ? TRUE : FALSE;
}
int get_length_clist(clistlink head)//获取链表长度
{
    clistlink p = NULL;
    int count = 0;
    p = head->next;
    while(p)
    {
        count ++;
        p = p->next;
    }
    return count;
}
int get_elem_clist(clistlink head, int i, datatype *ret)//获取链表元素
{
    int j=1;
    clistlink p = head->next;
    if(i<1 || i>get_length_clist(head))
    {
        printf("i is wrong!\n");
        return FALSE;
    }
    while(j<i)
    {
        p = p->next;
        j++;
    }
    *ret = p->data;
    return TRUE;
}
int locate_clist(clistlink head, datatype x)//返回值为x的节点在链表中的位置
{
    int i = 0;
    clistlink p = head->next;
    if(p == NULL)
        return i;
    while(p)
    {
        if(p->data != x)
        {
            p = p->next;
            i++;
        }
        else
            return i+1;
    }
}

void insert_clist(clistlink head, datatype x, int i)//在第i个元素前插入值为x的节点
{
    int j = 1;
    clistlink p = NULL, q = NULL;
    if(i<1 || i>get_length_clist(head)+1)
    {
        printf("i is wrong!\n");
        return;
    }
    q = creat_clist_node(x);
    p = head;
    while(j<i)
    {
        p = p->next;
        j++;
    }
    q->next = p->next;
    p->next = q;

}
int del_clist(clistlink head, int i, datatype *ret)//删除指定位置的元素
{
    int j=1;
    clistlink p = head, q = NULL;
    if(isempty_clist(head))
    {
        printf("clist is empty!\n");
        return FALSE;
    }
    if(i<1 || i>get_length_clist(head))
    {
        printf("i is wrong!\n");
        return FALSE;
    }
    while(j<i)
    {
        p = p->next;
        j++;
    }
    q = p->next;
    *ret = q->data;
    p->next = q->next;
    free(q);
    q = NULL;
    return TRUE;
}

void show_clist(clistlink head)//打印链表
{
    clistlink p = head->next;
    while(p)
    {
        printf("%d,",p->data);
        p = p->next;
    }
    putchar('\n');
}

main.c

#include "common.h"

int main (int argc, char *argv[])
{
    int i=1;
    datatype k;
    clistlink head = creat_clist();
    while(i<=5)//创建一个1，2，3，4，5的链表
    {
        insert_clist(head, i, i);
        i++;
    }
    show_clist(head);//打印链表
    get_elem_clist(head, 3, &k);//获取指定位置的元素，并返回值
    printf("%d\n",k);
    del_clist(head, 2, &k);//删除指定元素，并返回值
    show_clist(head);
    return 0;
}