数据结构学习（C语言）–单链表的基本操作
#include<stdio.h>
#include<malloc.h>
//结构体声明
typedef struct Node {
int data; //数据域
struct Node * pNext; //指针域
}*pNode, Node;
//函数声明
pNode createList(); //创建链表，返回头结点指针
void ergodicList(pNode);//遍历链表中数据
bool isEmpty(pNode);//判断链表是否为空
int getListLength(pNode);//获取链表的长度
bool insertByIndex(pNode, int, int);//插入元素（在第几个位置后）
bool deleteByIndex(pNode, int, int*);//删除元素（删除第几个元素）
bool deleteByValue(pNode, int);//删除元素（删除值为多少的元素）
bool serchByIndex(pNode, int);//查找（查看第几个元素的值）
bool serchByValue(pNode, int);//查找（查看某值的元素所在位置（第一个））
void selectSort(pNode);//排序（对链表中元素进行选择排序）
pNode reverseOrder(pNode);//倒序输出所有元素
//主函数
int main(void) {
pNode pHead = NULL;
int val;
int len;
pHead = createList();//创建链表，并将头指针赋给pHead
ergodicList(pHead);//遍历链表中数据
isEmpty(pHead);//判断链表是否为空
len = getListLength(pHead);//获取链表的长度
printf_s("链表的长度为：%d\n", len);
insertByIndex(pHead, 3, 7);//在第3个结点（数据）后插入数据7
ergodicList(pHead);
printf_s("此时链表长度为：%d\n", getListLength(pHead));
deleteByIndex(pHead, 3, &val);//将第3个结点删除
ergodicList(pHead);
deleteByValue(pHead, 7);//将值为7的结点删除
ergodicList(pHead);
serchByIndex(pHead, 3);//查找第3个结点的值是多少
serchByValue(pHead, 12);//查找第一个值为12的结点位置
selectSort(pHead);//排序
ergodicList(pHead);
ergodicList(reverseOrder(pHead));//倒置并输出
return 0;
}
//函数
pNode createList() { //创建申请空间
int len;
int val;
int i;
pNode pHead; //创建头结点
pHead = (pNode)malloc(sizeof(Node)); //动态分配一个结点内存
pNode pTail = pHead; //用于挂在当前尾结点上
pTail->pNext = NULL;
printf_s("请输入要创建链表的长度:");
scanf_s("%d", &len);
for (i = 0; i < len; i++) {
printf_s("请输入第%d个结点的值：", i + 1);
scanf_s("%d", &val);
pNode pNew = (pNode)malloc(sizeof(Node));
pNew->data = val;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHead;
}
void ergodicList(pNode pHead) { //遍历链表
pNode p = pHead->pNext;
printf_s("链表中元素如下：\n");
while (p != NULL) {
printf_s("%d ", p->data);
p = p->pNext;
}
putchar('\n');
return;
}
bool isEmpty(pNode pHead) {//判断链表是否为空
if (pHead->pNext == NULL) {
printf_s("链表为空！\n");
return true;
}
else {
printf_s("链表不为空！\n");
return false;
}
}
int getListLength(pNode pHead) { //获取链表的长度
pNode p = pHead->pNext;
int len = 0;
while (p != NULL) {
len++;
p = p->pNext;
}
return len;
}
bool insertByIndex(pNode pHead, int pos, int val) { //插入数据
pNode p = pHead;
int i = 0;
if (pos<1 || pos>getListLength(pHead)) {
printf_s("您选择的插入位置不合法！\n");
return false;
}
while (i < pos) {
p = p->pNext;
i++;
}
pNode pNew = (pNode)malloc(sizeof(Node));
pNew->data = val;
pNew->pNext = p->pNext;
p->pNext = pNew;
printf_s("已将新结点插入到第%d个结点之后!\n", pos);
return true;
}
bool deleteByIndex(pNode pHead, int pos, int *val) { //删除第几个数据
int i = 0;
pNode p = pHead;
if (pos<1 || pos>getListLength(pHead)) {
printf_s("您选择的删除位置不合法！\n");
return false;
}
while (i < pos - 1) {
p = p->pNext;
i++;
}
pNode q = p->pNext;
*val = q->data;
p->pNext = q->pNext;
free(q);//释放q所指向的空间，但q指针仍是存在的
q->pNext = NULL;
printf_s("已将第%d个值为%d结点删除！\n", pos, *val);
return true;
}
bool deleteByValue(pNode pHead, int val) { //删除某特定值的数据（结点）
int pos = 0;
int i = 0;
pNode p = pHead;
while (p->data != val) {//这里的结果是p将挂在要删除的结点下面
p = p->pNext;
pos++;
}
if (pos<1 || pos>getListLength(pHead)) {
printf_s("没有您要删除的数据\n");
return false;
}
p = pHead;//将p重新挂回头结点下
while (i < pos - 1) {//定位到要删除结点的前一个结点
p = p->pNext;
i++;
}
pNode q = p->pNext;
p->pNext = q->pNext;
free(q);
q->pNext = NULL;
printf_s("已将值为%d的结点删除，其为第%d个结点\n", val, pos);
return true;
}
bool serchByIndex(pNode pHead, int pos) { //查找第几个结点的值是
int i = 0;
if (pos<1 || pos>getListLength(pHead)) {
printf_s("查找位置不合法！\n");
return false;
}
pNode p = pHead;
for (i; i < pos; i++) {
p = p->pNext;
}
printf_s("第%d个结点的值是：%d\n", pos, p->data);
return true;
}
bool serchByValue(pNode pHead, int val) { //查找第一个值为结点的位置
int pos = 0;
pNode p = pHead;
while (p->data != val) {
p = p->pNext;
pos++;
}
if (pos<1 || pos>getListLength(pHead)) {
printf_s("没有要查找的值！\n");
return false;
}
printf_s("第一个值为%d的结点为第%d个结点！\n", val, pos);
return true;
}
void selectSort(pNode pHead) {//选择排序
pNode p;
pNode q;
int t;
int i, j;
for (i = 1, p = pHead->pNext; i < getListLength(pHead); i++, p = p->pNext) {
for (j = i + 1, q = p->pNext; j < getListLength(pHead) + 1; j++, q = q->pNext) {
if (p->data > q->data) {
t = p->data;
p->data = q->data;
q->data = t;
}
}
}
printf_s("已完成排序！\n");
return;
}
pNode reverseOrder(pNode pHead) {//倒置整个链表
if (pHead == NULL || pHead->pNext == NULL)
return pHead;
pNode top = NULL;
pNode mid = pHead->pNext;
pNode end = mid->pNext;
while (1) {
mid->pNext = top;
if (end == NULL) {
break;
}
top = mid;
mid = end;
end = end->pNext;
}
pHead->pNext = mid;
return pHead;
}
运行结果：
关于倒置（倒序输出）功能的说明：
倒序输出函数的方法可以参考文章单链表反转详解（4种算法实现）