数据结构线性表的单链表存储结构

发布网友发布时间：2022-04-24 08:29

共2个回答

懂视网时间：2022-05-06 17:23

链式存储结构.单链表2 顺序存储结构的创建实质是一个数组的初始化，存储空间连续且其大小和类型已经固定；单链表存储空间不连续，是一种动态结构且它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。一.单链表的整

链式存储结构.单链表2
顺序存储结构的创建实质是一个数组的初始化，存储空间连续且其大小和类型已经固定；单链表存储空间不连续，是一种动态结构且它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。一.单链表的整表创建创建单链表的过程就是一个动态生成链表的过程，即从“空表”的初始化起，依次建立各元素结点，并逐个插入链表。 1.算法思路 (1)声明一个结点p和计数器变量i; (2)初始化一空链表L (3)让链表L的头结点的指针指向NULL,即建立一个带头结点的单链表 *L=(LinkList)malloc(sizeof(Node)); (*L)->next=NULL; (4)循环： a.生成一个新结点赋值给p; b.随机生成一个数字赋值给p的数据域p->data; c.将p插入到头结点之前与一新结点之间 2.源码实现 (1)头插法:始终让新结点在第一的位置 /*随机产生n个元素的值，建立带头结点的单链线性表L(头插法)*/ typedef struct Node *LinkList; //定义LinkList void CreateListHead(LinkList *L,int n) { LinkList p; int i; srand(time(0)); //初始化随机数种子 /*1.建立一个带头结点的单链表*/ *L=(LinkList)malloc(sizeof(Node)); //初始化一空链表L (*L)->next=NULL; //让链表L的头结点的指针指向NULL /*2.循环插入新结点到单链表中*/ for(i=0;idata=rand()%100+1; //设置新结点的数据域 p->next=(*L)->next; //设置新结点的指针域：使p结点的后继结点为头指针之前指向的结点 (*L)->next=p; //更改头结点的后继结点为新结点p } } (2)后插法：把每次新结点都插在终端结点的后面 /*随机产生n个元素的值，建立带头结点的单链线性表L(尾插法)*/ typedef struct Node *LinkList; //定义LinkList void CreateListTail(LinkList *L,int n) { LinkList p,r; int i; srand(time(0)); //初始化随机数种子 /*1.建立一个带头结点的单链表并设置尾结点*/ *L=(LinkList)malloc(sizeof(Node)); //初始化一空链表L,L指整个单链表 r=*L; //r为指向尾部的结点 /*2.循环插入新结点到单链表中*/ for(i=0;idata=rand()%100+1; //设置新结点的数据域 r->next=p; //将表尾终端结点的指针指向新结点 r=p; //将当前的新结点定义为表尾终端结点 } r->next=NULL; //此时的尾结点为p，相当于p->next=null,，表示当前链表结束 } 注释：注意L与r的关系，L是指整个单链表，而r是指向尾结点的变量；r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。

升华笔记: 1.如何创建一个带头结点的单链表？ (1)初始化一空链表L (2)让链表L的头结点的指针指向NULL 源码实现： LinkList *L; *L=(LinkList)malloc(sizeof(Node)); (*L)->next=NULL; 2.头插法如何实现插入新结点？ (1)生成一个新结点 (2)设置新结点的数据域 (3)设置新结点的指针域 (4)将新结点作为上一个结点的后继结点源码实现：p=(LinkList)malloc(sizeof(Node)); p->data=e; //e为数据 p->next=(*L)->next; //设置新结点的指针域：使p结点的后继结点为头指针之前指向的结点 (*L)->next=p; //更改头结点的后继结点为新结点p 3.尾差法如何实现插入新结点？ (1)声明一个结点r，并将其设置为链表L的尾部结点 (2)生成一个新结点p (3)设置新结点的数据域 (4)将表尾终端结点的指针指向新结点,并将新结点设置为尾部结点 (5)设置新的表位结点指针指向NULL，表示当前链表结束源码实现：LinkList *L,p; *L=(LinkList)malloc(sizeof(Node)); r=*L; p=(LinkList)malloc(sizeof(N【本文来自鸿网互联 (http://www.68idc.cn)】ode)); p->data=rand()%100+1; r->next=p; r=p;

二.单链表的整表删除
1.算法思路
(1)声明一个结点p和q; (2)将单链表的第一个结点赋值给p (3)循环： a.将下一结点赋值给q b.释放p c.将q赋值给p 2.源码实现： /*初始化条件：单链式线性表L已存在，操作结果：将单链表L重置为空表*/ typedef struct Node *LinkList; //定义LinkList
typedef int Status;
Status ClearList(LinkList *L) { LinkList p,q; p=(*L)->next; //将单链表的第一个结点赋值给结点p while(p) { q=p->next; //将p的下一个结点设置为q free(p); //释放结点p p=q; //p指向下一结点q } (*L)->next=NULL; //最后，单链表头结点指针域为空 returm OK; } 三.单链表结构与顺序存储结构的优缺点 1.存储分配方式 (1)顺序存储结构用一段联系的存储单元依次存储线性表的数据元素 (2)单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素 2.时间性能 (1)查找：顺序存储结构O(1);单链表O(n) (2)删除和插入：顺序存储结构需要平均移动表长一半的元素，时间为O(n);单链表在指出某位置的指针后，插入和删除时间仅为O(1) 3.空间性能 (1)顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生溢出； (2)单链表不需要分配存储空间，只要有就可以分配，元素个数不受限制

热心网友时间：2022-05-06 14:31

线性表是一种数据元素有序的逻辑结构，通常采用顺序存储结构和链式存储结构。线性表采用顺序存储结构时，有利用线性表长度的计算、线性表数据元素的存取和数据元素的遍历，同时也从物理结构上反映了线性表数据元素的逻辑结构，有点类似于c语言中的数组，但是采用顺序存储结构时，插入和删除数据元素时，要移动较多的数据元素；采用链表结构存储的线性表，克服了插入和删除数据元素时要移动较多元素的缺点，其只要寻找到需要插入和删除的数据元素处，处理相应的指针就可以实现数据元素的插入和删除，同时也和顺序存储的线性表一样方便遍历，但是其不利于计算线性表的长度，线性表的链表存储结构有以下几种常见类型：采用带头指针和头结点的单链表、采用仅带头指针的单链表、带头指针和头结点的循环链表、带头指针和尾结点的循环链表、双向链表等形式。在实际应用中，结合顺序表易于计算表长和链表易于插入和删除的特点，实际一般采用两者结合的一种单链表，其链表类型为带有头指针（含头结点）和尾指针，以及含有线性表长度的分量，在一元多项式的运算中采用的就是这种链式存储结构。此外，还有一种一般应用于无指针的高级语言中的静态单链表的存储结构。追问so ？