单链表操作

1. Status 是函数的类型，其值是函数结果状态代码

   typedef int Status

2. //函数结果状态代码

   #define True 1

   #define False 0

   #define OK 1;

   #define ERROR 0

   #define INFEASIBLE -1

   #define OVERFLOW -2

   ---

    

1.单链表的定义和表示

typedef struct {
    char name[10];
    char num[20];
    double score;
}Stu;

typedef struct LNode {
    Stu data;
    struct LNode *next;
}LNode,*LinkList;

2.初始化链表（带头结点的单链表）

思路：

1. 生成新结点作头结点，用头指针L指向头结点
2. 头结点的指针域置空

Status InitList_L(LinkList L)
{
    L = (LinkList)mallloc(sizeof(LNode));
    L->next = NULL;
    return OK;
}

3.判断链表是否为空

1. 空表：链表中无元素（头指针和头结点仍然存在）

   思路：判断头结点指针域是否为空

   Status ListEmpty(LinkList L)
   {
      if(L->netx)
          return 0;
       else
           return 1;
   }
   

4.销毁单链表

思路：从头指针开始，依次释放所有结点

Status DestroyList_L(LinkList L)
{
    LNode *p; //或者 LinkList p;
    while(L)
    {
        p=L;
        L=L->next;
        free p;
    }
}

5.清空单链表

思路：依次释放所有结点，并为头结点指针域设置为空

Status ClearList(LinkList L)
{
    LNode *p,*q;
    p=L->next;
    while(p)
    {
        q = p->next;
        free p;
        p = q;
    }
    L->next = NULL; //头结点指针域为空
    return OK;
}

6.求单链表长度

思路：从首元结点开始，依次计数所有结点

Status ListLength_L(LinkList L)
{
    LNode *p;
    p = L->next; //p指向第一个结点
    int i = 0;
    while(p)  //遍历单链表，统计结点数
    {
        i++;
        p = p->next;
    }
    return i;
}

7.取值

Status GetElem_L(LinkList L, int i, ElemType e)
{
    LinkList p = L->next; 
    int j = 1;  //p指向第一个结点,j做计数器，累计当前扫描过的结点数
    while(p && j<i)  //向后扫描，p指向第i个元素或者p为空
    {
        p = p->next;
        j++;
    }
    if (!p || j>i)   //第i个元素不存在
        return ERROR;
    e = p->data;    //取第i个元素
    return Ok;
}

8.按值查找

Status LocatElem_L(LinkList L,Elemtype e)
{
    LinkList p = L->next;
    int j = 1;
    while(p && p->data != e)
    {
        p = p->next;  //遍历
        j++;          //位置序号
    }
    if(p)
        return i;
    else 
        return 0;
}

9.插入值

思路：

1. 想要在链表第 i 个元素前面插入新结点，则需要将指针指向第 i-1 个元素，从而将其 next 域中保存的第 i 个元素地址赋值给新结点，实现链接

LinkList p = L;
int j = 0;
while(p && j<i-1)

2. 代码中创建了指向头结点的指针变量，初始化起点并非首元结点，所以要想在第 i 个位置插入，while 循环次数需为 i-1

   若初始化为首元结点，即

   LinkList p = L->next;
   

   则 while 循环次数为 i-2，从而根据循环次数要求去初始化 j 或改变循环结束的条件

    

Status ListInsert_L(LinkList L, int i, Elemtype e)
{
    LinkList p = L;
    int j = 0;
    while(p && j<i-1)
    {
        p = p->next;
        ++j;
    }
    if(!p || j>i-1)
        return ERROR;
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return Ok;
}

10. 删除第 i 个结点

