2015.2.6
星期五，晴天
今天上课的内容不是很多，包括链表，栈和队列，但是代码量相比以前大了很多，栈和队列分别用了数组和链表两种方法实现了相应的功能。今天很郁闷的一件事是昨晚写的一个程序
让我纠结一天：将一个乱序的数组中的元素有序的插入到一个链表中。找不出来那里出错，边上课边分析，搞了一天，谢了三个不同的测试程序，得到相同的“出错”结果。最后放到
张恒斌的电脑上测试，没有问题。FUCK，程序本身跟本就没有问题，问题出来打印上面，在插入一个乱序的元素并且插一次打印一个元素，是不可能有序的把所有元素打印出来的，
插入程序和打印程序必须分开，教训啊！！！值得高兴的，编写的三个测试程序都是对的。
下面是单链表的程序，最后三个程序实现的是同一个功能：
#include <stdio.h>
#include <stdlib.h>
typedef int data_t;
typedef struct node{
struct node *next;
data_t data;
}linknode_t,*linklist_t,*Pnode;
//linklist_t list;
linklist_t Create_Empty_Linklist()
{
linklist_t list;
list = (linklist_t)malloc(sizeof(linknode_t));
if(list)
{
list->next = NULL;
}
return list;
}
void Clear_Linklist(linklist_t list)
{
linklist_t next_node;
if(list == NULL)
{
return ;
}
while(NULL != list->next)
{
next_node = list->next;
list->next = next_node->next;
free(next_node);
}
return;
}
void Destory_Linklist(linklist_t list)
{
if(list != NULL)
{
Clear_Linklist(list);
free(list);
}
}
int Length_Linklist(linklist_t list)
{
int len = 0;
linklist_t next_node;
if(list == NULL)
{
return -1;
}
next_node = list->next;
while(next_node != NULL)
{
len++;
next_node = next_node->next;
}
return len;
}
int Empty_Linklist(linklist_t list)
{
if(NULL != list)
{
if(NULL == list->next)
{
return 1;
}
else
{
return 2;
}
}
else
{
return -1;
}
}
int Get_Linklist(linklist_t list,int at,data_t *x)
{
linklist_t new_node;
int new_at = 1;
if(list == NULL)
{
return -1;
}
if(at < 0)
{
return -1;
}
new_node = list->next;
while(new_node != NULL)
{
if(new_at == at)
{
if(x)
{
*x = new_node->data;
}
return 0;
}
new_node = new_node->next;
new_at++;
}
return -1;
}
int Set_Linklist(linklist_t list,int at,data_t x)
{
linklist_t new_node;
int new_at = 1;
if(list == NULL)
{
return -1;
}
if(at < 0)
{
return -1;
}
new_node = list->next;
while(new_node != NULL)
{
if(new_at == at)
{
new_node->data = x;
return 0;
}
new_at++;
new_node = new_node->next;
}
return -1;
}
int Insert_Linklist(linklist_t list,int at,data_t x)
{
linklist_t node_prev,node_at,node_new;
int new_at = 1;
if(list == NULL)
{
return -1;
}
if(at < 0)
{
return -1;
}
node_prev = list;
node_at = list->next;
node_new = (linklist_t)malloc(sizeof(linknode_t));
node_new->data = x;
node_new->next = NULL;
while(node_at != NULL)
{
if(new_at == at)
{
node_prev->next = node_new;
node_new->next = node_at;
return 0;
}
new_at++;
node_prev = node_at;
node_at = node_at->next;
}
node_prev->next = node_new;
return 0;
}
int Delete_Linklist(linklist_t list,int at)
{
linklist_t node_prev,node_at;
int new_at = 1;
if(list == NULL)
{
return -1;
}
if(at < 0)
{
return -1;
}
node_prev = list;
node_at = list->next;
while(node_at != NULL)
{
if(new_at == at)
{
node_prev->next = node_at->next;
free(node_at);
return 0;
}
new_at++;
node_prev = node_at;
node_at = node_at->next;
}
return -1;
}
void Reversel_Linklist(linklist_t list)
{
linklist_t node_prev, node_next;
node_prev = list->next;
list->next = NULL;
while(node_prev != NULL)
{
node_next = node_prev;
node_prev = node_next->next;
node_next->next = list->next;
list->next = node_next;
}
return;
}
int Insert_Order_Linklist(linknode_t **plist, int new_value)
{
linklist_t node_prev;
linklist_t node_new ;
while(((node_prev = *plist) != NULL) && (node_prev->data) < new_value )
{
plist = &node_prev->next;
}
node_new = (linklist_t)malloc(sizeof(linknode_t));
if(node_new == NULL)
{
return -1;
}
node_new->data = new_value;
node_new->next = node_prev;
*plist = node_new;
return 1;
}
int Insert_Order_Linklist1(linklist_t list, int new_value)
{
linklist_t node_prev;
linklist_t node_new ;
linklist_t node_at;
node_prev = list;
node_at = list->next;
node_new = (linklist_t)malloc(sizeof(linknode_t));
if(node_new == NULL)
{
return -1;
}
node_new->data = new_value;
while((node_at != NULL ) && (node_at->data < new_value))
{
node_prev = node_at;
node_at = node_at->next;
}
node_new->next = node_at;
node_prev->next = node_new;
return 1;
}
int Insert_Order_Linklist2(linklist_t list, int new_value)
{
linklist_t node_prev;
linklist_t node_new ;
linklist_t node_at;
node_prev = list;
node_at = list->next;
node_new = (linklist_t)malloc(sizeof(linknode_t));
if(node_new == NULL)
{
return -1;
}
node_new->data = new_value;
node_new->next = NULL;
while(node_at != NULL && node_at->data < new_value)
{
node_prev = node_at;
node_at = node_at->next;
}
if(node_at == NULL)
{
node_prev->next = node_new;
}
else
{
node_new->next = node_at;
node_prev->next = node_new;
}
return 1;
}
int main(int argc,char **argv)
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
int c[12] = { 18,10,15,16,14,12,13,17,20,19,22,21};
int b[12];
int i,j=0,length = 0;
data_t *p=&j;
linklist_t list;
putchar(‘\n‘);
printf("a[] = {");
for(i = 0; i < 10; i++)
{
printf("%5d",a[i]);
}
printf("}\n");
list = Create_Empty_Linklist();
Clear_Linklist(list);
Empty_Linklist(list);
printf("list ");
for(i = 0; i < 10; i++)
{
Insert_Linklist(list,i+1,a[i]);
Get_Linklist(list,i+1,&b[i]);
printf("->%d",b[i]);
}
printf("->NULL\n");
printf("list_length = %d\n",Length_Linklist(list));
Reversel_Linklist(list);
printf("list ");
for(i = 0; i < 10; i++)
{
Get_Linklist(list,i+1,&b[i]);
printf("->%d",b[i]);
}
printf("->NULL\n");
Get_Linklist(list,5,p);
printf("linklist number five is => %d\n",*p);
printf("==>delete five element of linklist\n");
Delete_Linklist(list,5);
length=Length_Linklist(list);
printf("now list_length = %d\n",length);
printf("list ");
for(i = 0; i < length; i++)
{
Get_Linklist(list,i+1,&b[i]);
printf("->%d",b[i]);
}
printf("->NULL\n");
printf("==>modify the number five and insert an element 100 in three member\n");
Set_Linklist(list,4,200);
Insert_Linklist(list,2,100);
length=Length_Linklist(list);
printf("now list_length = %d\n",length);
printf("list ");
for(i = 0; i < length; i++)
{
Get_Linklist(list,i+1,&b[i]);
printf("->%d",b[i]);
}
printf("->NULL\n");
printf("==>at last,the release list\n");
Clear_Linklist(list);
printf("Empty list length = %d \n",Length_Linklist(list));
Destory_Linklist(list);
list = NULL;
printf("now list_length after destory = %d\n",Length_Linklist(list));
printf("==>create a list again\n");
list = Create_Empty_Linklist();
Clear_Linklist(list);
Empty_Linklist(list);
list->next = NULL;
for(i = 0; i <12; i++)
{
Insert_Order_Linklist(&list ,c[i]);
}
length=Length_Linklist(list);
printf("list ");
for(i = 0; i < length; i++)
{
Get_Linklist(list,i+1,&b[i]);
printf("->%d",b[i]);
}
printf("->NULL\n");
printf("list_length = %d\n",Length_Linklist(list));
putchar(‘\n‘);
return 0;
}
执行效果：
lg@lg-desktop:/mnt/hgfs/source test/pdf$ gcc testlink.c
lg@lg-desktop:/mnt/hgfs/source test/pdf$ ./a.out
a[] = { 1 2 3 4 5 6 7 8 9 10}
list ->1->2->3->4->5->6->7->8->9->10->NULL
list_length = 10
list ->10->9->8->7->6->5->4->3->2->1->NULL
linklist number five is => 6
==>delete five element of linklist
now list_length = 9
list ->10->9->8->7->5->4->3->2->1->NULL
==>modify the number five and insert an element 100 in three member
now list_length = 10
list ->10->100->9->8->200->5->4->3->2->1->NULL
==>at last,the release list
Empty list length = 0
now list_length after destory = -1
==>create a list again
list ->10->12->13->14->15->16->17->18->19->20->21->22->NULL
list_length = 12
lg@lg-desktop:/mnt/hgfs/source test/pdf$
原文：http://www.cnblogs.com/cnlg/p/4279502.html