数据结构顺序表的基本操作C语言版

love1ning

顺序表的基本操作C语言版
//list.h                         list.h头文件
/*
* ADT list
*/

#define LIST_INIT_SIZE 100
#define LISTINCREMENT  10
#define  TRUE  1
#define  FALSE  0
#define  OK  1
#define  ERROR  0

#define  INFEASIBLE  -1  //不可实行的
#define  OVERFLOW  -2    //溢出

typedef  int  elemtype;
typedef struct {
    elemtype *elem;  //存储空间基址
    int length;    //当前长度
    int listsize;  //当前分配的存储容量（以sizeof(ElemType)为单位）
} sqlist;

int init_list(sqlist *L);
//操作结果：构造一个空的线性表L

void list_create(sqlist *L);
//初始条件：线性表L已存在
//操作结果：依次向线性表L中插入元素 直到输入-1表示结束

void destroy_list(sqlist *L);
//初始条件：线性表L已存在
//操作结果：销毁线性表L

void clear_list(sqlist *L);
//初始条件：线性表L已存在
//操作结果：将L重置为空表

int list_empty(sqlist *L);
//初始条件：线性表L已存在
//操作结果：若L为空表则返回TRUE 否则返回FALSE

int list_length(sqlist *L);
//初始条件：线性表L已存在
//操作结果：返回L中数据元素的个数

void get_elem(sqlist *L, int i, elemtype *e);
//初始条件：线性表L已存在 1<=i<=list_length(&L)
//操作结果：用e返回L中第i个数据元素的值

int prior_elem(sqlist *L, elemtype cur_e, elemtype *pre_e);
//初始条件：线性表L已存在
//操作结果：若cur_e是L的数据元素 且不是第一个 则用pre_e返回它的前驱
//否则操作失败 pre_e无定义

int next_elem(sqlist *L, elemtype cur_e, elemtype *pre_e);
//初始条件：线性表L已存在
//操作结果：若cur_e是L的数据元素 且不是最后一个 则用pre_e返回它的
//后继 否则操作失败 pre_e无定义

void list_insert(sqlist *L, int i, elemtype e);
//初始条件：线性表L已存在 1<=i<=List_length(&L)+1
//操作结果：在L中第i个位置之前插入新的数据元素e L的长度加1

void list_delete(sqlist *L, int i, elemtype *e);
//初始条件：线性表L已存在且非空 1<=i<=list_length(&L)
//操作结果：删除L的第i个数据元素 并用e返回其值 L的长度减1

void list_traverse(sqlist *L, int (*visit)(elemtype));
//初始条件：线性表L已存在
//操作结果：依次对L的每个数据元素调用函数visit() 并在线性表L中保存修改结果

int list_search(sqlist *L, elemtype e);
//初始条件：线性表L已存在
//操作结果：查找元素e 若找到则返回元素e的位置 否则返回-1

void list_travel(sqlist *L);
//初始条件：线性表L已存在
//操作结果：依次输出线性表L中的元素

void insert_end(sqlist *L, elemtype e);
//初始条件：线性表L已存在
//操作结果：在线性表L最后插入元素e

int visit(elemtype e);
//visit函数


//list.c
#include"list.h"
#include<stdio.h>
#include<stdlib.h>

int init_list(sqlist *L)  
{
//操作结果：构造一个空的线性表L

    L -> elem = (elemtype *)malloc(LIST_INIT_SIZE * sizeof(elemtype));
    if (!L -> elem)
        exit(OVERFLOW);
    L -> length = 0;
    L -> listsize = LIST_INIT_SIZE;

    return OK;
}

void list_create(sqlist *L)
{
//操作结果：依次向线性表L中插入元素 直到输入-1表示结束

    int i;
    elemtype elem;
    i = 0;
    printf("please input some elem : \n");
    do {
        scanf("%d", &elem);
        if (elem == -1)
            break;
        L -> elem[i++] = elem;
        L -> length++;
    } while(1);
}

void destroy_list(sqlist *L)
{
//操作结果：销毁线性表L

    free(L -> elem);
    L -> length = 0;
    L -> listsize = 0;
}

void clear_list(sqlist *L)
{
//操作结果：将L重置为空表

    L -> length = 0;
}

int list_empty(sqlist *L)
{
//操作结果：若L为空表则返回TRUE 否则返回FALSE

    if (L -> length)
        return TRUE;
    else
        return FALSE;
}

int list_length(sqlist *L)
{
//操作结果：返回L中数据元素的个数

    return L -> length;
}

