链表的每一个结点中只包含一个指针域
优点 : 储存空间利用高效
举例来说:
typedef struct student{ int id; //学生编号 char* name; //学生名称 //指向下一结点的指针 struct Student* pNext; }Student;
与之相反的是多链表
typedef struct student{ int id; //学生编号 char* name; //学生名称 //指向下一结点的指针 struct Student* pNext; struct Student* qNext; }Student;
1.定义数据元素
//定义数据元素 typedef struct student{ int id; char* name; }ElementType;
2.定义顺序表结构
typedef struct { ElementType dates[MAX_SIZE]; //当前顺序表中的数据集合 int length; //当前顺序表中的元素个数 }SeqList;
3.定义链表的结点(包括数据域和指针域)
typedef struct Node { ElementType date; //数据域 struct Node* node; //指针域,指向下一个结点 }Node;
4.设置头结点
我们在定义链表时,习惯性的会定义头结点,以便统一链表结点的插入和删除操作
typedef struct Linklist { Node* next; //头指针 int length; }Linklist;
如果链表有头结点,next就指向头结点,没有就指向第一个结点
链表的长度初始值为0
在第i个结点后插入数据元素
1.创建空节点并为数据域赋值
//创建空节点并为数据赋值 Node* node = (Node*)malloc(sizeof(Node)); node -> date = element; node -> next = NULL;
2.通过循环找到要插入的结点
for (int i = 1; currNode && i < pos - 1; i++) { currNode = currNode->next; }
3.将结点插入并对接前面的结点
if (currNode) { node->next = currNode->next; currNode->next = node; linkList->length++; }
void InitLinkList(LinkList* linkList, ElementType* dateArrar, int length) { for (int i = 0; i < length; i++) { InsertLinkList(linkList, i + 1, dateArrar[i]); } }
void PrintLinkList(LinkList* linklist) { Node* node = linklist->next; if (!node) { printf("链表为空!\n"); linklist->length = 0; return 0; } for (int i = 0; i < linklist->length; i++) { printf("%d\t%s\t\n", node->date.id, node->date.name); node = node->next; } }
int IsLinkListEmpty(LinkList* linkList) { return linkList->length == 0 ? TRUE : FALSE; }
if (pos == 1) { node = linkList->next; if (node) { element = node->date; linkList->next = node->next; free(node); //释放被删除的结点 linkList->length--; } return element; }
Node* preNode; //前缀结点 node = linkList->next; for (int i = 1; node && i < pos; i++) { preNode = node; node = node->next; } if (node) { element = node->date; preNode->next = node->next; free(node); linkList->length--; } return element;
ElementType DeleteLinkListElement(LinkList* linkList, int pos) { ElementType element; //被删除的元素 element.id = -999; //赋一个不可能的值,来判断删除是否成功 Node* node = NULL; if (pos == 1) { node = linkList->next; if (node) { element = node->date; linkList->next = node->next; free(node); //释放被删除的结点 linkList->length--; } } Node* preNode; //前缀结点 node = linkList->next; for (int i = 1; node && i < pos; i++) { preNode = node; node = node->next; } if (node) { element = node->date; preNode->next = node->next; free(node); linkList->length--; } return element; }
void CleatLinkList(LinkList* linkList) { Node* node = linkList->next; Node* nextNode; while (node) { nextNode = node->next; //先记录当前结点的下一个结点,以便释放当前结点的内存 free(node); node = nextNode; } linkList->next = NULL; linkList->length = 0; }