C语言.链表.学习笔记.doc

C语言.链表.学习笔记链表的插入节点的小程序，其原理与删除节点的差不多。都是首先要找到欲处理的节点。插入节点的情况有3种，即所谓的头节点，尾节点和中间节点。1.头节点的处理：将节点插入在链表第一个元素前面，只要将新建立的节点指针指向链表的第一个节点就可以了。2.尾节点的处理：将节点插入在链表的最后一个元素后面，将尾节点的指针指向新建立的节点，然后将新建立的节点指向NULL位置。3.中间节点的处理：将节点插入在链表中间的任意位置，比如有p，q2个节点（p在前），则需将新建立的节点指向q，将p指向新建立的节点。在下面的程序中还用到了冒泡排序法。不要小瞧这个冒泡排序哦。据说GOOGLE的笔试题中一个冒泡就能让60%的人回家。好了，下面贴出程序。#include#includestruct list/定义链表的结构，方法很固定，熟记int data;struct list *next;typedef struct list node;typedef node *link;link create_list(int array,int num)/创建链表，以数组和元素个数作为形参变量link tmp1,tmp2,pointer;/pointer指针始终指向该链表，tmp1和tmp2指针用来将数组元素输入到节点中int i;pointer=(link)malloc(sizeof(node);/首先分配地址空间pointer-data=array0;/输入第一个元素tmp1=pointer;for(i=1;inext=NULL; tmp2-data=arrayi; tmp1-next=tmp2; tmp1=tmp2;return pointer;void bubble_sort(link pointer,int num)/给出链表指针和节点个数，可以用冒泡算法进行排序link tmp;int i,j,k;for(i=1;inum;i+)/冒泡算法不同于第2讲中的选择性排序的算法，注意区别。冒泡属于交换排序 tmp=pointer; for(j=1;jdatatmp-next-data) k=tmp-data; tmp-data=tmp-next-data; tmp-next-data=k; tmp=tmp-next; void print_list(link pointer)while(pointer) printf(2: %dn,pointer-data); pointer=pointer-next;link insert_node(link pointer,link btmp,int value)link newnode;if(btmp=NULL)/此为头节点前需要插入元素的情况 newnode=(link)malloc(sizeof(node); newnode-data=value; newnode-next=pointer; return newnode;else if(btmp-next=NULL)/此为尾节点后需要加入的元素的情况 newnode=(link)malloc(sizeof(node); newnode-data=value; btmp-next=newnode; newnode-next=NULL; else/此为在链表中间需要加入元素的情况 newnode=(link)malloc(sizeof(node); newnode-data=value; newnode-next=btmp-next;/注意下面这两句的先后顺序，要先指明新节点的后续节点。 btmp-next=newnode; return pointer;/返回链表头指针link search_insert_location(link pointer,int value)link tmp,btmp;int OTRUE=1;tmp=pointer;btmp=NULL;while(tmp&OTRUE) if(valuedata) OTRUE=0; if(OTRUE) btmp=tmp; tmp=tmp-next; pointer=insert_node(pointer,btmp,value);return pointer;void main()int arr=3,12,8,9,11;link ptr;ptr=create_list(arr,5);bubble_sort(ptr,5);printf(1:Print before insert node.n);print_list(ptr);ptr=search_insert_location(ptr,15);printf(1:Print after insert node 15n);print_list(ptr);ptr=search_insert_location(ptr,7);printf(1:Print after insert node 7n);p