C语言实现数据结构的链表

链表是用一组任意的存储单元来存放线性表的结点.

为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址信息,这个信息称为指针或链

下面是C语言实现链表的数据结构及基本的算法。

# include <stdio.h>
# include <stdlib.h>
typedef char DataType;   //定义节点数据域类型
typedef struct node      //节点类型定义
{
 DataType data;      //节点的数据域
 struct node *next;  //节点的指针域指向下一个节点
}ListNode;
typedef ListNode *LinkList;
ListNode *p;   //定义节点指针
LinkList head; //定义链表头指针


/*错误信息输出函数*/
void Error(char *message)
{
 fprintf(stderr,"Error:%s/n",message); //输出错误信息
 exit(1);//终止程序，返回1给操作系统
}

/*打印输出链表*/
void printList(LinkList head)
{
 ListNode *p; //节点
 int i=0;
 if(head!=NULL)
 {
  p=head;
  while(p->next!=NULL)
  {
   p=p->next;
   printf("node[%d]=%c/n",i,p->data);
   i++;
  }

 }
}

/*创建链表*/
LinkList CreateList()
{
 char ch;
 LinkList head=(LinkList)malloc(sizeof(ListNode));//生成头节点
 ListNode *s,*r;
 r=head;
 head->data=''*'';
 while((ch=getchar())!=''/n'')
 {
  s=(LinkList)malloc(sizeof(ListNode));
  s->data=ch;
  r->next=s;
  r=s;
 }
 r->next=NULL;
 return head;
}

/*取得第i个结点*/
ListNode * getNode(LinkList head,int i)
{
 int j=0;
 ListNode *p;
 p=head;
 while(p->next!=NULL)
 {
  p=p->next;
  j++;
  if(j==i)
  {
   return p;
  }
 }
 return NULL;
}

/*根据结点值域找到结点*/
ListNode * getNodeByKey(LinkList head,DataType key)
{
 int j=0;
 ListNode *p;
 char nodeData;
 p=head;
 while(p->next!=NULL)
 {
  p=p->next;
  nodeData=p->data;
  if(key==nodeData)
  {
   return p;
  }
 }
 return NULL;
}
/*插入结点*/
void insertList(LinkList head,DataType x,int i)
{
 ListNode *p,*s;
 p=getNode(head,i-1);
 if(p==NULL)
 {
  Error("position error");
 }
 s=(ListNode *)malloc(sizeof(ListNode));
 s->data=x;
 s->next=p->next;
 p->next=s;
}

/*删除结点*/
void deleteList(LinkList head,int i)
{
 ListNode *p,*r;
 p=getNode(head,i-1);
 if(p==NULL||p->next==NULL)
 {
  Error("position error");
 }
 r=p->next;
 p->next=r->next;
 free(r);
}

void main()
{
 LinkList list;
 ListNode *node;
 int getIndex=4;
 list=CreateList(); //创建链表
 printList(list);
 node=getNode(list,getIndex);  //取得链表中索引为4的节点
 printf("get node%d is%c/n",getIndex,node->data);
 printf("insert X to node %d/n",3);
 insertList(list,''X'',3); //在索引为3的地方插入节点
 printList(list);
 printf("delete %d node/n",3);
 deleteList(list,3);   //删除索引为3的节点
 printList(list);
}