(一)数据结构之线性表的简单实现：链表

阳光穿透心脏的1/2处 2022-06-08 06:13 160阅读 0赞

## 1、线性表的定义 ##

线性表（Linear List）：由同类型的数据元素构成的有序序列的线性结构：表中元素个数称为线性表的长度，线性表没有元素时，称为空表，表起始位置称表头，表结束位置称为表尾。

## 2、链表的顺序存储的实现 ##

### 2.1 数据结构表示 ###

利用数组的连续存储空间顺序存放线性表的各元素。首先定义链表的基本数据结构如下所示：

/* 定义List的基本结构 */	
    #define MAXSIZE 	10			// 链表的长度
    typedef int ElementType;
    typedef struct _List{
    	ElementType Data[MAXSIZE];		
    	int Last;	// 链表中最后一个元素的下标
    } List;

### 2.2 创建一个空链表 ###

/* 初始化一个链表，即构造一个空表 */
    List *MakeEmpty( )
    { 
    	List *PtrL;
    	PtrL = (List *)malloc( sizeof(List) );
    	PtrL->Last = -1;
    	return PtrL;
    }

### 2.3 插入操作 ###

/*	插入操作:在第i个位置上插入一个元素X	*/
    void Insert( ElementType X, int i, List *PtrL )
    { 
    	int j = 0;
    	if ( PtrL->Last == MAXSIZE-1 )
    	{ 
    		/* 表空间已满，不能插入*/
    		printf("Table is full!\n");
    		return;
    	}
    	if ( i < 1 || i > PtrL->Last+2) 
    	{ 
    		/*检查插入位置的合法性*/
    		printf("The position of insert is illegal!\n");
    		return;
    	}
    	for ( j = PtrL->Last; j >= i-1; j-- )
    		PtrL->Data[j+1] = PtrL->Data[j]; 	/*将 ai～an倒序向后移动*/
    	PtrL->Data[i-1] = X; 					/*新元素插入*/
    	PtrL->Last++; 							/*Last仍指向最后元素*/
    	return;
    }

### 2.4 删除操作 ###

/* 删除表第i个元素 */
    void Delete( int i, List *PtrL )
    { 
    	int j = 0;
    	if( i < 1 || i > PtrL->Last+1 ) 
    	{ 
    		/*检查空表及删除位置的合法性*/
    		printf ("The position of delete is illegal!\n");
    		return ;
    	}
    	for ( j = i; j <= PtrL->Last; j++ )
    		PtrL->Data[j-1] = PtrL->Data[j]; 	/*将 ai+1～ an顺序向前移动*/
    	PtrL->Last--; 							/*Last仍指向最后元素*/
    	return;
    }

### 2.5 查找操作 ###

/**	查找:按指定元素来查找
      *		X 要查找的元素值
      *		PtrL 要查找的链表的头结点指针
      *		返回值 对应元素的下标
      */
    int Find( ElementType X, List *PtrL )
    { 
    	int i = 0;
    	while( i <= PtrL->Last && PtrL->Data[i]!= X )
    		i++;
    	if (i > PtrL->Last) return -1; /* 如果没找到，返回-1 */
    	else return i; /* 找到后返回的是存储位置 */
    }

### 2.6 修改操作 ###

/* 修改元素值 */
    void Change( ElementType X, int i, List *PtrL)
    {
    	if ( i < 1 || i > PtrL->Last+1) 
    	{ 
    		/*检查插入位置的合法性*/
    		printf("The position of change is illegal!\n");
    		return;
    	}
    	PtrL->Data[i - 1] = X;	/* 对要修改的元素进行赋值 */
    }

### 2.7 完整的示例代码 ###

