怎么给喜欢的人做网站,北京网上注册公司,工作邮箱认证提额,wordpress 探针储备知识#xff1a; 线性表 #xff1a;一对一的数据所组成的关系称为线性表。 线性表是一种数据内部的逻辑关系#xff0c;与存储形式无关线性表既可以采用连续的顺序存储(数组)#xff0c;也可以采用离散的链式存储(链表)顺序表和链表都称为线性表 顺序存储就是将数据存… 储备知识 线性表 一对一的数据所组成的关系称为线性表。 线性表是一种数据内部的逻辑关系与存储形式无关线性表既可以采用连续的顺序存储(数组)也可以采用离散的链式存储(链表)顺序表和链表都称为线性表 顺序存储就是将数据存储到一片连续的内存中在C语言环境下可以是具名的栈数组或者是匿名的堆数组。 栈空间char buf[4];自动申请空间函数结束后自动释放{}内定义的局部变量{}过后自动释放空间大小为8M 堆空间:malloc(16) calloc(4,sizeof(int)) realloc() 手动分配空间手动释放空间空间大小为实际物理内存空间生命周期为整个程序的生命周期 1.优点 不需要多余的信息来记录数据的关系存储密度高所有数据顺序存储在一片连续的内存中支持立即访问任意一个随机数据 2.缺点 插入、删除时需要保持数据的物理位置反映其逻辑关系需要成片移动数据当数据节点较多时需要一整片较大的连续内存空间当数据节点数量变化剧烈时内存的释放和分配不灵活 链表存储可以将数据存储到不连续的内存空间中可以是单链表或双链表。 单链表
一种常见的数据结构它由一系列节点组成每个节点包含了数据部分和指向下一个节点的指针。在单链表中第一个节点称为头节点最后一个节点的指针指向空表示链表的结束。
特点
动态大小单链表的大小可以根据需要动态增长或缩小。插入和删除操作在单链表中插入或删除节点通常比较灵活只需要改变相邻节点的指针即可。不需要连续内存与数组不同单链表的节点不需要在内存中连续存储它们可以分散在内存的任何位置。访问效率访问单链表中的元素需要从头节点开始逐个遍历到所需位置因此访问效率相对较低。
单链表的常见操作包括
插入在链表的指定位置插入新节点。删除删除链表中的指定节点。搜索查找链表中包含特定数据的节点。遍历从头节点开始依次访问链表中的每个节点。
创建有头结点单链表
1. 从无到有第一个节点的诞生此时的首节点和尾节点都是它本身
2 .从少到多(添加节点过程)
尾插法
新节点插入在选定节点后面若所选节点为尾节点last原指向的节点则原来的尾节点被新节点替代成为新的尾节点。
头插法
新节点插入在选定节点前面若所选节点为首节点last原指向的节点则原来的首节点被新节点替代成为新的首节点。
// 定义数据节点
struct node
{dataType data; // 数据域struct node *next; // 指针域存放(指向)下一个节点的地址
};// 定义头节点
struct headNode
{struct node *first; // 指向第一个数据节点struct node *last; // 指向最后一个数据节点int nodeNumber; // 记录链表节点数
};//创建头节点
struct headNode* create_new_headNode()
{struct headNode* head malloc(sizeof(struct headNode));if(head NULL)return NULL;head-first NULL;head-last NULL;head-nodeNumber 0;return head;
}// 创建新节点
struct node* create_new_node(dataType data)
{struct node* pnew malloc(sizeof(struct node));if(pnew NULL)return NULL;pnew-data data;pnew-next NULL;return pnew;
}// 尾插法
void addTail(struct headNode *head,struct node* pnew)
{head-last-next pnew;head-last pnew;
}//创建链表
struct headNode* create_list()
{// 创建头节点struct headNode* head create_new_headNode();if(head NULL)return NULL;dataType data -1;while(1){scanf(%d,data);if(data 0)break;// 创建新节点struct node* pnew create_new_node(data);if(pnew NULL)return NULL;// 从无到有if(head-first NULL){head-first pnew;head-last pnew;}else // 从少到多{// 尾插法addTail(head,pnew);}// 更新节点head-nodeNumber;}return head;
}//显示链表
void showList(struct headNode* head)
{if(head-first NULL){printf(链表为空\n);return;}for(struct node* p head-first;p ! head-last-next;p p-next){printf(%d\t,p-data);}printf(\n);printf(链表节点数为%d\n,head-nodeNumber);
}
双链表
是一种链式数据结构它由一系列节点组成每个节点除了包含数据外还包含两个指针一个指向前一个节点一个指向后一个节点。这种结构允许双向遍历链表即可以从头节点开始向前遍历也可以从尾节点开始向后遍历。
特点
双向链接每个节点都有指向前一个和后一个节点的指针这使得在链表中的移动更加灵活。动态大小与单链表一样双链表的大小可以动态变化。插入和删除操作在双链表中插入和删除操作通常比单链表更加高效因为可以直接访问前一个或后一个节点而不需要像单链表那样从头节点开始遍历。不需要连续内存节点在内存中不需要连续存储可以分散在内存的任何位置。
双链表的常见操作包括
插入可以在链表的任意位置插入新节点包括在头节点之前或尾节点之后。删除可以快速删除指定节点因为可以直接访问前一个和后一个节点来更新指针。搜索可以从头或尾开始搜索特定数据的节点。遍历可以正向或反向遍历链表。
创建有头结点双链表
// 创建数据节点
struct node
{dataType data;struct node *prev;// 指向上一个节点struct node *next;// 指向下一个节点
};// 创建头节点
struct headNode
{struct node *first; // 指向首节点struct node *last; // 指向最后一个节点int nodeNumber; // 记录节点数
};// 创建头节点
struct headNode *create_head()
{// 创建头节点struct headNode *head malloc(sizeof(struct headNode));if(head NULL){perror(create head failed:);return NULL;}head-first NULL;head-last NULL;head-nodeNumber 0;return head;
}// 创建新节点
struct node *create_new_node(dataType data)
{struct node *pnew malloc(sizeof(struct node));if(pnew NULL){perror(create new node failed:);return NULL;}pnew-data data;pnew-prev NULL;pnew-next NULL;
}//增加节点
struct headNode *add_node_list(struct headNode *head,dataType newData,dataType data)
{// 创建新节点struct node *pnew create_new_node(newData);if(pnew NULL)return NULL;// 找节点struct node *p head-first;while(p){if(p-data data)break;else{p p-next;}}// 如果找的是第一个节点if(p-data head-first-data){addHead(pnew,head);}else if(p NULL){addTail(pnew,head);}else{pnew-next p;pnew-prev p;p-prev-next pnew;pnew-prev pnew; }head-nodeNumber;return head;
}//删除节点
struct headNode *del_node(struct headNode *head,dataType data)
{// 找节点struct node *p head-first;while(p){if(p-data data)break;elsep p-next;}// 如果是第一个节点if(head-first-data data){head-first-next-prev head-first;head-first p-next;p-next NULL;p-prev NULL;free(p);}else if(p-data head-last-data){p-prev-next NULL;p-prev NULL;free(p);}else if(p NULL){printf(没有可删除的节点\n);}else{p-next-prev p-prev;p-prev-next p-next;p-prev NULL;p-next NULL;free(p);}head-nodeNumber--;return head;
}//链表遍历
void showList(struct headNode *head)
{for(struct node *p head-first;p ! head-last-next;p p-next){printf(%d\t,p-data);}printf(\n);printf(节点数为%d\n,head-nodeNumber);
}// 销毁链表
struct headNode * distory_list(struct headNode *head)
{if(isEmpty(head))return false;// 逐一删除节点struct node *p NULL;for(struct node *tmp head-first;tmp ! NULL; tmp p){p tmp-next;free(tmp);head-nodeNumber--;}return head;
}
双向循环链表
结构上和双向链表就只差首尾相连。
// 至少还有一个节点时将首尾相连
if(head-nodeNumber ! 0)
{head-last-next head-first;head-first-prev head-last;
}
