线性表的链式存储实现

㈠ 1、线性表顺序存储方式操作2、线性表链式存储方法操作：。两个都用c语言

下面是从我的博客里面给你找的，你参考一下。更多的数据结构的内容，也可以去看我的博客。

/************************************************************
说明：
1、主函数内的代码是为了测试方便，可以自行修改。
2、宏定义NEWS是人机交互信息提示，若不需要，可修改为0。
3、若是windows系统，请将258行中的clear修改为cls。
4、在输入数据后，请多按一下回车，实现清屏。
环境：ubuntu12.04LTS、codeblocks10.05、2014-04-02
************************************************************/
#include<iostream>
#include<stdlib.h>
#include<malloc.h>
#include<cstring>
#defineNEWS1
#defineLIST_INIT_SIZE100
#defineLIST_ADD_SIZE10
#defineNEW_SIZE(L->list_size+LIST_ADD_SIZE)
usingnamespacestd;
typedefintElem_Type;
typedefstruct
{
Elem_Type*data;//元素
intlen;//长度
intlist_size;//空间
}Sq_List;
typedefenum
{
OK=0,//正常
ERROR=-1,//逻辑异常
OVER=-2//内存异常
}Status;
/******************************
函数名：Init_List
功能：构造、初始化线性表
******************************/
Sq_List*Init_List(void)
{
Sq_List*L=(Sq_List*)malloc(sizeof(Sq_List));
if(!L)
exit(OVER);
L->data=(Elem_Type*)malloc(LIST_INIT_SIZE*sizeof(Elem_Type));
if(!L->data)
exit(OVER);
L->len=0;
L->list_size=LIST_INIT_SIZE;
#if(NEWS)
cout<<"构造成功，已初始化"<<endl;
#endif
returnL;
}
/******************************
函数名：Destroy_List
功能：销毁线性表
******************************/
StatusDestroy_List(Sq_List*L)
{
free(L);
#if(NEWS)
cout<<"销毁成功，请不要再使用"<<endl;
#endif
returnOK;
}
/******************************
函数名：Clear_List
功能：清空线性表
******************************/
StatusClear_List(Sq_List*L)
{
memset(L->data,-1,sizeof(L->data));
L->len=0;
#if(NEWS)
cout<<"已全部清空"<<endl;
#endif
returnOK;
}
/******************************
函数名：Empty_List
功能：判断线性表是否为空
******************************/
boolEmpty_List(Sq_List*L)
{
returnL->len==0;
}
/******************************
函数名：Length_List
功能：获取线性表长度
******************************/
intLength_List(Sq_List*L)
{
returnL->len;
}
/******************************
函数名：Get_Elem_List
功能：指定位置获取元素
******************************/
StatusGet_Elem_List(Sq_List*L,intindex,Elem_Type*e)
{
if(!(1<=index&&index<=Length_List(L)))
#if(NEWS)
{
cout<<"获取位置不合法"<<endl
<<"下面显示的数据是上次输入的num的值,请注意！！！"<<endl;
returnERROR;
}
#else
returnERROR;
#endif
*e=L->data[index-1];
returnOK;
}
/******************************
函数名：Insert_List
功能：指定位置插入元素
******************************/
StatusInsert_List(Sq_List*L,intindex,Elem_Typee)
{
if(!(1<=index&&index<=Length_List(L)+1))
#if(NEWS)
{
cout<<"插入位置不合法"<<endl;
returnERROR;
}
#else
returnERROR;
#endif
if(Length_List(L)>=L->list_size)
#if(NEWS)
cout<<"刚才增加了存储空间"<<endl;
#endif
L->data=(Elem_Type*)realloc(L->data,NEW_SIZE*sizeof(Elem_Type));
if(!L->data)
exit(OVER);

L->list_size+=LIST_ADD_SIZE;

for(inti=Length_List(L);i>=index-1;i--)
L->data[i+1]=L->data[i];

L->data[index-1]=e;
L->len++;
#if(NEWS)
cout<<"插入成功"<<endl;
#endif
returnOK;
}
/******************************
函数名：Delete_List
功能：指定位置删除元素
******************************/
StatusDelete_List(Sq_List*L,intindex,Elem_Type*e)
{
if(Empty_List(L)||!(1<=index&&index<=Length_List(L)))
#if(NEWS)
{
cout<<"删除位置不合法or目前是空表"<<endl;
returnERROR;
}
#else
returnERROR;
#endif
*e=L->data[index-1];
for(inti=index;i<Length_List(L);i++)
L->data[i-1]=L->data[i];
#if(NEWS)
cout<<"删除成功"<<endl;
#endif
L->len--;
returnOK;
}
/******************************
函数名：Print_List
功能：输出所有元素
******************************/
StatusPrint_List(Sq_List*L)
{
if(Empty_List(L))
returnERROR;
inttemp;
for(inti=1;i<=Length_List(L);i++)
{
Get_Elem_List(L,i,&temp);
cout<<temp<<"";
}
cout<<endl;
returnOK;
}
/******************************
函数名：print_news
功能：方便用户选择
******************************/
voidprint_news(void)
{
cout<<" ********************"
<<"*****************************"<<endl
<<" * 0建立、初始化 *"<<endl
<<" * *"<<endl
<<" * 1插入元素 *"<<endl
<<" * *"<<endl
<<" * 2删除元素 *"<<endl
<<" * *"<<endl
<<" * 3销毁 *"<<endl
<<" * *"<<endl
<<" * 4获取表长 *"<<endl
<<" * *"<<endl
<<" * 5清空 *"<<endl
<<" * *"<<endl
<<" * 6获取元素 *"<<endl
<<" * *"<<endl
<<" * 7打印 *"<<endl
<<" * *"<<endl
<<" * 8退出程序 *"<<endl
<<" ********************"
<<"*****************************"<<endl;
}
intmain(void)
{
Sq_List*test=NULL;
while(true)
{
print_news();
intchoose,index,num;
cout<<"要进行什么操作？"<<endl;
cin>>choose;
switch(choose)
{
case0:
test=Init_List();break;
case1:
cout<<"插入位置"<<endl;
cin>>index;
cout<<"插入数据"<<endl;
cin>>num;
Insert_List(test,index,num);break;
case2:
cout<<"删除的位置"<<endl;
cin>>index;
Delete_List(test,index,&num);
cout<<"被删除的元素是："<<num<<endl;break;
case3:
Destroy_List(test);break;
case4:
cout<<Length_List(test)<<endl;break;
case5:
Clear_List(test);break;
case6:
cout<<"获取哪个位置的元素"<<endl;
cin>>index;
Get_Elem_List(test,index,&num);
cout<<num<<endl;break;
case7:
Print_List(test);break;
case8:
return0;
default:
break;
}
getchar();
getchar();
system("clear");
}
return0;
}

