c/c++语言开发共享C语言超详细讲解线性表

1. 顺序表顺序表是指用一段连续的地址,依次存放数据元素的线性数据结构。此种存储方式使得顺序表的物理结构与逻辑结构都是连续的。与数组的区别:函数中的数组被存放在栈段中,而栈段有系统限制的大小(可使用u

%ignore_a_1%

1. 顺序表

顺序表是指用一段连续的地址,依次存放数据元素的线性数据结构。此种存储方式使得顺序表的物理结构与逻辑结构都是连续的。

与数组的区别:函数中的数组被存放在栈段中,而栈段有系统限制的大小(可使用ulimit -s查看系统限制的大小,单位为kb),因此顺序表往往使用在堆段中操作管理动态数组的方式实现。

1.1 管理结点

在顺序表中,管理节点内部一般存放:数据域地址(*data)、**总容量(size)以及当前数据量(len)**等等。

C语言超详细讲解线性表

#include<stdio.h>  #include<stdlib.h>  #include<string.h>  typedef struct vector {  	//数据域   	int *data;  	//总容量   	int size;  	//当前元素个数 或 指向末尾元素的后一位  	int len;  } vector;   //初始化  vector *initvector(int size){  	vector *v = (vector *) malloc(sizeof(vertor));  	v->data = (int *) malloc(sizeof(int) * size);  	v->len = 0;  	v->size = size;  	return v;   }   //释放  void freevector(vector *v){  	if(!v) return;  	free(v->data);  	free(v);  }  int main(){  	//初始化size为10的线性表  	vector *v = initvector(10)  	return 0;  }

1.2 顺序表的插入

C语言超详细讲解线性表

//插入   //将 v->data[idx] 处变成 val   void insert(vector *v, int idx, int val){  	//判断 v 是否为空 返回   	if(!v) return;   	//判断 idx 是否合法   	if(idx > v->len || idx < 0) return ;  	//判断 v 的容量是否已满  	if(v->len == v->size) return ;   	//维护顺序表的特性  将 idx 及之后的元素后移   	for(int i = v->len; i > idx ;i++){  		v->data[i] = v->data[i - 1];  	}  	//在 idx 处插入数据   	v->data[i] = val;  	//更新当前元素个数   	v->len++;   } 

1.3 顺序表的删除

C语言超详细讲解线性表

//删除  //将 v->data[idx] 删除   void delete(vector *v, int idx){  	if(!v) return ;  	if(idx >= v->len || idx < 0) return ;  	// idx 之后的元素前移  	for(int i = idx; i < v->len-1; i++){  		v->data[i] = v->data[i + 1];  	}  	v->len--;  }  

1.4 顺序表的扩容

扩容:新创建 原size * 2 的空间,然后将原数据从原空间迁移到新空间

C语言超详细讲解线性表

//倍增法扩容 size -> size + exsize  int expand(vector *v){  	//扩容为 size + exsize   	int exsize = v->size;  	int *tmp;  	while(exsize){  		//尝试向内存申请空间   		tmp = (int *) realloc(v->data, sizeof(int) * (v->size + exsize));  		//申请成功   		if(tmp) break;  		//申请不成功 exsize/2 继续申请   		exsize >>= 1;   	}  	//彻底失败 未申请到空间   	if(!tmp) return 0;  	//扩容成功  	v->data = tmp;   	v->size += exsize;  	return 1;  }  //插入   //将 v->data[idx] 处变成 val   void insert(vector *v, int idx, int val){  	...  	if(v->len == v->size) {  		//尝试扩容 扩容成功为 1 失败为 0   		if(!expand(v)) return;   	}   	...  } 

2. 链表

2.1 定义

链表是一种物理结构不连续,但可以依靠结点中的指针实现逻辑结构连续的线性数据结构。

构成链表的数据元素被称为“结点”,节点内部存放数据与指向下一个结点的指针。

//定义结点   typedef struct node{  	int val;  	struct node *next;  } node;   //结点初始化   node *initnode(int val){  	node *node = (node *) malloc(sizeof(node));  	node->val = val;  	node->next = null;  	return node;  }   //释放结点  void freenode(node *node){  	if(!node) return ;  	free(node);  }   

只有单一结点指针的链表的全程是“单链表”,经常被简称为链表。

链表的管理结点一般仅需要存放头结点指针(*head)。

如果需要频繁获取链表长度,管理结点中可以额外存放链表长度(len)。

C语言超详细讲解线性表

//定义链表 管理结点   typedef struct list{  	node *head;  	int len;  } list;  //初始化链表  list *initlist() {  	list *list = (list *) malloc(sizeof(list));  	list->head = null;  	list->len = 0;  	return list;  }

2.2 头部插入

头插法:将新插入的节点放在 head 后,时间复杂度o(1)

//头部插入  void inserttohead(list *list, int val){  	if(!list) return ;  	node *node = initnode(val);  	node->next = list->head;  	list->head = node;  	list->len++;  }   

2.3 尾部插入

尾插法:找到最后一个结点,将新节点插入。如果没有设计尾指针,则时间复杂度为o(n)。

//尾部插入   void inserttotail(list *list, int val){  	if(!list) return ;  	node *node = initnode(val);  	//如果list为空 则node为第一个结点 让head等于node  	//判断条件可更改为list->len == 0   	if(list->head == null){  		list->head = node;  		list->len++;  		return ;  	}  	node *p = list->head;  	while(p->next != null){  		p = p->next;  	}  	p->next = node;  	list->len++;  }  
//测试  int main(){  	list *list1 = initlist();  	list *list2 = initlist();  	for(int i = 0;i <= 10;i += 2){  		inserttohead(list1,i);  	}  	node *p = list1->head;  	while(p){  		printf("%d -> ",p->val);  		p = p->next;  	}  	printf("n");  	for(int i = 1;i <= 10;i += 2){  		inserttotail(list2,i);  	}  	node *q = list2->head;  	while(q){  		printf("%d -> ",q->val);  		q = q->next;  	}  	printf("n");  	return 0;  }  

输出结果:

C语言超详细讲解线性表

2.4 任意位置插入

C语言超详细讲解线性表

C语言超详细讲解线性表

//任意位置的插入  // idx = 0 待插入结点为头结点  // idx > 0 插入至第 i 个结点后  void insert(list *list, int idx, int val){  	if(!list) return ;  	if(idx > list->len || idx < 0) return ;  	if(idx == 0){  		//头插法   		inserttohead(list,val);  		return;  	}  	node *node = initnode(val);  	//结点索引为 0   	node *p = list->head;  	//p 找到第 idx - 1个结点  	// i = 1  结点索引为 1   	// i = 2 结点索引为 2  	// i = idx - 1 结点索引为 idx - 1   	for(int i = 1;i <= idx - 1;i++){  		p = p->next;  	}   	//插入  	node->next = p->next;  	p->next = node;  	list->len++;  }  

2.5 任意位置删除

C语言超详细讲解线性表

C语言超详细讲解线性表

//任意位置的删除   void remove(list *list, int idx){  	if(!list) return ;  	if(idx > list->len || idx < 0) return ;  	//p为0号索引结点  	node *p = list->head;  	//删除索引为 0 的结点 更改head   	if(idx == 0){  		list->head = p->next;   		list->len--;  		freenode(p);  		return;  	}  	//找到idx-1个结点  	for(int i = 1;i <= idx - 1;i ++){  		p = p->next;  	}  	node *node = p->next;  	//删除   	p->next = p->next->next;  	list->len--;  	freenode(node);  }   

2.6 虚头结点

在需要特殊处理头结点的时候,可以实现一个带有虚头结点的链表。在链表初始化或在某些操作执行时,将一个额外的结点放在头指针执行的地方。虚头结点可以使得整个链表永远不空,永远有头。所以拥有虚头结点的链表在处理各类结点操作时会更加便捷。

C语言超详细讲解线性表

任意位置插入:不需要特殊考虑插入位置是否在链表头部。

任意位置删除:不需要特殊考虑删除的结点是否是链表的第一个结点。

//结点部分没有改动  //定义结点   typedef struct node{  	int val;  	struct node *next;  } node;   //结点初始化   node *initnode(int val){  	node *node = (node *) malloc(sizeof(node));  	node->val = val;  	node->next = null;  	return node;  }   //释放结点  void freenode(node *node){  	if(!node) return ;  	free(node);  }    //定义链表 管理结点   typedef struct list{  	node *head;  	int len;  } list;  //初始化链表  list *initlist() {  	list *list = (list *) malloc(sizeof(list));  	//变动  :初始化的时候赋予一个结点 任意数值都可以   	list->head = initnode(-1);  	list->len = 0;  	return list;  }  //头部插入  void inserttohead(list *list, int val){  	if(!list) return ;  	node *node = initnode(val);  	// 变动  	node->next = list->head->next;  	// 变动  	list->head->next = node;  	list->len++;  }   //尾部插入   void inserttotail(list *list, int val){  	if(!list) return ;  	node *node = initnode(val);  	//变动 删除对链表是否为空的判断  可以直接进行插入  	//此处可以谢伟 node *p = list->head->next;   	node *p = list->head;  	while(p->next != null){  		p = p->next;  	}  	p->next = node;  	list->len++;  }  //任意位置的插入  void insert(list *list, int idx, int val){  	if(!list) return ;  	if(idx > list->len || idx < 0) return ;  	//变动 : 删除对链表是否为空的判断   	node *node = initnode(val);  	node *p = list->head;  	for(int i = 1;i <= idx;i++){  		p = p->next;  	}   	//插入  	node->next = p->next;  	p->next = node;  	list->len++;  }   //任意位置的删除   void remove(list *list, int idx){  	if(!list) return ;  	if(idx > list->len || idx < 0) return ;  	node *p = list->head;  	for(int i = 1;i <= idx;i ++){  		p = p->next;  	}  	node *node = p->next;  	//删除   	p->next = p->next->next;  	list->len--;  	freenode(node);  }  

到此这篇关于c语言超详细讲解线性表的文章就介绍到这了,更多相关c语言线性表内容请搜索<计算机技术网>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网>!

需要了解更多c/c++开发分享C语言超详细讲解线性表,都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/1121010.html

(0)
上一篇 2022年7月13日
下一篇 2022年7月13日

精彩推荐