- /*
- * 根据郝斌老师视频整理
- * 编译环境：
- * guo@linux:~$ gcc --version
- * gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4
- */
- #include <stdio.h>
- #include <malloc.h>
- #include <stdlib.h>
- #define FALSE 0
- #define TRUE 1
- typedef struct Node
- {
- int data; /*数据域*/
- struct Node *pNext; /*指针域*/
- }NODE, *PNODE;
- /**********************声明**********************************/
- /*创建链表*/
- PNODE CreateLink(void);
- /*遍历链表*/
- void TraverseLink(PNODE );
- /*判断链表是否为空*/
- int IsEmptyLink(PNODE );
- /*求链表长度*/
- int LengthLink(PNODE );
- /*链表排序*/
- void SortLink(PNODE );
- /*链表插入节点*/
- int InsertLink(PNODE , int , int );
- /*链表删除节点*/
- int DeleteLink(PNODE , int , int *);
- /*
- * 函数名称：CreateLink。
- * 输入参数：无。
- * 输出参数：返回头节点的指针。
- * 函数说明：创建一个链表，并由用户输入每个节点的值。
- */
- PNODE CreateLink(void)
- {
- int len; /*链表个数*/
- int val; /*存储临时值*/
- int i;
- /*为头节点分配内存，并把地址赋值给pHead*/
- PNODE pHead = (PNODE)malloc(sizeof(NODE));
- if (NULL == pHead)
- {
- printf("内存分配失败！\n");
- exit(-1);
- }
- PNODE pTail = pHead;
- pTail->pNext = NULL;
- printf("请输入链表的个数：len=\n");
- scanf("%d",&len);
- for (i=0;i<len;++i)
- {
- PNODE pNew = (PNODE)malloc(sizeof(NODE));
- if (NULL == pNew)
- {
- printf("内存分配失败！\n");
- exit(-1);
- }
- printf("请输入第%d个节点的值:\n",i+1);
- scanf("%d",&val);
-
- pNew->data = val; /*保存新节点的数据*/
- pNew->pNext = NULL; /*新节点的指针指向NULL*/
- pTail->pNext = pNew; /*上个节点的指针指向新节点*/
- pTail = pNew; /*pTail指向新节点(保存新节点地址)*/
- }
-
- return pHead;
- }
- /*
- * 函数名称：TraverseLink。
- * 输入参数：pHead链表头节点的指针。
- * 输出参数：无。
- * 函数说明：遍历一个链表，并输出每个节点的值。
- */
- void TraverseLink(PNODE pHead)
- {
- PNODE p = pHead->pNext; //p指向第一个有效节点(首节点)
- while(NULL != p)
- {
- printf("%d ", p->data);
- p = p->pNext;
- }
- printf("\n");
- return;
- }
- /*
- * 函数名称：IsEmptyLink。
- * 输入参数：pHead链表头节点的指针。
- * 输出参数：为空返回TRUE；否则返回FALSE。
- * 函数说明：判断一个链表是否为空。
- */
- int IsEmptyLink(PNODE pHead)
- {
- if (NULL == pHead->pNext)
- return TRUE;
- else
- return FALSE;
- }
- /*
- * 函数名称：LengthLink。
- * 输入参数：pHead链表头节点的指针。
- * 输出参数：链表长度。
- * 函数说明：求链表长度。
- */
- int LengthLink(PNODE pHead)
- {
- int len = 0;
- PNODE p = pHead->pNext;
-
- while (NULL != p)
- {
- ++len;
- p = p->pNext;
- }
- return len;
- }
- /*
- * 函数名称：SortLink。
- * 输入参数：pHead链表头节点的指针。
- * 输出参数：无。
- * 函数说明：选择排序，升序。
- */
- void SortLink(PNODE pHead)
- {
- int i,j,t,len;
- PNODE p,q;
- len = LengthLink(pHead);
- /*i，j决定循环次数*/
- 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;
- }
- }
- }
- return;
- }
- /*
- * 函数名称：InsertLink。
- * 输入参数：pHead链表头节点的指针；pos要插入的位置，从1开始；value要插入的值；
- * pos可以比链表长度大1。
- * 输出参数：插入成功返回TRUE,否则返回FALSE。
- * 函数说明：插入一个节点。
- * 假设有5个节点，如下所示：
- * pHead 节点1 节点2 节点3 节点4 节点5
- * OOOO——>OOOO——>OOOO——>OOOO——>OOOO——>OOOO
- * 假设pos=3，即在第三个节点前插入数值。在while语句中带入数值：
- * 1)初始值： i=0，p指向pHead
- * 2)while成立：i=1，p指向节点1
- * 3)while成立：i=2，p指向节点2
- * 4)2<3-1不成立，所以此时可以确定pos没有超过链表长度，p正好指向第三个节点的
- * 前一个节点。
- * 5)如果只有2个节点，pos=3的话，在经过3)后，p指向节点2，此时p！= NULL，
- * p->pNext = NULL。此时while语句的前半部分成立，后半部分不成立，所以while的
- * 判断条件适合pos的值可以比链表的长度大1.
- */
- int InsertLink(PNODE pHead, int pos, int value)
- {
- int i = 0;
- PNODE p = pHead;
- /*利用循环找到pos位置，或者到尾节点*/
- while (NULL!=p && i<pos-1)
- {
- p = p->pNext;
- ++i;
- }
- /*从while循环中可以得知，i>pos-1不会成立，在此加一个是为了保证逻辑严密？？*/
- /*如果因为NULL==p导致while退出循环，说明pos超过链表的长度*/
- if (i>pos-1 || NULL==p)
- return FALSE;
- PNODE pNew = (PNODE)malloc(sizeof(NODE));
- if (NULL == pNew)
- {
- printf("动态分配内存失败！\n");
- exit(-1);
- }
- pNew->data = value;
- pNew->pNext = p->pNext;
- p->pNext = pNew;
- return TRUE;
- }
- /*
- * 函数名称：DeleteLink。
- * 输入参数：pHead链表头节点的指针；pos要删除的位置，从1开始；value保存要删除节点的值。
- * 输出参数：删除成功返回TRUE,否则返回FALSE。
- * 函数说明：删除一个节点。思路跟InsertLink相同，注意要释放内存。
- */
- int DeleteLink(PNODE pHead, int pos, int *pValue)
- {
- int i = 0;
- PNODE p = pHead;
- while (NULL!=p && i<pos-1)
- {
- p = p->pNext;
- ++i;
- }
- if (i>pos-1 || NULL == p)
- return FALSE;
- /*此时p指向pos的前一个节点*/
- *pValue = p->pNext->data;
- PNODE q = p->pNext;
- p->pNext = p->pNext->pNext;
- free(q);
- q = NULL;
- return TRUE;
- }
- int main(void)
- {
- PNODE pHead = NULL;
- int DeleteVal; /*存储删除的值*/
- pHead = CreateLink();
- TraverseLink(pHead);
- if (IsEmptyLink(pHead))
- printf("链表为空！\n");
- else
- printf("链表非空！\n");
- printf("链表长度为%d\n",LengthLink(pHead));
- printf("链表按升序排列为：\n");
- SortLink(pHead);
- TraverseLink(pHead);
- printf("链表插入一个值：\n");
- InsertLink(pHead, 3, 33);
- TraverseLink(pHead);
- printf("链表删除一个值：\n");
- DeleteLink(pHead, 2, &DeleteVal);
- TraverseLink(pHead);
- printf("链表删除的值为%d：\n",DeleteVal);
- return 0;
- }
| 
楼主
