‘壹’ 线性表的链式存储结构和顺序存储结构的区别
顺序存储结构就是用一组地址连续的存储单元依次存储该线性表中的各个元素.由于表中各个元素具有相同的属性,所以占用的存储空间相同.因此,在内存中可以通过地址计算直接存取线性表中的任一元素.这种结构的特点是逻辑上相邻的元素物理上也相邻.用顺序结构存储的线性表称作顺序表.
线性表按链式存储时,每个数据元素
(结点)的存储包括数据区和指针区两个部分.数据区存放结点本身的数据,指针区存放其后继元素的地址
(没有后继元素时设置为空字符(Null)..只要知道该线性表的起始地址
(记录在头指针中),表中的各个元素就可通过其间的链接关系逐步找到
‘贰’ 链接存储的存储结构所占存储空间_______。
写在前面的话：数据结构很多人都是只看不去实战，这样很难取得很好的效果，我会在每个知识点下面配套几道从Leetcode和剑指offer上找到的经典题目（比如本章说完链表以后，会配套LeetCode.206等题目）。
程序这种东西还是多敲键盘比较好，纸上得来终觉浅，绝知此事要躬行。
数据结构中的线性表 是理解图，堆栈，二叉树的基础，他的官方定义为：
线性表 是 零个或多个数据元素的有限序列。
比如：a1, a2, a3 ,a4, ...... , ai-1, ai, ai+1,....., an
ai-1 是ai的前驱元素，而ai+1是ai的后继元素。我们可以得知，当i=2, ...., n-1时，他们只有唯一的一个前驱元素和后继元素。
并且，在线性表中，a1~an所代表的元素必须是相同的数据类型的元素。（比如a1-an代表有n个不同类型的人，但他们都是人，你不能在其中添加一个帽子的存储）。
线性表在物理结构上可以分为：顺序存储结构和链表存储结构。
第一节：首先我们了解下顺序存储结构：
顺序存储结构就是在内存空间中开辟一片连续的空间，然后把数据按照顺序进行存储的一种方式。
他包含三个属性：1、存储空间的起始位置（也就代表我们定义了一个数组）2、最大的存储容量（数组最大长度）3、线性表的当前长度
属性2和3的区别是：数组的长度是基本不变的，这是我们在申请内存空间的时候就已经确定好的，而我们的线性表的长度是代表着元素个数，是不确定的长度。则两者的关系为： 线性表的当前长度<=数组长度；
1 顺序存储结构的插入与删除：
1.1、插入思路：
①、我们首先需要考虑异常（插入位置异常，插入后的长度异常等）
②、从最后一个元素遍历到插入位置，分别将每一个元素向后移动一个位置；
③、插入目标元素，表长加1；
1.2、删除思路：
①、我们仍然需要首先考虑异常（删除位置错误等）
②、查找到需要删除的位置，遍历将其后的每一个元素向前进行移动。
2 总结
我们可以看出，在插入算法中，顺序存储结构中元素在插入位置的过程中，多数元素都需要进行移动，来给插入的元素腾位置。并且，在删除算法中也是类似的道理。我们计算下他们的时间复杂度：顺序存储结构在读取数据的时候，因为可以按照list[index]进行读取，所以时间复杂度为O(1)，但在插入和删除算法的时候，平均的时间复杂度为O(n);
我们可以看出顺序存储结构的优点和缺点：
优点是：不需要为表示元素之间的逻辑关系而增加额外存储空间，可以快速的存取表中的任一位置的元素。
缺点是：插入和删除操作需要移动大量的元素。当线性表变化较大的时候，难以确定存储空间的容量。
‘叁’ 存储结构的概念
存储结构的概念
数据元素之间的关系有两种不同的表示方法:顺序映象和非顺序映象，并由此得到两种不同的存储结构:顺序存储结构和链式存储结构。
数据的存储结构是指数据的逻辑结构在计算机中的表示。
数据储存结构
分类
顺序存储方法它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
链接存储方法它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。
存储和链接存储的基本原理
顺序存储和链接存储是数据的两种最基本的存储结构。
在顺序存储中，每个存储空间含有所存元素本身的信息，元素之间的逻辑关系是通过数组下标位置简单计算出来的线性表的顺序存储，若一个元素存储在对应数组中的下标位置为i，则它的前驱元素在对应数组中的下标位置为i-1，它的后继元素在对应数组中的下标位置为i+1。在链式存储结构中，存储结点不仅含有所存元素本身的信息，而且含有元素之间逻辑关系的信息。
数据的链式存储结构可用链接表来表示
其中data表示值域，用来存储节点的数值部分。Pl，p2，…，Pill(1n≥1)均为指针域，每个指针域为其对应的后继元素或前驱元素所在结点(以后简称为后继结点或前驱结点)的存储位置。通过结点的指针域(又称为链域)可以访问到对应的后继结点或前驱结点，若一个结点中的某个指针域不需要指向其他结点，则令它的值为空(NULL)。
在数据的顺序存储中，由于每个元素的存储位置都可以通过简单计算得到，所以访问元素的时间都相同;而在数据的链接存储中，由于每个元素的存储位置保存在它的前驱或后继结点中，所以只有当访问到其前驱结点或后继结点后才能够按指针访问到，访问任一元素的时间与该元素结点在链式存储结构中的位置有关。
‘肆’ 线性存储与链式存储的区别
定义
顺序存储结构就是用一组地址连续的存储单元依次存储该线性表中的各个元素。由于表中各个元素具有相同的属性，所以占用的存储空间相同。
线性表按链式存储时，每个数据元素
(结点)的存储包括数据区和指针区两个部分。数据区存放结点本身的数据，指针区存放其后继元素的地址只要知道该线性表的起始地址表中的各个元素就可通过其间的链接关系逐步找到
优缺点
顺序存储需要开辟一个定长的空间，读写速度快，缺点不可扩充容量(如果要扩充需要开辟一个新的足够大的空间把原来的数据重写进去)
链式存储无需担心容量问题，读写速度相对慢些，由于要存储下一个数据的地址所以需要的存储空间比顺序存储大。
‘伍’ 线性顺序存储结构和链式存储结构有什么区别
区别：
1、顺序存储需要开辟一个定长的空间，读写速度快，缺点不可扩充容量(如果要扩充需要开辟一个新的足够大的空间把原来的数据重写进去)。
2、链式存储无需担心容量问题，读写速度相对慢些，由于要存储下一个数据的地址所以需要的存储空间比顺序存储大。
‘陆’ 比较顺序存储和链接存储两种存储结构的优缺点。（参考教材4.1）
/*****************************************************
顺序表算法
严格按照《数据结构C语言版》实现
敬请指正
vincent
2006-12-28
******************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int Status;
typedef int ElemType;
/*C中的函数指针类型*/
typedef Status (*cmp)(ElemType x,ElemType i);
typedef void (*vis)();
struct sqlist{
ElemType *elem;
int length;
int listsize;
};
/*创建新的顺序表*/
Status InitList(SqList &L);
/*销毁顺序表*/
Status DestroyList(SqList &L);
/*如果顺序表为空TRUE 否则FALSE*/
Status ListEmpty(SqList &L);
/*返回顺序表长度*/
int ListLength(SqList &L);
/*返回指定位置的元素*/
ElemType GetElem(SqList &L,int i,ElemType *e);
/*定位指定元素，如果有返回第一个匹配的元素的位置*/
int LocateElem(SqList &L,ElemType e,cmp f);
/*int LocateElem_sq(SqList &L,ElemType e);*/
/*返回当前元素的前一个元素*/
ElemType PriorElem(SqList &L,int pos,ElemType *pre_e);
/*返回当前元素的后一个元素*/
ElemType NextElem(SqList &L,int pos,ElemType *next_e);
/*清空表*/
Status ClearList(SqList &L);
/*在指定位置插入元素*/
Status ListInsert(SqList &L,int i,ElemType e);
/*删除指定位置的元素*/
Status ListDelete(SqList &L, int i, ElemType e);
/*遍历顺序表*/
Status ListTraverse(SqList &L, vis v);
/*在顺序表中比较元素e*/
Status compare(ElemType x,ElemType i);
/*visit 函数在遍历表时返回当前元素*/
void visit(SqList &L);
main(){
int i,t ;
ElemType a;
int b;
cmp f;
SqList L;
ElemType *e;
if(!InitList(L)){
printf("E001\n");
exit(ERROR);
}
printf("请输入数字，默认为5个\n");
for(i =1;i <= 5; i++){
int z[5] ;
scanf("%d",&z[i-1]);
if (!ListInsert(L,i,z[i-1])){
printf("E002\n");
exit(ERROR);
}
}
printf("结果是:\n");
for(i = 1 ; i <= L.length;i++){
printf("%d\n",GetElem(L,i,e));
}
/*返回表长*/
printf("%d\n",ListLength(L));
a=3;
printf("%d\n",LocateElem(L,a, f));
DestroyList(L);
}
/*构造一个空表*/
Status InitList(SqList &L) {
L.elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType));
if(!L.elem)exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
/*销毁一个表*/
Status DestroyList(SqList &L) {
if(!L.elem)exit(ERROR);
free(L.elem);
L.elem = NULL;
//L = NULL;
return OK;
}
/*如果顺序表为空TRUE 否则FALSE*/
Status ListEmpty(SqList &L){
if(L.elem == NULL){
return TRUE;
}
else {
return FALSE;
}
}
/*返回顺序表长度*/
int ListLength(SqList &L){
if(!L.elem)exit(ERROR);
return L.length;
}
/*返回指定位置的元素*/
ElemType GetElem(SqList &L,int i,ElemType *e){
if(!L.elem || i > L.length || i < 1 )exit(ERROR);
/*e = L.elem + sizeof(ElemType)*(i-1);*/
e = L.elem + i - 1;
return *e;
}
/*定位指定元素，如果有返回第一个匹配的元素的位置*/
int LocateElem(SqList &L,ElemType e,cmp f){
//f = compare(ElemType x,int i);
int z,s;
ElemType *y;
if(!L.elem) exit(ERROR);
for(z=0;z<= L.length;z++){
/*y = L.elem + sizeof(ElemType)*z;*/
y = L.elem + z;
s = f(*y,e);
if (s == TRUE) return z;
}
return 0;
}
/*在顺序表中比较元素e*/
Status compare(ElemType x,ElemType i){
if (x == i) return TRUE;
return FALSE;
}
/*返回当前元素的前一个元素*/
ElemType PriorElem(SqList &L,int pos,ElemType *pre_e){
if(pos > L.length || pos < 2) exit(ERROR);
pre_e = L.elem + pos -1;
return *pre_e;
}
/*返回当前元素的后一个元素*/
ElemType NextElem(SqList &L,int pos,ElemType *next_e){
if(pos > L.length -1 || pos < 1)exit(ERROR);
next_e = L.elem + pos +1;
return *next_e;
}
/*清空表将表中元素去掉，设置长度为0*/
Status ClearList(SqList &L){
int i;
if(!L.elem)exit(ERROR);
free(L.elem);
L.length = 0;
return OK;
}
/*在指定位置插入元素*/
Status ListInsert(SqList &L,int i,ElemType e){
ElemType *p,*q,*newbase;
if(i <1 || i > L.length +1){
printf("E004\n");
return(ERROR);
}
if(L.length >= L.listsize){
newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase)exit(OVERFLOW);
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
q = &(L.elem[i -1]);
for(p = &(L.elem[L.length -1]);p >= q; --p) *(p+1) = *p;
*q = e ;
++L.length;
return OK;
}
/*删除指定位置的元素*/
Status ListDelete(SqList &L, int i, ElemType e){
ElemType *p,*q;
if(i <1 || i > L.length +1)return(ERROR);
p = &(L.elem[i - 1]);
e = *p;
q = L.elem + L.length -1;
for(++p;p <= q;++p) *(p-1) = *p;
--L.length;
return OK;
}
‘柒’ C语言编程 帮帮忙哦~~比较顺序存储和链接存储两种存储结构的优缺点
(1) 分别用顺序存储和链接存储实现线性表的基本操作
顺序存储:
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
#define List_Init_Size 10
#define ListIncrement 2
typedef char ET;
typedef ET * Ep;
typedef int Status;
typedef struct {
ET *elem;
int Length;
int ListSize;
} SqList;
SqList La,Lb,Lc;
/*This program provide some functions for linear table.
Header file writen user are sqlist.h */
#include"stdio.h"
#include"alloc.h"
#include"sqlist.h"
SqList La,Lb,Lc;
/*Output the linear table emements. */
void printsq(SqList *L) {
int i;
printf("Size=%d Length=%d ",L->ListSize,L->Length);
for (i=0;i<L->Length;i++)
printf("%3c",L->elem[i]);
printf("\n");
}
Status InitList( SqList *L){
L->elem=(Ep)malloc(List_Init_Size*sizeof(ET));
if(L->elem==NULL)
exit(OVERFLOW);
L->Length=0;
L->ListSize=List_Init_Size;
return OK;
}
Status Init(SqList *L) {
int done=TRUE;
ET e;
InitList(L);
while (done) {
scanf("%c",&e);
if (e != '\n')
ListInsert(L,L->Length+1,e);
else done = FALSE;
}
}
/*Insert the ith data into a linear table */
Status ListInsert(SqList *L,int i,ET e){
ET *p,*q;
if (i<1 || i>L->Length+1) return ERROR;
if(L->Length >= L->ListSize){
p=(ET*)realloc(L->elem,(L->ListSize+ListIncrement)*sizeof(ET));
if (p==NULL)exit(OVERFLOW);
L->elem=p;L->ListSize+=ListIncrement;
}
q=L->elem+i-1;
for(p=L->elem+L->Length-1;p>=q;--p)
*(p+1)=*p;
*q=e;
++L->Length;
return OK;
}
Status Insert(SqList *L) {
int i,flag;
ET data;
printf("Please input the position and data: ");
scanf("%d",&i);
printf("Please input the data : ");
data = getche();
flag = ListInsert(L,i,data);
return flag;
}
/*Delete the ith data from a linear table*/
Status ListDelete(SqList *L,int i,ET *e) {
ET *p,*q;
}
Status Delete(SqList *L) {
int i,flag;
ET e;
}
/* Get element from a linear table. */
Status GetElem(SqList *L , int i , ET *e){
}
int LocateElem(SqList *L,ET e) {
int i,flag=FALSE;
}
/*Merge two linear table into one. If they have the same elements,
keep one of them and delete another. */
void Union( SqList *La ,SqList *Lb){
int i;
ET e;
}
}
/*Merge two sequence into one,don't change any elements in
these two linear tables. Join two sequence to one. */
void MergeList(SqList *L1,SqList *L2,SqList *L3) {
int i=0,k=0,j=0;
ET ai,bj;
while((i<L1->Length)&&(j<L2->Length)) {
ai=*(La.elem+i);
bj=*(Lb.elem+j);
if(ai<=bj) {
ListInsert(L3,++k,ai);
++i;
}
else {
ListInsert(L3,++k,bj);
++j;
}
}
while (i<L1->Length){
ai=*(L1->elem+i);
ListInsert(L3,++k,ai);
i++;
}
while(j<L2->Length){
bj=*(L2->elem+j);
ListInsert(L3,++k,bj);
j++;
}
}
/*List the Menu*/
void MenuList() {
printf("\n\n\n**************************\n");
printf(" 1 ------- Insert LA\n");
printf(" 2 ------- Insert LB\n");
printf(" 3 ------- Union LA and LB\n");
printf(" 4 ------- Delete LA\n");
printf(" 5 ------- Delete LB\n");
printf(" 6 ------- Merge LA and LB to LC\n");
printf(" 7 ------- print Linear\n");
printf(" 8 ------- Exit\n");
printf("**************************\n");
}
/*Select the menu */
void MenuSelect( ){
int select,done=1;
while (done) {
MenuList( );
printf("input the operating code : ");
scanf("%d",&select);
switch(select){
case 1: Insert(&La);break;
case 2: Insert(&Lb);break;
case 3: Union(&La,&Lb);break;
case 4: Delete(&La);break;
case 5: Delete(&Lb);break;
case 6: InitList(&Lc);
MergeList(&La,&Lb,&Lc);
printf("LC: ");printsq(&Lc);
break;
case 7: printf("LA: ");printsq(&La);
printf("LB: ");printsq(&Lb);break;
case 8: done=0;break;
default: printf(" ERROR\n");
}
}
}
main( ){
printf("Please input the init LA's element : ");
Init(&La) ;
printf("Please input the init LB's element : ");
Init(&Lb) ;
MenuSelect();
}
链接存储:
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
#define List_Init_Size 10
#define ListIncrement 2
typedef char ET;
typedef ET * Ep;
typedef int Status;
typedef struct LNode{
ET data;
struct LNode *next;
}LNode, *LinkList;
/*LinkList La,Lb,Lc;*/
#include "stdio.h"
#include "alloc.h"
#include "llist.h"
/*Display the linklist's elements. */
void printlk(LinkList L) {
}
/*Creat linklist from head node. */
void CreatList( LinkList *L,int n){
int i;
LinkList p,q;
ET str[20],c;
p=(LinkList)malloc(sizeof(LNode));
p->next=NULL;
*L = q = p;
printf("Please input the data : ");
for (i=n;i>0;i--) {
p=(LinkList)malloc(sizeof(LNode));
c = getche(); /*scanf("%c",&c);*/
printf("\n\n");
p->data = c;
p->next = q->next;
q->next = p;
}
}
/*Init the linklist. */
void Init(LinkList *L) {
int n;
printf("Please input the number of the node : ");
scanf("%d",&n);
CreatList(L,n);
}
/* Get the value of element I; */
int GetElem(LinkList L,int i,ET *e) {
/* Add your own codes. */
}
/*Insert a element after I */
int ListInsert(LinkList *L,int i,ET e) {
/* Add your own codes. */
}
/*Delete the element I */
int ListDelete(LinkList *L,int i,ET *e)
{
/* Add your own codes. */
}
int Insert(LinkList *L) {
int i,flag;
ET data;
printf("Please input the position : ");
scanf("%d",&i);
printf("Please input the data : ");
data = getche(); /*scanf("%c",&data);*/
flag = ListInsert(L,i,data);
return flag;
}
Status Delete(LinkList *L) {
int i,flag;
ET e;
printf("Please input the number : ");
scanf("%d",&i);
flag = ListDelete(L,i,&e);
printf("Deleted element is %c\n",e);
return flag;
}
/*Find the element's position. */
int LocateElem(LinkList L,ET e) {
int i=0;
LinkList p;
p = L->next;
while (p) {
i++;
if (p->data == e) return i;
}
return 0;
}
/*Add the Lb after the La. */
void Union( LinkList *La ,LinkList *Lb){
LinkList pa,pb;
/* Add your own codes. */
}
/*Merge two sequence into one,don't change any elements in
these two link lists. Join two sequence to one. */
void MergeList(LinkList *L1,LinkList *L2,LinkList *L3) {
LinkList pa,pb,pc;
/* Add your own codes. */
}
/*List the Menu*/
void MenuList() {
printf("\n\n\n==========================\n");
printf(" 1 ******* Insert LA\n");
printf(" 2 ******* Insert LB\n");
printf(" 3 ******* Delete LA\n");
printf(" 4 ******* Delete LB\n");
printf(" 5 ******* Union LA and LB\n");
printf(" 6 ******* Merge LA and LB to LC\n");
printf(" 7 ******* print LinkList\n");
printf(" 8 ******* Exit\n");
printf("==========================\n");
}
/*Select the menu */
void MenuSelect(LinkList *La,LinkList *Lb){
int select,done=1;
LinkList Lc;
while (done) {
MenuList( );
printf("input the operating code : ");
scanf("%d",&select);
switch(select){
case 1: Insert(La);break;
case 2: Insert(Lb);break;
case 3: Delete(La);break;
case 4: Delete(Lb);break;
case 5: Union(La,Lb);break;
case 6: MergeList(La,Lb,&Lc);
printf("LC: ");printlk(Lc);
break;
case 7: printf("LA: ");printlk(*La);
printf("LB: ");printlk(*Lb);
break;
case 8: done=0;break;
default: printf(" ERROR\n");
}
}
}
main( ){
LinkList La,Lb;
printf("LA ");
Init(&La) ;
printlk(La);
printf("LB ");
Init(&Lb) ;
printlk(Lb);
MenuSelect(&La,&Lb);
}
(2) 比较两者的优缺点，并说明两者的适用场合
顺序存储:
要求存储的空间物理上连续，但是可以直接完成查找。
链接存储：
不用物理相邻，逻辑上采用指针连续，储存要求不高，但是查找要花更多的时间，修改很方便。
所以，在建立的线性表不需要进行大量的修改，需要查找的时候，就用顺序存储；不经常查找，但是经常进行修改的时候，就用链式存储。
自己的理解，应该正确～
‘捌’ 单链表是一种链接存储结构,但它属于顺序存储结构,为什么
你把他理解成很多人在排队买票，并且每个人都是被一根绳子连在一起的。
‘玖’ 栈的顺序存储和链表存储的差异
顺序存储： 线性表的顺序表：指的是用一组地址连续的存储单元，依次存储线性表的数据元素。
线性表的顺序存储结构具备如下两个基本特征： 1、线性表中的所有元素所占的存储空间是连续的（即要求内存中可用存储单元的地址必须是连续的）。 2、线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 即：线性表逻辑上相邻、物理也相邻（逻辑与物理统一：相邻数据元素的存放地址也相邻），则已知第一个元素首地址和每个元素所占字节数，则可求出任一个元素首地址。 优点： 1、
无须为表示结点间的逻辑关系而增加额外的存储空间。
2、
可以方便的随机存取表中的任一结点。
3、
存储密度大（＝1），存储空间利用率高。 缺点： 1、
插入和删除运算不方便，需移动大量元素。 2、
由于要求占用连续的存储空间，存储分配只能按最大存储空间预先进行，致使存储空间不能得到充分利用。
3、
表的容量难以扩充。 链表存储： 线性表的链式存储：指用一组任意的存储单元存储线性表中的数据元素。
线性表的链式存储结构具备的基本特征： 链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。 优点： 1、
插入、删除操作很方便，可通过修改结点的指针实现，无须移动元素。
2、
方便扩充存储空间。
缺点： 1、
不能随机存取元素。
2、
存储密度小（<1），存储空间利用率低。 总结： 1、
顺序表适宜于做查找这样的静态操作；
链表宜于做插入、删除这样的动态操作。 2、若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
‘拾’ 文件顺序存取与随机存取的主要区别是什么它们对有结
文件的存取方法分为顺序存取和直接存取。一般来说，对顺序存取的文件，文件系统可把它组织成顺序文件和链接文件；对于随机存取的文件，文件系统可把它组织成索引文件。但索引文件也可以进行顺序存取。
1、随机存取（有时亦称直接访问）代表同一时间访问一组序列中的一个随意组件。反之则称循序访问，即是需要更多时间去访问一个远程组件。随机存取存储器的基本结构可分为三个部分：存储矩阵，地址译码器，读写电路。
2、直接存取，访问时读写不见先直接指向一个小区域，再在该区域内
顺序查找，访问时间与数据位置有关（
磁盘）