C语言线性表(基于链式结构)

zzpdljd 2014-08-06

C语言线性表(基于链式结构)

List.h文件

/**
 * C语言线性表(基于链式结构)
 * 指定数据类型为整型
 * 采用头结点方式
 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define NO 0

typedef int Status;
typedef int ElemType;
//定义表节点的结构
typedef struct Node{
    ElemType data;
    struct Node* next;
}Node;
//定义表的结构
typedef struct Node* List;

/*
 * 初始化线性表
 */
List InitList(int n);
/*
 * 销毁线性表
 */
void DestroyList(List l);
/*
 * 清空线性表
 */
void ClearList(List l);
/*
 * 判断线性表是否为空
 */
Status ListEmpty(List l);
/*
 * 计算线性表中元素的个数
 */
int ListLength(List l);
/*
 * 获得指定位置元素
 */
Status GetElem(List l, int i, ElemType* e);
/*
 * 获得指定元素位置
 */
int LocateElem(List l, ElemType e);
/*
 * 获取指定元素的前一个元素
 */
Status PriorElem(List l, int i, ElemType* e);
/*
 * 获取指定元素的后一个元素
 */
Status NextElem(List l, int i, ElemType* e);
/*
 * 向线性表指定位置插入一个元素
 */
Status ListInsert(List l, int i, ElemType e);
/*
 * 删除线性表指定位置的元素
 */
Status ListDelete(List l, int i);
/*
 * 输出链表内所有元素的值
 */
void PrintList(List l);

List.c文件

#include <stdio.h>
#include <stdlib.h>
#include "List.h"

List InitList(int n)
{
    //{
    /*
    * 以下是一种正常的初始化方法,为了进一步提高效率还有两种改进方法头插法和尾插法,
    * 这两种方法可以减少循环中一次复制运算,并减少了定义临时指针
    */
    List l;    //定义一个节点指针,用于保存链表第一个节点的地址
    l = (List)malloc(sizeof(Node));    //定义一个节点作为头节点并赋给节点指针
    l->next = NULL;    //初始化头结点

    Node *t;    //定义一个节点指针,用于保存临时地址
    t = l;  //将头结点的地址赋给指针

    int i;
    for(i=1; i<=n; i++){
        //创建一个新节点并初始化
        Node* p = (Node*)malloc(sizeof(Node));
        p->data = i;
        p->next = NULL;
        t->next = p;    //另上个节点的next指针指向p;
        t = p;  //让t保存新节点p的地址
    }

    return l;
    //}
}

void DestroyList(List l)
{
    Node* t;
    while(l){
        t = l;
        l = l->next;
        free(t);
    }
    l = NULL;
}

void ClearList(List l)
{
    l = l->next;
    while(l){
        l->data = 0;
        l = l->next;
    }
}

Status GetElem(List l, int i, ElemType* e)
{
    while(l && i){
        l = l->next;
        i--;
    }
    if(i != 0)
        return NO;
    *e = l->data;
    return OK;
}

Status ListEmpty(List l)
{
    if(l)
        return FALSE;
    else
        return TRUE;
}

int ListLength(List l)
{
    int length = 0;
    while(l){
        l = l->next;
        length++;
    }
    return length;
}

int LocateElem(List l, ElemType e)
{
    l = l->next;
    int location = 0;
    while(l){
        location++;
        if(l->data == e)
            return location;
        l = l->next;
    }
    return 0;
}

Status PriorElem(List l, int i, ElemType* e)
{
    int j = 1;
    l = l->next;
    Node* tmp_node;
    while(l && j<i){
        tmp_node = l;
        l = l->next;
        j++;
    }
    if(j < i)
        return FALSE;
    else{
        *e = tmp_node->data;
        return TRUE;
    }
}

Status NextElem(List l, int i, ElemType* e)
{
    while(l && i){
        l = l->next;
        i--;
    }
    if(i != 0)
        return FALSE;
    else{
        if(l->next){
            *e = l->next->data;
            return TRUE;
        }else{
            return FALSE;
        }
    }
}

Status ListInsert(List l, int i, ElemType e)
{
    l = l->next;
    Node* tmp_node;
    while(l && i){
        tmp_node = l;
        l = l->next;
        i--;
    }
    if(i != 0)
        return FALSE;
    else{
        Node* p = (Node*)malloc(sizeof(Node));
        p->data = e;
        p->next = l;
        tmp_node->next = p;
        return TRUE;
    }

}

Status ListDelete(List l, int i)
{
    Node* tmp_node;
    while(l && i){
        tmp_node = l;
        l = l->next;
        i--;
    }
    if(i != 0)
        return TRUE;
    else{
        tmp_node->next = l->next;
        free(l);
        return TRUE;
    }
}

void PrintList(List l)
{
    l = l->next;
    while(l){
        printf("%d\n",l->data);
        l = l->next;
    }
}

int main()
{
    List l = InitList(5);
    ElemType tmp_elem = 0;

    PrintList(l);

    int s = GetElem(l,3,&tmp_elem);
    printf("the element is %d\n", tmp_elem);

    NextElem(l,3,&tmp_elem);
    printf("the goal element's next element is %d\n", tmp_elem);

    if(PriorElem(l,3,&tmp_elem))
        printf("the goal element's prior element is %d\n", tmp_elem);

    int location = LocateElem(l,4);
    printf("the location id is %d\n", location);

    ListInsert(l,3,8);
    PrintList(l);

    ListDelete(l,4);
    PrintList(l);

    return 0;
}

将C语言梳理一下,分布在以下10个章节中:

  1. Linux-C成长之路(一):Linux下C编程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
  2. Linux-C成长之路(二):基本数据类型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
  3. Linux-C成长之路(三):基本IO函数操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
  4. Linux-C成长之路(四):运算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
  5. Linux-C成长之路(五):控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
  6. Linux-C成长之路(六):函数要义 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
  7. Linux-C成长之路(七):数组与指针 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
  8. Linux-C成长之路(八):存储类,动态内存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
  9. Linux-C成长之路(九):复合数据类型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
  10. Linux-C成长之路(十):其他高级议题

相关推荐