单链表基本操作总结

链表基本概念：
链表：线性表的链式存储。
数据域：存储数据信息。即数据。
指针域：存放下一节点的位置信息。即该指针指向下一节点。单链表：每一个节点node：一个数据域 + 一个指针域。
头节点：
1、数据域可以存放线性表长度等公共信息。
2、指针域，指向第一个节点（数据域）的位置。
3、头结点不一定是链表的必须元素。不过有了头结点，对第一个元素节点前插入和删除元素，就和其它节点一致了。
4、头结点是为了操作的同一和方便设立的，其数据域一般无意义，也可存放链表长度。
头指针：指向第一个结点的指针。
最后一个节点：数据域存放数据；指针域为空，即NULL。
若线性表为空，则头节点的指针域为空。
// 循环链表：将单链表中的终端节点的指针由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表简称循环链表。
// 双向链表：是在单链表的每个节点中，再设置一个指向其前驱节点的指针域。单链表基本操作有：创建、输出、测长、插入、删除、逆置、排序等。单链表结构定义代码：typedef struct Node{int data;struct Node *next;}ListNode;创建单链表操作：

/**创建链表*/ListNode * Create_list（int n） // 注意这里函数返回值为一个指向Node的指针，n表示几个节点{int elem,i;i = 1;ListNode *head, *current, *temp; /*current：代表一个当前节点，它的下一节点是你正要创建的；temp：代表你正要创建的节点。*/head = new ListNode;head->next = NULL;head->data = n;current = head;while（i <= n） /*尾插法：即新节点放在尾部*/{cout << "please input elem: " << endl;cin >> elem;temp = new ListNode;temp->data = elem;temp->next = NULL;current->next = temp;current = temp;i++;}return head;}

输出操作：

/**输出链表*/int Output_list（ListNode *head）{ListNode *p;p = head->next;if（p == NULL）{cout << "The List is NULL" << endl;return 0;}do{cout << p->data << " ";p = p->next;}while（p ！= NULL）; // 这里需要加“；”cout << endl;return 0;}

测一个链表的节点数，即长度：

/**测长度*/int Length_test（ListNode *head）{ListNode *p;int i = 0;p = head->next;while（p ！= NULL）{i++;p = p->next;}cout << "The length of list is " << i << endl;return 0;}

插入节点操作：

/**在第i个节点后插入一个节点，elem：表示你要插入的数据*/ListNode * Insert_node（ListNode *head,int elem,int i）{int j = 0;ListNode *p,*temp;temp = head->next;/*错误写法while（NULL ！= temp） 在找到 j 后没有跳出循环{j++;if（j <= i）temp = temp->next;}*/while（NULL ！= temp）{j++;if（j >= i） /**指针停在第i个节点之前*/break;temp = temp->next;}if（temp == NULL）{cout << "There is no i" << endl;return head;}p = new ListNode;p->data = elem;p->next = temp->next;temp->next = p;head->data = head->data + 1; /**插入一个结点，头结点数据保存的链表长加一*/return head;}

删除操作：

/**删除第i个结点*/ListNode * Delete_node（ListNode *head,int i）{int j = 0;ListNode *temp,*pre_temp;temp = head->next;while（NULL ！= temp）{j++;if（j >= i）break;pre_temp = temp; /**保存之前节点*/temp = temp->next;}if（temp == NULL）{cout << "There is no i" << endl;return head;}pre_temp->next = temp->next;/**这里不能写成temp = temp->next; 因为下面有 delete temp;会将后面的节点删掉*/delete temp;head->data -= 1; /**删掉一个结点，头结点数据保存的链表长减一*/return head;}

逆置操作：

/**单链表逆置，将头结点后的节点一个个断开，使用头插法插入在头结点后*/ListNode * Reverse_list（ListNode *head）{if（NULL == head）return head;if（NULL == head->next）return head;if（NULL == head->next->next）return head;/**要实现逆置，除了头结点外，至少需要2个数据节点*/ListNode *curr, *temp;curr = head->next;/**curr用来保存断开后的那一串*/head->next = NULL;/**头结点与后面结点断开*/while（NULL ！= curr）{temp = curr->next; /**temp起临时代替curr的作用*/curr->next = head->next; /**头插法*/head->next = curr;curr = temp; /**temp将功能还给curr*/}return head;}

单链表排序（使用冒泡排序法）：此排序算法，仅交换了数据，没有交换结点

void Swap_data（int &a,int &b） /**这里必须要加引用符，不然交换没效果*/{int temp;temp = a;a = b;b = temp;}ListNode * Sort_list（ListNode *head）{int i,len;ListNode *p;len = head->data;p = head->next;if（NULL == p）cout << "list is null" << endl;for（i = 1; i <= len; i++）{while（NULL ！= p->next）{if（p->data > p->next->data）Swap_data（p->data,p->next->data）;p = p->next;}p = head->next;}return head;}

一个特别的函数：用于找出单链表中间节点，在不知道节点总数的情况下

/**不知节点总数，只遍历一次就可以求出中间结点*//**这个函数有问题，只能对节点为奇数的求解，节点为偶数时，会出现p->next->next无意义的情况，使程序发生错误*//*原理是：找两个指针，一个每次走一步，另一个每次走两步，当走两步的指针到结尾时，走一步的指针刚好走到中间结点处*/void Search_mid（ListNode *head）{ListNode *p_1,*q_2;ListNode *mid;p_1 = head->next;q_2 = head->next;while（NULL ！= q_2->next）{p_1 = p_1->next;q_2 = q_2->next->next;mid = p_1;}cout << "中间值为: " << mid->data << endl;}

测试主函数：

int main（）{ListNode *p;int a=3;int b = 4;p = Create_list（5）;cout << "The list is:" << endl;Output_list（p）;Length_test（p）;p = Insert_node（p,6,5）;cout << "插入节点后:" << endl;Output_list（p）;cout << "New length: " << p->data << endl;p = Delete_node（p,3）;cout << "删除节点后:" << endl;Output_list（p）;p = Reverse_list（p）;cout << "逆置后:" << endl;Output_list（p）;p = Sort_list（p）;cout << "排序后（从小到大）:" << endl;Output_list（p）;cout << "原ab: " << a << b << endl;Swap_data（a,b）;cout << "交换后: " << a << b << endl;Search_mid（p）;return 0;}

本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-07/119767.htm