链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
- 链表结构在逻辑上是连续的，但是在物理上不一定是连续的
- 现实中的结点一般都是从堆上申请出来的
- 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
链表分类
简单分类来讲，我们把链表的属性分为以下三种：
- 单向或者双向
- 有头或者无头
- 循环或者非循环
根据2^3=8推出链表一共分为8种类型，而在这8种链表中最常见的是：
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。
有头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。
链表的实现
单向无头非循环链表
假设我们需要创建一个由个人信息组成的链表。
第一步：先创建关于person的结构体，并将其包含在listNode链表对象之中作为成员。
struct person {
char name[10];
int year;
char sex;
};
struct listNode {
person info;
listNode* next;
};
第二步：为listNode提供操作函数
/*
开辟内存
*/
list* createList(person info) {
/*
不直接使用malloc分配内存
listNode l;
l.info = info;
l.next = NULL;
return &l;
*/
listNode* l = (listNode*)malloc(sizeof(listNode));
l->info = info;
l->next = NULL;
return l;
}
/*
尾部插入
*/
void pushback(person info, listNode** head) {
listNode* add = createList(info);
if (*head == NULL) {
*head = add;
}
else {
listNode* tail = *head;
while (tail->next != NULL) {
tail = tail->next;
}
tail->next = add;
}
}
/*
头部插入
*/
void pushfront(person info, listNode** head) {
listNode* add = createList(info);
if (*head == NULL) {
*head = add;
}
else {
add->next = *head;
*head = add;
}
}
/*
尾部删除
*/
void popback(listNode** head) {
if (*head != NULL) {
listNode* temp = *head;
listNode* prev = temp;
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
prev->next = NULL;
free(temp); //释放内存
temp = NULL;
}
}
/*
头部删除
*/
void popfront(listNode** head) {
if (*head != NULL) {
listNode* temp = *head;
*head = (*head)->next;
free(temp);
temp = NULL;
}
}
/*
打印链表
*/
void printList(listNode* head) {
assert(head != NULL); //断言assert(0) 则abort();退出
while (head != NULL) {
printf("%s %d %c\n", head->info.name, head->info.year, head->info.sex);
head = head->next;
}
}
第三步：在main函数中操作链表
int main() {
person p = { "XiaoMing",8,'M' };
person p2 = { "XiaoHong",8,'F' };
person p3 = { "XiaoGang",8,'M' };
listNode* l = NULL;
pushback(p, &l);
pushback(p2, &l);
pushback(p3, &l);
pushfront(p3, &l);
popfront(&l);
popback(&l);
printList(l);
}
Output:
XiaoMing 8 M
XiaoHong 8 F
双向有头循环链表
现在我们创建班级的双向有头循环链表。
第一步：构造cls结构体，并对cls重载符号==函数（在后面进行Search操作时会用到）。并将cls包含在我们的listNode链表结构体内。
struct cls {
int id;
int memnum;
//重载==符号函数
bool operator == (const cls& clazz) {
return clazz.id == this->id && this->memnum == clazz.memnum;
}
};
struct listNode {
cls clazz;
listNode* pre;
listNode* next;
};
第二步：为listNode提供操作函数，具体作用查看注释。
/*
申请空间
*/
listNode* createList(cls clazz) {
listNode* node = (listNode*)malloc(sizeof(listNode));
node->clazz = clazz;
return node;
}
/*
初始创建链表头节点
*/
listNode* headInit(void) {
listNode* head = createList(cls{0,0});
head->next = head;
head->pre = head;
return head;
}
/*
查询cls对应节点
*/
listNode* listSearch(listNode** list, cls clazz) {
listNode* pos = *list;
while (!(pos->clazz == clazz)) {
pos = pos->next;
if (pos == *list) {
return NULL;
}
}
return pos;
}
/*
删除指定cls节点
*/
void listErase(listNode* list, cls clazz) {
listNode* pos = listSearch(&list,clazz);
pos->pre->next = pos->next;
pos->next->pre = pos->pre;
free(pos);
}
/*
头插
*/
void pushFront(listNode** head,cls clazz) {
assert(*head != NULL);
listNode* node = createList(clazz);
listNode* phead = (*head)->next; //头节点后的第一位单元
phead->pre = node;
(*head)->next = node;
node->next = phead;
node->pre = *head;
}
/*
尾插
*/
void pushBack(listNode** head, cls clazz) {
listNode* ptail = (*head)->pre;
listNode* node = createList(clazz);
ptail->next = node;
node->pre = ptail;
node->next = *head;
(*head)->pre = node;
}
/*
头删
*/
void popFront(listNode** head) {
assert(*head != NULL);
listErase(*head,(*head)->next->clazz);
}
/*
尾删
*/
void popBack(listNode** head) {
assert(*head != NULL);
listErase(*head, (*head)->pre->clazz);
}
/*
指定cls前插入
*/
void insert(listNode** head,cls clazz) {
listNode* node = createList(clazz);
listNode* pos = listSearch(head, clazz);
pos->pre->next = node;
node->pre = pos->pre;
pos->pre = node;
node->next = pos;
}
/*
打印链表
*/
void listPrint(listNode* head) {
assert(head != NULL);
listNode* phead = head->next;
while (phead != head) {
printf("Class:%d Mem:%d\n", phead->clazz.id, phead->clazz.memnum);
phead = phead->next;
}
}
第三步：在main函数中进行操作测试。
int main() {
cls c1 = { 1,50 };
cls c2 = { 2,60 };
cls c3 = { 3,40 };
cls c4 = { 4,40 };
listNode* list = headInit();
printf("==================\n尾插\n");
pushBack(&list, c1);
pushBack(&list, c2);
listPrint(list);
printf("==================\n头插\n");
pushFront(&list, c3);
pushFront(&list, c4);
listPrint(list);
printf("==================\n删c1\n");
listErase(list, c1);
listPrint(list);
printf("==================\n头删\n");
popFront(&list);
listPrint(list);
printf("==================\n尾删\n");
popBack(&list);
listPrint(list);
}
Output:
==================
尾插
Class:1 Mem:50
Class:2 Mem:60
==================
头插
Class:4 Mem:40
Class:3 Mem:40
Class:1 Mem:50
Class:2 Mem:60
==================
删c1
Class:4 Mem:40
Class:3 Mem:40
Class:2 Mem:60
==================
头删
Class:3 Mem:40
Class:2 Mem:60
==================
尾删
Class:3 Mem:40
小结
因其长度可变，内存不连续等优点，链表的运用将极大提高对多个同一结构的操作效率。
