用代码实现对链表的操作。
/* 创建一个链表, 实现对链表的创建,插入/追加,删除等操作*/# include# include # include //创建一个结构体typedef struct Node{ int data; struct Node * pNext;}NODE,*PNODE;//函数前置声明PNODE create_list(void); //创建一个链表void traverse_list(PNODE); //遍历整个链表bool is_empty(PNODE); //判断列表是否为空int length_list(PNODE); //返回链表的长度bool insert_list(PNODE, int , int); //在链表中插入元素bool delete_list(PNODE, int, int *);//删除链表中的某个元素,并且返回被删除的元素的值。void sort_list(PNODE); //对链表进行排序int main(void){ //初始化头指针变量 PNODE pHead = NULL; int val; //创建一个链表,将头结点的指针返回,保存到头指针变量中 pHead = create_list(); //判断这个链表是否为空 /* if( is_empty(pHead) ) { printf("这个链表为空\n"); } else { printf("链表不为空\n"); } */ //查看元素的个数 printf("该链表元素的个数为:%d\n",length_list(pHead)); //遍历整个链表 printf("遍历整个链表:"); traverse_list(pHead); //插入元素 printf("在第3个元素前插入一个99的值:"); insert_list(pHead, 3, 99); traverse_list(pHead); //对链表进行排序 printf("对链表进行升序排序:"); sort_list(pHead); traverse_list(pHead); //删除链表中的元素 printf("删除第三个位置的值: "); delete_list(pHead, 3, &val); //遍历这个链表 traverse_list(pHead); return 0;}/* 常见一个链表 @param void @return pHead 头指针*/PNODE create_list(void){ int val; //用于保存用户输入的值 int i; //for循环自增变量 int data; //创建头结点 PNODE pHead = (PNODE)malloc(sizeof(NODE)); if(NULL == pHead) { printf("动态内存创建失败\n"); exit(-1); } PNODE pTail = pHead; pTail -> pNext = NULL; printf("需要创建元素的个数len="); scanf("%d",&val); for(i = 0; i < val; ++i) { printf("请输入第%d个元素:", i + 1); scanf("%d",&data); //创建这个节点 PNODE pNew = (PNODE)malloc(sizeof(NODE)); if(NULL == pNew) { printf("动态内存创建失败\n"); exit(-1); } pNew -> data = data; pNew -> pNext = NULL; pTail -> pNext = pNew; pTail = pNew; } return pHead; }/* 遍历一个链表 @param PNODE 头指针 @return void*/void traverse_list(PNODE pHead){ PNODE p; p = pHead; if( is_empty(pHead) ) { printf("这个链表为空\n"); return; } while(NULL != p->pNext) { p = p->pNext; printf("%d ",p->data); } printf("\n");}/* 判断链表是否为空 @param PNODE pHead 头指针 @return bool */bool is_empty(PNODE pHead){ if( NULL == pHead -> pNext) { return true; } else{ return false; }}/* 返回链表的长度 @param PNODE pHead 头指针 @return int i 指针的长度 */int length_list(PNODE pHead){ PNODE p; int i = 0; if( is_empty(pHead) ) { printf("链表为空。\n"); } p = pHead->pNext; while( NULL != p) { ++i; p = p->pNext; } return i;}/* 对链表进行排序 @param PNODE pHead 头指针 @return void 思路:昨天对数组的排序方法,同样适用于链表, 需要对for循环稍微改造一下。*/void sort_list(PNODE pHead){ int i, j, len, t; PNODE p, q; len = length_list(pHead); for(i = 0,p = pHead->pNext; i < len-1; ++i,p=p->pNext) { for(j = i+1, q = p->pNext; j < len; ++j,q = q ->pNext) { if(p->data > q->data) { t = p->data; p->data = q->data; q->data = t; } } } }/* 插入一个元素 @param PNODE pHead 头指针 @param int pos 插入元素的位置 @param int val 要插入元素的值 @return bool */bool insert_list(PNODE pHead, int pos, int val){ PNODE p = pHead; int i = 0; /* 目的:判断用户输入信息是否合法 思路: 假如有5个元素,在第3个元素前插入 第一次:i = 0 指针不为空,i 变为1,p指针指向第1个元素 第二次:i = 1 指针不为空,i 变为2,p指针指向第2个元素 假如有5个元素,在第4个元素前插入 第一次:i = 0 指针不为空,i 变为1,p指针指向第1个元素 第二次:i = 1 指针不为空,i 变为2,p指针指向第2个元素 第三次;i = 2 指针不为空,i 变为3,p指针指向第3个元素 假如有5个元素,在第5个元素前插入 第一次:i = 0 指针不为空,i 变为1,p指针指向第1个元素 第二次:i = 1 指针不为空,i 变为2,p指针指向第2个元素 第三次;i = 2 指针不为空,i 变为3,p指针指向第3个元素 第四次;i = 3 指针不为空,i 变为4,p指针指向第4个元素 假如有5个元素,在第6个元素前插入 第一次:i = 0 指针不为空,i 变为1,p指针指向第1个元素 第二次:i = 1 指针不为空,i 变为2,p指针指向第2个元素 第三次;i = 2 指针不为空,i 变为3,p指针指向第3个元素 第四次;i = 3 指针不为空,i 变为4,p指针指向第4个元素 第五次;i = 4 指针不为空,i 变为5,p指针指向第5个元素 */ while(NULL != p && i < pos-1) { ++i; p = p -> pNext; } /* 2016年1月2日10:26:24 修改 昨天的时候,这里犯了一个错误,写的是 if(i > pos-1 || NULL == p->pNext) 这样写的结果就是,不能在最后一个元素之后插入,也就是5个有效元素,不能再第6 个元素前插入,因为NULL == p->pNext会判断上一个元素的指针域是否为空,最后一个元素的 指针域肯定是空了,所以就显示了一个输入值非法。 这样做显然是不恰当的,应该可以再最后也可以插入一个值,就类似于追加的效果。 所以,为了验证用户输入的值的合法性,只需要判断前一个元素是否为空即可, 而不是判断前一个元素的指针域是否为空,所以应该改成这样子: if(i > pos-1 || NULL == p) 这样就可以实现追加的效果了 */ if(i > pos-1 || NULL == p) { printf("您输入的值非法\n"); return false; } PNODE pNew=(PNODE)malloc(sizeof(NODE)); if(NULL == pHead) { printf("动态内存创建失败\n"); exit(-1); } pNew -> data = val; pNew -> pNext = p -> pNext; p -> pNext = pNew; return true;}/* 删除一个元素 @param PNODE pHead 头指针 @param int pos 删除元素的位置 @param PNODE val 返回删除元素的值 @return bool */bool delete_list(PNODE pHead, int pos, int * val){ PNODE p = pHead; PNODE t; int i = 0; while(NULL != p->pNext && i < pos-1) { ++i; p = p -> pNext; } /* 这里的判断就需要是NULL == p -> pNext, 假如有5个元素,肯定不能删除第6个元素,因为第6个元素为空。 只能删除第1个元素到第5个元素。 */ if(i > pos-1 || NULL == p -> pNext) { printf("您输入的值非法\n"); exit(-1); } t = p -> pNext->pNext; *val = p->pNext->data; free(p->pNext); p->pNext = t; return true;}/* VC++6.0中的输出为: =========================================== 需要创建元素的个数len=5 请输入第1个元素:1 请输入第2个元素:2 请输入第3个元素:3 请输入第4个元素:4 请输入第5个元素:5 该链表元素的个数为:5 遍历整个链表:1 2 3 4 5 在第3个元素前插入一个99的值:1 2 99 3 4 5 对链表进行升序排序:1 2 3 4 5 99 删除第三个位置的值: 1 2 4 5 99 =========================================== 总结: 通过对比,可以很明显的体现出链表和数组操作的差异。 体现了,数据的储存方式不同,对应的算法也不同。*/
好累啊,刚刚写完,今天就到这吧,明天再把注释完善一下,整个程序感觉不难,就是在插入和删除函数需要判断位置是否合法那里,费了好长时间,还是有点难度的。
明天再总结吧,睡觉!
学PHP的小蚂蚁 博客
2016年1月2日11:07:18
今天添加了注释,对于第249行的算法,之前有些不足,无法对链表进行追加,改进之后实现了追加。