C语言单链表-增强
C语言创建单链表-入门部分的代码存在一系列问题，现在在其基础上写了第二版，改进了入门部分代码的问题并增强了其功能。
代码在“C语言网”为：
http://bbs.cyuyan.com.cn/thread-5310-1-1.html
#include <stdio.h> #include <malloc.h> #include <string.h> #include <ctype.h>#include <process.h> /************************************************************************ * Name :linked_list(单链表) * Author :luchunli * Date :2012-03-20 * Description :对链表的基本操作，如链表的创建、查找、插入、删除、翻转等 * Environment:Turbo C/C++ for windows集成实验域学习环境2007.5 * Functions:void help (void) *void print (const struct node * head) *int getNo (void) *int isExists (struct node * q, int no) *struct node * create (struct node * head) *void queryByNo (const struct node * head) *void queryByName (const struct node * head) * struct node * insert (struct node * head) * struct node * delete (struct node * head) * struct node * reverse (struct node * head) * ---------------------------------- * TimeModifierComment * 2012/03/22luchunli容错处理和功能扩展(链表翻转) * *************************************************************************/#define TRUE 1#define FALSE 0static const int ZERO = 0;/** 声明一个结构体,名称为node*/struct node {int no;char name[20];struct node * next;};/*** Author : luchunli* Description : 帮助* Date : 2012-03-22*/void help (void) {printf("1、新建链表(create)\n");printf("2、根据编号查找(q_by_no)\n");printf("3、根据名称查找(q_by_name)\n");printf("4、插入指定编号的节点(insert)\n");printf("5、删除指定编号的节点(delete)\n");printf("6、链表翻转(reverse)\n");printf("7、查看链表节点数据(print)\n");printf("8、清除屏幕显示(clear)\n");printf("9、退出系统(exit)\n");printf("10、帮助信息(?)\n");}/*** Author : luchunli* Date : 2012-03-21* Description : 打印链表的数据*/void print (const struct node * head) {struct node * q = head;/**/while(NULL != q) {printf("no is %d and name is '%s'.\n", q->no, q->name);q = q->next;}}/*** Author : luchunli* Date : 2012-03-20* Description : 获取编号(执行校验或得到一个有效的编号)* 关于scanf函数返回值的问题：1、若函数中只存在一种输入,即scanf("%d", &m),如果输入成功返回值为1，不成功返回值为0;2、若函数中存在多种输入,即scanf("%d %d %d", &m, &n, &k),如果输入的数据a为整数,b、c为无效数据,则返回1;如果输入的数据a、b为整数,c为无效数据,则返回2;如果输入的数据a、b、c均为整数,则返回3;如果a、b、c均为无效数据,则返回0。问题一：当我们执行scanf("%d", &m),但是如果我的输入为非数字的话(如一个字符),则会出现刷屏现象,即屏幕不停的滚动,这是因为%d不能接收的缘故。解决方式：使用k = scanf("%d", &m);然后判断k的值问题二：使用上述方式可以解决刷屏问题,但是当前输入的字符会影响下次的输入,因为键盘缓冲区就可能还有残余信息。解决方式：使用fflush(stdin);刷新缓冲区,可以清理掉标准输入流中的缓存数据;同理,标准输出流为stdout。扩展：scanf()函数应该只是扫描stdin流。问题三：使用scanf("%c", &c);时\n和\w等都会赋值给字符c */int getNo (void) {int no = ZERO;while(!scanf("%d", &no) || no < ZERO) {/*保证输入的是有效的整数(而非字符或负数)*/fflush(stdin);/*刷新缓冲区*/printf("编号输入错误,请输入编号(整数(1~65535)):");}return no;}/*** Author : luchunli* Date : 2012-03-20* Description : 判定指定编号的节点是否已存在*/int isExists (struct node * q, int no) {while(q) {if (q->no == no) {return TRUE;}q = q->next;}return FALSE;}/*** Author : luchunli* Date : 2012-03-21* Description : 新建链表* 现在暂未使用该种创建链表的方式,因为这种方式在创建时每次都在最后添加新的节点,而不是根据编号的大小来创建有序的链表,详见insert()方法。*/struct node * create (struct node * head) {/*定义局部结构体类型的变量*/struct node * p = NULL;struct node * q = NULL;/*定义局部整形变量*/int no = 0;/*获取编号*/printf("请输入节点编号(输入0表示结束):");no = getNo();while (ZERO != no) {p = (struct node *)malloc(sizeof(struct node));if (NULL == p) {printf("内存空间不足,分配失败!");exit(1);}/**/p->no = no;printf("请输入编号 %d 处的名称:", p->no);scanf("%s", p->name);printf("\n");/*每次有新的节点时都链接到链表的末尾*/if (NULL == head) {head = p;} else {q->next = p;}q = p;q->next = NULL;/**//**/printf("请继续输入编号(输入0表示结束):");no = getNo();while(isExists(head, no)) {printf("编号已存在,请重新输入:");no = getNo();}}printf("\n");return head;}/*** Author : luchunli* Date : 2012-03-20* Description : 从链表中查找特定编号的节点*/void queryByNo (const struct node * head) {struct node * q = NULL;int no = ZERO;printf("请输入查找的节点编号(输入0表示结束):");no = getNo();while (ZERO != no) {q = head; /*必须的*/while(NULL != q) {if (q->no == no) {printf("编号为 %d 处的节点名称为:%s\n", q->no, q->name);break;}q = q->next;}if (NULL == q) {/*找到链表最后都没有找到该编号的节点*/printf("编号为 %d 的节点不存在.\n", no);}/**/printf("请继续输入查找的节点编号(输入0表示结束):");no = getNo();}printf("\n");}/*** Author : luchunli* Date : 2012-03-20* Description : 从链表中查找特定名称的节点*/void queryByName (const struct node * head) {struct node * q = NULL;char name[20] = {'\0'};int flag = ZERO;printf("请输入查找的节点名称(输入0表示结束):");scanf("%s", name);while(ZERO != strcmp(name, "0")) {/*相等返回0,结束while循环*/q = head; /*必须的*/flag = 0;while(NULL != q) {if (0 == strcmp(name, q->name)) {printf("名称为 %s 处的节点为:%d\n", q->name, q->no);if (!flag) {flag = 1;/*找到了*/}/*可能不同编号的节点有相同的名称*//*break;*/}q = q->next;}if (!flag) {printf("名称为 %s 的节点不存在.\n", name);}/**/printf("请输入继续查找的节点的名称(输入0表示结束):");scanf("%s", name);}printf("\n");}/*** Author : luchunli* Date : 2012-03-20* Description : 向链表中指定位置处插入指定编号的节点*/struct node * insert (struct node * head) {struct node * q = NULL;/*遍历链表时指向不同的节点*/struct node * p = NULL;/*指向每次分配的空间*/struct node * temp = NULL;int no = ZERO;printf("请输入新节点编号(输入0表示结束):");no = getNo();while(isExists(head, no)) {printf("编号已存在,请重新输入:");no = getNo();}while (ZERO != no) {p = (struct node *)malloc(sizeof(struct node));if (NULL == p) {printf("内存空间不足,分配失败!");exit(1);}p->no = no;printf("请输入编号为 %d 处的节点的名称:", no);scanf("%s", p->name);if (NULL == head) {/*空链表*/head = p;} else {if (no < head->no) {/*放在头节点之前*/p->next = head;head = p;} else{/*放在头节点之后*/q = head;temp = q->next;/*需要用temp来比较,而q节点记录其前一个节点,以便新节点接入链表*/while (NULL != temp) { if (no < temp->no) { p->next = q->next; q->next = p; q = NULL;/*在链表最后节点之前找到新则插入新节点,同时使p指向NULL,否则说明找到最后都没有找到*/ break; } q = temp; temp = q->next;}if (NULL != q) {/*p不为空说明在链表中未找到插入的合适位置,在最后插入*/q->next = p;q = p;q->next = NULL;}}}/*输出链表*/printf("\n");print (head);printf("\n");printf("请继续输入新节点编号(输入0表示结束):");no = getNo();while(isExists(head, no)) {printf("编号已存在,请重新输入:");no = getNo();}}printf("\n");return head;}/*** Author : luchunli* Date : 2012-03-20* Description : 从链表中删除特定编号的节点*/struct node * delete (struct node * head) {struct node * q = NULL;/*遍历链表时指向不同的节点*/struct node * temp = NULL;int no = ZERO;printf("请输入删除的节点编号(输入0表示结束):");no = getNo();while (ZERO != no && !isExists(head, no)) {printf("编号不存在,请重新输入:");no = getNo();}while (ZERO != no) {if (NULL == head) {/*保证q = head;和q->next处不会报地址访问错误*/printf("当前链表为空!\n");} else {q = head;if (no == head->no) {/*要删除的不是第一个节点*//*q = head;就是为了后面的free(p);*/head = head->next;free(q);/*先使q指向head处的内存单元,head指向其next内存单元后,释放其原来占有的内存单元,用p来标识该单元*/} else {temp = q->next;/*temp的作用和q=head;处head的作用一样,记下内存单元,方便free*/while (NULL != temp) {if (no == q->next->no) {q->next = q->next->next;free(temp);/*free q的next指向的内存单元*/break;/*跳出while*/}q = q->next;temp = q->next;/* 用q记下需要删除的节点的previous,因为我们这里的是单向链表 */}}}/*输出链表*/printf("\n");print (head);printf("\n");printf("请继续输入删除的节点编号(输入0表示结束):");no = getNo ();while (ZERO != 0 && !isExists(head, no)) {printf("编号不存在,请重新输入:");no = getNo();}}printf("\n");return head;}/*** Author : luchunli* Description : 链表翻转* Date : 2012-03-22*/struct node * reverse (struct node * head) {struct node * newhead = NULL;/*必须每次都将最后的节点摘下来*/struct node * q = NULL;struct node * p = NULL;struct node * temp = NULL;if (NULL == head) {return head;} else {q = head;while (NULL != q->next) {/*用q的next记下哪个节点需要被从链表上摘下来,next域存储的节点的地址*/if (NULL == q->next->next) {/*注意:必须要通过next的next来实现*/if (NULL == newhead) {newhead = q->next;}else {p->next = q->next;}p = q->next;p->next = NULL;q->next = NULL;q = head;continue;/*当找到最后一个节点后,然后再从头head开始找*/}q = q->next;}p->next = q;p = q;p->next = NULL;/** 此时q和head都仍然指向第一个节点,也就是newhead指向的链表的最后一个节点*/}/*printf("\n----------------------ori~head~begin---------------------\n");print(head);printf("----------------------ori~head~end---------------------\n");printf("----------------------new~head~begin---------------------\n");print(newhead);printf("----------------------new~head~end---------------------\n");*/return newhead;}/*** Author : luchunli* Date : 2012-03-20* Description : 程序入口地址*/int main(int argc, char * argv[]) {/*定义结构体类型的变量*/struct node * head = NULL;/*操作类型*/char optype[20] = {'\0'};help();printf("\n");printf("请输入希望执行的操作的类型:");scanf("%s", optype);while (0 != strcmp(optype, "exit")) {if (0 == strcmp(optype, "create")) {/*创建链表*/head = insert (head);/*输出链表*/print (head);} else if (0 == strcmp(optype, "q_by_no")) {/*从链表中查找特定编号的节点*/queryByNo (head);} else if (0 == strcmp(optype, "q_by_name")) {/*从链表中查找特定名称的节点*/queryByName (head);} else if (0 == strcmp(optype, "insert")) {/*向链表中指定位置处插入指定编号的节点*/head = insert (head);/*输出链表*/print (head);} else if (0 == strcmp(optype, "delete")) {/*从链表中删除特定编号的节点*/head = delete (head);/*输出链表*/print (head);} else if (0 == strcmp(optype, "reverse")) {/*链表翻转*/head = reverse (head);/*输出链表*/print (head);} else if (0 == strcmp(optype, "print")) {/*输出链表*/print (head);} else if (0 == strcmp(optype, "clear")) {/*清除屏幕缓冲区及液晶显示缓冲区*/system("cls"); /*clrscr();*/} else if (0 == strcmp(optype, "?")) {/*帮助信息*/help();} else {help();}printf("\n");printf("请输入希望执行的操作的类型:");scanf("%s", optype);}return 0;}