线性表：由 >=0 个数据元素组成的有限序列（线性表有两种存储结构：顺序存储结构和链式存储结构）
一. 顺序存储结构的线性表
-
图示：
顺序表.png
- 地址计算方法：
如：已知数组int a[n]的初始地址是location(a[0])，求第i个元素的地址location(a[i])
location(a[i]) = location(a[0]) + (i-1)
因此，顺序存储结构的线性表 查询操作的时间复杂度为 O(1)。
为了描述顺序表表，我们首先要声明一个结构，如下
/**
首先声明一个顺序表的结构
*/
#define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量
#define LISTINCREMENT 5 //线性表存储空间的分配增量(当存储空间不够时要用到)
typedef int ElemType; //数据元素的类型，假设是int型的
typedef struct{
ElemType *elem; //存储空间的基地址
int length; //当前线性表的长度
int listsize; //当前分配的存储容量
}SqList;
1.创建线性表
/**
创建线性表
*/
int InitList(SqList *L)
{
L->elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//开辟一个存储空间，并把这块存储空间的基地址赋值给elem
if (L->elem == NULL)
{
return -1;//空间分配失败
}
L->length = 0;//线性表的当前长度
L->listsize = LIST_INIT_SIZE;//当前分配量
return 0;
}
2.1查找元素（按位置 or 地址查找），时间复杂度为O(1)。
/**
查找元素（按位置 or 地址查找），时间复杂度为O(1)
查找第i个元素，存储在e中
成功为0，失败为-1
*/
int GetElem(SqList *L, int i, ElemType *e)
{
#if 0 //按位置查找
//判断查找的合法性
if (i<1 || i>L->length)
{
return -1;
}
*e = L->elem[i-1];
return 0;
#endif
//按地址查找
//判断查找的合法性
if (i<1 || i>L->length)
{
return -1;
}
*e = *(L->elem+(i-1));
return 0;
}
2.2查找元素（按值查找），时间复杂度为O(n)。
/**
查找元素（按值查找），时间复杂度为O(n)
返回元素的坐标
*/
int LocateElem(SqList *L, ElemType x)
{
int pos = -1;
for (int i = 0; i < L->length; i++)
{
if (L->elem[i] == x)
{
pos = i;
}
}
return pos;
}
3.插入元素，时间复杂度为O(n)。
/**
插入元素，时间复杂度为O(n)
返回该坐标的元素
*/
int ListInsert(SqList *L, int i, ElemType e)
{
//判断插入位置的合法性
if (i<1 || i>L->length+1) return -1;
//判断存储空间是否够用
if (L->length >= L->listsize)
{
ElemType *newbase = (ElemType *)realloc(L->elem, (L->listsize + LISTINCREMENT)*sizeof(ElemType));
if (!newbase) return -1;//存储空间分配失败
L->elem = newbase;//新基址
L->listsize += LISTINCREMENT;//增加存储容量
}
//插入操作
ElemType *q, *p; //定义2个指针变量
q = &(L->elem[i-1]); //q为插入位置(注意形参i是序号，序号是从从1开始的，而下标是从0开始的，因此这里转成下标后是i-1)
for (p = &(L->elem[L->length - 1]); p >= q; --p) //从ai到an-1依次后移，注意后移操作要从后往前进行
{
*(p + 1) = *p;
}
*q = e;
++L->length;//表长加1
return 0;
}
4.删除元素，时间复杂度为O(n)。
/**
删除元素，时间复杂度为O(n)
删除第i个元素，并将删除的元素保存在e中
*/
int ListDelete(SqList *L, int i, ElemType *e)
{
//判断删除位置是否越界
if (i<1 || i>L->length)
{
return -1;
}
ElemType *p = &(L->elem[i]);//将p指向i位置的元素
*e = *p;//将p指向i位置的元素保存在e中
ElemType *q = &(L->elem[L->length-1]);//将q指向最后的元素
for (; p <= q; p++)
{
*p = *(p+1);//将顺序表中的元素依次平移一个位置
}
return 0;
}
5.清空顺序表
/**
清空顺序表
*/
int ListClean(SqList *L)
{
L->length = 0;//把当前线性表的长度设置为0，表示清空
return 0;
}
测试代码如下：
int main(int argc, const char * argv[]) {
SqList *l = (SqList *)malloc(sizeof(SqList));
//创建顺序表
InitList(l);
//从第1个元素开始，先顺序插入10个元素
for (int i=1; i<11; i++)
{
ListInsert(l, i, 11-i);
}
//输出线性表
for (int i = 0; i < 10; i++)
{
printf("%d ", l->elem[i]);
}
printf("\n");
//在坐标为3的位置插入元素
int status = ListInsert(l, 3, 99);
//输出线性表
for (int i = 0; i < l->length; i++)
{
printf("%d ", l->elem[i]);
}
printf("\n");
//在顺序表中查找元素为7的坐标
int pos = LocateElem(l, 7);
printf("l->elem[%d] = %d", pos, l->elem[pos]);
//删除第5个元素，并且删除的元素保存在e中
ElemType e = 0;
ListDelete(l, 5, &e);
printf("\n");
//输出线性表
for (int i = 0; i < l->length; i++)
{
printf("%d ", l->elem[i]);
}
printf("\n");
//查找第3个元素，并且结果保存在find_e中
ElemType find_e = 0;
GetElem(l, 3, &find_e);
printf("find_e = %d ", find_e);
printf("\n");
if (l != NULL)
{
//清空顺序表
ListClean(l);
free(l->elem);
free(l);
l = NULL;
}
return 0;
}
二. 链式存储结构的线性表
解释俩概念头指针和头节点。
头指针：指向链表的第一个节点的指针，若链表有头节点，则是只想头节点的指针。头指针的变量名字常用来表识链表的名字。无论链表是否为空，头指针均不为空。（是链表的必要元素）
头节点：头节点是为了从左统一和方便而设立的，放在第一个元素的节点之前，其数据域一般无意义（但也可以用来存放链表的长度）。
单链表
单链表、空链表图例：
单链表.png
为了描述单链表，我们首先要声明一个结构，如下
/**
首先声明一个单链表的结构
*/
typedef int ElemType; //数据元素的类型，假设是int型的
typedef struct{
ElemType data;//数据域
struct LNode *next;//指针域
}LNode;
typedef LNode LinkList;
1.创建单链表
头插法
/**
1.1创建链表(头插法) 时间复杂度O(n)
*/
LinkList * CreateListHead(int n)
{
LNode *L = NULL;
L = (LNode *)malloc(sizeof(LNode));
L->next = NULL;
LNode *p = NULL;//p为新结点，指向最后一个元素
for (int i=1 ; i<=n; ++i)
{
p = (LNode *)malloc(sizeof(LNode));
p->data = i;
p->next = L->next;//将p的next指向L的next
L->next = p;//将L的next指向p
}
return L;
}
尾插法
/**
1.2创建链表(尾插法) 时间复杂度O(n)
*/
LinkList * CreateListTail(int n)
{
LNode *L = NULL;
L = (LNode *)malloc(sizeof(LNode));
L->next = NULL;
LNode *r = L;
LNode *p = NULL;
for (int i=1 ; i<=n; ++i)
{
p = (LNode *)malloc(sizeof(LNode));
p->data = i;
p->next = NULL;
r->next = p;//将r的next指向p
r = p;//将r指向p的指向
}
return L;
}
2.单链表查找
/**
2.查找元素(取第i个元素) 时间复杂度O(n)
*/
int GetElemFromLinkList(LinkList *L, int i, ElemType *e)
{
LNode *node = L;//设node为第i-1个结点
while (i!=0 && node!=NULL) {
--i;
node = node->next;
}
if (i==0 && node != NULL) {
*e = node->data;
return 0;
} else {
return -1;//第i个元素不存在
}
}
3.单链表插入
/**
3.插入元素 时间复杂度为O(n)，但是频繁插入时，为O(1)
在第i个元素位置，插入数据e
*/
int LinkListInsert(LinkList *L, int i, ElemType e)
{
LNode *p = L;//设p为第i-1个结点
while(i!=0 && p!=NULL) {
--i;
p = p->next;
}
if (i==0 && p!=NULL) {
LNode *s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;//s的直接后继指向p原来的直接后继
p->next = s;//p的直接后继指向s
return 0;
} else {
return -1;
}
}
4.单链表删除
/**
4.插入元素 时间复杂度为O(n)，但是频繁删除时，为O(1)
删除第i个节点
*/
int LinkListDelete(LNode *L, int i, ElemType *e)
{
LNode *p = L;//设p为第i-1个结点
while(i!=0 && p!=NULL) {
--i;
p = p->next;
}
if (i==0 && p!=NULL) {
LNode *q = p->next;
p->next = q->next;
*e = q->data;
return 0;
} else {
return -1;
}
}
5.清空单链表
/**
5.清空单链表 时间复杂度为O(n)
*/
int ClearLinkList(LinkList *L)
{
LNode *p, *q;
p = L->next;
while (p != NULL) {
q = p->next;
free(p);
p = q;
}
L->next = NULL;
return 0;
}
测试代码如下：
// 创建链表:头插法
LinkList *l1 = CreateListHead(10);
//输出链表中的数据
while (l1->next != NULL) {
LNode *node = l1->next;
printf("%d ", node->data);
l1 = node;
}
printf("\n");
// 创建链表:尾插法
LinkList *l2 = CreateListTail(10);
//输出链表中的数据
while (l2->next != NULL) {
LNode *node = l2->next;
printf("%d ", node->data);
l2 = node;
}
printf("\n");
// 查找第7个节点
LinkList *l3 = CreateListTail(10);
int xdata = 0;
int status = GetElemFromLinkList(l3, 7, &xdata);// 返回7
// 查找第7个节点位置插入777
status = LinkListInsert(l3, 7, 777);
GetElemFromLinkList(l3, 8, &xdata);// 返回777
// 删除第i个节点
status = LinkListDelete(l3, 4, &xdata);
// 清空单链表
status = ClearLinkList(l3);
//输出链表中的数据
while (l3->next != NULL) {
LNode *node = l3->next;
printf("%d ", node->data);
l2 = node;
}
printf("\n");
网友评论