(数据结构&C语言)对链表的认识-创新互联
(数据结构&C语言)链表创新互联主营殷都网站建设的网络公司,主营网站建设方案,app软件开发,殷都h5成都微信小程序搭建,殷都网站营销推广欢迎殷都等地区企业咨询文章目录
线性表也可以使用链表来实现。
文章题目:(数据结构&C语言)对链表的认识-创新互联
网页路径:http://myzitong.com/article/cohpjj.html
- (数据结构&C语言)链表
- 初始化链表
- 单链表结点的插入
- 单链表结点的删除
- 获取指定位置上的元素
- 查找指定元素的位置
- 获取链表长度
- 相关问题
线性表也可以使用链表来实现。
链表不同于顺序表,顺序表底层采用数组作为存储容器,需要分配一块连续且完整的内存空间进行使用,而链表则不需要,它通过一个指针来连接各个分散的结点,形成了一个链状的结构,每个结点存放一个元素,以及一个指向下一个结点的指针,通过这样一个一个相连,最后形成了链表。它不需要申请连续的空间,只需要按照顺序连接即可,虽然物理上可能不相邻,但是在逻辑上依然是每个元素相邻存放的,这样的结构叫做链表(单链表)。
链表分为带头结点的链表和不带头结点的链表,带头结点的链表就是会有一个头结点指向后续的整个链表,但是头结点不存放数据,而不带头结点的链表就像上面那样,第一个节点就是存放数据的结点,一般设计链表都会采用带头结点的结构,因为操作更加方便。
接下来以带头结点的链表为例:
struct NodeList {int element; //保存当前元素
struct NodeList * next; //指向下一个结点的指针
};
typedef struct NodeList * Node;
初始化链表void initList(Node head) {head->next = NULL; 头结点默认下一个为NULL
}
单链表结点的插入先修改新插入结点的后继结点指向,指向原本在这个位置上的结点,接着将前驱结点的后继结点指向修改为新插入的结点:
寻找带插入位置的前驱结点:
_Bool insertList(Node head, int element, int index){//index表示位序
if(index< 1) return 0; //如果在非法位置插入,返回0表示插入操作执行失败
while (--index) {//通过--index的方式不断向后寻找前驱结点,index为0时程序跳出循环
head = head->next; //正常情况下继续向后找
if(head == NULL) return 0; //当已经没有后续结点时,说明index超出可插入的范围
}
return 1;
}
再根据上述思路,实现新结点的插入:
_Bool insertList(Node head, int element, int index){if(index< 1) return 0;
while (--index) {head = head->next;
if(head == NULL) return 0;
}
Node node = malloc(sizeof (Node));
if(node == NULL) return 0; //创建一个新的结点,如果内存空间申请失败返回0
node->element = element; //将元素保存到新结点中
node->next = head->next; //先让新插入的节点指向原本位置上的这个结点
head->next = node; //接着将前驱结点指向新的这个结点
return 1;
}
单链表结点的删除直接将待删除节点的前驱结点指向修改为待删除节点的下一个:
这样,待删除结点其实已经不在链表中了,所以只需要释放掉待删除结点占用的内存空间:
_Bool deleteNode(Node head,int index) {//head表示头结点
_Bool deleteList(Node head, int index){if(index< 0) return 0;
while (index--) {//找到前驱结点
head = head->next;
if(head == NULL) return 0;
}
if(head->next == NULL) return 0; //如果前驱结点下一个是NULL,说明index也已超出代删除范围(删除与插入范围不一样)
Node tmp = head->next; //保存待删除结点
head->next = head->next->next; //让前驱结点指向下一个的下一个结点
free(tmp); //使用free函数释放掉待删除结点的内存
return 1;
}
获取指定位置上的元素int getList(Node head,int index) {if(index< 1) return 0;
do {head = head->next; //使用do while语句跳过头结点
if(head == NULL) return 0;
} while(--index); //为的是找到指定位置的结点
return head->element;
}
查找指定元素的位置int findList(Node head, int element){head = head->next; //先走到第一个结点
int i = 1; //从位序1开始
while (head) {if(head->element == element) return i;
head = head->next;
i++;
} //遍历完都没找到,则返回-1
return -1;
}
获取链表长度int sizeNode(Node head) {int i = 0; //从空的头结点开始
while(head->next) {head = head->next;
i++;
}
return i;
}
完整代码如下:
#include#includestruct NodeList {int element;
struct NodeList * next;
};
typedef struct NodeList * Node;
void initNode(Node head) {head->next = NULL;
}
_Bool insertNode(Node head,int element,int index) {if(index< 1) return 0;
while(--index) {head = head->next;
if(head == NULL) return 0;
}
Node node = malloc(sizeof(Node));
node->element = element;
node->next = head->next;
head->next = node;
return 1;
}
_Bool deleteNode(Node head,int index) {if(index< 1) return 0;
while(--index) {head = head->next;
if(head == NULL) return 0;
}
if(head->next == NULL) return 0;
Node baocun = head->next;
head->next = head->next->next;
free(baocun);
return 1;
}
int getNode(Node head,int index) {if(index< 1) return 0;
do { head = head->next;
if(head == NULL) return 0;
} while(--index);
return head->element;
}
int findNode(Node head,int element) {head = head->next;
int i = 1;
while(head) {if(head->element == element) return i;
head = head->next;
i++;
}
return -1;
}
int sizeNode(Node head) {int i = 0;
while(head->next) {head = head->next;
i++;
}
return i;
}
void printNode(Node head) {//打印链表
while(head->next) {head = head->next;
printf("%d ",head->element);
}
printf("\n");
}
int main() {struct NodeList biao;
initNode(&biao);
for (int i = 0; i< 5; ++i) {insertNode(&biao, i * 50, i + 1);
}
deleteNode(&biao,3);
printNode(&biao);
printf("%d\n",getNode(&biao, 3));
printf("%d\n",sizeNode(&biao));
printf("%d\n",findNode(&biao,150));
}
运行后,成功得到结果:
相关问题值得注意的是:
- 插入:因为要寻找对应位置的前驱结点,所以平均时间复杂度为 O ( n ) O(n) O(n),但是不需要做任何的移动操作,效率肯定是比顺序表要高的。
- 删除:同上,所以平均时间复杂度为 O ( n ) O(n) O(n)
- 获取元素:由于必须要挨个向后寻找,才能找到对应的结点,所以时间复杂度为 O ( n ) O(n) O(n),不支持随机访问,只能顺序访问,比顺序表慢。
在随机访问元素时,链表需要通过遍历,而顺序表则利用数组的特性直接访问得到。
插入或删除某个元素时,顺序表需要通过遍历,而链表只需修改结点指向。
进行不同的操作时,从执行效率来看,各有各的有优势。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
文章题目:(数据结构&C语言)对链表的认识-创新互联
网页路径:http://myzitong.com/article/cohpjj.html