(1)数据结构复习之线性表

忘是亡心i 2022-11-12 09:51 210阅读 0赞

# 一、线性表 #

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

### 1.1线性表的定义 ###

> 线性表是具有相同数据类型的n个数据元素的**有限序列**

注意是有限序列，n为表长，且当n=0时，表为空表。  
除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继

--------------------

线性表的特性：

*  元素的个数有限
 *  表中的元素具有逻辑上的顺序性，有先后次序
 *  元素的数据类型都相同，因此占有的存储空间大小相同
 *  表中的元素都是数据元素，每个元素都是单个元素
 *  表中元素具有抽象性，因此只关心元素间逻辑结构，不考虑元素表示什么内容

## 1.2线性表的线性表示 ##

### 1.2.1线性表的定义 ###

线性表的顺序存储又称为顺序表，用一组连续的存储空间依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素，物理上也相邻，**即逻辑顺序与物理顺序相同**

> **线性表的位序是从1开始的**  
> **动态分配并不是链式存储**，它仍然属于顺序存储结构，依然是随机存取，只是分配的空间大小可以在运行时动态决定

--------------------

### 1.2.2顺序表的基本操作（c语言） ###

##### 1.定义顺序表，动态分配的方式 #####

typedef int ElemType;
    
    //动态分配 
    typedef struct SqList{ 
    	ElemType *elem;
    	int length;//顺序表的长度
    	int listSize;//顺序表的大小
    }SqList;

##### 2.初始化顺序表 #####

申请LIST\_INIT\_SIZE大小的空间，并把长度置为0，  
总长度置为LIST\_INIT\_SIZE

void initList(SqList *L){ 
    	L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    	L->length=0;
    	L->listSize=LIST_INIT_SIZE;
    	
    }

--------------------

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

首先判断插入位置是否合法，然后检查顺序表空间是否足够，不够就申请，然后从顺序表的表尾向前遍历，依次将向后挪一个单位，给要插入的元素腾出位置，遍历到要插入的位置就停止，将元素插入到对应位置，表长对应加1

//插法
    int insertFun(int e,SqList *L,int n){ 
    	if(n<1||n>L->length+1)//插入的位置不合法 
    		return 0;
    		
    	if(L->length>=L->listSize){ //空间不够，申请更多的空间 
    		ElemType *p=L->elem;
    		L->elem=(ElemType*)malloc((L->listSize+LISTINCREMENT)*sizeof(ElemType));
    		int j;
    		for(j=0;j<L->listSize;j++)
    			L->elem[j]=p[j];
    		L->listSize+=LISTINCREMENT;//改变顺序表长度 
    		free(p);
    	}
    	
    	int i;
    	for(i=L->length;i>=n;i--){ 
    		L->elem[i]=L->elem[i-1];
    		
    	}
    	L->elem[n-1]=e;
    	L->length++;
    	return 1;		
    		
    }

##### 4.按位序删除元素 #####

注意位序是从1开始的，从要删除的位置向后遍历，将元素向前挪一个单位即可

//按位序删除元素
    int  deleteByIndexFun(SqList *L, int index){ 
    	if(index>L->length)//输入的位序不合法 
    		return 0;
    	int i;
    	for(i=index-1;i<L->length-1;i++)
    		L->elem[i]=L->elem[i+1];
    	L->length--;	
    	return 1;
    }

##### 5.按值删除元素 #####

这里遍历了表，调用了按位序删除元素的函数，将所有值为val的元素删除了

//按值删除元素 
    int deleteByValFun(SqList *L, int val){ 
    	int i=0;
    	for(;i<L->length;i++){ 
    		if(L->elem[i]==val){ 
    			deleteByIndexFun(L,i+1);
    			i--;//若删除了一个元素，则需要进行i--操作，防止遗漏便利数据，这种情况在连续相同的值恰好等于val时才会发生 
    		}
    	} 	
    }

--------------------

##### 6.完整代码 #####

