C语言数据结构003——线性表的链式表示

秒速五厘米 2023-10-06 18:00 140阅读 0赞

## 一、链表前导知识 ##

### 指针 ###

`指针（pointer）`：指向`物理存储单元地址`的变量，也称为链（link）或引用（reference），指针变量存放一个内存地址。  
int i, \*j;

### 指针的运算 ###

取地址运算（&）和对内容进行操作（\*）  
int a,\*pi;  
pi = &a;  
a = 5;  
\*pi = 10;

### 指针和数组 ###

数组名代表数组首地址，就是指针（常指针）  
int a\[5\] ; int \*p=a; int *p=&a\[0\];  
引用数组元素  
（1）下标法： a\[3\]=7;  
（2）指针法 ：*(a+3)=7; 或 \*(p+3)=7;

### 指向结构体的指针 ###

typedef struct Node{
        
    		int data;
    		Nodeptr link; //struct Node *link;
    }LNode;
     typedef struct Node *Nodeptr;

任何数据类型都可以定义指向它的指针

### 线性链表的特点 ###

用任意的存储单元（连续或不连续）存储线性表数据

### 单链表的存储结构 ###

(1)单链表中构成链表的结点只有一个指向直接后继结点的指针域。  
结点结构如图示：  
![在这里插入图片描述][20210622100019872.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70]

## 二、头指针、头结点和首元结点的区别 ##

![在这里插入图片描述][20210622105717404.png]  
1）`头指针`是指向链表中第一个结点（或为头结点、或为首元结点）的指针；  
2）`头结点`是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，计它不入表长度。数据域通常涂上阴影  
3）`首元结点`是指链表中存储线性表第一个数据元素a０的结点。

## 三、带头节点单链表和不带头结点单链表的比较 ##

### 1). 在带头结点单链表第一个数据元素前插入结点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 2]

### 2). 删除带头结点单链表第一个数据元素结点 ###

![在这里插入图片描述][20210622105933525.png]

### 3).在不带头结点单链表第一个数据元素前插入结点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 4]

### 4).在不带头结点单链表其他数据元素前插入结点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 5]

### 5).删除不带头结点单链表第一个数据元素结点 ###

![在这里插入图片描述][20210622110142873.png]

### 6).删除不带头结点单链表其他数据元素结点 ###

![在这里插入图片描述][20210622110159888.png]

> 1、c语言的动态申请内存空间函数：  
> 动态申请内存空间函数：  
> void\* malloc(unsigned size)  
> 2、释放动态申请的内存空间  
> void free(void \*p)  
> 3、计算任意一种数据类型占用字节个数的运算符  
> int sizeof(已定义的数据类型)

## 四、单链表集体实现代码 ##

//单链表结构体
    typedef struct Node
    {
        
      	DataType data;
      	struct Node *next;
    }SLNode;
    
    //（1）初始化
    void ListInitiate(SLNode **head)
    {
        
    	 *head = (SLNode *)malloc(sizeof(SLNode));
    	(*head)->next = NULL;				
    }
    
    //（2）求当前数据元素个
    int ListLength(SLNode *head)
    {
        
    	SLNode *p = head;           //p指向头结点
    	int size= 0;		     	//size初始化为0		
    	while(p->next != NULL)      //循环计数		
    	{
        	
    		p = p->next;
    		size ++;	
    	}
    	return size;
    } 
    
    //（3）插入ListInsert(head, i, x)
    int ListInsert(SLNode *head, int i, DataType x)
    //在带头结点的单链表head的第i（0≤i ≤ length）个结点前插入一个存放数据
    //元素x的结点。插入成功则返回1；失败则返回0
    {
        	
    	SLNode *p, *q;
    	int j;
     	p = head;	j = -1;	
    	while(p->next != NULL && j < i - 1) //最终让指针p指向第i-1个结点
    	{
        	
    		p = p->next;	
    		j++;	
    	}
    	
    	if(j != i - 1)
    	{
        	
    		printf("插入位置参数错！");	
    		return 0;   
    	} 
    	q = (SLNode *)malloc(sizeof(SLNode));
    	q->data = x;
    
     	q->next = p->next; 
    	p->next = q;	
    	return 1;
    }
    
    //（4）删除   ListDelete(head, i, x)
    int ListDelete(SLNode *head, int i, DataType *x)
    {
        	
    	SLNode *p, *s;	int j;
     	p = head;	j = -1;
    	while(p->next != NULL && p->next->next!= NULL && j < i - 1) 
    	{
        	p = p->next;	
    		j++;		
    	}
    	if(j != i – 1 || p->next==NULL) 	//第i个元素不存在
    	{
        	
    		printf("插入位置参数错！");	
    		return 0;		
    	}
     	s = p->next; 
    	*x = s->data;	
    	p->next = p->next->next; 
    	free(s);
    	return 1;
    } 
    
     //（5）取数据元素   ListGet(head, i, x)
    int ListGet(SLNode *head, int i, DataType *x)
    {
        	
    	SLNode *p;
    	int j;
     	p = head;	j = -1;
    	while(p->next != NULL && j < i)
    	{
        	
    		p = p->next;	
    		j++;	
    	}
     	if(j != i)
    	{
        	
    		printf("取元素位置参数错！");	
    		return 0;
    	}
     	*x = p->data;
    	return 1;
    } 
    
    //（6）撤消单链表   Destroy(head)
    void Destroy(SLNode **head)
    {
        	
    	SLNode *p, *p1;
     	p = *head;
    	while(p != NULL)
    	{
            	
    		p1 = p;	
    		p = p->next;
    		free(p1);	
    	}
    	*head = NULL;
    }

