数据结构(四)——单链表的整表创建与删除

    xiaoxiao2021-12-12  6

    单链表整表的创建思路: 1.说明一结点p和计数器变量i; 2.初始化一空链表L; 3.让L的头结点的指针指向NULL,即建立一个带头结点的单链表 4.循环 生成一新结点赋值给p; 赋值;

    将p插入到头结点与千亿新结点之间;

    代码:(这里的赋值采用随机数赋值)

    [cpp]  view plain  copy   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() 0 +1;  //随机生成100以内的数字       p->next = (*L)->next;       (*L)->next = p;       }   }   上述代码采用的是头插法。我们也可以采用尾插法:

    代码如下:

    [cpp]  view plain  copy   void CreateListTail(LinkList *L,int n)   {       LinkList p,r;       int i;       srand(time(0));      //初始化随机数       *L = (LinkList)malloc(sizeof(Node));       r = *L;       for(i = 0; i < n; i++)       {       p = (LinkList)malloc(sizeof(Node));       p->data = rand() 0 +1;  //随机生成100以内的数字       r->next = p;       r = p;       }       r->next = NULL;   }  

    下面介绍单链表的整表删除:

    思路如下:

    1.声明结点p和q; 2.第一个结点赋值给p 3.循环 下一结点赋值给q; 释放p; q赋值给p;

    代码举例:

    [cpp]  view plain  copy   int ClearList(LinkList *L)   {       LinkList q,p;       p = (*L)->next;       while(p)     //没到链表尾       {       q = p->next;       free(p);       p = q;       }       (*L)->next = NULL;       return success;   }  

    单链表结构与顺序存储结构的优缺点: 在存储分配方式上:顺序存储结构用一段连续的存储单元依次存储数据元素;而单链表用一组任意的存储单元存放元素 在时间性能上: 查找:      1.顺序存储结构为O(1);单链表为O(n); 2.插入和删除 顺序存储结构时间为O(n);单链表的时间仅为O(1) 在空间性能上: 顺序存储结构需要预分配存储空间,分配的空间过大造成浪费,过小又不够 单链表不需要分配,只要有就可以分配,元素个数也没有限制
    转载请注明原文地址: https://ju.6miu.com/read-899995.html

    最新回复(0)