数据结构——单链表

目录1、链表的定义2、链表的分类1、不带头结点的单向不循环链表2、带头结点的单向不循环链表3、不带头结点单向循环链表4、带头结点的单向循环链表5、不带头结点的双向不循环链表6、带头结点的双向不循环链表7、不带头结点的双向循环链表8、带头节点的双向循环链表链表的结构1、结构2、创造一个节点3、初始化链表4、求链表长度5、打印链表6、查找元素根据数值查找根据下标查找7、插入根据下标插入头插尾插8、删除根据下标删除头删尾删9、销毁前言上次介绍了一种数据的存储结构——顺序表但是他会有缺陷当我们要插入元素和申请空间的时候一般情况下后扩容原来的2倍但是不一定每一个空间都装数据这样会造成空间的浪费而且进行插入和删除的时候对应实现的接口的时间复杂的位ON效率第因此一些大佬有发明了一个链表。下面是单链表的介绍。1、链表的定义链表Linked List是一种线性表由一系列节点Node组成每个节点包含数据域和指针域节点之间通过指针链接在一起。2、链表的分类链表的分类有很多种如下主要看他三个方面是否单向是否带头结点是否循环这样就有了八种链表。注意节点现代和结点偏传统这两种叫法都可以。下面是链表的具体情况在介绍链表的具体情况之前先区分一下头结点和头指针头结点也称为哨兵位他和普通的节点在结构上是一样的也分为数值域和指针域只不过他的数值域不存储有效数据然后他的指针域指向的是第一个有效节点的地址。头指针他仅仅是一个结构体类型的指针用于存储节点的地址他是链表最开始的部分。1、不带头结点的单向不循环链表2、带头结点的单向不循环链表3、不带头结点单向循环链表4、带头结点的单向循环链表5、不带头结点的双向不循环链表6、带头结点的双向不循环链表7、不带头结点的双向循环链表8、带头节点的双向循环链表链表的结构下面是对有头结点的不循环单链表的介绍1、结构//List.h #include stdio.h #include stdlib.h #include stdbool.h #include assert.h typedef int LDataType; //定义数值域存放的是int的类型的变量利用LDataType代替方便对数值域的类型进行修改 typedef struct ListNode { LDataType data; // 存储数据 struct ListNode* next; // 存放后继结点地址 }LNode, *LinkList;这里对LDataType进行重命名以至于对链表数值的存储方便修改更具有普适性。定义结构体变量需要注意这里的struct ListNode* next不能写成LNode*或者是*LinkList因为这里next是在重命名之前的。还要知道这里有一个typedef和结构体的知识struct ListNodeLNode; struct ListNode**LinkList2、创造一个节点List.h //创造一个新的节点节点的数值域是data LNode* BuyListNode(int data); //List.c //创造一个新的节点节点的数值域是data LNode* BuyListNode(int data) { LNode* newNode (LNode*)malloc(sizeof(LNode*)); if (newNode NULL) { printf(malloc创建空间失败); exit(-1); } newNode-data data; newNode-next NULL; return newNode; }这里创造完节点之后要判空而且要把节点的next置为空防止野指针还要返回节点的地址是为了能让链表之间的节点连起来。3、初始化链表//List.h LNode* ListInit(); //List.c LNode* ListInit() { LNode* node BuyListNode(-1);//头结点,初始化完了之后只有他一个 return node; }这里初始化的是有头结点的链表随便给他一个-1的值4、求链表长度int ListSize(LNode* L) { assert(L);//L是头结点 int size 0; LNode* cur L-next;//第一个有效节点 while (cur)//从第一个有效节点开始这样也是遍历有头结点单链表的代码 { size; cur cur-next; } return size; }这里涉及到一个遍历链表的循环cur是第一个有效节点0开始。5、打印链表//List.h void ListPrint(LNode* L) //List.c //打印链表 void ListPrint(LNode* L) { assert(L); LNode* cur L-next;//第一个有效节点,这里的L是哨兵位头结点数值域不放东西 while (cur) { printf(%d-,cur-data); cur cur-next; } printf(NULL\n); }6、查找元素根据数值查找//获取第一个节点为x的链表并返回其地址 LNode* ListLocateElem(LNode* L, LDataType x) { assert(L); LNode* cur L-next; while (cur)//遍历一个一个比较 { if (cur-data x) { return cur; } cur cur-next; } return NULL; }通过一个一个的比对查找根据下标查找//获取下标是i的节点并且返回其地址 LNode* ListGetElem(LNode* L, int i) { assert(L); assert(i 0); int j 0; LNode* iNode L-next; while (iNodeji) { j; iNode iNode-next; } return iNode; }7、插入根据下标插入//在下标为i的节点处插入一个节点 LNode* ListInsert(LNode* L, int i) { assert(L); assert(i 0); int j -1;//从头结点开始不然头插不了 LNode* i_1Node L; while (i_1Node j i-1) { i_1Node i_1Node-next; j; } assert(i_1Node);//先判断是否符合是空的 LNode* newNode BuyListNode(30);//再来创造新的节点如果顺序打乱可能创造了节点没有连接形成野指针 newNode-next i_1Node-next; i_1Node-next newNode; return newNode; }链表的插入很容易错因为进行头插的时候要从头结点开始遍历而不是从第一个有效节点开始不然覆盖不了所有节点。还有当插入链表的时候一定要先修改新节点的next,也就是从后面开始修改再将i_1Node的next和newNode进行连接防止找不到后面的节点。头插//头插,数值是x void ListPushFront(LNode* L, LDataType x) { assert(L); LNode* newNode BuyListNode(x); newNode-next L-next; L-nextnewNode; }尾插//尾插,数值是x void ListPushBack(LNode* L, LDataType x) { assert(L); LNode* newNode BuyListNode(x); newNode-next NULL; // 情况1空链表 if (L-next NULL) { L-next newNode; return; } // 情况2非空链表 LNode* cur L-next; while (cur-next ! NULL) { cur cur-next; } cur-next newNode; }这里要判断一下是否是空表8、删除根据下标删除//在下标为i的节点处删除一个节点,返回该节点处的值 LDataType ListDelete(LNode* L, int i) { assert(L); assert(i0); int j -1; LNode* i_1Node L; while (i_1Node j i-1 ) { i_1Node i_1Node-next; j; } assert(i_1Node i_1Node-next); LNode* iNode i_1Node-next; LDataType x iNode-data; i_1Node-next iNode-next; free(iNode); return x; }这里同理的要注意一下头指针在进行删除第一个有效节点的时候同样从头结点开始头删//头删并且返回删除的值 LDataType ListPopFront(LNode* L) { assert(L); assert(L-next); LNode* first L-next; LDataType x first-data; L-next first-next; free(first); first NULL; return x; }尾删//尾删,返回删除的值 LDataType ListPopBack(LNode* L) { assert(L); assert(L-next); LNode* prev L; LNode* cur L-next; while (cur-next) { prev cur; cur cur-next; } LDataType x cur-data; free(cur); prev-next NULL; return x; }9、销毁//销毁链表 void ListDestroy(LNode* L) { assert(L); LNode* cur L; while (cur) { LNode* next cur-next; free(cur); cur next; } }这里不用置空是因为是局部变量会销毁的。