//// main.c// testLink//// Created by lan on 16/3/6.// Copyright © 2016年 lan. All rights reserved.//#include#include #include #include typedef struct Node { int date; // 数据域 struct Node * pNext; // 指针域}NODE, * PNODE;PNODE create_list(void); // 创建一个链表void traverse_link(PNODE); // 遍历链表bool is_empty(PNODE pHead);int length_list(PNODE);bool insert_list(PNODE, int, int);bool delete_list(PNODE, int, int *);void sort_list(PNODE);int main(int argc, const char * argv[]){ int val; // 存放删除节点的值 PNODE pHead = NULL; pHead = create_list(); printf("创建好的链表: "); traverse_link(pHead); bool isEmpty = is_empty(pHead); printf("链表是否为空 = %d\n", isEmpty); int length = length_list(pHead); printf("链表的节点数 = %d\n", length); insert_list(pHead, 3, 99); printf("在第 3 个节点插入 99: "); traverse_link(pHead); delete_list(pHead, 4, &val); printf("删除第 4 个节点: "); traverse_link(pHead); printf("删除了 = %d\n", val); sort_list(pHead); printf("降序: "); traverse_link(pHead); return 0;}PNODE create_list(){ int len; // 节点个数 int value; // 暂时存放节点的值 PNODE pHead = (PNODE)malloc(sizeof(NODE)); if (NULL == pHead) { printf("分配失败。程序终止!\n"); exit(-1); } PNODE pTail = pHead; pTail->pNext = NULL; printf("请输入创建链表节点的个数: "); scanf("%d", &len); for (int i = 0; i < len; i++) { printf("请输入第%d个节点值: ", i+1); scanf("%d", &value); PNODE pNew = (PNODE)malloc(sizeof(NODE)); if (NULL == pNew) { printf("分配失败，程序终止!\n"); exit(-1); } pNew->date = value; pTail->pNext = pNew; pNew->pNext = NULL; pTail = pNew; } return pHead;}void traverse_link(PNODE pHead){ PNODE p = pHead->pNext; while (NULL != p) { printf("%d ", p->date); p = p->pNext; } printf("\n");}bool is_empty(PNODE pHead) { if (NULL == pHead->pNext) { return true; } else { return false; }}int length_list(PNODE pHead) { int len = 0; PNODE p = pHead->pNext; while (NULL != p) { len++; p = p->pNext; } return len;}bool insert_list(PNODE pHead, int pos, int value) {// if (pos > length_list(pHead) || pos <= 0) {// return false;// }// PNODE pNew = (PNODE)malloc(sizeof(NODE));// if (NULL == pNew) {// printf("分配失败。程序终止!\n");// exit(-1);// }// pNew->date = value;// // PNODE p = pHead->pNext;// for (int i = 1; i < pos - 1; i++) {// p = p->pNext;// }// // PNODE q = p->pNext;// p->pNext = pNew;// pNew->pNext = q;// return true; // 一种更高效的实现方式 PNODE p = pHead; int i = 0; while (p != NULL && i < pos - 1) { p = p->pNext; i++; } if (p == NULL || i > pos - 1) { return false; } PNODE pNew = (PNODE)malloc(sizeof(NODE)); if (NULL == pNew) { printf("分配失败，程序终止!\n"); exit(-1); } pNew->date = value; PNODE q = p->pNext; p->pNext = pNew; pNew->pNext = q; return true;}bool delete_list(PNODE pHead, int pos, int * pValue) {// if (pos > length_list(pHead) || pos <= 0) {// return false;// }// PNODE p = pHead->pNext;// for (int i = 1; i < pos - 1; i++) {// p = p->pNext;// }// // PNODE q = p->pNext;// *pValue = q->date;// p->pNext = p->pNext->pNext;// free(q);// q = NULL;// return true; // 一种更高效的实现方式 PNODE p = pHead; int i = 0; while (NULL != p->pNext && i < pos - 1) { p = p->pNext; i++; } if (NULL == p->pNext || i > pos - 1) { return false; } PNODE q = p->pNext; *pValue = q->date; p->pNext = p->pNext->pNext; free(q); // 记得释放 q 所指向的结构体 q = NULL; // 并把 q 指针指向 NULL return true;}void sort_list(PNODE pHead) { int i,j,temp,len; PNODE p,q; // int a[7] = {2,5,3,1,7,4,9};// len = 7;// for (i = 0; i < len - 1; i ++) {// for (j = i + 1; j < len; j++) {// if (a[i] < a[j]) {// temp = a[i];// a[i] = a[j];// a[j] = temp;// }// }// }// // 打印输出// for (int i = 0; i < 7; i ++) {// printf("%d ", a[i]);// }// printf("\n"); // 仿照数组的排序来实现链表的排序 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->date < q->date) { temp = p->date; p->date = q->date; q->date = temp; } } }}
输出结果：
请输入创建链表节点的个数: 5请输入第1个节点值: 1请输入第2个节点值: 2请输入第3个节点值: 3请输入第4个节点值: 4请输入第5个节点值: 5创建好的链表: 1 2 3 4 5 链表是否为空 = 0链表的节点数 = 5在第 3 个节点插入 99: 1 2 99 3 4 5 删除第 4 个节点: 1 2 99 4 5 删除了 = 3降序: 99 5 4 2 1 Program ended with exit code: 0