022+-链表基础及基本操作
本帖最后由 moc 于 2018-9-23 16:10 编辑1、链表基本概念
链表：是一种物理存储单元上非连续的存储结构，由一系列结点（链表中每一个元素称为结点）组成，结点动态生成，结点与结点之间通过指针链接。
每个结点包括两个部分：一部分是存储数据元素的数据域，另一部分是存储下一个结点地址的指针域。
链表的特点：
1 链表是一种常用的数据结构，它通过指针将一些列数据结点，连接成一个数据链。相对于数组，链表具有更好的动态性。
2 数据域用来存储数据，指针域用于建立与下一个结点的联系。
3 建立链表时无需预先知道数据总量的，可以随机的分配空间，可以高效的在链表中的任意位置实时插入或删除数据。
4 链表的开销，主要是访问顺序性和组织链的空间损失。
约定：
•头结点、当前结点、前趋结点、后继结点新建结点
•pHead、pCurrent、 pPrior、 pNext、 pMalloc
链表编程关键点：
1、指针指向谁，就把谁的地址赋给指针
2、辅助指针变量&操作逻辑的关系
2、静态链表
手工依次为各结点建立指向关系，不能动态增加或减少结点，应用范围小。
struct AdvTeacher
{
char name;
int age;
struct AdvTeacher *next;
};
struct AdvTeacher t1, t2, t3;
struct AdvTeacher *p;
t1.age = 10;
t2.age = 20;
t3.age = 30;
t1.next = &t2;//建立结点之间的指向
t2.next = &t3;
t3.next = NULL;
//遍历链表
while (p)
{
printf("age:%d\n", p->age);
p = p->next;
}
3、带头结点的单项链表
头结点作为链表的开始，第一个结点为业务结点的开始，在进行接口的封装和设计时，链表的对外属性只有指向头结点的指针，其余的操作通过封装好的函数进行。
1.创建链表
创建链表的头结点，需要在函数内申请内存空间，返回内存空间的首地址（指针函数，二级指针做输出）。
2.循环打印链表
通过辅助指针记录当前位置，在链表中循环。
3. 指定结点前插入结点，如果没找到指定结点插到最后
建立要插入的结点，建立两个辅助指针变量，一个指向当前结点，一个指向当前结点的前一个结点，循环每个结点，如果找到指定结点break，最后新结点链到当前结点，前一个结点链到新结点。
4.删除指定的结点
循环每个结点，找到指定结点后删除并返回。
5.链表的逆置操作
1.当链表只有头结点或只有一个业务结点不需要逆置，直接返回即可。
2.准备环境：p保存第一个结点，q保存第二个结点
3.从第二个结点开始操作，先缓存q的下一个结点，然后逆置（让第二个结点指向第一个结点），然后p,q各向后移一个对第三个结点做同样操作，知道q的指向NULL.
4.最后把原先的第一个结点指向NULL,头结点指向p即可。
示例代码：
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
#define _CRT_SECURE_NO_WARNINGS
typedef struct Node
{
int data;
struct Node *pNext;
}SLIST;
SLIST *Creat_SList()
{
int data = 0;
// 1建立头结点并初始化
SLIST *pHead = NULL, *pm = NULL, *pCur = NULL;
pHead = (SLIST*)malloc(sizeof(SLIST));
if (pHead == NULL)
{
return -1;
}
pHead->data = 0;
pHead->pNext = NULL;
pCur = pHead;
// 2循环建立结点，结点中的数据域由键盘输入
printf("\n Please enter the data of node(-1:quit):");
scanf("%d", &data);
while (data != -1)
{
// 不断的malloc新结点， 并为数据域赋值
pm = (SLIST*)malloc(sizeof(SLIST));
if (pm == NULL)
{
SList_Destory(pHead);
return NULL;
}
pm->data = data;
pm->pNext = NULL;
// 新结点加入链表
pCur->pNext = pm;
pCur = pm;
printf("\n Please enter the data of node(-1:quit):");
scanf("%d", &data);
}
return pHead;2.
}
//打印链表中的每一个值
int SList_Print(SLIST *pHead)
{
SLIST *pCur = NULL;
if (pHead == NULL)
{
return -1;
}
// 准配环境
pCur = pHead->pNext;
printf("\nBegin ");
while (pCur)
{
printf("%d ", pCur->data);
pCur = pCur->pNext;
}
printf("End\n ");
}
// 在结点数值为x的前面插入y,如果没找到加到最后
int SList_NodeInsert(SLIST *pHead, int x, int y)
{
SLIST *pCur = pHead, *pPre = NULL, *pTemp = NULL;
if (pHead == NULL)
{
return -1;
}
pTemp = (SLIST*)malloc(sizeof(SLIST));
if (pTemp == NULL)
{
return -2;
}
pTemp->data = y;
while (pCur) // 查找值为x结点的前一个结点
{
if (pCur->data == x)
{
break;
}
pPre = pCur;
pCur = pCur->pNext;
}
// 新结点链接到后继结点
pTemp->pNext = pPre->pNext;
// 让前驱结点链接到pTemp
pPre->pNext = pTemp;
return 0;
}
// 删除值为y的结点,如果不存在则打印删除结点不存在
int SList_NodeDel(SLIST *pHead, int y)
{
SLIST *pCur = pHead, *pPre = NULL;
if (pHead == NULL)
{
return -1;
}
while (pCur)
{
if (pCur->data == y)
{
pPre->pNext = pCur->pNext;
free(pCur);
return 0;
}
pPre = pCur;
pCur = pCur->pNext;
}
printf("值为%d结点不存在！\n", y);
}
// 链表逆置操作 //从第二个结点开始逆置
int SList_revse(SLIST *pHead)
{
SLIST *p = NULL, *q = NULL, *t = NULL;
if (pHead == NULL)
{
return -1;
}
if (pHead->pNext == NULL || pHead->pNext->pNext == NULL)
{
return 0;
}
// 准备环境
p = pHead->pNext;
q = pHead->pNext->pNext;
while (q != NULL)
{
//1. 逆置之前做个缓存
t = q->pNext;
//2.开始逆置
q->pNext = p;
//3.p,q分别后移
p = q;
q = t;
}
// 扫尾工作
pHead->pNext->pNext = NULL;
pHead->pNext = p;
return 0;
}
// 销毁整个链表
int SList_Destory(SLIST *pHead)
{
SLIST *pCur = pHead, *pTemp = NULL;
if (pHead == NULL)
{
return -1;
}
while (pCur)
{
// 缓存后继结点
pTemp = pCur->pNext;
// 删除当前结点
free(pCur);
// 当前结点下移
pCur = pTemp;
}
return 0;
}
void main()
{
SLIST *pHead = NULL;
pHead = Creat_SList();
SList_Print(pHead);
SList_NodeInsert(pHead, 20, 19);
SList_Print(pHead);
SList_NodeDel(pHead, 20);
SList_Print(pHead);
SList_revse(pHead);
SList_Print(pHead);
SList_Destory(pHead);
system("pause");
}
页:
[1]