线性表的顺序与链式表示

本文作者：韩申权
作者博客：http://www.cnblogs.com/hsqdboke
转载请注明出处，侵权必究，保留最终解释权！

分别建立包含10个数据元素的顺序线性表和链式线性表；

从键盘输入一个数据元素和插入位置k，将元素插入到线性表中第k（包含0号位置）个位置；

从键盘输入一个数据元素关键字或位置k（包含1号位置），从线性表中删除相应数据元素；

能完成查找功能；

给出程序及插入、删除前和插入、删除后线性表结果。

顺序表示：

//顺序表示
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define TURE 1
#define FAUSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 4
typedef int Status;
typedef int ElemType;
typedef struct
{
    ElemType *elem;
    int length;
    int listsize;
}SqList;

Status InitList_Sq(SqList *L) //初始化线性表
{
    L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L->elem)return OVERFLOW;
    L->length=0;
    L->listsize =LIST_INIT_SIZE;
    return OK;
}

Status ListInsert_Sq(SqList *L,int i,ElemType e)//向表中插入元素
{
    ElemType *q,*p,*newbase;
    if(i<1||i>L->length+1)
        return ERROR;
    if(L->length>=L->listsize)//若当前表长>=计划表长则开辟新空间
    {
        newbase=(ElemType *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));
        if(!newbase)return ERROR;
        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_Sq(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;
 }
int ListFind(SqList L,int k)
 {
     return L.elem[k-1];
 }
int main()
{
    SqList Lst;
    int i,j,n=10,a,k,p=1;
    ElemType e;
    if(InitList_Sq(&Lst)==OK)
    {
        for(i=1;i<=n;i++)
            if(ListInsert_Sq(&Lst,i,i)!=OK)break;
            printf("原来线性表中的元素为:");
            for(i=0;i<Lst.length;i++)
                printf("%d ",Lst.elem[i]);
                printf("\n");
            while(p)
            {
                printf("1)插入元素2)删除元素3)查找元素4)显示操作结果0)退出\n");
                scanf("%d",&j);                
                switch(j)
                {
                    case 1:
                printf("请输入要插入的元素和插入的位置:");
                scanf("%d%d",&a,&k);
                ListInsert_Sq(&Lst,k,a);break;
                    case 2:
                    printf("请输入要删除的元素和删除的位置:");
                scanf("%d",&k);
                ListDelete_Sq(&Lst,k,&e);break;
                    case 3:
                    printf("请输入查找元素的位置:");
                    scanf("%d",&k);                    
                    printf("位置为%d的元素为%d\n",k,ListFind(Lst,k));
                    case 4:
                for(i=0;i<Lst.length;i++)
                    printf("%d ",Lst.elem[i]);
                    printf("\n");break;
                    case 0:p=0;break;
                }
            }
            
    }//if
    return 0;
}//main

链式表示：

#include<stdio.h>//带头结点的链表操作
#include<stdlib.h>
#define ERROR 0
#define OK 1
#define OVERFLOW -1
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
void GetElem(LinkList L,int i,ElemType *e)//查找第i个元素并返回
{    
    LNode *p;
    int j=1;
    p=L->next;
    while(p&&j<i)
    {
        p=p->next;++j;
    }
    if(!p||j>i)printf("不存在,查找错误\n");
    else
    *e=p->data;    
}
void ListInsert_L(LinkList *L,int i,ElemType e)//插入元素
{
    LinkList p=*L,s=NULL;
    int j=0;
    while(p&&j<i-1){p=p->next;++j;}
    if(!p||j>i-1)printf("插入位置错误\n");    
    s=(LinkList)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
}
void ListDelet_L(LinkList *L,int i,ElemType *e)//删除元素
{
    LNode *p=*L,*q=NULL;
    int j=0;
    while(p->next&&j<i-1)
    {
        p=p->next;++j;
    }
    if(!(p->next)||j>i-1)printf("删除位置错误");
    q=p->next;p->next=q->next;
    *e=q->data;
    free(q);    
}
void CreatList(LinkList *L,int n)//建立链表 输入n个ElemType类型的数
{
    LinkList p=NULL,q=NULL;
    int i;
    ElemType m;
    (*L)=(LinkList)malloc(sizeof(LNode));
    (*L)->next=NULL;
    p=(LinkList)malloc(sizeof(LNode));
    p->next=NULL;
    q=p;
    scanf("%d",&m);
    p->data=m;
    (*L)->next=p;
    for(i=1;i<n;i++)
    {
        p=(LinkList)malloc(sizeof(LNode));        
        scanf("%d",&m);
        p->data=m;
        q->next=p;
        p->next=NULL;
        q=p;
    }
}
void DisList(LinkList L)
{
    LinkList p=L->next;    
    while(p)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}
int main()
{
    LinkList L=NULL;
    int i,p=1,m;
    ElemType e;
    printf("请输入10个元素:\n");
    CreatList(&L,10);
    printf("原来的10个元素为:");
    DisList(L);
    while(p)
    {
        printf("1)插入2)删除3)查找4)显示操作结果0)退出\n");
        scanf("%d",&m);
        switch(m)
        {
        case 1:printf("请分别输入要插入元素的位置及与元素值: ");
            scanf("%d%d",&i,&e);ListInsert_L(&L,i,e);break;
        case 2:printf("请分别输入要删除元素的位置: ");
            scanf("%d",&i);ListDelet_L(&L,i,&e);printf("删除的元素值为:%d\n",e);break;
        case 3:printf("请分别输入要查找的元素的位置: ");
            scanf("%d",&i);GetElem(L,i,&e);printf("该位置的元素为:%d\n",e);break;
        case 4:DisList(L);break;
        case 0:p=0;break;
        }
    }

    return 0;
}