C语言编程 帮帮忙哦~~比较顺序存储和链接存储两种存储结构的优缺点

Question

C语言编程 比较顺序存储和链接存储两种存储结构的优缺点。
(1) 分别用顺序存储和链接存储实现线性表的基本操作；
(2) 比较两者的优缺点，并说明两者的适用场合。
谢谢了~~

Answer 1

(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) 比较两者的优缺点，并说明两者的适用场合
顺序存储:
要求存储的空间物理上连续，但是可以直接完成查找。
链接存储：
不用物理相邻，逻辑上采用指针连续，储存要求不高，但是查找要花更多的时间，修改很方便。

所以，在建立的线性表不需要进行大量的修改，需要查找的时候，就用顺序存储；不经常查找，但是经常进行修改的时候，就用链式存储。

自己的理解，应该正确～