#include <stdlib.h>
#include <malloc.h>
#include <stdio.h> typedef struct Node
{
int data;
struct Node *pNext;
}NODE,*PNODE; PNODE create_list(void);
void traverse_list(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(void)
{
PNODE pHead = NULL;
int val;
pHead = create_list();
sort_list(pHead);
if (delete_list(pHead, , &val))
{
printf("delete %d ok!\n",val);
}
else
{
printf("delete wrong");
}
traverse_list(pHead);
int len = length_list(pHead);
if (is_empty(pHead))
{
printf("list is empty!");
}
else
{
printf("list isn't empty!");
}
return ;
} PNODE create_list(void)
{
int len;
int val;//用于存放用户输入的结点的值
printf("请输入链表的长度:len=");
scanf("%d", &len);
PNODE pHead = (PNODE)malloc(sizeof(Node)); if (NULL == pHead)
{
printf("分配失败,程序终止!");
exit(-);
}
PNODE pTail = pHead;
pTail->pNext = NULL; for (int i = ; i < len; ++i)
{
printf("请输入第%d个节点的值", i + );
scanf("%d", &val);
PNODE pNew = (PNODE)malloc(sizeof(Node));
if (NULL == pNew)
{
printf("分配失败,程序终止!");
exit(-);
}
pNew->data = val;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHead;
} void traverse_list(PNODE pHead)
{
PNODE p = pHead->pNext;
while (NULL != p)
{
printf("%d", p->data);
p = p->pNext;
}
printf("\n");
} bool is_empty(PNODE pHead)
{
if (NULL == pHead->pNext)
{
return true;
}
return false;
} int length_list(PNODE pHead)
{
int length = ;
PNODE p = pHead->pNext;
while (NULL != p)
{
length++;
p = p->pNext;
}
return length;
} void sort_list(PNODE pHead)
{
int i, j, t;
int len = length_list(pHead);
PNODE p, q;
for (i = , p = pHead->pNext; i < len - ; ++i, p=p->pNext)
{
for (j = i + , 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;
}
//在pHead指向链表的第pos个节点的前面插入一个新的节点,该节点的值为value,pos从1开始
bool insert_list(PNODE pHead, int pos, int value)
{
int i = ;
PNODE p = pHead;
while (NULL != p && i < pos - )
{
p = p->pNext;
++i;
}
if (i > pos - || NULL == p)
return false;
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew)
{
printf("动态分配内存失败!\n");
exit(-);
}
pNew->data = value;
PNODE q = p->pNext;
p->pNext = pNew;
pNew->pNext = q;
return true;
} bool delete_list(PNODE pHead, int pos, int *pVal)
{
int i = ;
PNODE p = pHead;
while (NULL != p->pNext && i < pos - )
{
p = p->pNext;
++i;
}
if (i > pos - || NULL == p->pNext)
{
return false;
}
PNODE q = p->pNext;
*pVal = q->data;
//删除p节点后面的节点
p->pNext = p->pNext->pNext;
free(q);
q = NULL;
return true;
} /*
1.链表的删除,比如删除p后的节点,如何操作?有时很容易遗漏free(r)的操作,导致内存泄漏。
可以如下操作:
r = p->next;
p->next = r->next;
free(r);
*/