#include <stdio.h>
    #include<malloc.h>
    #define LIST_INIT_SIZE 5
    #define LISTINCREMENT 10 
    
    typedef int ElemType;
    
    //动态分配 
    typedef struct SqList{ 
    	ElemType *elem;
    	int length;
    	int listSize;
    }SqList;
    
    void initList(SqList *L){ 
    	L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    // if(!L.elem) exit();
    	L->length=0;
    	L->listSize=LIST_INIT_SIZE;
    	
    }
    
    
    //插法
    int insertFun(int e,SqList *L,int n){ 
    	if(n<1||n>L->length+1)//插入的位置不合法 
    		return 0;
    		
    	if(L->length>=L->listSize){ //空间不够，申请更多的空间 
    		ElemType *p=L->elem;
    		L->elem=(ElemType*)malloc((L->listSize+LISTINCREMENT)*sizeof(ElemType));
    		int j;
    		for(j=0;j<L->listSize;j++)
    			L->elem[j]=p[j];
    		L->listSize+=LISTINCREMENT;//改变顺序表长度 
    		free(p);
    	}
    	
    	int i;
    	for(i=L->length;i>=n;i--){ 
    		L->elem[i]=L->elem[i-1];
    		
    	}
    	L->elem[n-1]=e;
    	L->length++;
    	return 1;		
    		
    } 
    
    
    //打印顺序表
    void printTable(SqList *L){ 
    	int i=0;
    	printf("顺序表的元素是：");
    	for(;i<L->length;i++)
    		printf("%d ",L->elem[i]);	
    	printf("\n顺序表的长度是%d\n",L->length);
    	printf("顺序表的容量是%d\n",L->listSize);
    } 
    
    //按位序删除元素
    int  deleteByIndexFun(SqList *L, int index){ 
    	if(index>L->length)//输入的位序不合法 
    		return 0;
    	int i;
    	for(i=index-1;i<L->length-1;i++)
    		L->elem[i]=L->elem[i+1];
    	L->length--;	
    	return 1;
    }
    
    //按值删除元素 
    int deleteByValFun(SqList *L, int val){ 
    	int i=0;
    	for(;i<L->length;i++){ 
    		if(L->elem[i]==val){ 
    			deleteByIndexFun(L,i+1);
    			i--;//若删除了一个元素，则需要进行i--操作，防止遗漏便利数据，这种情况在连续相同的值恰好等于val时才会发生 
    		}
    	} 	
    }
     
    
    int main(){ 
    	SqList L;
    	initList(&L);
    	
    	insertFun(5,&L,1);//插入元素 
    	insertFun(4,&L,2);
    	insertFun(3,&L,3);
    	insertFun(2,&L,4);
    	insertFun(1,&L,5);
    	insertFun(2,&L,5);
    	insertFun(2,&L,5);
    	int flag=insertFun(2,&L,1);
    	
    	if(flag==0)
    		printf("插入失败\n");
    		
    		
    // deleteByIndexFun(&L,2); //按位序删除元素 
    // deleteByIndexFun(&L,4); 
    	
    	deleteByValFun(&L,2); 
    	
    	printTable(&L);//打印顺序表
    	
    	 
    		
    	return 0;
    }
    
    > 顺序表的插入、删除和查找的平均时间复杂度都为O(n)

--------------------

## 1.3线性表的链式表示 ##

### 1.3.1单链表的定义 ###

> **链表不需要逻辑上相连，通过指针将元素串联成一条链，插入和删除不需要移动元素，但是也失去了随机存取的特性**

> **头节点和头指针的区别：不管带不带头节点，头指针都指向链表的第一个节点，头节点是带头节点的链表的第一个节点，通常不存储信息**

引入头节点的优点：

*  由于第一个数据节点的的位置被存放在头节点的指针域里，因此在链表的第一个位置上的操作和在表上其他位置的操作一致，无需特殊处理
 *  无论链表是否为空，其头指针都指向头节点的非空指针（空表中头节点的指针与为空），因此非空链表和空链表的操作也是一致的

### 1.3.1单链表的基本操作（带头节点） ###

###### 1.定义链表 ######

typedef int ElemType;
    
    typedef struct LNode{ 
    	ElemType data;
    	struct LNode *next;
    }LNode,*LinkList;

