8 单链表---带表头节点

上节课所学的顺序表的缺点

请添加图片描述
顺序表的最大问题：插入和删除时需要移动大量元素

链式存储的定义

请添加图片描述

链式存储的逻辑结构

请添加图片描述

链表中的基本概念：

请添加图片描述
注意：表头节点并不属于数据元素

单链表图示：

请添加图片描述

把3个需要的结构体定义出来：

请添加图片描述

typdef struct _tag_LinkList{LinkListNode header; //指针域int length; //单链表的长度
}TLinkList

获取第pos个元素

请添加图片描述

插入元素到pos位置

请添加图片描述

请添加图片描述

注意：新的链表形成之前，旧的链表不能断

删除元素：

请添加图片描述

请添加图片描述

一定要注意：index是从0开始还是从1开始【程序员永恒问题】

代码实现—单链表—带表头节点—头插法

linklist.c

#include "LinkList.h"typedef struct _tag_LinkList
{LinkListNode* header;//头指针int length;//单链表的长度
}TLinkList; //类型：即代表头结点，又代表整个单链表LinkList* LinkList_Create() {TLinkList* ret = (TLinkList*)malloc(sizeof(TLinkList));if (ret) {ret->length = 0;ret->header = NULL;}
}void LinkList_Destory(LinkList* list) {free(list);
}void LinkList_Clear(LinkList* list) {((TLinkList*)list)->length = 0;
}int LinkList_Length(LinkList* list) {return ((TLinkList*)list)->length;
}int LinkList_Insert(LinkList* list, LinkListNode* node, int pos) {TLinkList* tll = (TLinkList*)list;int i = 0;int ret = -1;ret = (tll != NULL) && (pos >= 0) && (node != NULL);if (ret) {LinkListNode* current = (LinkListNode*)tll;//移动current指针到pos位置for (i=0; (i<pos)&&(current->next!=NULL); i++){current = current->next;}//关键node->next = current->next;current->next = node;tll->length++;}return ret;
}LinkListNode* LinkList_Get(LinkList* list, int pos) {TLinkList* tll = (TLinkList*)list;LinkListNode* ret = NULL;int i = 0;if ((tll != NULL) && (pos >= 0) && pos < tll->length) {LinkListNode* current = (LinkListNode*)tll;for (i=0;i<pos;i++){current = current->next;}ret = current->next;}return ret;
}LinkListNode* LinkList_Delete(LinkList* list, int pos) {TLinkList* tll = (TLinkList*)list;LinkListNode* ret = NULL;int i = 0;if ((tll != NULL) && (pos >= 0) && pos < tll->length) {LinkListNode* current = (LinkListNode*)tll;for (i = 0; i < pos; i++){current = current->next;}ret = current->next;current->next = ret->next;tll->length--;}return ret;
}

linklist.h

#pragma once
#pragma once
#include <stdio.h>typedef void LinkList;
//定义包含指针next的结构体
typedef struct _tag_LinkListNode LinkListNode;
typedef struct _tag_LinkListNode
{LinkListNode*  next;
};/*
该方法用于创建并且返回一个空的线性表
*/
LinkList* LinkList_Create();/*
该方法用于销毁一个线性表LinkList
*/
void LinkList_Destory(LinkList* list);/*
该方法用于将一个线性表LinkList中的所有元素清空
使得线性表回到创建时的初始状态
*/
void LinkList_Clear(LinkList* list);/*
该方法用于返回一个线性表LinkList中的所有元素个数
*/
int LinkList_Length(LinkList* list);int LinkList_Capacity(LinkList* list);/*
该方法用于向一个线性表LinkList的pos位置处插入新元素node
返回值为1表示插入成功，0表示插入失败
*/
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);/*
该方法用于获取一个线性表LinkList的pos位置处的元素
返回值为pos位置处的元素，NULL表示获取失败
*/
LinkListNode* LinkList_Get(LinkList* list, int pos);/*
该方法用于删除一个线性表LinkList的pos位置处的元素
返回值为被删除的元素，NULL表示删除失败
*/
LinkListNode* LinkList_Delete(LinkList* list, int pos);

main.c


#include "LinkList.h"//普通节点的结构体
struct Value
{LinkListNode* header; //指针域int v;//数据域
};
int main() {int i = 0;LinkList* list = LinkList_Create();struct Value v1;struct Value v2;struct Value v3;struct Value v4;struct Value v5;v1.v = 1;v2.v = 2;v3.v = 3;v4.v = 4;v5.v = 5;//头插法LinkList_Insert(list, (LinkListNode*)&v1, 0);LinkList_Insert(list, (LinkListNode*)&v2, 0);LinkList_Insert(list, (LinkListNode*)&v3, 0);LinkList_Insert(list, (LinkListNode*)&v4, 0);LinkList_Insert(list, (LinkListNode*)&v5, 0);for (i = 0; i < LinkList_Length(list); i++){struct Value* pv = LinkList_Get(list, i);printf("%d\n", pv->v);}while (LinkList_Length(list) >0){struct Value* pv = LinkList_Delete(list, LinkList_Length(list) - 1);printf("%d\n", pv->v);}LinkList_Destory(list);return 0;
}