数据结构与算法（007）：线性表-单链表和静态链表

比眉伴天荒 2022-02-03 23:23 244阅读 0赞

# 静态链表 #

这一节课，我们试图通过静态链表的讲解来瞻仰古人的伟大！

神马是静态链表呢？又跟古人能有半毛钱关系？

地球人都知道C语言是个伟大的语言，他的魅力在于指针的灵活性，使得它可以非常容易地操作内存中的地址和数据，这比其他高级语言更加灵活方便。（面向对象使用对象引用机制间接地实现了指针的某些功能）

但是古人还木有C语言，木有JAVA，只有原始的Basic，Fortran等早期的编程语言，这些语言没有类似于C的指针功能，但是他们又想描述单链表，就没法实现了，怎么办呢？

真是不得不佩服他们的智慧，有人想出了用数组代替指针来描述单链表。大家能猜一猜他们是如何做到的么？

在讲解原理之前，先让大家知道这种用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法。

**线性表的静态链表存储结构**

#define MAXSIZE 1000
    
    typedef struct
    
    {
    
        ElemType data;  // 数据
    
        int cur;        // 游标（Cursor）
    
    } Component, StaticLinkList[MAXSIZE];

对静态链表进行初始化相当于初始化数组：

Status InitList(StaticLinkList space)
 {
 int i;
 for( i=0; i < MAXSIZE-1; i++ )
 space[i].cur = i + 1;
 
 space[MAXSIZE-1].cur = 0;
 
 return OK;
 }

备忘录：

我们对数组的第一个和最后一个元素做特殊处理，他们的data不存放数据。

我们通常把未使用的数组元素称为备用链表。

数组的第一个元素，即下标为0的那个元素的cur就存放备用链表的第一个结点的下标。

数组的最后一个元素，即下标为MAXSIZE-1的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用。

## 静态链表的插入操作 ##

有些喜欢思考的同学可能就会说，你这不是挂羊头买鱼肉吗？还是数组丫，貌似没看出太多单链表的端倪~\_~

那我们接着从行为学的角度来剖析下，静态链表如何模拟单链表进行插入和删除的操作呢？

现在我们来看看如何实现元素的插入。静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间分配，也就是需要的时候申请，不需要的时候释放。

我们前面说过，在动态链表中，结点的申请和释放分别借用C语言的malloc()和free()两个函数来实现。

在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放的问题，所以我们需要自己实现这两个函数，才可以做到插入和删除操作。

为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的用游标链成一个备用链表，应该如何操作呢？请大家课后头脑风暴一下！

上节课我们说到，为了辨明数组中哪些分量未被使用，解决的方法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表。

每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。可能这样说大家都还是难以理解吧？我们结合图片来讲解，这里我们假设要在A后边插入B：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTU2MzE4_size_16_color_FFFFFF_t_70][]

那我们来谈谈代码，代码由两部分组成：

首先是获得空闲分量的下标：

int Malloc_SLL(StaticLinkList space)
    {
        int i = space[0].cur;
        if( space[0].cur )
            space[0].cur = space[i].cur;
           // 把它的下一个分量用来作为备用。
        return i;
    }

插入操作的实现代码如下：ListInsert.c

/* 在静态链表L中第i个元素之前插入新的数据元素e */
 
 Status ListInsert( StaticLinkList L, int i, ElemType e )
 {
 int j, k, l;
 
 k = MAX_SIZE - 1; // 数组的最后一个元素
 if( i<1 || i>ListLength(L)+1 )
 {
 return ERROR;
 }
 
 j = Malloc_SLL(L);
 if( j )
 {
 L[j].data = e;
 for( l=1; l <= i-1; l++ )
 {
 k = L[k].cur;
 }
 L[j].cur = L[k].cur;
 L[k].cur = j;
 
 return OK;
 }
 
 return ERROR;
 }

## 静态链表的删除操作 ##

我们的故事还没结束，小C看到小A和2B这样非法的勾当，内心觉得很不爽，一句话也不说就离开了队伍。。。。。。

我们先在图上实践一下，然后研究代码：

代码：ListDelete.c

/* 删除在L中的第i个数据元素 */
 Status ListDelete(StaticLinkList L, int i)
 {
 int j, k;
 
 if( i<1 || i>ListLength(L) )
 {
 return ERROR;
 }
 
 k = MAX_SIZE - 1;
 
 for( j=1; j <= i-1; j++ )
 {
 k = L[k].cur; // k1 = 1, k2 = 5
 }
 
 j = L[k].cur; // j = 2
 L[k].cur = L[j].cur;
 
 Free_SLL(L, j);
 
 return OK;
 }
 
 /* 将下标为k的空闲结点回收到备用链表 */
 void Free_SLL(StaticLinkList space, int k)
 {
 space[k].cur = space[0].cur;
 space[0].cur = k;
 }
 
 /* 返回L中数据元素个数 */
 int ListLength(StaticLinkList L)
 {
 int j = 0;
 int i = L[MAXSIZE-1].cur;
 
 while(i)
 {
 i = L[i].cur;
 j++;
 }
 
 return j;
 }

## 静态链表优缺点总结 ##

**优点：**

在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。

**缺点：**

没有解决连续存储分配（数组）带来的表长难以确定的问题。

失去了顺序存储结构随机存取的特性。

总的来说，静态链表其实是为了给没有指针的编程语言设计的一种实现单链表功能的方法。

尽管我们可以用单链表就不用静态链表了，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需。

## 单链表小结腾讯面试题 ##

**题目：快速找到未知长度单链表的中间节点。**

