189 8069 5689
下列代码已上传至GitHub
若有错误，欢迎指正
链表基础功能包括新建新链表，打印链表元素，释放链表内存，新增节点，删除节点，排序，查找节点······
struct cell {
ElementType val;
struct cell* next;
};在这里，ElementType为任意类型，为了方便下面功能实现，我们假定ElementType为int，即
typedef int ElementType;···假定新链表以0为结尾，且首位不为0···c/c++实现：
struct cell* Build() {
struct cell* head, * p, * tail;
head = p = tail = NULL;
int n = 0; //计录当前节点数
while (true) {
if (!n) { //若n节点数为0，则添加一个头节点
head = (struct cell*)malloc(sizeof(struct cell)); //为头节点申请一个新空间
scanf("%d", &head->val); //输入头节点
tail = head; //此时头节点也是尾节点
tail->next = NULL;
n = 1;
}
else {
p = (struct cell*)malloc(sizeof(struct cell)); //为新节点申请一个新空间
scanf("%d", &p->val);
if (p->val == 0) { //若输入为0，则释放此时p节点的内存并跳出循环
free(p);
break;
}
tail->next = p; //tail指向p，实现节点连接
tail = p; //tail移动到p，实现tail移动到尾节点位置
tail->next = NULL;
}
}
return head;
}c/c++实现：
void Print(struct cell* head) {
while (head) {
printf("%d ", head->val);
head = head->next;
}
}打印链表就是把链表每一个节点遍历一遍就完了，没什么好说的
四、释放链表内存（Release）c/c++实现：
void Release(struct cell* head) {
struct cell* p;
while (head) {
p = head->next;
free(p);
head = p;
}
}这个也是遍历链表，但与打印链表不同的是，由于释放当前节点，需要保存下一节点的位置，不然释放节点处后面的节点将变成野指针，释放head后将无法访问到下一节点位置，所以需要用p保存head下一节点地址
c/c++实现：
struct cell* Add(struct cell* head, int n) {
if (head == NULL || n< 0) { //若为空链表或n不合法，则返回NULL
return NULL;
}
struct cell* p, * p0;
p0 = head;
p = (struct cell*)malloc(sizeof(struct cell)); //为新增节点p申请一个新空间
scanf("%d", &p->val);
if (n == 1) { //当新增节点位置为头节点处时
p->next = head;
return p;
}
else {
for (int i = 1; i< n - 1; i++) {
p0 = p0->next; //p0记录新增节点位置的前一个节点
if (p0 == NULL) { //若n超过链表长度，则返回原头节点head
return head;
}
}
p->next = p0->next; //***标注A***
p0->next = p;
}
return head;
}标注A：必须先将新节点指向下一节点位置,再将前一节点指向新节点（若相反,则会丢失下一节点地址）
c/c++实现：
struct cell* Del(struct cell* head, int n) {
if (head == NULL || n<= 0) { //若为空链表或n不合法，则返回NULL
return NULL;
}
struct cell* p, * p0;
p = p0 = head;
if (n == 1) { //当删除节点为头节点时
head = head->next;
free(p); //***标注B***
}
else {
for (int i = 1; i< n - 1; i++) {
p0 = p0->next; //p0记录删除节点位置的前一个节点
if (p0 == NULL) { //若n超过链表长度，则返回原头节点head
return head;
}
}
p = p0->next;
if (p) { //检测p是否为NULL，即p0是否为位节点
p0->next = p->next;
free(p); //***标注B***
}
}
return head;
}标注B：删除节点需要释放内存
c/c++实现：
ElementType FindElement(struct cell* head, int n) {
if (head == NULL || n<= 0) { //若为空链表或n不合法，则返回0
return 0;
}
for (int i = 1; i< n; i++) {
head = head->next;
if (head == NULL) { //若n超过链表长度，则返回0
return 0;
}
}
return head->val;
}c/c++实现：
bool FindSite(struct cell* head, ElementType n) {
int x = 1; //记录节点位置
bool TorN = false;
while (head) {
if (head->val == n) {
printf("%d ", x);
TorN = true; //若找到则标记true
}
head = head->next;
x++;
}
if (x) {
return true;
}
printf("NULL");
return false; //未找到返回0并打印NULL
}总结：通过节点查找元素，只需要定位节点位置即可；通过元素查找节点，则会有多种可能性，需要遍历链表一个一个抓取
2022/11/26
要期末考了，先鸽一段时间再写blog
争取一个星期写两篇（理论上可以做到，只要不摆）
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