《大话数据结构》第三章线性表

灰太狼 2022-03-17 09:24 280阅读 0赞

### 《大话数据结构 》 ###

*  第三章 线性表
 *   *  算法时间复杂度
     *  线性表
     *   *  顺序线性表结点插入与删除
         *  单链表结点插入与删除
         *  单链表整表创建与删除
         *  静态链表

# 第三章 线性表 #

## 算法时间复杂度 ##

**时间复杂度**：语句的总执行次数T(n)是一个关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。时间复杂度，也就是算法的时间量度，记：T(n) = O(f(n))。这样用大写O(　)来体现算法时间复杂度记法，我们称之为大O记法。  
大O记法推导：

1.  用常数1取代运行时间中的所有加法常数。
2.  在修改后的运行次数函数中，只保留最高阶项。
3.  如果最高阶存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶。

**所谓的算法复杂度，就是找执行次数与n的关系。**

*  顺序执行结构，不管f(n)是1次 ，还是5次，把所有加法常数换成常数1，没有最高阶项，所以时间复杂度是O(1) 。
 *  线性阶：for(int i = 0; i<n ;++)\{ 执行时间复杂度是1的步骤\} , f(n) = n，因此时间复杂度是O(n)
 *  对数阶：int count = 1; while(count < n)\{ count = count\*2; \} ，需要执行次数log2n，时间复杂度是O（log2n）
 *  平方阶：嵌套两个线性阶循环，时间复杂度O（n2）

常见的时间复杂度：  
          ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70]  
常用的时间复杂度所耗费时间从小到大：  
    ![在这里插入图片描述][20190223163911829.png]

## 线性表 ##

**线性表的定义：零个或者多个数据元素的有限序列**。线性表是最简单的一种数据结构，线性表元素个数定义为线性表的长度。每次幼儿园小朋友排队出门的次序、一年的星座排列、也是线性表。

### 顺序线性表结点插入与删除 ###

分析插入和删除的时间复杂度：最好情况时，插入或者删除最后一个元素，时间复杂度是O(1)，若插入到第一个元素或者删除第一个元素，意味着要移动所有的元素向前或者向后，此时时间复杂度是O(n)。  
  **顺序线性表的数据结构**：

struct SqList{ 
    		ElemType data[MAXSIZE];
    		int length;
    	};

以下为顺序链表的插入与删除：**无论何种数据结构的删除与插入操作，首先要对传入的参数进行判断，更改的数据结构是否有意义、删除插入位置是否超出范围，特别要注意的是移动过程中不能使用超出数据结构最大范围的值，否则会出现异常**。

#include<stdio.h>
    	#define MAXSIZE 20      /*存储空间初始分配量*/
    	typedef int ElemType;   /*ElemType类型根据实际情况而定，这里假定为int*/
    	//线性表顺序存储结构 
    	typedef struct
    	{ 
    		ElemType data[MAXSIZE]; //数组存储元素最大值为MAXSIZE 
    		int length;				//线性表当前长度 
    	}SqList; 
    	
    	#define OK 1
    	#define ERROR 0
    	#define TRUE 1
    	#define FALSE 0
    	typedef int Status;          //Status描述方法运行的状态 OK ERROR
    	/* SqList L:需要从L线性表中获取 int i:第i个元素 ElemType *e: 最终结果保存在*e中 */
    	Status GetElem(SqList L,int i,ElemType *e)
    	{ 
    		//无论什么方法先判断传进来的参数是否有效
    		 
    		if(L.length == 0 || i>L.length||i < 1)
    		{ 
    			return ERROR;
    		}
    		*e = L.data[i - 1];
    		return OK;
    	}
    	/* SqList L :需要向L线性表中插入 int i:在第i个位置 ElemType e: 插入的元素是e 初始条件： 1<= i <= L.length */
    	Status ListInsert(SqList *L,int i,ElemType e)
    	{ 
    		int k;
    		//插入时判断线性表是否已满、插入的位置是否在范围内 
    		if(L->length == MAXSIZE)
    		{ 
    			return ERROR;
    		} 
    		if(i < 1 || i > L->length+1)
    		{ 
    			return ERROR;
    		}
    		//若不初始化线性表第一个元素直接插入第一个位置会有问题 
    		if(i <= L->length)
    		{ 
    			for(k = L->length -1; k >= i -1; k--)
    			L->data[k+1] = L->data[k];
    		}
    		L->data[i - 1] = e;
    		L->length ++;
    		return OK;
    	}
    	 /* SqList *L :需要在L线性表中删除 int i:第i个位置的元素 ElemType *e: 并用e返回其删除的值 初始条件： 1<= i <= L.length */
    	Status ListDelete(SqList *L ,int i,ElemType *e) 
    	{ 
    		int k;
    		//判断线性表是否为空 删除的位置是否超出范围
    		if(L->length == 0)
    			return ERROR;
    	    if(i<1 || i> L->length) 
    	    	return ERROR;
    	   	*e = L->data[i - 1];
    	   	if(i < L->length)
    	   	{ 
    	   		//从要删除的位置依次移位到线性表最大值
    	   		for(k = i; k < L->length ;k ++)
    			{ 
    				L->data[k-1] = L->data[k]; 
    			}	
    		}
    		L->length -- ;
    		return OK;
    	}
    	int main()
    	{ 
    		int first ;
    		SqList shunxuLinearTable ;
    		shunxuLinearTable.length = 1;
    		shunxuLinearTable.data[0] = 1;
    		//测试线性表插入功能 
    		if(ListInsert(&shunxuLinearTable,1,2) == ERROR) printf("insert error");
    		if(ListInsert(&shunxuLinearTable,1,3) == ERROR) printf("insert error");
    		//测试线性表读取 
    		if(GetElem(shunxuLinearTable,1,&first) == ERROR) printf("get error");
    		
    		printf("hello\n");
    		printf("first is :%d\n",first);
    		ListDelete(&shunxuLinearTable,1,&first);
    		printf("删除的first is:%d\n",first);
    		if(GetElem(shunxuLinearTable,1,&first) == ERROR) printf("get error");
    		printf("删除后的first is :%d\n",first);
    		return 0;
    	}