###### 2.头插法插入数据 ######

void head_Insert(LinkList L,int e){ 
    	LNode *s=(LNode*)malloc(sizeof(LNode));
    	s->data=e;
    	s->next=L->next;
    	L->next=s;
    }

###### 3.尾部插入节点 ######

遍历链表，找到为节点，然后将新的节点接到链尾

void tail_Insert(LinkList L,int e){ 
    	LNode *s=(LNode*)malloc(sizeof(LNode));
    	s->data=e;
    	s->next=NULL;
    	while(L->next!=NULL)
    		L=L->next;
    	L->next=s;	
    }

###### 4.按序号删除元素 ######

因为要删除指定序号节点，需要先找到该节点，所以遍历链表，同时记录序号，找到后，将其删除

/按照序号删除元素 
    int deleteNodeByIndex(LinkList L,int index){ 
    	int i=1;
    	if(index<1)
    		return 0;
    	while(L->next!=NULL){ 
    		if(i<index){ 
    			L=L->next;
    			i++;
    		}
    		else break;
    	}
    	 
    	if(i<index)
    		return 0;//序号大于链表长度
    	
    	L->next=L->next->next;	
    		 
    }

###### 5.完整代码 ######

#include <stdio.h>
    #include<malloc.h>
    
    typedef int ElemType;
    
    typedef struct LNode{ 
    	ElemType data;
    	struct LNode *next;
    }LNode,*LinkList; 
    
    
    void printLinkList(LinkList L){ //打印链表中的元素 
    	printf("链表中的元素是：");
    	L=L->next;
    	while(L!=NULL){ 
    		printf("%d ",L->data);
    		L=L->next;
    	}
    }
    
    //头部插入
    void head_Insert(LinkList L,int e){ 
    	LNode *s=(LNode*)malloc(sizeof(LNode));
    	s->data=e;
    	s->next=L->next;
    	L->next=s;
    } 
    
    
    //尾部插入 
    void tail_Insert(LinkList L,int e){ 
    	LNode *s=(LNode*)malloc(sizeof(LNode));
    	s->data=e;
    	s->next=NULL;
    	while(L->next!=NULL)
    		L=L->next;
    	L->next=s;	
    }
    //n 1 2
    
    //按照序号删除元素 
    int deleteNodeByIndex(LinkList L,int index){ 
    	int i=1;
    	if(index<1)
    		return 0;
    	while(L->next!=NULL){ 
    		if(i<index){ 
    			L=L->next;
    			i++;
    		}
    		else break;
    	}
    	 
    	if(i<index)
    		return 0;//序号大于链表长度
    	
    	L->next=L->next->next;	
    		 
    } 
    
    int main(){ 
    	LinkList L=(LinkList)malloc(sizeof(LNode));//头节点 
    	L->next=NULL;
    	int i=1;
    	for(;i<6;i++){ 
    // head_Insert(L,i);
    		tail_Insert(L,i);
    	}
    	
    	int flag1=deleteNodeByIndex(L,6);
    	if(flag1==0)
    		printf("序号不合法，删除失败\n");
    	printLinkList(L); 
    	return 0;
    }

### 1.3.3双链表 ###

同时存在前驱和后继节点

### 1.3.4循环链表 ###

##### 1.循环单链表 #####

循环单链表与单链表的区别是表中最后一个节点的指针不是NULL，而是指向了头节点，从而整条链就形成了一个环

> 循环链表判断空表的条件是尾节点是否等于头节点

##### 2.循环双链表 #####

在循环单链表的基础上，增加一个前驱指针prior，头节点的prior指针要指向尾节点

### 1.3.5静态链表 ###

> 静态链表借助数组描述线性表的链式存储结构，节点也有数据域data和指针域next，这里的指针是数组的下标，又称游标，静态链表也需要先分配一块连续的存储空间

静态链表以next=-1作为其结束的标志，静态链表的插入删除操作域动态链表一样，不需要移动元素，只需要修改指针。

### 1.3.6顺序表和链表的比较 ###