学步园

单链表中链表中结点的结构：分为数据域和指针域两个部分，指针域指示下一个结点的地址
首先设一个head指针指向开始结点，终端结点的指针域为NULL。由于单链表的头指针是唯一的，
所以可以用作链表的名字。

用到的几个函数：
①：void * malloc(unsigned int size);//在内存的动态存储区中分配一个长度为size的连续空间
②：void * calloc(unsigned n,unsigned size); //分配长度为n长度的空间
③：void free(void * p) // 释放p所指向的内存区

建立单链表的方法（将字符放入链表中）

一：头插法建表
在一个空表中，生成新的结点，将读入的数据放到新的结点数据域中，然后将新的结点插入到链表的表头位置
缺点：输入的顺序与链表的顺序相反

二：尾插入法建表
链表结构中有一个尾指针，并始终指向尾结点。操作方法是在空表中，将新的结点存放到头指针中，其余的结点放在其前驱结点的指针域中。
缺点：需要对头结点单独处理。

三。带头结点的尾插法（常规建表法）

开始的结点的位置存放在头结点的指针域中，无论链表是否为空，其头指针是指向头结点的非空指针。
一般在头结点的数据域中存放长度等信息

下面是示例代码

#include "stdlib.h"<br /> #include "stdio.h"</p> <p>typedef char DataType;</p> <p>typedef struct node {<br /> DataType data; //链表的数据域<br /> struct node *next; //链表的指针域<br /> } ListNode;</p> <p>typedef ListNode *LinkList;</p> <p>void Error(char * message)<br /> {<br /> fprintf(stderr,"Error:%s/n",message);<br /> exit(1);<br /> }</p> <p>// 头插法建表--生成链表节点的次序和输入相反<br /> LinkList CreateListF(void)<br /> {<br /> char ch;<br /> LinkList head; //头指针<br /> ListNode *s; //工作指针<br /> head = NULL; //链表开始为空<br /> ch = getchar();<br /> while(ch!='/n') {<br /> s=(LinkList)malloc(sizeof(ListNode));//生成新的节点<br /> s->data=ch;<br /> s->next=head; //将节点*s插到单链表head的头上<br /> head = s; //重新定义头指针<br /> ch=getchar();<br /> }<br /> return head;<br /> }</p> <p>// 尾插法建表<br /> LinkList CreateListR(void)<br /> {<br /> char ch;<br /> LinkList head;<br /> ListNode *s, *r; //r为尾指针<br /> head=NULL; r=NULL; // 链表初始值为空<br /> ch = getchar();<br /> while(ch!='/n') {<br /> s=(LinkList)malloc(sizeof(ListNode)); //生成新的节点<br /> s->data=ch;<br /> if(head==NULL) {<br /> head=s; //开始的节点的位置存在head中<br /> }else{<br /> r->next=s; // 其余的节点在其前驱节点的指针域中。<br /> }<br /> r=s; //尾指针指向新的表尾<br /> ch = getchar();<br /> }</p> <p> if(r!=NULL) {<br /> r->next=NULL; //将尾节点置为空<br /> }<br /> return head;<br /> }</p> <p>// 有头结点的单链表(通常用法)<br /> LinkList CreateListR1(void)<br /> {<br /> char ch;<br /> LinkList head = (LinkList)malloc(sizeof(ListNode));//生成一个头结点<br /> ListNode *s,*r;<br /> r=head; //尾结点初始值指向头结点<br /> while((ch=getchar())!='/n') {<br /> s=(LinkList)malloc(sizeof(ListNode)); //生成一个新结点<br /> if(s==NULL)<br /> printf("Error!");<br /> s->data=ch; //新结点数据域赋值<br /> r->next=s; //尾结点指针域((*r).next)指向新结点<br /> r=s; //尾指针指向新结点<br /> }<br /> r->next=NULL;<br /> return head;<br /> }<br /> // 按序号查找<br /> ListNode * GetNode(LinkList head,int i)<br /> {<br /> int j;<br /> ListNode *p;<br /> p=head;j=0;<br /> while(p->next&&j<i) {<br /> p=p->next;<br /> j++;<br /> }<br /> if(i==j) {<br /> return p;<br /> }else {<br /> return NULL;<br /> }<br /> }<br /> // 按值查找<br /> ListNode * LocateNode(LinkList head,DataType val) {<br /> ListNode *p=head->next;<br /> while(p&&p->data!=val) {<br /> p=p->next;<br /> }<br /> return p;<br /> }<br /> // 插入运算(将x插入到第i个结点上)<br /> void InsertList(LinkList head,DataType x,int i) {<br /> ListNode *s; // 工作指针<br /> ListNode *p;<br /> p=GetNode(head,i-1); // 找到第i-1个结点<br /> if(p==NULL) {<br /> Error("position error");<br /> }<br /> s=(LinkList)malloc(sizeof(ListNode)); //生成一个新结点<br /> s->data =x; // 将x赋值于新结点的数据域<br /> s->next = p->next; // 新结点的指针域指向原来的指针域<br /> p->next = s; // 原来的指针域指向新的结点<br /> }</p> <p>// 删除运算(删除第i个结点)<br /> void DeleteList(LinkList head,int i) {<br /> ListNode *p,*r;<br /> p=GetNode(head,i-1); // 找到第i-1个结点<br /> if(p==NULL||p->next==NULL) {<br /> Error("position error");<br /> }<br /> r=p->next; // r指向要删除的结点<br /> p->next=r->next; // 第i-1个结点的指针域指向要删除结点的后继结点<br /> free(r); // 释放删除的结点<br /> }</p> <p>// 打印链表<br /> void PrintAll(LinkList head) {<br /> ListNode *p;<br /> p=head;<br /> printf("链表元素一览：/n");<br /> while(p!=NULL) {<br /> printf("%c/n",p->data);<br /> p=p->next;<br /> }<br /> }</p> <p>main() {<br /> //ListNode *L1=CreateListF();<br /> //ListNode *L2 = CreateListR();</p> <p> ListNode *L3 = CreateListR1();<br /> ListNode *p;<br /> int i=2;<br /> //PrintAll(L1);<br /> //PrintAll(L2);<br /> PrintAll(L3);<br /> p=GetNode(L3,i);<br /> printf("第%d个元素为：%c/n",i,p->data);<br /> printf("添加一个结点后：");<br /> InsertList(L3,'P',3);<br /> PrintAll(L3);<br /> printf("删除后：");<br /> DeleteList(L3,3);<br /> PrintAll(L3);<br /> }