c语言实现--带头结点单链表操作

可能是顺序表研究的细致了一点，单链表操作一下子就实现了。这里先实现带头结点的单链表操作。

大概有以下知识点.

1;结点：结点就是单链表中研究的数据元素，结点中存储数据的部分称为数据域，存储直接后继地址的部分称为指针域。

2;结点示意图：

3;头指针：头指针始终指向链表第一个元素，当有头结点时头结点就是链表第一个元素。头指针具有标识左右，故头指针命名为链表的名字，这里为linklist。头指针是一定存在的。

4;头结点：引入头结点的目的是，将链表首元结点的插入和删除操作与其他结点的插入和删除操作统一起来。（即头指针地址不在发生变化）

5;单链表结点结构体表示：

struct LNode
{
     int data;     //姑且认为其数据为整型
    struct LNode * next;
};

typedef struct LNode * linklist

6;单链表的操作集合，头文件 defs.h

#ifndef _DEFS_H_
#define _DEFS_H_

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

struct LNode                         //单链表结点的定义
{
    int data;
    struct LNode * next;
}
typedef struct LNode * linklist

                //操作集合
void InitList(linklist *L);  //申请头结点，头指针地址改变
void DestroyList(linklist *L);  //须释放头结点，头指针地址改变
void ClearList(linklist L);  //保留头结点，头指针地址不变
void ListEmpty(linklist L);
int ListLength(linklist L);
int GetElem(linklist L, int i, int *e);
int LocateElem(linklist L, int e);
int PriorElem(linklist L, int cur_e, int *pri_e);
int NextElem(linklist L, int cur_e, int *nex_e);
int ListInsert(linklist L, int i, int e);  //插入不改变头指针的值
int ListDelete(linklist L, int i, int *e); //删除操作也不改变头指针的值
void TravelList(linklist L);
#endif

7;InitList操作实现

#include"defs.h"

void InitList(linklist *L)   //接受头指针的地址值
{
    *L = (linklist)malloc(sizeof(struct LNode));  //*L表示头指针
    
    if (*L == NULL)
     {
         printf("分配结点失败。\n");
         exit(-1);
     }
     (*L)->next = NULL;   //置头结点的next域为空
}

8;DestroyList操作的实现

#include"defs.h"

void DestroyList(linklist *L) //接受的参数为头指针的地址值
{
    linklist p ;
    while (*L)    
    {
        p = (*L)->next;  //释放结点之前先保存结点的下一个地址，防止线索被断
        free(*L);
        *L = p;  //将下一个结点，作为释放结点
    }
}

9;ClearList操作的实现

#include"defs.h"

void ClearList(linklist L) //保留头结点
{
    linklist p = L->next;  //p将头指针的next值保存起来，p指向首元结点
   L->next = NULL;     
    
    DestroyList(&p);  //调用撤销函数，释放后面的结点
    
}

10;ListEmpty操作的实现

#include"defs.h"

void ListEmpty(linklist L)
{
    if (L->next == NULL)     //判断头结点指针域是否为空
        printf("链表为空.\n");
    else
        printf("链表不为空.\n");
}

11;ListLength操作实现

#include"defs.h"

int ListLength(linklist L)
{
    int j=0;     //作为计数器
   linklist p = L->next; //p指向首元结点，作为移动指针

   while (p)   //从首元结点开始
    {
        ++j;
        p = p->next;
    }
    return j;
}

12;GetElem操作实现

#include"defs.h"

int GetElem(linklist L, int i, int *e) // 1<= i <=ListLength(L)
{
    int j = 0; //j作为计数器
   linklist p = L;  

    while (p && j<i)        //找到第i个结点
    {
        ++j;
        p = p->next;
    }
    if (!p || i<1)   //取值位置不合理
       exit(0);

     *e = p->data; 
      return 0;
}

13;LocateElem操作实现

#include"defs.h"

int LocateElem(linklist L, int e)
{
    linklist p = L->next;  //p作为移动指针，p指向第一个元素
   int j = 0;   //j作为计数器

   while (p)
    {
        ++j;
        if (p->data == e)
            return j;
        p = p->next;
    }
    return 0;
}

14;PriorElem操作实现

#include"defs.h"

int PriorElem(linklist L, int cur_e, int *pri_e) //第一个元素无前驱
{
    linklist p = L->next;   //p指向首元结点
   linklist q;

    while (p)
    {
        q = p->next;  //q为p的后继
      
      if (q && q->data == cur_e)  //则p就是q的前驱
            *pri_e = p->data;  
        p = q;     //循环
    }
    return 0;
}

15;NextElem操作的实现

#include"defs.h"

int NextElem(linklist L, int cur_e, int *nex_e) //最后一个元素无后继
{
    linklist p = L->next;  //p指向首元结点
   linklist q;

   while (p)
   {
       q = p->next;  //q为p的后继
      
     if (q && p->data == cur_e) //p有后继，且p的数据域与当前值相等
         *nex_e = q->data;
       p = q;  //更新p
   }
   return 0;
}

16;ListInsert操作的实现

#include"defs.h"

int ListInsert(linklist L, int i, int e) //1<= i <= ListLength(L)
{
    int j=0;  //j为基数器
   linklist p = L;    //p为移动指针，p指向头结点
   linklist q, s;

   while (p && j<i-1)  //找到第i-1个结点
    {
        ++j;
        p = p->next;
    }
    
    if (!p || i<1)  //插入位置不合理
       return 0;

    q = p->next;  //q指向第i个结点
   
    s = (linklist)malloc(sizeof(struct LNode));
    if (!s)  //分配失败
        exit(-1);

    s->data = e;     //置s的数据域为e
    s->next = q;     //插入操作,是指针连起来
    p->next = s;
    return 0;
}

17;ListDelete操作的实现

#include"defs.h"

int ListDelete(linklist L, int i, int *e) // 1<= i <=ListLength(L)
{
    int j = 0; //j为计数器
   linklist p = L;
    linklist q;

    while (p && j<i-1)       //找到第i-1个结点
     {
        ++j;
        p = p->next;
    }
    
    if (!p || i<1) //删除位置不合理
       exit(0);
    q = p->next;  //q指向第i个结点
 
   *e = q->data;  //先将第i个结点的数据域带出
   p->next = q->next;  //连起指针
    free(q);         //释放第i个结点

    return 0;
}

18;TravelList操作实现

#include"defs.h"

void TravelList(linklist L)
{
    linklist p = L->next;  //p指向首元结点
   int j = 0;   //j为计数器

   while (p)
    {
        ++j;
        printf("第%d个结点的数据域的值为：%d\n", j, p->data);
        p = p->next;  //更新p
    }
}

19;makefile的实现，其代码与顺序表的一样,这里换成另一种写法

object = main.o InitList.o DestroyList.o ClearList.o ListEmpty.o \
ListLength.o GetElem.o LocateElem.o PriorElem.o NextElem.o \
ListInsert.o ListDelete.o TravelList.o

test : $(object)
       gcc -g -Wall -o test $(object)

$(object) : defs.h

.PHONY : clean
clean : 
        rm -f *.o

20;顺序表与单链表的比较

顺序表是用一段地址连续的存储单元来存放数据元素，适合查找，不适合频繁插入和删除（没一次操作都是O(n)）；

单链表是用不连续的存储单元，其数据元素之间是用指针来连接，每一次的查找都必须通过头指针来遍历，因此其不适合频繁的查找。但是对于插入和删除操作，它不需要移动其它元素，算法时间复杂度为O(1)，因此特别适合频繁的插入和删除操作。