Question

如何建立一个顺序存储的线性表，实现线性表的插入、删除操作？

Answer 1

顺序存储结构线性表基本操作 C语言实现

#include <stdio.h>
//以下为函数运行结果状态代码
#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; //假设数据元素为整型
typedef struct
{
     ElemType *elem; //存储空间基址
    int length; //当前长度
    int listsize; //当前分配的存储容量
}SqList;
//实现线性表的顺序存储结构的类型定义
//函数声明开始
Status InitList_Sq(SqList &L);
void DestroyList_Sq(SqList &L);
void ClearList_Sq(SqList &L);
void ListEmpty_Sq(SqList L);
Status GetElem_Sq(SqList L,i,&e);
int LocateElem_Sq(SqList L,e,compare());
Status PriorElem_Sq(SqList L,cur_e,&pre_e);
Status NextElem_Sq(SqList L,cur_e,&next_e);
Status ListInsert_Sq(SqList &L,i,e);
Status ListDelete_Sq(SqList &L,i,&e);
ListTravel_Sq(SqList L,visit());
//函数声明结束
int main(void)
{
    return 0;
}
//函数定义开始
///////////////////////////////////////
//函数名：InitList_Sq()
//参数：SqList *L
//初始条件：无
//功能：构造一个空线性表
//返回值：存储分配失败：OVERFLOW
//         存储分配成功：OK
///////////////////////////////////////
Status InitList_Sq(SqList *L)
{
     L.elem=(ElemType*)malloc((LIST_INIT_SIZE *sizeof(ElemType)); //分配空间
    if(!L.elem)
         exit(OVERFLOW); //若存储分配失败，返回OVERFLOW
     L.length=0; //空表，长度为0
     L.listsize=LIST_INIT_SIZE; //初始存储容量
    return OK;
}
///////////////////////////////////////
//函数名：DestroyList_Sq()
//参数：SqList *L
//初始条件：线性表L已存在
//功能：销毁线性表
//返回值：无
///////////////////////////////////////
void DestroyList_Sq(SqList *L)
{
    if (L->elem)
         free(L->elem); //释放线性表占据的所有存储空间
}
///////////////////////////////////////
//函数名：ClearList_Sq()
//参数：SqList *L
//初始条件：线性表L已存在
//功能：清空线性表
//返回值：无
///////////////////////////////////////
void ClearList_Sq(SqList *L)
{
     L->length=0; //将线性表的长度置为0
}
///////////////////////////////////////
//函数名：ListEmpty_Sq()
//参数：SqList L
//初始条件：线性表L已存在
//功能：判断线性表是否为空
//返回值：空：TRUE
//         非空：FALSE
///////////////////////////////////////
Status ListEmpty_Sq(SqList L)
{
    if (L.length==0)
        return TRUE;
     else
        return FALSE;
}
///////////////////////////////////////
//函数名：ListLength_Sq()
//参数：SqList L
//初始条件：线性表L已存在
//功能：返回线性表长度
//返回值：线性表长度(L.length)
///////////////////////////////////////
Status ListLength_Sq(SqList L)
{
    return (L.length);
}
///////////////////////////////////////
//函数名：GetElem_Sq()
//参数：SqList L,int i,ElemType *e
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：用e返回线性表中第i个元素的值
//返回值：(i<1)||(i>ListLength(L))：ERROR
//         1<=i<=ListLength(L)：OK
///////////////////////////////////////
Status GetElem_Sq(SqList L,int i,ElemType *e)
{
    if (i<1||i>L.length)
        return ERROR; //判断i值是否合理，若不合理，返回ERROR
     *e=L.elem[i-1]; //数组中第i-1的单元存储着线性表中第i个数据元素的内容
    return OK;
}
///////////////////////////////////////
//函数名：LocateElem_Sq()
//参数：L,e,compare(ElemType1,ElemType2)
//初始条件：线性表L已存在，compare()为数据元素判定函数
//功能：返回顺序表L中第1个与e满足关系 compare( ) 的数据元素的位序
//返回值：若在L中存在于e满足关系compare()的元素：其位序
//         若在L中不存在于e满足关系compare()的元素：0
///////////////////////////////////////
int LocateElem_Sq(SqList L,e,compare(ElemType1,ElemType2))
{
　　int i = 1; // i 的初值为第1元素的位序
　　int p = L.elem; // p 的初值为第1元素的存储位置
　　while (i <= L.length && !(*compare)(*p++,e))
　　　++i; // 依次进行判定
　　if (i <= L.length)
      return i; // 找到满足判定条件的数据元素为第 i 个元素
　　else
      return 0; // 该线性表中不存在满足判定的数据元素
}
Status PriorElem_Sq(SqList L,cur_e,&pre_e);
//见Status NextElem_Sq(SqList L,cur_e,&next_e);
Status NextElem_Sq(SqList L,cur_e,&next_e);
//我的思路是先用LocateElem_Sq()搜索cur_e的位序，
//再看是否大于等于length，
//若是，则返回OVERFLOW；否则返回后继
//这样也许有点麻烦？所以希望大家能够补充方案
//by wangweinoo1
///////////////////////////////////////
//函数名：ListInsert_Sq()
//参数：SqList *L,int i,ElemType e
//初始条件：线性表L已存在，1<=i<=ListLength(L)+1
//功能：在线性表中第i个数据元素之前插入数据元素e
//返回值：失败：ERROR
//         成功：OK
///////////////////////////////////////
Status ListInsert_Sq(SqList *L,int i,ElemType e)
{
     ElemType *j;
    if (L->length==LIST_MAX_LENGTH)
        return ERROR; //检查是否有剩余空间
    if (i<1||i>L->length+1)
        return ERROR; //检查i值是否合理
    //将线性表第i个元素之后的所有元素向后移动
    for (j=L->length-1;j>=i-1;i++)
         L->elem[j+1]=L->elem[j];
     L->elem[i-1]=e; //将新元素的内容放入线性表的第i个位置，
     L->length++;
    return OK;
}
///////////////////////////////////////
//函数名：ListDelete_Sq()
//参数：SqList *L,int i,Elemtype *e
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：将线性表L中第i个数据元素删除
//返回值：失败：ERROR
//         成功：OK
///////////////////////////////////////
int ListDelete_Sq(SqList *L,int i,Elemtype *e)
{
    if (IsEmpty(L))
        return ERROR; //检测线性表是否为空
    if (i<1||i>L->length)
        return ERROR; //检查i值是否合理
     *e=L->elem[i-1]; //将欲删除的数据元素内容保留在e所指示的存储单元中
    //将线性表第i+1个元素之后的所有元素向前移动
    for     (j=i;j<=L->length-1;j++) L->elem[j-1]=L->elem[j];
     L->length--;
    return OK;
}
//函数定义结束

Answer 2

链表
1。是由结构体和指针构成的。
2。包括两个部分一个是数据域和指针域。
3。链表中的结点分为两类：头结点和一般结点。头结点是没有数据域的。
4。基本操作有：初始化链表，增加结点和删除结点，求链表的长度等等。
struct Linknode{
int data;
struct Linknode *next;
};
这个地方有个知识点：这个是链表的数据结构是有结构体和指针构成。结构体名为Linknode.但这里面没有定义结构体变量，只有我们定义了结构体变量才能使用结构体。
结构体变量怎么定义呢？
有两种方式：
1。struct Linknode Linklist;
2.typedef struct linknode Linklist.
一般我们都希望采用第2种，这样的好处是: 当我们再定义结构体变量时，可以用：Linklist p;而如果我们采用第一种还必须采用 struct Linknode p;对比一下就可以知道第2种要简单很多。那么下面我们都采用第2种方式来定义结构体变量。
上面我们已经定义了一个链表：
1。初始化链表。
#include
#include
int InitLinkList(Linklist **Lnode)
{
*Lnode=(Linklist)malloc(sizeof(Linklist));//*Lnode等于L，对与*Lnode的分配空间相当与对主函数中的L分配空间。
if(!*Lnode)
return 0;
（*Lnode）->next=NULL;
}
在初始化链表的时候，我们用到了2级指针为什么呢？因为我们希望在InitLinkList函数生成的头结点，主函数中也能指向这个头结点。如果我们用一级指针的话，用malloc分配空间的时候，它将会返回分配空间的首地址给指针变量Lnode，而不能使是的空间被主函数中指针变量L得到这个地址。所以我们要用2级指针。
void main()
{
Linklist *L;
InitLikList(&L);
}
2。增加链表结点
增加链表结点其实很简单，一般用到三个结构体指针变量和一个循环结构。
InsertLinkList(Linklist *Lnode)
{
Linklist *p,*q;
int d;
{
scanf("%d",&d);
if(d==-9999)
break;
p=Lnode->next;//p指向头结点
//通过while循环和指针变量p定位要插入的结点q的位置。
while（p）
p=p->next;
//生成一个要插入的结点
q=(Linklist)malloc(sizeof(Linklist));//申请要插入的结点空间
q->data=d;//填充要插入结点的数据域
q->next=p->next;//首先填充要插入结点q的指针域进行填充。
p->next=q;//然后把定位好的p指针域进行修改指向q.

}while(9);//循环退出的条件是输入的数据-9999

}
void main()
{
Linklist *L;
InitLinkList(&L);//生成一个头结点
InsertLinkList(L);//插入结点
}
3。求链表的长度：
int LengthLinkList(Linklist *Lnode)
{
int i=0;
Linklist *p;
p=Lnode->next;//p指向链表的第一个结点。
while(p)
{
i++;
p=p->next;
}
return i;
}
void main()
{
Linklist *L;
InitLinkList(&L);//生成一个头结点
InsertLinkList(L);//插入一个结点
LengthLinkList(L)//求链表的长度。
}
4.删除结点
删除链表结点其实很简单，一般用到三个结构体指针变量和一个循环结构。
DestroyLinkList(Linklist *Lnode)
{
Linklist *p,*q;
p=Lnode;//p指向链表的头结点
while(p)
{
q=p->next;//q指向当前结点的下一个结点。
free(p);//释放当前结点
p=q;//p指向下一个结点
}
}
void main()
{
Linklist *L;
InitLinkList(&L);//生成一个头结点
InsertLinkList(L);//插入结点
LengthLinkList(L)//求链表的长度。
DestroyLinkList(L);//删除链表结点
}