[数据结构与算法]单链表实现笔记LinkList

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#include <stdio.h>
#include <time.h>

//clock_t start, finish;
//#define duration ((double)(finish - start) / CLK_TCK)
typedef int ElemType;
typedef struct{
    ElemType data;
    struct Node *next;
}Node;
typedef Node *LinkList;
typedef int Status;

Status initList(LinkList *L)
{
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    return OK;
}
Status emptyList(LinkList L)
{
    if(!L->next) return OK;
    return ERROR;
}
Status clearList(LinkList *L)
{
    LinkList p,q;
    p = (*L)->next;
    while(p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    return OK;
}
int listLength(LinkList L)
{
    int j = 0;
    LinkList p = L->next;
    while (p)
    {
        p = p->next;
        ++j;
    }
    return j;
}
Status getElem(LinkList L, int i, ElemType *e)
{
    LinkList p = L->next;
    int j = 1;
    for (; p && j<i; ++j)/*第10个节点为例，j运行到第10个节点就不再进入循环，指针指向第9个节点的next即第10个节点*/
    {
        p = p->next;
    }
    if(!p || j>i) return ERROR;
    *e = p->data;
    return OK;
}
int locElem(LinkList L, ElemType e)
{
    LinkList p = L->next;
    int i;
    for(i=1; p; ++i)
    {
        if(p->data == e) return i;
        p = p->next;        
    }
    return ERROR;
}
Status insertElem(LinkList *L, int i, ElemType e)
{
    LinkList p = *L,s;
    int j = 1;
    for (; p && j<i; ++j)/*第10个节点为例，j运行到第10个节点指针指向第8个节点的next即第9个节点*/
    {
        p = p->next;
    }
    if (!p || j > i) 
		return ERROR;   /* 第i个元素不存在 */
    s = (LinkList)malloc(sizeof(Node));
    s->next = p->next;
    p->next = s;
    s->data = e;
    return OK;
}
Status delElem(LinkList *L, int i, ElemType *e)
{
    LinkList p = *L,q;
    int j = 1;
    for (; p->next && j<i; ++j)
    {
        p = p->next;
    }
    if(!(p->next) || j>i)
        return ERROR;
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return OK;
}


Status visit(ElemType c)/*提出来的好处是易于维护*/
{
    printf("%d ",c);
    return OK;
}
Status listTraverse(LinkList L)
{
    LinkList p = L->next;
    
    for (; p; )
    {
        visit(p->data);
        p = p->next;
    }
    return OK;
}
// void createListHead2(LinkList *L, int i)/*自己写的实现*/
// {
//     initList(L);
//     int j;
//     for (j=0; j<i; ++j)
//     {
//         insertElem(L, 1, rand()%100+1);
//     }
//     listTraverse(*L);
// }

void createListHead(LinkList *L, int n) 
{
	LinkList p;
	int i;
	srand(time(0));                         /* 初始化随机数种子 */
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;                      /*  先建立一个带头结点的单链表 */
	for (i=0; i<n; i++) 
	{
		p = (LinkList)malloc(sizeof(Node)); /*  生成新结点 */
		p->data = rand()%100+1;             /*  随机生成100以内的数字 */
		p->next = (*L)->next;    
		(*L)->next = p;						/*  插入到表头 */
	}
}
// void createListTail2(LinkList *L,int n)/*自己写的实现*/
// {
//     LinkList last,p;
//     *L = (LinkList)malloc(sizeof(Node));
//     (*L)->next = NULL;
//     
//     int i;
//     p = *L;
//     for (i=1; p->next; ++i)
//     {
//         p = p->next;
//     }
//     for (i=0; i<n; ++i)
//     {
//         last = (LinkList)malloc(sizeof(Node));
//         last->data = rand()%100+1;
//         last->next = p->next;
//         p->next = last;
//     }    
// }
void createListTail(LinkList *L,int n)/*换一种实现*/
{
    LinkList p,r;
    int i;
    *L = (LinkList)malloc(sizeof(Node));
    r = *L;
    for(i=0; i<n; ++i)
    {
        p = (LinkList)malloc(sizeof(Node));
        p->data = rand()%100+1;
        r->next = p;/*把桥*next搭在p上，顺着桥爬上去*/
        r = p;/*到达p上了，把p占了，等着下一个节点的到来*/
    }
    r->next = NULL;/*没有节点要来了*/
}
int main()
{
    LinkList L;
    ElemType e;
    Status i;
    int j,k;
    i=initList(&L);
    printf("初始化L后：listLength(L)=%d\n",listLength(L));
    for(j=1;j<=5;j++)
            i=insertElem(&L,1,j);
    printf("在L的表头依次插入1～5后：L.data=");
    listTraverse(L); 

    printf("listLength(L)=%d \n",listLength(L));
    i=emptyList(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);

    i=clearList(&L);
    printf("清空L后：listLength(L)=%d\n",listLength(L));
    i=emptyList(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);

    for(j=1;j<=10;j++)
            insertElem(&L,j,j);
    printf("在L的表尾依次插入1～10后：L.data=");
    listTraverse(L); 

    printf("listLength(L)=%d \n",listLength(L));

    insertElem(&L,1,0);
    printf("在L的表头插入0后：L.data=");
    listTraverse(L); 
    printf("listLength(L)=%d \n",listLength(L));

    getElem(L,5,&e);
    printf("第5个元素的值为：%d\n",e);
    for(j=3;j<=4;j++)
    {
        k=locElem(L,j);
        if(k)
            printf("第%d个元素的值为%d\n",k,j);
        else
            printf("没有值为%d的元素\n",j);
    }
    

    k=listLength(L); /* k为表长 */
    for(j=k+1;j>=k;j--)
    {
        i=delElem(&L,j,&e); /* 删除第j个数据 */
        if(i==ERROR)
            printf("删除第%d个数据失败\n",j);
        else
            printf("删除第%d个的元素值为：%d\n",j,e);
    }
    printf("依次输出L的元素：");
    listTraverse(L); 

    j=5;
    delElem(&L,j,&e); /* 删除第5个数据 */
    printf("删除第%d个的元素值为：%d\n",j,e);

    printf("依次输出L的元素：");
    listTraverse(L); 

    i=clearList(&L);
    printf("\n清空L后：listLength(L)=%d\n",listLength(L));
    createListHead(&L,20);
    printf("整体创建L的元素(头插法)：");
    listTraverse(L); 
    
    i=clearList(&L);
    printf("\n删除L后：listLength(L)=%d\n",listLength(L));
    createListTail(&L,20);
    printf("整体创建L的元素(尾插法)：");
    listTraverse(L); 


    return 0;
}

打印结果：?

?初始化L后：listLength(L)=0
在L的表头依次插入1～5后：L.data=5 4 3 2 1 listLength(L)=5
L是否空：i=0(1:是 0:否)
清空L后：listLength(L)=0
L是否空：i=1(1:是 0:否)
在L的表尾依次插入1～10后：L.data=1 2 3 4 5 6 7 8 9 10 listLength(L)=10
在L的表头插入0后：L.data=0 1 2 3 4 5 6 7 8 9 10 listLength(L)=11?
第5个元素的值为：4
第4个元素的值为3
第5个元素的值为4
删除第12个数据失败
删除第11个的元素值为：10
依次输出L的元素：0 1 2 3 4 5 6 7 8 9 删除第5个的元素值为：4
依次输出L的元素：0 1 2 3 5 6 7 8 9
清空L后：listLength(L)=0
整体创建L的元素(头插法)：17 28 17 4 31 66 13 6 40 26 39 8 55 68 3 70 8 19 14 19
删除L后：listLength(L)=0
整体创建L的元素(尾插法)：59 11 18 42 15 77 86 78 15 92 97 56 90 67 5 3 72 52 29 19