《linkedlist链表实现》由会员分享，可在线阅读，更多相关《linkedlist链表实现（12页珍藏版）》请在金锄头文库上搜索。
1、LinkedListLinkedList 链表实现链表实现#include #include #include typedef struct Nodeint data;struct Node * pNext;NODE,* PNODE;PNODE create_list(void);void traverse_list(PNODE pHead);int is_empty(PNODE pHead);int length_list(PNODE pHead);void sort_list(PNODE pHead); /升序排序int insert_list(PNODE pHead,int index,
2、int val); /在有效节点间插入一个新节点 index 从 0 开始，传 0 则在第一个有效节点前插入int delete_list(PNODE pHead,int index,int * pVal);void inversion_list(PNODE pHead); /倒置链表 有效节点保存的数据倒置void clear_list(PNODE pHead); /清空有效节点 只保留头节点void destroy_list(PNODE pHead); /销毁链表int main(void)PNODE pHead = NULL;int len,val,index,choose;/创建初始链
3、表printf(“创建链表:n“);pHead = create_list();printf(“*n“);printf(“请选择：n“);printf(“1) 查看链表tt2) 插入节点n“);printf(“3) 删除节点tt4) 升序排序n“);printf(“5) 倒置链表tt6) 求节点数n“);printf(“7) 清空节点tt0) 销毁链表并退出n“);printf(“*n“);printf(“);scanf(“%d“,doswitch(choose)case 1:/遍历链表printf(“链表节点如下:n“);if (is_empty(pHead)printf(“链表空!n“);
4、traverse_list(pHead);break;case 2:/插入节点printf(“输入要插入节点的数据和位置: “);scanf(“%d%d“,if (insert_list(pHead,index,val)printf(“插入%d到 index%d成功!n“,val,index);elseprintf(“插入%d到 index%d失败!n“,val,index);break;case 3:/删除节点printf(“输入要删除节点的位置：“);scanf(“%d“,if(delete_list(pHead,index,elseprintf(“删除 index%d失败!n“,inde
5、x);break;case 4:/升序排序sort_list(pHead);printf(“升序排序成功!n“);break;case 5:/倒置链表inversion_list(pHead);printf(“倒置链表成功!n“);break;case 6:/求节点数len = length_list(pHead);printf(“链表节点个数为%d!n“,len);break;case 7:/清空节点clear_list(pHead);printf(“链表节点已清空!n“,len);break;case 0:/销毁链表destroy_list(pHead);printf(“退出.n“,len
6、);exit(0);default:break;printf(“*n“);printf(“请选择：n“);printf(“1) 查看链表tt2) 插入节点n“);printf(“3) 删除节点tt4) 升序排序n“);printf(“5) 倒置链表tt6) 求节点数n“);printf(“7) 清空节点tt0) 销毁链表并退出n“);printf(“*n“);printf(“);while(scanf(“%d“,return 0;PNODE create_list(void)int len; /有效节点的个数int val; /临时存放输入节点数据的值printf(“请输入你要生成链表节点的个
7、数：“);scanf(“%d“,PNODE pHead = (PNODE)malloc(sizeof(NODE);if (NULL = pHead)printf(“分配动态内存失败，程序终止!n“);exit(-1);PNODE pTail = pHead;pTail-pNext = NULL; /pTail 指向尾节点for (int i = 0;i data = val;pTail-pNext = pNew;pNew-pNext = NULL;pTail = pNew;return pHead;void traverse_list(PNODE pHead)PNODE p = pHead-p
8、Next;printf(“头指针 头节点 “);while (NULL != p)/printf(“%p: %dn“,printf(“%d “,p-data);p = p-pNext;printf(“NULLn“);return;int is_empty(PNODE pHead)PNODE p = pHead-pNext;if (NULL = p)return 1;elsereturn 0;int length_list(PNODE pHead)int len = 0;PNODE p = pHead-pNext;while (NULL != p)+len;p = p-pNext;return
9、len;void sort_list(PNODE pHead)int temp;PNODE p,q;if (is_empty(pHead)printf(“链表空!n“);return;/*for(p = pHead-pNext;p != NULL;p = p-pNext)for(q = p-pNext;q != NULL;q = q-pNext)if (p-data q-data)temp = p-data;p-data = q-data;q-data = temp;*/int i,j,len = length_list(pHead);for (i = 0,p = pHead-pNext;i
10、pNext)for (j = i+1,q = p-pNext;j pNext)if (p-data q-data) /等价于 ai ajtemp = p-data; /等价于 temp = ai;p-data = q-data; / 等价于 ai = aj;q-data = temp; /等价于 aj = temp;return;int insert_list(PNODE pHead,int index,int val)int len = length_list(pHead),i;PNODE p,q,t;q = (PNODE)malloc(sizeof(NODE);if (NULL = q)p
11、rintf(“分配动态内存失败，程序终止!n“);return 0;q-data = val;q-pNext = NULL;if (index len)printf(“传入的插入索引位置%d不合法! 插入位置只能在0 %d 之间n“,index,len);return 0;t = pHead;for (i = 0,p = pHead-pNext;i pNext;p = p-pNext;q-pNext = p;t-pNext = q;return 1;int delete_list(PNODE pHead,int index,int * pVal)int len = length_list(pH
12、ead),i;PNODE p,q,t;if (is_empty(pHead)printf(“链表空!n“);return 0;if (index = len)printf(“传入的删除索引位置%d不合法! 删除索引位置只能在 0 %d 之间n“,index,len-1);return 0;q = pHead;t = pHead-pNext;for (i = 0,p = t-pNext;i pNext;p = p-pNext;t = q-pNext;*pVal = t-data;q-pNext = p;free(t);return 1;void inversion_list(PNODE pHea
13、d)int len,i,temp;PNODE p,q;if (is_empty(pHead)printf(“链表空!n“);return;len = length_list(pHead);for(i = 0,p = pHead-pNext;i pNext;NULL != q;q = q-pNext)temp = p-data;p-data = q-data;q-data = temp;p = p-pNext;return;void clear_list(PNODE pHead)PNODE current = pHead-pNext,temp;while(NULL != current)temp = current;current = current-pNext;free(temp);pHead-pNext = NULL;return;void destroy_list(PNODE pHead)PNODE p,q;p = pHead;/从头指针依次释放每个节点的动态内存while(p)q = p;p = p-pNext;free(q);return;
