剑法篇
C语言-列表
线性表
- 顺序表
- 链式表
线性表的本质
定义：
由0个或多个数据元素的集合
数据元素之间是有顺序的
数据元素的个数是有限个
数据元素的类型必须相同
专业的定义：
线性表是具有相同类型的n(n>=0)个数据元素的有限序列
(a0,a1,a2,..an)
ai是表项，n是长度
性质：
a0为线性表的第一个元素，只有一个后继
an为线性表的最后一个元素，只有一个前驱
除a0和an以外的其他元素ai，既有前驱也有后继.
线性表的操作
创建
销毁
插入
删除
获得表中某个位置的元素
获得线性表的长度
清空
线性表的操作对应于我们程序中的一组函数
List *List_Create(void);
void List_Destroy(List *list);
void List_Clear(List *list);
int List_Insert(List *list, ListNode *node, int pos)
ListNode * List_Delete(List *list, int pos)
ListNode * List_Get(List *list, int pos)
int List_Length(List *list)
线性表的顺序存储结构
线性表的顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素 看成C语言的数组，用C语言的一维数组实现顺序存储结构
#define MAXSIZE 20 //线性表的最大容量
typedef struct _list {
char node[MAXSIE]; //存储空间的起始地址是node
int length; //表示线性表的当前长度
}List;
获得元素的操作
char Get(List *list, int pos) {
char ret = -1;
// 1. 判断list的合法性
// 2. 判断位置的合法性
if ( (list!=NULL) &&(0<=pos) && (pos<list->length) )
// 3. 获得元素
ret = list->node[pos];
return ret;
}
插入元素的操作
算法：
1.判断线性表的合法性
2.判断插入位置的合法性
3.把最后一个元素到插入位置的元素依次后移一个位置
4.将新元素插入
5.将长度加1
int Insert(List *list, char c, int pos) {
int ret = (list!=NULL);
int i = 0;
ret = ret && (list->length <= MAXSIZE);
ret = ret && (0<=pos);
if ( ret ) {
if ( pos > list->length)
pos = list->length;
for (i=list->length; i>pos; i--)
list->node[i] = list->node[i-1];
list->node[i] = c;
list->length++;
}
return ret;
}
删除元素操作
算法：
1.判断线性表的合法性
2.判断删除位置的合法性
3.将元素取出
4.将删除位置之后的所有元素都向前移动一个位置
5.顺序表的长度-1
har Delete(List *list, int pos) {
char ret = -1;
int i = 0;
if ( (list!=NULL)&&(0<=pos)&&(pos<list->length) ){
ret = list->node[pos];
for (i=pos+1; i<list->length; i++)
list->node[i-1] = list->node[i];
list->length--;
}
return ret;
}
优点：可以快速的获取表中合法位置的元素 缺点：插入和删除的时候需要移动大量的元素
