【数据结构】线性表的知识点全面总结

目录

1.线性表的顺序表示

    1.1顺序表的基本概念 

    1.2顺序表的基本操作 

         1.2.1插入

         1.2.2删除

         1.2.3查找 

2.线性表的链式表示

    2.1单链表

         单链表的基本概念

         2.1.1基本操作

               2.1.1.1单链表的建立

               2.1.1.2插入

               2.1.1.3删除

               2.1.1.4查找 

    2.2双链表

         2.2.1基本操作

               2.2.1.1插入

               2.2.1.2删除

               2.2.1.3遍历

    2.3循环链表

         2.3.1循环单链表

         2.3.2循环双链表 

               2.3.2.1循环双链表的插入

               2.3.2.2循环双链表的删除 

3.静态链表

4.顺序表和链表的比较 

---

1.线性表的顺序表示

1.1顺序表的基本概念 

存储结构：逻辑上相邻的数据元素物理上也相邻。

实现方式分为：静态分配和动态分配

静态分配：使用静态数组实现，大小一旦确定无法改变。

动态分配：使用动态数组实现，顺序表存满时可以用malloc动态扩展顺序表的最大容量，需要将数据元素复制到新的存储区域，并用free函数释放原区域。

1.2顺序表的基本操作 

1.2.1插入

最好时间复杂度：O(1)

最坏时间复杂度：O(n)

平均时间复杂度：O(n)

//插入
bool ListInsert(SqList &L,int i,int e)
{
	if (i < 1 || i > L.length + 1)         //判断i是否合法
		return false;
	if (L.length >= MaxSize)             //判断是否存满
		return false;
	for (int j = L.length;j >= i;j--)//插入结点的位置之后的元素依次后移
		L.data[j] = L.data[j - 1];
	L.data[i - 1] = e;                     //插入e
	L.length++;               //顺序表长度加一
	return true;
}

1.2.2删除

最好时间复杂度：O(1)

最坏时间复杂度：O(n)

平均时间复杂度：O(n)

//删除
bool ListDelete(SqList& L, int i, int e)
{
	if (i < 1 || i > L.length + 1)//判断i是否合法
		return false;
	e = L.data[i - 1];        //将删除结点位置的元素值赋给e
	for (int j = i;j < L.length;j++)//删除结点后面的元素依次前移
		L.data[j - i] = L.data[j];
	L.length--;              //顺序表长度减一
	return true;
}

1.2.3查找 

查找方式有按位查找和按值查找。

按位查找

//按位查找
int GetElem(SqList L, int i)
{
	return L.data[i - 1];
}
 

按值查找

最好时间复杂度：O(1)

最坏时间复杂度：O(n)

平均时间复杂度：O(n)

//按值查找
int LocateElem(SqList L.int e)
{
	for (int i = 0;i<L>length;i++)
		if (L.data[i] == e)
			return i + 1;
	return 0;
}

注意：C语言中，结构体的比较不能直接用“==” 

2.线性表的链式表示

2.1单链表

单链表的基本概念 

定义：线性表的链式存储。

两种实现方式：带头结点和不带头结点。

带头结点的空表判断：L->next==NULL

不带头结点的空表判断：L==NULL

头结点和头指针的区分：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点时带头结点的链表中的第一个结点，结点内通常不存储信息。

2.1.1基本操作

2.1.1.1单链表的建立

头插法

应用：链表的逆置（带头结点的单链表的就地逆置：http://t.csdn.cn/J6bph） 

// 头插法建立单链表
LinkList List_HeadInsert(LinkList &L)
{
	LNode* s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));//创建头结点
	L->next = NULL;               //初始为空链表
	scanf("%d", &x);             //输入结点的值
	while (x != 9999)          //循环结束条件，可以自己设置为其他值
	{
		s = (LNode*)malloc(sizeof(LNode));  //创建新的结点
		s->data = x;
		s->next = L->next;        
		L->next = s;          //将新结点插入表中，L为头指针
		scanf("%d", &x);
	}
	return L;
}
 

尾插法

//尾插法
LinkList List_TailInsert(LinkList& L)
{
	int x;
	L = (LinkList)malloc(sizeof(LNode));//创建头结点
	LNode* s, * r = L;      //r为表尾指针
	scanf("%d", &x);
	while (x != 9999)
	{
		s = (LNode*)malloc(sizeof(LNode));  //创建新的结点
		s->data = x;
		r->next = s;                 
		r = s;                      //r指向新的表尾结点
		scanf("%d", &x);
	}
	r->next = NULL;
	return L;
}

2.1.1.2插入

后插 

//插入（后插）
s->next = p->next;
p->next = s;
 

前插

//插入（前插）
s->next = p->next;
p->next = s;
temp = p->data;    //交换数据域（偷天换日）
p->data = s->data;
s->data = temp;

2.1.1.3删除

按位序删除

p = GetElem(L, i - 1);  //查找删除位置的前驱节点
q = p->next;            //令q指向被删除结点
p->next = q->next;      //将*q结点从链中断开
free(q);                //释放结点的存储空间

指定结点删除

如果指定结点是最后一个结点时，需要特殊处理

q = p->next;            //令q指向*p的后继结点
p->data = p->next->data; //用后继结点的数据域覆盖
p->next = q->next;       //将*q结点从链中断开
free(q);                 //释放结点的存储空间

2.1.1.4查找 

 按位查找，按值查找，求单链表的长度

2.2双链表

2.2.1基本操作

2.2.1.1插入

1.s->next = p->next;
2.if(p->next!=NULL)
	p->next->prior = s;
3.s->next = p;
4.p->next = s;

上述代码的语句顺序不是唯一，但是1和2必须在4之前，否则会出现断链。 

2.2.1.2删除

//删除双链表结点*p的后继结点*q
bool DeleteNextNode(DNode* p)
{
	if (p == NULL)
		return false;
	DNode* q = p->next;//找到p的后继结点q
	if (q == NULL)      //p没有后继
		return false;
	p->next = q->next;
	if(q->next!=NULL)   //q不是最后一个结点
		q->next->prior = p;
	free(q);
	return true;
}

2.2.1.3遍历

后向遍历

//后向遍历
while (p != NULL)
{
	p = p->next;
}

前向遍历 

//前向遍历
while (p != NULL)
{
	p = p->prior;
}
//前向遍历（跳过头结点）
while (p->prior != NULL)
{
	p = p->prior;
}

2.3循环链表

2.3.1循环单链表

表尾结点的next指针指向头结点 

2.3.2循环双链表 

 表尾结点的next指针指向头结点 ；

 表头结点的prior指针指向表尾结点

2.3.2.1循环双链表的插入

//循环双链表的插入
/ bool InsertNextDNode(DNode * p, DNode * s)
{
	s->next = p->next;
	p->next->prior = s;
	s->prior = p;
	p->next = s;
}

2.3.2.2循环双链表的删除 

//循环双链表的删除 
p->next = q->next;
q->next->prior = p;
free(q);

3.静态链表

分配一整片的连续空间，容量固定不变，结束标志：next == -1

优点：增，删操作不需要大量移动元素。

缺点：不能随机存取，只能从头结点开始依次往后查找。 

4.顺序表和链表的比较