线性表的顺序存储和链式存储c语言实现

一.线性表的顺序存储

typedef int ElemType;
typedef struct List

{

    ElemType *data;//动态分配 ,需要申请空间

    int length;

}List;

0.完整代码

#include <stdio.h>

#include <stdlib.h>

#define MaxSize 50

#define TRUE 1

#define FALSE 0

typedef int ElemType ;

struct List

{

    ElemType *data;//动态分配 ,需要申请空间

    int length;

};

void InitList(List *p);//初始化表

int ListInsert(List *p,int i,ElemType e);//插入操作 (前插),在第i个位置插入数据e

int ListDelete(List *p,int i);//删除操作，删除第i个位置数据

int ListFindValue(List L,ElemType e);//按值查找元素e ,返回e在顺序表表的位置

int ListFindLocate(List L,int i);//按位查找第i位的值

int Empty(List L); //判空，如果表为空返回TRUE

void PrintList(List L);//输出操作 

int main()

{

    List L;

    InitList(&L);

    ListInsert(&L,,);

    ListInsert(&L,,);

    ListInsert(&L,,);

    ListInsert(&L,,);

    ListInsert(&L,,);

    PrintList(L);

    return ;

 } 

 void InitList(List *p)

 {

     p->data=(ElemType*)malloc(sizeof(ElemType)*MaxSize);

     p->length=;

 }

 int ListInsert(List *p,int i,ElemType e)

 {

     if(i< || i>p->length+)

     {

         return FALSE;//插入位置不合法

     }

     if(p->length>=MaxSize)

     {

         return FALSE;//顺序表已满

     }

     for(int j=p->length;j>=i;j--)

     {

         p->data[j]=p->data[j-];

     }

     p->data[i-]=e;

     p->length++;

     return TRUE;

 }

 int ListDelete(List *p,int i)

 {

     if(i< || i>p->length)

     {

         return FALSE;

     }

     for(int j=i;j<p->length;j++)

     {

         p->data[j-]=p->data[j];

     }

     p->length--;

     return TRUE;

  } 

  int ListFindValue(List L,ElemType e)

  {

      for(int i=;i<L.length;i++)

      {

          if(L.data[i]==e)

          {

              return i+;

        }

    }

    return FALSE;

  }

  int ListFindLocate(List L,int i)

  {

      return L.data[i-];

  }

 void PrintList(List L)

 {

     for(int i=;i<L.length;i++)

     {

         printf("%d ",L.data[i]);

     }

     printf("\n");

 }

 int Empty(List L)

 {

     if(L.length==)

     {

         return TRUE;

     }

     else

     {

         return FALSE;

     }

 }

1.初始化顺序表

void InitList(List *p)

 {

     p->data=(ElemType*)malloc(sizeof(ElemType)*MaxSize);

     p->length=;

 }

2.插入操作 ,在第i个位置插入数据e

int ListInsert(List *p,int i,ElemType e)

 {

     if(i< || i>p->length+)

     {

         return FALSE;//插入位置不合法

     }

     if(p->length>=MaxSize)

     {

         return FALSE;//顺序表已满

     }

     for(int j=p->length;j>=i;j--)

     {

         p->data[j]=p->data[j-];

     }

     p->data[i-]=e;

     p->length++;

     return TRUE;

 }

3.删除操作，删除第i个位置数据

int ListDelete(List *p,int i)

 {

     if(i< || i>p->length)

     {

         return FALSE;

     }

     for(int j=i;j<p->length;j++)

     {

         p->data[j-]=p->data[j];

     }

     p->length--;

     return TRUE;

  }

4.按值查找元素 ,返回元素在顺序表的位置

int ListFindValue(List L,ElemType e)

  {

      for(int i=;i<L.length;i++)

      {

          if(L.data[i]==e)

          {

              return i+;

        }

    }

    return FALSE;

  }

5.按位置查找元素

int ListFindLocate(List L,int i)

  {

      return L.data[i-];

  }

6.判断顺序表是否为空，为空返回TRUE

int Empty(List L)

 {

     if(L.length==)

     {

         return TRUE;

     }

     else

     {

         return FALSE;

     }

 }

7.显示顺序表

void PrintList(List L)

 {

     for(int i=;i<L.length;i++)

     {

         printf("%d ",L.data[i]);

     }

     printf("\n");

 }

二.线性表的链式存储

typedef int ElemType;

typedef struct Node{

    ElemType data;

    struct Node *next;

}Node;

