赞
踩
- #include <stdio.h>
- #include <stdlib.h>
-
- typedef struct Node
- {
- int date;
- struct Node *pNext;
- } NODE, *PNODE;
-
- PNODE creat_list()
- {
- int len, temp; //temp负责临时接收输入值
- printf("请输入你要创建的链表长度\n");
- scanf("%d", &len);
- PNODE phead; //头指针
- phead = (PNODE)malloc(sizeof(NODE));
- if (NULL == phead)
- {
- printf("空间分配失败\n");
- exit(-1);
- }
- phead->pNext = NULL;
- PNODE ptail = phead; //创建尾指针并初始化,方便指针的移动
- for (int i = 0; i < len; ++i)
- {
- printf("请输入节点的值\n");
- scanf("%d", &temp);
- PNODE pnew = (PNODE)malloc(sizeof(NODE));
- if (NULL == pnew)
- {
- printf("空间分配失败\n");
- exit(-1);
- }
- pnew->date = temp;
- ptail->pNext = pnew;
- pnew->pNext = NULL;
- ptail = pnew;
- }
- return (phead);
- }
-
- void traverse_list(PNODE phead)
- {
- PNODE p = phead->pNext; //让p指向第一个有效的节点(首节点)
- while (p != NULL)
- {
- printf("%d ", p->date);
- p = p->pNext;
- }
- printf("\n");
- }
-
- int list_length(PNODE phead)
- {
- int len = 0;
- PNODE p = phead->pNext;
- while (p != NULL)
- {
- len++;
- p = p->pNext;
- }
- return len;
- }
-
- bool is_empty(PNODE phead)
- {
- PNODE p = phead->pNext;
- if (p != NULL)
- return true;
- else
- return false;
- }
-
- void sort_list(PNODE phead)
- {
- /* //冒泡排序的 数组版
- int i, j ,temp;
- for(i=0;i<len-1;i++)
- {
- for(j=0;j<len-1-i;j++)
- {
- if(a[j]>a[j+1])
- {
- temp = a[j];
- a[j] = a[j+1];
- a[j+1] = a[j];
- }
- }
- } */
- //下面是模仿数组版写出来 ,体现了泛型的思想,这是交换节点的数据域,没有交换节点,当数据源很大时,效率就会很低,后期有时间要学下怎么交换节点
- int i, j, temp;
- PNODE p1, p2;
- for (i = 0; i < list_length(phead) - 1; i++)
- {
- p1 = phead->pNext;
- p2 = p1->pNext;
- for (j = 0; j < list_length(phead) - i - 1; j++)
- {
- if (p1->date > p2->date)
- {
- temp = p1->date;
- p1->date = p2->date;
- p2->date = temp;
- }
- p1 = p1->pNext;
- p2 = p2->pNext;
- }
- }
- }
-
- bool insert_list(PNODE phead, int pos, int val) //在第pos-1位置前插入一个节点,关键就是找前一个节点的位置, POS是从一开始
- {
- int i = 0;
- PNODE p = phead;
- while (p != NULL && i < pos - 1)
- {
- i++;
- p = p->pNext;
- } //这个算法可以很好让P指向第pos-1个节点 如果p=NULL 的话说明要在插入的位置前 链表以及为空(pos大于len+1)
-
- if (i > pos - 1 || p == NULL) //这个可以防止 pos为负数;
- return false;
-
- PNODE pnew = (PNODE)malloc(sizeof(NODE));
- if (pnew == NULL)
- {
- printf("分配内存失败\n");
- exit(-1);
- }
- pnew->date = val;
- pnew->pNext = p->pNext; //这先让pnew的尾巴和第pos个连接起来
- p->pNext = pnew; // 这个让POS-1个节点与PNEW 连接起来
- return true;
- }
-
- bool delet_list(PNODE phead, int pos, int *val)
- {
- int i = 0;
- PNODE p = phead;
- while (p->pNext != NULL && i < pos - 1)
- {
- i++;
- p = p->pNext;
- } //这个算法可以很好让P指向第pos-1个节点 如果p->next=NULL 的话说明要在删除的位置前 链表以及为空(pos大于len)
-
- if (i > pos - 1 || p->pNext == NULL) //这个可以防止 pos为负数;
- return false;
-
- PNODE ptemp = (PNODE)malloc(sizeof(NODE)); //需要一个临时的指针指向被删除的节点 方便日后释放内存,以免找不回被删的节点
- if (ptemp == NULL)
- {
- printf("分配内存失败\n");
- exit(-1);
- }
- ptemp = p->pNext;
- *val = ptemp->date;
- p->pNext = p->pNext->pNext;
- free(ptemp);
- ptemp = NULL; //规范操作 释放后让不能再用了
- return true;
- }
-
- int main()
- {
- int val;
- PNODE phead;
- phead = creat_list();
- traverse_list(phead);
- insert_list(phead, 1, 3);
- traverse_list(phead);
- delet_list(phead, 22, &val);
- printf("删除值是 %d \n", val);
- traverse_list(phead);
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。