C语言 数据结构链表的实例(十九种操作)攻略
简介
链表是一种动态数据结构,以链式存储方式让任意节点之间相互连接,链表中的每个节点包含两个部分:数据域和指针域,数据域存储节点的数据,指针域存储下一个节点的地址。链表的优点是可以动态地分配内存,其缺点是查询效率较低。
本攻略将介绍19种链表操作,其中包括创建链表、添加节点、删除节点、查找节点以及遍历链表等操作。
创建链表
创建链表需要动态分配内存,同时需要指向链表头的指针,以下是创建链表的代码:
typedef struct node{
int data;
struct node *next;
}LinkedList, *LinkedListPtr;
//创建链表
LinkedListPtr createList(){
LinkedListPtr head = (LinkedListPtr)malloc(sizeof(LinkedList));
head->next = NULL;
return head;
}
添加节点
添加节点需要在链表尾部或者指定位置插入节点,以下是添加节点的代码:
在链表尾部添加节点
//在链表尾部添加节点
void addTail(LinkedListPtr head, int data){
LinkedListPtr node = (LinkedListPtr)malloc(sizeof(LinkedList));
node->data = data;
node->next = NULL;
LinkedListPtr p = head;
while(p->next != NULL){//找到链表的尾节点
p = p->next;
}
p->next = node;
}
在指定位置插入节点
//在指定位置插入节点
void insertNode(LinkedListPtr head, int pos, int data){
LinkedListPtr node = (LinkedListPtr)malloc(sizeof(LinkedList));
node->data = data;
LinkedListPtr p = head;
int i = 0;
while(p != NULL && i < pos){//找到要插入位置的前一个节点
p = p->next;
i++;
}
if(p == NULL || i > pos){//如果节点不存在或插入位置非法,直接返回
free(node);
return;
}
node->next = p->next;
p->next = node;
}
删除节点
删除节点需要找到要删除的节点的前一个节点,将其指向要删除的节点的指针指向要删除节点的下一个节点,以下是删除节点的代码:
//删除节点
void deleteNode(LinkedListPtr head, int data){
LinkedListPtr p = head;
while(p->next != NULL && p->next->data != data){//找到要删除节点的前一个节点
p = p->next;
}
if(p->next == NULL){//如果要删除的节点不存在,直接返回
return;
}
LinkedListPtr tmp = p->next;
p->next = p->next->next;
free(tmp);//释放要删除节点的内存空间
}
查找节点
查找节点可以根据节点的位置或者节点的值查找,以下是查找节点的代码:
根据节点的位置查找
//根据位置查找节点
LinkedListPtr findNodeByPos(LinkedListPtr head, int pos){
LinkedListPtr p = head->next;
int i = 0;
while(p != NULL && i < pos){//找到要查找的节点
p = p->next;
i++;
}
return p;
}
根据节点的值查找
//根据节点的值查找节点
LinkedListPtr findNodeByData(LinkedListPtr head, int data){
LinkedListPtr p = head->next;
while(p != NULL && p->data != data){//找到要查找的节点
p = p->next;
}
return p;
}
遍历链表
遍历链表可以按顺序输出链表中的每个节点的值,以下是遍历链表的代码:
//遍历链表
void traverseList(LinkedListPtr head){
LinkedListPtr p = head->next;
while(p != NULL){//遍历链表中的每个节点
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
示例
示例1:创建链表,向链表尾部添加元素,遍历链表
LinkedListPtr head = createList();
addTail(head,1);
addTail(head,2);
addTail(head,3);
addTail(head,4);
traverseList(head);
输出结果:
1 2 3 4
示例2:创建链表,向链表中插入元素,删除链表中的元素,遍历链表
LinkedListPtr head = createList();
addTail(head,1);
addTail(head,2);
addTail(head,3);
addTail(head,4);
insertNode(head, 1, 10);
traverseList(head);
deleteNode(head, 3);
traverseList(head);
输出结果:
1 10 2 3 4
1 10 2 4
以上是链表的19种操作的攻略,可以根据需要进行修改和扩展。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C语言 数据结构链表的实例(十九种操作) - Python技术站