单链表的基本运算

单链表的定义

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. typedef char ElemType;
  4. typedef struct node
  5. {
  6. ElemType data; /*数据域*/
  7. struct node *next; /*指针域*/
  8. } SLink;

初始化单链表

  1. void InitList(SLink *&L) /*L作为引用型参数*/
  2. {
  3. L=(SLink *)malloc(sizeof(SLink)); /*创建头结点*L*/
  4. L->next=NULL;
  5. }

求线性表的长度

  1. int GetLength(SLink *L) /*求线性表的长度*/
  2. {
  3. int i=0;
  4. SLink *p=L->next;
  5. while (p!=NULL)
  6. {
  7. i++;
  8. p=p->next;
  9. }
  10. return i;
  11. }

求线性表中第i个元素

  1. int GetElem(SLink *L,int i,ElemType &e) /*求线性表中第i个元素*/
  2. {
  3. int j=1;
  4. SLink *p=L->next;
  5. if (i<1 || i>GetLength(L))
  6. return(0); /*i参数不正确,返回0*/
  7. while (j<i) /*从第1个结点开始找,查找第i个结点*/
  8. {
  9. p=p->next;j++;
  10. }
  11. e=p->data;
  12. return(1); /*返回1*/
  13. }

按值查找

  1. int Locate(SLink *L,ElemType x) /*按值查找*/
  2. {
  3. int i=1;
  4. SLink *p=L->next;
  5. while (p!=NULL && p->data!=x) /*从第1个结点开始查找data域为x的结点*/
  6. {
  7. p=p->next;
  8. i++;
  9. }
  10. if (p==NULL)
  11. return(0);
  12. else
  13. return(i);
  14. }

插入结点

  1. int InsElem(SLink *L,ElemType x,int i) /*插入结点*/
  2. {
  3. int j=1;
  4. SLink *p=L,*s;
  5. s=(SLink *)malloc(sizeof(SLink)); /*创建data域为x的结点*/
  6. s->data=x;s->next=NULL;
  7. if (i<1 || i>GetLength(L)+1)
  8. return 0; /*i参数不正确,插入失败,返回0*/
  9. while (j<i) /*从头结点开始找,查找第i-1个结点,由p指向它*/
  10. {
  11. p=p->next;j++;
  12. }
  13. s->next=p->next; /*将*s的next域指向*p的下一个结点(即第i个结点)*/
  14. p->next=s; /*将*p的next域指向*s,这样*s变成第i个结点*/
  15. return 1; /*插入运算成功,返回1*/
  16. }

删除结点

  1. int DelElem(SLink *L,int i) /*删除结点*/
  2. {
  3. int j=1;
  4. SLink *p=L,*q;
  5. if (i<1 || i>GetLength(L))
  6. return 0; /*i参数不正确,插入失败,返回0*/
  7. while (j<i) /*从头结点开始,查找第i-1个结点,由p指向它*/
  8. {
  9. p=p->next;j++;
  10. }
  11. q=p->next; /*由q指向第i个结点*/
  12. p->next=q->next; /*将*p的next指向*q之后结点,即从链表中删除第i个结点*/
  13. free(q); /*释放第i个结点占用的空间*/
  14. return 1; /*删除运算成功,返回1*/
  15. }

输出单链表

  1. void DispList(SLink *L) /*输出单链表*/
  2. {
  3. SLink *p=L->next;
  4. while (p!=NULL)
  5. {
  6. printf("%c ",p->data);
  7. p=p->next;
  8. }
  9. printf("\n");
  10. }

main

  1. void main()
  2. {
  3. int i;
  4. ElemType e;
  5. SLink *L;
  6. InitList(L); /*初始化单链表L*/
  7. InsElem(L,'a',1); /*插入元素*/
  8. InsElem(L,'c',2);
  9. InsElem(L,'a',3);
  10. InsElem(L,'e',4);
  11. InsElem(L,'d',5);
  12. InsElem(L,'b',6);
  13. printf("线性表:");DispList(L);
  14. printf("长度:%d\n",GetLength(L));
  15. i=3;GetElem(L,i,e);
  16. printf("第%d个元素:%c\n",i,e);
  17. e='a';
  18. printf("元素%c是第%d个元素\n",e,Locate(L,e));
  19. i=4;printf("删除第%d个元素\n",i);
  20. DelElem(L,i);
  21. printf("线性表:");DispList(L);
  22. }