运行结果：  
      ![在这里插入图片描述][20190224111924941.png]

### 单链表结点插入与删除 ###

为解决顺序存储结构，插入和删除需要移动大量元素缺点，改用链式存储线性表。链式存储线性表(也称单链表)数据结构：

typedef struct Node{ 
    		ElemType data;
    		struct Node *next;//注意结构体可以自引用结构体指针 ，不能struct Node next 
    	}Node;
    	typedef struct Node *LinkList;

获得链式存储线性表第i个数据算法思路：

*  1、声明一个节点p指向链表的第一个结点，初始化j从1开始
 *  2、当j<i时就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
 *  3、若链表末尾p为空，则说明第i个元素不存在
 *  4、若查找成功，则返回节点p的数据

单链表第i个数据插入节点算法思路：

*  1、声明一个节点指向第一个节点，初始化j从1开始
 *  2、当j<i时就遍历链表，让p的指针向后移动，不断指向下一个节点，j累加1
 *  3、若链表末尾p为空，则说明第i个元素不存在
 *  4、若查找成功，在系统中生成一个空节点s
 *  5、**将数据元素e赋值给s->data**
 *  6、**单链表的插入语句s->next = p->next; p->next = s**  
    **注意：s->next = p->next; p->next两条语句顺序不可变**，否则导致插入的s最终的next是自己，没有了上级。自己手写时，需要先画出p 、p->next、插入的结点s之间的关系图。  
           ![在这里插入图片描述][20190224161841520.png]  
    单链表第i个数据删除结点的算法思路：  
    1、声明一个结点p指向链表第一个结点，初始化j从1开始  
    2、当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加  
    3、若到链表末尾p为空，则说明第i个元素不存在  
    4、**若查找成功，将于删除的结点p->next赋值给q**  
    5、**单链表的删除标准语句p->next = q->next**  
    6、将q结点的数据赋值给e，作为返回  
    7、**释放q结点内存**  
    手写前先画出p 要删除的q节点之间的关系。  
          ![在这里插入图片描述][20190224162049929.png]  
      由于单链表的结构没有定义表长，所以不知道事先要循环多少次，只能尝试先循环将指针移到插入或者删除的位置，然后判断此时的结点是否有意义，有意义进行插入或者删除。