既然是面试题就一定有普通方法和高级方法，而高级方法无疑会让面试官大大加分！

**普通的方法**很简单，首先遍历一遍单链表以确定单链表的长度L。然后再次从头节点出发循环L/2次找到单链表的中间节点。

算法复杂度为：O(L+L/2)=O(3L/2)。

能否再优化一下这个时间复杂度呢？

**有一个很巧妙的方法：利用快慢指针！**

利用快慢指针原理：设置两个指针\*search、\*mid都指向单链表的头节点。其中\* search的移动速度是\*mid的2倍。当\*search指向末尾节点的时候，mid正好就在中间了。这也是标尺的思想。

我们来看下代码实现：GetMidNode.c

Status GetMidNode(LinkList L, ElemType *e)
    {
        LinkList search, mid;
        mid = search = L;
    
        while (search->next != NULL)
        {
            //search移动的速度是 mid 的2倍
            if (search->next->next != NULL)
            {
                search = search->next->next;
                mid = mid->next;
            }
            else
            {
                search = search->next;
            }
        }
    
        *e = mid->data;
    
        return OK;
    }

课后作业：写一个完整的程序，实现随机生成20个元素的链表（尾插法或头插法任意），用我们刚才学到的方法快速查找中间结点的值并显示。

程序演示：GetMidNode2.exe

#include "stdio.h"
 
 #define OK 1
 #define ERROR 0
 #define TRUE 1
 #define FALSE 0
 
 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
 typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
 
 typedef struct Node
 {
 	ElemType data;
 	struct Node *next;
 }Node;
 
 typedef struct Node *LinkList; /* 定义LinkList */
 
 Status visit(ElemType c)
 {
 	printf("%d ", c);
 	return OK;
 }
 
 /* 初始化顺序线性表 */
 Status InitList(LinkList *L)
 {
 	*L = (LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
 
 	if (!(*L)) /* 存储分配失败 */
 	{
 		return ERROR;
 	}
 
 	(*L)->next = NULL; /* 指针域为空 */
 
 	return OK;
 }
 
 /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
 int ListLength(LinkList L)
 {
 	int i = 0;
 	LinkList p = L->next; /* p指向第一个结点 */
 
 	while (p)
 	{
 		i++;
 		p = p->next;
 	}
 
 	return i;
 }
 
 /* 初始条件：顺序线性表L已存在 */
 /* 操作结果：依次对L的每个数据元素输出 */
 Status ListTraverse(LinkList L)
 {
 	LinkList p = L->next;
 
 	while (p)
 	{
 		visit(p->data);
 		p = p->next;
 	}
 
 	printf("\n");
 
 	return OK;
 }
 
 /* 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
 void CreateListTail(LinkList *L, int n)
 {
 	LinkList p, r;
 	int i;
 
 	srand(time(0)); /* 初始化随机数种子 */
 	*L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
 	r = *L; /* r为指向尾部的结点 */
 
 	for (i = 0; i < n; i++)
 	{
 		p = (Node *)malloc(sizeof(Node)); /* 生成新结点 */
 		p->data = rand() % 100 + 1; /* 随机生成100以内的数字 */
 		r->next = p; /* 将表尾终端结点的指针指向新结点 */
 		r = p; /* 将当前的新结点定义为表尾终端结点 */
 	}
 
 	r->next = NULL; /* 表示当前链表结束 */
 	// 创建有环链表
 	//r->next = p;
 }
 
 Status GetMidNode(LinkList L, ElemType *e)
 {
 	LinkList search, mid;
 	mid = search = L;
 
 	while (search->next != NULL)
 	{
 		//search移动的速度是 mid 的2倍
 		if (search->next->next != NULL)
 		{
 			search = search->next->next;
 			mid = mid->next;
 		}
 		else
 		{
 			search = search->next;
 		}
 	}
 
 	*e = mid->data;
 
 	return OK;
 }
 
 int main()
 {
 	LinkList L;
 	Status i;
 	char opp='1';
 	ElemType e;
 	int find;
 	int tmp;
 
 	i = InitList(&L);
 	printf("初始化L后：ListLength(L)=%d\n", ListLength(L));
 
 	printf("\n1.查看链表 \n2.创建链表（尾插法） \n3.链表长度 \n4.中间结点值 \n0.退出 \n请选择你的操作：\n");
 	while (opp != '0')
 	{
 		scanf_s("%c", &opp);
 		switch (opp)
 		{
 		case '1':
 			ListTraverse(L);
 			printf("\n");
 			break;
 
 		case '2':
 			CreateListTail(&L, 20);
 			printf("整体创建L的元素(尾插法)：\n");
 			ListTraverse(L);
 			printf("\n");
 			break;
 
 		case '3':
 			//clearList(pHead); //清空链表
 			printf("ListLength(L)=%d \n", ListLength(L));
 			printf("\n");
 			break;
 
 		case '4':
 			//GetNthNodeFromBack(L,find,&e);
 			GetMidNode(L, &e);
 			printf("链表中间结点的值为：%d\n", e);
 			//ListTraverse(L);
 			printf("\n");
 			break;
 
 		case '0':
 			exit(0);
 		}
 	}
 }

### ***[可下载观看 数据结构与算法动画演示，以帮助我们更好的理解和学习代码的实现过程。][Link 1]*** ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTU2MzE4_size_16_color_FFFFFF_t_70]: /images/20220204/74e9f6f9166c42d197925cd05d657da2.png
[Link 1]: https://download.csdn.net/download/qq_41556318/11162006