温州黑帮6.5火拼:单向链表操作详解(一)
来源:百度文库 编辑:偶看新闻 时间:2024/05/01 19:52:21
*
===============================================
作者:rerli
时间:2003-12-05
目的:学习单向链表的创建、删除、
插入(无序、有序)、输出、
排序(选择、插入、冒泡)、反序说明:编译没有任何错误,能生成EXE文件。
这个程序TC2.0中编译生成的EXE文件,
在运行输入节点时出现以下错误(TC2.01中没有任何错误):
scanf : floating point formats not linked
Abnormal program termination
即:struct student中float score字段在输入时,
它不认float数格式,而改为long score却可以正常运行。
但是在TC2.01中float score重新编译、链接、运行很正常。
因此,我认为这是TC2.0在结构类型中的Bug.
================================================
*//*
单向链表的图示:
---->[NULL]
head图1:空链表
---->[p1]---->[p2]...---->[pn]---->[NULL]
head p1->next p2->next pn->next图2:有N个节点的链表
*/#include
#include
#define NULL 0
#define LEN sizeof(struct student)struct student
{
long num; /*学号*/
float score; /*分数,其他信息可以继续在下面增加字段*/
struct student *next; /*指向下一节点的指针*/
};int n; /*节点总数*//*
==========================
功能:创建节点
返回:指向链表表头的指针
==========================
*/
struct student *Create()
{
struct student *head; /*头节点*/
struct student *p1=NULL; /*p1保存创建的新节点的地址*/
struct student *p2=NULL; /*p2保存原链表最后一个节点的地址*/ n = 0; /*创建前链表的节点总数为0:空链表*/
p1 = (struct student *)malloc(LEN); /*开辟一个新节点*/
p2 = p1; /*如果节点开辟成功,则p2先把它的指针保存下来以备后用*/ if (p1 == NULL) /*节点开辟不成功*/
{
printf("\nCann't create it, try it again in a moment!\n");
return NULL;
}
else /*节点开辟成功*/
{
head = NULL; /*开始head指向NULL*/ printf("Please input %d node -- num,score: ",n+1);
scanf("%ld,%f",&(p1->num),&(p1->score)); /*录入数据*/
}
while(p1->num != 0) /*只要学号不为0,就继续录入下一个节点*/
{
n += 1; /*节点总数增加1个*/ if (n==1) /*如果节点总数是1,则head指向刚创建的节点p1*/
{
head = p1;
/*
注意:
此时的p2就是p1,也就是p1->next指向NULL。
这样写目的是与下面else保持一致。
*/
p2->next = NULL;
}
else
{
p2->next = p1; /*指向上次下面刚开辟的节点*/
} p2 = p1; /*把p1的地址给p2保留,然后p1去产生新节点*/
p1 = (struct student *)malloc(LEN);
printf("Please input %d node -- num,score: ",n+1);
scanf("%ld,%f",&(p1->num),&(p1->score));
}
p2->next = NULL; /*此句就是根据单向链表的最后一个节点要指向NULL*/
free(p1); /*释放p1。用malloc()、calloc()的变量都要free()*/
p1 = NULL; /*特别不要忘记把释放的变量清空置为NULL,否则就变成"野指针",即地址不确定的指针。*/
return head; /*返回创建链表的头指针*/
}
/*
===========================
功能:输出节点
返回: void
===========================
*/
void Print(struct student *head)
{
struct student *p; printf("\nNow , These %d records are:\n",n);
p = head;
if(head != NULL) /*只要不是空链表,就输出链表中所有节点*/
{
printf("head is %o\n", head); /*输出头指针指向的地址*/
do
{
/*
输出相应的值:当前节点地址、各字段值、当前节点的下一节点地址。
这样输出便于读者形象看到一个单向链表在计算机中的存储结构,和我们
设计的图示是一模一样的。
*/
printf("%o %ld %5.1f %o\n", p, p->num, p->score, p->next);
p = p->next; /*移到下一个节点*/
}
while (p != NULL);
}
}
/*
==========================
功能:删除指定节点
(此例中是删除指定学号的节点)
返回:指向链表表头的指针
==========================
*//*
单向链表的删除图示:
---->[NULL]
head图3:空链表从图3可知,空链表显然不能删除
---->[1]---->[2]...---->[n]---->[NULL](原链表)
head 1->next 2->next n->next---->[2]...---->[n]---->[NULL](删除后链表)
head 2->next n->next图4:有N个节点的链表,删除第一个节点
结合原链表和删除后的链表,就很容易写出相应的代码。操作方法如下:
1、你要明白head就是第1个节点,head->next就是第2个节点;
2、删除后head指向第2个节点,就是让head=head->next,OK这样就行了。
---->[1]---->[2]---->[3]...---->[n]---->[NULL](原链表)
head 1->next 2->next 3->next n->next---->[1]---->[3]...---->[n]---->[NULL](删除后链表)
head 1->next 3->next n->next图5:有N个节点的链表,删除中间一个(这里图示删除第2个)
结合原链表和删除后的链表,就很容易写出相应的代码。操作方法如下:
1、你要明白head就是第1个节点,1->next就是第2个节点,2->next就是第3个节点;
2、删除后2,1指向第3个节点,就是让1->next=2->next。
*/
struct student *Del(struct student *head, long num)
{
struct student *p1; /*p1保存当前需要检查的节点的地址*/
struct student *p2; /*p2保存当前检查过的节点的地址*/
if (head == NULL) /*是空链表(结合图3理解)*/
{
printf("\nList is null!\n");
return head;
} /*定位要删除的节点*/
p1 = head;
while (p1->num != num && p1->next != NULL) /*p1指向的节点不是所要查找的,并且它不是最后一个节点,就继续往下找*/
{
p2 = p1; /*保存当前节点的地址*/
p1 = p1->next; /*后移一个节点*/
} if (num == p1->num) /*找到了。(结合图4、5理解)*/
{
if (p1 == head) /*如果要删除的节点是第一个节点*/
{
head = p1->next; /*头指针指向第一个节点的后一个节点,也就是第二个节点。这样第一个节点就不在链表中,即删除。*/
}
else /*如果是其它节点,则让原来指向当前节点的指针,指向它的下一个节点,完成删除*/
{
p2->next = p1->next; } free(p1); /*释放当前节点*/
p1 = NULL;
printf("\ndelete %ld success!\n",num);
n -= 1; /*节点总数减1个*/
}
else /*没有找到*/
{
printf("\n%ld not been found!\n",num);
} return head;
}
/*
==========================
功能:插入指定节点的后面
(此例中是指定学号的节点)
返回:指向链表表头的指针
==========================
*//*
单向链表的插入图示:
---->[NULL](原链表)
head---->[1]---->[NULL](插入后的链表)
head 1->next图7 空链表插入一个节点
结合原链表和插入后的链表,就很容易写出相应的代码。操作方法如下:
1、你要明白空链表head指向NULL就是head=NULL;
2、插入后head指向第1个节点,就是让head=1,1->next=NULL,OK这样就行了。 ---->[1]---->[2]---->[3]...---->[n]---->[NULL](原链表)
head 1->next 2->next 3->next n->next---->[1]---->[2]---->[x]---->[3]...---->[n]---->[NULL](插入后的链表)
head 1->next 2->next x->next 3->next n->next图8:有N个节点的链表,插入一个节点(这里图示插入第2个后面)
结合原链表和插入后的链表,就很容易写出相应的代码。操作方法如下:
1、你要明白原1->next就是节点2,2->next就是节点3;
2、插入后x指向第3个节点,2指向x,就是让x->next=2->next,1->next=x。
*/
struct student *Insert(struct student *head, long num, struct student *node)
{
struct student *p1; /*p1保存当前需要检查的节点的地址*/ if (head == NULL) /*(结合图示7理解)*/
{
head = node;
node->next = NULL;
n += 1;
return head;
} p1 = head;
while (p1->num != num && p1->next != NULL) /*p1指向的节点不是所要查找的,并且它不是最后一个节点,继续往下找*/
{
p1 = p1->next; /*后移一个节点*/
}
if (num == p1->num) /*找到了(结合图示8理解)*/
{
node->next = p1->next; /*显然node的下一节点是原p1的next*/
p1->next = node; /*插入后,原p1的下一节点就是要插入的node*/
n += 1; /*节点总数增加1个*/
}
else
{
printf("\n%ld not been found!\n",num);
}
return head;
}
/*
==========================
功能:反序节点
(链表的头变成链表的尾,链表的尾变成头)
返回:指向链表表头的指针
==========================
*//*
单向链表的反序图示:
---->[1]---->[2]---->[3]...---->[n]---->[NULL](原链表)
head 1->next 2->next 3->next n->next[NULL]<----[1]<----[2]<----[3]<----...[n]<----(反序后的链表)
1->next 2->next 3->next n->next head 图9:有N个节点的链表反序
结合原链表和插入后的链表,就很容易写出相应的代码。操作方法如下:
1、我们需要一个读原链表的指针p2,存反序链表的p1=NULL(刚好最后一个节点的next为NULL),还有一个临时存储变量p;
2、p2在原链表中读出一个节点,我们就把它放到p1中,p就是用来处理节点放置顺序的问题;
3、比如,现在我们取得一个2,为了我们继续往下取节点,我们必须保存它的next值,由原链表可知p=2->next;
4、然后由反序后的链表可知,反序后2->next要指向1,则2->next=1;
5、好了,现在已经反序一个节点,接着处理下一个节点就需要保存此时的信息:
p1变成刚刚加入的2,即p1=2;p2要变成它的下一节点,就是上面我们保存的p,即p2=p。
*/
struct student *Reverse(struct student *head)
{
struct student *p; /*临时存储*/
struct student *p1; /*存储返回结果*/
struct student *p2; /*源结果节点一个一个取*/
p1 = NULL; /*开始颠倒时,已颠倒的部分为空*/
p2 = head; /*p2指向链表的头节点*/
while (p2 != NULL)
{
p = p2->next;
p2->next = p1;
p1 = p2;
p2 = p;
}
head = p1;
return head;
}/*
以上函数的测试程序:
提示:根据测试函数的不同注释相应的程序段,这也是一种测试方法。
*/
main()
{
struct student *head;
struct student *stu;
long thenumber; /* 测试Create()、Print()*/
head = Create();
Print(head);
/*测试Del():请编译时去掉注释块*/
/*
printf("\nWhich one delete: ");
scanf("%ld",&thenumber);
head = Del(head,thenumber);
Print(head);
*/ /*测试Insert():请编译时去掉注释块*/ /*
stu = (struct student *)malloc(LEN);
printf("\nPlease input insert node -- num,score: ");
scanf("%ld,%f",&stu->num,&stu->score);
printf("\nInsert behind num: ");
scanf("%ld",&thenumber);
head = Insert(head,thenumber,stu);
free(stu);
stu = NULL;
Print(head);
*/
/*测试Reverse():请编译时去掉注释块*/ /*
head = Reverse(head);
Print(head);
*/
printf("\n");
system("pause");
}/*
下次将接着讲
排序(选择、插入、冒泡)
插入(有序)
希望有兴趣的朋友关注
*/ 本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/rerli/archive/2003/12/07/19038.aspx
===============================================
作者:rerli
时间:2003-12-05
目的:学习单向链表的创建、删除、
插入(无序、有序)、输出、
排序(选择、插入、冒泡)、反序说明:编译没有任何错误,能生成EXE文件。
这个程序TC2.0中编译生成的EXE文件,
在运行输入节点时出现以下错误(TC2.01中没有任何错误):
scanf : floating point formats not linked
Abnormal program termination
即:struct student中float score字段在输入时,
它不认float数格式,而改为long score却可以正常运行。
但是在TC2.01中float score重新编译、链接、运行很正常。
因此,我认为这是TC2.0在结构类型中的Bug.
================================================
*//*
单向链表的图示:
---->[NULL]
head图1:空链表
---->[p1]---->[p2]...---->[pn]---->[NULL]
head p1->next p2->next pn->next图2:有N个节点的链表
*/#include
#include
#define NULL 0
#define LEN sizeof(struct student)struct student
{
long num; /*学号*/
float score; /*分数,其他信息可以继续在下面增加字段*/
struct student *next; /*指向下一节点的指针*/
};int n; /*节点总数*//*
==========================
功能:创建节点
返回:指向链表表头的指针
==========================
*/
struct student *Create()
{
struct student *head; /*头节点*/
struct student *p1=NULL; /*p1保存创建的新节点的地址*/
struct student *p2=NULL; /*p2保存原链表最后一个节点的地址*/ n = 0; /*创建前链表的节点总数为0:空链表*/
p1 = (struct student *)malloc(LEN); /*开辟一个新节点*/
p2 = p1; /*如果节点开辟成功,则p2先把它的指针保存下来以备后用*/ if (p1 == NULL) /*节点开辟不成功*/
{
printf("\nCann't create it, try it again in a moment!\n");
return NULL;
}
else /*节点开辟成功*/
{
head = NULL; /*开始head指向NULL*/ printf("Please input %d node -- num,score: ",n+1);
scanf("%ld,%f",&(p1->num),&(p1->score)); /*录入数据*/
}
while(p1->num != 0) /*只要学号不为0,就继续录入下一个节点*/
{
n += 1; /*节点总数增加1个*/ if (n==1) /*如果节点总数是1,则head指向刚创建的节点p1*/
{
head = p1;
/*
注意:
此时的p2就是p1,也就是p1->next指向NULL。
这样写目的是与下面else保持一致。
*/
p2->next = NULL;
}
else
{
p2->next = p1; /*指向上次下面刚开辟的节点*/
} p2 = p1; /*把p1的地址给p2保留,然后p1去产生新节点*/
p1 = (struct student *)malloc(LEN);
printf("Please input %d node -- num,score: ",n+1);
scanf("%ld,%f",&(p1->num),&(p1->score));
}
p2->next = NULL; /*此句就是根据单向链表的最后一个节点要指向NULL*/
free(p1); /*释放p1。用malloc()、calloc()的变量都要free()*/
p1 = NULL; /*特别不要忘记把释放的变量清空置为NULL,否则就变成"野指针",即地址不确定的指针。*/
return head; /*返回创建链表的头指针*/
}
/*
===========================
功能:输出节点
返回: void
===========================
*/
void Print(struct student *head)
{
struct student *p; printf("\nNow , These %d records are:\n",n);
p = head;
if(head != NULL) /*只要不是空链表,就输出链表中所有节点*/
{
printf("head is %o\n", head); /*输出头指针指向的地址*/
do
{
/*
输出相应的值:当前节点地址、各字段值、当前节点的下一节点地址。
这样输出便于读者形象看到一个单向链表在计算机中的存储结构,和我们
设计的图示是一模一样的。
*/
printf("%o %ld %5.1f %o\n", p, p->num, p->score, p->next);
p = p->next; /*移到下一个节点*/
}
while (p != NULL);
}
}
/*
==========================
功能:删除指定节点
(此例中是删除指定学号的节点)
返回:指向链表表头的指针
==========================
*//*
单向链表的删除图示:
---->[NULL]
head图3:空链表从图3可知,空链表显然不能删除
---->[1]---->[2]...---->[n]---->[NULL](原链表)
head 1->next 2->next n->next---->[2]...---->[n]---->[NULL](删除后链表)
head 2->next n->next图4:有N个节点的链表,删除第一个节点
结合原链表和删除后的链表,就很容易写出相应的代码。操作方法如下:
1、你要明白head就是第1个节点,head->next就是第2个节点;
2、删除后head指向第2个节点,就是让head=head->next,OK这样就行了。
---->[1]---->[2]---->[3]...---->[n]---->[NULL](原链表)
head 1->next 2->next 3->next n->next---->[1]---->[3]...---->[n]---->[NULL](删除后链表)
head 1->next 3->next n->next图5:有N个节点的链表,删除中间一个(这里图示删除第2个)
结合原链表和删除后的链表,就很容易写出相应的代码。操作方法如下:
1、你要明白head就是第1个节点,1->next就是第2个节点,2->next就是第3个节点;
2、删除后2,1指向第3个节点,就是让1->next=2->next。
*/
struct student *Del(struct student *head, long num)
{
struct student *p1; /*p1保存当前需要检查的节点的地址*/
struct student *p2; /*p2保存当前检查过的节点的地址*/
if (head == NULL) /*是空链表(结合图3理解)*/
{
printf("\nList is null!\n");
return head;
} /*定位要删除的节点*/
p1 = head;
while (p1->num != num && p1->next != NULL) /*p1指向的节点不是所要查找的,并且它不是最后一个节点,就继续往下找*/
{
p2 = p1; /*保存当前节点的地址*/
p1 = p1->next; /*后移一个节点*/
} if (num == p1->num) /*找到了。(结合图4、5理解)*/
{
if (p1 == head) /*如果要删除的节点是第一个节点*/
{
head = p1->next; /*头指针指向第一个节点的后一个节点,也就是第二个节点。这样第一个节点就不在链表中,即删除。*/
}
else /*如果是其它节点,则让原来指向当前节点的指针,指向它的下一个节点,完成删除*/
{
p2->next = p1->next; } free(p1); /*释放当前节点*/
p1 = NULL;
printf("\ndelete %ld success!\n",num);
n -= 1; /*节点总数减1个*/
}
else /*没有找到*/
{
printf("\n%ld not been found!\n",num);
} return head;
}
/*
==========================
功能:插入指定节点的后面
(此例中是指定学号的节点)
返回:指向链表表头的指针
==========================
*//*
单向链表的插入图示:
---->[NULL](原链表)
head---->[1]---->[NULL](插入后的链表)
head 1->next图7 空链表插入一个节点
结合原链表和插入后的链表,就很容易写出相应的代码。操作方法如下:
1、你要明白空链表head指向NULL就是head=NULL;
2、插入后head指向第1个节点,就是让head=1,1->next=NULL,OK这样就行了。 ---->[1]---->[2]---->[3]...---->[n]---->[NULL](原链表)
head 1->next 2->next 3->next n->next---->[1]---->[2]---->[x]---->[3]...---->[n]---->[NULL](插入后的链表)
head 1->next 2->next x->next 3->next n->next图8:有N个节点的链表,插入一个节点(这里图示插入第2个后面)
结合原链表和插入后的链表,就很容易写出相应的代码。操作方法如下:
1、你要明白原1->next就是节点2,2->next就是节点3;
2、插入后x指向第3个节点,2指向x,就是让x->next=2->next,1->next=x。
*/
struct student *Insert(struct student *head, long num, struct student *node)
{
struct student *p1; /*p1保存当前需要检查的节点的地址*/ if (head == NULL) /*(结合图示7理解)*/
{
head = node;
node->next = NULL;
n += 1;
return head;
} p1 = head;
while (p1->num != num && p1->next != NULL) /*p1指向的节点不是所要查找的,并且它不是最后一个节点,继续往下找*/
{
p1 = p1->next; /*后移一个节点*/
}
if (num == p1->num) /*找到了(结合图示8理解)*/
{
node->next = p1->next; /*显然node的下一节点是原p1的next*/
p1->next = node; /*插入后,原p1的下一节点就是要插入的node*/
n += 1; /*节点总数增加1个*/
}
else
{
printf("\n%ld not been found!\n",num);
}
return head;
}
/*
==========================
功能:反序节点
(链表的头变成链表的尾,链表的尾变成头)
返回:指向链表表头的指针
==========================
*//*
单向链表的反序图示:
---->[1]---->[2]---->[3]...---->[n]---->[NULL](原链表)
head 1->next 2->next 3->next n->next[NULL]<----[1]<----[2]<----[3]<----...[n]<----(反序后的链表)
1->next 2->next 3->next n->next head 图9:有N个节点的链表反序
结合原链表和插入后的链表,就很容易写出相应的代码。操作方法如下:
1、我们需要一个读原链表的指针p2,存反序链表的p1=NULL(刚好最后一个节点的next为NULL),还有一个临时存储变量p;
2、p2在原链表中读出一个节点,我们就把它放到p1中,p就是用来处理节点放置顺序的问题;
3、比如,现在我们取得一个2,为了我们继续往下取节点,我们必须保存它的next值,由原链表可知p=2->next;
4、然后由反序后的链表可知,反序后2->next要指向1,则2->next=1;
5、好了,现在已经反序一个节点,接着处理下一个节点就需要保存此时的信息:
p1变成刚刚加入的2,即p1=2;p2要变成它的下一节点,就是上面我们保存的p,即p2=p。
*/
struct student *Reverse(struct student *head)
{
struct student *p; /*临时存储*/
struct student *p1; /*存储返回结果*/
struct student *p2; /*源结果节点一个一个取*/
p1 = NULL; /*开始颠倒时,已颠倒的部分为空*/
p2 = head; /*p2指向链表的头节点*/
while (p2 != NULL)
{
p = p2->next;
p2->next = p1;
p1 = p2;
p2 = p;
}
head = p1;
return head;
}/*
以上函数的测试程序:
提示:根据测试函数的不同注释相应的程序段,这也是一种测试方法。
*/
main()
{
struct student *head;
struct student *stu;
long thenumber; /* 测试Create()、Print()*/
head = Create();
Print(head);
/*测试Del():请编译时去掉注释块*/
/*
printf("\nWhich one delete: ");
scanf("%ld",&thenumber);
head = Del(head,thenumber);
Print(head);
*/ /*测试Insert():请编译时去掉注释块*/ /*
stu = (struct student *)malloc(LEN);
printf("\nPlease input insert node -- num,score: ");
scanf("%ld,%f",&stu->num,&stu->score);
printf("\nInsert behind num: ");
scanf("%ld",&thenumber);
head = Insert(head,thenumber,stu);
free(stu);
stu = NULL;
Print(head);
*/
/*测试Reverse():请编译时去掉注释块*/ /*
head = Reverse(head);
Print(head);
*/
printf("\n");
system("pause");
}/*
下次将接着讲
排序(选择、插入、冒泡)
插入(有序)
希望有兴趣的朋友关注
*/ 本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/rerli/archive/2003/12/07/19038.aspx
混沌军团操作详解
化学一题(望有详解)
将单向循环链表改成双向链表
C语言高手:什么是“单向链表”????解释一下!!
带有尾指针的单向循环链表R中,
求常用的单向链表的遍历算法
一数学题求详解
高一周期函数详解
详解一高考数学题
详解高一数学题
详解一高考数学题
一数学题求详解
求助!!用后接法建立一个带头结点的单向链表,并就地逆址该带头结点的单向链表。不甚感激!!
高一数学问题(最好有详解)
谁有setup factory 中action(操作)的使用方法详解?
黑帮生涯:帮派战争 操作详解
假设有一个单向循环链表,其结点含三个域:pre,
编写一个函数,检测两个单向链表P1和P2的内容是否相同
单向晶闸管(可控硅)触发电路!
高一数学教材内容详解
求 庄严 一词详解!
求“唏嘘”一此详解。。
求“唏嘘”一词详解。。
什么是成交量(详解)