LinearList.c文件
#include <stdio.h>
#include <malloc.h>
#include "LinearList.h"
//线性表
static void clear(LinearList *This);
static int isEmpty(LinearList *This);
static int length(LinearList *This);
static void print(LinearList *This);
static int indexElem(LinearList *This, ElemType* x);
static int priorElem(LinearList *This, ElemType* cur_elem, ElemType* pre_elem);
static int getElem(LinearList *This, int index, ElemType* e);
static int modifyElem(LinearList *This, int index, ElemType* e);
static int nextElem(LinearList *This, ElemType* cur_elem, ElemType* next_elem);
static int insertElem(LinearList *This, int index, ElemType* e);
static int deleteElem(LinearList *This, int index, ElemType* e);
static int appendElem(LinearList *This,ElemType* e);
static int popElem(LinearList *This, ElemType* e);
LinearList *InitLinearList(){
LinearList *L = (LinearList *)malloc(sizeof(LinearList));
LinearList_P *p = (LinearList_P *)malloc(sizeof(LinearList_P));
p->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
p->length = 0; //当前长度
p->size = LIST_INIT_SIZE; //当前分配量
L->This = p;
L->clear = clear;
L->isEmpty = isEmpty;
L->length = length;
L->print = print;
L->indexElem = indexElem;
L->priorElem = priorElem;
L->getElem = getElem;
L->modifyElem = modifyElem;
L->nextElem = nextElem;
L->insertElem = insertElem;
L->deleteElem = deleteElem;
L->appendElem = appendElem;
L->popElem = popElem;
return L;
}
void DestroyLinearList(LinearList *L){
free(L->This);
free(L);
L = NULL;
}
static void clear(LinearList *This){
LinearList_P *p = This->This;
p->length = 0; //当前长度
}
static int isEmpty(LinearList *This){
LinearList_P *p = This->This;
return (p->length == 0);
}
static int length(LinearList *This){
LinearList_P *p = This->This;
return p->length;
}
static void print(LinearList *This){
LinearList_P *p = This->This;
int i;
for (i=0; i < p->length; i++){
printf("%d ", p->elem[i]);
}
printf("\n");
}
static int indexElem(LinearList *This, ElemType* x){
LinearList_P *p = This->This;
int pos = -1;
for (int i = 0; i < p->length; i++){
if (p->elem[i] == *x){
pos = i;
}
}
return pos;
}
static int priorElem(LinearList *This, ElemType* cur_elem, ElemType* pre_elem){
LinearList_P *p = This->This;
int pos = -1;
pos = indexElem(This, cur_elem);
if(pos <= 0) return -1;
*pre_elem = p->elem[pos-1];
return 0;
}
static int getElem(LinearList *This, int index, ElemType* e){
LinearList_P *p = This->This;
if (index<0 || index >= p->length) return -1;
*e = p->elem[index];
return 0;
}
static int modifyElem(LinearList *This, int index, ElemType* e){
LinearList_P *p = This->This;
if (index<0 || index >= p->length) return -1;
p->elem[index] = *e;
return 0;
}
static int nextElem(LinearList *This, ElemType* cur_elem, ElemType* next_elem){
LinearList_P *p = This->This;
int pos = -1;
pos = indexElem(This, cur_elem);
if(pos == -1 || pos == (p->length - 1)) return -1;
*next_elem = p->elem[pos+1];
return 0;
}
static int insertElem(LinearList *This, int index, ElemType* e){
LinearList_P *p = This->This;
if (index<0 || index >= p->length) return -1;
if (p->length >= p->size){ //判断存储空间是否够用
ElemType *newbase = (ElemType *)realloc(p->elem, (p->size + LISTINCREMENT)*sizeof(ElemType));
if (!newbase) return -1;//存储空间分配失败
p->elem = newbase;//新基址
p->size += LISTINCREMENT;//增加存储容量
}
ElemType *elem_q = NULL;, *elem_p = NULL;;
elem_q = &(p->elem[index]); //q为插入位置
for (elem_p = &(p->elem[p->length - 1]); elem_p >= elem_q; --elem_p){ //从ai到an-1依次后移，注意后移操作要从后往前进行
*(elem_p + 1) = *elem_p;
}
*elem_q = *e;
++p->length;
return 0;
}
static int deleteElem(LinearList *This, int index, ElemType* e){
LinearList_P *p = This->This;
if (index<1 || index > p->length) return -1;
ElemType *elem_q = NULL;, *elem_p = NULL;;
elem_p = &(p->elem[index]);//elem_p为被删除元素的位置
*e = *elem_p; //被删除的元素赋值给e
elem_q = p->elem + p->length - 1;//elem_q指向表尾最后一个元素
for (++elem_p; elem_p <= elem_q; ++elem_p){ //从elem_p的下一个元素开始依次前移
*(elem_p - 1) = *elem_p;
}
--p->length;
return 0;
}
static int appendElem(LinearList *This,ElemType* e){
LinearList_P *p = This->This;
if (p->length >= p->size){ //判断存储空间是否够用
ElemType *newbase = (ElemType *)realloc(p->elem, (p->size + LISTINCREMENT)*sizeof(ElemType));
if (!newbase) return -1;//存储空间分配失败
p->elem = newbase;//新基址
p->size += LISTINCREMENT;//增加存储容量
}
p->elem[p->length] = *e;
++p->length;
return 0;
}
static int popElem(LinearList *This, ElemType* e){
LinearList_P *p = This->This;
if (isEmpty(This)) return -1;
*e = p->elem[p->length - 1];
--p->length;
return 0;
}
LinearList.h文件：
/* Define to prevent recursive inclusion -------------------------------------*/
#ifndef __LINEAR_LIST_H
#define __LINEAR_LIST_H
/* Includes ------------------------------------------------------------------*/
/* Exported types ------------------------------------------------------------*/
typedef int ElemType; //数据元素的类型，假设是int型的
typedef struct LinearList_P{
ElemType *elem; //存储空间的基地址
int length; //当前线性表的长度
int size; //当前分配的存储容量
}LinearList_P;
typedef struct LinearList{
LinearList_P *This;
void (*clear)(struct LinearList *This);
int (*isEmpty)(struct LinearList *This);
int (*length)(struct LinearList *This);
void (*print)(struct LinearList *This);
int (*indexElem)(struct LinearList *This, ElemType* x);
int (*priorElem)(struct LinearList *This, ElemType* cur_elem, ElemType* pre_elem);
int (*getElem)(struct LinearList *This, int index, ElemType* e);
int (*modifyElem)(struct LinearList *This, int index, ElemType* e);
int (*nextElem)(struct LinearList *This, ElemType* cur_elem, ElemType* next_elem);
int (*insertElem)(struct LinearList *This, int index, ElemType* e);
int (*deleteElem)(struct LinearList *This, int index, ElemType* e);
int (*appendElem)(struct LinearList *This,ElemType* e);
int (*popElem)(struct LinearList *This, ElemType* e);
}LinearList;
/* Exported define -----------------------------------------------------------*/
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量(当存储空间不够时要用到)
/* Exported macro ------------------------------------------------------------*/
LinearList *InitLinearList();
void DestroyLinearList(LinearList *L);
#endif
测试文件 testLinearList.c
#include <stdio.h>
#include <malloc.h>
#include "LinearList.h"
int main(void)
{
int i;
ElemType elem,elem1;
LinearList *list = InitLinearList();
printf("list is empty:%d\n",list->isEmpty(list));
for (i = 0; i < 10; i++){
list->appendElem(list,&i);
}
list->print(list);
printf("list is empty:%d\n",list->isEmpty(list));
printf("list length:%d\n",list->length(list));
list->clear(list);
for (i = 10; i < 20; i++){
list->appendElem(list,&i);
}
list->print(list);
elem = 17;
printf("the index of 17 is %d\n",list->indexElem(list,&elem));
list->priorElem(list,&elem,&elem1);
printf("the prior elem of 17 is %d\n",elem1);
list->nextElem(list,&elem,&elem1);
printf("the next elem of 17 is %d\n",elem1);
list->getElem(list,3,&elem1);
printf("the elem of index 3 is %d\n",elem1);
list->modifyElem(list,3,&elem);
list->getElem(list,3,&elem1);
printf("modify the elem of index 3 to %d\n",elem1);
list->print(list);
elem = 25;
list->insertElem(list,5,&elem);
printf("insert elem %d to index 5\n",elem);
list->deleteElem(list,7,&elem);
printf("delete elem %d of index 7\n",elem);
list->print(list);
list->popElem(list,&elem);
printf("pop elem %d\n",elem);
list->print(list);
DestroyLinearList(list);
return 0;
}
编译：
gcc LinearList.c LinearList.h testLinearList.c -o testLinearList
运行testLinearList
输出：
list is empty:1
0 1 2 3 4 5 6 7 8 9
list is empty:0
list length:10
10 11 12 13 14 15 16 17 18 19
the index of 17 is 7
the prior elem of 17 is 16
the next elem of 17 is 18
the elem of index 3 is 13
modify the elem of index 3 to 17
10 11 12 17 14 15 16 17 18 19
insert elem 25 to index 5
delete elem 16 of index 7
10 11 12 17 14 25 15 17 18 19
pop elem 19
10 11 12 17 14 25 15 17 18
网友评论