/*
* 根据郝斌老师视频整理
* 编译环境：
* 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;
}
| 
楼主
标题置顶
标题高亮
