数据结构基础（一）-创新互联

线性表

线性顺序表

1、线性表的数据操作

创新互联服务项目包括西岗网站建设、西岗网站制作、西岗网页制作以及西岗网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，西岗网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到西岗省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

数据结构基础（一）

2、使用定义的函数实现两个集合LA和LB的合并：

void unionList(List LA,List LB,List &LC)
{
    int lena,i;
    ElemType e;
    InitList(LC);
    //将LA的所有元素插入到LC中
    for (i=1;i<=ListLength(LA);i++)
    {
        GetElem(LA,i,e);
        ListInsert(LC,i,e);
     } 
     lena=ListLength(LA);

     //将LB的所有元素插入到LC
     for(i=1;i

3、顺序表存储类型的定义

# define MaxSize 50
typedef struct
{

    ElemType date[MaxSize];
        int length;
}SqList;

4、创建线性表

void CreateList(Sqlist *&L,ElemType a[],int n)
{
    int i;
    L=(SqList *)malloc(sizeof(SqList)); 
    // malloc 相当于new,分配SqList大小的内存空间，指向SqLost的指针，并将地址赋值给L 

    for (i=0;idata[i]=a[i];
    L->length=n;    
}

5、初始化线性表

void InitList(SqList *&L) // 应用指针
{
    L=(SqList *)malloc(sizeof(SqList));
    L->length=0;   // 初始化线性表的长度 
}

6、销毁线性表

void DestroyList(SqlList *&L)
{

 free(L); 
}

7、判断线性表是否为空

bool ListEmpty(SqList *L)
{
    return(L->length==0);
}

8、求线性表的长度

int ListLength(SqList *L)
{
    return(L->length);  
}

9、输出线性表

void DispList(SqList *L)
{
    int i;
    if (ListEmpty(L))
        return;
    for (i=0;ilength;i++)
        printf("%d ",L->data[i]);
    printf("\n");
}

10、求某个数据元素的值，返回L中的第i个元素的值，并存入e中，1<=i<=ListLength(L)

bool GetElem(SqList *L,int i,ElemType &e)
{
    if (i<1||i>L->length)
        return false;
    e=L->data[i-1];
    return true;
}

11、按元素值查找

int LocateElem(L,e)
{
    int i = 0;
   while (ilength && L->data[i]!=e)
        i++;
    if (i>=L->length)
        return 0;
    else
        return i+1;

}

12、插入元素

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

13、删除元素

bool ListDelete(SqList *&L,int i,ElemType &e)
{
    int j;
    if (i<1||i>L->length)
        return false;
    i--;
    e=L->data[i];
    for(j=i;jlength-1;j++)
        L->data[j]=L->data[j+1];
    L->length--;
    return true; 

}


线性链表
1、单链表的存储结构的定义
typedef struct LNode // 定义单链表节点类型
{
    ElemType data; //数据域
    struct LNode *next; //指针域，指向后继节点  递归结构 
}LinkList;
2、单链表的头插法：
void CreateListF(LinkList *&L,ElemType a[],int n)
{
    LinkList *S;
    int i;
    L=(LinkList *)malloc(sizeof(LinkList));
    L->next=NULL;
    for(i=0;idata=a[i];
        S->next=L->next;
        L->next=S;
    }   
 }
3、单链表尾插法
void CreateListR(LinkList *&L,ElemType a[],int n)
{
    LinkList *s,*r;
    int i;
    L=(LinkList *)malloc(sizeof(LinkList));
    r=L;
    for(i=0;idata=a[i];
        r->next=s;
        r=s;
    }
    r->next=NULL;
}
4、单链表的基本操作
5、初始化线性表
void InitList(LinkList *&L)
{
    L=(LinkList *)malloc(sizeof(LinkList));
    L->next=NULL;
}
6、销毁线性表
void DestroyList(LinkList *&L)
{
    LinkList *pre=L,*p=L->next;
   while (p=NULL)
    {
        free(pre);
        pre=p;
        p=pre->next;
    }
    free(pre);
 }
7、判断表为空
bool ListEmpty(LinkList *L)
{
    return(L->next==NULL);
}
8、求线性表的ListLength(L)
 int ListLength(LinkList *L)
 {
    int n=0;
    LinkList *p=L;
   while (p->next!=NULL)
    {
        n++;
        p=p->next;
    }
    return(n);
 }
9、输出线性表：
void DisList(LinkList *L)
{
    LinkList *p=L->next;
   while(p!=NULL)
    {
        printf("%d",p->data);
        p=p->next;
    }
    printf("\n")
 }
10、查找某个元素
bool GetElem(LinkList *L,int i,ElemType &e)
 {
    int j=0;
    LinkList *p=L;
   while (jnext;
            }   
    if (p==NULL)
        return false;
    else
    {
        e=p->data;
        return true;
    }
 }
11、 按元素查找，返回元素的位置
 int LocateElem(LinkList *L,ElemType e)
 {
    int i=1;
    LinkList *p=L->next;
   while (p!=NULL&& p->data!=e)
    {
        p=p->next;
        i++;
     } 
     if (p==NULL)
         return 0;
     else
         return i;
  }
12、插入数据元素：
 bool ListInsert(LinkList *&L,int i,ElemType e){
    int j=0;
    LinkList *p=L,*S;
   while (jnext; 
     }
     if (p==NULL)
         return false;
     else{
        S=LinkList *)malloc(sizeof(LinkList));
        S->data=e;
        S->next=p->next;
        p->next=S;
        return true;    
     }
   }
13、删除数据元素
 bool ListDelete(LinkList *&L,int i,ElemType &e)
 {
    int j=0;
    LinkList *p=L,*q;
   while(jnext;
     }
    if (p==NULL)
        return false;
    else{
        q=p->next;
        if(q=NULL)
            return false;
        e=q->data;
        p->next=q->next;
        free(q);
        return true;
    }
 }

双链表
1、双向链表的定义和存储结构
 typedef struct DNode
 {
    ElemType data;
    struct DNode *prior;
    struct DNode *next;

 }DLinkList;
2、头插法建立双链表
{
    DLinkList *S;
    int i;
    L=(DLinkList *)malloc(sizeof(DLinkList));
    L->prior=L->next=NULL;
    for(i=0;idata=a[i];
        S->next=L->next;
        if(L->next!=NULL)
            L->next->prior=S;
        L->next=S;
        S->prior=L;
     }
 }
3、尾插法建立双链表
 void CreateListR(DLinkList *&L,ElemType a[],int n)
 {
    DLinkList *s,*r;
    int i;
    L=(DLinkList *)malloc(sizeof(DLinkList));
    r=L;
    for (i=0;idata=a[i];
        r->next=s;
        s->prior=r;
        r=s;
     }
     r->next=NULL;
 }
4、插入节点：
 bool ListInsert(DLinkList *&L,int i,ElemType e)
 {
    int j=0;
    DLinkList *p=L,*s;
   while(jnext;
     }
    if (p=NULL)
        return false;
    else 
    {
        s=(DLink *)malloc(sizeof(DLinkList));
        s->data=e;
        s->next=p->next;
        if (p->next!=NULL)
            P->next->prior=s;
        s->prior=p;
        p->next=s;
        return true;
    }
 }
5、双链表删除节点
 bool ListDelete(DLinkList *&L,int i,ElemType &e)
 {
    int j=0;
    DLinkList *p=L, *q;
   while (jnext; 
     } 
    if (p==NULL)
        return false;
    else
    {
        q=p->next;
        if (q==NULL)
            return false;
        e=q->data;
        p->next=q->next;
        if (p->next!=NULL)
            p->next->prior=p;
        free(q);
        return true;

    }
 }
有序表的操作
1、有序顺序表的插入操作：
 void ListInsert(SqList *&L,ElemType e)
 {
    int i =0,j;
   while (ilength && L->data[i]i;j--)
        L->data[j]=L->data[j-1];
    L->data[i]=e;
    L->length++; 
 }
2、有序链表的插入操作：
 void ListInsert(LinkList *&L,ElemType e)
 {
    LinkList *pre=L, *p;
   while (pre->next!=NULL && pre->next->data < e)
        pre=pre->next;
    p=(LinkList *)malloc(sizeof(LinkList));
    p->data=e;
    p->next=pre->next;
    pre->next=p;
 }
3、采用顺序表存放有序表时的归并算法（将顺序表LA和LB中的元素插入到LC中形成一个新的顺序表）：
void UnionList(SqList *LA,SqList *LB,SqList *&LC)
{
    int i=0,j=0,k=0;
    LC=(SqList *)malloc(sizeof(SqList));

    // LA和LB均未达到末尾时，择其小加入LC
   while(ilength && jlength)
    {
        if(LA->data[i]data[j])
           {
             LC->data[k]=LA->data[i];
             i++;
            }
        else
        {
            LC->data[k]=LB->data[j];
            j++; 
        }
        k++;
    }  

    // LA 尚未扫描完，将其余元素插入LC中
   while(ilength)
    {
        LC->data[k]=LA->data[i];
        i++;
        k++;
     } 

   while(jlength)
    {
        LC->data[k]=LB->data[j];
        j++;
        k++;
    }
}
4、采用单链表存放有序表时的归并算法（将有序链表LA和LB中的元素插入到LC中形成一个新的有序链表）：
void UnionList1(LinkList *LA,LinkList *LB,LinkList *&LC)
{
    LinkList *pa=LA->next, *pb=LB->next, *r,*s;
    LC=(LinkList *)malloc(sizeof(LinkList));
    r=LC;

    // LA 和 LB 均未达到末尾时，择其小优先尾插

   while(pa!=NULL && pb!=NULL)
    {
        S=(LinkList *)malloc(sizeof(LinkList));
        if(pa->datadata)
        {
            s->data=pa->data;
            pa=pa->next;
        }
        else
        {
            s->data=pb->data;
            pb=pb->next;
        }
        r->next=s;
        r=s;
     } 

     // LA 未达到末尾，复制LA中所有结点
    while(pa!=NULL)
     {
        s=(LinkList *)malloc(sizeof(LinkList));
        s->data=pa->data;
        r->next=s;
        r=s;
        pa=pa->next;
      } 

      // LB 未达到末尾，复制LA中所有结点

    while(pb!=NULL)
     {
        s=(LinkList *)malloc(sizeof(LinkList));
        s->data=pb->data;
        r->next=s;
        r=s;
        pb=pb->next;
      } 
}
栈和队列
1、栈的判定：
栈空： top = -1
栈满： top = MaxSize-1
进栈e操作：top ++ ; 将e放在top处
退栈操作：从top处取出元素e; top --;
2、初始化一个空栈s,实际上是将栈顶指针指向-1即可。
// 定义一个顺序栈
typedef struct
{
    ElemType data[MaxSize];
        int top;
}SqStack;

void InitStack(SqStack *&s)
{
  s=(SqStack *)malloc(sizeof(SqStack)); // 申请内存空间
    s->top=-1;
}
3、释放栈s占用的空间，销毁栈：
void DestoryStack(SqStack *&s)
{
    free(s);
}
4、进栈操作push(&s,e)
条件：在栈不满时，可以进栈
操作：
将栈指针+1
在该位置上插入元素e
bool Push(SqStack *&s,ElemType e)
{
    if （s->top==MaxSize-1）
        return false;   // 栈满
        s->top++
        s->data[s->top]=e;
        return true;

}
5、Pop(&s,&e)出栈
条件： 栈不为空
操作：
栈顶元素赋值给e
指针减1
bool Pop(SqStack *&s,ElemType &e)
{

    if (s->top==-1)
            return false;

    e=s->data[s->top];
        s->top--;
        return true;
}
6、用栈判断对称串算法
bool summetry(ElemType str[])
{
    int i;
        ElemType e;
        SqStack *st;
        InitStack(st);

        // 将所有元素进栈

        for (i=0;str[i]!='\0';i++)
            Push(str,str[i]);

        // 出栈的字符与从左向右读取的字符串比较

        for(i=0;str[i]!='\0';i++)
        {
        Pop(st,e);
        if(str[i]!=e)
        {
            DestroyStack(st);
                return false;

        }
        }
DestroyStack(st);
return true;

}

栈的链式存储结构
1、栈的链式存储
 *  采用单链表： 头结点后保存栈顶
 *  优点：不存在栈满上溢的情况
 *  栈空条件： s->next=NULL
定义：
typedef struct linknode
{
    ElemType data;
    struct linknode *next;
 }LiStack;
2、建立一个空栈
void InitStack(LiStack *&s)
{
    s=(LiStack *)malloc(sizeof(LiStack));
    s->next=NULL;
 }
3、释放栈的全部占用空间
 void DetroyStack(LiStack *&s)
 {
    LiStack *p=s, *q=s->next;
   while (q!=NULL)
    {
        free(p);
        p=q;
        q=p->next;
     }
     free(p);
 }
4、判断栈是否为空
 bool StackEmpty(LiStack *S)
 {
    return(s->next==NULL);
 }
5、进栈
 void Push(LiStack *&s,ElemType e)
 {
    LiStack *p;
    p=(LiStack *)malloc(sizeof(LiStack));
    p->data=e;
    p->next=s->next;
    s->next=p;
 }
6、 出栈
 bool Pop(LiStack *&s, ElemType &e)
 {
    LiStack *p;
    if (s->next==NULL)
        return false;
    p=s->next;
    e=p->data;
    s->next=p->next;
    free(p);
    return true;
 }
7、取栈顶元素
 bool GetTop(LiStack *s,ElemType &e)
 {
    if (s->next==NULL)
        return false;
    e=s->next->data;
    return true;
 }
队列
队列的数据操作：
InitQueue(&q): 初始化队列，构造一个新队列
DestroyQueue(&q): 销毁队列。
QueueEmpty(q):判断队列是否为空
enQueue(&q,e): 进队列。将元素e进队，作为队尾元素。
deQueue(&q,&e): 出队列。
队列的存储结构：
数据元素data : 元素具有同一类型ElemType.最多Maxsize
当前队首： front
当前队尾：rear
定义结构：
typedef struct
{
    ElemType data[MaxSize];
    int front,rear; //队首和队尾指针 
 } SqQueue;
1、顺序队的特性
队空条件： front = rear
队满条件： rear = MaxSize - 1
元素e进队： rear ++; data[rear]=e;
元素e出队： front ++; e=data[front];
rear指向队尾元素
front指向队头元素的前一个位置
2、初始化队列
 void InitQueue(SqQueue *&q)
 {
    q=(SqQueue *)malloc(sizeof(SqQueue));
    q->front=q->rear=-1;
  }
3、释放队列q所占的存储空间
  void DestroyQueue(SqQueue *&q)
  {
    free(q);
  }
4、判断队列是否为空QueueEmpty
bool QueueEmpty(SqQueue *q)
{
    return(q->front==q->rear);
}
5、进队列
bool enQueue(SqQueue *&q,ElemType e)
{
    if (q->rear==MaxSize-1)
    return false;
    q->rear++
    q->data[q->rear]=e;
    return true;
}
6、出队列
bool deQueue(SqQueue *&q,ElemType &e)
{
    if (q->front==q->rear)
        return false;
    q->front++;
    e=q->data[q->front];
    return true;
}

提示：顺序队列在满队数据取完后，在队空的情况下会出现front==rear&&  rear = MaxSize - 1的情况，而出现这种情况后，无法再插入数据，这就需要使用环形队列。
环形队列
队空条件： front=rear
队满条件：（rear+1）%MaxSize=front
进队e操作： rear=(rear+1)%MaxSize; 将e放在rear处
处队操作：front=(front+1)%MaxSize; 取出front处元素e;
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
                

                当前文章：数据结构基础（一）-创新互联                

                网站路径：http://myzitong.com/article/dcisoj.html


        
            其他资讯
            
                
                        怎么解决C++异常问题处理
                    

                        Centos命令中nohup的作用是什么
                    

                        python爬虫抓取网页数据的方法
                    

                        HTML怎么画出弧线旋转的图形效果
                    

                        如何配置Kafka集群以使用PAM后端