C和数据结构——链表实例

#include <stdio.h>
#include <stdlib.h>
//链表的实现和函数实现
/*链表的结构必定包涵一个指针域，所以地址的分配不一定连续
由计算据随机分配，所以单链表只能单向操作，但是也正是因此
可以使得表基本无线扩容。 
结构：
每个数据元素由结点构成
链表的第一个元素节点称为首结点 
最后一个元素称为尾结点，指针域NULL
一般定义head（头节点）指向首结点a1，这样比较好！！！ 
*/
typedef int ElemType;
typedef struct node
{
    ElemType data;     //数据域
    struct node *next; //指针域
} LNode, *LinkList;

//初始化单链表
int InitList_L(LinkList &L)
{
    L = (LinkList)malloc(sizeof(LNode)); //分配空间
    if (!L)
        return 0;   //判断是否成功
    L->next = NULL; //初始结点指针域为空
    return 1;
}

//销毁单链表
int DestroyList(LinkList &L)
{
    LinkList p;
    while (L)
    {
        p = L->next;
        free(L);
    }
}

//求单链表的长度
int ListLength(LinkList L)
{
    int i = 0;
    //不能直接while(L)因为这样会把头节点移动到尾部；
    LinkList p = L->next;
    while (p)
    {
        i++;
        p = p->next;
    }
    return i;
}

//求单链表中值为e的元素
int LocataElem(LinkList L, ElemType e)
{
    int i = 0;
    LinkList p = L->next;
    while (p)
    {
        i++;
        if (p->data == e)
            return i;
        p = p->next;
    }
    return 0; //如果没有找到，返回0；
}

//单链表的插入操作
int ListInsert_L(LinkList &L, int i, ElemType e)
{
    LinkList p, s; //创建两个指向结点的指针，这里的LinkList等价于LNode * ；
    p = L;         //让p指向头节点；
    int j = 0;
    while (p && j < i - 1)
    { //先让p找到目标结点的上一个结点，
        p = p->next;
        ++j;
    }
    if (!p || j > i - 1)
        return 0; //判断i是否合法
    //给s分配空间，来存储数据e，
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;

    /*先让s的指针域指向i,此时i-1对应的结点，此时s和p
	都指向目标结点*/
    s->next = p->next;

    /*再让p指向s，这样就把s插入到目标结点的前面了，也
	就是把e插入进去了，此时链表i位置上就是e了；*/
    p->next = s;
    return 1;
}

//单链表的删除算法,类似于插入操作
int ListDelete_L(LinkList &L, int i, ElemType &e)
{
    LinkList p, q;
    p = L;
    int j = 0;
    //同样，先找到i-1个位置
    while (p->next && j < i - 1)
    {
        p = p->next;
        ++j;
    }
    //判断上一步是否正确进行
    if (!p->next || j > i - 1)
    {
        return 0;
        ;
    }
    /*这里要先让p指向q,再让q指向p->next，
	也就是把链表通过q链接起来，再让p指向
	q的下一个位置，此时p就直接跳过i结点，指向
	i+1结点了，这时候就可以释放i结点了/
	如果直接让q指向i+1的结点，那么i的结点就会被遗忘在
	缓存区，当程序运行足够长时间时，会导致内存不够，
	或者其他的关于内存的问题*/
    q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return 1;
}

//显示链表的元素和物理存储位置
void ShowAddress(LinkList L)
{
    int i;
    LinkList p = L->next;
    //当然，这里如果使用while写起来会更简便一些
    if (p)
    {
        printf("\n头节点的地址为：\t%p\n", L); //前面说过了，头结点一般不存储数据
        for (i = 1; p; i++)
        {
            printf("第%d个结点的值为：\t%d;\t地址为：%p\n", i, p->data, p);
            p = p->next;
        }
    }
}

/*确定一个链表中元素值最大的结点,我这里设定的是返回对应的结点
当然，也可以返回具体的值*/
LNode *MaxNode(LNode *L)
{
    LNode *p = L->next, *maxp = p;
    while (p != NULL)
    {
        if (maxp->data < p->data)
            maxp = p;
        p = p->next;
    }
    return maxp;
}
/*int Search_L(LinkList L)//这是返回具体的值函数
{
    LinkList p;
    ElemType e;
    p = L->next;//第一次写的时候这里出现了问题，原因是L指向头结点，里面没有数据
    //通过不断的调试程序，我发现每次输出的值的地址和都不一样，所以我认为一定是
    //出现了地址和数值比较的情况，回头检查，意识到这里出现了问题。
    e = p->data;
    p = p->next;
    while (p)
    {
        if (p->data > e)
            e = p->data;
        p = p->next;
    }
    return e;
}
*/

//删除元素值最大的结点,这是一个经常用到的，但是比较难的知识点
/*注意：再删除单链表的某一位置的时候，要知道它的前一个位置
1，p遍历，同时pre指向p的前驱
2，用maxp 同步p，使得maxp指向最大值，同样maxpre指向maxp的前驱
3，基于maxpre和maxpre执行删除操作
*/
void DelMaxNode(LNode *&L) //其实这里我觉的参数改成LinkList &L，也行
{
    LNode *p = L->next, *pre = L, *maxp = p, *maxpre = pre;
    while (p)
    {
        if (maxp->data < p->data) //比较大小
        {
            maxp = p;
            maxpre = pre;
        }
        //对pre和maxpre同步后移，保证紧随p，maxp后面
        pre = p;
        p = p->next;
    }
    maxpre->next = maxp->next; //简单的删除操作1
    free(maxp);                //简单的删除操作2
}
/*将表中元素逆置*/
void ListReverse(LNode *&L)
{
    //先将表一分为二，一个是空的表头，一个是无表头的表
    LNode *p = L->next, *q;
    L->next = NULL;
    //尾插法实现
    while (p)
    {
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q; //尾插法这一步特别关键，可以保持p始终在第一个元素的位置（L的后继）
    }
}
//查找带头结点的单链表的倒数k个位置上的地址
/*思路：其实和前面的删除最大值的思路一致，只不过此时
    的同步指针不是立刻同步，而是在p移动了k个单位之后，才
    进行同步*/
int Searchk(LinkList list, int k)
{
    LinkList p, q;
    int count = 0;
    p = q = list->next;
    while (p && count < k) //把p从首结点移动到k结点
    {
        p = p->next;
        count++;
    }
    //判断k的位置是否合法
    if (p == NULL)
        return 0;
    else
    {
        while (p) //此时只要p指向尾节点，那么q就指向了倒数k的结点，输出就行
        {
            q = q->next;
            p = p->next;
        }
        printf("倒数%d个位置的元素是：%d", k, q->data); //打印
        return 1;
    }
}
int main()
{
    int A[8] = {1, 2, 3, 4, 5, 100, 200, 300}; //测试数据
    int i, j, e = 586;                         //e时是测试数据
    LinkList head, p;                          //head是头节点，相当于&L;
    InitList_L(head);

    for (i = 1, j = 0; i <= 8; i++, j++) //注意这里i从1开始，
        ListInsert_L(head, i, A[j]);     //将数据依次放入
    Search_L(head);
    printf("%d", Search_L(head));
}