/**	线性表的顺序存储
      *		Date : 2017-09-10
      */
    #include <stdio.h>
    #include <stdlib.h>
    
    /* 定义List的基本结构 */	
    #define MAXSIZE 	10			// 链表的长度
    typedef int ElementType;
    typedef struct _List{
    	ElementType Data[MAXSIZE];		
    	int Last;	// 链表中最后一个元素的下标
    } List;
    
    /* 初始化一个链表，即构造一个空表 */
    List *MakeEmpty( )
    { 
    	List *PtrL;
    	PtrL = (List *)malloc( sizeof(List) );
    	PtrL->Last = -1;
    	return PtrL;
    }
    
    /* 销毁一个链表，释放内存空间 */
    void MakeDestroy(List *PtrL)
    {
    	if(PtrL != NULL) free(PtrL);
    	PtrL = NULL;
    }
    
    /**	查找:按指定元素来查找
      *		X 要查找的元素值
      *		PtrL 要查找的链表的头结点指针
      *		返回值 对应元素的下标
      */
    int Find( ElementType X, List *PtrL )
    { 
    	int i = 0;
    	while( i <= PtrL->Last && PtrL->Data[i]!= X )
    		i++;
    	if (i > PtrL->Last) return -1; /* 如果没找到，返回-1 */
    	else return i; /* 找到后返回的是存储位置 */
    }
    
    /*	插入操作:在第i个位置上插入一个元素X	*/
    void Insert( ElementType X, int i, List *PtrL )
    { 
    	int j = 0;
    	if ( PtrL->Last == MAXSIZE-1 )
    	{ 
    		/* 表空间已满，不能插入*/
    		printf("Table is full!\n");
    		return;
    	}
    	if ( i < 1 || i > PtrL->Last+2) 
    	{ 
    		/*检查插入位置的合法性*/
    		printf("The position of insert is illegal!\n");
    		return;
    	}
    	for ( j = PtrL->Last; j >= i-1; j-- )
    		PtrL->Data[j+1] = PtrL->Data[j]; 	/*将 ai～an倒序向后移动*/
    	PtrL->Data[i-1] = X; 					/*新元素插入*/
    	PtrL->Last++; 							/*Last仍指向最后元素*/
    	return;
    }
    
    /* 删除表第i个元素 */
    void Delete( int i, List *PtrL )
    { 
    	int j = 0;
    	if( i < 1 || i > PtrL->Last+1 ) 
    	{ 
    		/*检查空表及删除位置的合法性*/
    		printf ("The position of delete is illegal!\n");
    		return ;
    	}
    	for ( j = i; j <= PtrL->Last; j++ )
    		PtrL->Data[j-1] = PtrL->Data[j]; 	/*将 ai+1～ an顺序向前移动*/
    	PtrL->Last--; 							/*Last仍指向最后元素*/
    	return;
    }
    
    /* 修改元素值 */
    void Change( ElementType X, int i, List *PtrL)
    {
    	if ( i < 1 || i > PtrL->Last+1) 
    	{ 
    		/*检查插入位置的合法性*/
    		printf("The position of change is illegal!\n");
    		return;
    	}
    	PtrL->Data[i - 1] = X;	/* 对要修改的元素进行赋值 */
    }
    
    /* 遍历这个链表中的元素 */
    void Traversal(List *PtrL)
    {
    	int i = 0;
    	if((PtrL == NULL) || (PtrL->Last < 0))
    	{
    		printf("List is illegal!\n");
    		return ;
    	}
    	for(i = 0; i <= PtrL->Last; i++)
    		printf("%d ", PtrL->Data[i]);
    	printf("\n");
    }
    
    /* 返回线性表的长度 */
    int Length(List *PtrL)
    {
    	if(PtrL == NULL)
    	{
    		printf("List is illegal!\n");
    		return -1;
    	}
    	return PtrL->Last + 1;
    }
    
    /* 程序入口 */
    int main()
    {
    	int i, index;
    	ElementType temp;
    	List *list;
    
    	list = MakeEmpty();	/* 创建一个链表 */
    
    	/* 向链表中插入五个元素 */
    	printf("Input 5 numbers : ");
    	for(i = 0; i < 5; i++)
    	{
    		scanf("%d", &temp);
    		Insert(temp, i+1, list);		// 注意这里要插入的是第i个元素，而数组的下标是从零开始的，所以要加一
    	}
    
    	printf("************************************Traversal*****************************\n");
    	/* 打印链表中的元素 */
    	Traversal(list);
    	printf("Length = %d\n", Length(list));
    
    	printf("************************************Delete********************************\n");
    	/* 删除一个元素 */
    	Delete(3, list);
    	Traversal(list);	
    	printf("Length = %d\n", Length(list));
    
    	printf("************************************Insert********************************\n");
    	/* 插入一个元素 */
    	Insert(100, 2, list);
    	Traversal(list);	
    	printf("Length = %d\n", Length(list));
    
    	printf("************************************Change********************************\n");
    	/* 插入一个元素 */
    	Change(888, 1, list);
    	Traversal(list);	
    	printf("Length = %d\n", Length(list));
    
    	printf("************************************Find*********************************\n");
    	/* 查找一个元素 */
    	index = Find(100, list);
    	Traversal(list);	
    	printf("Length = %d, Index = %d\n", Length(list), index);
    
    	MakeDestroy(list);		/* 销毁这个链表 */
    	
    	return 0;
    }

## 3、链表的链式存储的实现 ##

不要求逻辑上相邻的两个元素物理上也相邻；通过链建立起数据元素之间的逻辑关系；插入、删除不需要移动数据元素，只需要修改链。

### 3.1 基本数据结构 ###

