à1.数据结构及说明 typedef struct node { int number; struct node *next; }LNode, *LinkList; à2.算法设计及说明 1)建立带头结点的单链表 首先申请空间建立头结点和第一个结点；q指向第一个结点，扫描输入第一个结点的数据；p指向q；while循环，当扫描输入的q的数据域的值不等于结束标志时，p指向新开辟的空间；再输入数据，用于下一次循环判断；p指向q，连接新的q结点；p跳到q上，准备连接下一个新的结点；当循环推出后，置尾结点指针域为空指针；最后返回头结点，链表建立完毕。 2）将值为x的结点插入一个按整数值递增的带头结点的单链表中，仍保持有序 在递增单链表中插入值，使之仍保持有序的关键在于：找到p结点的前驱结点q，然后在q之后插入s即可。 àError LINKLIST.C 43: Type mismatch in redeclaration of ‘list’ 错因分析：list函数在主函数之后，应在主函数之前加以函数声明，或者直接将list函数放在主函数之前即可解决。 à在第一步的基础上，对源程序进行细化和修正时，对新插入的结点S，只给它申请了空间，并未把X的值赋给待插入结点的数据域，导致出来的结果是个随机值，运用了“打印输出”的调试思想，及时的发现了问题并予以改正。 àProgram begin to create the linklist!! Please input the first data: 5 Please input the oter data: 16 Please input the oter data: 31 Please input the oter data: -1 5 16 31 与预期结果吻合，成功实现了用“尾接法”带头节点（便于标识且操作统一）创建线性单链表，并顺次输出各个结点。 àProgram begin to create the linklist!! Please input the first data: 5 Please input the oter data: 16 Please input the oter data: 31 Please input the oter data: 49 Please input the oter data: -1 Before insert X the LinkList is: 5 16 31 49 Pleas input the X's data that you want to insert:43 After insert X the LinkList is: 5 16 31 43 49 与预期结果不吻合，进行一番调试后，终于与正确结果相符。 程序是调试调处来的，写程序时再怎么小心都不过分，经过屡次调试，失败后，最后看见了正确的运行结果，那种成就感、自豪感是不言而喻的。 程序是充满逻辑，充满哲理的；我们应该对每一种情况予以分析，予以假设，使我们的程序足够的健壮，最终方可呈递给用户使用。 写程序时应当勇于尝试，不要惧怕、担心；失败是成功之母，多尝试、换个角度思考、换个方法、换个模式来解决问题。 源程序代码： 步骤1(在TC3、VC++6.0中运行通过)à #include <stdio.h> #include <alloc.h> #include <conio.h> typedef struct node { int number; struct node *next; }LNode, *LinkList; LinkList createlink() { int i; LinkList p, q, head; head = (LinkList)malloc(sizeof(LNode)); /*生成头结点*/ q = (LinkList)malloc(sizeof(LNode)); /*生成第一个结点*/ head->next = q; /*q指向第一个结点*/ printf("Please input the first data:\n"); scanf("%d", &q->number); p = q; while (q->number != -1) { q = (LinkList)malloc(sizeof(LNode)); printf("Please input the oter data:\n"); scanf("%d", &q->number); p->next = q; /*连接q结点*/ p = q; /*p跳到q上，准备连接下一个结点*/ } p->next = NULL; /*置尾结点指针域为空指针*/ return head; /*返回头节点*/ } void list(LinkList head) { LinkList p = head->next; while(p != NULL && p->number != -1) { printf("%3d", p->number); p = p->next; } } void main() { LinkList h; clrscr(); /*清屏*/ printf("Program begin to create the linklist!!\n"); h = createlink(); list(h); } 步骤2(在TC3、VC++6.0中运行通过)à #include <stdio.h> #include <alloc.h> #include <conio.h> typedef struct node { int number; struct node *next; }LNode, *LinkList; LinkList createlink() { int i; LinkList p, q, head; head = (LinkList)malloc(sizeof(LNode)); /*生成头结点*/ q = (LinkList)malloc(sizeof(LNode)); /*生成第一个结点*/ head->next = q; /*q指向第一个结点*/ printf("Please input the first data:\n"); scanf("%d", &q->number); p = q; while (q->number != -1) { q = (LinkList)malloc(sizeof(LNode)); printf("Please input the oter data:\n"); scanf("%d", &q->number); p->next = q; /*连接q结点*/ p = q; /*p跳到q上，准备连接下一个结点*/ } p->next = NULL; /*置尾结点指针域为空指针*/ return head; /*返回头节点*/ } void list(LinkList head) { LinkList p = head->next; while(p != NULL && p->number != -1) { printf("%3d", p->number); p = p->next; } } LinkList insert(LinkList h, int y) { LinkList p, q, s; p = h->next; /*p指向第一个结点*/ while(p != NULL && y > p->number) { p = p->next; /*p继续移动*/ } s = (LinkList)malloc(sizeof(LNode)); /*开辟新结点存放待插入的值X*/ s->number = y; q = h; while(q->next != p) q = q->next; /*找p的前驱结点q*/ s->next = q->next; /*将待插入结点s插在q之后*/ q->next = s; return h; } void main() { LinkList h; int x; clrscr(); /*清屏*/ printf("Program begin to create the linklist!!\n"); h = createlink(); printf("Before insert X the LinkList is:\n"); list(h); printf("\n"); printf("Pleas input the X's data that you want to insert:"); scanf("%d", &x); /*DEBUG:printf("%d\n", x);*/ printf("After insert X the LinkList is:\n"); h = insert(h, x); list(h); }
评论