线性表-SqList

数据结构线性表-SqList 参考书：《数据结构（C语言）》作者：严蔚敏

如果发现错误，请帮忙指正，谢谢。

转载请注明@author vaneng

SqList.h:

/*@author vaneng
 *数组下标从0元素开始
 *指针定义格式：类型名 *类型名缩写+"_ptr"
 *struct名首字母大写
 *函数名首字母小写
 *函数指针写具体的函数名，便于对照
 *带下标的变量从0开始写
 *第几个都是从1开始，即：不存在第0个
 */
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct {
	ElemType *e_ptr;
	int length;
	int listsize;
}SqList;
SqList *initList();					//构造一个空的线性表
void destroyList(SqList *l_ptr);	//销毁线性表
void clearList(SqList *l_ptr);		//将线性表置为空
int listEmpty(SqList list);			//判断是否为空表
int listLength(SqList list);		//线性表长度
void getElem(SqList list, int i, ElemType *e_ptr);	//得到第i个元素存储到e
ElemType *locateElem(SqList list, ElemType e, int (*compare)(ElemType e0, ElemType e1));					//将第一个值为e的指针返回
void priorElem(SqList list, ElemType cur_e, ElemType *pre_e_ptr, int (*compare)(ElemType e1, ElemType e2));	//cur_e的前一个元素赋值到pre_e_ptr
void nextElem(SqList list, ElemType cur_e, ElemType *next_e_ptr, int (*compare)(ElemType e1, ElemType e2));	//cur_e的后一个元素赋值到next_e_ptr
void listInsertLast(SqList *l_ptr, ElemType e);				//从最后一个位置插入e
void listInsert(SqList *l_ptr, int i, ElemType e);			//将e插入到第i个位置
void listDelete(SqList *l_ptr, int i, ElemType *e_ptr);		//将第i个删除，结果放到e_ptr
void listTraverse(SqList list, void (*visit)(ElemType e));	//遍历list

void error(char *name, char *msg);		//显示错误信息msg为function名
int resize(SqList *l_ptr);	//realloc

SqList.c

