/*
Get
1、我这里的单独创建了一个结构体 List来保存整个链表的信息和一般的参考书上可能不一样
2、实际的单链表由 List里面的 头结点Head进行连接。
3、头结点有数据域和指针域 ，数据域可以任意替换
4、本程序实现了
①、单链表的创建(使用尾插法，符合先进先出的生活逻辑。头插法也可以)
②、单链表的删除(释放所有节点，head=NULL, 链表长度为0)；
③、节点的插入、删除、查找(获取)
5、单链表 <->顺序储存结构 相比较(优缺点)
① 插入和删除： 顺序储存复杂度是 O(n)，单链表第一次O(n)，之后O(1)。 所以 对于插入和删除越频繁的工作，单链表的效率就越明显。
因为如果在同一位置连续插入10个元素， 第一次插入的时候如要逐个遍历找到插入点， 但是之后就可以记录下次插入点， 后面的几次插
入就要快得多了。但是对于顺序储存结构的话，还要每次都要把插入点后面的元素向后移动，这样会耗费很多时间的。
② 任一储存单元的链式储存结构 <-> 连续的储存单元依次存放元素的顺序储存结构
③ 时间性能：
查找：单链表O(n) 顺序O(1)
插入删除：单链表O(n)->O(1) 顺序O(n);
④ 空间性能：
顺序储存需要预备更多的空间，会产生浪费。如果空间小了还会溢出。
单链表，随时用随时申请，不用了还可以释放。
*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef struct node
{
//数据域
ElemType data;
//指针域
struct node *next;
} Node;
typedef struct
{
Node *head;
int length;
char *information;
} List;
typedef int Status;
//这个是尾插法 初始化链表。 还有在我的程序里面 我把Node封装在了一个List结构体里面 ，
//List的变量用来说明这个List的属性
Status InitList(List *list, int nodeAmount);
//复杂度 O(n) 对于插入和删除越频繁的工作，单链表的效率就越明显(在同一位置连续插入10个元素)
Status insert(List *list, ElemType e, int Index);//链表下标还是从1开始
Status delete(List *list, int Index);
//获取单个元素
Status getElem(List *list, ElemType *e, int Index);
//整表删除
Status FreeList(List *list);
void test(List *list);
Status IteratorOutPut(List *list);
/*
1、链表的创建与初始化(带有头指针)
2、遍历链表
3、单链表的插入和删除(删除后 记得释放内存 链表的长度的加减)
*/
//头结点使得空链表与非空链表处理一致，并且方便对链表的第一个结点的插入和删除操作。
int main(void)
{
//printf("test_X");
List list;
ElemType e, e1;
//初始化创建链表。为链表赋值
if (InitList(&list, 4) != OK)
{
printf("单链表创建失败\n");
}
e = 999;
//插入元素 e=999
if (insert(&list, e, 1) != OK )
{
printf("插入失败\n");
}
// test(&list);
//删除指定位置的元素
if (delete(&list, 4) != OK )
{
printf("删除失败\n");
}
//遍历链表
IteratorOutPut(&list);
//获取前面插入的 999
getElem(&list, &e1, 1);
printf("\n获取指定位置的元素进行输出：%d\n", e1);
printf("释放链表\n");
FreeList(&list);
printf("释放后再对链表进行遍历，检查是否释成功：\n");
IteratorOutPut(&list);
return 0;
}
//手动申请的空间，不会被自动回收。 不限制与这个函数的作用域里面。
Status InitList(List *list, int nodeAmount)
{
int i = 0;
Status status;
Node *p, *r, *head;
head = (Node *)malloc(sizeof(Node));//创建头结点
list->head = head;
list->length = 0; //初始化链表长度
p = (Node *)malloc(sizeof(Node)); //创建第一个节点
head->next = p;
printf("请输入第%d个结点的数据信息 :",
i + 1); //向数据域的第一次写数据
scanf("%d", &(p -> data));
for (i = 1; i < nodeAmount; i++)
{
r = (Node *)malloc(sizeof(Node)); //创建新节点
p -> next = r; //连接节点
p = r; //为下一次连接做好准备
printf("请输入第%d个结点的数据信息 :",
i + 1); //向数据域写数据
scanf("%d", &(p -> data));
list->length++; //链表长度++
fflush(stdin); //清除缓存区
}
p->next=NULL;
status = OK;
return status;
}
Status insert(List *list, ElemType e, int Index)
{
Node *p, *node;
int i;
p = list->head;
if (Index > list -> length || Index < 1)
{
return ERROR;
}
for (i = 0; i < Index - 1; i++)
{
p = p->next;
}
node = (Node *)malloc(sizeof(Node)); //为插入的节点申请空间
node ->data = e;
node->next = p->next;
p->next = node;
list->length++; //链表长度+1
return OK;
}
Status delete(List *list, int Index)
{
Node *p, *r;
int i;
Status status;
p = list->head;
if (Index > list->length || Index < 1)
{
status = ERROR;
}
else
{
//1 2 3 4 5
for (i = 0; i < Index - 1; i++)
{
p = p->next;
}
r = p->next;
p->next = p->next->next;
free(r);
status = OK;
list->length--;//链表长度-1
}
return status;
}
//不同的数据域需要有不同的输入格式和输出格式 在c语言里面 如果遍历得到每个元素的话，不太方便。
//因为不好设置iterator对象 还不如直接遍历
Status IteratorOutPut(List *list)
{
Node *p;
if(list->length == 0 || list->head == NULL)
{
return ERROR;
}
p = list->head->next;
while(p)//C语言的NULL在实际的底层代码中就是0
{
printf("%d ", p->data); //遍历的具体操作 这里是遍历输出
p = p -> next;
}
return OK;
}
Status getElem(List *list, ElemType *e, int Index)
{
Node *p, *r;
int i;
p = list->head;
if (Index > list->length || Index < 1)
{
return ERROR;
}
//1 2 3 4 5
for (i = 0; i < Index; i++)
{
p = p->next;
}
*e = p->data;
return OK;
}
Status FreeList(List *list)
{
Node *p, *r;
p = list->head;
while(p)
{
r = p ->next;
free(p);
p = r;
}
list->length = 0;
list->head = NULL;
return OK;
}
/*
void test(List *list)
{
if (insert(list, 999, 1) != OK )
{
printf("插入失败\n");
}
}
*/
