• 双链表的基本运算
    • 双链表的定义
    • 初始化双链表
    • 求表长运算
    • 求线性表中第i个元素
    • 按值查找
    • 插入运算
    • 删除运算
    • 输出线性表
    • main

    双链表的基本运算

    双链表的定义

    1. #include <stdio.h>
    2. #include <malloc.h>
    3. typedef char ElemType;
    4. typedef struct node
    5. {
    6. ElemType data; /*数据域*/
    7. struct node *prior,*next; /*分别指向前驱结点和后继结点的指针*/
    8. } DLink;

    初始化双链表

    1. void InitList(DLink *&L)
    2. {
    3. L=(DLink *)malloc(sizeof(DLink)); /*创建头结点*L*/
    4. L->prior=L->next=NULL;
    5. }

    求表长运算

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

    求线性表中第i个元素

    1. int GetElem(DLink *L,int i,ElemType &e) /*求线性表中第i个元素*/
    2. {
    3. int j=1;
    4. DLink *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(DLink *L,ElemType x) /*按值查找*/
    2. {
    3. int i=1;
    4. DLink *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(DLink *L,ElemType x,int i) /*插入运算*/
    2. {
    3. int j=1;
    4. DLink *p=L,*s;
    5. s=(DLink *)malloc(sizeof(DLink)); /*创建data域为x的结点*/
    6. s->data=x;s->prior=s->next=NULL;
    7. if (i<1 || i>GetLength(L)+1) /*i参数不正确,插入失败,返回0*/
    8. return 0;
    9. while (j<i) /*找到第i-1个结点,由p指向它*/
    10. {
    11. p=p->next;j++;
    12. }
    13. s->next=p->next; /**s的next域指向*p的下一个结点*/
    14. s->prior=p; /**s的prior域指向*p*/
    15. if (p->next!=NULL) /*若*p不是最后结点,则将*p之后结点的prior域指向*s*/
    16. s->next->prior=s;
    17. p->next=s; /**p的next域指向*s*/
    18. return 1; /*插入运算成功,返回1*/
    19. }

    删除运算

    1. int DelElem(DLink *L,int i) /*删除运算*/
    2. {
    3. int j=1;
    4. DLink *p=L,*q;
    5. if (i<1 || i>GetLength(L)) /*i参数不正确,删除失败,返回0*/
    6. return 0;
    7. while (j<i) /*找到第i-1个结点,由p指向它*/
    8. {
    9. p=p->next;j++;
    10. }
    11. q=p->next; /*q指向*p的下一个结点,即要删除的结点*/
    12. p->next=q->next;
    13. if (q->next!=NULL) /*若*q不是最后结点,则将*q之后结点的prior域指向*p*/
    14. q->next->prior=p;
    15. free(q); /*释放第i个结点占用的空间*/
    16. return 1; /*删除运算成功,返回1*/
    17. }

    输出线性表

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

    main

    1. void main()
    2. {
    3. int i;
    4. ElemType e;
    5. DLink *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. }