1 /*链表插入和删除，判断链表是否为空，求链表长度算法的，链表排序算法演示*/  2 # include <stdio.h>  3 # include <malloc.h>  4 # include <stdlib.h>  5   6 typedef struct Node  7 {  8     int data;//数据域  9     struct Node * pNext;//指针域 10 }NODE, *PNODE;//NODE等价于struct Node 11  12               //函数声明 13 PNODE create_list(void); 14 void traverse_list(PNODE pHead); 15 bool is_empty(PNODE pHead); 16 int length_list(PNODE); 17 bool insert_list(PNODE, int, int);//要插入一个数据的话，要知道这个链表，再一个是位置，再一个是要删除的元素  18 bool delete_list(PNODE, int, int *);//要删除一个数据，要知道这个链表，再一个是位置，之所以定义了int * 型是因为要完成一个暂时的 19                                     //存储，就像是实现回收站的功能一样  20 void sort_list(PNODE); 21  22 int main(void) 23 { 24     int val; 25     PNODE pHead = NULL;//等价于 struct Node * pHead = NULL；把首节点的地址赋值给pHead(在一个链表中首节点和尾节点后面都是NULL，没有其他元素) 26                        //PNODE 等价于struct Node * 27     pHead = create_list(); 28     traverse_list(pHead); 29     printf("--------------------------------------\n"); 30     if (is_empty(pHead)) 31         printf("链表为空!\n"); 32     else 33         printf("链表不空!\n"); 34     printf("--------------------------------------\n"); 35     int len = length_list(pHead); 36     printf("链表的长度是%d\n", len); 37     printf("--------------------------------------\n"); 38     printf("重新排序之后："); 39     sort_list(pHead); 40     traverse_list(pHead); 41     printf("--------------------------------------\n"); 42     printf("插入新的节点后为："); 43     insert_list(pHead,3,33); 44     traverse_list(pHead); 45     printf("--------------------------------------\n"); 46     if (delete_list(pHead, 4, &val)) 47     { 48         printf("删除成功，您删除的元素是：%d\n", val); 49  50     } 51     else 52     { 53         printf("删除失败!您删除的元素不存在！\n"); 54     } 55     traverse_list(pHead); 56     getchar(); 57     getchar(); 58     return 0; 59 } 60  61 //创建地址类型的地址，因为create_list 这个函数是要返回的地址 62 //功能就是把头节点的地址返回，最终才能头节点才能指向一个链表 63 PNODE create_list(void) 64 { 65     int len;//存放有效节点的个数 66     int i; 67     int val;//用来临时存放用户熟入的节点是值 68  69             //前面说过只要是找到头节点，对于链表的操作就方便了，所以在这里我们首先先定义头节点 70     PNODE pHead = (PNODE)malloc(sizeof(NODE));//定义头节点（不存放有效数据） 71     if (NULL == pHead) //如果指针指向为空，则动态内存分配失败 72     { 73         printf("分配失败，程序终止！\n"); 74         exit(-1); 75     } 76     PNODE pTail = pHead; //pHead 是指向头节点的，如果用户是输入节点的个数是0，那么只有一个“头节点” 77     pTail->data = http://www.mamicode.com/NULL; //此时把pHead 赋值给pTail,则就合理l，然后指针域为空（和初始化差不多...） 78  79     printf("请您输入要生成链表节点的个数：len = "); 80     scanf("%d", &len); 81     for (i = 0; i < len; i++) 82     { 83         printf("请输入第%d个节点的值", i + 1); 84         scanf("%d", &val); 85         PNODE pNew = (PNODE)malloc(sizeof(NODE));//创建新节点，使之指针都指向每一个节点（循环了len次） 86         if (NULL == pNew) //如果指针指向为空，则动态内存分配失败 87         { 88             printf("分配失败，程序终止！\n"); 89             exit(-1); 90         } 91         /* 92  93         pNew->data = http://www.mamicode.com/val;//一个临时的节点> 94         pHead->pNext = pNew;//把pNew挂到pHead上 95         pNew->pNext=NULL; //这个临时的节点最末尾是空 96  97         */ 98  99 100         //上面/**/注释掉的这行代码是有问题的，上面注释掉的代码的含义是分别把头节点后面的节点都挂在头节点上，101         //导致头节点后面的节点的指针域丢失，而我们想的是只是把第一个节点挂在头节点上，后面的依次进行，即把第二个102         //节点挂在第一个节点的指针域上，依次类推，很明显上面所注释掉的代码是实现不了这个功能的103 104         //下面是改进之后的105         pNew->data = http://www.mamicode.com/val; //把有效数据存入pNEW106         pTail->pNext = pNew; //把pNew 挂在pTail的后面（也就是pTail指针域指向，依次串起来）107         pNew->pNext = NULL;//把pNew的指针域清空108         pTail = pNew;   //在把pNew赋值给pTai，这样就能循环，实现依次连接（而我们想的是只是把第一个节点挂在头节点上，后面的依次进行，即把第二个109                         //节点挂在第一个节点的指针域上）110     }111     return pHead;112 }113 114 115 //遍历函数并不需要返回值，参数还是要有的，要不然怎么知道是对哪个对象进行的遍历！116 //还是定义指针变量 PNODE pHead 因为 traverse_list(pHead)  调用的是地址117 118 119 /*120 链表的遍历写法的整体思路：121 1. 定义一个指针变量p指向第一个有效的节点122 2.判断这个节点的指针域是不是为空（如果不是就不是最后一个）123 3.不为空就输出此节点的有效数据，并且p-pNext来指向下一个节点（不能用p++哦！）124 4.如果为空的话，说明到来尾节点125 */126 127 128 void traverse_list(PNODE pHead)//怎样遍历，是不能像以前一样用数组的，以为数组是连续的，这里不连续129 {130     PNODE p = pHead->pNext;131 132     while (NULL != p)133     {134         printf("%d ", p->data);135         p = p->pNext;136     }137     printf("\n");138 }139 140 /*141 说明：_Bool依然仍是整数类型，但与一般整型不同的是，_Bool变量只能赋值为0或1，非0的值都会被存储为1。142 C99还提供了一个头文件 <stdbool.h> 定义了bool代表_Bool，true代表1，false代表0。只要导入 stdbool.h ，143 就能非常方便的操作布尔类型了。144 */145 146 147 //判断链表是否为空的函数 148 bool is_empty(PNODE pHead)149 {150     if (NULL == pHead->pNext)151         return true;152     else153         return false;154 }155 156 //链表长度计算函数157 int length_list(PNODE pHead)158 {159     PNODE p = pHead->pNext;160     int len = 0;161 162     while (NULL != p)163     {164         ++len;165         p = p->pNext;//链表不为空的时候，p就往下移一个 166 167     }168     return len;169 }170 171 //排序函数172 void sort_list(PNODE pHead)173 {174     int i, j, t, len = length_list(pHead);175     PNODE p, q;176 177     for (i = 0, p = pHead->pNext; i<len - 1; ++i, p = p->pNext)178     {179         for (j = i + 1, q = p->pNext; j<len; ++j, q = q->pNext)180         {181             if (p->data > q->data)// 类似于数组中的：a[i] >a[j]182             {183                 t = p->data; //类似于数组中的：t = a[i];184                 p->data = http://www.mamicode.com/q->data; //类似于数组中的：a[i] = a[j];185                 q->data = http://www.mamicode.com/t;  //类似于数组中的：a[j] = t;186             }187         }188     }189     190 191     return;192 }193 194 195 196 //插入函数197 198 //在pHead 所指向链表的第pos个节点的前面插入一个新的结点，该节点的值是val，并且pos的值是从1开始的199 bool insert_list(PNODE pHead, int pos, int val)200 {201     int i = 0;202     PNODE p = pHead;203     while (NULL != p && i < pos - 1)204     {205         p = p->pNext;206         ++i;207     }208     if (i > pos - 1 || NULL == p)209         return false;210     PNODE pNew = (PNODE)malloc(sizeof(NODE));//在插入之前先分配一个动态内存空间211     if (NULL == pNew)212     {213         printf("动态内存分配失败！\n");214         exit(-1);215     }216     pNew->data =http://www.mamicode.com/ val;217     PNODE q = p->pNext;//具体见93行附近注释218     p->pNext = pNew;219     pNew->pNext = q;220 221     return true;222 223 224 }225 226 //节点删除函数227 bool delete_list(PNODE pHead, int pos, int * pVal)228 {229 230     int i = 0;231     PNODE p = pHead;232     while (NULL != p->pNext && i < pos - 1)233     {234         p = p->pNext;235         ++i;236     }237     if (i > pos - 1 || NULL == p->pNext)238         return false;239     PNODE q = p->pNext;240     *pVal = q->data;  //删除之前先保存241 242     //删除p节点后面的节点243     p->pNext = p->pNext->pNext;244     free(q);245     q = NULL;246     return true;247 }248 249 /*对于排序函数的一个说明，其实是用了一个广义的算法上的一个应用吧算是250 算法：251 狭义的算法是与数据的存储方式密切相关252 广义的算法是与数据的存储方式无关253 泛型：254 利用某种技术达到的 效果就是：不同的存数方式，执行的操作是一样的255 */