提供秦皇岛网站建设价格,网上商城建站服务商,云南建设厅网站安全员报名入口,老牛wordpress1. 链表基本概念1.1 什么是链表链表是一种常用的数据结构#xff0c;它通过指针将一些列数据结点#xff0c;连接成一个数据链。相对于数组#xff0c;链表具有更好的动态性#xff08;非顺序存储#xff09;。数据域用来存储数据#xff0c;指针域用于建立与下一个结点的…1. 链表基本概念1.1 什么是链表链表是一种常用的数据结构它通过指针将一些列数据结点连接成一个数据链。相对于数组链表具有更好的动态性非顺序存储。数据域用来存储数据指针域用于建立与下一个结点的联系。建立链表时无需预先知道数据总量的可以随机的分配空间可以高效的在链表中的任意位置实时插入或删除数据。链表的开销主要是访问顺序性和组织链的空间损失。数组和链表的区别数组一次性分配一块连续的存储区域。优点随机访问元素效率高缺点1) 需要分配一块连续的存储区域很大区域有可能分配失败2) 删除和插入某个元素效率低链表无需一次性分配一块连续的存储区域只需分配n块节点存储区域通过指针建立关系。优点1) 不需要一块连续的存储区域2) 删除和插入某个元素效率高缺点随机访问元素效率低1.2 有关结构体的自身引用问题1请问结构体可以嵌套本类型的结构体变量吗问题2请问结构体可以嵌套本类型的结构体指针变量吗typedef struct _STUDENT{char name[64];int age;
}Student;typedef struct _TEACHER{char name[64];Student stu; //结构体可以嵌套其他类型的结构体//Teacher stu;//struct _TEACHER teacher; //此时Teacher类型的成员还没有确定编译器无法分配内存struct _TEACHER* teacher; //不论什么类型的指针都只占4个字节编译器可确定内存分配
}Teacher;结构体可以嵌套另外一个结构体的任何类型变量;结构体嵌套本结构体普通变量不可以。本结构体的类型大小无法确定类型本质固定大小内存块别名;结构体嵌套本结构体指针变量可以, 指针变量的空间能确定32位 4字节、 64位 8字节;1.3 链表节点大家思考一下我们说链表是由一系列的节点组成那么如何表示一个包含了数据域和指针域的节点呢链表的节点类型实际上是结构体变量此结构体包含数据域和指针域数据域用来存储数据指针域用于建立与下一个结点的联系当此节点为尾节点时指针域的值为NULLtypedef struct Node
{//数据域int id;char name[50];//指针域struct Node *next;
}Node;1.4 链表的分类链表分为静态链表和动态链表静态链表和动态链表是线性表链式存储结构的两种不同的表示方式所有结点都是在程序中定义的不是临时开辟的也不能用完后释放这种链表称为“静态链表”。所谓动态链表是指在程序执行过程中从无到有地建立起一个链表即一个一个地开辟结点和输入各结点数据并建立起前后相链的关系。1.4.1 静态链表typedef struct Stu
{int id; //数据域char name[100];struct Stu *next; //指针域
}Stu;void test()
{//初始化三个结构体变量Stu s1 { 1, yuri, NULL };Stu s2 { 2, lily, NULL };Stu s3 { 3, lilei, NULL };s1.next s2; //s1的next指针指向s2s2.next s3;s3.next NULL; //尾结点Stu *p s1;while (p ! NULL){printf(id %d, name %s\n, p-id, p-name);//结点往后移动一位p p-next; }
}1.4.2 动态链表typedef struct Stu{int id; //数据域char name[100];struct Stu *next; //指针域
}Stu;void test(){//动态分配3个节点Stu *s1 (Stu *)malloc(sizeof(Stu));s1-id 1;strcpy(s1-name, yuri);Stu *s2 (Stu *)malloc(sizeof(Stu));s2-id 2;strcpy(s2-name, lily);Stu *s3 (Stu *)malloc(sizeof(Stu));s3-id 3;strcpy(s3-name, lilei);//建立节点的关系s1-next s2; //s1的next指针指向s2s2-next s3;s3-next NULL; //尾结点//遍历节点Stu *p s1;while (p ! NULL){printf(id %d, name %s\n, p-id, p-name);//结点往后移动一位p p-next; }//释放节点空间p s1;Stu *tmp NULL;while (p ! NULL){tmp p;p p-next;free(tmp);tmp NULL;}
}1.4.3 带头和不带头链表带头链表固定一个节点作为头结点(数据域不保存有效数据)起一个标志位的作用以后不管链表节点如果改变此头结点固定不变不带头链表头结点不固定根据实际需要变换头结点(如在原来头结点前插入新节点然后新节点重新作为链表的头结点)。1.4.4 单向链表、双向链表、循环链表单向链表双向链表循环链表2. 链表基本操作2.1 创建链表使用结构体定义节点类型typedef struct _LINKNODE
{int id; //数据域struct _LINKNODE* next; //指针域
}link_node;编写函数link_node* init_linklist()建立带有头结点的单向链表循环创建结点结点数据域中的数值从键盘输入以 -1 作为输入结束标志链表的头结点地址由函数值返回。typedef struct _LINKNODE{int data;struct _LINKNODE* next;
}link_node;link_node* init_linklist(){//创建头结点指针link_node* head NULL;//给头结点分配内存head (link_node*)malloc(sizeof(link_node));if (head NULL){return NULL;}head-data -1;head-next NULL;//保存当前节点link_node* p_current head;int data -1;//循环向链表中插入节点while (1){printf(please input data:\n);scanf(%d,data);//如果输入-1则退出循环if (data -1){break;}//给新节点分配内存link_node* newnode (link_node*)malloc(sizeof(link_node));if (newnode NULL){break;}//给节点赋值newnode-data data;newnode-next NULL;//新节点入链表也就是将节点插入到最后一个节点的下一个位置p_current-next newnode;//更新辅助指针p_currentp_current newnode;}return head;
}2.2 遍历链表编写函数void foreach_linklist(link_node* head)顺序输出单向链表各项结点数据域中的内容//遍历链表
void foreach_linklist(link_node* head){if (head NULL){return;}//赋值指针变量link_node* p_current head-next;while (p_current ! NULL){printf(%d ,p_current-data);p_current p_current-next;}printf(\n);
}2.3 插入节点编写函数: void insert_linklist(link_node* head,int val,int data)在指定值后面插入数据data,如果值val不存在则在尾部插入li//在值val前插入节点
void insert_linklist(link_node* head, int val, int data){if (head NULL){return;}//两个辅助指针link_node* p_prev head;link_node* p_current p_prev-next;while (p_current ! NULL){if (p_current-data val){break;}//两个辅助指针向后p_prev p_current;p_current p_prev-next;}//如果p_current为NULL说明不存在值为val的节点//if (p_current NULL){// printf(不存在值为%d的节点!\n,val);// return;//}//创建新的节点link_node* newnode (link_node*)malloc(sizeof(link_node));newnode-data data;newnode-next NULL;//新节点入链表newnode-next p_current;p_prev-next newnode;
}2.4 删除节点编写函数: void remove_linklist(link_node* head,int val)删除第一个值为val的结点//删除值为val的节点
void remove_linklist(link_node* head,int val){if (head NULL){return;}//辅助指针link_node* p_prev head;link_node* p_current p_prev-next;//查找值为val的节点while (p_current ! NULL){if (p_current-data val){break;}p_prev p_current;p_current p_prev-next;}//如果p_current为NULL表示没有找到if (p_current NULL){return;}//删除当前节点 重新建立待删除节点(p_current)的前驱后继节点关系p_prev-next p_current-next;//释放待删除节点的内存free(p_current);
}2.5 销毁链表编写函数: void destroy_linklist(link_node* head)销毁链表释放所有节点的空间//销毁链表
void destroy_linklist(link_node* head){if (head NULL){return;}//赋值指针link_node* p_current head;while (p_current ! NULL){//缓存当前节点下一个节点link_node* p_next p_current-next;free(p_current);p_current p_next;}
}2.6 反转链表编写函数: void reverse_linklist(link_node* head)反转链表通过3个辅助指针变量实现链表的翻转:void reverse_linklist(link_node* head){if (head NULL){return;}//辅助指针link_node* p_prev NULL;link_node* p_current head-next;link_node* p_next NULL;while (p_current ! NULL){p_next p_current-next;//更改指针指向p_current-next p_prev;//移动辅助指针p_prev p_current;p_current p_next;}//更新头结点head-next p_prev;
}2.7 统计链表长度编写函数: int size_linklist(link_node* head)int size_linklist(link_node* head){if (head NULL){return -1;}//临时指针变量执行第一个真实数据的结点link_node* p_current head-next;//记录结点个数int num 0;while (p_current ! null) {num;p_current p_current-next;}return num;
}
