c语言实现顺序表

• 实现方法参考严蔚敏老师的数据结构教材

• 采用动态分配内存的方法

list.h

/* list.h--顺序表接口 */
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h>

#define LIST_INIT_SIZE 2
#define LIST_INCREMENT 10

typedef int Item;

typedef struct
{
    Item *elem;
    int listsize;
    int length;
}List;

/*初始化一个列表*/
void InitializeList(List * plist);

/*销毁列表*/
void DestroyList(List *plist);

/*将列表重置为空表*/
void ClearList(List *plist);
/*判断列表是否为空*/
bool ListIsEmpty(const List plist);

/*判断列表是否已满*/
//bool ListIsFull(const List plist);

/*返回列表中项目的个数*/
unsigned int ListItemCount(const List plist);

/*向列表尾部添加一个项目*/
//bool AddItem(List &plist, Item e);

/*删除列表尾部的一个元素,并将其值返回e*/
//bool popItem(List &plist, Item *e);

/*在位置i之前插入一个元素e*/
bool InsertItem(List *plist, int i, Item e);

/*删除第i个数据元素并用e返回其值*/
bool DeleteItem(List *plist, int i, Item *e);

/*获取第i个数据元素的值并用e返回*/
bool GetElem(List plist, int i, Item *e);

/*查找表中第一个值为e的元素并返回数据元素的位序*/
int LocateList(List plist, Item e);

/*返回当前元素的前驱*/
bool PriorElem(List plist, Item cur_e, Item *pri_e);

/*返回当前元素的后继*/
bool NextElem(List plist, Item cur_e, Item *Nex_e);

/*遍历*/
void TravelList(List plist);

#endif

list.c

/* list.c列表操作的函数 */
#include <stdio.h>
#include <stdlib.h>
#include "list.h"

#define OVERFLOW -1
#define ERROR 0
#define OK 1

void InitializeList(List * plist) {
    plist->elem = (Item* )malloc(LIST_INIT_SIZE*sizeof(Item));
    if (!plist->elem)
        exit(OVERFLOW);
    plist->length = 0;
    plist->listsize = LIST_INIT_SIZE;
}

void DestroyList(List *plist) {
    free(plist->elem);
    plist->elem = NULL;
    plist->length = 0;
    plist->listsize = 0;
}

void ClearList(List *plist) {
    plist->length = 0;
}

bool ListIsEmpty(const List plist) {
    return plist.length == 0;
}


unsigned int ListItemCount(const List plist) {
    return plist.length;
}

bool InsertItem(List *plist, int i, Item e) {
    if (i < 1 || i > plist->length + 1)
        return ERROR;
    if (plist->length >= plist->listsize) {
        Item *newbase;
        newbase = (Item* )realloc(plist->elem, (plist->listsize + LIST_INCREMENT) *sizeof(Item));
        if (!newbase) {
            exit(OVERFLOW);
        }
        plist->listsize += LIST_INCREMENT;
        plist->elem = newbase;

    }
    Item *q = &(plist->elem[i - 1]);
    for (Item *p = &(plist->elem[plist->length - 1]); p>=q; p--) {
        *(p + 1) = *p;
    }
    *q = e;
    plist->length++;
    return OK;
}

bool DeleteItem(List *plist, int i, Item *e) {
    if (i < 1 || i > plist->length + 1)
        return ERROR;
    Item *q = &(plist->elem[i - 1]);
    Item *p = &(plist->elem[plist->length - 1]);
    *e = *q;
    for (q++; q <= p; q++)
    {
        *(q - 1) = *q;
    }
    plist->length--;
    return OK;
}

bool GetElem(List plist, int i, Item *e) {
    if (i < 1 || i > plist.length + 1)
        return ERROR;
    *e = plist.elem[i - 1];
    return OK;
}

int LocateList(List plist, Item e) {
    for (int i = 0; i < plist.length; i++) {
        if (plist.elem[i] == e) {
            return (i+1);
        }
    }
    printf("Not exit! ");
    return ERROR;
}

bool PriorElem(List plist, Item cur_e, Item *pri_e) {
    Item *p = plist.elem;
    for (int i = 0; i < plist.length; i++,p++) {
        if (i == 0 && *p == cur_e) {
            printf("无前驱元素");
            return ERROR;
        }

        if (*p == cur_e) {
            *pri_e = *--p;
            return OK;
        }
    }
    printf("没有此值");
    return ERROR;
}

bool NextElem(List plist, Item cur_e, Item *Nex_e) {
    Item *p = plist.elem;
    for (int i = 0; i < plist.length; i++,p++) {
        if (i != plist.length - 1 && *p == cur_e) {
            *Nex_e = *++p;
            return OK;
        }
        if (*p == cur_e) {
            printf("无后继元素");
            return ERROR;
        }

    }
    printf("没有此值");
    return ERROR;
}

void TravelList(List plist) {
    int *p = plist.elem;

    for (int i = 0; i < plist.length; i++,p++)
    {
        printf("%d: ", i+1);
        printf("%d\n", *p);
    }
}

用于测试的函数main.c

#include "list.h"
#include <stdio.h>
int main () {
    List L;
    Item e;
    InitializeList(&L);
    ClearList(&L);
    printf("%d\n", L.listsize);
    InsertItem(&L, 1 , 2);
    InsertItem(&L, 2 , 3);
    printf("%d\n", L.listsize);
    InsertItem(&L, 3 , 5);
    printf("%d\n", L.listsize);
    TravelList(L);
    PriorElem(L, 3, &e);
    printf("the Prior of the elem whose value is 3 is %d\n", e);
    NextElem(L, 3, &e);
    printf("the Next of the elem whose value is 3 is %d\n", e);
    DeleteItem(&L, 1, &e);
    printf("the delete elem is %d\n",e);
    TravelList(L);
    printf("the count of the elem is %d\n", ListItemCount(L));
    GetElem(L, 2, &e);
    printf("get the second location's value is %d\n", e);
    printf("get the position of whose value is 5 is %d\n", LocateList(L, 5));
    DestroyList(&L);
    return 0;
}