㈡ 线性表两种 存储结构各自的优缺点有哪些

线性表的链式存储结构：

优点：

插入和删除不需要移动插入时只需要对插入位置后的一个元素进行操作，不需要大量的移动元素。空间有效利用高。

缺点：

大量访问操作时不如顺序存储结构，因为每次都需要从头开始遍历整个线性表直到找到相应的元素为止。

线性表的顺序存储结构：

优点：

可随机存取表中任一元素。因为有下标可以操作可以快速的定位到指定位置的元素，但是不知道位置的话也需要顺序遍历。

缺点：

插入或删除操作时，需大量移动元素。合适在很少进行插入和删除运算的情况下。

(2)线性表的链式存储实现扩展阅读：

线性表的特征

集合中必存在唯一的一个“第一元素”。

集合中必存在唯一的一个 “最后元素” 。

除最后一个元素之外，均有唯一的后继(后件)。

除第一个元素之外，均有唯一的前驱(前件)。

线性表的基本操作

MakeEmpty(L) 这是一个将L变为空表的方法。

Length（L） 返回表L的长度，即表中元素个数。

Get（L，i） 这是一个函数，函数值为L中位置i处的元素（1≤i≤n）。

Prior（L，i） 取i的前驱元素。

Next（L，i） 取i的后继元素。

Locate（L，x） 这是一个函数，函数值为元素x在L中的位置。

Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置。