#include<stdio.h>
    	#include<stdlib.h>
    	#define OK 1
    	#define ERROR 0
    	typedef int Status;          //Status描述方法运行的状态 OK ERROR
    	typedef int ElemType;
    	typedef struct Node 
    	{ 
    		int data;
    		struct Node *next;
    	}Node;
    	typedef struct Node *LinkList;
    	
    	/* LinkList L:需要从L线性表中获取 int i:第i个元素 ElemType *e: 最终结果保存在*e中 */
    	Status GetElem(LinkList L,int i,ElemType *e)
    	{ 
    		//因为不知道链式存储链表的长度所以第i个元素是否存在一下子不能判断 
    		 if( !L ) return ERROR; 
    		 
    		 int j = 1;
    		 LinkList p = L; //传入的链表头就当第一个结点 
    	  	 while( p && j < i)
    	  	 { 
    	  	 	p = p->next;
    	  	 	j++;
    	     }
    	     if(!p || j>i)
    	     { 
    	     	return ERROR;
    	     }
    	     *e = p->data;
    		 return OK; 
    	}
    	/* LinkList L :需要向L线性表中插入 int i:在第i个位置 1<= i <= 单链表的长度 当链表一个元素也没有时也不能插入第一个位置 ElemType e: 插入的元素是e */
    	Status ListInsert(LinkList L,int i,ElemType e)
    	{ 
    		//插入时判断线性表是否已满、插入的位置是否在范围内
    		//由于是单链表，长度没有固定，单链表长度不确定，只能先判断传入的参数是否有意义 
    		if(!L ) return ERROR;
    		int j = 1;
    		LinkList p,s;
    		p = L;
    		while( p && j<i)
    		{ 
    			p = p->next;
    			j++;	
    		}
    		if(!p ||j>i) //若第i个元素不存在 ，若插入的范围超出链表长度返回ERROR 
    	    { 
    	 		return ERROR; 	
    	 	}
    	 	s = (LinkList) malloc(sizeof(Node));//malloc函数内存中找片空地，生成一个新节点 
    	 	s->data = e;
    	 	s->next = p->next;
    	 	p->next = s;
    		return OK;
    	}
    	 /* LinkList L:需要在L线性表中删除 int i:第i个位置的元素 ElemType *e: 并用e返回其删除的值 初始条件： 1<= i <= L.length */
    	Status ListDelete(LinkList L ,int i,ElemType *e) 
    	{ 
    		int j = 1;
    		LinkList p,q;
    		p = L;
    		while(p -> next &&j < i)
    		{ 
    			p = p->next;
    			j++;
    		}
    		if(!p || j>i)
    		{ 
    			return ERROR;
    		}
    		q = p->next;
    		p->next = q->next;
    		*e = q->data;
    		free(q);
    		return OK;
    	}
    	int main()
    	{ 
    			int first ;
    			LinkList linkLinearTable = (LinkList)malloc(sizeof(Node)) ;
    			linkLinearTable ->data = 1;
    			linkLinearTable ->next = NULL;
    			if(ListInsert(linkLinearTable,1,2) == ERROR) printf("insert error\n");
    			if(ListInsert(linkLinearTable,1,3) == ERROR) printf("insert error\n");
    			if(ListInsert(linkLinearTable,4,4) == ERROR) printf("insert error\n");
    			if(GetElem(linkLinearTable,1,&first) == ERROR) printf("get error");
    			printf("first element is :%d\n",first);
    			//测试删除结点
    			if(ListDelete(linkLinearTable,1,&first)  == ERROR) printf("delete error\n");
    			printf("delete element is :%d\n",first);
    			if(GetElem(linkLinearTable,1,&first) == ERROR) printf("get error");
    			printf("after delete first is :%d\n",first);
    			if(ListDelete(linkLinearTable,1,&first)  == ERROR) printf("delete error\n");
    			printf("delete element is :%d\n",first);
    			if(GetElem(linkLinearTable,1,&first) == ERROR) printf("get error\n");
    			printf("after delete first is :%d\n",first);	
    			return 0;
    	}

运行结果：  
      ![在这里插入图片描述][20190224153602647.png]

### 单链表整表创建与删除 ###

单链表整表创建的算法思路（头插法）：

*  1、声明一结点p和计数器变量i
 *  2、初始化一空链表L
 *  3、让L的头结点指针指向NULL
 *  4、**循环(生成一新结点赋值给p ，随机生成一个数值赋值给p->data，将p插入头结点和前一新结点直接)**  
    头插法新建链表LinkList L关键在于：始终让L处于头结点，每次循环新增的一个结点处于第二个结点。

头插法新建的单链表：第一个头结点是传入的L，书中给的头插法L->data是没有赋值的，L头结点是没有值的 .