/* 基本数据结构定义 */
    typedef int ElementType;
    typedef struct Node{
    	ElementType Data;
    	struct Node *Next;
    } List;

### 3.2 插入操作 ###

通过插入操作就可以创建一个链式链表，所以不需要单独为其创建一个头结点。

/* 在第i个结点位置上插入一个新结点 */
    List *Insert( ElementType X, int i, List *PtrL )
    { 
    	List *p, *s;
    	if ( i == 1 ) 
    	{ 
    		/* 新结点插入在表头 */
    		s = (List *)malloc(sizeof(List)); /*申请、填装结点*/
    		s->Data = X;
    		s->Next = PtrL;
    		return s; /*返回新表头指针*/
    	}
    	p = FindKth( i-1, PtrL ); /* 查找第i-1个结点 */
    	if ( p == NULL ) 
    	{ 
    		/* 第i-1个不存在，不能插入 */
    		printf("the node of i-1 is not exist!\n");
    		return NULL;
    	}
    	else 
    	{
    		s = (List *)malloc(sizeof(List)); /*申请、填装结点*/
    		s->Data = X;
    		s->Next = p->Next; /*新结点插入在第i-1个结点的后面*/
    		p->Next = s;
    		return PtrL;
    	}
    }

### 3.3 删除操作 ###

/* 删除第i个结点 */
    List *Delete( int i, List *PtrL )
    { 
    	List *p, *s;
    	if ( i == 1 ) 
    	{ 
    		/* 若要删除的是表的第一个结点 */
    		s = PtrL; 								/*s指向第1个结点*/
    		if (PtrL!=NULL) PtrL = PtrL->Next; 		/*从链表中删除*/
    		else return NULL;
    		free(s); 								/*释放被删除结点 */
    		return PtrL;
    	}
    	p = FindKth( i-1, PtrL ); /*查找第i-1个结点*/
    	if ( p == NULL ) 
    	{
    		printf("the node of i-1 is not exist!\n"); return NULL;
    	} 
    	else if ( p->Next == NULL )
    	{
    		printf("the node of i is not exist!\n"); return NULL;
    	} 
    	else 
    	{
    		s = p->Next; 		/*s指向第i个结点*/
    		p->Next = s->Next; 	/*从链表中删除*/
    		free(s); 			/*释放被删除结点 */
    		return PtrL;
    	}
    }

### 3.4 查找操作 ###

查找操作实现了两种：一种是按照元素值查找，还有一种是按照存在链表中的位置来查找具体实现如下：

按元素值来查找：

/* 查找链表中值为X的元素 */
    List *Find( ElementType X, List *PtrL )
    {
    	List *p = PtrL;
    	while ( p!=NULL && p->Data != X )
    		p = p->Next;
    	return p;
    }

按位置来查找：

/* 查找链表中第K个元素 */
    List *FindKth( int K, List *PtrL )
    { 
    	List *p = PtrL;
    	int i = 1;
    	while (p != NULL && i < K )
    	{
    		p = p->Next;
    		i++;
    	}
    	if ( i == K ) return p;	/* 找到第K个，返回指针 */
    	else return NULL;		/* 否则返回空 */
    }

### 3.5 修改操作 ###

/* 修改元素值 */
    void Change( ElementType X, int i, List *PtrL)
    {
    	List *p;
    	p = FindKth( i, PtrL ); /* 查找第i个结点 */
    	if ( p == NULL ) 
    	{ 
    		/* 第i-1个不存在，不能插入 */
    		printf("the node of i-1 is not exist!\n");
    		return ;
    	}
    	else
    	{
    		p->Data = X;
    	}
    }

### 3.6 完整的示例代码实现 ###