/*@author vaneng*/
#include "SqList.h"
#include <malloc.h>
SqList *initList(){
	SqList *l_ptr = (SqList *)malloc(sizeof(SqList));
	l_ptr->length = 0;
	l_ptr->listsize = LIST_INIT_SIZE;
	l_ptr->e_ptr = (ElemType *)malloc(l_ptr->listsize*sizeof(ElemType));
	if(!l_ptr->e_ptr){
		error("initList","Malloc failed");
		return 0;
	}
	return l_ptr;
}
void destroyList(SqList *l_ptr){
	/*destroy之后程序应该把l_ptr=0*/
	if(l_ptr){
		free(l_ptr->e_ptr);
		l_ptr->e_ptr = 0;
		free(l_ptr);
	}else{
		error("destroyList", 
			"l_ptr is null");
	}
}
void clearList(SqList *l_ptr){
	/*我觉得这样就可以了，
	*initList是建造一个空表
	*clearlist是将有东西的表设为一个空表
	*/
	if(l_ptr){
		l_ptr->length=0;
	}else{
		error("clearList", "l_ptr is null");
	}
}
int listEmpty(SqList list){
	return list.length;
}
int listLength(SqList list){
	return list.length;
}
void getElem(SqList list, int i, ElemType *e_ptr){
	/*测试 0<i<=length
	这个地方应该是针对e的地址的一个赋值，直接
	将e = list->e_ptr+i 没有意义
	*/
	if(i<=0||i>list.length){
		error("getElem","i is larg or small");
	}else
		*e_ptr=*(list.e_ptr+i-1);
}
ElemType *locateElem(SqList list, ElemType e, int (*compare)(ElemType e1, ElemType e2)){
	ElemType *e_ptr = list.e_ptr;
	int i = 0;
	while(i++<list.length&&!compare(*(e_ptr++),e));
	if(i==list.length)
		return 0;
	else
		return e_ptr-1;
}
void priorElem(SqList list, ElemType cur_e, ElemType *pre_e_ptr, int (*compare)(ElemType e1, ElemType e2)){
	ElemType *e_ptr = locateElem(list, cur_e, compare);
	if(e_ptr == list.e_ptr || !e_ptr){
		error("priorElem", "Current element is the first element or it is not exist");
		*pre_e_ptr = 0;
	}else{
		*pre_e_ptr = *(--e_ptr);
	}
}
void nextElem(SqList list, ElemType cur_e, ElemType *next_e_ptr, int (*compare)(ElemType e1, ElemType e2)){
	ElemType *e_ptr = locateElem(list, cur_e, compare);
	if(e_ptr == list.e_ptr+list.length-1){
		error("nextElem", "There is no element after the current element");
	}else{
		*next_e_ptr = *(++e_ptr);
	}
}
void listInsertLast(SqList *l_ptr, ElemType e){
	int flag = 1;
	if(l_ptr->length == l_ptr->listsize){
		flag = resize(l_ptr);
	}
	if(flag){
		*(l_ptr->e_ptr+l_ptr->length)=e;
		l_ptr->length++;
	}else{
		error("listInsertLast", "InsertLast failed");
	}
}
void listInsert(SqList *l_ptr, int i, ElemType e){
	ElemType *flag_ptr = l_ptr->e_ptr+i-1;
	ElemType *cursor_ptr;
	int flag = 1;
	if(i<=0 ||i >l_ptr->length+1){
		/*i可以比length大1
		此刻相当于listInsertLast*/
		error("listInsert", "i is out of the array bound");
		return;
	}
	if(l_ptr->length == l_ptr->listsize && resize(l_ptr)){
		return;
	}
	for(cursor_ptr = l_ptr->e_ptr + l_ptr->length; cursor_ptr>flag_ptr;cursor_ptr--)
		/*    *cursor_ptr = *(--cursor_ptr)
		不要这么写，等式左右两边不知道先计算哪个
		*/
		*cursor_ptr = *(cursor_ptr-1);
	*cursor_ptr = e;
	l_ptr->length++;
}
void listDelete(SqList *l_ptr, int i, ElemType *e_ptr){
	ElemType *cursor_ptr;
	if(i<1 ||i >l_ptr->length){
		error("listDelete", "i is out of the array bound");
		return;
	}
	*e_ptr = *(l_ptr->e_ptr+i-1);
	for(cursor_ptr = l_ptr->e_ptr +i-1; cursor_ptr < l_ptr->e_ptr + l_ptr->length - 1;cursor_ptr++)
		/**cursor_ptr = *(++cursor_ptr)
		不要这么写，等式左右两边不知道先计算哪个
		*/
		*cursor_ptr = *(cursor_ptr+1);
	l_ptr->length--;
}
void listTraverse(SqList list, void (*visit)(ElemType e)){
	ElemType *e_ptr;
	for(e_ptr = list.e_ptr; e_ptr<list.e_ptr+list.length; e_ptr++){
		(*visit)(*e_ptr);
	}
	if(!list.length)
		printf("There is 0 element in the SqList!");
	printf("\n");
}

void error(char *name, char *msg){
	printf("-----Errors occured in \"%s\"!-----\n", name);
	printf("  %s!\n",msg);
	printf("\n");
}
int resize(SqList *l_ptr){
	l_ptr->e_ptr = (ElemType *)realloc(l_ptr->e_ptr, (l_ptr->listsize + LISTINCREMENT)*sizeof(ElemType));
	l_ptr->listsize += LISTINCREMENT;
	if(!l_ptr->e_ptr){
		l_ptr->listsize-=LISTINCREMENT;
		error("resize", "Realloc failed");
		return 0;
	}
	return 1;
}

test.c

#include "SqList.h"
#include <stdio.h>

void visit(ElemType e);
int compare(ElemType e1, ElemType e2);

int main(){
	SqList *list = initList();
	int i;
	printf("链表是否为空，%d\n", listEmpty(*list));
	for(i = 0 ; i < 10; i++){
		listInsertLast(list, i+1);
	}
	printf("链表长度 %d \n", listLength(*list));
	listTraverse(*list, visit);

	listInsert(list, 5, 50);
	listTraverse(*list, visit);
	
	getElem(*list, 5, &i);
	printf("getElem5: %d\n",i);

	priorElem(*list, 50, &i,compare);
	printf("priorElem50: %d\n",i);

	nextElem(*list, 50, &i, compare);
	printf("nextElem50: %d\n",i);

	listDelete(list, 5, &i);
	listTraverse(*list, visit);

	printf("%d\n", i);
	getElem(*list, 15, &i);
	printf("%d\n", i);

	clearList(list);
	listTraverse(*list, visit);

	destroyList(list);
	list = 0;
}

void visit(ElemType e){
	printf("%4d", e);
}
int compare(ElemType e1, ElemType e2){
	return e1==e2?1:0;
}