C高级编程 第九天（链表）

目录

1.数组

2.链表

3.链表的分类

3.1静态链表（栈）

3.2 动态链表（堆）

3.3单向链表、双向链表、单向循环链表、双向循环链表

4.带头节点的链表

5.链表的操作

①初始化链表

②插入节点

③删除节点

④释放链表

⑤销毁链表

1.数组

优点：

• 访问速度快；
• 每个元素占用空间少。

缺点：

• 一旦分配内存，不可以动态扩展；
• 分配过多内存，会造成资源浪费；
• 头部插入，删除效率低。

2.链表

struct LinkNode
{int num;struct LinkNode* next;
}

结点是由数据域和指针域构成的

3.链表的分类

3.1静态链表（栈）

//静态链表，在栈上
void test_staticLinkNode()
{//声明好每个节点struct LinkNode node1 = { 10,NULL };struct LinkNode node2 = { 20,NULL };struct LinkNode node3 = { 30,NULL };struct LinkNode node4 = { 40,NULL };struct LinkNode node5 = { 50,NULL };//建立节点之间的关系node1.next = &node2;node2.next = &node3;node3.next = &node4;node4.next = &node5;node5.next = NULL;//链表的首节点struct LinkNode* begin = &node1;//遍历链表while (begin != NULL){printf("%d\n", begin->num);begin = begin->next;}
}

3.2 动态链表（堆）

//动态链表在堆上
void test_dynamicLinkNode()
{//创建节点struct LinkNode* node1 = malloc(sizeof(struct LinkNode));struct LinkNode* node2 = malloc(sizeof(struct LinkNode));struct LinkNode* node3 = malloc(sizeof(struct LinkNode));struct LinkNode* node4 = malloc(sizeof(struct LinkNode));struct LinkNode* node5 = malloc(sizeof(struct LinkNode));//给节点赋值，并创建关系node1->num = 10;node1->next = node2;node2->num = 20;node2->next = node3;node3->num = 30;node3->next = node4;node4->num = 40;node4->next = node5;node5->num = 50;node5->next = NULL;//链表的首节点struct LinkNode* begin = node1;//遍历链表while (begin != NULL){printf("%d\n", begin->num);begin = begin->next;}
}

3.3单向链表、双向链表、单向循环链表、双向循环链表

4.带头节点的链表

头节点只维护指针域，不维护数据域

5.链表的操作

①初始化链表

void initLinkList()
{//头节点struct LinkNode* pheader = malloc(sizeof(struct LinkNode));//尾节点struct LinkNode* ptail = malloc(sizeof(struct LinkNode));pheader->num = -1;pheader->next = NULL;ptail = pheader;while (1){int number = -1;scanf("%d", &number);if (-1 == number){//以-1作为结束标志break;}struct LinkNode* node = malloc(sizeof(struct LinkNode));node->num = number;node->next = NULL;//尾结点向后移动ptail->next = node;ptail = node;}
}

②插入节点

//在oldValue后插入newVal
void insert_LinkList2(struct LinkNode* pHeader, int oldValue, int newVal)
{if (NULL == pHeader){return;}struct LinkNode* pPrev = pHeader;struct LinkNode* pCurrent = pHeader->next;while (pCurrent != NULL){if (pCurrent->num == oldValue){break;}//两个辅助指针向后移动pPrev = pCurrent;pCurrent = pCurrent->next;}struct LinkNode* newNode = malloc(sizeof(struct LinkNode));newNode->num = newVal;newNode->next = NULL;newNode->next = pCurrent;pPrev->next = newNode;
}

③删除节点

void delete_LinkList(struct LinkNode* pHeader, int delue)
{while (NULL != pHeader){//要删除节点的前置节点struct LinkNode* pPrev = pHeader;//要删除的当前节点struct LinkNode* pCurrent = pHeader->next;if (NULL != pCurrent){if (delue == pCurrent->num){pPrev->next = pCurrent->next;}//两个辅助指针向后移动pPrev = pCurrent;pCurrent = pCurrent->next;}else{printf("没有找到要删除的节点");}}return;
}

④释放链表

void clear_LinkList(struct LinkNode* pHeader)
{while (NULL == pHeader){return;}struct LinkNode* node = pHeader->next;if (NULL != node){//先记录下一个节点的位置struct LinkNode* nodeNew = node->next;//释放当前节点free(node);//当前节点向后移动node = nodeNew;}pHeader->next = NULL;free(pHeader);
}

⑤销毁链表

void destroy_LinkList(struct LinkNode* pHeader)
{if (NULL == pHeader){return;}clear_LinkList(pHeader);free(pHeader);pHeader = NULL;
}