数据结构---链表

• 单向链表
• • 定义
  • 创建
  • • 建链
    • 建表-头插法
    • 建表-尾插法
  • 遍历
  • • 递归
    • 非递归
  • 求表长
  • 取第i个元素
  • 按值查找
  • 查p结点前驱
  • 查值为e的结点后继
  • 插入元素
  • 删除元素
  • 合并单链表
• 循环链表
• 双向链表
• • 定义
  • 插入
  • 删除

typedef struct node {
     int data;
     struct node  *next;
}LNode, *linkList；

LNode   *h,*p;
//或者
linkList h,p;

头节点：第一个节点的前设节点，可有可无，也就是俗称的表头
头指针：指向（记录）链式存储中第1个节点位置（地址）的指针变量。

int InitList (linkList  &L)//带头节点
{
  L=new LNode ;
  if (L==NULL)
   {printf(“无内存空间可分配”);retutn 0;}
  L->next=NULL;
  return 1;
}

void ListCreat1(linkList &L)
{ //用头插法建立带头结点的单链表
    LNode *p;
    L = new LNode;
    L->next = NULL;   //初始化一个空链表，L为头指针
    scanf(“% d”, &x); //x是和链表元素具有相同类型的变量,假设为整型
    while (x != flag) //flag为结束输入的标志，可自己设置如999
    {
        p = new LNode; //生成新结点
        p->data = x;   //输入元素值
        p->next = L->next;
        L->next = p;      //插入到表头
        scanf(“% d”, &x); //读入下一个元素的值
    }
}

linkList ListCreat2(linkList &L)
{ //用尾插法建立带头结点的单链表
    LNode *r, *p;
    L = new LNode;
    L->next = NULL;
    r = L;
    scanf(“% d”, &x);
    while (x != flag) //设置结束标志
    {
        p = new LNode;
        p->data = x; //赋值元素值
        r->next = p; //在尾部插入新结点
        r = p;       //r 指向新的尾结点
        scanf(“% d”, &x);
    }
    r->next = NULL; //最后结点的指针域放空指针
}

void print(linkList L) //非递归
{
    linkList p = L->next;
    while (p)
    {
        printf(“% d”, p->data);
        p = p->next;
    }
}

void out(linkList p) //递归
{
    if (p)
    {
        printf(“% c”, p->data);
        out(p->next);
    }
}

int  ListLength(linkList  L)
{//求带头结点的单链表的长度
LNode *p; int j; 
p=L->next;      //p指向第一结点
 j=0;							
while(p!=NULL) 
 {
  j++;
  p=p->next;
 } //移动p指向下一结点
return  j;
} 

linkList ListGet(linkList L, int i)
{ //在单链表L中查找第i个元素结点，返回该结点的地址，否则返回空
    LNode *p;
    int j;
    if (i < 1)
    {
        printf(“参数错误”);
        return NULL;
    }
    p = L->next;
    j = 1;
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    if (j == i)
        return p;
    else
        return NULL;
}

linkList ListLocate1(linkList L, int x)
{ //在单链表L中查找值为x的结点，找到后返回其指针，否则返回空
    LNode *p;
    p = L->next;
    while (p != NULL && p->data != x)
        p = p->next;
    if (!p)
    {
        printf(“无值为X的结点”);
        return NULL;
    }
    else
        return p;
}

linkList ListLocate2(linkList L, LNode *p)
{ //在单链表L中求p指向的结点(假定存在）的前驱
    LNode *pre;
    if (L->next == p)
    {
        printf(“p指向第一元素结点，无前驱”);
        return NULL;
    }
    pre = L->next;
    while (pre != NULL && pre->next != p)
        pre = pre->next;
    if (pre)
        return pre;
    else
        return NULL;
}

linkList ListLocate3(linkList L, int e)
{ //在单链表L中求元素值为e的结点(假定存在）的后继
    LNode *p;
    p = L->next;
    while (p != NULL && p->data != e)
        p = p->next;
    if (p == NULL)
    {
        printf(“不存在值为e的结点”);
        return NULL;
    }
    else if (p->next == NULL)
    {
        printf(“值为e的结点是最后一个结点，无后继”);
        return NULL;
    }
    else
        return p->next;
}

void ListInsert(linkList L, LNode *p, int x)
{//在结点p之前插入元素为x的结点
    LNode *pre;
    pre = L;
    while (pre->next != NULL && pre->next != p)
        pre = pre->next; //找p的直接前驱
    if (!pre->next)
    {
        printf(“不存在 * p结点”) ；return;
    }
    s = new Lnode; //创建新结点
    s->data = x;   //设置新结点的元素值
    s->next = pre->next;
    pre->next = s; //插入新结点
}

void ListDel(linkList L, int i)
{ //删除单链表L上的第i个结点
    LNode *pre, *p;
    if (i < 1)
    {
        printf(“参数错误”);
        return;
    }
    if (i == 1)
    {
        p = L->next;
        L->next = p->next;
        free(p);
        return;
    }
    pre = L->next;
    j = 1;
    while (pre != NULL && j < i - 1)
    {
        pre = pre->next;
        j++;
    }
    if (pre == NULL)
    {
        printf(“删除位置不正确”);
        return;
    }
    p = pre->next;
    pre->next = p->next; //从链表中删除
    delete p;            //释放被删除结点
}

linkList Union(linkList la, linkList lb)
{
    //将非递减有序的单链表la和lb合并成新的非递减有序单链表lc，并要求利用原表空间
    linkList pa, pb, lc, pc;
    pa = la->next; //pa是链表la的工作指针
    pb = lb->next;     //pb是链表lb的工作指针
    lc = la;           //利用原a的表头做c的头
    pc = lc;           //pc是链表lc的工作指针
    while (pa && pb)   //la和lb均非空
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    //lb中元素插入lc
    }
    if (pa)
        pc->next = pa; //若pa未到尾，将pc指向pa
    else
        pc->next = pb; //若pb未到尾，将pc指向pb
}

链表尾结点的指针域指向头结点

如果希望查找前驱的时间复杂度达到O(1)，我们可以用空间换时间,每个结点再加一个指向前驱的指针域，使链表可以进行双方向查找。用这种结点结构组成的链表称为双向链表

typedef int ElemType；
typedef struct  DLNode
{ElemType data;           
 struct DLNode *prior,*next;
}DLNode,*DlinkList;