【数据结构基本代码】-----线性表

一、顺序表

1、顺序表的定义

（1）基于静态数组

#define Maxsize 50
typedef struct{
   Elemtype data[Maxsize];
   int length;
}SeqList 

（2）基于动态数组

#define InitSize 100
typedef struct{
   Elemtype *data;   //data指针指向第一个元素的位置
   int length;       
   int Maxsize;
}SeqList

L.data=(Elemtype *)malloc(sizeof(Elemtype)*InitSize);

2、顺序表的销毁

（1）基于静态数组

L.length = 0;   //由系统自动回收空间

（2）基于动态数组

free(L.data);

3、顺序表的插入

在顺序表L的第i个位置插入元素e，若i的输入不合法，返回false；插入成功，返回true；

顺序表的位序从1开始；在对顺序表操作时，是对数组进行操作，数组下标从1开始。

bool ListInsert(SeqList &L, int i, Elemtype e){
   if(i<1 || i>L.length+1)
      return false;
   if(L.length>=MaxSize)
      return false;
   for(int j=length;j>=i,j--){
      L.data[j]==L.data[j-1];
   }
   L.data[i-1]=e;
   L.length++;
   return true;
}  

最好情况：在表尾插入，不需要移动元素，时间复杂度为O(1)；

最坏情况：在表头插入，需要移动n个元素，时间复杂度为O(n)；

平均时间复杂度为O(n)。

4、顺序表的删除

删除顺序表第i个元素，用引用变量e返回。

bool Listdel(SeqList &L, Elemtype &e, int i){
   if(i<1 || i>length)
      return false;
   e=L.data[i-1];   //先将data[i-1]赋值给e再删除
   for(int j=i;j<=L.length-1,j++)
      L.data[j-1]=L.data[j];
   L.length--;
   return true;
}

最好情况：删除表尾元素，不需要移动元素，时间复杂度为O(1)；

最坏情况：删除表头元素，需要移动n-1个元素，时间复杂度为O(n)；

平均时间复杂度为O(n)。

5、顺序表的查找

（1）按序号查找，由于顺序表随机存取的特性，按序号查找元素的时间复杂度为O(1)。

（2）按值查找

在顺序表L中查找第一个值为e的元素，并返回其位序。

int Locate(SeqList L,Elemtype e){
   for(int i=0;i<length;i++){
      if(L.data[i]==e)
         return i+1;    //查找成功返回位序
      return 0；        //退出循环,查找失败
}

最好情况：查找的元素就在表头，时间复杂度O(1)；

最坏情况：查找的元素在表尾，需要遍历整个顺序表，时间复杂度O(n)；

平均时间复杂度O(n)。

二、单链表

1、单链表的定义

typedef struct{
   Elemtype data;
   struct LNode *next; 
}LNode,*LinlList;

2、单链表的创建

（1）头插法

  元素的插入顺序与在单链表中的顺序相反，因此可以利用头插法实现链表的逆置。

步骤：

a：初始化一个单链表（创建一个头结点，并将该单链表置为空）

b：输入结点的data值，同时也要为每个data值建立一个结点。

LinkList Headinsert(LinkList &L){
   //不用再声明L,L不是变量
   L=(LinkList)malloc(sizeof(LNode));    //头结点为LinkList,用来表示该结点为头结点
   L->next=NULL;
   LNode *q;
   int x;
   scanf("%d",&x);
   whlie(x！=-1){
      q=(LNode*)malloc(sizeof(LNode));   //普通结点用LNode*
      q->data=x;
      q->next=L->next;      //顺序不能颠倒,否则会断链
      L->next=q;
   }
   return L;
}

（2）尾插法

LinkList endInsert(LinkList &L){
   L=(LinkList)malloc(sizeof(LNode));
   LNode *q;
   LNode *r=L;
   int x;
   scanf("%d",&x);
   while(x!=-1){
      q=(LNode*)malloc(sizeof(LNode));
      q->data=x;
      r->next=q;
      r=q;
   }
   r->next=NULL;
   return L;
}

3、查找

（1）按序号查找

LNode *GetElem(LinkList L,int i){
   if(i<0)
      return NULL;
   if(i==0)
      return L;
   LNode *p=L->next;
   while(p&&j<i)            //p！=NULL且j<i
      p=p->next;            //遍历不是由于j++,而是由于p=p->next,随着j++,最后j=i时退出循环
      j++;
   }
   return p;               //返回的不是位序，而是查找到的结点
}

（2）按值查找

LNode *GetElem(LinkList L,int e){
   LNode *p=L->next;
   while(p!=NULL&&p->data!=e)
      p=p->next;   //遍历
   return p;
}

4、插入结点

5、删除结点

最后

以上就是结实小白菜为你收集整理的【数据结构基本代码】-----线性表的全部内容，希望文章能够帮你解决【数据结构基本代码】-----线性表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。