1.链表实现
/*
* 链表:插入 O(1) 查找 O(n)
* 线性表：插入 O(logn) 查找 O(1)
* 链表优点:不需要预先知道数据大小;
* 链表缺点:不能随机存取,增加了节点的指针域,空间开销大
*/
#include <stdio.h>
#include <stdlib.h>
#define Error( Str ) FatalError( Str )
#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 )
typedef int ElementType;
#ifndef _LIST_H
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
//List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
int Find(ElementType X, List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
Position Insert(ElementType X, List L, Position P);
void DeleteList(List L);
//Position Header(List L);
//Position First(List L);
//Position Advance(Position P);
//ElementType Retrieve(Position P);
#endif /* _LIST_H */
struct Node
{
ElementType Element;
Position Next;
};
/*初始化*/
int InitList(List *L)
{
*L = (List)malloc(sizeof(List));
if(!*L)
return 0;
(*L)->Next = NULL;
}
/* 判断链表是否为空
* L里为链接的头节点，当头节点里的Next为空时，整个链表为空
*/
int IsEmpty(List L)
{
return L->Next == NULL;
}
/*
* 判断是否是链表的最后一个元素
*/
int IsLast( Position P, List L )
{
return P->Next == NULL;
}
/*
* 判断值X是在链表中的第几个节点
*/
int Find(ElementType X, List L)
{
Position P;
P = L->Next;
int key = 1;
while(P != NULL && P->Element != X)
{
key++;
P = P->Next;
}
return key;
}
/*
* 将第key个节点的值修改为X
*/
void Edit(List L, int key, ElementType X)
{
Position P;
P = L;
int i,compar=0;
//头结点的值不能修改
if(0 != key)
{
for(i=0; i<key; i++)
{
if(P != NULL)
{
P = P->Next;
compar++;
}
else
break;
}
if(key == compar)
P->Element = X;
else
printf("修改失败,该节点不存在！\n");
}
}
/*
* 删除值为X的节点
*/
void Delete(ElementType X, List L)
{
Position P, TmpCell;
P = FindPrevious(X,L);
if(!IsLast(P,L))
{
TmpCell = P->Next;
P->Next = TmpCell->Next;
free(TmpCell);
}
}
/*
* 寻找前驱
*/
Position FindPrevious(ElementType X, List L)
{
Position P;
P = L;
while(P->Next != NULL && P->Next->Element != X)//当P->Next为NULL时,说明已到链表的末尾
P = P->Next;
return P;
}
/*
* 将数据X插入到位置P之后
*/
Position Insert(ElementType X, List L, Position P)
{
Position TmpCell;
TmpCell = malloc(sizeof(struct Node));
if(TmpCell == NULL)
FatalError("Out of space!!!");
TmpCell->Element = X;
TmpCell->Next = P->Next;
P->Next = TmpCell;
return TmpCell;
}
/*
* 链表遍历
*/
void TraverseList(List L)
{
int key = 0;
while(L->Next != NULL)
{
key++;
L = L->Next;
printf("节点%d:%d\n", key,L->Element);
}
}
int main()
{
int res;
List single_list = NULL;
res = InitList(&single_list);
//头结点
Position list_position = FindPrevious(0, single_list);
if(res)
{
int len;
char input[10];
int list_val=0,key;
printf("初始化成功,皮卡！\n操作说明:\n");
printf("数据插入:insert 12,将12插入到链表的尾部,皮卡！\n");
printf("数据删除:delete 12,将12这个节点从链表中删除,皮卡！\n");
printf("数据修改:edit 2 13,将节点2的值修改为13,皮卡！\n");
printf("数据查询:find 13,值为13的节点是第几个,皮卡！\n");
printf("其它:traverse,遍历整个数组,退出:exit,皮卡！\n");
//主循环
while(1)
{
//参数接收
int par_key=1,par3=0;
while(1)
{
if(1 == par_key)
scanf("%s", &input);
else if(2 == par_key)
scanf("%d", &list_val);
else if(3 == par_key)
scanf("%d", &par3);
else
break;
char c=getchar();
if(c=='\n')
break;
par_key++;
}
if(strcmp(input , "insert") == 0)
{
//结点新增
list_position = Insert(list_val, single_list, list_position);
printf("插入完成,新插入的值为:%d,下面是目前的链表,皮卡！\n", list_val);
TraverseList(single_list);
}
else if(strcmp(input , "find") == 0)
{
//结点查找
key = Find(list_val, single_list);
printf("该元素位于第%d个节点\n", key);
}
else if(strcmp(input , "delete") == 0)
{
//结点删除
Delete(list_val, single_list);
printf("节点删除完成,要删除的值为:%d,下面是目前的链表,皮卡！\n", list_val);
TraverseList(single_list);
}
else if(strcmp(input, "edit") == 0)
{
//结节修改
Edit(single_list, list_val, par3);
TraverseList(single_list);
}
else if(strcmp(input , "traverse") == 0)
{
//链表遍历
TraverseList(single_list);
}
else if(strcmp(input , "exit") == 0)
break;
}
}else
FatalError("初始化失败,皮卡！");
}运行结果:
[root@iZ28mhfkaunZ list]# ./list 初始化成功,皮卡！ 操作说明: 数据插入:insert 12,将12插入到链表的尾部,皮卡！ 数据删除:delete 12,将12这个节点从链表中删除,皮卡！ 数据修改:edit 2 13,将节点2的值修改为13,皮卡！ 数据查询:find 13,值为13的节点是第几个,皮卡！ 其它:traverse,遍历整个数组,退出:exit,皮卡！ insert 12 插入完成,新插入的值为:12,下面是目前的链表,皮卡！ 节点1:12
2.链表应用
木桶排序->基数排序(基数排序时，需要从低位往高位排，否则不能得出正确结果)，多项式的抽象数据类型;