各种基本算法实现小结（一）—— 单链表
（均已测试通过）
============================================================
单链表(测试通过)
测试环境： Win-TC
#include <stdio.h>
struct _node
{
int data;
struct _node *next;
};
typedef struct _node list;
void display(list *l)
{
list *p;
p=l;
while(p->next)
{
printf("%5d", p->next->data);
p=p->next;
}
}
void main()
{
int i, n;
list *h, *p, *s;
printf("Enter num n:");
scanf("%d", &n);
h=(list*)malloc(sizeof(list));
h->data=-1;
h->next=NULL;
s=p=h;
for(i=n;i>0;i--)
{
p=(list*)malloc(sizeof(list));
scanf("%d", &(p->data));
p->next=h->next;
h->next=p;
h=h->next;
}
display(s);
getch();
}
运行结果：
=================================================
单链表各种操作(测试通过)
测试环境： Win-TC
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
struct _node
{
int data;
struct _node *next;
};
typedef struct _node node, *plist;
plist init_list()
{
plist pl;
pl=(plist)malloc(sizeof(node));
if(NULL==pl)
{
printf("init list, malloc is fail.../n");
return NULL;
}
pl->data=-1;
pl->next=NULL;
return pl;
}
int isempty_list(plist pl)
{
if(NULL==pl || NULL!=pl->next)
return 1;
else
return 0;
}
plist clear_list(plist pl)
{
pl=NULL;
return pl;
}
void destroy_list(plist pl)
{
plist p, s;
p=pl->next;
while(p)
{
s=p;
p=p->next;
free(s);
}
pl=NULL;
}
void insert_item(plist pl, int i, int e)
{
int j=1;
plist p, s;
p=pl;
while(p && j<i)
{
p=p->next;
j++;
}
if(!p || j>i) /* >len or <1 */
printf("Insert fail.../n");
s=(plist)malloc(sizeof(node));
s->data=e;
s->next=p->next;
p->next=s;
}
void display(plist pl)
{
plist p;
p=pl->next;
while(pl && p)
{
printf("%5d", p->data);
p=p->next;
}
printf("/n/n");
}
int getbyid_item(plist pl, int i)
{
plist p=pl->next;
int j=1;
while(p && j<i)
{
p=p->next;
j++;
}
if(!p || j>i) /* >len or <1 */
{
printf("fail.../n");
exit(1);
}
return p->data;
}
int locate_item(plist pl, int e)
{
plist p=pl->next;
int j=1;
while(p->data != e && p->next)
{
p=p->next;
j++;
}
if(p->data == e)
return j;
else
{
printf("There is n %d in list/n", e);
return -1;
}
}
void delete_item(plist pl, int i, int *e)
{
plist p=pl;
plist q;
int j=1;
while(p->next && j<i)
{
p=p->next;
j++;
}
if(!p->next || j>i) /* >len or <1 */
{
printf("fail..../n");
return;
}
q=p->next;
p->next=q->next;
*e=q->data;
free(q);
}
int len_list(plist pl)
{
int j=0;
plist p=pl;
while(pl && p->next)
{
j++;
p=p->next;
}
return j;
}
plist traverse_list(plist pl)
{
plist h, p, s;
if(!pl || !pl->next)
return pl;
h=pl->next;
s=h;
p=s->next;
h->next=NULL;
while(p)
{
s=p;
p=p->next;
s->next=h;
h=s;
}
pl->next=h;
return pl;
}
void main()
{
int len, pos, *del;
plist pl=NULL;
del=(int *)malloc(sizeof(int));
pl=init_list();
isempty_list(pl);
insert_item(pl, 1, 1);
insert_item(pl, 2, 3);
insert_item(pl, 3, 5);
insert_item(pl, 4, 7);
insert_item(pl, 5, 9);
insert_item(pl, 6, 11);
display(pl);
len=len_list(pl);
printf("link list len: %d/n", len);
pos=locate_item(pl, 7);
printf("num 7 pos: %d/n", pos);
delete_item(pl, 3, del);
printf("delete pos 3 num: %d/n", *del);
display(pl);
printf("link list traverse.../n");
pl=traverse_list(pl);
display(pl);
destroy_list(pl);
getch();
}
运行结果：
=================================================
单向循环链表(测试通过)
测试环境： Win-TC
#include <stdio.h>
#include <malloc.h>
struct _node
{
int data;
struct _node *next;
};
typedef struct _node node, *plist;
plist init_list()
{
plist pl=(plist)malloc(sizeof(node));
if(!pl)
{
printf("error malloc fail.../n");
return NULL;
}
pl->data=-1;
pl->next=pl; /* pl->next=NULL */
return pl;
}
void insert_item(plist pl, int pos, int data)
{
int j=0;
plist p,s;
s=p=pl;
while(p && j<pos-1)
{
p=p->next;
j++;
}
if(!p || j>pos-1)
{
printf("Error insert fail.../n");
return;
}
s=(plist)malloc(sizeof(node));
if(!s)
{
printf("Error malloc fail.../n");
return;
}
s->data=data;
s->next=p->next;
p->next=s;
}
int find_item(plist pl, int data)
{
plist s,p;
s=p=pl;
p=p->next;
while(s != p)
{
if(data==p->data)
return 1;
p=p->next;
}
return 0;
}
void delete_item(plist pl, int data)
{
plist p,s;
s=p=pl;
if(data == p->data) /* first item is equal with data, then last item = second item */
{
s=p;
while(s != p->next)
p=p->next;
p->next=s->next;
return;
}
while(s != p->next) /* first item is not equal with data */
{
if(data == p->next->data)
{
p->next=p->next->next;
return;
}
p=p->next;
}
}
void display(plist pl)
{
plist s,p;
s=p=pl;
printf("%5d", p->data); /* print first item */
p=p->next;
while(s != p)
{
printf("%5d", p->data);
p=p->next;
}
printf("/n/n");
}
void main()
{
int f;
plist pl;
pl=init_list();
insert_item(pl, 1, 1);
insert_item(pl, 2, 3);
insert_item(pl, 3, 5);
insert_item(pl, 4, 7);
insert_item(pl, 5, 9);
display(pl);
printf("Finding 3.../n");
f=find_item(pl, 3);
if(f)
printf("True find 3/n");
else
printf("False find 3.../n");
printf("/nDeleting 1.../n");
delete_item(pl->next, 1);
display(pl->next);
getch();
}
运行结果：
=================================================
双向循环链表(测试通过)
测试环境： Win-TC
#include <stdio.h>
#include <malloc.h>
struct _node
{
int data;
struct _node *prior;
struct _node *next;
};
typedef struct _node node, *plist;
plist init_list()
{
plist p;
p=(plist)malloc(sizeof(node));
if(!p)
{
printf("Error, malloc fail.../n");
return NULL;
}
p->data=-1; /* head->data = -1 */
p->prior=p;
p->next=p;
return p;
}
void insert_item(plist pl, int pos, int data)
{
int j=0;
plist s,p;
p=pl;
while(p && j<pos-1)
{
p=p->next;
j++;
}
if(!p || j>pos-1) /* pos is less than 1 or pos larger than len_list+1 */
{
printf("Error %d is invalide num.../n", pos);
return;
}
s=(plist)malloc(sizeof(node));
if(!s)
{
printf("Error, malloc fail.../n");
return NULL;
}
s->data=data;
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
}
int find_item(plist pl, int data)
{
plist s,p;
s=p=pl;
if(data == p->data)
return 1;
p=p->next;
while(s != p)
{
if(data == p->data)
return 1;
p=p->next;
}
return 0;
}
void delete_item(plist pl, int data)
{
plist s,p;
s=p=pl;
if(data == p->data) /* first check equal */
{
p->prior->next=p->next;
p->next=p->prior;
return;
}
while(s != p->next)
{
if(data == p->next->data)
{
p->next=p->next->next;
p->next->next->prior=p;
}
p=p->next;
}
}
void display(plist pl)
{
plist s,p;
s=p=pl;
printf("%5d", p->data); /* first item, such as head->data is -1 */
p=p->next;
while(s != p)
{
printf("%5d", p->data);
p=p->next;
}
printf("/n/n");
}
void main()
{
int f;
plist pl;
pl=init_list();
insert_item(pl, 1, 1);
insert_item(pl, 2, 3);
insert_item(pl, 3, 5);
insert_item(pl, 4, 7);
insert_item(pl, 5, 9);
display(pl);
printf("Finding 3.../n");
f=find_item(pl->next->next, 3);
if(f)
printf("True find 3/n");
else
printf("Fail find 3.../n");
printf("Finding 6.../n");
f=find_item(pl->prior->prior, 6);
if(f)
printf("True find 6/n");
else
printf("Fail find 6.../n");
printf("/nDeleting 3.../n");
delete_item(pl->next->next, 3);
display(pl);
getch();
}
运行结果：
======================================================
以上代码，均在Win-TC 1.9.1 编译器环境测试通过（测试部分用例）
由于刚刚学习算法，编程水平有限，以上代码多有考虑不周或错误
