数据结构之链表（一）

链表的应用

链表的数据结构定义链表链表操作1. 查找元素2. 插入元素3.删除元素

链表的数据结构

以下是带头结点的链表，数据结构较为简单，这里不再赘述。

定义链表

#include <stdio.h> #include <stdlib.h> struct node{ int data; node* next; }; // 创建链表 node* create(int Array[]){ node *p, *pre, *head; head = new node; head->next = NULL; pre = head; for(int i=0; i<5;i++){ p = new node; p->next = NULL; p->data = Array[i]; pre->next = p; pre = p; } return head; } // 显示链表（带头结点）中的元素 void show(node* p){ p = p->next; while(p != NULL){ printf("%d", p->data); p = p->next; } } int main(){ int Array[5] = {1, 2, 3, 4, 5}; node* L = create(Array); show(L); return 0; }

链表操作

1. 查找元素

需要知道寻找元素的值需要知道链表的头结点需要知道怎样查找 // 显示链表（带头结点）中的元素 void show(node* p){ p = p->next; while(p != NULL){ printf("%d", p->data); p = p->next; } } //查找链表元素,返回链表中目标元素x的个数 int search1(node *head, int x){ int count = 0; node *p = head->next; while(p->next != NULL){ if(p->data == x){ count++; } p = p->next; } return count; }

2. 插入元素

需要知道插入元素的位置需要知道插入元素的值插入元素的顺序问题一定要清楚 如果先p->next = q，会造成p的下一个元素指针丢失问题，这样q的下一个就没法连接上了 void insert(node* head, int pos, int x){ node* p = head; for(int i=0; i<pos-1; i++){ p = p->next; } node* q = new node; q->data = x; q->next = p->next; p->next = q; } int main(){ insert(L, 2, 6); show(L); return 0; }

3.删除元素

需要知道链表的引用（head）考虑如果删除最后一个结点的情况 建立pre和p指针，p是要被删除的结点，pre是被删除节点的前驱结点pre和p两个指针不断向后移动，直到p到位（前提是p不为NULL，如果NULL就无法删除p了）执行pre->next = p->next，p节点就被忽略（删除）了 //删除元素 void del(node* head, int pos){ node* pre = head; node* p = head->next; for(int i=0; i<pos-1 && p!=NULL ; i++){ p = p->next; pre = pre->next; } pre->next = p->next; delete(p); //可加可不加，delete方法用来撤销指针。 }