线性表的定义
线性表(List)是零个或多个数据元素的集合
线性表中的数据元素之间是有顺序的
线性表中的数据元素个数是有限的
线性表中的数据元素的类型必须相同
线性表的性质
a0为线性表的第一个元素，只有一个后继
an为线性表的最后一个元素，只有一个前驱
除a0和an外的其它元素ai，既有前驱，又有后继
线性表能够逐项访问和顺序存取
线性表的一些常用操作
创建线性表
销毁线性表
清空线性表
将元素插入线性表
将元素从线性表中删除
获取线性表中某个位置的元素
获取线性表的长度
线性表操作的实现
线性表在程序中表现为一种特殊的数据类型，其操作在程序中的表现为一组函数
10年积累的网站建设、网站设计经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站策划后付款的网站建设流程，更有宝坻免费网站建设让你可以放心的选择与我们合作。
List* List_Create(); //创建线性表
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语言中可以用一维数组来实现顺序存储结构
存储空间的起始位置：数组node
线性表的最大容量：数组长度MAXSIZE
线性表的当前长度：length
#define MAXSIZE 20
typedef struct _tag_List
{
char node[MAXSIZE];
int length;
} List;获取元素操作
判断线性表是否合法
判断位置是否合法
直接通过数组下标的方式获取元素
char Get(List* list, int pos)
{
char ret = -1;
if((list != NULL) && (0 <= pos ) && (pos <= list->length))
{
ret = list->node[pos];
}
return ret;
}插入元素操作
判断线性表是否合法
判断插入位置是否合法
把最后一个元素到插入位置的元素后移一个位置
将新元素插入
线性表长度加1
int Insert(List* list, char c, int pos)
{
//判断线性表是否合法
int ret = (list != NULL);
int i = 0;
//判断插入位置是否合法
ret = ret && ((list->length + 1) <= MAXSIZE);
ret = ret && (0 <= pos);
if(ret)
{
if(pos >= list->length)
pos = list->length;
//从最后一个元素开始到第pos个位置，分别将他们地洞到后一个位置
for(i=list->length;i > pos; i--)
{
list->node[i] = list->node[i-1];
}
//将新元素插入
list->node[pos] = c;
//长度加1
list->length++;
}
return ret;
}删除元素操作
判断线性表是否合法
判断删除位置是否合法
将元素取出
将删除位置后的元素分别向前移动一个位置
线性表长度减1
char Delete(List* list, int pos)
{
char ret = -1;
int i = 0;
//判断线性表是否合法，判断删除位置是否合法
if((list != NULL)&&(0 <= pos)&&(pos < list-> length))
{
ret = list->node[pos];
for(int i=pos+1; i < list->length; i++)
list->node[i-1] = list->node[i];
list->length--;
}
return ret;
}链式存储定义
为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息。
链式存储逻辑结构
n个结点链接成一个链式线性表的结构叫做链表，当每个结点中只包含一个指针域时，叫做单链表。
链表的基本概念
表头结点
链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息
数据结点
链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息
尾结点
链表中的最后一个数据结点，其下一元素指针为空，表示无后继
单链表示例
在C语言中可以用结构体来定义链表中的指针域；链表中的表头结点也可以用结构体实现
//结点指针域定义
typedef struct _tag_LinkListNode{
LinkListNode* next;
} LinkListNode;
//头结点定义
typedef struct _tag_LinkList
{
LinkListNode header;
int length;
} TLinkList;
//数据元素定义
struct Value
{
LinkListNode header;
int v;
};获取第pos个元素操作
判断线性表是否合法
判断位置是否合法
由表头开始通过next指针移动pos次后，当前元素的next指针即指向要获取的元素
LinkListNode* current = (LinkListNode*) list;
for(i=0; inext;
}
ret = current->next; 插入元素操作
判断线性表是否合法
判断插入位置是否合法
由表头开始通过next指针移动pos次后，当前元素的next指针即指向要插入的位置
将新元素插入
线性表长度加1
删除元素操作
判断线性表是否合法
判断插入位置是否合法
获取第pos个元素
将第pos个元素从链表中删除
线性表长度减1
实现代码