0.完整代码

 #include <stdio.h>

 #include <stdlib.h>

 #define TRUE 1

 #define FALSE 0

 typedef int ElemType;

 typedef struct Node{

     ElemType data;

     struct Node *next;

 }Node;

 Node* InitNode();//初始化创建头结点

 Node* Node_HeadInsert(Node *L);//头插法建立链表

 Node* Node_TailInsert(Node *L);//尾插法建立链表

 Node* NodeInsert(Node *L,int i);//在第i个位置插入结点

 Node* NodeDelete(Node *L,int i);//删除第i个结点

 Node* NodeSearchNum(Node *L,int i);//按序号查找

 Node* NodeSearchValue(Node *L,ElemType x);//按值查找

 void PrintNode(Node *L);//显示单链表

 Node* NodeMerge(Node *p,Node *q);//合并两个递增链表 

 int main()

 {

     Node *L;

     L=InitNode();

     L=Node_TailInsert(L);

     L=NodeInsert(L,);

     PrintNode(L);

     L=NodeDelete(L,);

     PrintNode(L);

     return ;

  }

 Node* InitNode()

 {

     Node *L;

     L=(Node*)malloc(sizeof(Node));

     L->next=NULL;

     return L;

 }

 Node* Node_HeadInsert(Node *L)

  {

      Node *s;

      ElemType x;

      scanf("%d",&x);//插入结点的值

      while(x!=)

      {

          s=(Node*)malloc(sizeof(Node));

          s->data=x;

          s->next=L->next;

          L->next=s;

          scanf("%d",&x);

       }

       return L;

  }

  Node* Node_TailInsert(Node *L)

  {

      ElemType x;

      Node *s,*r=L;

      scanf("%d",&x);

      while(x!=)

      {

          s=(Node*)malloc(sizeof(Node));

          s->data=x;

          r->next=s;

          r=s;

          scanf("%d",&x);

      }

      r->next=NULL;

      return L;

 }

 Node* NodeInsert(Node *L,int i)

 {

     ElemType x;

     Node *s,*p=NodeSearchNum(L,i-);

     printf("输入插入节点的值:") ;

     scanf("%d",&x);

     s=(Node*)malloc(sizeof(Node));

     s->data=x;

     s->next=p->next;

     p->next=s;

     printf("插入完成!\n");

     return L;

 }

 Node* NodeDelete(Node *L,int i)

 {

     Node *p,*q;

     p=NodeSearchNum(L,i-);

     q=p->next;

     p->next=q->next;

     free(q);

     printf("删除完成!\n");

     return L;

 }

  Node *NodeSearchNum(Node *L,int i)

  {

      int count=;//计数

      Node *p=L->next;

      if(i==)

          return L;

     if(i<)

         return NULL;

     while(p&&count<i)

     {

         p=p->next;

         count++;

      }

      return p;

  }

  Node *NodeSearchValue(Node *L,ElemType x)

  {

      Node *p=L->next;

      while(p&&p->data!=x)

      {

          p=p->next;

      }

      return p;

  }

  void PrintNode(Node *L)

  {

      Node *p=L->next;

      printf("单链表:");

      while(p)

      {

          printf("%d ",p->data);

          p=p->next;

      }

      printf("\n");

  }

  Node* NodeMerge(Node *p,Node *q)

  {

      Node *r,*t;

      r=InitNode();

      t=r;

      while(p->next&&q->next)

      {

          if(p->next->data<q->next->data)

          {

              t->next=p->next;

              p->next=p->next->next;

              t=t->next;

          }

          else

          {

              t->next=q->next;

              q->next=q->next->next;

              t=t->next;

          }

      }

      while(p->next)

      {

          t->next=p->next;

          p->next=p->next->next;

          t=t->next;

      }

      while(q->next)

      {

          t->next=q->next;

          q->next=q->next->next;

          t=t->next;

      }

      free(p);

      free(q);

      return r;

  }

1.初始化创建头结点

Node* InitNode()

{

    Node *L;

    L=(Node*)malloc(sizeof(Node));

    L->next=NULL;

    return L;

}

2.头插法建立链表

Node* Node_HeadInsert(Node *L)

 {

     Node *s;

     ElemType x;

     scanf("%d",&x);//插入结点的值

     while(x!=)

     {

         s=(Node*)malloc(sizeof(Node));

         s->data=x;

         s->next=L->next;

         L->next=s;

         scanf("%d",&x);

      }

      return L;

 }

3.尾插法建立链表

 Node* Node_TailInsert(Node *L)

 {

     ElemType x;

     Node *s,*r=L;

     scanf("%d",&x);

     while(x!=)

     {

         s=(Node*)malloc(sizeof(Node));

         s->data=x;

         r->next=s;

         r=s;

         scanf("%d",&x);

     }

     r->next=NULL;

     return L;

}

4.在第i个位置插入结点

Node* NodeInsert(Node *L,int i)

{

    ElemType x;

    Node *s,*p=NodeSearchNum(L,i-);

    printf("输入插入节点的值:") ;

    scanf("%d",&x);

    s=(Node*)malloc(sizeof(Node));

    s->data=x;

    s->next=p->next;

    p->next=s;

    printf("插入完成!\n");

    return L;

}

5.删除第i个结点

Node* NodeDelete(Node *L,int i)

{

    Node *p,*q;

    p=NodeSearchNum(L,i-);

    q=p->next;

    p->next=q->next;

    free(q);

    printf("删除完成!\n");

    return L;

}

6.按序号查找

 Node *NodeSearchNum(Node *L,int i)

 {

     int count=;//计数

     Node *p=L->next;

     if(i==)

         return L;

    if(i<)

        return NULL;

    while(p&&count<i)

    {

        p=p->next;

        count++;

     }

     return p;

 }

7.按值查找

 Node *NodeSearchValue(Node *L,ElemType x)

 {

     Node *p=L->next;

     while(p&&p->data!=x)

     {

         p=p->next;

     }

     return p;

 }

8.显示单链表

void PrintNode(Node *L)

 {

     Node *p=L->next;

     printf("单链表:");

     while(p)

     {

         printf("%d ",p->data);

         p=p->next;

     }

     printf("\n");

 }

9.合并两个递增链表

Node* NodeMerge(Node *p,Node *q)

 {

     Node *r,*t;

     r=InitNode();

     t=r;

     while(p->next&&q->next)

     {

         if(p->next->data<q->next->data)

         {

             t->next=p->next;

             p->next=p->next->next;

             t=t->next;

         }

         else

         {

             t->next=q->next;

             q->next=q->next->next;

             t=t->next;

         }

     }

     while(p->next)

     {

         t->next=p->next;

         p->next=p->next->next;

         t=t->next;

     }

     while(q->next)

     {

         t->next=q->next;

         q->next=q->next->next;

         t=t->next;

     }

     free(p);

     free(q);

     return r;

 }

输出示例：

2020-06-27

巴特西

线性表的顺序存储和链式存储c语言实现

最新文章

热门文章