Delete（L，p） 从表L中删除位置p处的元素。

IsEmpty(L) 如果表L为空表(长度为0)则返回true，否则返回false。

Clear（L）清除所有元素。

Init（L）同第一个，初始化线性表为空。

Traverse（L）遍历输出所有元素。

Find（L，x）查找并返回元素。

Update（L，x）修改元素。

Sort（L）对所有元素重新按给定的条件排序。

strstr(string1,string2)用于字符数组的求string1中出现string2的首地址。

参考资料来源：网络-线性表

㈢ 线性表的链式存储结构

结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

n个结点链成一个链表，即为线性表的链式存储结构。

在单链表的第一个结点前附设一个头结点，头结点的数据域可以不存储任何数据，头结点的指针域存储指向第一个结点的指针，链表可以没有头结点。

头指针是链表指向第一个结点的指针，如果链表有头结点，头指针指向头结点。

获得链表第i个数据的方法，定义一个指针，从链表第一个数据开始遍历，不断指向下一个结点，直到第i个。

㈣ 线性表的链式存储结构是一种（）存储结构

线性表的链式存储结构是一种顺序存储的存储结构。

线性表的链式存储结构中的每一个存储结点不仅含有一个数据元素，还包括指针，每一个指针指向一个与本结点有逻辑关系的结点，此类存储方式属于顺序存储；线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

(4)线性表的链式存储实现扩展阅读：

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。

比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

㈤ 线性表链式存储结构的基本操作算法实现

这是我学数据结构时亲手码的，好用的话记得给分。。。。。
#include<iostream>
using namespace std;

//线性表的单链表存储表示
struct LNode
{
int data;
struct LNode *next;
};

//逆序创建链表
void CreateList(LNode *L,int a[],int n)
{
LNode *s;
L->next = NULL;
for(int i=n-1;i>=0;--i)
{
s= new LNode;
s->data=a[i];
s->next=L->next;
L->next=s;
}
}
//显示链表
void display(LNode *L)
{
LNode *p;
p=L->next;
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
}
//插入结点操作
void ListInsert(LNode *L,int d, LNode *s)
{
LNode *p;
int i=1;
p=L->next;
while(i<d-1)
{
p=p->next;
i++;
}
s->next=p->next;
p->next=s;
}
//删除节点操作
void ListDelete(LNode *L,int d,int &e)
{
LNode *p,*q;
int i=0;
p=L->next ;
while(i<d-1)
{
q=p;
p=p->next;
i++;
}
e=p->data;
q->next=p->next;
delete p;
}
//查找元素
LNode* LocalElem(LNode *L,int e)
{
LNode *p;
p=L->next;
while(p&&p->data!=e) p=p->next;
return p;
}
//逆置单链表
void InvertLinkedList(LNode *L)
{
LNode *p,*s;
p=L->next;
L->next=NULL;
while(p)
{
s=p;
p=p->next;
s->next=L->next;
L->next=s;
}
}

int main()
{
LNode *H;
int n;
cout<<"please enter the length of the list: ";
cin>>n;
int *A=new int[n];
int i;
H=new LNode;
H->next=NULL;
cout<<"please enter "<<n<<" number of the list:"<<endl;
for(i=0;i<n;i++)
cin>>A[i];
CreateList(H,A,n);
cout<<"show the members of the list: ";
display(H);
cout<<endl;

int d;
cout<<"please enter the address of the add member: ";
cin>>d;
LNode *s;
s= new LNode;//初始化局部变量s
cout<<"please enter the data of the add member: ";
cin>>s->data;
ListInsert(H,d, s);
display(H);
cout<<endl;

int p;
cout<<"please enter the address of the delete member: ";
cin>>p;
int c=0;
int &e=c;//非常量引用的初始值必须为左值!!!
ListDelete(H,p,e);
display(H);
cout<<endl;

int g;
cout<<"please enter the member that you want to find: ";
cin>>g;
cout<<"the local of the member is: "<<LocalElem(H,g);
cout<<endl;

InvertLinkedList(H);
cout<<"the invertlinklist is: ";
display(H);
cout<<endl;
return 0;
}

花时间好好看看，一定要看懂