Status ListDelete_L(LinkList_L, int i, Elemtype e)
{
    LinkList p = L;
    LinkList q;
    int j = 0;
    while(p->next && j<i-1)   //寻找第i个结点，并令p指向其前驱
    {
        p = p->next;
        ++j;
    }
    if(!(p->next) || j>i-1) //删除位置不合理
        return ERROR;
    q = p->next;        //临时保存被删除结点的地址以备释放
    p->next = q->next;  //改变删除结点的前驱结点的指针域
    e = q->data;        //保存删除结点的数据域
    free q;             //释放删除结点的空间
    return OK;
}

单链表的创建

1. 头插法(前插法）

思路：

1. 从一个空表L开始，重复读入数据；
2. 生成新结点，将读入数据存放到新结点的数据域中
3. 从最后一个结点开始，依次将各结点插入到链表的前端

void CreatList_H(LinkList L, int n)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;  //建立一个带头结点的单链表
    for(i=n; i>0; --i)
    {
       p = (LinkList)malloc(sizeof(LNode));  //生成新结点p
        scanf(&p->data);                    //获取输入值
        p->next = L->next;                //插入到表头
        L->next = p;
    }
}

2. 尾插法(后插法)

思路：

1. 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针 r 指向链表的尾结点
2. 初始时，r 同 L 均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r 指向新结点

void CreatList(LinkList L, int n)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *r;
    r = L;   //尾指针 r 指向头结点
    for(i=0; i<n; i++)
    {
        p = (LinkList)malloc(sizeof(LNode));   //生成新结点，输入元素值
        scanf(&p->data);
        p->next = NULL;
        r->next = p;    //插入到表尾
        r = p;          //r 指向新的尾结点
    }
}

循环链表

1.创建

//先创建初始化结点函数
LinkList initlist()
{
    LNode *head = (LinkList)malloc(sizeof(LNode));
    if(head == NULL)
    {
        printf("创建失败，退出程序");
    }
    else
    {
        head->next = NULL;
        return head;
    }
}

//创建循环链表
Status Insert_List(LNode *head)
{
    int data;
    printf("输入插入的元素：");
    scanf("%d",&data);
    
    LinkList node = initlist();
    node->data = data;   //初始化新结点
    
    if(head != NULL)
    {
        LNode *p = head;
        while(p->next != head)  //找到最后一个元素
        {
            p = p->next;
        }
        p->next = node;
        node->next = head;
        return 1;
    }
    else
    {
        printf("头结点已无元素\n");
        return 0;
    }
}

2. 带尾指针循环链表合并

LinkList Connect(LinkList Ta, LinkList Tb)
{  //假设Ta，Tb都是非空的单循环链表 
    p = Ta->netx;       //p 存表头结点
    Ta->next = Tb->next->next;  //Tb 表头连接 Ta 表尾
    free Tb->next;         //释放 Tb 表头结点
    Tb->next = p;          //修改指针
    return Yb;
}//时间复杂度O(1)

双向链表

1. 创建

//结点创建
typedef struct DuLNode
{
    Elemtype data;           //data
    struct DuLNode *pre;   //前驱 node
    struct DuLNode *next;  //后继 node
}DuLNode,*DuLinkList;

//插入数据
Status ListInsert_DuL(DuLinkList L, int i, ElemType e)
{
    //在带头结点的双链循环线性表L中第i个位置之前插入元素e
    //i的合法值为 1<=i<=表长+1
    if(!(p = GetElemP_DuL(L,i)))  //在L中确定插入的位置
        return ERROR;         //p=NULL,即插入位置不合法
    if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))
        return ERROR;
    s->data = e;
    s->prior = p->prior;    p->prior->next = s;
    s->next = p;            p->prior = s;
    return OK;
}//LinkInsert_DuL

2.删除

Status ListDelete_DuL(DuLinkList L, int i, ElemType e)
{
    //删除带头结点的双链循环线性表L的第i个元素，i的合法值为1<=i<=表长
    if(!(p = GetElemP_DuL(L,i)))   //在L中确定第i个元素的位置指针p
        return ERROR;
    e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return OK;
}ListDelete_DuL