void get_elem(sqlist *L, int i, elemtype *e)
{
//操作结果：用e返回L中第i个数据元素的值

    if (L -> length == 0) {
        printf("error : sqlist\n");
        return;
    }
    if (i < 1 || i > L -> length) {
        printf("error : i\n");
        return;
    }
    *e = L -> elem[i - 1];
}

int prior_elem(sqlist *L, elemtype cur_e, elemtype *pre_e)
{
//操作结果：若cur_e是L的数据元素 且不是第一个 则用pre_e返回它的前驱
//否则操作失败 pre_e无定义

    int i = 1;
    if (L -> length == 0) {
        printf("error : sqlist\n");
        return ERROR;
    }
    while (i < L -> length) {
        if (L -> elem == cur_e) {
            *pre_e = L -> elem[i - 1];
            return OK;
        }
        i++;
    }

    return ERROR;
}

int next_elem(sqlist *L, elemtype cur_e, elemtype *pre_e)
{
//操作结果：若cur_e是L的数据元素 且不是最后一个 则用pre_e返回它的
//后继 否则操作失败 pre_e无定义

    int i = 0;
    if (L -> length == 0) {
        printf("error : sqlist\n");
        return ERROR;
    }
    while (i < L -> length - 1) {
        if (cur_e == L -> elem) {
            *pre_e = L -> elem[i + 1];
            return OK;
        }
        i++;
    }

    return ERROR;
}

void list_insert(sqlist *L, int i, elemtype e)
{
//操作结果：在L中第i个位置之前插入新的数据元素e L的长度加1

    int j;
    if (i < 1 || i > L -> length + 1) {
        printf("error : i\n");
        return;
    }
    j = L -> length;
    while (j >= i) {
        L -> elem[j] = L -> elem[j - 1];
        j--;
    }
    L -> elem[j] = e;
    L -> length++;
}

void list_delete(sqlist *L, int i, elemtype *e)
{
//操作结果：删除L的第i个数据元素 并用e返回其值 L的长度减1

    if (i < 1 || i > L -> length) {
        printf("error : i\n");
        return;
    }
    *e = L -> elem[i - 1];
    while (i < L -> length) {
        L -> elem[i - 1] = L -> elem;
        i++;
    }
    L -> length--;
}

int list_search(sqlist *L, elemtype e)
{
//操作结果：查找元素e 若找到则返回元素e的位置 否则返回-1

    int i;
    for (i = 0; i < L -> length; i++)
        if (L -> elem == e)
            return i + 1;

    return -1;
}

void list_travel(sqlist *L)
{
//操作结果：依次输出线性表L中的元素

    int i;
    for (i = 0; i < L -> length; i++)
        printf("%d  ", L -> elem);
    putchar('\n');
}

void insert_end(sqlist *L, elemtype e)
{
//操作结果：在线性表L最后插入元素e

    L -> elem[L ->length] = e;
    L -> length++;
}

void list_traverse(sqlist *L, int (*visit)(elemtype))
{
//操作结果：依次对L的每个数据元素调用函数visit() 并在线性表L中保存修改结果

    int i;
    for (i = 0; i < L-> length; i++)
        L -> elem = visit(L -> elem);
}

int visit(elemtype e)
{
    elemtype elem;

    elem = e * e;
    return elem;
}


以下是我编写的测试主程序：
//main.c
#include <stdio.h>
#include <stdlib.h>
#include"list.h"

int main(void)
{
    sqlist L;
    int ren;
    int pre_e;
    int e;

    ren = init_list(&L);
    if (ren != 1)
        printf("error : init_list\n");

    printf("%d\n", L.listsize);

    if (list_empty(&L))
        printf("list not null\n");
    else
        printf("list null\n");

    printf("length : %d\n", list_length(&L));

    list_create(&L);
    list_traverse(&L, visit);
    list_travel(&L);

    clear_list(&L);

    if (list_empty(&L))
        printf("list not null\n");
    else
        printf("list null\n");

    list_insert(&L, 1, 11);
    list_insert(&L, 2, 22);
    list_insert(&L, 1, 1);

    printf("length : %d\n", list_length(&L));

    prior_elem(&L, 11, &pre_e);
    printf("%d\n", pre_e);

    next_elem(&L, 11, &pre_e);
    printf("%d\n", pre_e);
    printf("length : %d\n", list_length(&L));

    insert_end(&L, 33);

    list_travel(&L);

    printf("%d\n", list_search(&L, 11));

    list_delete(&L, 1, &e);
    printf("%d\n", e);
    printf("length : %d\n", list_length(&L));

    clear_list(&L);
    printf("length : %d\n", list_length(&L));

    destroy_list(&L);

    return 0;
}

yjn866y

学习了。。谢谢。。

dd650705

可以呀 挺好的~

奥斯特

真好，我刚学到链表，就卡在顺序表这里