![在这里插入图片描述][20210622110645931.png]

## 五、循环单链表 ##

特点：最后一个结点的指针域指向整个链表的第一个结点，从而使链表形成一个环。  
![在这里插入图片描述][20210622111116445.png]  
程序设计：带头结点的循环单链表和带头结点的单链表操作实现方法类似.  
初始化函数:

（*head）->next=NULL 改为（*head）->next=head

在其他函数循环判断条件中：

p->next!=NULL	改为	 p->next != head

## 六、双向链表 ##

双向链表的存储结构  
![在这里插入图片描述][20210622111229936.png]  
![在这里插入图片描述][20210622111301767.png]  
循环双向链表的插入过程如图示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 6]  
删除过程如图示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 7]  
代码实现如下：

//（1）插入数据元素
    int ListInsert(DLNode *head, int i, DataType x)
    //在带头结点的双向循环链表head的第i（0≤i ≤ size）个结点前插入一个存放数据
    //元素x的结点。插入成功则返回1；失败则返回0
    {
        	
    	DLNode *pi, *px;	 //指针pi最终指向第i个结点,px为新结点
    	int j;
     	pi = head->next;	j = 0;	
    	while(pi!=head && j < i ) {
        	
    		pi = pi->next;	j++;	
    	}
    	if(j != i) {
        
    		printf(“插入元素位置参数出错！");	return 0;   } 
    	px = (DLNode *)malloc(sizeof(DLNode));
    	px->data = x;
     	px->prior = pi->prior; 
    	px->next   = pi;
    	pi->prior ->next = px;
    	pi->prior = px;
    	return 1;
    }
    
    //（2）删除数据元素   
    int ListDelete(DLNode *head, int i, DataType *x)
    {
        	
    	DLNode *pi;	int j;
     	pi = head->next;	j =0;
    	while(pi != head && j < i ) 
    	{
        	
    		pi = pi->next;	
    		j++;		
    	}
    	if(j != i || pi->next==head) 	//第i个元素不存在
    	{
        	
    		printf("插入位置参数错！");	
    		return 0;		
    	}
     	*x = pi->data; 
    	pi->prior->next= pi->next;	
    	pi->next->prior = pi->prior; 
    	free(pi);
    	return 1;
    }

## 七、静态链表 ##

静态链表：在数组中增加一个(或两个)指针域用来存放下一个(或上一个)数据元素在数组中的下标，从而构成用数组构造的单链表。因为数组内存空间的申请方式是静态的，所以称为静态链表，增加的指针称做仿真指针。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 8]

[20210622100019872.png]: https://img-blog.csdnimg.cn/20210622100019872.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210622100057378.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70
[20210622105717404.png]: https://img-blog.csdnimg.cn/20210622105717404.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210622105908105.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210622105912816.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70
[20210622105933525.png]: https://img-blog.csdnimg.cn/20210622105933525.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210622105957736.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2021062211000272.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2021062211001219.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70
[20210622110142873.png]: https://img-blog.csdnimg.cn/20210622110142873.png
[20210622110159888.png]: https://img-blog.csdnimg.cn/20210622110159888.png
[20210622110645931.png]: https://img-blog.csdnimg.cn/20210622110645931.png
[20210622111116445.png]: https://img-blog.csdnimg.cn/20210622111116445.png
[20210622111229936.png]: https://img-blog.csdnimg.cn/20210622111229936.png
[20210622111301767.png]: https://img-blog.csdnimg.cn/20210622111301767.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20210622111329246.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20210622111353849.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20210622111534521.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70