C语言讲义——链表完整代码
2024-08-28 09:20:52
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node {
int _id;
char s[50];
struct Node* pre;// 指向前一个节点的地址
struct Node* next;// 指向下一个节点的地址
};
void node_free(struct Node** q) {
if( *q != NULL) {
printf("free %d\n",(*q)->_id);
free(*q);
*q = NULL;
}
}
void node_print(struct Node* q) {
if (NULL == q) {
puts("节点打印：空节点，无可打印");
return;
}
printf("preview=%10d ", q->pre);
printf("【address=%10d】 ", q);
printf("【id=%2d】", q->_id);
printf("next=%10d\n", q->next);
}
void chain_print(struct Node* qFirst) {
if (qFirst == NULL) {
puts("没有元素可以打印");
return;
}
puts("----------↓↓↓打印链表------------");
// 遍历链表
struct Node* q;
for(q = qFirst; q != NULL; q=q->next ) {
node_print(q);
}
puts("----------↑↑↑打印链表------------");
}
/*
* 为链表追加节点（加在最后）
* 参数：头节点，需要追加的节点
* 返回值：无
*/
void chain_add(struct Node* qFirst, struct Node* qAdd) {
// 定位到链表头
struct Node* q = qFirst;
// 只要后面（next）有节点，往后找；直到没有next的节点（最后一个）
for(q; q->next!= NULL; q=q->next ) {
//node_print(q);
}
// 此时定位在最后一个节点，下图1
// 将新节点加在最后节点的后面（next）
q->next = qAdd;// 下图2
qAdd->pre = q;//下图3
}
/*
* 删除节点
* 参数：1.头结点 2.待删除的结点
* 因为被删除的结点需要置空，所以需要使用二级指针
* 返回值：-1 删除失败/0 删除成功
*/
int chain_remove(struct Node** qFirst, struct Node** qRemove) {
struct Node* qPre = NULL;
struct Node* qNext = NULL;
struct Node* q = *qFirst;
// 1.输入Check
if(NULL == *qRemove) {
puts("删无可删！");
return -1;
} else {
printf("删除节点：id=%d\n", (*qRemove)->_id);
}
// 2.删除头结点，特殊对待
if(*qFirst == *qRemove ) {
if((*qFirst)->next == NULL) {
// 就一个头结点的场合
node_free(qFirst);
} else { // 见下图4
qNext = q->next;
node_free(qFirst);
*qFirst = qNext;
}
printf("---chain_remove（头结点）:%d\n", *qFirst);
return 0;
}
// 3.遍历链表
for(q; q != NULL; q=q->next ) {
if (q == *qRemove) {
qPre = q->pre;
qNext = q->next;
if (qNext!=NULL) {// 见下图5
qNext->pre = qPre;
qPre->next= qNext;
} else {
// 尾节点的场合，见下图6
qPre->next= NULL;
}
node_free(qRemove);
return 0;
}
}
}
void chain_clear(struct Node** qFirst) {
puts("\n----------Clear------------");
if (qFirst == NULL) {
puts("已经是空");
return;
}
// 遍历链表
// 不断删除第一个元素
while(*qFirst != NULL) {
chain_remove(qFirst,qFirst);
printf("---chain_clear（）:头结点 %d\n", *qFirst);
}
}
struct Node* chain_get(struct Node* qFirst, int index) {
printf("---获取index = %d的节点：", index);
int i = 0;
// 遍历链表
struct Node* q = qFirst;
for(q; q!= NULL; q=q->next,i++ ) {
if (index == i) {
return q;
}
}
return NULL;
}
/*
* 获取链表长度（即节点的个数）
* 参数：头节点
* 返回值：链表长度
*/
int chain_count(struct Node* qFirst) {
if (qFirst == NULL) {
// 头节点都没有，长度为0
return 0;
}
int i = 0;
// 遍历链表
struct Node* q = qFirst;
for(q; q != NULL; q=q->next) {
// 顺藤摸瓜，直到最后一个节点
i++;// 找到一个就+1
}
return i;
}
struct Node* node_new(int id) {
struct Node* q = (struct Node*)malloc(sizeof(struct Node));
memset(q, 0, sizeof(struct Node));
q->_id = id;
return q;
}
int g_id = 1;
struct Node* qHead = NULL;
void test0Node() {
puts("###0节点的链表：");
printf("count = %d\n",chain_count(NULL));
chain_print(NULL);
}
void testAddNode() {
puts("\n###添加一个节点：");
struct Node* _q = node_new(g_id++);
chain_add(qHead, _q);
printf("count = %d\n",chain_count(qHead));
chain_print(qHead);
}
void test3Node() {
testAddNode();
testAddNode();
testAddNode();
chain_print(qHead);
}
void testGetNode() {
puts("输入需要get的节点的id");
int nId;
scanf("%d", &nId);
getchar();
struct Node* pGet;
pGet = chain_get(qHead, nId);
node_print(pGet);
}
void testRemoveNode() {
puts("输入需要删除的节点的id");
int nId;
scanf("%d", &nId);
getchar();
struct Node* pGet;
pGet = chain_get(qHead, nId);
node_print(pGet);
chain_remove(&qHead, &pGet);
}
void menu() {
puts("***********************");
puts("0.空链表打印");
puts("1.添加1个节点");
puts("3.添加3个节点");
puts("4.获取节点");
puts("5.打印链表");
puts("7.删除节点");
puts("8.清空节点");
puts("9.清屏");
puts("其它数字.退出");
if (NULL== qHead) {
qHead = node_new(g_id++);
puts("生成头结点");
}
puts("***********************");
}
void testMain() {
while(1) {
menu();
int nSelect = 0;
scanf("%d", &nSelect);
getchar();
switch(nSelect) {
case 0:
test0Node();
break;
case 1:
testAddNode();
break;
case 3:
test3Node();
break;
case 4:
testGetNode();
break;
case 5:
chain_print(qHead);
break;
case 7:
testRemoveNode();
break;
case 8:
chain_clear(&qHead);
break;
case 9:
system("cls");
break;
default:
return;
}
}
}
int main(int argc, char** argv) {
testMain();
return 0;
}
最新文章
- <hr> 的18种样式
- 八皇后（dfs+回溯）
- Sharepoint更新字段触发工作流(无代码)
- 迭代器、泛型和增强For
- 关于开发环境 git 重新部署
- web service client端调用服务器接口
- libevent linux安装
- 【poj解题】3664
- jquery学习总结（超级详细）
- Identity（五）
- 3D 特征点概述（2）
- day_5.21 py 高级编程
- Android Studio连接不到MuMu模拟器；
- ORA-10997:another startup/shutdown operation of this instance in progress解决方法
- 局域网传输-LED灯搭建局域网：数据传输可达每秒3Gb
- memory引擎和innodb引擎速度对比
- 凸包算法（Graham扫描法）详解
- fs 小计
- centos的nginx支持ssl
- SWIG 和 Python——c/c++与脚本交互