/* 线性表的链式存储 */
    #include <stdio.h>
    #include <stdlib.h>
    
    /* 基本数据结构定义 */
    typedef int ElementType;
    typedef struct Node{
    	ElementType Data;
    	struct Node *Next;
    } List;
    
    /* 销毁一个链表，释放内存空间 */
    void MakeDestroy(List *PtrL)
    {
    	List *PtrTemp = PtrL;
    	List *PtrNext;
    	while(PtrTemp)
    	{
    		PtrNext = PtrTemp->Next;
    		free(PtrTemp);
    		PtrTemp = PtrNext;
    	}
    }
    
    /* 查找链表中第K个元素 */
    List *FindKth( int K, List *PtrL )
    { 
    	List *p = PtrL;
    	int i = 1;
    	while (p != NULL && i < K )
    	{
    		p = p->Next;
    		i++;
    	}
    	if ( i == K ) return p;	/* 找到第K个，返回指针 */
    	else return NULL;		/* 否则返回空 */
    }
    
    /* 查找链表中值为X的元素 */
    List *Find( ElementType X, List *PtrL )
    {
    	List *p = PtrL;
    	while ( p!=NULL && p->Data != X )
    		p = p->Next;
    	return p;
    }
    
    /* 在第i个结点位置上插入一个新结点 */
    List *Insert( ElementType X, int i, List *PtrL )
    { 
    	List *p, *s;
    	if ( i == 1 ) 
    	{ 
    		/* 新结点插入在表头 */
    		s = (List *)malloc(sizeof(List)); /*申请、填装结点*/
    		s->Data = X;
    		s->Next = PtrL;
    		return s; /*返回新表头指针*/
    	}
    	p = FindKth( i-1, PtrL ); /* 查找第i-1个结点 */
    	if ( p == NULL ) 
    	{ 
    		/* 第i-1个不存在，不能插入 */
    		printf("the node of i-1 is not exist!\n");
    		return NULL;
    	}
    	else 
    	{
    		s = (List *)malloc(sizeof(List)); /*申请、填装结点*/
    		s->Data = X;
    		s->Next = p->Next; /*新结点插入在第i-1个结点的后面*/
    		p->Next = s;
    		return PtrL;
    	}
    }
    
    /* 删除第i个结点 */
    List *Delete( int i, List *PtrL )
    { 
    	List *p, *s;
    	if ( i == 1 ) 
    	{ 
    		/* 若要删除的是表的第一个结点 */
    		s = PtrL; 								/*s指向第1个结点*/
    		if (PtrL!=NULL) PtrL = PtrL->Next; 		/*从链表中删除*/
    		else return NULL;
    		free(s); 								/*释放被删除结点 */
    		return PtrL;
    	}
    	p = FindKth( i-1, PtrL ); /*查找第i-1个结点*/
    	if ( p == NULL ) 
    	{
    		printf("the node of i-1 is not exist!\n"); return NULL;
    	} 
    	else if ( p->Next == NULL )
    	{
    		printf("the node of i is not exist!\n"); return NULL;
    	} 
    	else 
    	{
    		s = p->Next; 		/*s指向第i个结点*/
    		p->Next = s->Next; 	/*从链表中删除*/
    		free(s); 			/*释放被删除结点 */
    		return PtrL;
    	}
    }
    
    /* 修改元素值 */
    void Change( ElementType X, int i, List *PtrL)
    {
    	List *p;
    	p = FindKth( i, PtrL ); /* 查找第i个结点 */
    	if ( p == NULL ) 
    	{ 
    		/* 第i-1个不存在，不能插入 */
    		printf("the node of i-1 is not exist!\n");
    		return ;
    	}
    	else
    	{
    		p->Data = X;
    	}
    }
    
    /* 遍历这个链表中的元素 */
    void Traversal(List *PtrL)
    {
    	List *p;
    	p = PtrL;
    	while(p)
    	{
    		printf("%d ", p->Data);
    		p = p->Next;
    	}
    }
    
    
    /* 求表长 */
    int Length ( List *PtrL )
    { 
    	List *p = PtrL; /* p指向表的第一个结点*/
    	int j = 0;
    	while ( p ) 
    	{
    		p = p->Next;
    		j++; 		/* 当前p指向的是第 j 个结点*/
    	}
    	return j;
    }
    
    
    /* 程序入口 */
    int main()
    {
    	int i, index;
    	ElementType temp;
    	List *node;
    	List *list = NULL;		/* 防止野指针 */
    	
    	/* 向链表中插入五个元素 */
    	printf("Input 5 numbers : ");
    	for(i = 0; i < 5; i++)
    	{
    		scanf("%d", &temp);
    		list = Insert(temp, i + 1, list);
    	}
    
    	printf("************************************Traversal*****************************\n");
    	/* 打印链表中的元素 */
    	Traversal(list);
    	printf("Length = %d\n", Length(list));
    
    	printf("************************************Delete********************************\n");
    	/* 删除一个元素 */
    	list = Delete(3, list);
    	Traversal(list);	
    	printf("Length = %d\n", Length(list));
    
    	printf("************************************Insert********************************\n");
    	/* 插入一个元素 */
    	Insert(100, 2, list);
    	Traversal(list);	
    	printf("Length = %d\n", Length(list));
    
    	printf("************************************Change********************************\n");
    	/* 插入一个元素 */
    	Change(888, 1, list);
    	Traversal(list);	
    	printf("Length = %d\n", Length(list));
    
    	printf("************************************Find**********************************\n");
    	/* 查找一个元素 */
    	node = Find(100, list);
    	Traversal(list);	
    	printf("Length = %d, Value = %d\n", Length(list), node->Data);
    
    	MakeDestroy(list);		/* 销毁这个链表 */
    	
    	return 0;	
    }