线性结构--线性表常用操作

迷南。 2022-02-03 05:53 332阅读 0赞

#### 线性表常用操作（顺序存储，链式存储） ####

**顺序存储的优点：**  
1.根据位序查找和求线性表长度比较简单  
2.代码容易理解  
**链式存储优点**  
1.节省空间  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70]

##### 一、顺序存储实现 #####

###### 1.声明定义 ######

#include<stdio.h>
    #include<stdlib.h>
    
    typedef int Position;
    typedef int ElementType;
    typedef struct LNode *PtrToLNode;
    typedef PtrToLNode List;
    
    #define MAXSIZE 100
    
    struct LNode{ 
    	ElemenType Data[MAXSIZE];
    	Position Last;
    };

###### 2.创建空线性表（初始化） ######

List MakeEmpty()//构造一个空表 
    { 
    	List L;
    	L=(List)malloc(sizeof(struct LNode));
    	L->Last=-1;
    	return L;
    }

###### 3.在指定位置插入 ######

bool Insert(List L,Elementype X,int i)
    { 
    	Position j;
    	if(L->Last==MAXSIZE-1)//检测表是否满 
    	{ 
    		printf("表满");
    		return false;
    	} 
    	 
    	if(i<1||i>Last+2)//检测插入位置是否合法 
    	{ 
    		printf("插入位置不合法");
    		return false; 
    	}
    	
    	for(j=L->Last;j>i-1;j--)//数组下标从0开始 
    		L->Data[j+1]=L->Data[j];//从最后一个元素开始，依次向后移动 
    		
    	L->Data[i-1]=X;
    	L->Last++;//Last仍指向最后元素 
    	return true; 
    }

###### 4.查找元素第一次出现的位置 ######

int Find(ElemenType X,List L)
    { 
    	int i=0;
    	while(i<=L->Last&&L->Data!=X)
    	i++;
    	if(i>L->Last)
    	return -1;//如果未找到返回-1 
    	else
    	return i;//如果找到返回位置 
    *}*

###### 5.删除指定位置元素 ######

bool Delete(List L,int i)
    { 
    	Position j;
    	if(i<1||i>Last+1)
    	{ 
    		printf("删除位置不合法");
    		return false; 
    	}
    	
    	for(j=i;j<=L->Last;j++)//将后面元素依次向前移动 
    	{ 
    		L->Data[j-1]=L->Data[j];
    	}
    	L->Last--;
    	return true;
    }

###### 6.根据位序返回相应元素 ######

ElementType FindKth(int k,List L)
    { 
    	if(k<1||k>L->Last+1)
    	{ 
    		printf("查找位置不合法");
    		return ; 
    	}
    	
    	return L->Data[k-1];
    }

###### 7.返回线性表的长度 ######

int Length(List L)
    { 
    	return L->Last;
    }

##### 二、链式存储实现 #####

###### 1.定义和声明 ######

#include<stdio.h>
    #include<stdlib.h>
    
    typedef int ElemenType;
    typedef struct LNode *PtrNode;
    
    struct LNode{ 
    	ElemenType Data;
    	PtrNode Next;
    };
    
    typedef PtrNode Position;
    typedef PtrNode List;
    List L;

###### 2.求线性表长度 ######

int Length(List L)
    { 
    	int cnt=0;//计数
    	Position P;
    	P=L;
    	while(P)
    	{ 
    		P=P->Next;
    		cnt++;
    	 } 
    	 return cnt;
    }

###### 3.按位序查找线性表中的元素 ######

#define ERROR -1
    ElemenType FindKth(List L,int k)
    { 
    	Position P;
    	int cnt=1;
    	P=L;
    	while(P&&cnt<k)
    	{ 
    		P=P->Next;
    		cnt++;
    	}
    	
    	if(cnt==k&&P)
    	return P->Data;
    	else
    	return ERROR;
    }

###### 4.按值查找线性表中的元素并返回地址 ######

Position Find(List L,ElemenType X)
    { 
    	Position P=L;
    	
    	while(P&&P->Data!=x)
    	P=P->Next;
    	
    	if(P&&P->Data==X)
    	return P;
    	else
    	return NULL;
    }

###### 5.在指定位置插入元素 ######

**基本思路：** 找到位序为i-1的结点pre。若存在，则申请一个新结点并在数据域填上相应值X，然后将新结点插入到**pre之后**，返回结果链表。

注：在这里为链表增加一个空的头结点，目的是：如果不增加，要在第一个位置插入，

tmp->next=L;
    return tmp;

表头指针L可能会变，L不能被带回来，所以为链表增加一个空的头结点

bool Insert(List L,ElemenType X,int i)
    { 
    	Position tmp,pre;
    	int cnt=0;
    	
    	pre=L;
    	while(pre&&cnt<i-1)
    	{ 
    		pre=pre->Next;
    		cnt++;
    	}
    	
    	if(pre==NULL||cnt!=i-1)
    	{ 
    		printf("插入位置错误");
    		return false; 
    	}
    	else
    	{ 
    		tmp=(Position)malloc(sizeof(struct LNode));
    		
    		tmp->Data=X;
    		tmp->Next=pre->Next;
    		pre->Next=temp;
    		return true;
    	}
    }

###### 6.删除指定位序i的元素 ######

先找到前一个元素，然后删除结点并释放空间

bool Delete(List L,int i)
    { 
    	Position tmp,pre;
    	int cnt=0;
    	
    	pre=L;
    	while(pre&&cnt<i-1)//先找到要删除元素的前一个结点 
    	{ 
    		pre=pre->Next;
    		cnt++;
    	}
    	
    	if(pre==NULL||cnt!=i-1||pre->Next==NULL) //注意准备删除的元素不能为空
    	{ 
    		printf("删除位置参数错误")；
    		return false; 
    	 } 
    	 
    	 else//找到待删结点的前一个结点 
    	 { 
    	 	tmp=pre->Next;
    		pre->Next=tmp->Next;
    		free(tmp);
    		
    		return true; 
    	 }
    }

**重要操作**

1.在插入元素时,先连tmp与后面相连，在将前面与temp相连，顺序不可颠倒

tmp->Data=X;
    tmp->Next=pre->Next;
    pre->Next=temp;

2.在删除操作时，先让temp这个临时结点等于pre后面要删除的结点，然后再让pre的下一个结点等于temp（等价于要删除的结点）的下一个结点，最后释放临时结点temp（也就是要删除的结点）。

tmp=pre->Next;
    pre->Next=tmp->Next;
    free(tmp);

3.基本的遍历

pre=L;
    	while(pre&&cnt<i-1)
    	{ 
    		pre=pre->Next;
    		cnt++;
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70]: /images/20220203/3a17fc5481224ecaaccc4ffb07c1f5b0.png