1. 顺序表
顺序表是指用一段连续的地址，依次存放数据元素的线性数据结构。此种存储方式使得顺序表的物理结构与逻辑结构都是连续的。
与数组的区别：函数中的数组被存放在栈段中，而栈段有系统限制的大小（可使用ulimit -s查看系统限制的大小，单位为kb），因此顺序表往往使用在堆段中操作管理动态数组的方式实现。
1.1 管理结点
在顺序表中，管理节点内部一般存放：数据域地址(*data)、**总容量(size)以及当前数据量(len)**等等。
#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 顺序表的插入
//插入 //将 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 顺序表的删除
//删除 //将 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 的空间，然后将原数据从原空间迁移到新空间
//倍增法扩容 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)。
//定义链表 管理结点 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; }
输出结果：
2.4 任意位置插入
//任意位置的插入 // 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 任意位置删除
//任意位置的删除 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 虚头结点
在需要特殊处理头结点的时候，可以实现一个带有虚头结点的链表。在链表初始化或在某些操作执行时，将一个额外的结点放在头指针执行的地方。虚头结点可以使得整个链表永远不空，永远有头。所以拥有虚头结点的链表在处理各类结点操作时会更加便捷。
任意位置插入：不需要特殊考虑插入位置是否在链表头部。
任意位置删除：不需要特殊考虑删除的结点是否是链表的第一个结点。
//结点部分没有改动 //定义结点 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语言线性表内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>！
需要了解更多c/c++开发分享C语言超详细讲解线性表，都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/1121010.html