Chinaunix首页 | 论坛 | 博客
  • 博客访问: 654284
  • 博文数量: 63
  • 博客积分: 1265
  • 博客等级: 中尉
  • 技术积分: 789
  • 用 户 组: 普通用户
  • 注册时间: 2010-04-06 21:54
文章分类

全部博文(63)

文章存档

2017年(1)

2016年(3)

2015年(2)

2013年(5)

2012年(20)

2011年(32)

分类: C/C++

2011-07-03 10:37:52

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

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

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

  1. # include <stdio.h>
  2. # include <stdlib.h>
  3. typedef char DataType; //定义节点数据域类型
  4. typedef struct node //节点类型定义
  5. {
  6.  DataType data; //节点的数据域
  7.  struct node *next; //节点的指针域指向下一个节点
  8. }ListNode;
  9. typedef ListNode *LinkList;
  10. ListNode *p; //定义节点指针
  11. LinkList head; //定义链表头指针


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

  18. /*打印输出链表*/
  19. void printList(LinkList head)
  20. {
  21.  ListNode *p; //节点
  22.  int i=0;
  23.  if(head!=NULL)
  24.  {
  25.   p=head;
  26.   while(p->next!=NULL)
  27.   {
  28.    p=p->next;
  29.    printf("node[%d]=%c/n",i,p->data);
  30.    i++;
  31.   }
  32.   
  33.  }
  34. }

  35. /*创建链表*/
  36. LinkList CreateList()
  37. {
  38.  char ch;
  39.  LinkList head=(LinkList)malloc(sizeof(ListNode));//生成头节点
  40.  ListNode *s,*r;
  41.  r=head;
  42.  head->data=''*'';
  43.  while((ch=getchar())!=''/n'')
  44.  {
  45.   s=(LinkList)malloc(sizeof(ListNode));
  46.   s->data=ch;
  47.   r->next=s;
  48.   r=s;
  49.  }
  50.  r->next=NULL;
  51.  return head;
  52. }

  53. /*取得第i个结点*/
  54. ListNode * getNode(LinkList head,int i)
  55. {
  56.  int j=0;
  57.  ListNode *p;
  58.  p=head;
  59.  while(p->next!=NULL)
  60.  {
  61.   p=p->next;
  62.   j++;
  63.   if(j==i)
  64.   {
  65.    return p;
  66.   }
  67.  }
  68.  return NULL;
  69. }

  70. /*根据结点值域找到结点*/
  71. ListNode * getNodeByKey(LinkList head,DataType key)
  72. {
  73.  int j=0;
  74.  ListNode *p;
  75.  char nodeData;
  76.  p=head;
  77.  while(p->next!=NULL)
  78.  {
  79.   p=p->next;
  80.   nodeData=p->data;
  81.   if(key==nodeData)
  82.   {
  83.    return p;
  84.   }
  85.  }
  86.  return NULL;
  87. }
  88. /*插入结点*/
  89. void insertList(LinkList head,DataType x,int i)
  90. {
  91.  ListNode *p,*s;
  92.  p=getNode(head,i-1);
  93.  if(p==NULL)
  94.  {
  95.   Error("position error");
  96.  }
  97.  s=(ListNode *)malloc(sizeof(ListNode));
  98.  s->data=x;
  99.  s->next=p->next;
  100.  p->next=s;
  101. }

  102. /*删除结点*/
  103. void deleteList(LinkList head,int i)
  104. {
  105.  ListNode *p,*r;
  106.  p=getNode(head,i-1);
  107.  if(p==NULL||p->next==NULL)
  108.  {
  109.   Error("position error");
  110.  }
  111.  r=p->next;
  112.  p->next=r->next;
  113.  free(r);
  114. }

  115. void main()
  116. {
  117.  LinkList list;
  118.  ListNode *node;
  119.  int getIndex=4;
  120.  list=CreateList(); //创建链表
  121.  printList(list);
  122.  node=getNode(list,getIndex); //取得链表中索引为4的节点
  123.  printf("get node%d is%c/n",getIndex,node->data);
  124.  printf("insert X to node %d/n",3);
  125.  insertList(list,''X'',3); //在索引为3的地方插入节点
  126.  printList(list);
  127.  printf("delete %d node/n",3);
  128.  deleteList(list,3); //删除索引为3的节点
  129.  printList(list);
  130. }

阅读(1325) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~