/* 头插法：随机产生n个元素的值的单链表L 头插法新建的单链表：第一个头结点是传入的L，此处提供的头插法L->data是没有赋值 */
    	void CreateListHead(LinkList L,int n)
    	{ 
    		LinkList p;
    		int i;
    		srand(time(0));
    /// L = (LinkList) malloc(sizeof(Node));
    		L->next = NULL;
    		for(i = 0; i<n; i++)
    		{ 
    			p = (LinkList)malloc(sizeof(Node));
    			p->data = rand()%100+1; //A=rand()%x+y;产生一个以y为下限，以x+y为上限的随机数，并把值赋给A。
    			p->next = L->next;   //每次循环新创建的结点都是此次循环的第二个结点 
    			L->next = p;  //每次循环结束 都让L作为单链表的头结点 
    		} 
    	}

尾插法新建链表LinkList L关键在于：先让L赋值给r，然后始终让r处于尾结点，每次循环新增的结点处于倒数第二个。L是尾插法的链表头结点指针，在理解r->next = p; r = p; 中可能会有点问题，要将r想象成只是充当中介的作用，r如果最后不等于p，那么 下一轮循环中如何让这个p接着指向下一个新建的p。以第一次执行r->next = p; r = p; 为例，第一次执行r = L，ai-1的地址是L，r->next = p后，L指向p。r = p后，r的表示的是p的地址，而ai-1到a之间的引用关系已经完成，r就是充当完成ai-1到a引用关系的中介。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 1]

/* 尾插法：尾插法 关键在于将L赋值给r，而r始终充当链表的尾结点作用 */
    	void CreateListTail(LinkList L,int n)
    	{ 
    		LinkList p,r;
    		int i;
    		srand(time(0));
    		r = L;
    		for(i = 0; i<n; i++)
    		{ 
    			p  = (LinkList)malloc(sizeof(Node));
    			p->data = rand()%100 +1;
    			r->next = p;  //将新创建的结点作为倒数第二个结点 
    			r = p; 		  //r始终是要作为最后一个结点 
    		}
    		r->next = NULL; 
    	}

单链表整表删除的算法思路：

*  1、声明结点p和q
 *  2、将第一个结点赋值给p
 *  3、**循环(将下一个结点赋值给q，释放p，将q赋值给p）**

/* 显然传入的参数要为链表的头结点 */
    	Status ClearList(LinkList L)
    	{ 
    		LinkList p,q;
    		p = L->next;
    		while(p)
    		{ 
    			q = p->next;
    			free(p);
    			p = q;
    		}
    		L->next = NULL;
    		return OK;
    	}

测试代码：

int main()
    	{ 
    			int first ;
    			LinkList linkLinearTable = (LinkList)malloc(sizeof(Node)) ;
    			linkLinearTable ->data = 1;
    			linkLinearTable ->next = NULL;
    			if(ListInsert(linkLinearTable,1,2) == ERROR) printf("insert error\n");
    			if(ListInsert(linkLinearTable,1,3) == ERROR) printf("insert error\n");
    			if(ListInsert(linkLinearTable,4,4) == ERROR) printf("insert error\n");
    			if(GetElem(linkLinearTable,1,&first) == ERROR) printf("get error");
    			printf("first element is :%d\n",first);
    			//测试删除结点
    			if(ListDelete(linkLinearTable,1,&first)  == ERROR) printf("delete error\n");
    			printf("delete element is :%d\n",first);
    			if(GetElem(linkLinearTable,1,&first) == ERROR) printf("get error");
    			printf("after delete first is :%d\n",first);
    			if(ListDelete(linkLinearTable,1,&first)  == ERROR) printf("delete error\n");
    			printf("delete element is :%d\n",first);
    			if(GetElem(linkLinearTable,1,&first) == ERROR) printf("get error\n");
    			printf("after delete first is :%d\n",first);
    			//测试单链表头插法新增，头插法无法读取头结点的值 
    			int second;
    			LinkList  headLinkList =(LinkList) malloc(sizeof(Node));
    		 	CreateListHead(headLinkList,10);
    			if(GetElem(headLinkList,2,&second) == ERROR) printf("get headLinkList 单链表 error\n");
    			printf("头插法得到的单链表 second is :%d\n",second);
    			//测试单链表尾插法新增------尾插法读起来有些困难
    			//测试删除头插法创建的链表
    			 ClearList(headLinkList);
    			if(GetElem(headLinkList,2,&second) == ERROR) printf("get删除后 headLinkList 单链表 fail\n");
    			//测试尾插法 
    		 	LinkList  tailLinkList = (LinkList)malloc(sizeof(Node));   // CreateListTail会给tailLinkList分配内存所以不用自己分配 
    			 CreateListTail(tailLinkList,10);
    			if(GetElem(tailLinkList,2,&second) == ERROR) printf("get tailLinkList 单链表 error\n");
    			printf("尾插法得到的单链表 second is :%d\n",second);
    			//测试单链表尾插法新增------尾插法读起来有些困难
    			//测试删除尾插法创建的链表
    			 ClearList(tailLinkList);
    			if(GetElem(tailLinkList,2,&second) == ERROR) printf("get删除后 tailLinkList 单链表 fail\n");	  
    			return 0;
    	}

运行结果：  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 2]  
单链表和顺序存储线性表优缺点：

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>空间性能</th> 
   <th>空间性能</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>单链表</td> 
   <td>插入和删除时间复杂度O(1)</td> 
   <td>不需要分配存储空间，元素个数不受限制</td> 
  </tr> 
  <tr> 
   <td>顺序存储线性表</td> 
   <td>顺序存储链表时间复杂度最多可以达到O(N)</td> 
   <td>需要预分配存储空间，分大了浪费，分小了容易溢出</td> 
  </tr> 
 </tbody> 
