链表的基本操作(增删改查)
前提：
节点的类型：
typedef struct Node {
int id;
struct Node* next;
}SNode;
目录：
1链表的创建；
2 链表的插入；
3 链表的删除；
4 改，查；
5 链表的排序；
6 链表的翻转；
7 链表的打印；
1 链表的创建
//创建链表
SNode *CreateList() {
SNode *head = NULL;
head = (SNode*)malloc(sizeof(SNode));
head->id = -1;
head->next = NULL;
//需要一个当前节点连接新节点
SNode *pCur = head;
int data; //可要可不要，用于保存键盘输入的值
SNode *pNew = NULL; //新节点
//循环创建新节点
while (1) {
cout << "请输入节点数据域：";
scanf("%d", &data);
//若输入值为-1让他停止创建节点
if (data == -1) {
break;
}
pNew = (SNode*)malloc(sizeof(SNode));
pNew->id = data;
pNew->next = NULL;
//新节点与链表建立关系
pCur->next = pNew;
pNew->next = NULL;
//最后要将当前节点往新节点移------我漏了
pCur = pNew;
}
return head;
}
2 插入节点
1）要求：查找x,找到就创建新节点，放在该节点前；没找到就放在最后面。
void InsertList(SNode *head, int x, int y) {
//由于插入需要知道新节点的前后节点，所以在定义两个节点指针
SNode* pPre = head; //指向头结点
SNode* pCur = head->next; //指向第二个节点
//遍历寻找
while (pCur != NULL) {
//找到直接退出
if (pCur->id == x) {
break;
}
//没找到就就将两节点后移
pPre = pCur; //指向后一节点，即pCur
pCur = pCur->next; //指向后一节点，即pCur的下一节点
}
//while退出的两种情况
//1.找到退出，pCur为匹配到的节点；pPre为匹配的前一节点
//2.没找到末尾退出。 pCur为空节点NULL;pPre为最后一个节点
//但是插入的代码是一样的
SNode * pNew = (SNode*)malloc(sizeof(SNode));
pNew->id = y;
pNew->next = NULL;
pPre->next = pNew;
pNew->next = pCur;
}
2）排序(升序)后的插入，SortList()为下面讲到的排序函数。
要求：在值为x的节点前插入。
这里的插入都是按值来插。 当然你也可以按下标插入，这里不写，因为删除一会会说到。
int InsertListPro(SNode *head, int x) {
cout << "=====================" << endl;
int ret = SortList(head);
if (ret != 0) {
cout << "插入失败" << endl;
return -2;
}
PrintList(head);
//升序排序后插入
//由于插入需要知道新节点的前后节点，所以在定义两个节点指针
SNode* pPre = head; //指向头结点
SNode* pCur = head->next; //指向第二个节点
//遍历寻找
while (pCur != NULL) {
//找到直接退出
if (x < pCur->id) { //就改了这个条件和y改成x与插入相比
break;
}
//没找到就就将两节点后移
pPre = pCur; //指向后一节点，即pCur
pCur = pCur->next; //指向后一节点，即pCur的下一节点
}
//while退出的两种情况
//1.找到退出，pCur为匹配到的节点；pPre为匹配的前一节点
//2.没找到末尾退出。 pCur为空节点NULL;pPre为最后一个节点
//但是插入的代码是一样的
SNode * pNew = (SNode*)malloc(sizeof(SNode));
pNew->id = x;
pNew->next = NULL;
pPre->next = pNew;
pNew->next = pCur;
return 0;
}
3 删除节点
1）删除链表的所有节点。(当然会包括头结点)
//删除链表所有节点 需要一个保存下一个节点的临时节点tmp
int DelListall(SNode *head) {
if (head == NULL) {
cout << "链表为空." << endl;
return -1;
}
//用于统计删除节点次数
int i = 0;
while (head != NULL) {
SNode *tmp = head->next;
free(head);
head = tmp;
i++;
}
//因为也删除头结点了，所以值为显示的节点加上头结点
cout << "删除所有节点的次数：" << i << endl;
return 0;
}
2）删除表中第一个值为x的节点。
void DelListone(SNode *head, int x) {
SNode *pPre = head;
SNode *pCur = head->next;
//没找到为0，找到为1
int flag = 0;
//循环遍历查找
while (pCur != NULL) {
if (pCur->id == x) {
pPre->next = pCur->next;
free(pCur);
pCur = NULL;
cout << "找到并删除了:" << x << endl;
flag = 1;
break;
}
//没找到继续遍历
pPre = pCur; //或者PPre=pPre->next;
pCur = pCur->next;
}
//不能用pCur==NULL为判断，因为他是被删除的节点，并不会循环到尾部，而且被删除后又置为NULL
//所以用标志位
if (flag == 0) {
cout << "没找到:" << x << endl;
}
}
3）删除链表中值为x的全部节点。(与删除一个点基本一样,不退出循环就行)
void DelListX(SNode *head, int x) {
SNode *pPre = head;
SNode *pCur = head->next;
while (pCur != NULL) {
if (pCur->id == x) {
pPre->next = pCur->next;
free(pCur);
pCur = NULL;
//break 删除一个节点时的代码
//使pCur保持在pPre继续做判断
pCur = pPre->next;
//找到删除的点后，后面不需要节点后移，否则被删节点的后一节点就没做if判断
continue;
}
//没找到就继续循环
pPre = pPre->next;
pCur = pCur->next;
}
}
4)删除下标为n的节点。
void DelListPos(SNode* head, int n) {
if (head == NULL) {
return;
}
SNode* pPre = head;
SNode* pCur = pPre->next;
int count = 0; // 记录当前下标 用于和下标n比较
int falg = 0;
while (pCur != NULL) {
//先判断
if (count == n) {
pPre->next = pCur->next;
free(pCur);
pCur = NULL;
falg = 1; // 为1 说明下标n在链表范围内 否则就超过了 因为前面已经将小于0的排除
//break; 用else逻辑好点
}
else { // 不等于就继续循环
count++;
pPre = pCur;
pCur = pCur->next;
}
}
//判断是否超出链表大小
if (falg == 0) {
cout << "下标n超过了链表的大小！" << endl;
}
}
4 修改与查找值就不给出了，不难，都是遍历的问题。
5 链表的排序。(重要)
//链表排序
int SortList(SNode *head) {
#if 0
//参考选择排序
int a[] = { 2,5,1,7,6 };
int len = sizeof(a) / sizeof(int);
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (a[i] < a[j]) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
}
for (int i = 0; i < len; i++) {
cout << a[i];
}
#endif
if (head == NULL || head->next == NULL) {
cout << "无数据可排序" << endl;
return -1;
}
SNode *pData1; //指向第一个有效数据
SNode *pData2; //指向第二个有效数据
//第一个for从1有效节点循环到倒数第一个. 第二个for从第二个循环到最后一个节点
for (pData1 = head->next; pData1->next != NULL; pData1 = pData1->next) {
for (pData2 = pData1->next; pData2 != NULL; pData2 = pData2->next) {
if (pData1->id > pData2->id) {
//将节点的数据两两交换，注意不是改变指针指向
SNode tmp = *pData1;
*pData1 = *pData2;
*pData2 = tmp;
// 经过上面的赋值后，SNode 里面的next元素指向是调换了
// 所以将指向调整回来
tmp.next = pData1->next;// 先保存pData2->next的内容
pData1->next = pData2->next;// 恢复pData1->next的指向
pData2->next = tmp.next;// 恢复pData2->next的指向
}
}
}
return 0;
}
6 链表的翻转。
int ReverseList(SNode *head) {
//如果空链表或者只有头结点或者头结点+一个有效节点就不用翻转
if (head == NULL || head->next == NULL || head->next->next == NULL) {
return -1;
}
SNode *pPre = head->next;
SNode *pCur = pPre->next;
SNode *tmp = NULL;
while (pCur != NULL) { //或者写pPre->next!=NULL
//先保存pCur的下一节点再翻转
tmp = pCur->next;
pCur->next = pPre;
//翻转后pPre、pCur往后移
pPre = pCur;
pCur = tmp;
}
//最后head的next和第一个节点的next指针没做处理 pPre此时是最后一个节点即翻转后的第一个节点
head->next->next = NULL; //使第一个有效节点指向NULL
head->next = pPre; //使头结点指向最后节点
//这两个顺序不能调换,必须第一个节点的next置为NULL先,否则只输出一个节点
return 0;
}
7 最后就是链表的打印。
int PrintList(SNode *head) {
if (head == NULL) {
return -1;
}
//从有效数据第二个开始遍历
SNode *pCur = head->next;
cout << "head->";
//循环遍历链表打印
while (pCur != NULL) {
cout << pCur->id << "->";
pCur = pCur->next;
}
cout << "NULL" << endl;
return 0;
}
总结上面的代码：
1）所有的操作基本上都是基于遍历链表来进行的。
2）这里只有链表的翻转和链表的排序用到三个临时节点。当然，如果你有更好的方法，用两个节点实现也是可以的。
