C语言-单链表相关操作
- 陈大剩
- 2021-02-04 00:03:31
- 3969
复习C语言单链表其实并不顺利,网上查找教程标题是《C语言操作单链表》,内容却是C++;
当时看到&link这种甚至搜索了一个多星期*;
后面才搞明白二维指针其实* &==* *
,只是C语言中并没有*&
这样引用,只有C++才具有;
注意:严蔚敏的《数据结构 C语言版中》大部分代码是C++,C语言运行可能会报错(血的教训);
单链表操作平均时间负杂度为O(n)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int data;
struct Link *next;
} link;
void initList(link **list);
void createNode(link **list);
void getInput(link *list);
void insertHeadNode(link *list);
void insertTailNode(link *list);
void freeList(link **list);
void insertRandNode(link *list, int add);
void selectNode(link *list, int add);
void amendNode(link *list, int add);
//初始化链表
void initList(link **list) {
//申请头节点
link *temp, *p = (link *) malloc(sizeof(link));
if (p == NULL) {
printf("%s函数执行,申请内存失败\n", __FUNCTION__);
}
p->data = NULL;
createNode(&temp);
p->next = temp;
*list = p;
}
//获取输入值
void getInput(link *list) {
link *temp = list;
printf("请输入值\n");
temp->next = NULL;
scanf("%d", &temp->data);
}
//创建节点
void createNode(link **list) {
link *temp = (link *) malloc(sizeof(link));
if (temp == NULL) {
printf("%s函数执行,申请内存失败\n", __FUNCTION__);
}
getInput(temp);
*list = temp;
}
//头插法
void insertHeadNode(link *list) {
link *temp = NULL, *p = list;
createNode(&temp);
if (p->next == NULL) {
printf("%s函数执行,头结点为空\n", __FUNCTION__);
}
temp->next = p->next;
p->next = temp;
}
//尾插法
void insertTailNode(link *list) {
link *temp = NULL, *p = list;
createNode(&temp);
if (p == NULL) {
printf("%s函数执行,链表为空\n", __FUNCTION__);
} else {
while (p->next) {
p = p->next;
}
p->next = temp;
}
}
//插入指定位置
void insertRandNode(link *list, int add) {
link *p = list, *temp;
int i;
for (i = 1; i < add; i++) {
if (p == NULL) {
printf("%s函数执行,插入位置无效\n", __FUNCTION__);
}
p = p->next;
}
createNode(&temp);
temp->next = p->next;
p->next = temp;
}
//查找节点
void selectNode(link *list, int add) {
link *temp = list;
int i;
for (i = 1; i <= add; i++) {
if (temp == NULL) {
printf("%s函数执行,查询位置无效\n", __FUNCTION__);
}
temp = temp->next;
}
printf("查找的值为:%d \n", temp->data);
}
//修改节点
void amendNode(link *list, int add) {
link *temp = list;
int i;
for (i = 1; i <= add; i++) {
if (temp == NULL) {
printf("%s函数执行,查询位置无效\n", __FUNCTION__);
}
temp = temp->next;
}
printf("请输入修改的值\n");
scanf("%d", &temp->data);
}
//清空链表
void freeList(link **list) {
link *temp = *list;
link *del = NULL;
if (temp == NULL) {
printf("%s函数执行,链表为空\n", __FUNCTION__);
} else {
while (temp->next) {
del = temp;
temp = temp->next;
free(del);
}
}
del = temp;
free(del);
*list = NULL;
}
//打印链表
void printList(link *list) {
link *temp = list;
if (temp == NULL) {
printf("%s函数执行,链表为空\n", __FUNCTION__);
} else {
while (temp->next) {
temp = temp->next;
printf("输出的值为:%d \n", temp->data);
}
}
putchar('\n');
}
int main() {
link *list;
initList(&list);
insertHeadNode(list);
insertHeadNode(list);
insertTailNode(list);
amendNode(list, 3);
insertTailNode(list);
insertRandNode(list, 3);
selectNode(list, 4);
printList(list);
freeList(&list);
printList(list);
return 0;
}
输入与输出
//输入
1
2
3
4
5
6
7
//输出
查找的值为:5
输出的值为:3
输出的值为:2
输出的值为:7
输出的值为:5
输出的值为:4
输出的值为:6
printList函数执行,链表为空
文章如有错误之处,欢迎大神指导。
赞
(0)