</table>

### 静态链表 ###

在动态链表中，结点的申请和释放借用malloc()和free()两个函数。单链表创建时无论是头插法还是尾插法，个人感觉使用起来都有问题。而**静态链表操作的是数组，需要手动模拟动态链表的存储结构申请malloc和释放free函数**。  
静态链表的数据结构：

#define MAXSIZE 1000 //假设链表最大长度1000
    typedef struct
    { 
    	ElemType data;
    	int cur; //游标 为0时表示无指向 
    } Component,StaticLinkList[MAXSIZE];

静态链表也要初始大小，为了方便插入不溢出，暂定链表最大长度为1000，StaticLinkList\[MAXSIZE\]数组的第一个元素StaticLinkList\[0\]的cur用于存放备用剩余链表结点的第一个结点的下标。存放的第一个位置数据是存放在StaticLinkList\[1\]中的。  
    ![在这里插入图片描述][20190224214151827.png]  
模拟malloc和free函数，需要不断改动StaticLinkList\[0\]中的cur。下面例子中，一开始插入了甲乙丁戊已庚，想在第三个位置插入丙，则Malloc\_SSL开辟出的第一个空节点游标是7，space\[7\]存放丙，需要更改乙的游标指向7，丙的游标指向丁。

#include<stdio.h>
    	#define MAXSIZE 1000 //假设链表最大长度1000
    	typedef char * ElemType;	
    	#define OK 1
    	#define ERROR 0
    	#define TRUE 1
    	#define FALSE 0
    	typedef int Status;          //Status描述方法运行的状态 OK ERROR
    	typedef struct
    	{ 
    		ElemType data;
    		int cur; //游标 为0时表示无指向 
    	} Component,StaticLinkList[MAXSIZE];
    	//初始化静态链表为空，最后一个元素的cur为0 
    	Status InitList(StaticLinkList space)
    	{ 
    		int i;
    		for(i = 0;i<MAXSIZE -1 ;i++)
    		{ 
    			space[i].cur = i+1;
    		}
    		space[MAXSIZE - 1].cur = 0;
    	}
    	//需要手动模拟malloc和free函数
    	int Malloc_SSL(StaticLinkList space) 
    	{ 
    		int i = space[0].cur;  //space[0]存放一个备用的空闲的下标 
    		if(space[0].cur)
    			space[0].cur = space[i].cur;//空闲的备用下标被使用后，把它的下一个作为备用 
    		return i;
    	}
    	void Free_SSL(StaticLinkList space,int k)
    	{ 
    		space[k].cur = space[0].cur; //将空闲的备用下标存放在要删除的结点中 
    		space[0].cur = k;			 //将要删除的下标作为space[0]首选备用的下标 
    	}
    	//返回静态链表L中的数据元素个数
    	int ListLength(StaticLinkList L)
    	{ 
    		int j = 0;
    		int i = L[MAXSIZE -1].cur; //最后一个元素指向的下一个的下标 
    		while(i)
    		{ 
    			i = L[i].cur;
    			j++;
    		}
    		return j;
    	}
    	//获得静态链表第I个元素 
    	ElemType getElement(StaticLinkList L,int i)
    	{ 
    		int k = MAXSIZE - 1;
    		int j ;
    		if(i <1 || i>ListLength(L))
    			return ERROR;
    		for(j = 0; j<i; j++)
    			k = L[k].cur;
    		return L[k].data;	
    	} 
    	Status ListInsert(StaticLinkList L,int i,ElemType e)
    	{ 
    		int j,k,l;
    		k = MAXSIZE - 1;
    		//判断插入的元素是否超出范围，静态链表可以知道链表的元素个数 
    		if(i<1 || i>ListLength(L)+1)
    			return ERROR;
    		j = Malloc_SSL(L);   //获得空闲分量的下标
    		if(j)
    		{ 
    			L[j].data = e;  //找个空着的结点存放要插入的元素 ，而不是用malloc分配内存开辟 
    			for(l = 1; l<= i-1;l++)//遍历要插入的位置是放在哪个结点的游标中，每次从MAXSIZE-1开始遍历 
    			{ 
    				k = L[k].cur;
    			}
    			L[j].cur = L[k].cur;
    			L[k].cur = j;
    			return OK;
    		} 
    		return ERROR;
    	}
    	//默认space[0]为第一个结点位置，i为插入的位置 
    	Status ListDelete(StaticLinkList L,int i)
    	{ 
    		int j,k;
    		if(i <1 ||i >ListLength(L))
    			return ERROR;
    		k = MAXSIZE - 1;  //最后一个地方存放着首结点的下标 
    		for(j = 1;j<i - 1;j++)//先找到要删除的位置前后的游标 
    		{ 
    			k = L[k].cur;
    		}
    		j = L[k].cur;
    		L[k].cur = L[j].cur;
    		Free_SSL(L,j);//释放要删除的位置 结点 
    		return OK; 
    		
    	} 
    	int main()
    	{ 
    		StaticLinkList staticLinkList;
    		InitList(staticLinkList);
    		ListInsert(staticLinkList,1,"甲");
    		ListInsert(staticLinkList,2,"乙");
    		ListInsert(staticLinkList,3,"丁");
    		ListInsert(staticLinkList,4,"戊");
    		ListInsert(staticLinkList,5,"已");
    		ListInsert(staticLinkList,6,"庚");
    		printf("第一个位置值：%s\n",getElement(staticLinkList,1));
    		printf("第三个位置值：%s\n",getElement(staticLinkList,1));
    		printf("第六个位置值：%s\n",getElement(staticLinkList,6));
    		if(	ListInsert(staticLinkList,3,"丙") == ERROR) printf("插入丙失败"); 
    		printf("插入后第三个位置值：%s\n",staticLinkList[3].data);
    		printf("插入后第六个位置值：%s\n",getElement(staticLinkList,6));
    		printf("插入后第七个位置值：%s\n",getElement(staticLinkList,7));
    		//测试删除函数
    		ListDelete(staticLinkList,6); 
    	    printf("删除原本第六个位置后，新的第六个位置值：%s\n",getElement(staticLinkList,6));
    		return 0;
    	}

运行结果：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 3]  
  静态链表在插入和删除操作，只需要修改游标，不要移动元素，但是还是需要遍历知道插入位置的游标在哪个结点上，夸大的说是在插入和删除时改进了移动了大量元素缺点，但是还是没有解决连续存储带来的表长问题，但是肯定是比连续线性表好用的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70]: /images/20220317/d9c586d655784d239d3f055315b7d5ad.png
[20190223163911829.png]: /images/20220317/7d407a5fd2684878963620266c653344.png
[20190224111924941.png]: /images/20220317/97a12892361d458faf70264067409895.png
[20190224161841520.png]: /images/20220317/6726d5ad7a384da8a1051f98dbc4fec2.png
[20190224162049929.png]: /images/20220317/05122a87e5944090b990b6ac1967af49.png
[20190224153602647.png]: /images/20220317/041aafc36e8c470a96c57848e0c38e47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 1]: /images/20220317/c76d860c0f6e4fb1869c959cf8d990b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 2]: /images/20220317/f4432ece7feb4ad69cfbcc695d2c03fc.png
[20190224214151827.png]: /images/20220317/6866e1aad5b64ed2901b4accbbed3226.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 3]: /images/20220317/71e15c5741354764b015fb30ae74e0e4.png