群晖建设网站,哪些网站可以做招商广告,常德优化公司,广州联亨科技网站建设目录
前言
顺序表
链表
概念
与数组的不同
单链表
1. 创建节点
2.插入节点
尾插节点#xff08;形成链表结构#xff09;
向指定位置插入节点#xff08;链表已有#xff09;
编辑
3.遍历链表数据
4.获取链表长度
5.删除节点
删除尾节点
删除指定节点
… 目录
前言
顺序表
链表
概念
与数组的不同
单链表
1. 创建节点
2.插入节点
尾插节点形成链表结构
向指定位置插入节点链表已有
编辑
3.遍历链表数据
4.获取链表长度
5.删除节点
删除尾节点
删除指定节点
6.清空链表
7.链表的数据查找
8.链表的转置 测试集 环形链表
创建环形链表
双向循环链表
创建双向循环链表 前言 在此之前我们学习过了数组数组也是一种顺序表连续储存结构但是数组本质上是一种静态空间而我们主要讲的是动态空间的顺序表顾名思义也就是我们常见的链表链表又分为单链表以及环状链表和双向循环链表下面我们就一起来看看吧我已经上传代码,可下载代码资源
顺序表 定义 顺序表全名顺序存储结构是线性表的一种。通过《什么是线性表》一节的学习我们知道线性表用于存储逻辑关系为“一对一”的数据顺序表自然也不例外。 不仅如此顺序表对数据的物理存储结构也有要求。顺序表存储数据时会提前申请一整块足够大小的物理空间然后将数据依次存储起来存储时做到数据元素之间不留一丝缝隙。 我们常见的顺序表有数组和链表等前者是一个静态空间的数据储存结构后者是一个动态空间数据储存结构。二者都可以去通过引索去实现表的操作下面就看链表的相关操作。
链表
概念 链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点链表中每一个元素称为结点组成结点可以在运行时动态生成。每个结点包括两个部分一个是存储数据元素的数据域另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构操作。 链表的节点是分为两部分数据域和指针域
数据域存放各种数据比如int、char类型等等
指针域作为指向下一个节点的桥梁
typedef struct student{//数据域int index;//作为下标表示第几位long num;//学号char name[20];//名字int score;//分数//指针域struct student* next;//指向下一位的指针
}Student;
图解 与数组的不同 单链表 单链表是作为最简单的一种线性表的数据结构通过动态空间分配可以实现单链表的创建下面我们就学习单链表的创建以及增删改查等方法。 1. 创建节点
这里我们就不去按照之前学习链表时的做法了之前我们是一次性去创建节点的同时还把节点连接起来这里我们就把这两个步骤分开来做让代码更加灵活。
#includestdio.h
#includestdlib.h
#includestring.h
typedef struct date{long num;//学号char name[20];//名字int score;//分数
}Date;//存放数据
typedef struct student{//数据域Data x;//指针域struct student* next;//指向下一位的指针
}Student;//创建节点
Student* create_node(Date x) {Student* node (Student*)malloc(sizeof(Student));//数据赋值node-x x;//指针域指向空node-next NULL;//返回这个节点return node;
}
2.插入节点
尾插节点形成链表结构
//把节点连接起来
void create_studentlist(Student**head,Date x) {Student* new_node create_node(x);//如果头指针指向空节点的话那么将头指针指向这个新的节点if (*head NULL) {*head new_node;}//如果头指针指向一个不为空的节点的话那么就要顺着这个链表找到最后的节点把新节点放入else {Student* move*head;//创建一个移动节点,找到最后一个节点的位置while (move-next ! NULL) {move move-next; //一直往后移}move-next new_node;//把新节点放入进去}
}
向指定位置插入节点链表已有 //指定位置插入节点
void insert_node(Student** head, Student *new_node,int n) //向链表第n个位置插入节点
{Student* move*head;//通过循环找到这个节点for (int i 0; i n; i){move move-next;}//下面这两步的顺序千万不能反过来new_node-next move-next;move-next new_node;
}
3.遍历链表数据
//输出数据
void listprint(Student**head)
{Student* cur*head;while (cur ! NULL) {printf(%ld %s %d\n, cur-x.num, cur-x.name, cur-x.score);cur cur-next;}printf(output over!);
}
4.获取链表长度
//获取链表长度
int get_listlength(Student**head)
{int length0;Student* cur *head;while (cur ! NULL){length;cur cur-next;}return length;//返回长度的大小
}
5.删除节点 删除节点是链表的基本操作之一分为删除尾节点和删除指定的节点不是尾节点这两种情况要去分类讨论下面请看代码案例 删除尾节点
//删除尾节点
void pop_lastnode(Student** head)
{//如果没有节点就直接返回if (*head NULL)return;//如果只有一个节点的话就直接删除else if ((*head)-next NULL){free(*head);*head NULL;//重新置空}/*如果有多个节点的话要找到最后一个节点的上一个节点删除掉最后一个节点然后再把这个节点的next指向空*/else{Student* move *head;while (move-next-next!NULL){move move-next;}free(move-next);move-next NULL;}
}
删除指定节点 //删除指定节点
void pop_node(Student** head, int n)//删除第n个节点
{Student* move *head;Student* p;//通过循环依次去找到要删除节点的上一个节点for (int i 0; i n-1; i){move move-next;}p move-next;//此时要删除的节点标记为p节点move-next p-next;//让p节点的上一个节点指向p节点的下一个节点此时p节点已经断链free(p);
}
6.清空链表
//清空链表,释放全部的空间
void clear_list(Student**head){Student* cur*head;Student* next;while (cur ! NULL) {next cur-next;free(cur);cur next;}*head NULL;//头指针置空printf(clear over!\n);
}
7.链表的数据查找
//数据查找//按学号查找
Student* list_search_num(Student** head, int num) {Student* cur *head;while (cur!NULL) {if (cur-x.num num) { return cur; //找到了就返回这个节点}elsecur cur-next;}printf(No find);return NULL;
}//按名字查找
Student* list_search_name(Student** head, char *name) {Student* cur *head;while (cur ! NULL) {if (strcmp(cur-x.name,name)0) {return cur; //找到了就返回这个节点}elsecur cur-next;}printf(No find);return NULL;
}
8.链表的转置 我们已有的链表顺序是: 1-2-3-4-5 现在我想让这个链表顺序变为5-4-3-2-1如下图所示 这个过程就是链表的转置我们可以去通过头插法去实现 头插法步骤如下 //链表的转置(头插法)
void list_reverse(Student** head) {Student *L, *start,* p, * q;//开辟一个暂存节点LL (Student*)malloc(sizeof(Student));//初始化start *head;L-next start;p L-next;L-next NULL;while (p! NULL) {q p-next;p-next L-next;L-next p;p q;}*head L-next;//将此时的头结点等于新的头结点free(L);//释放掉暂存节点printf(reverse over!\n);
} 测试集
//测试结果
int main()
{Date a[4] { {1,xiaoming,90} ,{ 2,Jack,80 } ,{ 3,Amy,98 } ,{ 4,John,77 } };Student* head NULL;//实例化一个头节点指针for (int i 0; i 4; i) {//要把实例化的头指针的地址存入进去create_studentlist(head, a[i]);//依次成链}listprint(head);//输出数据printf(当前节点数量 %d\n, get_listlength(head));list_reverse(head);//逆转链表listprint(head);//输出数据pop_lastnode(head);//删除最后一个节点printf(当前节点数量 %d\n, get_listlength(head));listprint(head);//输出数据clear_list(head);//清空链表printf(当前节点数量 %d\n, get_listlength(head));}
//输出如下
/*1 xiaoming 90
2 Jack 80
3 Amy 98
4 John 77
output over!
当前节点数量 4
reverse over!
4 John 77
3 Amy 98
2 Jack 80
1 xiaoming 90
output over!
当前节点数量 3
4 John 77
3 Amy 98
2 Jack 80
output over!
clear over!
当前节点数量 0
*/ 环形链表 链表从名字上来看是一条数据链一般的链表其末尾节点是没有指向的但当把链表的末尾节点指定为指向头节点时则构成了一个环形链表。所以要想去建立一个环形链表只需要把最后一个节点重新指向头节点就行了或者指向其他节点可以形成局部环形链表。下面我就讲讲通过代码去创建环形链表相关操作方法增删改查跟上面所说的基本一样。 创建环形链表
#includestdio.h
#includestdlib.h
typedef struct node {int date;struct node* next;
}Node;
//创建节点
Node *create_node(int date) {Node* node (Node*)malloc(sizeof(Node));node-date date;node-next NULL;return node;
}
//把节点连起来
void create_annuallist(Node** head,int date) {Node* new_node create_node(date);if (*head NULL) {*head new_node;}else{Node* cur *head;while (cur-next) {cur cur-next;}cur-next new_node;}//成链//成环new_node-next *head;
}
当你仔细细看的话前面跟链表的创建基本上没什么区别实际上就在最后面加上一个尾节点指向头节点就是了
双向循环链表 带头双向循环链表是链表当中结构最复杂的链式结构一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个链表虽然结构复杂但是使用代码实现以后会发现能带来很多优势。 创建双向循环链表 实现思路 要想创建双向循环链表就意味着在单相链表的基础上增加一个前指针来指向上一个节点然后在成链的过程中后一个节点要指向前一个节点前一个节点指向后一个节点最后头尾节点互相指向就可以形成双向循环了。 代码实现
#includestdio.h
#includestdlib.h
#includestring.h
//创建双向循环链表
typedef struct node {struct node* prev; //前指针char date[10];//数据域struct node* next; //后指针
}D_node;
D_node* create_D_node(char*date) {D_node* new_node (D_node*)malloc(sizeof(D_node));strcpy(new_node-date, date);//前后指针都指向空初始化new_node-prev NULL;new_node-next NULL;return new_node;
}
void create_D_list(D_node** head, char* date) {D_node* new_node create_D_node(date);if (*head NULL) { //判断头结点是否为空*head new_node;}else{D_node* cur *head;while (cur-next) {cur cur-next;}//双向指向前指向后后指向前new_node-prev cur;cur-next new_node;}//头尾指针互相指向成环new_node-next *head;(*head)-prev new_node;
} 好了以上就是本期的全部内容了我们下一期再见
分享一张壁纸
