实验三线性表的链式存储结构
㈠ 线性表的两种存储结构分别为
线性表的两种存储结构分别如下：顺序存储结构和链式存储结构。
这两部分信息组成数据元素的存储映像，称为结点（node）。它包括两个域；存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。
时间有序表、排序表、和频率有序表都可以看做是线性表的推广。如果按照结点到达结构的时间先后，作为确定结点之间关系的，这样一种线性结构称之为时间有序表。
例如，在红灯前停下的一长串汽车，最先到达的为首结点，最后到达的为尾结点；在离开时最先到达的汽车将最先离开，最后到达的将最后离开。这些汽车构成了一个队列，实际上就是一个时间有序表。
㈡ 线性表的顺序结构和链表结构各有什么优缺点
顺序表特点是利用物理上的相邻关系表达出逻辑上的前驱和后继关系，要求用连续的存储单元顺序存储线性表中各元素，对顺序表进行插入和删除时需要通过移动数据元素来实现线性表的逻辑上的相邻关系，从而影响其运行效率。
㈢ 用C语言编写链式存储结构下实现线性表的创建,插入,删除,按值查找
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
int data; //链表数据
struct LNode* next; //链表指针
}LNode,*LinkList;
/*头插法-建立单链表*/
LinkList HeadCreate(LinkList la)
{
int num;
la=(LinkList)malloc(sizeof(LNode)); //建立头结点
la->next=NULL;
scanf("%d",&num);
while(num!=10)
{
LNode *p=(LinkList)malloc(sizeof(LNode));
p->data=num;
p->next=la->next;
la->next=p;
scanf("%d",&num);
}
return la;
}
/*尾插法-建立单链表*/
LinkList TailCreate(LinkList la)
{
int num;
la=(LinkList)malloc(sizeof(LNode));
la->next=NULL;
LinkList s,r=la;
scanf("%d",&num);
while(num!=10)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=num;
r->next=s;
r=s;
scanf("%d",num);
}
r->next=NULL;
return la;
}
/*单链表遍历*/
void TravelList(LinkList la)
{
LinkList p=la->next;
while(p!=NULL)
{
printf("%d->",p->data);
p=p->next;
}
printf("\n");
}
/*单链表的按位查找*/
LinkList GetElem(LinkList la,int i)
{
int j=1;
LNode* p=la->next;
if(i<1)
return NULL;
while(p && j<i)
{
p=p->next;
j++;
}
return p;
}
/*单链表的按值查找*/
LinkList LocalElem(LinkList la,int e)
{
LNode* p=la->next;
while(p!=NULL && p->data!=e)
p=p->next;
return p;
}
/*单链表插入操作*/
bool InsertList(LinkList la,int i,int e)
{
//在la链表中的i位置插入数值e
int j=1;
LinkList p=la,s;
while(p && j<i)
{
p=p->next;
j++;
}
if(p==NULL)
return false;
if((s=(LinkList)malloc(sizeof(LNode)))==NULL)
return false;
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
/*单链表删除操作*/
bool DeleteList(LinkList la,int i)
{
int j=1;
LinkList p=la,q;
while(p && j<i) //p指向第i-1个元素
{
p=p->next;
j++;
}
if(p==NULL || p->next==NULL) //表示不存在第i-1个和第i的元素
return false;
q=p->next;
p->next=q->next;
free(q);
return true;
}
/*单链表的表长*/
int LengthList(LinkList la)
{
int nLen=0;
LinkList p=la->next;
while(p)
{
p=p->next;
nLen++;
}
return nLen;
}
/*单链表逆置*/
LinkList Reserve(LinkList la)
{
if(la==NULL || la->next==NULL)
return la;
LinkList p=la->next,q=p->next,r=q->next;
la->next=NULL;
p->next=NULL;
while(r!=NULL)
{
q->next=p;
p=q;
q=r;
r=r->next;
}
q->next=p;
la->next=q;
return la;
}
int main()
{
LNode la;
LinkList p;
p=HeadCreate(&la); //头插法创建单链表
TravelList(p);
printf("%p\n",GetElem(p,1)); //获得第1个结点地址
InsertList(p,2,10); //在链表的第2个位置插入元素10
TravelList(p);
DeleteList(p,3); //删除链表的第3个元素
TravelList(p);
printf("%d\n",LengthList(p)); //获得链表长度
p=Reserve(p);
TravelList(p);
return 0;
}
//运行结果
//5 6 12 7 8 14 9 3 2 5 14 10 头插法创建链表
//14->5->2->3->9->14->8->7->12->6->5-> 显示链表
//00382490 第一个结点的地址
//14->10->5->2->3->9->14->8->7->12->6->5-> 插入元素值为10的结点
//14->10->2->3->9->14->8->7->12->6->5-> 删除第三个结点
//11 获得链表长度
//5->6->12->7->8->14->9->3->2->10->14-> 链表逆置
//Press any key to continue
这是我写的一个线性表链式存储的综合程序，包含了你所要的创建、删除、插入、按值查找的功能，还有一些额外的功能。下面加注释的是程序运行结果，你可以参考试着改改程序，让程序更加完美。希望对你有帮助，呵呵！
㈣ 线性表顺序存储结构和链式存储结构的定义，以及各自的有缺点，分别适合于哪些应用
定义
顺序存储结构就是用一组地址连续的存储单元依次存储该线性表中的各个元素。由于表中各个元素具有相同的属性，所以占用的存储空间相同。
线性表按链式存储时，每个数据元素 (结点)的存储包括数据区和指针区两个部分。数据区存放结点本身的数据，指针区存放其后继元素的地址只要知道该线性表的起始地址表中的各个元素就可通过其间的链接关系逐步找到
优缺点
顺序存储需要开辟一个定长的空间，读写速度快，缺点不可扩充容量(如果要扩充需要开辟一个新的足够大的空间把原来的数据重写进去)
链式存储无需担心容量问题，读写速度相对慢些，由于要存储下一个数据的地址所以需要的存储空间比顺序存储大。
㈤ 线性表的链式存储结构优于顺序存储结构
线性表的链式存储结构优于顺序存储结构，这句话是错误的。
线性表的存储结构：
线性表主要由顺序表示或链式表示。在实际应用中，常以栈、队列、字符串等特殊形式使用。顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。
链式表示指的是用一组任意的存储单元存储线性表中的数据元素，明纯称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点（node）。
它包括两个域：存储数据元素信息的域称为数激卜咐据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。