//
// main.c
// testLink
//
// Created by lan on 16/3/6.
// Copyright © 2016年 lan. All rights reserved.
// #include <stdio.h>
#include <malloc/malloc.h>
#include <stdlib.h>
#include <stdbool.h> typedef struct Node {
int date; // 数据域
struct Node * pNext; // 指针域
}NODE, * PNODE; PNODE create_list(void); // 创建一个链表
void traverse_link(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(int argc, const char * argv[])
{
int val; // 存放删除节点的值 PNODE pHead = NULL;
pHead = create_list();
printf("创建好的链表: ");
traverse_link(pHead); bool isEmpty = is_empty(pHead);
printf("链表是否为空 = %d\n", isEmpty); int length = length_list(pHead);
printf("链表的节点数 = %d\n", length); insert_list(pHead, 3, 99);
printf("在第 3 个节点插入 99: ");
traverse_link(pHead); delete_list(pHead, 4, &val);
printf("删除第 4 个节点: ");
traverse_link(pHead);
printf("删除了 = %d\n", val); sort_list(pHead);
printf("降序: ");
traverse_link(pHead); return 0;
} PNODE create_list()
{
int len; // 节点个数
int value; // 暂时存放节点的值 PNODE pHead = (PNODE)malloc(sizeof(NODE));
if (NULL == pHead)
{
printf("分配失败。程序终止!\n");
exit(-1);
}
PNODE pTail = pHead;
pTail->pNext = NULL; printf("请输入创建链表节点的个数: ");
scanf("%d", &len); for (int i = 0; i < len; i++)
{
printf("请输入第%d个节点值: ", i+1);
scanf("%d", &value);
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew)
{
printf("分配失败,程序终止!\n");
exit(-1);
}
pNew->date = value; pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHead;
} void traverse_link(PNODE pHead)
{
PNODE p = pHead->pNext;
while (NULL != p)
{
printf("%d ", p->date);
p = p->pNext;
}
printf("\n");
} bool is_empty(PNODE pHead) {
if (NULL == pHead->pNext) {
return true;
} else {
return false;
}
} int length_list(PNODE pHead) {
int len = 0;
PNODE p = pHead->pNext;
while (NULL != p) {
len++;
p = p->pNext;
}
return len;
} bool insert_list(PNODE pHead, int pos, int value) {
// if (pos > length_list(pHead) || pos <= 0) {
// return false;
// }
// PNODE pNew = (PNODE)malloc(sizeof(NODE));
// if (NULL == pNew) {
// printf("分配失败。程序终止!\n");
// exit(-1);
// }
// pNew->date = value;
//
// PNODE p = pHead->pNext;
// for (int i = 1; i < pos - 1; i++) {
// p = p->pNext;
// }
//
// PNODE q = p->pNext;
// p->pNext = pNew;
// pNew->pNext = q;
// return true; // 一种更高效的实现方式
PNODE p = pHead;
int i = 0;
while (p != NULL && i < pos - 1) {
p = p->pNext;
i++;
}
if (p == NULL || i > pos - 1) {
return false;
} PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew) {
printf("分配失败,程序终止!\n");
exit(-1);
}
pNew->date = value; PNODE q = p->pNext;
p->pNext = pNew;
pNew->pNext = q;
return true;
} bool delete_list(PNODE pHead, int pos, int * pValue) {
// if (pos > length_list(pHead) || pos <= 0) {
// return false;
// }
// PNODE p = pHead->pNext;
// for (int i = 1; i < pos - 1; i++) {
// p = p->pNext;
// }
//
// PNODE q = p->pNext;
// *pValue = q->date;
// p->pNext = p->pNext->pNext;
// free(q);
// q = NULL;
// return true; // 一种更高效的实现方式
PNODE p = pHead;
int i = 0;
while (NULL != p->pNext && i < pos - 1) {
p = p->pNext;
i++;
}
if (NULL == p->pNext || i > pos - 1) {
return false;
} PNODE q = p->pNext;
*pValue = q->date;
p->pNext = p->pNext->pNext;
free(q); // 记得释放 q 所指向的结构体
q = NULL; // 并把 q 指针指向 NULL
return true;
} void sort_list(PNODE pHead) {
int i,j,temp,len;
PNODE p,q; // int a[7] = {2,5,3,1,7,4,9};
// len = 7;
// for (i = 0; i < len - 1; i ++) {
// for (j = i + 1; j < len; j++) {
// if (a[i] < a[j]) {
// temp = a[i];
// a[i] = a[j];
// a[j] = temp;
// }
// }
// }
// // 打印输出
// for (int i = 0; i < 7; i ++) {
// printf("%d ", a[i]);
// }
// printf("\n"); // 仿照数组的排序来实现链表的排序
len = length_list(pHead);
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->date < q->date) {
temp = p->date;
p->date = q->date;
q->date = temp;
}
}
}
}
输出结果:
请输入创建链表节点的个数: 5
请输入第1个节点值: 1
请输入第2个节点值: 2
请输入第3个节点值: 3
请输入第4个节点值: 4
请输入第5个节点值: 5
创建好的链表: 1 2 3 4 5
链表是否为空 = 0
链表的节点数 = 5
在第 3 个节点插入 99: 1 2 99 3 4 5
删除第 4 个节点: 1 2 99 4 5
删除了 = 3
降序: 99 5 4 2 1
Program ended with exit code: 0