参考http://student.zjzk.cn/course_ware/data_structure/web/xianxingbiao/xianxingbiao2.3.1.2.htm
（1） 头插法建表
① 算法思路从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。
动画演示: <-----------------
② 具体算法实现
LinkList CreatListF(void)
{//返回单链表的头指针
char ch;
LinkList head;//头指针
ListNode *s; //工作指针
head=NULL; //链表开始为空
ch=getchar(); //读入第1个字符
while(ch!='\n'){
s=(ListNode *)malloc(sizeof(ListNode));//生成新结点
s->data=ch; //将读入的数据放入新结点的数据域中
s->next=head;
head=s;
ch=getchar(); //读入下一字符
}
return head;
}
创建一个链表,并倒置输出:
/*链式存储相关面试体 **单链表的翻转 要求10分钟写出代码,注意代码风格以及时间复杂的/空间复杂度 ** 考点:(1)基本概念;链表基础; 代码规范问题; 代码健壮性问题 ** (2)对时间复杂度的敏感 */ #include <stdio.h> #include <stdlib.h> typedef struct node { int iData; struct node *next; }LNode,*LinkList; LinkList Link_insert(LinkList p,int num) { LinkList temp = NULL; temp=(LinkList)malloc(sizeof(LNode)); if(NULL == temp) { perror("malloc");exit(EXIT_FAILURE); } temp->iData = num; temp->next= p; p=temp; return p; } void Link_print(LinkList temp) { while(temp!=NULL) { printf("%d\t",temp->iData); temp = temp->next; } printf("\n"); } LinkList reverse_link(LinkList list) { //以头插法实现链表的翻转,head指针不动,从第一个节点开始一直将后续节点插入head之后,//依次将第一个节点到最后一个节点插入它头节点与第一个节点(不断变化)之间即可 if(NULL == list || NULL == list->next) return list; //初始化 LinkList temp,prev,next; prev = list; temp = list->next; prev->next = NULL; while(temp != NULL) { next = temp->next; //存下未遍历的节点 temp->next = prev; //将当前遍历的节点连上第一个节点 prev = temp; //将头节点连上当前遍历的节点 temp = next; //遍历下一个节点 } return prev; } int main(int argc,char *argv[]) { LinkList head=NULL; int temp = 0; int i; for(i=0;i<10;i++) { printf("input number:"); scanf("%d",&temp); head=Link_insert(head,temp); Link_print(head); } head = reverse_link(head); Link_print(head); return 0; }
